最適解探索装置
【目的】 線形計画問題解決の処理効率を向上させた最適解探索装置を提供する。
【構成】 区間束縛条件保持手段１、共通束縛条件保持手段２内の区間束縛条件、共通束縛条件を束縛条件とし、目的関数計算手段５で計算された目的関数とともに線形計画問題を線形計画問題解決エンジン部６に渡す。線形計画問題解決エンジン部６では、線形計画問題ステータス保持手段１１内のステータスに基づき、実行可能性判定を省略し、または線形計画問題基底解保持手段８に保持されている基底解を用いて計算する。基底解を計算により求めたときは、隣接問題基底解計算手段７により隣接問題の基底解を計算し、線形計画問題基底解保持手段８に登録する。実行可能性の判定、基底解の計算を行なったときには、線形計画問題ステータス計算手段９は、変更起点リスト１０を用い、他の線形計画問題のステータスを計算し、変更する。
【構成】 区間束縛条件保持手段１、共通束縛条件保持手段２内の区間束縛条件、共通束縛条件を束縛条件とし、目的関数計算手段５で計算された目的関数とともに線形計画問題を線形計画問題解決エンジン部６に渡す。線形計画問題解決エンジン部６では、線形計画問題ステータス保持手段１１内のステータスに基づき、実行可能性判定を省略し、または線形計画問題基底解保持手段８に保持されている基底解を用いて計算する。基底解を計算により求めたときは、隣接問題基底解計算手段７により隣接問題の基底解を計算し、線形計画問題基底解保持手段８に登録する。実行可能性の判定、基底解の計算を行なったときには、線形計画問題ステータス計算手段９は、変更起点リスト１０を用い、他の線形計画問題のステータスを計算し、変更する。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】本発明は、線形計画問題、すなわち、パラメータに関する一次式で示された束縛条件のもとで、同じくパラメータによって定まる目的関数の値を最適にするパラメータの値を計算する最適解探索装置に関するものである。
【０００２】
【従来の技術】一般に、線形計画問題は、種々の条件のもとで最適な状態を得るために用いられる。例えば、損益分岐点の計算や、列車、航空機等の最適運行、生産工程の管理など、幅広い分野で応用されている。
【０００３】従来の線形計画問題を解決する装置の１つとして、複数の部分問題ごとに線形計画問題を解決し、各線形計画問題から得られた局所解を走査して最適解を求める方式が用いられている。以下に、この方式について述べる。
【０００４】区間ごとの束縛条件を与える一次不等式の斉次部を、Ｔ1 ，・・・，Ｔk と表わす。各Ｔi は、パラメータｘ1 ，・・・，ｘm に関する一次式ｐi,1 ｘ1 ＋・・・ｐi,m ｘmである。
【０００５】各斉次一次関数Ｔｉには、単調増加数列ｓi,1 ，・・・，ｓi,k(i)が固有に与えられている。これを区間特性列と呼ぶ。ここで、ｋ（ｉ）は、ｋi を表わす。添字の添字が表現できないため、以下、このような表記を用いる。
【０００６】この区間特性列を用い、１≦ｊi ≦ｋi −１を満たす任意のｊi に対して、一次不等式ｓi,j(i)≦ｐi,1 ｘ1 ＋・・・ｐi,m ｘm ≦ｓi,j(i)+1が、区間束縛条件の１つとなる。
【０００７】ここで、各斉次一次関数Ｔi に対してｊi ∈｛１，・・・，ｋi −１｝を一つずつ定めて、連立一次不等式ｐ1,1 ｘ1 ＋・・・＋ｐ1,m ｘm ≧ｓ1,j(1)ｐ1,1 ｘ1 ＋・・・＋ｐ1,m ｘm ≦ｓ1,j(1)+1・・・ｐk,1 ｘ1 ＋・・・＋ｐk,m ｘm ≧ｓk,j(k)ｐk,1 ｘ1 ＋・・・＋ｐk,m ｘm ≦ｓk,j(k)+1が区間束縛条件の組である。この連立一次不等式は、すべての（ｊ1 ，・・・，ｊk ）∈［１，・・・，ｋ1 −１］×・・・×［１，・・・，ｋk −１］に対して作成される。
【０００８】この連立一次不等式を１組ずつ取り出してきて、それをもとに１つずつ線形計画問題を定義する。この線形計画問題をｊ1 ，・・・，ｊk が定める線形計画問題（単純に（ｊ1 ，・・・，ｊk ）−問題）と呼ぶ。（ｊ1 ，・・・，ｊk ）−問題の束縛条件および目的関数について述べる。ユーザは、ｊ1 ，・・・，ｊk によらないパラメータに関する一次方程式または一次不等式の組（以下、共通束縛条件と呼ぶ）を指定することができる。これらの共通束縛条件は、必要ならばスラック変数を用いて一次方程式の形式で表現することができる。すなわち、共通束縛条件をｐ'1,1ｘ1 ＋・・・＋ｐ'1,mｘm ＝ｓ'1・・・ｐ'k',1 ｘ1 ＋・・・＋ｐ'k',m ｘm ＝ｓ'k'であるものとする。
【０００９】スラック変数は、例えば、ｐ'i,1ｘ1 ＋・・・＋ｐ'i,mｘm ≦ｓ'iのときは、スラック変数ｕi （≧０）を用いて、ｐ'i,1ｘ1 ＋・・・＋ｐ'i,mｘm ＋ｕi ＝ｓ'iとすることができる。一方、ｐ'i,1ｘ1 ＋・・・＋ｐ'i,mｘm ≧ｓ'iのときは、スラック変数ｕi （≧０）を用いて、ｐ'i,1ｘ1 ＋・・・＋ｐ'i,mｘm −ｕi ＝ｓ'iとすることができる。
【００１０】区間束縛条件である連立一次不等式の組と、共通束縛条件である連立一次方程式とを連立させたものが、（ｊ1 ，・・・，ｊk ）−問題の束縛条件となる。すなわち、
【数１】
と同値である。この線形方程式を、（ｊ1 ，・・・，ｊk ）−問題の束縛条件と呼ぶ。一般性を失うことなく全てのパラメータは非負の値を取るものと仮定できるので、以下の説明においてはｘi ≧０，ｙi ≧０，ｚi ≧０であるものとする。
【００１１】さて、最適解を評価するための物理量は目的関数で与えられる。物理量は必ずしもパラメータの一次関数で与えられるとは限らないが、束縛斉次一次関数とその区間特性列を適切に与えることにより、パラメータが１つの区間束縛条件の組を満たしている場合に、目的関数が一次関数になるような例が知られている。例えば、表の割付を行なう際に、各欄に割り付けられるテキストの行折りが一定になるように定め、目的関数を表の割付面積とすると、その行折りの一定の区間においては目的関数はパラメータの一次関数となる。このように、区分的に線形関数となる物理量を、目的関数として求める。ここでは、（ｊ1 ，・・・，ｊk ）−問題の目的関数は、ｊ1 ，・・・，ｊk に依存して定まる線形関数ｖ1 ｘ1 ＋・・・＋ｖm ｘmであるものとする。
【００１２】以上のようにして取得した連立一次不等式をもとに、（ｊ1 ，・・・，ｊk ）−問題を完成させる。完成された（ｊ1 ，・・・，ｊk ）−問題は、（１）線形計画問題が実行不可能である、すなわち、線形計画問題の束縛条件を満たすようなパラメータの値が存在しないことを確かめるか、（２）線形計画問題の束縛条件を満たすパラメータの値で、目的関数を最小（最大）にするものを求めることによって解決される。そのための処理として、以下のような処理を行なう。
【００１３】まず、（ｊ1 ，・・・，ｊk ）−問題の実行可能性を、線形計画法を用いて判定する。（ｊ1 ，・・・，ｊk ）−問題が実行不可能である場合は、その旨を出力して処理を終了する。
【００１４】実行可能である場合は、（ｊ1 ，・・・，ｊk ）−問題に関する最初の実行可能基底を掃き出し法などを用いて計算し、計算した実行可能基底に属するパラメータの値を最初の基底解とする。現在の基底解が目的関数の最小値（最大値）を与えているときには、計算された目的関数の最小値（最大値）と、属する基底解（最適パラメータ）の情報を併せて出力し、処理を終了する。
【００１５】基底解が目的関数の最小値（最大値）を与えないときには、ピボット変換を用いて新たな実行可能基底と、新たな基底解を計算し、最小値（最大値）が与えられるまで、基底解の評価と新たな実行可能基底、基底解の計算を繰り返す。上述の（ｊ1 ，・・・，ｊk ）−問題を解決する処理を、全ての（ｊ1 ，・・・，ｊk ）∈［１，・・・，ｋ1 −１］×・・・×［１，・・・，ｋk −１］に対して行なう。全ての線形計画問題を解決し終わると、各（ｊ1 ，・・・，ｊk）−問題を解決して得られた局所最適解を走査して、目的関数の値が最良値（最小値または最大値）となるものを探索し、対応するパラメータの値の組を最適解とする。
【００１６】上述の方式では、各（ｊ1 ，・・・，ｊk ）−問題について、それぞれ、線形計画問題を解決する処理を行なっている。１つの線形計画問題を解決するだけでも、多くの時間を要するため、全体として最適解を得るために、非常に時間がかかってしまい、効率の点で難点があった。
【００１７】
【発明が解決しようとする課題】本発明は、上述した事情に鑑みてなされたもので、処理効率を向上させた最適解探索装置を提供することを目的とするものである。
【００１８】
【課題を解決するための手段】本発明は、請求項１に記載の発明においては、複数の線形計画問題から構成される複合線形計画問題の最適解を計算する最適解探索装置において、複数のパラメータに関する有限個の斉次一次関数を保持するとともに各斉次一次関数に付随する２個以上の実数からなる単調増加数列であって斉次一次関数の上限と下限を隣接する実数として有する区間特性列を保持する区間束縛条件保持手段と、常にパラメータ間に成立すべき一次方程式または一次不等式を共通束縛条件として保持する共通束縛条件保持手段と、前記区間束縛条件保持手段に保持されている各斉次一次関数の区間特性列から隣接する２個の実数を選択して得られる束縛条件の組ごとにパラメータに関する一次式として目的関数を計算する目的関数計算手段と、該目的関数計算手段で計算された目的関数と該目的関数に対応する束縛条件の組および前記共通束縛条件保持手段に保持されている共通束縛条件等からなる線形計画問題を実行可能基底および基底解を計算しながら解決する線形計画問題解決エンジン部と、線形計画問題解決エンジン部が実行可能基底と基底解を計算するたびに計算された実行可能基底を挟んで隣接する線形計画問題の実行可能基底と基底解を計算する隣接問題基底解計算手段と、計算済みの実行可能基底および基底解を線形計画問題と対応づけて保持する線形計画問題基底解保持手段と、前記区間束縛条件保持手段と前記共通束縛条件保持手段と前記目的関数計算手段と前記線形計画問題解決エンジン部を制御し前記線形計画問題解決エンジン部から前記束縛条件の組ごとに得られた結果をもとに最適値を探索する線形計画問題管理手段を有し、前記線形計画問題解決エンジン部が新たに線形計画問題を解きはじめる際に、前記線形計画問題基底解保持手段に解くべき線形計画問題に対応する実行可能基底と基底解が存在すれば、その実行可能基底と基底解を用いて計算を開始することを特徴とするものである。
【００１９】また、請求項２に記載の発明においては、複合線形計画問題の最適解を計算する最適解探索装置において、複数のパラメータに関する有限個の斉次一次関数を保持するとともに各斉次一次関数に付随する２個以上の実数からなる単調増加数列であって斉次一次関数の上限と下限を隣接する実数として有する区間特性列を保持する区間束縛条件保持手段と、常にパラメータ間に成立すべき一次方程式または一次不等式を共通束縛条件として保持する共通束縛条件保持手段と、前記区間束縛条件保持手段に保持されている各斉次一次関数の区間特性列から隣接する２個の実数を選択して得られる束縛条件の組ごとにパラメータに関する一次式として目的関数を計算する目的関数計算手段と、前記束縛条件の組ごとに導出される線形計画問題それぞれに対して、少なくとも「実行可能である」、「実行不可能である」、「実行可能性が未知である」を指示するステータスを保持する線形計画問題ステータス保持手段と、前記目的関数計算手段で計算された目的関数と該目的関数に対応する束縛条件の組および前記共通束縛条件保持手段に保持されている共通束縛条件等からなる線形計画問題について実行可能性を判断して前記線形計画問題ステータス保持手段に保持されている該線形計画問題のステータスを変更した上で該線形計画問題を解決する線形計画問題解決エンジン部と、該線形計画問題解決エンジン部が各線形計画問題についてその実行可能性を判定するたびに該線形計画問題のステータスの変化がもたらす他の線形計画問題のステータスの変化を再計算し前記線形計画問題ステータス保持手段に保持されているステータスを変更する線形計画問題ステータス計算手段と、前記区間束縛条件保持手段と前記共通束縛条件保持手段と前記目的関数計算手段と前記線形計画問題解決エンジン部を制御し前記線形計画問題解決エンジン部から前記束縛条件の組ごとに得られた結果をもとに最適値を探索する線形計画問題管理手段を有し、前記線形計画問題解決エンジン部が線形計画問題を解く際に、前記線形計画問題ステータス保持手段に保持されているステータスを参照し、少なくとも「実行可能性が未知である」ステータス以外の場合には、該線形計画問題の実行可能性の判定処理を行なわないことを特徴とするものである。
【００２０】さらに、請求項３に記載の発明においては、複合線形計画問題の最適解を計算する最適解探索装置において、複数のパラメータに関する有限個の斉次一次関数を保持するとともに各斉次一次関数に付随する２個以上の実数からなる単調増加数列であって斉次一次関数の上限と下限を隣接する実数として有する区間特性列を保持する区間束縛条件保持手段と、常にパラメータ間に成立すべき一次方程式または一次不等式を共通束縛条件として保持する共通束縛条件保持手段と、前記区間束縛条件保持手段に保持されている各斉次一次関数の区間特性列から隣接する２個の実数を選択して得られる束縛条件の組ごとにパラメータに関する一次式として目的関数を計算する目的関数計算手段と、前記束縛条件の組ごとに導出される線形計画問題それぞれに対して、少なくとも「解決済みである」、「基底解保持済みである」、「実行可能である」、「実行不可能である」、「実行可能性が未知である」を指示するステータスを保持する線形計画問題ステータス保持手段と、前記目的関数計算手段で計算された目的関数と該目的関数に対応する束縛条件の組および前記共通束縛条件保持手段に保持されている共通束縛条件等からなる線形計画問題の実行可能性の判定および実行可能基底と基底解の計算を行ない各処理において前記線形計画問題ステータス保持手段に保持されているステータスを変更しながら線形計画問題を解決する線形計画問題解決エンジン部と、該線形計画問題解決エンジン部が実行可能基底と基底解を計算するたびに計算された実行可能基底を挟んで隣接する線形計画問題の実行可能基底と基底解を計算するとともに前記線形計画問題ステータス保持手段に保持されている該隣接問題のステータスを変更する隣接問題基底解計算手段と、計算済みの実行可能基底および基底解を保持する線形計画問題基底解保持手段と、前記線形計画問題解決エンジン部および前記隣接問題基底解計算手段の処理に従い線形計画問題のステータスの変化がもたらす他の線形計画問題のステータスの変化を再計算し前記線形計画問題ステータス保持手段に保持されているステータスを変更する線形計画問題ステータス計算手段と、前記区間束縛条件保持手段と前記共通束縛条件保持手段と前記目的関数計算手段と前記線形計画問題解決エンジン部を制御し前記線形計画問題解決エンジン部から前記束縛条件の組ごとに得られた結果をもとに最適値を探索する線形計画問題管理手段を有し、前記線形計画問題解決エンジン部が線形計画問題を解く際に、前記線形計画問題ステータス保持手段に保持されているステータスを参照し、少なくとも「実行可能性が未知である」ステータス以外の場合には該線形計画問題の実行可能性の判定処理を行なわず、ステータスが「基底解保持済みである」ことを示している場合には前記線形計画問題基底解保持手段から実行可能基底と基底解を得て計算を開始することを特徴とするものである。
【００２１】前記請求項２または３に記載の最適解探索装置において、前記線形計画問題ステータス保持手段に保持されたステータスは優先順位を持っており、前記線形計画問題管理手段は、該ステータスの優先順位に基づいて線形計画問題を解く順序を決定するように構成することができる。
【００２２】
【作用】区間束縛条件保持手段に区間束縛条件が保持され、共通束縛条件保持手段に共通束縛条件が保持される。また、目的関数計算手段により目的関数が計算される。ここで、（ｊ1 ，・・・，ｊk ）−問題を特定し、線形計画問題解決エンジン部に渡される。（ｊ1 ，・・・，ｊk ）−問題を解くに当たって、実行可能基底（Ｊ）と基底解（ξX ）（ここでＸ∈Ω）が得られたとする。ここで、Ω＝｛ｘ1 ，・・・，ｘm ，ｙ1 ，ｚ1 ，・・・，ｙk ，ｚk ｝、Ｊ⊂Ωである。
【００２３】行列
【数２】
中の変数Ｘ∈Ωに対応する列ベクトルをｖX と表わす。すなわち、ｖx(i)は第ｉ列、ｖy(i)は第ｍ＋２ｉ−１列、ｖz(i)は第ｍ＋２ｉ列を表わす。
【００２４】（Ｊ）が実行可能基底であるとは、｛ｖX ｝（Ｘ∈Ｊ）が、｛ｖX ｝（Ｘ∈Ω）が張る線形空間の基底であり、対応する基底解
【数３】
が存在して、束縛条件
【数４】
を満たすことである。ここで、実行可能基底に対して、対応する基底解は一意である。
【００２５】このとき、以下の性質が成り立つ。
（１）ξy(i)＝０が成り立つとき、（ｊ1 ，・・・，ｊi-1 ，ｊi ＋１，ｊi+1 ，・・・，ｊk ）−問題は実行可能であり、以下が成り立つ。
・Ｊ∋ｙi なら、（Ｊ）は実行可能基底である。
・Ω＼Ｊ∋ｙi ならば、（Ｊ∪｛ｙi ｝＼｛ｚi ｝）は実行可能基底である。
・（ξ'X）（Ｘ∈Ω）は基底解である。
【数５】
このとき、（ｊ1 ，・・・，ｊi-1 ，ｊi ＋１，ｊi+1 ，・・・，ｊk ）−問題を、実行可能基底（Ｊ）を挟んで（ｊ1 ，・・・，ｊi-1 ，ｊi ，ｊi+1 ，・・・，ｊk ）−問題と隣接しているという。
（２）ξz(i)＝０が成り立つとき、（ｊ1 ，・・・，ｊi-1 ，ｊi −１，ｊi+1 ，・・・，ｊk ）−問題は実行可能であり、以下が成り立つ。
・Ｊ∋ｚi なら、（Ｊ）は実行可能基底である。
・Ω＼Ｊ∋ｙi ならば、（Ｊ∪｛ｚi ｝＼｛ｙi ｝）は実行可能基底である。
・（ξ'X）（Ｘ∈Ω）は基底解である。
【数６】
このとき、（ｊ1 ，・・・，ｊi-1 ，ｊi −１，ｊi+1 ，・・・，ｊk ）−問題を、実行可能基底（Ｊ）を挟んで（ｊ1 ，・・・，ｊi-1 ，ｊi ，ｊi+1 ，・・・，ｊk ）−問題と隣接しているという。
【００２６】請求項１に記載の発明では、隣接問題基底計算手段は、線形計画問題解決エンジン部が線形計画問題の実行可能基底と基底解を計算する度に、その実行可能基底を挟んで隣接する線形計画問題がすでに線形計画問題基底解保持手段に保持されているかを調べ、保持されていない場合には、該隣接線形計画問題の実行可能基底と基底解を上述の性質にしたがって計算して、線形計画問題基底解保持手段に登録する。
【００２７】線形計画問題解決エンジン部が新たに線形計画問題を解くときには、まず、線形計画問題基底解保持手段に該線形計画問題が登録されているかを調べ、もし登録されているならば、登録されている実行可能基底と基底解を用いて計算を開始する。これにより、線形計画問題解決エンジン部で行なわれる実行可能性判定と初期実行可能基底探索のステップを省略することができる。
【００２８】また、各（ｊ1 ，・・・，ｊk ）−問題には、次のような性質がある。特定の一つの斉次一次関数Ｔi に関する区間束縛条件が異なる２つの線形計画問題、（ｊ1 ，・・・，ｊi-1 ，ｊi ，ｊi+1 ，・・・，ｊk ）−問題と、（ｊ1 ，・・・，ｊi-1 ，ｊ'i，ｊi+1 ，・・・，ｊk ）−問題について、以下の性質が成り立つ。ただし、ｊi ＜ｊ'iが成り立つものとする。
性質１）（ｊ1 ，・・・，ｊi-1 ，ｊi ，ｊi+1 ，・・・，ｊk ）−問題と（ｊ1 ，・・・，ｊi-1 ，ｊ'i，ｊi+1 ，・・・，ｊk ）−問題の双方が実行可能であるとき、任意のｊi ≦ｊ≦ｊ'iに対して、（ｊ1 ，・・・，ｊi-1 ，ｊ，ｊi+1 ，・・・，ｊk ）−問題は実行可能である。
性質２）（ｊ1 ，・・・，ｊi-1 ，ｊi ，ｊi+1 ，・・・，ｊk ）−問題が実行可能であり、（ｊ1 ，・・・，ｊi-1 ，ｊ'i，ｊi+1 ，・・・，ｊk ）−問題が実行不可能であるとき、任意のｊ≧ｊ'iに対して、（ｊ1 ，・・・，ｊi-1 ，ｊ，ｊi+1 ，・・・，ｊk ）−問題は実行不可能である。
性質３）（ｊ1 ，・・・，ｊi-1 ，ｊi ，ｊi+1 ，・・・，ｊk ）−問題が実行不可能であり、（ｊ1 ，・・・，ｊi-1 ，ｊ'i，ｊi+1 ，・・・，ｊk ）−問題が実行可能であるとき、任意のｊ≦ｊi に対して、（ｊ1 ，・・・，ｊi-1 ，ｊ，ｊi+1 ，・・・，ｊk ）−問題は実行不可能である。
【００２９】線形計画問題解決エンジン部は、線形計画問題の実行可能性を判定する度に、判定結果に応じて、「実行可能である」、「実行不可能である」のいずれかを指示するステータスを線形計画問題ステータス保持手段２２中に、線形計画問題に対応付けて登録する。
【００３０】線形計画問題ステータス計算手段は、ある線形計画問題のステータスの登録によって、上述の性質１）ないし性質３）からその実行可能性が判定できるすべての線形計画問題について、そのステータスを計算し、登録する。
【００３１】線形計画問題ステータス計算手段によって実行可能性が判定され、「実行可能である」、「実行不可能である」のいずれかのステータスが新たに付与される線形計画問題が存在すれば、その線形計画問題のステータスの登録によって、さらに実行可能性が判定できる線形計画問題が存在するかもしれない。線形計画問題ステータス計算手段は、このような線形計画問題が存在しなくなるまで、上記の手続きを繰り返す。
【００３２】請求項２に記載の発明では、この線形計画問題ステータス保持手段と、線形計画問題ステータス計算手段により、一部の線形計画問題の実行可能性を、線形計画法のプログラムを用いることなく知ることができ、「実行可能性が未知である」線形計画問題についてのみ、線形計画法を用いて実行可能性を検証すればよい。特に、線形計画問題管理手段は、線形計画問題ステータス計算手段によって「実行不可能である」ことを指示するステータスを付与された線形計画問題を除外して処理を進めることにより、処理の効率を向上させることができる。
【００３３】線形計画問題のステータスをさらに詳細に設定することができる。例えば、請求項３に記載の発明のように、請求項１に記載の隣接問題基底解計算手段および線形計画問題基底解保持手段を用い、線形計画問題のステータスとして、「実行可能である」、「実行不可能である」、「実行可能性が未知である」に加えて、「解決済みである」並びに「基底解が与えられている」ことを指示するステータスを設定することができる。
【００３４】「実行可能である」ことを示すステータスが設定された線形計画問題は、その実行可能性が線形計画法の処理により判定されたものではなく、線形計画問題ステータス計算手段によって、他の線形計画問題のステータスから計算されている線形計画問題である。「基底解が与えられている」ことを示すステータスが設定された線形計画問題は、隣接問題基底解計算手段によって、隣接する線形計画問題の実行可能基底と基底解から、その線形計画問題の実行可能基底と基底解が計算されている線形計画問題である。「実行不可能である」ことを示すステータスが設定された線形計画問題は、その実行不可能性が、線形計画法を用いて判定されたか、または、前記の線形計画問題ステータス計算手段によって他の線形計画問題のステータスから計算された線形計画問題である。実行可能な線形計画問題を線形計画問題解決エンジン部が解決すると、該線形計画問題のステータスは「解決済みである」に設定される。
【００３５】このような構成により、線形計画問題解決エンジン部は、解決する線形計画問題に対応したステータスを参照することにより、実行可能性の検証、あるいは、実行可能性の検証と実行可能基底および基底解の計算を省略することができ、効率の向上を図ることができる。
【００３６】請求項４に記載の発明において、ステータスに優先順位を付けることにより、線形計画問題管理手段における線形計画問題の選択を効率よく行なうことが可能となる。例えば、請求項３に記載の発明のように、５種類のステータスを有する場合、以下のように線形計画問題を選択することによって、処理の効率化を図ることができる。
（１）「基底解が与えられている」ことを示すステータスが設定された線形計画問題が存在すれば、それを取得する。
（２）「基底解が与えられている」ことを示すステータスが設定されている線形計画問題が存在しない場合、「実行可能である」ことを示すステータスが設定された線形計画問題が存在すれば、それを取得する。
（３）「基底解が与えられている」および「実行可能である」ことを示すステータスが設定された線形計画問題が存在しない場合、「実行可能性が未知である」線形計画問題を取得する。
【００３７】「基底解が与えられている」ことを示すステータスが設定された線形計画問題は、線形計画法のプログラム中の実行可能性の判定処理を省略することができるので、効率良く解を得ることができる。また、計算の途中で中間的に得られる基底解から、隣接する線形計画問題の基底解が得られるので、「基底解が与えられている」ことを示すステータスが設定された線形計画問題を優先的に解くことにより、他の線形計画問題の解決の効率を向上させる。この効果は、連鎖的である。すなわち、「基底解が与えられている」ことを示すステータスが設定された線形計画問題を解決することにより、「基底解が与えられている」ことを示すステータスが設定された線形計画問題が増殖していくという効果が得られる。
【００３８】「実行可能である」ことを示すステータスが設定された線形計画問題は、実行可能性の判定処理を省略することができる。ただし、「基底解が与えられている」ことを示すステータスが設定された線形計画問題とは異なり、問題自身を解決するためには線形計画法のプログラムのすべてのステップを実行しなければならないが、隣接する線形計画問題の基底解を与えるという点では、「基底解が与えられている」ことを示すステータスが設定された線形計画問題を解く場合と同様である。したがって、「実行可能である」ことを示すステータスが設定された線形計画問題を優先的に解くことにより、やはり、「基底解が与えられている」ことを示すステータスが設定された線形計画問題が連鎖的に増殖していくという効果が得られる。
【００３９】このように、線形計画問題管理手段が線形計画問題ステータス保持手段に保持されているステータスに応じて、線形計画問題解決エンジン部に引き渡す線形計画問題を計画的に選択することによって、処理の効率を向上させることができる。
【００４０】
【実施例】図１は、本発明の最適解探索装置の一実施例を示す構成図である。図中、１は区間束縛条件保持手段、２は共通束縛条件保持手段、３は線形計画問題管理手段、４は局所最適解リスト、５は目的関数計算手段、６は線形計画問題解決エンジン部、７は隣接問題基底解計算手段、８は線形計画問題基底解保持手段、９は線形計画問題ステータス計算手段、１０は変更起点リスト、１１は線形計画問題ステータス保持手段である。
【００４１】区間束縛条件保持手段１には、インデックスｉ∈｛１，・・・，ｋ｝に対応付けて、束縛条件の係数ベクトル（ｐi,1 ，・・・，ｐi,m ）と、境界特性列ｓi,1 ＜ｓi,2 ＜・・・＜ｓi,k(i)が保持されている。
【００４２】共通束縛条件保持手段２には、区間束縛条件に関わらずパラメータを用いた一次方程式の共通束縛条件がリストとして保持されている。共通束縛条件が一次不等式である場合には、スラック変数を用いて一次方程式に変形することができるので、以下の説明では共通束縛条件保持手段２に保持される共通束縛条件は、あらかじめ一次方程式の形に変形されているものとする。共通束縛条件保持手段に保持される束縛条件を、ｐ'i,1ｘ1 ＋・・・＋ｐ'i,mｘm ＝ｓ'iと表わす。ただし、１≦ｉ≦ｋ’とする。
【００４３】線形計画問題管理手段３は、（ｊ1 ，・・・，ｊk ）−問題を特定し、各インデックスｉに対応するｊi 、あるいは、必要ならば、区間束縛条件保持手段１に保持されている境界特性列中の隣接する境界値の組（ｓj(1)，ｓj(1)+1），（ｓj(2)，ｓj(2)+1），・・・，（ｓj(k)，ｓj(k)+1）を目的関数計算手段５に渡し、目的関数ｖ1 ｘ1 ＋・・・＋ｖm ｘmを得る。この（ｊ1 ，・・・，ｊk ）−問題の特定には、線形計画問題ステータス保持手段１１に保持されているステータスを参照し、「基底解が与えられている」線形計画問題を選択し、なければ、「実行可能である」線形計画問題を選択し、なければ、「実行可能性が未知である」線形計画問題を選択する。
【００４４】目的関数計算手段５から得られる目的関数と、区間束縛条件保持手段１に保持されている区間束縛条件、共通束縛条件保持手段２に保持されている共通束縛条件を線形計画問題解決エンジン部６に渡し、線形計画問題を解く。解くべき線形計画問題は、各インデックスｉに対してｊi ∈｛１，・・・，ｋi −１｝を１つずつ定めることにより特定される（ｊ1 ，・・・，ｊk ）−問題である。この線形計画問題は、すべての（ｊ1 ，・・・，ｊk ）∈［１，・・・，ｋ1 −１］×・・・×［１，・・・，ｋk −１］について存在する。線形計画問題解決エンジン部６からは、渡した線形計画問題の最小値（最大値）と、その最小値（最大値）を与える最適パラメータの値との組、あるいは、線形計画問題が実行不可能である旨の情報が返される。各（ｊ1 ，・・・，ｊk ）−問題を線形計画問題解決エンジン部６で解いて得られた局所解は、局所最適解リスト４に記録する。すべての（ｊ1 ，・・・，ｊk ）−問題が解決すると、局所最適解リスト４を走査し、全体の最適解を得る。
【００４５】局所最適解リスト４には、線形計画問題解決エンジン部６から返される線形計画問題の最小値（最大値）と、その最小値（最大値）を与える最適パラメータの値との組を順次保持する。
【００４６】目的関数計算手段５は、線形計画問題管理手段３が特定した（ｊ1 ，・・・，ｊk ）−問題の目的関数として、区間束縛条件保持手段１に保持されている区間束縛条件に基づき、ｊ1 ，・・・，ｊk に依存して定まる線形関数ｖ1 ｘ1 ＋・・・＋ｖm ｘmを求める。
【００４７】線形計画問題解決エンジン部６は、線形計画問題管理手段３から目的関数、区間束縛条件、共通束縛条件を受け取り、線形計画問題である（ｊ1 ，・・・，ｊk ）−問題を解決して、その線形計画問題の最小値（最大値）と、その最小値（最大値）を与える最適パラメータの値との組、あるいは、線形計画問題が実行不可能である旨の情報を返す。線形計画問題の解決は、まず、実行可能性を検証する。そして、実行可能である線形計画問題について、実行可能基底、基底解を求め、例えば、終了条件として単体法の単体基準Ｉおよび単体基準ＩＩを満たしたならば最適解として抽出し、終了条件を満たさないときは、ある特定の方法（例えば、単体基準ＩＩＩ）にしたがって新たな単体表を計算し（ピボッド変換）、さらに、終了条件を調べる。
【００４８】隣接問題基底解計算手段７は、線形計画問題解決エンジン部６が線形計画問題の実行可能基底と基底解を計算する度に、その実行可能基底を挟んで隣接する線形計画問題がすでに線形計画問題基底解保持手段８に保持されているかを調べ、保持されていない場合には、該隣接線形計画問題の実行可能基底と基底解を計算して、線形計画問題基底解保持手段８に登録する。
【００４９】線形計画問題基底解保持手段８は、（ｊ1 ，・・・，ｊk ）−問題に対して、その実行可能基底、基底解、実行可能基底に属する単体表主要部を対応付けて保持する。線形計画問題基底解保持手段８に保持される線形計画問題のステータスは、ＲＥＡＤＹまたはＳＯＬＶＥＤのいずれかである。ただし、ＲＥＡＤＹおよびＳＯＬＶＥＤは、上述の「基底解保持済みである」、「解決済みである」の各ステータスに相当する。
【００５０】実行可能基底に属する単体表主要部とは、（ｊ1 ，・・・，ｊk ）−問題の束縛条件行列
【数７】
を基底｛ｖX ｝（ｘ∈Ｊ）に関して基底変換して得られるｒ行２ｋ＋ｍ列の行列［ｑi,j ］である。Ｊ＝｛Ｘ1 ，・・・，Ｘr ｝とすると、ｑi,j はもとの束縛条件行列中のｊ番目の列ベクトルｖj の列ベクトルｖX(i)に対する相対成分である。すなわち、一意な一次結合ｖj ＝ｑi,j ｖX(1)＋・・・＋ｑr,j ｖX(r)が成り立つ。ここで、ｒは束縛条件行列のランクである。ここで、束縛条件の右辺（単体表の非斉次部分）である列ベクトルを、基底（ｖX ）（Ｘ∈Ｊ）の一次結合
【数８】
と表わすとき、連立一次方程式
【数９】
は、もとの束縛条件と同値な束縛条件を与える。
【００５１】線形計画問題ステータス計算手段９は、変更起点リスト１０に登録されている線形計画問題を先頭から順次取り出し、取り出した線形計画問題を起点として、上述の作用の項で説明した性質１）ないし性質３）から、その実行可能性が判定できるすべての線形計画問題について、そのステータスを計算し、線形計画問題ステータス保持手段１１内のステータスを変更する。それとともに、ステータスを変更した線形計画問題を変更起点リスト１０の最後尾に追加登録する。
【００５２】変更起点リスト１０には、隣接問題基底解計算手段７および線形計画問題ステータス計算手段９で線形計画問題ステータス保持手段１１内のステータスを変更するごとに、ステータスが変更された（ｊ1 ，・・・，ｊk ）−問題が登録される。
【００５３】線形計画問題ステータス保持手段１１は、各（ｊ1 ，・・・，ｊk ）−問題に対して、ＵＮＫＮＯＷＮ，ＦＥＡＳＩＢＬＥ，ＩＮＦＥＡＳＩＢＬＥ，ＲＥＡＤＹ，ＳＯＬＶＥＤのいずれかのステータスを対応付けて保持する。これらのステータスは、上述の「実行可能性が未知である」、「実行可能である」、「実行不可能である」、「基底解が与えられている」、「解決済みである」の各ステータスに相当する。初期状態においては、全ての問題のステータスはＵＮＫＮＯＷＮである。
【００５４】図２は、本発明の最適解探索装置の一実施例における処理の一例を示すフローチャートである。初期情報として、区間束縛条件保持手段１および共通束縛条件保持手段２には、それぞれ、区間束縛条件、共通束縛条件が格納されているものとする。
【００５５】Ｓ１０１において、線形計画問題管理手段３は、線形計画問題解決エンジン部６に引き渡すべき線形計画問題、すなわち、（ｊ1 ，・・・，ｊk ）−問題を特定する。Ｓ１０２において、線形計画問題管理手段３は、選択された（ｊ1 ，・・・，ｊk ）−問題を線形計画問題として完成させる。Ｓ１０３において、線形計画問題解決エンジン部６は、与えられた線形計画問題を解く。Ｓ１０４において、線形計画問題管理手段３は、線形計画問題解決エンジン部６からの返り値が最適パラメータと目的関数の最小値（最大値）である場合には、線形計画問題と対応付けて局所最適解リスト４に付け加えた後、Ｓ１０１へ戻り、手続きを繰り返す。線形計画問題解決エンジン部６からの返り値が、線形計画問題が実行不可能であることを報告するものである場合には、何もせず、Ｓ１０１へ戻り、手続きを繰り返す。
【００５６】この処理をすべての（ｊ1 ，・・・，ｊk ）−問題について繰り返し行なうことにより、局所最適解リスト４には、解決した（ｊ1 ，・・・，ｊk ）−問題の最適解およびそのときのパラメータが蓄積されている。線形計画問題管理手段３は、この局所最適解リスト４を走査し、最小の解を求める。これにより、区間束縛条件、共通束縛条件を満たす最適解が得られたことになる。
【００５７】以下、Ｓ１０１ないしＳ１０３の各ステップの詳細な処理について説明する。図３は、線形計画問題の特定処理の一例を示すフローチャートである。線形計画問題管理手段３は、以下の手続きを経て、線形計画問題解決エンジン部６に引き渡すべき線形計画問題を特定する。
【００５８】Ｓ１１１において、ＲＥＡＤＹ状態の線形計画問題が線形計画問題ステータス保持手段１１に登録されていれば、Ｓ１１２においてそれを取得する。
【００５９】Ｓ１１３において、ＲＥＡＤＹ状態の線形計画問題が線形計画問題ステータス保持部２２に登録されていない場合、ＦＥＡＳＩＢＬＥ状態の線形計画問題が線形計画問題ステータス保持手段１１に登録されていれば、Ｓ１１４においてそれを取得する。
【００６０】Ｓ１１５において、ＲＥＡＤＹ状態の線形計画問題、ＦＥＡＳＩＢＬＥ状態の線形計画問題のいずれも線形計画問題ステータス保持手段１１に登録されていない場合、ＵＮＫＮＯＷＮ状態の線形計画問題が線形計画問題ステータス保持手段１１に登録されていれば、Ｓ１１６においてそれを取得する。
【００６１】Ｓ１１７において、線形計画問題ステータス保持手段１１に登録されている全ての線形計画問題のステータスがＩＮＦＥＡＳＩＢＬＥ，ＳＯＬＶＥＤのいずれかであるか調べ、そうであるときにはＳ１１８の処理を行ない、少なくとも１つの線形計画問題のステータスがＲＥＡＤＹ，ＦＥＡＳＩＢＬＥ，ＵＮＫＮＯＷＮのいずれかであるときには、Ｓ１１２またはＳ１１４またはＳ１１６で線形計画問題が選択されているので、線形計画問題管理手段３による線形計画問題を特定する処理を終了し、次の線形計画問題を完成させる処理に移る。
【００６２】Ｓ１１７において、線形計画問題ステータス保持手段１１に登録されている全ての線形計画問題のステータスがＩＮＦＥＡＳＩＢＬＥ，ＳＯＬＶＥＤとなると、Ｓ１１８において、線形計画問題管理手段３は、局所最適解リスト４を走査して、登録された目的関数の最小値あるいは最大値の中から、大域的な最小値あるいは最大値を探す。次いで、探した最小値あるいは最大値を与える線形計画問題と最適パラメータを取得する。この最適パラメータが、得ようとする線形計画問題全体の最適解である。このＳ１１８の処理の後、本発明の最適解探索装置の処理を終了する。
【００６３】図４は、線形計画問題を完成させる処理の一例を示すフローチャートである。線形計画問題管理手段３は、図３で説明した線形計画問題の選択処理によって選択された線形計画問題、すなわち、（ｊ1 ，・・・，ｊk ）−問題を以下の手続きによって線形計画問題として完成する。
【００６４】Ｓ１２１において、特定された（ｊ1 ，・・・，ｊk ）−問題のステータスが、ＦＥＡＳＩＢＬＥ，ＵＮＫＮＯＷＮのいずれかである場合は、Ｓ１２２において、区分束縛条件保持手段および共通束縛条件保持手段から、（ｊ1 ，・・・，ｊk ）−問題に属する線形計画問題の束縛条件
【数１０】
を計算する。
【００６５】Ｓ１２３において、特定された（ｊ1 ，・・・，ｊk ）−問題のステータスがＲＥＡＤＹである場合は、Ｓ１２４において、線形計画問題基底解保持手段８中で、（ｊ1 ，・・・，ｊk ）−問題に対応付けられている単体表主要部［ｑi,j］と基底解（ξX ）（Ｘ∈Ω）を取得し、（ｊ1 ，・・・，ｊk ）−問題に属する線形計画問題の束縛条件
【数１１】
を計算する。
【００６６】Ｓ１２５において、目的関数計算手段５から与えられた（ｊ1 ，・・・，ｊk）−問題に対する線形計画問題の目的関数を得る。そして、Ｓ１２６において、Ｓ１２２またはＳ１２４で計算した束縛条件と目的関数からなる線形計画問題を定義し、線形計画問題解決エンジン部６に引き渡す。
【００６７】図５は、線形計画問題の解決処理の一例を示すフローチャートである。線形計画問題解決エンジン部６は、以下の手続きで、線形計画問題管理手段３から与えられた線形計画問題を解く。
【００６８】Ｓ１３１において、与えられた（ｊ1 ，・・・，ｊk ）−問題のステータスがＵＮＫＮＯＷＮであるときには、Ｓ１３２において、線形計画問題解決エンジン部６は、与えられた線形計画問題の実行可能性を線形計画法を用いて判定する。与えられた線形計画問題が実行不可能と判定された場合、Ｓ１３３において、線形計画問題ステータス保持手段１１中の（ｊ1 ，・・・，ｊk ）−問題に対応するステータスをＩＮＦＥＡＳＩＢＬＥに変更する。さらに、（ｊ1 ，・・・，ｊk ）−問題を変更起点リスト１０に登録した上で、線形計画問題ステータス計算手段９を呼び出す。線形計画問題ステータス計算手段９は、（ｊ1 ，・・・，ｊk ）−問題のステータスの変化がもたらす他の線形計画問題のステータスの変化を計算する。また、線形計画問題解決エンジン部６は処理を終え、線形計画問題管理手段３に制御を返す。
【００６９】Ｓ１３２において、該線形計画問題が実行可能と判断された場合、Ｓ１３４において、掃き出し法等を用いて実行可能基底（Ｊ）、基底解（ξX ）（Ｘ∈Ω）、実行可能基底に属する単体表（主要部と非斉次部）［ｑi,j ］i=1,・・・,r,j=1,・・・,2k+m，（ｂi ）i=1,・・・,r を計算して、現在の実行可能基底、基底解、単体表とする。そして、Ｓ１３６へ進む。
【００７０】Ｓ１３１において、与えられた（ｊ1 ，・・・，ｊk ）−問題のステータスがＦＥＡＳＩＢＬＥであるときには、図４のＳ１２２で求めた束縛条件をもとに、Ｓ１３４において、掃き出し法等を用いて実行可能基底（Ｊ）、基底解（ξX ）（Ｘ∈Ω）、実行可能基底に属する単体表（主要部と非斉次部）［ｑi,j ］i=1,・・・,r,j=1,・・・,2k+m，（ｂi ）i=1,・・・,r を計算して、現在の実行可能基底、基底解、単体表とする。そして、Ｓ１３６へ進む。
【００７１】一方、Ｓ１３１において、与えられた（ｊ1 ，・・・，ｊk ）−問題のステータスがＲＥＡＤＹである時には、Ｓ１３５において、線形計画問題基底解保持手段８から（ｊ1 ，・・・，ｊk ）−問題に対応付けられた実行可能基底（Ｊ）を取得して、図４のＳ１２４で計算した［ｑi,j ］i=1,・・・,r,j=1,・・・,2k+mと併せて、現在の実行可能基底、基底解、単体表とする。
【００７２】Ｓ１３６において、現在の実行可能基底を挟んで隣接する線形計画問題の実行可能基底（Ｊ’）、基底解（ξ'X）（Ｘ∈Ω）、（Ｊ’）に属する単体表主要部［ｑ'i,j］i=1,・・・,r,j=1,・・・,2k+mを求め、線形計画問題基底解保持手段８に登録する。この処理は、図６を用いて後述する。
【００７３】Ｓ１３７において、現在の基底解が（ｊ1 ，・・・，ｊk ）−問題の目的関数の最小値（最大値）を与えているか否かを判定し、与えていないときは、Ｓ１３８において、現在の単体表にピボット変換を施して、新たな実行可能基底、基底解、単体表を計算し、現在の実行可能基底、基底解、単体表とした上で、Ｓ１３６の処理を繰り返す。
【００７４】ここで、最小（最大）性の判定、実行可能基底、基底解、単体表の計算方法は単体（シンプレックス）法の単体基準Ｉないし単体基準ＩＩＩとして知られている方法による。
【００７５】Ｓ１３７において、現在の基底解が（ｊ1 ，・・・，ｊk ）−問題の目的関数の最小値（最大値）を与えているならば、Ｓ１３９において（ｊ1 ，・・・，ｊk ）−問題のステータスに応じて、以下の処理を行なう。（ｊ1 ，・・・，ｊk）−問題のステータスがＦＥＡＳＩＢＬＥあるいはＲＥＡＤＹであるときには、Ｓ１４０において、単に線形計画問題ステータス保持手段１１中の（ｊ1 ，・・・，ｊk ）−問題に対応するステータスをＳＥＴＴＬＥＤに変更する。
【００７６】Ｓ１３９において、（ｊ1 ，・・・，ｊk ）−問題のステータスがＵＮＫＮＯＷＮである時には、Ｓ１４１において、線形計画問題ステータス保持手段１１中の（ｊ1 ，・・・，ｊk ）−問題に対応するステータスをＳＥＴＴＬＥＤに変更したうえで、（ｊ1 ，・・・，ｊk ）−問題を変更起点リスト１０に登録し、線形計画問題ステータス計算手段９を呼び出して、他の線形計画問題のステータスの変化を計算させる。
【００７７】Ｓ１４２において、現在の基底解（最適パラメータ）と目的関数の最小値（最大値）を線形計画問題管理手段３に報告するとともに、制御を返す。
【００７８】図６は、現在の実行可能基底を挟んで隣接する線形計画問題の実行可能基底、基底解、単体表主要部を求める処理の一例を示すフローチャートである。図５R>５のＳ１３６で行なわれる処理は以下の手続きで実行される。
【００７９】Ｓ１５１において、判定１を行なう。判定１は、ξy(i)＝０かつ（ｊ1 ，・・・，ｊi-1 ，ｊi ＋１，ｊi+1 ，・・・，ｊk ）−問題のステータスがＵＮＫＮＯＷＮまたはＦＥＡＳＩＢＬＥであるようなインデックスｉが存在するか否かを判定するものである。
【００８０】Ｓ１５１で判定１の条件に合致するインデックスｉが存在するときは、Ｓ１５２において、（ｊ1 ，・・・，ｊi-1 ，ｊi ＋１，ｊi+1 ，・・・，ｊk ）−問題の実行可能基底（Ｊ’）、基底解（ξ'X）（Ｘ∈Ω）、単体表主要部［ｑ'i,j］i=1,・・・,r,j=1,・・・,2k+mを以下のように定める。
【数１２】
ただし、Ｔ-1［ｑi,j ］Ｔは、［ｑi,j ］の（ｚi ，ｙi ）を軸にしたピボット変換、すなわち、新しい実行可能基底（Ｊ’）に関する基底変換の結果であり、Ｊ＝｛Ｘ1 ，・・・，Ｘr ｝，ｚi ＝Ｘl であるとき、変換行列
【数１３】
によって計算される。ここで、Ｅn はｎ次単位行列を表す。
【００８１】Ｓ１５３において、Ｓ１５２で求められた実行可能基底、基底解、単体表主要部を、（ｊ1 ，・・・，ｊi-1 ，ｊi ＋１，ｊi+1 ，・・・，ｊk ）−問題と対応付けて、線形計画問題基底解保持手段８に登録する。
【００８２】Ｓ１５４において、線形計画問題ステータス保持手段１１中の（ｊ1 ，・・・，ｊi-1 ，ｊi ＋１，ｊi+1 ，・・・，ｊk ）−問題のステータスをＲＥＡＤＹに変更し、さらに、（ｊ1 ，・・・，ｊi-1 ，ｊi ＋１，ｊi+1 ，・・・，ｊk）−問題の変更前のステータスがＵＮＫＮＯＷＮであった場合には、（ｊ1 ，・・・，ｊi-1 ，ｊi ＋１，ｊi+1 ，・・・，ｊk ）−問題を変更起点リスト１０の最後尾に追加する。そして、Ｓ１５１へ戻る。
【００８３】Ｓ１５１における判定１において、ξy(i)＝０かつ（ｊ1 ，・・・，ｊi-1 ，ｊi ＋１，ｊi+1 ，・・・，ｊk ）−問題のステータスがＵＮＫＮＯＷＮまたはＦＥＡＳＩＢＬＥであるようなインデックスｉが存在しない場合には、Ｓ１５５において、判定２を行なう。判定２は、ξz(i)＝０かつ（ｊ1 ，・・・，ｊi-1，ｊi −１，ｊi+1 ，・・・，ｊk ）−問題のステータスがＵＮＫＮＯＷＮまたはＦＥＡＳＩＢＬＥであるようなインデックスｉが存在するか否かを判定するものである。この条件を満たすインデックスｉが存在しない場合には、現在の実行可能基底を挟んで隣接する線形計画問題についての処理が終了したものとして、図５のＳ１３６の処理を終了する。
【００８４】Ｓ１５５における判定２において、条件に合致するインデックスｉが存在するときは、Ｓ１５６において、（ｊ1 ，・・・，ｊi-1 ，ｊi −１，ｊi+1 ，・・・，ｊk ）−問題の実行可能基底（Ｊ’）、基底解（ξ'X）（Ｘ∈Ω）、単体表主要部［ｑ'i,j］i=1,・・・,r,j=1,・・・,2k+mを以下のように定める。
【数１４】
ただし、Ｔ-1［ｑi,j ］Ｔは、［ｑi,j ］の（ｙi ，ｚi ）を軸にしたピボット変換、すなわち、新しい実行可能基底（Ｊ’）に関する基底変換の結果であり、Ｊ＝｛Ｘ1 ，・・・，Ｘr ｝，ｙi ＝Ｘl であるとき、変換行列
【数１５】
によって計算される。
【００８５】Ｓ１５７において、求められた実行可能基底、基底解、単体表主要部は、（ｊ1 ，・・・，ｊi-1 ，ｊi −１，ｊi+1 ，・・・，ｊk ）−問題と対応付けて、線形計画問題基底解保持手段８に登録する。
【００８６】Ｓ１５８において、線形計画問題ステータス保持手段１１中の（ｊ1 ，・・・，ｊi-1 ，ｊi −１，ｊi+1 ，・・・，ｊk ）−問題のステータスをＲＥＡＤＹに変更し、さらに、（ｊ1 ，・・・，ｊi-1 ，ｊi −１，ｊi+1 ，・・・，ｊk）−問題の変更前のステータスがＵＮＫＮＯＷＮであった場合には、（ｊ1 ，・・・，ｊi-1 ，ｊi −１，ｊi+1 ，・・・，ｊk ）−問題を変更起点リスト１０の最後尾に追加する。
【００８７】上述のような処理により、ステータスがＩＮＦＥＡＳＩＢＬＥの場合には線形計画問題の解決の処理を行なわず、また、ステータスがＦＥＡＳＩＢＬＥの場合には、実行可能性を判断する処理を省略することができる。さらに、ステータスがＲＥＡＤＹの場合には、線形計画問題基底解保持手段８に登録されている実行可能基底、基底解、単体表主要部を用いることにより、これらの計算を省略することが可能となる。このように、線形計画法の処理の一部を省略することにより、処理速度を向上させることができる。
【００８８】図７は、線形計画問題ステータス計算手段９の動作の一例を示すフローチャートである。線形計画問題ステータス計算手段９が線形計画問題解決エンジン部６により起動されると、以下の手順で処理を行なう。
【００８９】Ｓ１６１において、変更起点リスト１０が空であれば処理を終了し、制御を線形計画問題解決エンジン部６に返す。変更起点リスト１０が空でないときは、Ｓ１６２において、変更起点リスト１０の先頭の線形計画問題を取り去り、取り去った線形計画問題を起点として、以下のステータスの変更を実行する。
【００９０】Ｓ１６３において、起点線形計画問題（例えば、（ｊ1 ，・・・，ｊk ）−問題とする）のステータスが、ＳＯＬＶＥＤ，ＲＥＡＤＹ，ＦＥＡＳＩＢＬＥのいずれかであるか否かを判定し、そのいずれかであるときはＳ１６４の処理を行ない、ＩＮＦＥＡＳＩＢＬＥであるときはＳ１６５の処理を行なった後、Ｓ１６１へ戻る。
【００９１】図８は、起点線形計画問題のステータスがＳＯＬＶＥＤ，ＲＥＡＤＹ，ＦＥＡＳＩＢＬＥのいずれかである場合の線形計画問題ステータス計算手段の動作の一例を示すフローチャートである。この処理は、起点線形計画問題が少なくとも実行可能である場合に、そのステータスを隣接する線形計画問題に伝播させるための処理である。初期設定として、Ｓ１７１において、インデックスｉを１に設定する。
【００９２】Ｓ１７２において、ｊi ＞１のとき、次の条件のいずれかを満たす最大のａ＜ｊi を探索する。
（１）（ｊ1 ，・・・，ｊi-1 ，ａ，ｊi+1 ，・・・，ｊk ）−問題のステータスは、ＳＯＬＶＥＤ，ＲＥＡＤＹ，ＦＥＡＳＩＢＬＥのいずれかである。
（２）（ｊ1 ，・・・，ｊi-1 ，ａ，ｊi+1 ，・・・，ｊk ）−問題のステータスはＩＮＦＥＡＳＩＢＬＥである。
（３）ａ＝１である。
【００９３】Ｓ１７３において、Ｓ１７２で探索されたａが、上述の条件「（１）（ｊ1 ，・・・，ｊi-1 ，ａ，ｊi+1 ，・・・，ｊk ）−問題のステータスは、ＳＯＬＶＥＤ，ＲＥＡＤＹ，ＦＥＡＳＩＢＬＥのいずれかである。」を満たすときは、Ｓ１７４において、ａ＜ｊ＜ｊi を満たすｊについて、（ｊ1 ，・・・，ｊi-1 ，ｊ，ｊi+1 ，・・・，ｊk ）−問題のステータスがＵＮＫＮＯＷＮであれば、ステータスをＦＥＡＳＩＢＬＥに変更する操作を施す。
【００９４】Ｓ１７５において、Ｓ１７２で探索されたａが、上述の条件「（２）（ｊ1 ，・・・，ｊi-1 ，ａ，ｊi+1 ，・・・，ｊk ）−問題のステータスはＩＮＦＥＡＳＩＢＬＥである。」を満たすとき、Ｓ１７６において、ｊ＜ａを満たすすべてのｊについて、（ｊ1 ，・・・，ｊi-1 ，ｊ，ｊi+1 ，・・・，ｊk ）−問題のステータスがＵＮＫＮＯＷＮであれば、ステータスをＩＮＦＥＡＳＩＢＬＥに変更する操作を施す。
【００９５】Ｓ１７７において、ｊi ＜ｋi −１のとき、次の条件のいずれかを満たす最小のｂ＞ｊi を探索する。
（１）（ｊ1 ，・・・，ｊi-1 ，ｂ，ｊi+1 ，・・・，ｊk ）−問題のステータスはＳＯＬＶＥＤ，ＲＥＡＤＹ，ＦＥＡＳＩＢＬＥのいずれかである。
（２）（ｊ1 ，・・・，ｊi-1 ，ｂ，ｊi+1 ，・・・，ｊk ）−問題のステータスはＩＮＦＥＡＳＩＢＬＥである。
（３）ｂ＝ｋi −１である。
【００９６】Ｓ１７８において、Ｓ１７７で探索されたｂが、上述の条件「（１）（ｊ1 ，・・・，ｊi-1 ，ｂ，ｊi+1 ，・・・，ｊk ）−問題のステータスはＳＯＬＶＥＤ，ＲＥＡＤＹ，ＦＥＡＳＩＢＬＥのいずれかである。」を満たすときは、Ｓ１７９において、ｂ＞ｊ＞ｊi を満たす全てのｊについて、（ｊ1 ，・・・，ｊi-1 ，ｊ，ｊi+1 ，・・・，ｊk ）−問題のステータスがＵＮＫＮＯＷＮであれば、ステータスをＦＥＡＳＩＢＬＥに変更する操作を施す。
【００９７】Ｓ１８０において、Ｓ１７７で探索されたｂが、上述の条件「（２）（ｊ1 ，・・・，ｊi-1 ，ｂ，ｊi+1 ，・・・，ｊk ）−問題のステータスはＩＮＦＥＡＳＩＢＬＥである。」を満たすときは、Ｓ１８１において、ｊ＜ｂを満たすすべてのｊについて、（ｊ1 ，・・・，ｊi-1 ，ｊ，ｊi+1 ，・・・，ｊk ）−問題のステータスがＵＮＫＮＯＷＮであればステータスをＩＮＦＥＡＳＩＢＬＥに変更する操作を施す。
【００９８】Ｓ１８２において、Ｓ１７１ないしＳ１８１の処理でステータスが変更された全ての線形計画問題を変更起点リスト１０の最後尾に追加する。
【００９９】Ｓ１８３において、インデックスｉが最後であるか、すなわち、ｉ＝ｋであるかをチェックし、そうであれば図７のＳ１６４の処理を終了する。もし、ｉ＜ｋであれば、Ｓ１８４において、インデックスｉを１増やして、Ｓ１７２以降の処理を繰り返す。
【０１００】図９は、起点線形計画問題のステータスがＩＮＦＥＡＳＩＢＬＥである場合の線形計画問題ステータス計算手段の動作の一例を示すフローチャートである。この処理は、起点線形計画問題が実行不可能の場合に、そのステータスを隣接する線形計画問題に伝播させるための処理である。初期設定として、Ｓ１９１において、インデックスｉを１に設定する。
【０１０１】Ｓ１９２において、ｊi ＞１のとき、次の条件のいずれかを満たす最大のａ＜ｊi を探索する。
（１）（ｊ1 ，・・・，ｊi-1 ，ａ，ｊi+1 ，・・・，ｊk ）−問題のステータスは、ＳＯＬＶＥＤ，ＲＥＡＤＹ，ＦＥＡＳＩＢＬＥのいずれかである。
（２）ａ＝１である。
【０１０２】Ｓ１９３において、Ｓ１９２で探索されたａが、上述の条件「（１）（ｊ1 ，・・・，ｊi-1 ，ａ，ｊi+1 ，・・・，ｊk ）−問題のステータスは、ＳＯＬＶＥＤ，ＲＥＡＤＹ，ＦＥＡＳＩＢＬＥのいずれかである。」を満たすときは、ｊ＞ｊi を満たす全てのｊについて、（ｊ1 ，・・・，ｊi-1 ，ｊ，ｊi+1 ，・・・，ｊk ）−問題のステータスがＵＮＫＮＯＷＮであれば、ステータスをＩＮＦＥＡＳＩＢＬＥに変更する操作を施す。
【０１０３】Ｓ１９４において、ｊi ＜ｋi −１のとき、次の条件のいずれかを満たす最小のｂ＞ｊi を探索する。
（１）（ｊ1 ，・・・，ｊi-1 ，ｂ，ｊi+1 ，・・・，ｊk ）−問題のステータスは、ＳＯＬＶＥＤ，ＲＥＡＤＹ，ＦＥＡＳＩＢＬＥのいずれかである。
（２）ｂ＝ｋi −１である。
【０１０４】Ｓ１９５において、Ｓ１９４で探索されたｂが、上述の条件「（１）（ｊ1 ，・・・，ｊi-1 ，ｂ，ｊi+1 ，・・・，ｊk ）−問題のステータスは、ＳＯＬＶＥＤ，ＲＥＡＤＹ，ＦＥＡＳＩＢＬＥのいずれかである。」を満たすときは、ｊ＜ｊi を満たす全てのｊについて、（ｊ1 ，・・・，ｊi-1 ，ｊ，ｊi+1 ，・・・，ｊk ）−問題のステータスがＵＮＫＮＯＷＮであれば、ＩＮＦＥＡＳＩＢＬＥに変更する操作を施す。
【０１０５】Ｓ１９６において、Ｓ１９１ないしＳ１９５でステータスが変更された全ての線形計画問題を、変更起点リスト１０の最後尾に追加する。
【０１０６】Ｓ１９７において、インデックスｉが最後であるか、すなわち、ｉ＝ｋであるかをチェックし、そうであれば図７のＳ１６５の処理を終了する。もし、ｉ＜ｋであれば、Ｓ１９８において、インデックスｉを１増やしてＳ１９２に戻り、次のｉについて処理を繰り返す。
【０１０７】図７ないし図９で示した処理により、起点線形計画問題から実行可能あるいは実行不可能が判別される線形計画問題について、ステータスを変更することができ、変更された線形計画問題については線形計画法に基づく実行可能性の判断処理を行なう必要がなくなるため、処理の高速化を図ることができる。
【０１０８】本発明の最適解探索装置は、例えば、表のレイアウト生成処理に用いることができる。表はその各項目欄にテキストが配置される。表の各欄の幅を決めると、テキストの行折りの数が決定され、それに伴って表の行の高さが決定される。逆に、高さが決まれば、テキストの行折り数が決定され、各列の幅も決まる。いま、テキストの行折りの数が不変となる範囲内で各欄の幅を可変とすることを考える。すると、各欄の幅は、階段関数として表現できる。その境界値を区間特性列とし、区間束縛条件を設定することができる。この区間特性列は、表の各列ごとに設定される。共通束縛条件としては、例えば、表の全体の幅などの条件が設定される。
【０１０９】各区間束縛条件の間では、テキストの行折りの数が不変であるから、行の高さは一意に決まる。表のレイアウトの最適性は、例えば、表の面積や周囲長、各欄に発生する空隙の和等で測ることができる。これらの値は、行の高さが一意に決まることから、各欄の幅を設定するためのパラメータを用いた一次式で表現することができる。これを目的関数とする。
【０１１０】このように設定された区間束縛条件、共通束縛条件、および、目的関数により生成される線形計画問題を解決する。このとき生成される線形計画問題の数は、各列ごとの区間特性列から１つずつ値を取り出すときの組み合わせの数だけ存在する。例えば、２つの欄に２文字ずつ配置する表を考えると、各欄に配置されるテキストが１行の場合と、行折りが発生して２行となる場合の２通りあり、それがそれぞれの列で発生するので、その組み合わせは４通りであり、解決する線形計画問題は４つとなる。同様に、３文字ずつ配置する場合には９つというように、解決すべき線形計画問題はテキスト量や列数等によって飛躍的に増大する。
【０１１１】本発明の最適解探索装置を用いることによって、線形計画問題を解決するために必要な計算量を激減させることができ、高速に最適な表のレイアウトを得ることができる。
【０１１２】本発明は、表のレイアウト以外にも、通常、線形計画問題が利用されている広範な分野において用いることができる。
【０１１３】
【発明の効果】以上の説明から明らかなように、本発明によれば、１つの線形計画問題を解く過程で計算される基底解から、隣接する他の線形計画問題の基底解を計算することによって、計算を複数の線形計画問題で共有し、処理の効率を向上させることができる。
【０１１４】また、線形計画問題の実行可能性の判定結果をステータスとして保持し、実行可能性が未知である他の線形計画問題の実行可能性を判定してステータスを変更しておき、線形計画問題を解決する際にこのステータスを参照することによってすでに実行可能性が判定されているものについては実行可能性の判定処理を省略することができ、処理の効率を向上させることができる。
【０１１５】さらに実行可能を示すステータスとして、例えば、実行可能性が判定された段階、基底解が計算された段階、すでに解決済みの段階というように細分することにより、基底解が計算されているものについては、実行可能性の判定と基底解の計算処理が、また、実行可能を示すものについては、実行可能性の判定処理が、それぞれ省略でき、処理効率の向上を図ることができる。
【０１１６】これらのステータスに優先順位を持たせ、線形計画問題を選択する際に、より計算量が少なくなるように選択してゆくことによって、さらに処理の効率を向上させることができるという効果がある。
【図面の簡単な説明】
【図１】 本発明の最適解探索装置の一実施例を示す構成図である。
【図２】 本発明の最適解探索装置の一実施例における処理の一例を示すフローチャートである。
【図３】 線形計画問題の特定処理の一例を示すフローチャートである。
【図４】 線形計画問題を完成させる処理の一例を示すフローチャートである。
【図５】 線形計画問題の解決処理の一例を示すフローチャートである。
【図６】 現在の実行可能基底を挟んで隣接する線形計画問題の実行可能基底、基底解、単体表主要部を求める処理の一例を示すフローチャートである。
【図７】 線形計画問題ステータス計算手段９の動作の一例を示すフローチャートである。
【図８】 起点線形計画問題のステータスがＳＯＬＶＥＤ，ＲＥＡＤＹ，ＦＥＡＳＩＢＬＥのいずれかである場合の線形計画問題ステータス計算手段の動作の一例を示すフローチャートである。
【図９】 起点線形計画問題のステータスがＩＮＦＥＡＳＩＢＬＥである場合の線形計画問題ステータス計算手段の動作の一例を示すフローチャートである。この処理は、起点線形計画問題が実行不可能の場合に、そのステータスを隣接する線形計画問題に伝播させるための処理である。
【符号の説明】
１…区間束縛条件保持手段、２…共通束縛条件保持手段、３…線形計画問題間利手段、４…局所最適解リスト、５…目的関数計算手段、６…線形計画問題解決エンジン部、７…隣接問題基底解計算手段、８…線形計画問題基底解保持手段、９…線形計画問題ステータス計算手段、１０…変更起点リスト、１１…線形計画問題ステータス保持手段。
【０００１】
【産業上の利用分野】本発明は、線形計画問題、すなわち、パラメータに関する一次式で示された束縛条件のもとで、同じくパラメータによって定まる目的関数の値を最適にするパラメータの値を計算する最適解探索装置に関するものである。
【０００２】
【従来の技術】一般に、線形計画問題は、種々の条件のもとで最適な状態を得るために用いられる。例えば、損益分岐点の計算や、列車、航空機等の最適運行、生産工程の管理など、幅広い分野で応用されている。
【０００３】従来の線形計画問題を解決する装置の１つとして、複数の部分問題ごとに線形計画問題を解決し、各線形計画問題から得られた局所解を走査して最適解を求める方式が用いられている。以下に、この方式について述べる。
【０００４】区間ごとの束縛条件を与える一次不等式の斉次部を、Ｔ1 ，・・・，Ｔk と表わす。各Ｔi は、パラメータｘ1 ，・・・，ｘm に関する一次式ｐi,1 ｘ1 ＋・・・ｐi,m ｘmである。
【０００５】各斉次一次関数Ｔｉには、単調増加数列ｓi,1 ，・・・，ｓi,k(i)が固有に与えられている。これを区間特性列と呼ぶ。ここで、ｋ（ｉ）は、ｋi を表わす。添字の添字が表現できないため、以下、このような表記を用いる。
【０００６】この区間特性列を用い、１≦ｊi ≦ｋi −１を満たす任意のｊi に対して、一次不等式ｓi,j(i)≦ｐi,1 ｘ1 ＋・・・ｐi,m ｘm ≦ｓi,j(i)+1が、区間束縛条件の１つとなる。
【０００７】ここで、各斉次一次関数Ｔi に対してｊi ∈｛１，・・・，ｋi −１｝を一つずつ定めて、連立一次不等式ｐ1,1 ｘ1 ＋・・・＋ｐ1,m ｘm ≧ｓ1,j(1)ｐ1,1 ｘ1 ＋・・・＋ｐ1,m ｘm ≦ｓ1,j(1)+1・・・ｐk,1 ｘ1 ＋・・・＋ｐk,m ｘm ≧ｓk,j(k)ｐk,1 ｘ1 ＋・・・＋ｐk,m ｘm ≦ｓk,j(k)+1が区間束縛条件の組である。この連立一次不等式は、すべての（ｊ1 ，・・・，ｊk ）∈［１，・・・，ｋ1 −１］×・・・×［１，・・・，ｋk −１］に対して作成される。
【０００８】この連立一次不等式を１組ずつ取り出してきて、それをもとに１つずつ線形計画問題を定義する。この線形計画問題をｊ1 ，・・・，ｊk が定める線形計画問題（単純に（ｊ1 ，・・・，ｊk ）−問題）と呼ぶ。（ｊ1 ，・・・，ｊk ）−問題の束縛条件および目的関数について述べる。ユーザは、ｊ1 ，・・・，ｊk によらないパラメータに関する一次方程式または一次不等式の組（以下、共通束縛条件と呼ぶ）を指定することができる。これらの共通束縛条件は、必要ならばスラック変数を用いて一次方程式の形式で表現することができる。すなわち、共通束縛条件をｐ'1,1ｘ1 ＋・・・＋ｐ'1,mｘm ＝ｓ'1・・・ｐ'k',1 ｘ1 ＋・・・＋ｐ'k',m ｘm ＝ｓ'k'であるものとする。
【０００９】スラック変数は、例えば、ｐ'i,1ｘ1 ＋・・・＋ｐ'i,mｘm ≦ｓ'iのときは、スラック変数ｕi （≧０）を用いて、ｐ'i,1ｘ1 ＋・・・＋ｐ'i,mｘm ＋ｕi ＝ｓ'iとすることができる。一方、ｐ'i,1ｘ1 ＋・・・＋ｐ'i,mｘm ≧ｓ'iのときは、スラック変数ｕi （≧０）を用いて、ｐ'i,1ｘ1 ＋・・・＋ｐ'i,mｘm −ｕi ＝ｓ'iとすることができる。
【００１０】区間束縛条件である連立一次不等式の組と、共通束縛条件である連立一次方程式とを連立させたものが、（ｊ1 ，・・・，ｊk ）−問題の束縛条件となる。すなわち、
【数１】
と同値である。この線形方程式を、（ｊ1 ，・・・，ｊk ）−問題の束縛条件と呼ぶ。一般性を失うことなく全てのパラメータは非負の値を取るものと仮定できるので、以下の説明においてはｘi ≧０，ｙi ≧０，ｚi ≧０であるものとする。
【００１１】さて、最適解を評価するための物理量は目的関数で与えられる。物理量は必ずしもパラメータの一次関数で与えられるとは限らないが、束縛斉次一次関数とその区間特性列を適切に与えることにより、パラメータが１つの区間束縛条件の組を満たしている場合に、目的関数が一次関数になるような例が知られている。例えば、表の割付を行なう際に、各欄に割り付けられるテキストの行折りが一定になるように定め、目的関数を表の割付面積とすると、その行折りの一定の区間においては目的関数はパラメータの一次関数となる。このように、区分的に線形関数となる物理量を、目的関数として求める。ここでは、（ｊ1 ，・・・，ｊk ）−問題の目的関数は、ｊ1 ，・・・，ｊk に依存して定まる線形関数ｖ1 ｘ1 ＋・・・＋ｖm ｘmであるものとする。
【００１２】以上のようにして取得した連立一次不等式をもとに、（ｊ1 ，・・・，ｊk ）−問題を完成させる。完成された（ｊ1 ，・・・，ｊk ）−問題は、（１）線形計画問題が実行不可能である、すなわち、線形計画問題の束縛条件を満たすようなパラメータの値が存在しないことを確かめるか、（２）線形計画問題の束縛条件を満たすパラメータの値で、目的関数を最小（最大）にするものを求めることによって解決される。そのための処理として、以下のような処理を行なう。
【００１３】まず、（ｊ1 ，・・・，ｊk ）−問題の実行可能性を、線形計画法を用いて判定する。（ｊ1 ，・・・，ｊk ）−問題が実行不可能である場合は、その旨を出力して処理を終了する。
【００１４】実行可能である場合は、（ｊ1 ，・・・，ｊk ）−問題に関する最初の実行可能基底を掃き出し法などを用いて計算し、計算した実行可能基底に属するパラメータの値を最初の基底解とする。現在の基底解が目的関数の最小値（最大値）を与えているときには、計算された目的関数の最小値（最大値）と、属する基底解（最適パラメータ）の情報を併せて出力し、処理を終了する。
【００１５】基底解が目的関数の最小値（最大値）を与えないときには、ピボット変換を用いて新たな実行可能基底と、新たな基底解を計算し、最小値（最大値）が与えられるまで、基底解の評価と新たな実行可能基底、基底解の計算を繰り返す。上述の（ｊ1 ，・・・，ｊk ）−問題を解決する処理を、全ての（ｊ1 ，・・・，ｊk ）∈［１，・・・，ｋ1 −１］×・・・×［１，・・・，ｋk −１］に対して行なう。全ての線形計画問題を解決し終わると、各（ｊ1 ，・・・，ｊk）−問題を解決して得られた局所最適解を走査して、目的関数の値が最良値（最小値または最大値）となるものを探索し、対応するパラメータの値の組を最適解とする。
【００１６】上述の方式では、各（ｊ1 ，・・・，ｊk ）−問題について、それぞれ、線形計画問題を解決する処理を行なっている。１つの線形計画問題を解決するだけでも、多くの時間を要するため、全体として最適解を得るために、非常に時間がかかってしまい、効率の点で難点があった。
【００１７】
【発明が解決しようとする課題】本発明は、上述した事情に鑑みてなされたもので、処理効率を向上させた最適解探索装置を提供することを目的とするものである。
【００１８】
【課題を解決するための手段】本発明は、請求項１に記載の発明においては、複数の線形計画問題から構成される複合線形計画問題の最適解を計算する最適解探索装置において、複数のパラメータに関する有限個の斉次一次関数を保持するとともに各斉次一次関数に付随する２個以上の実数からなる単調増加数列であって斉次一次関数の上限と下限を隣接する実数として有する区間特性列を保持する区間束縛条件保持手段と、常にパラメータ間に成立すべき一次方程式または一次不等式を共通束縛条件として保持する共通束縛条件保持手段と、前記区間束縛条件保持手段に保持されている各斉次一次関数の区間特性列から隣接する２個の実数を選択して得られる束縛条件の組ごとにパラメータに関する一次式として目的関数を計算する目的関数計算手段と、該目的関数計算手段で計算された目的関数と該目的関数に対応する束縛条件の組および前記共通束縛条件保持手段に保持されている共通束縛条件等からなる線形計画問題を実行可能基底および基底解を計算しながら解決する線形計画問題解決エンジン部と、線形計画問題解決エンジン部が実行可能基底と基底解を計算するたびに計算された実行可能基底を挟んで隣接する線形計画問題の実行可能基底と基底解を計算する隣接問題基底解計算手段と、計算済みの実行可能基底および基底解を線形計画問題と対応づけて保持する線形計画問題基底解保持手段と、前記区間束縛条件保持手段と前記共通束縛条件保持手段と前記目的関数計算手段と前記線形計画問題解決エンジン部を制御し前記線形計画問題解決エンジン部から前記束縛条件の組ごとに得られた結果をもとに最適値を探索する線形計画問題管理手段を有し、前記線形計画問題解決エンジン部が新たに線形計画問題を解きはじめる際に、前記線形計画問題基底解保持手段に解くべき線形計画問題に対応する実行可能基底と基底解が存在すれば、その実行可能基底と基底解を用いて計算を開始することを特徴とするものである。
【００１９】また、請求項２に記載の発明においては、複合線形計画問題の最適解を計算する最適解探索装置において、複数のパラメータに関する有限個の斉次一次関数を保持するとともに各斉次一次関数に付随する２個以上の実数からなる単調増加数列であって斉次一次関数の上限と下限を隣接する実数として有する区間特性列を保持する区間束縛条件保持手段と、常にパラメータ間に成立すべき一次方程式または一次不等式を共通束縛条件として保持する共通束縛条件保持手段と、前記区間束縛条件保持手段に保持されている各斉次一次関数の区間特性列から隣接する２個の実数を選択して得られる束縛条件の組ごとにパラメータに関する一次式として目的関数を計算する目的関数計算手段と、前記束縛条件の組ごとに導出される線形計画問題それぞれに対して、少なくとも「実行可能である」、「実行不可能である」、「実行可能性が未知である」を指示するステータスを保持する線形計画問題ステータス保持手段と、前記目的関数計算手段で計算された目的関数と該目的関数に対応する束縛条件の組および前記共通束縛条件保持手段に保持されている共通束縛条件等からなる線形計画問題について実行可能性を判断して前記線形計画問題ステータス保持手段に保持されている該線形計画問題のステータスを変更した上で該線形計画問題を解決する線形計画問題解決エンジン部と、該線形計画問題解決エンジン部が各線形計画問題についてその実行可能性を判定するたびに該線形計画問題のステータスの変化がもたらす他の線形計画問題のステータスの変化を再計算し前記線形計画問題ステータス保持手段に保持されているステータスを変更する線形計画問題ステータス計算手段と、前記区間束縛条件保持手段と前記共通束縛条件保持手段と前記目的関数計算手段と前記線形計画問題解決エンジン部を制御し前記線形計画問題解決エンジン部から前記束縛条件の組ごとに得られた結果をもとに最適値を探索する線形計画問題管理手段を有し、前記線形計画問題解決エンジン部が線形計画問題を解く際に、前記線形計画問題ステータス保持手段に保持されているステータスを参照し、少なくとも「実行可能性が未知である」ステータス以外の場合には、該線形計画問題の実行可能性の判定処理を行なわないことを特徴とするものである。
【００２０】さらに、請求項３に記載の発明においては、複合線形計画問題の最適解を計算する最適解探索装置において、複数のパラメータに関する有限個の斉次一次関数を保持するとともに各斉次一次関数に付随する２個以上の実数からなる単調増加数列であって斉次一次関数の上限と下限を隣接する実数として有する区間特性列を保持する区間束縛条件保持手段と、常にパラメータ間に成立すべき一次方程式または一次不等式を共通束縛条件として保持する共通束縛条件保持手段と、前記区間束縛条件保持手段に保持されている各斉次一次関数の区間特性列から隣接する２個の実数を選択して得られる束縛条件の組ごとにパラメータに関する一次式として目的関数を計算する目的関数計算手段と、前記束縛条件の組ごとに導出される線形計画問題それぞれに対して、少なくとも「解決済みである」、「基底解保持済みである」、「実行可能である」、「実行不可能である」、「実行可能性が未知である」を指示するステータスを保持する線形計画問題ステータス保持手段と、前記目的関数計算手段で計算された目的関数と該目的関数に対応する束縛条件の組および前記共通束縛条件保持手段に保持されている共通束縛条件等からなる線形計画問題の実行可能性の判定および実行可能基底と基底解の計算を行ない各処理において前記線形計画問題ステータス保持手段に保持されているステータスを変更しながら線形計画問題を解決する線形計画問題解決エンジン部と、該線形計画問題解決エンジン部が実行可能基底と基底解を計算するたびに計算された実行可能基底を挟んで隣接する線形計画問題の実行可能基底と基底解を計算するとともに前記線形計画問題ステータス保持手段に保持されている該隣接問題のステータスを変更する隣接問題基底解計算手段と、計算済みの実行可能基底および基底解を保持する線形計画問題基底解保持手段と、前記線形計画問題解決エンジン部および前記隣接問題基底解計算手段の処理に従い線形計画問題のステータスの変化がもたらす他の線形計画問題のステータスの変化を再計算し前記線形計画問題ステータス保持手段に保持されているステータスを変更する線形計画問題ステータス計算手段と、前記区間束縛条件保持手段と前記共通束縛条件保持手段と前記目的関数計算手段と前記線形計画問題解決エンジン部を制御し前記線形計画問題解決エンジン部から前記束縛条件の組ごとに得られた結果をもとに最適値を探索する線形計画問題管理手段を有し、前記線形計画問題解決エンジン部が線形計画問題を解く際に、前記線形計画問題ステータス保持手段に保持されているステータスを参照し、少なくとも「実行可能性が未知である」ステータス以外の場合には該線形計画問題の実行可能性の判定処理を行なわず、ステータスが「基底解保持済みである」ことを示している場合には前記線形計画問題基底解保持手段から実行可能基底と基底解を得て計算を開始することを特徴とするものである。
【００２１】前記請求項２または３に記載の最適解探索装置において、前記線形計画問題ステータス保持手段に保持されたステータスは優先順位を持っており、前記線形計画問題管理手段は、該ステータスの優先順位に基づいて線形計画問題を解く順序を決定するように構成することができる。
【００２２】
【作用】区間束縛条件保持手段に区間束縛条件が保持され、共通束縛条件保持手段に共通束縛条件が保持される。また、目的関数計算手段により目的関数が計算される。ここで、（ｊ1 ，・・・，ｊk ）−問題を特定し、線形計画問題解決エンジン部に渡される。（ｊ1 ，・・・，ｊk ）−問題を解くに当たって、実行可能基底（Ｊ）と基底解（ξX ）（ここでＸ∈Ω）が得られたとする。ここで、Ω＝｛ｘ1 ，・・・，ｘm ，ｙ1 ，ｚ1 ，・・・，ｙk ，ｚk ｝、Ｊ⊂Ωである。
【００２３】行列
【数２】
中の変数Ｘ∈Ωに対応する列ベクトルをｖX と表わす。すなわち、ｖx(i)は第ｉ列、ｖy(i)は第ｍ＋２ｉ−１列、ｖz(i)は第ｍ＋２ｉ列を表わす。
【００２４】（Ｊ）が実行可能基底であるとは、｛ｖX ｝（Ｘ∈Ｊ）が、｛ｖX ｝（Ｘ∈Ω）が張る線形空間の基底であり、対応する基底解
【数３】
が存在して、束縛条件
【数４】
を満たすことである。ここで、実行可能基底に対して、対応する基底解は一意である。
【００２５】このとき、以下の性質が成り立つ。
（１）ξy(i)＝０が成り立つとき、（ｊ1 ，・・・，ｊi-1 ，ｊi ＋１，ｊi+1 ，・・・，ｊk ）−問題は実行可能であり、以下が成り立つ。
・Ｊ∋ｙi なら、（Ｊ）は実行可能基底である。
・Ω＼Ｊ∋ｙi ならば、（Ｊ∪｛ｙi ｝＼｛ｚi ｝）は実行可能基底である。
・（ξ'X）（Ｘ∈Ω）は基底解である。
【数５】
このとき、（ｊ1 ，・・・，ｊi-1 ，ｊi ＋１，ｊi+1 ，・・・，ｊk ）−問題を、実行可能基底（Ｊ）を挟んで（ｊ1 ，・・・，ｊi-1 ，ｊi ，ｊi+1 ，・・・，ｊk ）−問題と隣接しているという。
（２）ξz(i)＝０が成り立つとき、（ｊ1 ，・・・，ｊi-1 ，ｊi −１，ｊi+1 ，・・・，ｊk ）−問題は実行可能であり、以下が成り立つ。
・Ｊ∋ｚi なら、（Ｊ）は実行可能基底である。
・Ω＼Ｊ∋ｙi ならば、（Ｊ∪｛ｚi ｝＼｛ｙi ｝）は実行可能基底である。
・（ξ'X）（Ｘ∈Ω）は基底解である。
【数６】
このとき、（ｊ1 ，・・・，ｊi-1 ，ｊi −１，ｊi+1 ，・・・，ｊk ）−問題を、実行可能基底（Ｊ）を挟んで（ｊ1 ，・・・，ｊi-1 ，ｊi ，ｊi+1 ，・・・，ｊk ）−問題と隣接しているという。
【００２６】請求項１に記載の発明では、隣接問題基底計算手段は、線形計画問題解決エンジン部が線形計画問題の実行可能基底と基底解を計算する度に、その実行可能基底を挟んで隣接する線形計画問題がすでに線形計画問題基底解保持手段に保持されているかを調べ、保持されていない場合には、該隣接線形計画問題の実行可能基底と基底解を上述の性質にしたがって計算して、線形計画問題基底解保持手段に登録する。
【００２７】線形計画問題解決エンジン部が新たに線形計画問題を解くときには、まず、線形計画問題基底解保持手段に該線形計画問題が登録されているかを調べ、もし登録されているならば、登録されている実行可能基底と基底解を用いて計算を開始する。これにより、線形計画問題解決エンジン部で行なわれる実行可能性判定と初期実行可能基底探索のステップを省略することができる。
【００２８】また、各（ｊ1 ，・・・，ｊk ）−問題には、次のような性質がある。特定の一つの斉次一次関数Ｔi に関する区間束縛条件が異なる２つの線形計画問題、（ｊ1 ，・・・，ｊi-1 ，ｊi ，ｊi+1 ，・・・，ｊk ）−問題と、（ｊ1 ，・・・，ｊi-1 ，ｊ'i，ｊi+1 ，・・・，ｊk ）−問題について、以下の性質が成り立つ。ただし、ｊi ＜ｊ'iが成り立つものとする。
性質１）（ｊ1 ，・・・，ｊi-1 ，ｊi ，ｊi+1 ，・・・，ｊk ）−問題と（ｊ1 ，・・・，ｊi-1 ，ｊ'i，ｊi+1 ，・・・，ｊk ）−問題の双方が実行可能であるとき、任意のｊi ≦ｊ≦ｊ'iに対して、（ｊ1 ，・・・，ｊi-1 ，ｊ，ｊi+1 ，・・・，ｊk ）−問題は実行可能である。
性質２）（ｊ1 ，・・・，ｊi-1 ，ｊi ，ｊi+1 ，・・・，ｊk ）−問題が実行可能であり、（ｊ1 ，・・・，ｊi-1 ，ｊ'i，ｊi+1 ，・・・，ｊk ）−問題が実行不可能であるとき、任意のｊ≧ｊ'iに対して、（ｊ1 ，・・・，ｊi-1 ，ｊ，ｊi+1 ，・・・，ｊk ）−問題は実行不可能である。
性質３）（ｊ1 ，・・・，ｊi-1 ，ｊi ，ｊi+1 ，・・・，ｊk ）−問題が実行不可能であり、（ｊ1 ，・・・，ｊi-1 ，ｊ'i，ｊi+1 ，・・・，ｊk ）−問題が実行可能であるとき、任意のｊ≦ｊi に対して、（ｊ1 ，・・・，ｊi-1 ，ｊ，ｊi+1 ，・・・，ｊk ）−問題は実行不可能である。
【００２９】線形計画問題解決エンジン部は、線形計画問題の実行可能性を判定する度に、判定結果に応じて、「実行可能である」、「実行不可能である」のいずれかを指示するステータスを線形計画問題ステータス保持手段２２中に、線形計画問題に対応付けて登録する。
【００３０】線形計画問題ステータス計算手段は、ある線形計画問題のステータスの登録によって、上述の性質１）ないし性質３）からその実行可能性が判定できるすべての線形計画問題について、そのステータスを計算し、登録する。
【００３１】線形計画問題ステータス計算手段によって実行可能性が判定され、「実行可能である」、「実行不可能である」のいずれかのステータスが新たに付与される線形計画問題が存在すれば、その線形計画問題のステータスの登録によって、さらに実行可能性が判定できる線形計画問題が存在するかもしれない。線形計画問題ステータス計算手段は、このような線形計画問題が存在しなくなるまで、上記の手続きを繰り返す。
【００３２】請求項２に記載の発明では、この線形計画問題ステータス保持手段と、線形計画問題ステータス計算手段により、一部の線形計画問題の実行可能性を、線形計画法のプログラムを用いることなく知ることができ、「実行可能性が未知である」線形計画問題についてのみ、線形計画法を用いて実行可能性を検証すればよい。特に、線形計画問題管理手段は、線形計画問題ステータス計算手段によって「実行不可能である」ことを指示するステータスを付与された線形計画問題を除外して処理を進めることにより、処理の効率を向上させることができる。
【００３３】線形計画問題のステータスをさらに詳細に設定することができる。例えば、請求項３に記載の発明のように、請求項１に記載の隣接問題基底解計算手段および線形計画問題基底解保持手段を用い、線形計画問題のステータスとして、「実行可能である」、「実行不可能である」、「実行可能性が未知である」に加えて、「解決済みである」並びに「基底解が与えられている」ことを指示するステータスを設定することができる。
【００３４】「実行可能である」ことを示すステータスが設定された線形計画問題は、その実行可能性が線形計画法の処理により判定されたものではなく、線形計画問題ステータス計算手段によって、他の線形計画問題のステータスから計算されている線形計画問題である。「基底解が与えられている」ことを示すステータスが設定された線形計画問題は、隣接問題基底解計算手段によって、隣接する線形計画問題の実行可能基底と基底解から、その線形計画問題の実行可能基底と基底解が計算されている線形計画問題である。「実行不可能である」ことを示すステータスが設定された線形計画問題は、その実行不可能性が、線形計画法を用いて判定されたか、または、前記の線形計画問題ステータス計算手段によって他の線形計画問題のステータスから計算された線形計画問題である。実行可能な線形計画問題を線形計画問題解決エンジン部が解決すると、該線形計画問題のステータスは「解決済みである」に設定される。
【００３５】このような構成により、線形計画問題解決エンジン部は、解決する線形計画問題に対応したステータスを参照することにより、実行可能性の検証、あるいは、実行可能性の検証と実行可能基底および基底解の計算を省略することができ、効率の向上を図ることができる。
【００３６】請求項４に記載の発明において、ステータスに優先順位を付けることにより、線形計画問題管理手段における線形計画問題の選択を効率よく行なうことが可能となる。例えば、請求項３に記載の発明のように、５種類のステータスを有する場合、以下のように線形計画問題を選択することによって、処理の効率化を図ることができる。
（１）「基底解が与えられている」ことを示すステータスが設定された線形計画問題が存在すれば、それを取得する。
（２）「基底解が与えられている」ことを示すステータスが設定されている線形計画問題が存在しない場合、「実行可能である」ことを示すステータスが設定された線形計画問題が存在すれば、それを取得する。
（３）「基底解が与えられている」および「実行可能である」ことを示すステータスが設定された線形計画問題が存在しない場合、「実行可能性が未知である」線形計画問題を取得する。
【００３７】「基底解が与えられている」ことを示すステータスが設定された線形計画問題は、線形計画法のプログラム中の実行可能性の判定処理を省略することができるので、効率良く解を得ることができる。また、計算の途中で中間的に得られる基底解から、隣接する線形計画問題の基底解が得られるので、「基底解が与えられている」ことを示すステータスが設定された線形計画問題を優先的に解くことにより、他の線形計画問題の解決の効率を向上させる。この効果は、連鎖的である。すなわち、「基底解が与えられている」ことを示すステータスが設定された線形計画問題を解決することにより、「基底解が与えられている」ことを示すステータスが設定された線形計画問題が増殖していくという効果が得られる。
【００３８】「実行可能である」ことを示すステータスが設定された線形計画問題は、実行可能性の判定処理を省略することができる。ただし、「基底解が与えられている」ことを示すステータスが設定された線形計画問題とは異なり、問題自身を解決するためには線形計画法のプログラムのすべてのステップを実行しなければならないが、隣接する線形計画問題の基底解を与えるという点では、「基底解が与えられている」ことを示すステータスが設定された線形計画問題を解く場合と同様である。したがって、「実行可能である」ことを示すステータスが設定された線形計画問題を優先的に解くことにより、やはり、「基底解が与えられている」ことを示すステータスが設定された線形計画問題が連鎖的に増殖していくという効果が得られる。
【００３９】このように、線形計画問題管理手段が線形計画問題ステータス保持手段に保持されているステータスに応じて、線形計画問題解決エンジン部に引き渡す線形計画問題を計画的に選択することによって、処理の効率を向上させることができる。
【００４０】
【実施例】図１は、本発明の最適解探索装置の一実施例を示す構成図である。図中、１は区間束縛条件保持手段、２は共通束縛条件保持手段、３は線形計画問題管理手段、４は局所最適解リスト、５は目的関数計算手段、６は線形計画問題解決エンジン部、７は隣接問題基底解計算手段、８は線形計画問題基底解保持手段、９は線形計画問題ステータス計算手段、１０は変更起点リスト、１１は線形計画問題ステータス保持手段である。
【００４１】区間束縛条件保持手段１には、インデックスｉ∈｛１，・・・，ｋ｝に対応付けて、束縛条件の係数ベクトル（ｐi,1 ，・・・，ｐi,m ）と、境界特性列ｓi,1 ＜ｓi,2 ＜・・・＜ｓi,k(i)が保持されている。
【００４２】共通束縛条件保持手段２には、区間束縛条件に関わらずパラメータを用いた一次方程式の共通束縛条件がリストとして保持されている。共通束縛条件が一次不等式である場合には、スラック変数を用いて一次方程式に変形することができるので、以下の説明では共通束縛条件保持手段２に保持される共通束縛条件は、あらかじめ一次方程式の形に変形されているものとする。共通束縛条件保持手段に保持される束縛条件を、ｐ'i,1ｘ1 ＋・・・＋ｐ'i,mｘm ＝ｓ'iと表わす。ただし、１≦ｉ≦ｋ’とする。
【００４３】線形計画問題管理手段３は、（ｊ1 ，・・・，ｊk ）−問題を特定し、各インデックスｉに対応するｊi 、あるいは、必要ならば、区間束縛条件保持手段１に保持されている境界特性列中の隣接する境界値の組（ｓj(1)，ｓj(1)+1），（ｓj(2)，ｓj(2)+1），・・・，（ｓj(k)，ｓj(k)+1）を目的関数計算手段５に渡し、目的関数ｖ1 ｘ1 ＋・・・＋ｖm ｘmを得る。この（ｊ1 ，・・・，ｊk ）−問題の特定には、線形計画問題ステータス保持手段１１に保持されているステータスを参照し、「基底解が与えられている」線形計画問題を選択し、なければ、「実行可能である」線形計画問題を選択し、なければ、「実行可能性が未知である」線形計画問題を選択する。
【００４４】目的関数計算手段５から得られる目的関数と、区間束縛条件保持手段１に保持されている区間束縛条件、共通束縛条件保持手段２に保持されている共通束縛条件を線形計画問題解決エンジン部６に渡し、線形計画問題を解く。解くべき線形計画問題は、各インデックスｉに対してｊi ∈｛１，・・・，ｋi −１｝を１つずつ定めることにより特定される（ｊ1 ，・・・，ｊk ）−問題である。この線形計画問題は、すべての（ｊ1 ，・・・，ｊk ）∈［１，・・・，ｋ1 −１］×・・・×［１，・・・，ｋk −１］について存在する。線形計画問題解決エンジン部６からは、渡した線形計画問題の最小値（最大値）と、その最小値（最大値）を与える最適パラメータの値との組、あるいは、線形計画問題が実行不可能である旨の情報が返される。各（ｊ1 ，・・・，ｊk ）−問題を線形計画問題解決エンジン部６で解いて得られた局所解は、局所最適解リスト４に記録する。すべての（ｊ1 ，・・・，ｊk ）−問題が解決すると、局所最適解リスト４を走査し、全体の最適解を得る。
【００４５】局所最適解リスト４には、線形計画問題解決エンジン部６から返される線形計画問題の最小値（最大値）と、その最小値（最大値）を与える最適パラメータの値との組を順次保持する。
【００４６】目的関数計算手段５は、線形計画問題管理手段３が特定した（ｊ1 ，・・・，ｊk ）−問題の目的関数として、区間束縛条件保持手段１に保持されている区間束縛条件に基づき、ｊ1 ，・・・，ｊk に依存して定まる線形関数ｖ1 ｘ1 ＋・・・＋ｖm ｘmを求める。
【００４７】線形計画問題解決エンジン部６は、線形計画問題管理手段３から目的関数、区間束縛条件、共通束縛条件を受け取り、線形計画問題である（ｊ1 ，・・・，ｊk ）−問題を解決して、その線形計画問題の最小値（最大値）と、その最小値（最大値）を与える最適パラメータの値との組、あるいは、線形計画問題が実行不可能である旨の情報を返す。線形計画問題の解決は、まず、実行可能性を検証する。そして、実行可能である線形計画問題について、実行可能基底、基底解を求め、例えば、終了条件として単体法の単体基準Ｉおよび単体基準ＩＩを満たしたならば最適解として抽出し、終了条件を満たさないときは、ある特定の方法（例えば、単体基準ＩＩＩ）にしたがって新たな単体表を計算し（ピボッド変換）、さらに、終了条件を調べる。
【００４８】隣接問題基底解計算手段７は、線形計画問題解決エンジン部６が線形計画問題の実行可能基底と基底解を計算する度に、その実行可能基底を挟んで隣接する線形計画問題がすでに線形計画問題基底解保持手段８に保持されているかを調べ、保持されていない場合には、該隣接線形計画問題の実行可能基底と基底解を計算して、線形計画問題基底解保持手段８に登録する。
【００４９】線形計画問題基底解保持手段８は、（ｊ1 ，・・・，ｊk ）−問題に対して、その実行可能基底、基底解、実行可能基底に属する単体表主要部を対応付けて保持する。線形計画問題基底解保持手段８に保持される線形計画問題のステータスは、ＲＥＡＤＹまたはＳＯＬＶＥＤのいずれかである。ただし、ＲＥＡＤＹおよびＳＯＬＶＥＤは、上述の「基底解保持済みである」、「解決済みである」の各ステータスに相当する。
【００５０】実行可能基底に属する単体表主要部とは、（ｊ1 ，・・・，ｊk ）−問題の束縛条件行列
【数７】
を基底｛ｖX ｝（ｘ∈Ｊ）に関して基底変換して得られるｒ行２ｋ＋ｍ列の行列［ｑi,j ］である。Ｊ＝｛Ｘ1 ，・・・，Ｘr ｝とすると、ｑi,j はもとの束縛条件行列中のｊ番目の列ベクトルｖj の列ベクトルｖX(i)に対する相対成分である。すなわち、一意な一次結合ｖj ＝ｑi,j ｖX(1)＋・・・＋ｑr,j ｖX(r)が成り立つ。ここで、ｒは束縛条件行列のランクである。ここで、束縛条件の右辺（単体表の非斉次部分）である列ベクトルを、基底（ｖX ）（Ｘ∈Ｊ）の一次結合
【数８】
と表わすとき、連立一次方程式
【数９】
は、もとの束縛条件と同値な束縛条件を与える。
【００５１】線形計画問題ステータス計算手段９は、変更起点リスト１０に登録されている線形計画問題を先頭から順次取り出し、取り出した線形計画問題を起点として、上述の作用の項で説明した性質１）ないし性質３）から、その実行可能性が判定できるすべての線形計画問題について、そのステータスを計算し、線形計画問題ステータス保持手段１１内のステータスを変更する。それとともに、ステータスを変更した線形計画問題を変更起点リスト１０の最後尾に追加登録する。
【００５２】変更起点リスト１０には、隣接問題基底解計算手段７および線形計画問題ステータス計算手段９で線形計画問題ステータス保持手段１１内のステータスを変更するごとに、ステータスが変更された（ｊ1 ，・・・，ｊk ）−問題が登録される。
【００５３】線形計画問題ステータス保持手段１１は、各（ｊ1 ，・・・，ｊk ）−問題に対して、ＵＮＫＮＯＷＮ，ＦＥＡＳＩＢＬＥ，ＩＮＦＥＡＳＩＢＬＥ，ＲＥＡＤＹ，ＳＯＬＶＥＤのいずれかのステータスを対応付けて保持する。これらのステータスは、上述の「実行可能性が未知である」、「実行可能である」、「実行不可能である」、「基底解が与えられている」、「解決済みである」の各ステータスに相当する。初期状態においては、全ての問題のステータスはＵＮＫＮＯＷＮである。
【００５４】図２は、本発明の最適解探索装置の一実施例における処理の一例を示すフローチャートである。初期情報として、区間束縛条件保持手段１および共通束縛条件保持手段２には、それぞれ、区間束縛条件、共通束縛条件が格納されているものとする。
【００５５】Ｓ１０１において、線形計画問題管理手段３は、線形計画問題解決エンジン部６に引き渡すべき線形計画問題、すなわち、（ｊ1 ，・・・，ｊk ）−問題を特定する。Ｓ１０２において、線形計画問題管理手段３は、選択された（ｊ1 ，・・・，ｊk ）−問題を線形計画問題として完成させる。Ｓ１０３において、線形計画問題解決エンジン部６は、与えられた線形計画問題を解く。Ｓ１０４において、線形計画問題管理手段３は、線形計画問題解決エンジン部６からの返り値が最適パラメータと目的関数の最小値（最大値）である場合には、線形計画問題と対応付けて局所最適解リスト４に付け加えた後、Ｓ１０１へ戻り、手続きを繰り返す。線形計画問題解決エンジン部６からの返り値が、線形計画問題が実行不可能であることを報告するものである場合には、何もせず、Ｓ１０１へ戻り、手続きを繰り返す。
【００５６】この処理をすべての（ｊ1 ，・・・，ｊk ）−問題について繰り返し行なうことにより、局所最適解リスト４には、解決した（ｊ1 ，・・・，ｊk ）−問題の最適解およびそのときのパラメータが蓄積されている。線形計画問題管理手段３は、この局所最適解リスト４を走査し、最小の解を求める。これにより、区間束縛条件、共通束縛条件を満たす最適解が得られたことになる。
【００５７】以下、Ｓ１０１ないしＳ１０３の各ステップの詳細な処理について説明する。図３は、線形計画問題の特定処理の一例を示すフローチャートである。線形計画問題管理手段３は、以下の手続きを経て、線形計画問題解決エンジン部６に引き渡すべき線形計画問題を特定する。
【００５８】Ｓ１１１において、ＲＥＡＤＹ状態の線形計画問題が線形計画問題ステータス保持手段１１に登録されていれば、Ｓ１１２においてそれを取得する。
【００５９】Ｓ１１３において、ＲＥＡＤＹ状態の線形計画問題が線形計画問題ステータス保持部２２に登録されていない場合、ＦＥＡＳＩＢＬＥ状態の線形計画問題が線形計画問題ステータス保持手段１１に登録されていれば、Ｓ１１４においてそれを取得する。
【００６０】Ｓ１１５において、ＲＥＡＤＹ状態の線形計画問題、ＦＥＡＳＩＢＬＥ状態の線形計画問題のいずれも線形計画問題ステータス保持手段１１に登録されていない場合、ＵＮＫＮＯＷＮ状態の線形計画問題が線形計画問題ステータス保持手段１１に登録されていれば、Ｓ１１６においてそれを取得する。
【００６１】Ｓ１１７において、線形計画問題ステータス保持手段１１に登録されている全ての線形計画問題のステータスがＩＮＦＥＡＳＩＢＬＥ，ＳＯＬＶＥＤのいずれかであるか調べ、そうであるときにはＳ１１８の処理を行ない、少なくとも１つの線形計画問題のステータスがＲＥＡＤＹ，ＦＥＡＳＩＢＬＥ，ＵＮＫＮＯＷＮのいずれかであるときには、Ｓ１１２またはＳ１１４またはＳ１１６で線形計画問題が選択されているので、線形計画問題管理手段３による線形計画問題を特定する処理を終了し、次の線形計画問題を完成させる処理に移る。
【００６２】Ｓ１１７において、線形計画問題ステータス保持手段１１に登録されている全ての線形計画問題のステータスがＩＮＦＥＡＳＩＢＬＥ，ＳＯＬＶＥＤとなると、Ｓ１１８において、線形計画問題管理手段３は、局所最適解リスト４を走査して、登録された目的関数の最小値あるいは最大値の中から、大域的な最小値あるいは最大値を探す。次いで、探した最小値あるいは最大値を与える線形計画問題と最適パラメータを取得する。この最適パラメータが、得ようとする線形計画問題全体の最適解である。このＳ１１８の処理の後、本発明の最適解探索装置の処理を終了する。
【００６３】図４は、線形計画問題を完成させる処理の一例を示すフローチャートである。線形計画問題管理手段３は、図３で説明した線形計画問題の選択処理によって選択された線形計画問題、すなわち、（ｊ1 ，・・・，ｊk ）−問題を以下の手続きによって線形計画問題として完成する。
【００６４】Ｓ１２１において、特定された（ｊ1 ，・・・，ｊk ）−問題のステータスが、ＦＥＡＳＩＢＬＥ，ＵＮＫＮＯＷＮのいずれかである場合は、Ｓ１２２において、区分束縛条件保持手段および共通束縛条件保持手段から、（ｊ1 ，・・・，ｊk ）−問題に属する線形計画問題の束縛条件
【数１０】
を計算する。
【００６５】Ｓ１２３において、特定された（ｊ1 ，・・・，ｊk ）−問題のステータスがＲＥＡＤＹである場合は、Ｓ１２４において、線形計画問題基底解保持手段８中で、（ｊ1 ，・・・，ｊk ）−問題に対応付けられている単体表主要部［ｑi,j］と基底解（ξX ）（Ｘ∈Ω）を取得し、（ｊ1 ，・・・，ｊk ）−問題に属する線形計画問題の束縛条件
【数１１】
を計算する。
【００６６】Ｓ１２５において、目的関数計算手段５から与えられた（ｊ1 ，・・・，ｊk）−問題に対する線形計画問題の目的関数を得る。そして、Ｓ１２６において、Ｓ１２２またはＳ１２４で計算した束縛条件と目的関数からなる線形計画問題を定義し、線形計画問題解決エンジン部６に引き渡す。
【００６７】図５は、線形計画問題の解決処理の一例を示すフローチャートである。線形計画問題解決エンジン部６は、以下の手続きで、線形計画問題管理手段３から与えられた線形計画問題を解く。
【００６８】Ｓ１３１において、与えられた（ｊ1 ，・・・，ｊk ）−問題のステータスがＵＮＫＮＯＷＮであるときには、Ｓ１３２において、線形計画問題解決エンジン部６は、与えられた線形計画問題の実行可能性を線形計画法を用いて判定する。与えられた線形計画問題が実行不可能と判定された場合、Ｓ１３３において、線形計画問題ステータス保持手段１１中の（ｊ1 ，・・・，ｊk ）−問題に対応するステータスをＩＮＦＥＡＳＩＢＬＥに変更する。さらに、（ｊ1 ，・・・，ｊk ）−問題を変更起点リスト１０に登録した上で、線形計画問題ステータス計算手段９を呼び出す。線形計画問題ステータス計算手段９は、（ｊ1 ，・・・，ｊk ）−問題のステータスの変化がもたらす他の線形計画問題のステータスの変化を計算する。また、線形計画問題解決エンジン部６は処理を終え、線形計画問題管理手段３に制御を返す。
【００６９】Ｓ１３２において、該線形計画問題が実行可能と判断された場合、Ｓ１３４において、掃き出し法等を用いて実行可能基底（Ｊ）、基底解（ξX ）（Ｘ∈Ω）、実行可能基底に属する単体表（主要部と非斉次部）［ｑi,j ］i=1,・・・,r,j=1,・・・,2k+m，（ｂi ）i=1,・・・,r を計算して、現在の実行可能基底、基底解、単体表とする。そして、Ｓ１３６へ進む。
【００７０】Ｓ１３１において、与えられた（ｊ1 ，・・・，ｊk ）−問題のステータスがＦＥＡＳＩＢＬＥであるときには、図４のＳ１２２で求めた束縛条件をもとに、Ｓ１３４において、掃き出し法等を用いて実行可能基底（Ｊ）、基底解（ξX ）（Ｘ∈Ω）、実行可能基底に属する単体表（主要部と非斉次部）［ｑi,j ］i=1,・・・,r,j=1,・・・,2k+m，（ｂi ）i=1,・・・,r を計算して、現在の実行可能基底、基底解、単体表とする。そして、Ｓ１３６へ進む。
【００７１】一方、Ｓ１３１において、与えられた（ｊ1 ，・・・，ｊk ）−問題のステータスがＲＥＡＤＹである時には、Ｓ１３５において、線形計画問題基底解保持手段８から（ｊ1 ，・・・，ｊk ）−問題に対応付けられた実行可能基底（Ｊ）を取得して、図４のＳ１２４で計算した［ｑi,j ］i=1,・・・,r,j=1,・・・,2k+mと併せて、現在の実行可能基底、基底解、単体表とする。
【００７２】Ｓ１３６において、現在の実行可能基底を挟んで隣接する線形計画問題の実行可能基底（Ｊ’）、基底解（ξ'X）（Ｘ∈Ω）、（Ｊ’）に属する単体表主要部［ｑ'i,j］i=1,・・・,r,j=1,・・・,2k+mを求め、線形計画問題基底解保持手段８に登録する。この処理は、図６を用いて後述する。
【００７３】Ｓ１３７において、現在の基底解が（ｊ1 ，・・・，ｊk ）−問題の目的関数の最小値（最大値）を与えているか否かを判定し、与えていないときは、Ｓ１３８において、現在の単体表にピボット変換を施して、新たな実行可能基底、基底解、単体表を計算し、現在の実行可能基底、基底解、単体表とした上で、Ｓ１３６の処理を繰り返す。
【００７４】ここで、最小（最大）性の判定、実行可能基底、基底解、単体表の計算方法は単体（シンプレックス）法の単体基準Ｉないし単体基準ＩＩＩとして知られている方法による。
【００７５】Ｓ１３７において、現在の基底解が（ｊ1 ，・・・，ｊk ）−問題の目的関数の最小値（最大値）を与えているならば、Ｓ１３９において（ｊ1 ，・・・，ｊk ）−問題のステータスに応じて、以下の処理を行なう。（ｊ1 ，・・・，ｊk）−問題のステータスがＦＥＡＳＩＢＬＥあるいはＲＥＡＤＹであるときには、Ｓ１４０において、単に線形計画問題ステータス保持手段１１中の（ｊ1 ，・・・，ｊk ）−問題に対応するステータスをＳＥＴＴＬＥＤに変更する。
【００７６】Ｓ１３９において、（ｊ1 ，・・・，ｊk ）−問題のステータスがＵＮＫＮＯＷＮである時には、Ｓ１４１において、線形計画問題ステータス保持手段１１中の（ｊ1 ，・・・，ｊk ）−問題に対応するステータスをＳＥＴＴＬＥＤに変更したうえで、（ｊ1 ，・・・，ｊk ）−問題を変更起点リスト１０に登録し、線形計画問題ステータス計算手段９を呼び出して、他の線形計画問題のステータスの変化を計算させる。
【００７７】Ｓ１４２において、現在の基底解（最適パラメータ）と目的関数の最小値（最大値）を線形計画問題管理手段３に報告するとともに、制御を返す。
【００７８】図６は、現在の実行可能基底を挟んで隣接する線形計画問題の実行可能基底、基底解、単体表主要部を求める処理の一例を示すフローチャートである。図５R>５のＳ１３６で行なわれる処理は以下の手続きで実行される。
【００７９】Ｓ１５１において、判定１を行なう。判定１は、ξy(i)＝０かつ（ｊ1 ，・・・，ｊi-1 ，ｊi ＋１，ｊi+1 ，・・・，ｊk ）−問題のステータスがＵＮＫＮＯＷＮまたはＦＥＡＳＩＢＬＥであるようなインデックスｉが存在するか否かを判定するものである。
【００８０】Ｓ１５１で判定１の条件に合致するインデックスｉが存在するときは、Ｓ１５２において、（ｊ1 ，・・・，ｊi-1 ，ｊi ＋１，ｊi+1 ，・・・，ｊk ）−問題の実行可能基底（Ｊ’）、基底解（ξ'X）（Ｘ∈Ω）、単体表主要部［ｑ'i,j］i=1,・・・,r,j=1,・・・,2k+mを以下のように定める。
【数１２】
ただし、Ｔ-1［ｑi,j ］Ｔは、［ｑi,j ］の（ｚi ，ｙi ）を軸にしたピボット変換、すなわち、新しい実行可能基底（Ｊ’）に関する基底変換の結果であり、Ｊ＝｛Ｘ1 ，・・・，Ｘr ｝，ｚi ＝Ｘl であるとき、変換行列
【数１３】
によって計算される。ここで、Ｅn はｎ次単位行列を表す。
【００８１】Ｓ１５３において、Ｓ１５２で求められた実行可能基底、基底解、単体表主要部を、（ｊ1 ，・・・，ｊi-1 ，ｊi ＋１，ｊi+1 ，・・・，ｊk ）−問題と対応付けて、線形計画問題基底解保持手段８に登録する。
【００８２】Ｓ１５４において、線形計画問題ステータス保持手段１１中の（ｊ1 ，・・・，ｊi-1 ，ｊi ＋１，ｊi+1 ，・・・，ｊk ）−問題のステータスをＲＥＡＤＹに変更し、さらに、（ｊ1 ，・・・，ｊi-1 ，ｊi ＋１，ｊi+1 ，・・・，ｊk）−問題の変更前のステータスがＵＮＫＮＯＷＮであった場合には、（ｊ1 ，・・・，ｊi-1 ，ｊi ＋１，ｊi+1 ，・・・，ｊk ）−問題を変更起点リスト１０の最後尾に追加する。そして、Ｓ１５１へ戻る。
【００８３】Ｓ１５１における判定１において、ξy(i)＝０かつ（ｊ1 ，・・・，ｊi-1 ，ｊi ＋１，ｊi+1 ，・・・，ｊk ）−問題のステータスがＵＮＫＮＯＷＮまたはＦＥＡＳＩＢＬＥであるようなインデックスｉが存在しない場合には、Ｓ１５５において、判定２を行なう。判定２は、ξz(i)＝０かつ（ｊ1 ，・・・，ｊi-1，ｊi −１，ｊi+1 ，・・・，ｊk ）−問題のステータスがＵＮＫＮＯＷＮまたはＦＥＡＳＩＢＬＥであるようなインデックスｉが存在するか否かを判定するものである。この条件を満たすインデックスｉが存在しない場合には、現在の実行可能基底を挟んで隣接する線形計画問題についての処理が終了したものとして、図５のＳ１３６の処理を終了する。
【００８４】Ｓ１５５における判定２において、条件に合致するインデックスｉが存在するときは、Ｓ１５６において、（ｊ1 ，・・・，ｊi-1 ，ｊi −１，ｊi+1 ，・・・，ｊk ）−問題の実行可能基底（Ｊ’）、基底解（ξ'X）（Ｘ∈Ω）、単体表主要部［ｑ'i,j］i=1,・・・,r,j=1,・・・,2k+mを以下のように定める。
【数１４】
ただし、Ｔ-1［ｑi,j ］Ｔは、［ｑi,j ］の（ｙi ，ｚi ）を軸にしたピボット変換、すなわち、新しい実行可能基底（Ｊ’）に関する基底変換の結果であり、Ｊ＝｛Ｘ1 ，・・・，Ｘr ｝，ｙi ＝Ｘl であるとき、変換行列
【数１５】
によって計算される。
【００８５】Ｓ１５７において、求められた実行可能基底、基底解、単体表主要部は、（ｊ1 ，・・・，ｊi-1 ，ｊi −１，ｊi+1 ，・・・，ｊk ）−問題と対応付けて、線形計画問題基底解保持手段８に登録する。
【００８６】Ｓ１５８において、線形計画問題ステータス保持手段１１中の（ｊ1 ，・・・，ｊi-1 ，ｊi −１，ｊi+1 ，・・・，ｊk ）−問題のステータスをＲＥＡＤＹに変更し、さらに、（ｊ1 ，・・・，ｊi-1 ，ｊi −１，ｊi+1 ，・・・，ｊk）−問題の変更前のステータスがＵＮＫＮＯＷＮであった場合には、（ｊ1 ，・・・，ｊi-1 ，ｊi −１，ｊi+1 ，・・・，ｊk ）−問題を変更起点リスト１０の最後尾に追加する。
【００８７】上述のような処理により、ステータスがＩＮＦＥＡＳＩＢＬＥの場合には線形計画問題の解決の処理を行なわず、また、ステータスがＦＥＡＳＩＢＬＥの場合には、実行可能性を判断する処理を省略することができる。さらに、ステータスがＲＥＡＤＹの場合には、線形計画問題基底解保持手段８に登録されている実行可能基底、基底解、単体表主要部を用いることにより、これらの計算を省略することが可能となる。このように、線形計画法の処理の一部を省略することにより、処理速度を向上させることができる。
【００８８】図７は、線形計画問題ステータス計算手段９の動作の一例を示すフローチャートである。線形計画問題ステータス計算手段９が線形計画問題解決エンジン部６により起動されると、以下の手順で処理を行なう。
【００８９】Ｓ１６１において、変更起点リスト１０が空であれば処理を終了し、制御を線形計画問題解決エンジン部６に返す。変更起点リスト１０が空でないときは、Ｓ１６２において、変更起点リスト１０の先頭の線形計画問題を取り去り、取り去った線形計画問題を起点として、以下のステータスの変更を実行する。
【００９０】Ｓ１６３において、起点線形計画問題（例えば、（ｊ1 ，・・・，ｊk ）−問題とする）のステータスが、ＳＯＬＶＥＤ，ＲＥＡＤＹ，ＦＥＡＳＩＢＬＥのいずれかであるか否かを判定し、そのいずれかであるときはＳ１６４の処理を行ない、ＩＮＦＥＡＳＩＢＬＥであるときはＳ１６５の処理を行なった後、Ｓ１６１へ戻る。
【００９１】図８は、起点線形計画問題のステータスがＳＯＬＶＥＤ，ＲＥＡＤＹ，ＦＥＡＳＩＢＬＥのいずれかである場合の線形計画問題ステータス計算手段の動作の一例を示すフローチャートである。この処理は、起点線形計画問題が少なくとも実行可能である場合に、そのステータスを隣接する線形計画問題に伝播させるための処理である。初期設定として、Ｓ１７１において、インデックスｉを１に設定する。
【００９２】Ｓ１７２において、ｊi ＞１のとき、次の条件のいずれかを満たす最大のａ＜ｊi を探索する。
（１）（ｊ1 ，・・・，ｊi-1 ，ａ，ｊi+1 ，・・・，ｊk ）−問題のステータスは、ＳＯＬＶＥＤ，ＲＥＡＤＹ，ＦＥＡＳＩＢＬＥのいずれかである。
（２）（ｊ1 ，・・・，ｊi-1 ，ａ，ｊi+1 ，・・・，ｊk ）−問題のステータスはＩＮＦＥＡＳＩＢＬＥである。
（３）ａ＝１である。
【００９３】Ｓ１７３において、Ｓ１７２で探索されたａが、上述の条件「（１）（ｊ1 ，・・・，ｊi-1 ，ａ，ｊi+1 ，・・・，ｊk ）−問題のステータスは、ＳＯＬＶＥＤ，ＲＥＡＤＹ，ＦＥＡＳＩＢＬＥのいずれかである。」を満たすときは、Ｓ１７４において、ａ＜ｊ＜ｊi を満たすｊについて、（ｊ1 ，・・・，ｊi-1 ，ｊ，ｊi+1 ，・・・，ｊk ）−問題のステータスがＵＮＫＮＯＷＮであれば、ステータスをＦＥＡＳＩＢＬＥに変更する操作を施す。
【００９４】Ｓ１７５において、Ｓ１７２で探索されたａが、上述の条件「（２）（ｊ1 ，・・・，ｊi-1 ，ａ，ｊi+1 ，・・・，ｊk ）−問題のステータスはＩＮＦＥＡＳＩＢＬＥである。」を満たすとき、Ｓ１７６において、ｊ＜ａを満たすすべてのｊについて、（ｊ1 ，・・・，ｊi-1 ，ｊ，ｊi+1 ，・・・，ｊk ）−問題のステータスがＵＮＫＮＯＷＮであれば、ステータスをＩＮＦＥＡＳＩＢＬＥに変更する操作を施す。
【００９５】Ｓ１７７において、ｊi ＜ｋi −１のとき、次の条件のいずれかを満たす最小のｂ＞ｊi を探索する。
（１）（ｊ1 ，・・・，ｊi-1 ，ｂ，ｊi+1 ，・・・，ｊk ）−問題のステータスはＳＯＬＶＥＤ，ＲＥＡＤＹ，ＦＥＡＳＩＢＬＥのいずれかである。
（２）（ｊ1 ，・・・，ｊi-1 ，ｂ，ｊi+1 ，・・・，ｊk ）−問題のステータスはＩＮＦＥＡＳＩＢＬＥである。
（３）ｂ＝ｋi −１である。
【００９６】Ｓ１７８において、Ｓ１７７で探索されたｂが、上述の条件「（１）（ｊ1 ，・・・，ｊi-1 ，ｂ，ｊi+1 ，・・・，ｊk ）−問題のステータスはＳＯＬＶＥＤ，ＲＥＡＤＹ，ＦＥＡＳＩＢＬＥのいずれかである。」を満たすときは、Ｓ１７９において、ｂ＞ｊ＞ｊi を満たす全てのｊについて、（ｊ1 ，・・・，ｊi-1 ，ｊ，ｊi+1 ，・・・，ｊk ）−問題のステータスがＵＮＫＮＯＷＮであれば、ステータスをＦＥＡＳＩＢＬＥに変更する操作を施す。
【００９７】Ｓ１８０において、Ｓ１７７で探索されたｂが、上述の条件「（２）（ｊ1 ，・・・，ｊi-1 ，ｂ，ｊi+1 ，・・・，ｊk ）−問題のステータスはＩＮＦＥＡＳＩＢＬＥである。」を満たすときは、Ｓ１８１において、ｊ＜ｂを満たすすべてのｊについて、（ｊ1 ，・・・，ｊi-1 ，ｊ，ｊi+1 ，・・・，ｊk ）−問題のステータスがＵＮＫＮＯＷＮであればステータスをＩＮＦＥＡＳＩＢＬＥに変更する操作を施す。
【００９８】Ｓ１８２において、Ｓ１７１ないしＳ１８１の処理でステータスが変更された全ての線形計画問題を変更起点リスト１０の最後尾に追加する。
【００９９】Ｓ１８３において、インデックスｉが最後であるか、すなわち、ｉ＝ｋであるかをチェックし、そうであれば図７のＳ１６４の処理を終了する。もし、ｉ＜ｋであれば、Ｓ１８４において、インデックスｉを１増やして、Ｓ１７２以降の処理を繰り返す。
【０１００】図９は、起点線形計画問題のステータスがＩＮＦＥＡＳＩＢＬＥである場合の線形計画問題ステータス計算手段の動作の一例を示すフローチャートである。この処理は、起点線形計画問題が実行不可能の場合に、そのステータスを隣接する線形計画問題に伝播させるための処理である。初期設定として、Ｓ１９１において、インデックスｉを１に設定する。
【０１０１】Ｓ１９２において、ｊi ＞１のとき、次の条件のいずれかを満たす最大のａ＜ｊi を探索する。
（１）（ｊ1 ，・・・，ｊi-1 ，ａ，ｊi+1 ，・・・，ｊk ）−問題のステータスは、ＳＯＬＶＥＤ，ＲＥＡＤＹ，ＦＥＡＳＩＢＬＥのいずれかである。
（２）ａ＝１である。
【０１０２】Ｓ１９３において、Ｓ１９２で探索されたａが、上述の条件「（１）（ｊ1 ，・・・，ｊi-1 ，ａ，ｊi+1 ，・・・，ｊk ）−問題のステータスは、ＳＯＬＶＥＤ，ＲＥＡＤＹ，ＦＥＡＳＩＢＬＥのいずれかである。」を満たすときは、ｊ＞ｊi を満たす全てのｊについて、（ｊ1 ，・・・，ｊi-1 ，ｊ，ｊi+1 ，・・・，ｊk ）−問題のステータスがＵＮＫＮＯＷＮであれば、ステータスをＩＮＦＥＡＳＩＢＬＥに変更する操作を施す。
【０１０３】Ｓ１９４において、ｊi ＜ｋi −１のとき、次の条件のいずれかを満たす最小のｂ＞ｊi を探索する。
（１）（ｊ1 ，・・・，ｊi-1 ，ｂ，ｊi+1 ，・・・，ｊk ）−問題のステータスは、ＳＯＬＶＥＤ，ＲＥＡＤＹ，ＦＥＡＳＩＢＬＥのいずれかである。
（２）ｂ＝ｋi −１である。
【０１０４】Ｓ１９５において、Ｓ１９４で探索されたｂが、上述の条件「（１）（ｊ1 ，・・・，ｊi-1 ，ｂ，ｊi+1 ，・・・，ｊk ）−問題のステータスは、ＳＯＬＶＥＤ，ＲＥＡＤＹ，ＦＥＡＳＩＢＬＥのいずれかである。」を満たすときは、ｊ＜ｊi を満たす全てのｊについて、（ｊ1 ，・・・，ｊi-1 ，ｊ，ｊi+1 ，・・・，ｊk ）−問題のステータスがＵＮＫＮＯＷＮであれば、ＩＮＦＥＡＳＩＢＬＥに変更する操作を施す。
【０１０５】Ｓ１９６において、Ｓ１９１ないしＳ１９５でステータスが変更された全ての線形計画問題を、変更起点リスト１０の最後尾に追加する。
【０１０６】Ｓ１９７において、インデックスｉが最後であるか、すなわち、ｉ＝ｋであるかをチェックし、そうであれば図７のＳ１６５の処理を終了する。もし、ｉ＜ｋであれば、Ｓ１９８において、インデックスｉを１増やしてＳ１９２に戻り、次のｉについて処理を繰り返す。
【０１０７】図７ないし図９で示した処理により、起点線形計画問題から実行可能あるいは実行不可能が判別される線形計画問題について、ステータスを変更することができ、変更された線形計画問題については線形計画法に基づく実行可能性の判断処理を行なう必要がなくなるため、処理の高速化を図ることができる。
【０１０８】本発明の最適解探索装置は、例えば、表のレイアウト生成処理に用いることができる。表はその各項目欄にテキストが配置される。表の各欄の幅を決めると、テキストの行折りの数が決定され、それに伴って表の行の高さが決定される。逆に、高さが決まれば、テキストの行折り数が決定され、各列の幅も決まる。いま、テキストの行折りの数が不変となる範囲内で各欄の幅を可変とすることを考える。すると、各欄の幅は、階段関数として表現できる。その境界値を区間特性列とし、区間束縛条件を設定することができる。この区間特性列は、表の各列ごとに設定される。共通束縛条件としては、例えば、表の全体の幅などの条件が設定される。
【０１０９】各区間束縛条件の間では、テキストの行折りの数が不変であるから、行の高さは一意に決まる。表のレイアウトの最適性は、例えば、表の面積や周囲長、各欄に発生する空隙の和等で測ることができる。これらの値は、行の高さが一意に決まることから、各欄の幅を設定するためのパラメータを用いた一次式で表現することができる。これを目的関数とする。
【０１１０】このように設定された区間束縛条件、共通束縛条件、および、目的関数により生成される線形計画問題を解決する。このとき生成される線形計画問題の数は、各列ごとの区間特性列から１つずつ値を取り出すときの組み合わせの数だけ存在する。例えば、２つの欄に２文字ずつ配置する表を考えると、各欄に配置されるテキストが１行の場合と、行折りが発生して２行となる場合の２通りあり、それがそれぞれの列で発生するので、その組み合わせは４通りであり、解決する線形計画問題は４つとなる。同様に、３文字ずつ配置する場合には９つというように、解決すべき線形計画問題はテキスト量や列数等によって飛躍的に増大する。
【０１１１】本発明の最適解探索装置を用いることによって、線形計画問題を解決するために必要な計算量を激減させることができ、高速に最適な表のレイアウトを得ることができる。
【０１１２】本発明は、表のレイアウト以外にも、通常、線形計画問題が利用されている広範な分野において用いることができる。
【０１１３】
【発明の効果】以上の説明から明らかなように、本発明によれば、１つの線形計画問題を解く過程で計算される基底解から、隣接する他の線形計画問題の基底解を計算することによって、計算を複数の線形計画問題で共有し、処理の効率を向上させることができる。
【０１１４】また、線形計画問題の実行可能性の判定結果をステータスとして保持し、実行可能性が未知である他の線形計画問題の実行可能性を判定してステータスを変更しておき、線形計画問題を解決する際にこのステータスを参照することによってすでに実行可能性が判定されているものについては実行可能性の判定処理を省略することができ、処理の効率を向上させることができる。
【０１１５】さらに実行可能を示すステータスとして、例えば、実行可能性が判定された段階、基底解が計算された段階、すでに解決済みの段階というように細分することにより、基底解が計算されているものについては、実行可能性の判定と基底解の計算処理が、また、実行可能を示すものについては、実行可能性の判定処理が、それぞれ省略でき、処理効率の向上を図ることができる。
【０１１６】これらのステータスに優先順位を持たせ、線形計画問題を選択する際に、より計算量が少なくなるように選択してゆくことによって、さらに処理の効率を向上させることができるという効果がある。
【図面の簡単な説明】
【図１】 本発明の最適解探索装置の一実施例を示す構成図である。
【図２】 本発明の最適解探索装置の一実施例における処理の一例を示すフローチャートである。
【図３】 線形計画問題の特定処理の一例を示すフローチャートである。
【図４】 線形計画問題を完成させる処理の一例を示すフローチャートである。
【図５】 線形計画問題の解決処理の一例を示すフローチャートである。
【図６】 現在の実行可能基底を挟んで隣接する線形計画問題の実行可能基底、基底解、単体表主要部を求める処理の一例を示すフローチャートである。
【図７】 線形計画問題ステータス計算手段９の動作の一例を示すフローチャートである。
【図８】 起点線形計画問題のステータスがＳＯＬＶＥＤ，ＲＥＡＤＹ，ＦＥＡＳＩＢＬＥのいずれかである場合の線形計画問題ステータス計算手段の動作の一例を示すフローチャートである。
【図９】 起点線形計画問題のステータスがＩＮＦＥＡＳＩＢＬＥである場合の線形計画問題ステータス計算手段の動作の一例を示すフローチャートである。この処理は、起点線形計画問題が実行不可能の場合に、そのステータスを隣接する線形計画問題に伝播させるための処理である。
【符号の説明】
１…区間束縛条件保持手段、２…共通束縛条件保持手段、３…線形計画問題間利手段、４…局所最適解リスト、５…目的関数計算手段、６…線形計画問題解決エンジン部、７…隣接問題基底解計算手段、８…線形計画問題基底解保持手段、９…線形計画問題ステータス計算手段、１０…変更起点リスト、１１…線形計画問題ステータス保持手段。
【特許請求の範囲】
【請求項１】 複数の線形計画問題から構成される複合線形計画問題の最適解を計算する最適解探索装置において、複数のパラメータに関する有限個の斉次一次関数を保持するとともに各斉次一次関数に付随する２個以上の実数からなる単調増加数列であって斉次一次関数の上限と下限を隣接する実数として有する区間特性列を保持する区間束縛条件保持手段と、常にパラメータ間に成立すべき一次方程式または一次不等式を共通束縛条件として保持する共通束縛条件保持手段と、前記区間束縛条件保持手段に保持されている各斉次一次関数の区間特性列から隣接する２個の実数を選択して得られる束縛条件の組ごとにパラメータに関する一次式として目的関数を計算する目的関数計算手段と、該目的関数計算手段で計算された目的関数と該目的関数に対応する束縛条件の組および前記共通束縛条件保持手段に保持されている共通束縛条件等からなる線形計画問題を実行可能基底および基底解を計算しながら解決する線形計画問題解決エンジン部と、線形計画問題解決エンジン部が実行可能基底と基底解を計算するたびに計算された実行可能基底を挟んで隣接する線形計画問題の実行可能基底と基底解を計算する隣接問題基底解計算手段と、計算済みの実行可能基底および基底解を線形計画問題と対応づけて保持する線形計画問題基底解保持手段と、前記区間束縛条件保持手段と前記共通束縛条件保持手段と前記目的関数計算手段と前記線形計画問題解決エンジン部を制御し前記線形計画問題解決エンジン部から前記束縛条件の組ごとに得られた結果をもとに最適値を探索する線形計画問題管理手段を有し、前記線形計画問題解決エンジン部が新たに線形計画問題を解きはじめる際に、前記線形計画問題基底解保持手段に解くべき線形計画問題に対応する実行可能基底と基底解が存在すれば、その実行可能基底と基底解を用いて計算を開始することを特徴とする最適解探索装置。
【請求項２】 複合線形計画問題の最適解を計算する最適解探索装置において、複数のパラメータに関する有限個の斉次一次関数を保持するとともに各斉次一次関数に付随する２個以上の実数からなる単調増加数列であって斉次一次関数の上限と下限を隣接する実数として有する区間特性列を保持する区間束縛条件保持手段と、常にパラメータ間に成立すべき一次方程式または一次不等式を共通束縛条件として保持する共通束縛条件保持手段と、前記区間束縛条件保持手段に保持されている各斉次一次関数の区間特性列から隣接する２個の実数を選択して得られる束縛条件の組ごとにパラメータに関する一次式として目的関数を計算する目的関数計算手段と、前記束縛条件の組ごとに導出される線形計画問題それぞれに対して、少なくとも「実行可能である」、「実行不可能である」、「実行可能性が未知である」を指示するステータスを保持する線形計画問題ステータス保持手段と、前記目的関数計算手段で計算された目的関数と該目的関数に対応する束縛条件の組および前記共通束縛条件保持手段に保持されている共通束縛条件等からなる線形計画問題について実行可能性を判断して前記線形計画問題ステータス保持手段に保持されている該線形計画問題のステータスを変更した上で該線形計画問題を解決する線形計画問題解決エンジン部と、該線形計画問題解決エンジン部が各線形計画問題についてその実行可能性を判定するたびに該線形計画問題のステータスの変化がもたらす他の線形計画問題のステータスの変化を再計算し前記線形計画問題ステータス保持手段に保持されているステータスを変更する線形計画問題ステータス計算手段と、前記区間束縛条件保持手段と前記共通束縛条件保持手段と前記目的関数計算手段と前記線形計画問題解決エンジン部を制御し前記線形計画問題解決エンジン部から前記束縛条件の組ごとに得られた結果をもとに最適値を探索する線形計画問題管理手段を有し、前記線形計画問題解決エンジン部が線形計画問題を解く際に、前記線形計画問題ステータス保持手段に保持されているステータスを参照し、少なくとも「実行可能性が未知である」ステータス以外の場合には、該線形計画問題の実行可能性の判定処理を行なわないことを特徴とする最適解探索装置。
【請求項３】 複合線形計画問題の最適解を計算する最適解探索装置において、複数のパラメータに関する有限個の斉次一次関数を保持するとともに各斉次一次関数に付随する２個以上の実数からなる単調増加数列であって斉次一次関数の上限と下限を隣接する実数として有する区間特性列を保持する区間束縛条件保持手段と、常にパラメータ間に成立すべき一次方程式または一次不等式を共通束縛条件として保持する共通束縛条件保持手段と、前記区間束縛条件保持手段に保持されている各斉次一次関数の区間特性列から隣接する２個の実数を選択して得られる束縛条件の組ごとにパラメータに関する一次式として目的関数を計算する目的関数計算手段と、前記束縛条件の組ごとに導出される線形計画問題それぞれに対して、少なくとも「解決済みである」、「基底解保持済みである」、「実行可能である」、「実行不可能である」、「実行可能性が未知である」を指示するステータスを保持する線形計画問題ステータス保持手段と、前記目的関数計算手段で計算された目的関数と該目的関数に対応する束縛条件の組および前記共通束縛条件保持手段に保持されている共通束縛条件等からなる線形計画問題の実行可能性の判定および実行可能基底と基底解の計算を行ない、各処理において前記線形計画問題ステータス保持手段に保持されているステータスを変更しながら線形計画問題を解決する線形計画問題解決エンジン部と、該線形計画問題解決エンジン部が実行可能基底と基底解を計算するたびに計算された実行可能基底を挟んで隣接する線形計画問題の実行可能基底と基底解を計算するとともに前記線形計画問題ステータス保持手段に保持されている該隣接問題のステータスを変更する隣接問題基底解計算手段と、計算済みの実行可能基底および基底解を保持する線形計画問題基底解保持手段と、前記線形計画問題解決エンジン部および前記隣接問題基底解計算手段の処理に従い線形計画問題のステータスの変化がもたらす他の線形計画問題のステータスの変化を再計算し前記線形計画問題ステータス保持手段に保持されているステータスを変更する線形計画問題ステータス計算手段と、前記区間束縛条件保持手段と前記共通束縛条件保持手段と前記目的関数計算手段と前記線形計画問題解決エンジン部を制御し前記線形計画問題解決エンジン部から前記束縛条件の組ごとに得られた結果をもとに最適値を探索する線形計画問題管理手段を有し、前記線形計画問題解決エンジン部が線形計画問題を解く際に、前記線形計画問題ステータス保持手段に保持されているステータスを参照し、少なくとも「実行可能性が未知である」ステータス以外の場合には該線形計画問題の実行可能性の判定処理を行なわず、ステータスが「基底解保持済みである」ことを示している場合には前記線形計画問題基底解保持手段から実行可能基底と基底解を得て計算を開始することを特徴とする最適解探索装置。
【請求項４】 前記線形計画問題ステータス保持手段に保持されたステータスは優先順位を持っており、前記線形計画問題管理手段は、該ステータスの優先順位に基づいて線形計画問題を解く順序を決定することを特徴とする請求項２または３に記載の最適解探索装置。
【請求項１】 複数の線形計画問題から構成される複合線形計画問題の最適解を計算する最適解探索装置において、複数のパラメータに関する有限個の斉次一次関数を保持するとともに各斉次一次関数に付随する２個以上の実数からなる単調増加数列であって斉次一次関数の上限と下限を隣接する実数として有する区間特性列を保持する区間束縛条件保持手段と、常にパラメータ間に成立すべき一次方程式または一次不等式を共通束縛条件として保持する共通束縛条件保持手段と、前記区間束縛条件保持手段に保持されている各斉次一次関数の区間特性列から隣接する２個の実数を選択して得られる束縛条件の組ごとにパラメータに関する一次式として目的関数を計算する目的関数計算手段と、該目的関数計算手段で計算された目的関数と該目的関数に対応する束縛条件の組および前記共通束縛条件保持手段に保持されている共通束縛条件等からなる線形計画問題を実行可能基底および基底解を計算しながら解決する線形計画問題解決エンジン部と、線形計画問題解決エンジン部が実行可能基底と基底解を計算するたびに計算された実行可能基底を挟んで隣接する線形計画問題の実行可能基底と基底解を計算する隣接問題基底解計算手段と、計算済みの実行可能基底および基底解を線形計画問題と対応づけて保持する線形計画問題基底解保持手段と、前記区間束縛条件保持手段と前記共通束縛条件保持手段と前記目的関数計算手段と前記線形計画問題解決エンジン部を制御し前記線形計画問題解決エンジン部から前記束縛条件の組ごとに得られた結果をもとに最適値を探索する線形計画問題管理手段を有し、前記線形計画問題解決エンジン部が新たに線形計画問題を解きはじめる際に、前記線形計画問題基底解保持手段に解くべき線形計画問題に対応する実行可能基底と基底解が存在すれば、その実行可能基底と基底解を用いて計算を開始することを特徴とする最適解探索装置。
【請求項２】 複合線形計画問題の最適解を計算する最適解探索装置において、複数のパラメータに関する有限個の斉次一次関数を保持するとともに各斉次一次関数に付随する２個以上の実数からなる単調増加数列であって斉次一次関数の上限と下限を隣接する実数として有する区間特性列を保持する区間束縛条件保持手段と、常にパラメータ間に成立すべき一次方程式または一次不等式を共通束縛条件として保持する共通束縛条件保持手段と、前記区間束縛条件保持手段に保持されている各斉次一次関数の区間特性列から隣接する２個の実数を選択して得られる束縛条件の組ごとにパラメータに関する一次式として目的関数を計算する目的関数計算手段と、前記束縛条件の組ごとに導出される線形計画問題それぞれに対して、少なくとも「実行可能である」、「実行不可能である」、「実行可能性が未知である」を指示するステータスを保持する線形計画問題ステータス保持手段と、前記目的関数計算手段で計算された目的関数と該目的関数に対応する束縛条件の組および前記共通束縛条件保持手段に保持されている共通束縛条件等からなる線形計画問題について実行可能性を判断して前記線形計画問題ステータス保持手段に保持されている該線形計画問題のステータスを変更した上で該線形計画問題を解決する線形計画問題解決エンジン部と、該線形計画問題解決エンジン部が各線形計画問題についてその実行可能性を判定するたびに該線形計画問題のステータスの変化がもたらす他の線形計画問題のステータスの変化を再計算し前記線形計画問題ステータス保持手段に保持されているステータスを変更する線形計画問題ステータス計算手段と、前記区間束縛条件保持手段と前記共通束縛条件保持手段と前記目的関数計算手段と前記線形計画問題解決エンジン部を制御し前記線形計画問題解決エンジン部から前記束縛条件の組ごとに得られた結果をもとに最適値を探索する線形計画問題管理手段を有し、前記線形計画問題解決エンジン部が線形計画問題を解く際に、前記線形計画問題ステータス保持手段に保持されているステータスを参照し、少なくとも「実行可能性が未知である」ステータス以外の場合には、該線形計画問題の実行可能性の判定処理を行なわないことを特徴とする最適解探索装置。
【請求項３】 複合線形計画問題の最適解を計算する最適解探索装置において、複数のパラメータに関する有限個の斉次一次関数を保持するとともに各斉次一次関数に付随する２個以上の実数からなる単調増加数列であって斉次一次関数の上限と下限を隣接する実数として有する区間特性列を保持する区間束縛条件保持手段と、常にパラメータ間に成立すべき一次方程式または一次不等式を共通束縛条件として保持する共通束縛条件保持手段と、前記区間束縛条件保持手段に保持されている各斉次一次関数の区間特性列から隣接する２個の実数を選択して得られる束縛条件の組ごとにパラメータに関する一次式として目的関数を計算する目的関数計算手段と、前記束縛条件の組ごとに導出される線形計画問題それぞれに対して、少なくとも「解決済みである」、「基底解保持済みである」、「実行可能である」、「実行不可能である」、「実行可能性が未知である」を指示するステータスを保持する線形計画問題ステータス保持手段と、前記目的関数計算手段で計算された目的関数と該目的関数に対応する束縛条件の組および前記共通束縛条件保持手段に保持されている共通束縛条件等からなる線形計画問題の実行可能性の判定および実行可能基底と基底解の計算を行ない、各処理において前記線形計画問題ステータス保持手段に保持されているステータスを変更しながら線形計画問題を解決する線形計画問題解決エンジン部と、該線形計画問題解決エンジン部が実行可能基底と基底解を計算するたびに計算された実行可能基底を挟んで隣接する線形計画問題の実行可能基底と基底解を計算するとともに前記線形計画問題ステータス保持手段に保持されている該隣接問題のステータスを変更する隣接問題基底解計算手段と、計算済みの実行可能基底および基底解を保持する線形計画問題基底解保持手段と、前記線形計画問題解決エンジン部および前記隣接問題基底解計算手段の処理に従い線形計画問題のステータスの変化がもたらす他の線形計画問題のステータスの変化を再計算し前記線形計画問題ステータス保持手段に保持されているステータスを変更する線形計画問題ステータス計算手段と、前記区間束縛条件保持手段と前記共通束縛条件保持手段と前記目的関数計算手段と前記線形計画問題解決エンジン部を制御し前記線形計画問題解決エンジン部から前記束縛条件の組ごとに得られた結果をもとに最適値を探索する線形計画問題管理手段を有し、前記線形計画問題解決エンジン部が線形計画問題を解く際に、前記線形計画問題ステータス保持手段に保持されているステータスを参照し、少なくとも「実行可能性が未知である」ステータス以外の場合には該線形計画問題の実行可能性の判定処理を行なわず、ステータスが「基底解保持済みである」ことを示している場合には前記線形計画問題基底解保持手段から実行可能基底と基底解を得て計算を開始することを特徴とする最適解探索装置。
【請求項４】 前記線形計画問題ステータス保持手段に保持されたステータスは優先順位を持っており、前記線形計画問題管理手段は、該ステータスの優先順位に基づいて線形計画問題を解く順序を決定することを特徴とする請求項２または３に記載の最適解探索装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【公開番号】特開平７−２８２０３６
【公開日】平成７年（１９９５）１０月２７日
【国際特許分類】
【出願番号】特願平６−６８２５５
【出願日】平成６年（１９９４）４月６日
【出願人】（０００００５４９６）富士ゼロックス株式会社 (21,908)
【公開日】平成７年（１９９５）１０月２７日
【国際特許分類】
【出願日】平成６年（１９９４）４月６日
【出願人】（０００００５４９６）富士ゼロックス株式会社 (21,908)
[ Back to top ]