(57)【要約】【課題】本発明は、拘束条件が過剰下における最適資源割当を行う設計支援方法及び設計支援装置を提供することを課題とする。【解決手段】物理的又は経済的資源の配分を行うための設計支援方法及び装置において、該極大化乃至極小化問題を、ヘッセの標準形表現を用いて、複数の等式拘束条件が形成する高次元空間の凸多面体が囲む許容定義領域の中で目的関数を最大化させる問題へと書き直し、該領域を該空間の半空間領域で扱い、該半空間領域の形成に寄与せぬ拘束条件を除去し、また、不要な拘束条件を除去し、複数の等式拘束条件が形成する高次元空間のピラミッド錐の解頂点形成条件を明確化し、解適合性判定演算時間を短縮し、適合解頂点絞り込み乃至は該解頂点への到達時間の高速化を図り、更には、整数計画問題解法への連動応用性を確保して、物理的乃至は経済的資源の配分を行う。【選択図】図5
2012203710.tif 000002
【特許請求の範囲】
【請求項１】
物理的又は経済的資源の配分を行うための設計支援方法であって、
目的関数f(ｘ)が次元数ｎが2以上のｎ次元ユークリッド空間Enの中の実ベクトルx=[x1
x2・・・xn]t∈Enとして表され、該ベクトルxのｎ個の成分x1,x2,・・・,xnは実の未知変数であり、該目的関数f(ｘ)は未知変数ベクトルxに関して極大化乃至極小化され、その際、ｎ以上の整数個数m1個の線型不等式拘束条件gi(ｘ)≧0あるいはgi(ｘ)≦0,(i=1,・・・,m1)が課せられ、該配分方法が、当該線型計画問題を解く、物理的乃至は経済的資源の配分を行う設計支援方法において、該方法が、
該極大化乃至極小化問題を、ヘッセの標準形表現を用いて、
不等式拘束条件    gi(ｘ)=<ni,x>≦pi  (i=1,・・・,m1)
が形成する共通領域の中で、
目的関数f(ｘ)=<nf,x>=pf
を最大化させる問題へと書き直し、
ここに各pfは正として、集合{ｘ｜<nf,x>=pf}は該空間Enの中で(n-1)次元の超平面Πf(ｘ)={ｘ｜<nf,x>=pf}を形成し、方向余弦ベクトルnfは該空間Enの原点Ｏより該超平面Πf(ｘ)に向かって直交する方向の単位ベクトルであり、該nfの向きは該原点Ｏより該超平面Πf(ｘ)に向かう方向とし、pfは該原点Ｏと、該原点より該超平面Πf(ｘ)に下ろした垂線の足Ffとの正なる距離であり、該pfは拘束条件全てを満足する最小値となるよう探索され、一方、集合{ｘ｜<ni,x>=pi},(i=1,・・・,m1)は該空間Enの中で(n-1)次元の超平面Πi(ｘ)={ｘ｜<ni,x>=pi},(i=1,・・・,m1)を形成し、各方向余弦ベクトルniは該原点より該超平面Πi(ｘ)に向かって直交する方向の単位ベクトルであり、該niの向きは該原点Ｏより該超平面Πf(ｘ)に向かう方向とし、piは該原点Ｏと、該原点Ｏより該超平面Πi(ｘ)に下ろした垂線の足Fiとの正なる距離であって、上記規約の下に、当該線型計画問題を該ヘッセの標準形表現に書き改める、第1のステップと、
該拘束条件gi(ｘ)=<ni,x>≦pi,(i=1,・・・,m1)の各々に呼応して、各niとnｆとの内積<ni,nf>,(i=1,・・・,m1)の各々の正負を判定し、負となる拘束条件を除外して、拘束条件の数を減ずる第2のステップと
を備えたことを特徴とする設計支援方法。
【請求項２】
残された拘束条件の中から、二つの互いに異なる拘束条件の任意の組｛gk(ｘ)=<nk,x>≦pk及びgl(ｘ)=<nl,x>≦pl｝を取り上げ、それぞれの組において、(1-内積<nk,nl>)の値を算出し、該算出値が、予め定められた値より小さいか、pkとplの相対比が予め設定された範囲を逸脱する場合は、pkとplの大きい方に対応する拘束条件を取り除いて、さらに拘束条件の数を減ずる第3のステップを更に備えたことを特徴とする請求項1に記載の設計支援方法。
【請求項３】
残された拘束条件を改めて、等式条件と見なして
gi(ｘ)=<ni,x>=pi≧0,(i=1,・・・,m)
とし、m≧ｎなることを確認し、
残されたm個の拘束条件からｎ個の拘束条件を選ぶにあたり、垂線距離p1,p2,p3,・・・,pmの大小バランスがとれているときは、<ni,nf>が1に近い拘束条件を取り上げ、垂線距離p1,p2,p3,・・・,pmに大小バランスがとれてないときは、垂線距離の小さい方の拘束条件を含めて<ni,nf>が1に近い拘束条件を取り上げる、予め定められた選定基準により、mCn個の組合せの中から、少なくとも一つの組を取り上げる第4のステップと、
選定された一つの組の、ｎ元ｎ次の連立方程式
gpi(ｘ)=<npi,x>=ppi≧0,(pi=p1,p2,・・・・・・,pn)
を解き、解頂点候補を求めるにあったて、対応する方向余弦ベクトルの組
npi,(pi=p1,p2,・・・・・・,pn)
が、前記空間Enの中でその原点を起点として形成するn次元ピラミッド錘をなし、該ピラミッド錘が凸錐であり、且つ、該ピラミッド錘内部に、該原点を起点として置かれた前記方向余弦ベクトルnｆが含まれることを確認する第5のステップと
を更に備えたことを特徴とする請求項1に記載の設計支援方法。
【請求項４】
残された拘束条件を改めて、等式条件と見なして
gi(ｘ)=<ni,x>=pi≧0,(i=1,・・・,m)
とし、m≧ｎなることを確認し、
残されたm個の拘束条件からｎ個の拘束条件を選ぶにあたり、垂線距離p1,p2,p3,・・・,pmの大小バランスがとれているときは、<ni,nf>が1に近い拘束条件を取り上げ、垂線距離p1,p2,p3,・・・,pmに大小バランスがとれてないときは、垂線距離の小さい方の拘束条件を含めて<ni,nf>が1に近い拘束条件を取り上げる、予め定められた選定基準により、mCn個の組合せの中から、少なくとも一つの組を取り上げる第4のステップと
選定された一つの組の、ｎ元ｎ次の連立方程式
gpi(ｘ)=<npi,x>=ppi≧0,(pi=p1,p2,・・・・・・,pn)
を解き、解頂点候補を求めるにあったて、対応する方向余弦ベクトルの組
npi,(pi=p1,p2,・・・・・・,pn)
が、前記空間Enの中でその原点を起点として形成するn次元ピラミッド錘をなし、該ピラミッド錘が凸錐であり、且つ、該ピラミッド錘内部に、該原点を起点として置かれた前記方向余弦ベクトルnｆが含まれることを確認する第5のステップと
を更に備えたことを特徴とする請求項2に記載の設計支援方法。
【請求項５】
前記m1個の超平面Πk,(k=1,・・・,m1)の中からｎ個の超平面の組を一つ取りあげ、該組の超平面Πi,(i=1,・・・,n)が形成するピラミッド錘の頂点座標を計算するにあたって、
超平面Π1,Π2の交叉から始めて、段階的に超平面を追加して都度の交叉、即ち、Π1∩Π2∩・・・∩Πj,(j=2からn-1まで)の交叉空間段階ごとにおける、原点Ｏからの最短距離点Ｓjを求め、最終的にΠ1∩Π2∩・・・∩Πnの交叉空間における、原点Ｏからの最短距離点Ｓnを求める第6のステップを更に備えたことを特徴とする請求項1に記載の設計支援方法。
【請求項６】
前記m1個の超平面Πk,(k=1,・・・,m1)の中からｎ個の超平面の組を一つ取り上げ、該組の超平面Π10,Π20,・・・,Πn0が形成するピラミッド錘の頂点ＳP0を求め、頂点ＳP0の前記nｆ軸への正射影標高をＨP0とし、この頂点ＳP0を出発点として、段階ごとに、異なるピラミッド錘頂点へ移動する、頂点間移動追跡を行うに当たって、
第j回目移動後の頂点をＳPj,該頂点ＳPjの該標高をＨPjとし、また、第j回目移動時のｎ個の超平面の組をΠ1j,Π2j,・・・,Πnjとし、ここに該組をΠ1j,Π2j,・・・,Πnjは、当該段までに用いられていない、超平面の一つをもって、該組をΠ1j,Π2j,・・・,Πnjの一つと置き換えて、次段の超平面の組Π1,j+1,Π2,j+1,・・・,Πn,j+1が構成され、その頂点をＳP,j+1,該頂点ＳP,j+1の該標高をＨP,j+1とし、
ここで、次の(j+1)段の組の構成は標高の正なる増大代(ＨP,j+1-ＨPj)が最小なるように、超平面の組Π1,j+1,Π2,j+1,・・・,Πn,j+1が選定され、前段の増大代を下回る組が枯渇したとき頂点間移動追跡を終了して、線型計画問題の解を探査する、第7のステップを更に備えたことを特徴とする請求項1に記載の設計支援方法。
【請求項７】
前記m1個の超平面Πk,(k=1,・・・,m1)の中からｎ個の超平面の組を一つ取り上げ、そのｎ個の組Πi(ｘ)={ｘ｜<ni,x>=pi},(i=1,・・・,n)が形成する、解頂点候補点が計算されたとき、該ｎ個の組の超平面Πi,(i=1,・・・,n)が形成するピラミッド錘が凸錐であることと、ピラミッド錘に、該解頂点候補点を通過して(−nf)軸方向直線が内包されていることとを確認する、第8のステップを更に備えたことを特徴とする請求項1に記載の設計支援方法。
【請求項８】
前記m1個の超平面Πk,(k=1,・・・,m1)の中からｎ個の超平面の組を一つ取り上げ、そのｎ個の組Πi(ｘ)={ｘ｜<ni,x>=pi},(i=1,・・・,n)が形成する、解頂点候補点が計算されたとき、該ｎ個の組の超平面Πi,(i=1,・・・,n)が形成するピラミッド錘が凸錐であることと、ピラミッド錘に、該解頂点候補点を通過して(−nf)軸方向直線が内包されていることとを確認する、第9のステップを更に備えたことを特徴とする請求項7に記載の設計支援方法。
【請求項９】
該ピラミッド錘体の頂点と該ピラミッド錘体の底面との距離を、SQRT(n)以下に設定することを特徴とする請求項8に記載の設計支援方法。
【請求項１０】
物理的又は経済的資源の配分を行うための設計支援装置であって、
目的関数f(ｘ)が次元数ｎが2以上のｎ次元ユークリッド空間Enの中の実ベクトルx=[x1
x2・・・xn]t∈Enとして表され、該ベクトルxのｎ個の成分x1,x2,・・・,xnは実の未知変数であり、該目的関数f(ｘ)は未知変数ベクトルxに関して極大化乃至極小化され、その際、ｎ以上の整数個数m1個の線型不等式拘束条件gi(ｘ)≧0あるいはgi(ｘ)≦0,(i=1,・・・,m1)が課せられ、該配分方法が、当該線型計画問題を解く、物理的乃至は経済的資源の配分を行う方法を実行し、
該極大化乃至極小化問題を、ヘッセの標準形表現を用いて、
不等式拘束条件    gi(ｘ)=<ni,x>≦pi(i=1,・・・,m1)
が形成する共通領域の中で、
目的関数    f(ｘ)=<nf,x>=pf
を最大化させる問題へと書き直し、
ここに各pfは正として、集合{ｘ｜<nf,x>=pf}は該空間Enの中で(n-1)次元の超平面Πf(ｘ)={ｘ｜<nf,x>=pf}を形成し、方向余弦ベクトルnfは該空間Enの原点Ｏより該超平面Πf(ｘ)に向かって直交する方向の単位ベクトルであり、該nfの向きは該原点Ｏより該超平面Πf(ｘ)に向かう方向とし、pfは該原点Ｏと、該原点より該超平面Πf(ｘ)に下ろした垂線の足Ffとの正なる距離であり、該pfは拘束条件全てを満足する最小値となるよう探索され、一方、集合{ｘ｜<ni,x>=pi},(i=1,・・・,m1)は該空間Enの中で(n-1)次元の超平面Πi(ｘ)={ｘ｜<ni,x>=pi},(i=1,・・・,m1)を形成し、各方向余弦ベクトルniは該原点より該超平面Πi(ｘ)に向かって直交する方向の単位ベクトルであり、該niの向きは該原点Ｏより該超平面Πf(ｘ)に向かう方向とし、piは該原点Ｏと、該原点Ｏより該超平面Πi(ｘ)に下ろした垂線の足Fiとの正なる距離であって、上記規約の下に、当該線型計画問題を該ヘッセの標準形表現に書き改める、第1の演算手段と
該拘束条件gi(ｘ)=<ni,x>≦pi,(i=1,・・・,m1)の各々に呼応して、各niとnｆとの内積<ni,nf>,(i=1,・・・,m1)の各々の正負を判定し、負となる拘束条件を除外して、拘束条件の数を減ずる第2の演算手段と
を備えたことを特徴とする設計支援装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、拘束条件が過剰下における最適資源割当を行う設計支援方法及び設計支援装置の技術分野に関するものであり、より具体的には、線型計画法問題解法乃至整数計画法問題解法に関連する。
【背景技術】
【０００２】
はじめに、本明細書ではベクトル量とスカラ量とを用いて、本発明の内容について詳細に説明するが、オンライン出願時に太字表記を使用出来ない為に、ベクトル量とスカラ量との区別を正確に表現することが困難な箇所が多数存在する。そのため、太字表記を用いてベクトル量とスカラ量との区別を明瞭にして本願の一層の理解に役立つように記載したものを、本願と同日付けの上申書で提出したので参照されたい。
工業技術上のあらゆる問題は、課題となるシステムについて、時間、労働資源を含めての資源を如何に効率的に割当てるか、つまりシステムのパラメータ変数を如何に決定・制御するかといっても言い過ぎではない。
本願の出願人による特許文献1(特許第3861012)及び特許文献2(特許第4599301［特開2007-188454］)は、拘束条件不足下での目的関数の極大・極小化解法乃至はシステムの最適化解法を開示している。該両文献によれば、目的関数自体あるいは対象システムの支配式自体とは独立して、複数拘束条件により形成される、システムの多変数パラメータに関しての許容定義領域を決定することが可能となり、高次元の該許容定義領域を階層的に追うことで目的関数あるいはシステム支配式の近似式のノルムが評価できてしまい、解を求めることが可能となる。これら両文献の手法に従えば、ラグランジュの未定乗数法、変分原理を用いる解法、残差法に帰着させる解法、固有値問題に関連付ける解法等を利用することなく最適問題に対処可能ともなる。目的関数自体あるいは対象システムの支配式自体より、拘束条件を主役に据えて求解にあたることが可能となり、目的関数あるいはシステム支配式の近似式のノルム(で表される多変数パラメータに関しての関数)は高度に非線形であってもよく、また多峰多谷性があってもよいので今後の応用性は広い。
しかしながら、これら最適問題は、拘束条件過剰の問題は対象外である。ここで、拘束条件が過剰とは、課題の対象システムあるいは目的関数に現れるパラメータ数と同数或いはそれを上回る数の線型不等式拘束条件の下で、システムの最適化あるいは目的関数の極大・極小化を図る場合を意味する。
尚、特許文献1(特許第3861012)の内容は、非特許文献１に解説されている。非特許文献１は特許文献2を理解するのに参考となる。
【０００３】
拘束条件過多の場合の端的な問題は線型計画法問題である。これについては特許文献3(WO86/06569或いはJP1986-502580乃至US4744028としてもよい)がある。特許文献3は線型計画法問題の中でも内点法（Narendra K. Karmarkar法・カーマーカー法）とも呼ばれる発明を開示している。
従来、線型計画法問題の解法と言えば、単体法(シンプレックス法)であり、これはダンツィク（George Dantig）によって1947年に創始されたとされる。単体法(シンプレックス法)及び内点法（カーマーカー法）については次段落以降で簡単な説明を行う。
線型計画法や整数計画法を含めた最適化問題の解説書は数多のものが出版されており、ここでは列挙することは避けるが、線型・非線形を含む最適化技法の集大成した代表的文献として非特許文献2を挙げておく。非特許文献2によれば、最適化問題の分野の全体が鳥瞰できる。特に、線型計画法が活用される諸問題の広がり(図20参照)について認識することができる。
【０００４】
単体法(シンプレックス法)であれ内点法（カーマーカー法）であれ、線型計画法においては、標準形（プライマリーモデル）の形、即ち、主問題(プライマリー)標準形
目的:    ctx→最大化              (導入式1)
条件:    Ax≦b,                  (導入式2)
なる最適化問題として捉えてもよく,また対応する整数計画法はその未知変数のベクトル成分が全て整数である問題と見てもよい。ここで、cは所与のｎ次元の係数ベクトル(実数ベクトル)、xはｎ次元の未知数パラメータのベクトル(実数ベクトル),bは所与のｍ次元の係数ベクトル(実数ベクトル)、Aはｎ×ｍ実係数行列(所与)である。ここで、更に、未知数パラメータのベクトルxの各成分は非負であると仮定してもよく、導入式2の不等号を等式に置き換えるべく、導入式2の各行毎にスラック変数(λ1,λ2,λ3,・・・,λm)を構えて、
目的:    ctx→最大化                  (導入式3)
条件:    Ax=b,x≧0              (導入式4)
をプライマリー標準形とみなすことも多い。導入式1及び2を導入式3及び4に書き換えると、未知数パラメータの個数は(n+m)個となり、線型等式拘束条件の数mを上回り、拘束条件数不足型の問題になる。一方、導入式1及び2の観点では、m≧nであり、拘束条件数不足型の問題である。尚、この拘束条件数不足の問題に対しては、特許文献1乃至文献2は扱ってはいない。
【０００５】
導入式1及び2から始めて、導入式3及び4を導出した場合、ベクトルc,xは(n+m)次元のベクトル、Aは(n+m)×ｍ実係数行列であると考え直すことになるが、ここは、導入式3及び4の問題設定にあっても、あらためて、cは所与のｎ次元の係数ベクトル(実数ベクトル)、xはｎ次元の未知数パラメータのベクトル(実数ベクトル),bは所与のｍ次元の係数ベクトル(実数ベクトル)、Aはｎ×ｍ実係数行列(所与)であることとする。
導入式1及び2による課題設定も、導入式3及び4による課題設定も等価な問題を取り扱っている。また、いずれの課題設定に対しても、それぞれに等価な双対問題表現が存在する。
【０００６】
また、単体法(シンプレックス法)であれ内点法（カーマーカー法）であれ、従来からの線型計画解法では、未知数パラメータのベクトルxの次元数nとして該次元数nを、拘束条件数mと比較すると、ｎ≦ｍなる条件が存在すると考えてよい。線型計画法では、過剰なｍ個の拘束条件の中から、未知数パラメータのn個分の拘束条件を選んで、n個の未知数パラメータについてのn個の線型連立方程式をといて、目的関数を最大化させるベクトルx(解頂点とも呼ぶ)を求めることになる。つまり、線型計画解法においては、解頂点の候補を決める拘束条件の組合せはmCn個あり、その中の一つの組がxを決定する。
上述のように、従来からの線型計画解法では、拘束条件不等式を等式に置き換えるために、一般に、スラック変数を導入する。このため、拘束条件数ｍに変化はなくても、未知数パラメータのベクトルxの次元数(スラック変数を導入するまえの当初の)nは(n+m)に増大する。次元数の増大は、前記組合せ数mCn個をm+nCn個に増やすこととなり、問題を複雑化させる。また、ベクトルxについて連立方程式を解く際に、たとえば掃出し法を実行した場合、ベクトルxの次元数の指数乗に比例して、コンピュータ計算時間が増大すると考えてよい。現代の線型計画法問題や整数計画法問題ではスーパーコンピュータでも処理が困難な(処理時間がパラメータ数の指数乗で収まらないような)問題も視野に入れるので、スラック変数の導入を回避して未知ベクトルの次元数を低減することが決定的な課題ともなりえる。図20における線型計画法問題の分野に記載は省略されたが、極限設計を含む構造解析等の応用分野(大規模計算分野)もあり、スラック変数の導入を回避して求解効率を著しく向上させることが期待される。
【０００７】
また、線型計画法は最適制御の分野にも応用される。例えば、刻々の状態量ベクトルの制御値を決定するために、式(1),(2)の線型計画法問題の解法が、果てしなく、(リアルタイムで)繰返されるようなときも、未知ベクトルの次元数を低減することは決定的な課題となる。実際、多変数の制御パラメータを、複数の不等式拘束条件を考慮しながら、オンラインで、原動機の運転を制御することが行なわれている。刻々のソルバー(線型計画問題の処理を行う方法・装置)の計算効率を向上させて、制御の特性(応答性・安定性等)を向上させることが重要となる。
【０００８】
また、単体法であれ内点法であれ、従来からの線型計画解法では、未知実数ベクトルxを決めるのは、mCn個の組合せの内、ある一つの組(あるｎ個の一組)が分ればよく、その他の組合せは、元来は不要である。従来の線型計画法では、m+nCn個の組合せの対象に対して、m+nC１回以内の繰返し追跡で収まるよう、“高次元空間の多面体の稜辺”を追うものとみなされている。
図18は単体法の解探索経路について図解した説明図である。導入式3及び4において、n=2,m=5の場合の例となっている。つまり、未知数パラメータのベクトルx及び係数ベクトルcの次元数は2である。ベクトルxについてみれば、xt=[x1  x2]であり、ベクトルxは2次元空間(平面)内の点として捉えることができる。5個の拘束条件（等式）は、該2次元面の第1象限の斜線部領域を囲む、5個の直線(線分)によって示されている。ここで5個の線分には矢印が付けられ、解頂点が探索される様子が描画されている。
図18の単体法においては、第1象限の斜線部領域即ち凸多角形領域(の角点=頂点)に接してctxが最大となる角点座標で、目的関数が最大となる。この角点に到達するように、凸多角形領域の稜辺上の点若しくは頂点の適当な点から始めて、頂点から頂点へと稜辺を辿って、解を与える頂点に到達する。なお、図18の場合、一つの頂点Ａから次の頂点Ｂへと稜辺Ｅを辿るに際しては、点Ａから点Ｂに向かう勾配が最も小さい(後述の図4参照)稜辺Ｅを選ぶようにしている。つまり、一つの頂点Ａから次の頂点Ｂへと稜辺Ｅを辿るに際して、目的関数を極力増大させないように、次々に頂点間を移動する。
【先行技術文献】
【特許文献】
【０００９】
【特許文献１】特許第３８６１０１２号公報
【特許文献２】特許第４５９９３０１号公報
【特許文献３】米国特許４７４４０２８号公報
【非特許文献】
【００１０】
【非特許文献１】“Vibration Reduction of ReciprocatingEngines,”K.Ito et al.,Journal of The JapanInstitution of Marine Engineering,2006,Vol.41 Special Issue
【非特許文献２】GeorgeL. Nemhauser他、「Optimization（Handbooksin Operations Research and Management Science）」North-Holland（1989/8/1）
【発明の概要】
【発明が解決しようとする課題】
【００１１】
単体法においては、上記のような頂点間移動の計算は単体表(説明省略)を用いて実施される。次々の頂点の座標を都度計算するに際しては、掃出し計算（枢軸演算）が繰返し実施される。単体表計算により、m+nCn個の組合せ数に登る頂点座標を全て計算する手間は、高々m+nC１個の組合せ数の頂点座標を計算する手間へと圧縮されるとも考えてよい。しかしながら、最適解を与える数パラメータのベクトルxは最終的に一点であり、未だ無駄が多い。また、不適切な解頂点から、計算が開始されると、最適解の解頂点に辿り着かない虞もある。不要な拘束条件を予め除去して、拘束条件数を低減することが課題となる。
尚、図18の例にあたっては、拘束条件は5個の不等式とした。これら不等式を等式で与えて、導入式1及び2の問題とみなし導入式3及び4の問題に転換する(スラック変数を導入する)場合を考えると、7次元ベクトルを扱うこととなり、問題は複雑化し図18で与えられたような図解は不可能となる(スラック変数を導入することが便利な工夫のようにも思えても、却って解法の効率を悪化させることにもなっている)。また、図18を見て分かることがある。ベクトルxに関する非負条件は必要かどうかという点である。少なくも図18の例においては、ベクトルxの決定に関して、横軸(x1軸)も縦軸(x2軸)も関与していない。横軸(x1軸)も縦軸(x1軸)は、スラック変数導入に伴って現れた便宜的な拘束条件であって本質的な所与の拘束条件ではない。実際、上記m=5のカウントに横軸(x1軸)も縦軸(x2軸)は組み込まれていない。なお、非負制約や上下限制約については、本発明の観点からは、必ずしも重要とならないが、従来技術ではパラメータ変数を増加してしまう。
【００１２】
また、ベクトルxに関する非負条件はベクトルxが2次元の場合は、図18のように、第1象限として認識可能であるが、3次元ベクトルの場合は、少々捉え難くなる。実際、3次元空間の第1の1/8部分領域などと呼んだりすることもない。4次元以上の高次元ベクトルの場合は非負条件の空間領域を認識することはより困難であり、非負条件の導入は問題を複雑化させてしまっている。後述のように、非負条件領域を意識した拘束領域を想定するより、高次元空間の場合、半空間(後述、2次元の場合は半平面)を想定するほうが、有用であり且つ本質的であるが、従来技術ではそうしていない。
【００１３】
図19は内点法の解探索経路について図解した説明図である。導入式3及び4において、n=2,m=5の場合の例となっている。図19の目的関数及び拘束条件式(あるいは不等式拘束条件式)は、図18のものと同一である。図18の単体法においては、凸多角形領域の稜辺上の点若しくは頂点の適当な点から始めて、頂点から頂点へと稜辺を辿って、解を与える頂点に到達するのに対し、図19の内点法（カーマーカー法）では、凸多角形（高次元空間の場合は、凸多面体）領域内で縮小して行く楕円（高次元空間の場合は、高次元楕円体）の系列を創成して、その極限が、求める頂点に到達するようにしている。このように、内点法では頂点間経路を直接的に追うものではないが、楕円列の中心の点列を次々創成するに際して、目的関数を極力増大させないように、稜線を参照している。この意味においては、単体法と同様に稜辺を辿っている。
また、内点法（カーマーカー法）では、単体表やそれに伴う掃出し計算（枢軸演算）を実施しないことになるが、楕円（楕円体）系列を次々創成する毎に逆行列計算を構えていて、判定条件より小さい楕円（楕円体）がある頂点の極近傍で収斂するまで反復を繰返す手間は要求される。内点法（カーマーカー法）も、問題の設定は導入式1及び2或いは導入式3及び4であり、単体法(シンプレックス法)と同じ難点を有する。
【００１４】
更にまた、単体法であれ内点法であれ、従来の線型計画解法では、対応する整数計画問題との間に隔たりがみられる。前記のように、導入式1及び2或いは導入式3及び4で、未知数パラメータのベクトルxの各成分が全て整数であるという条件を課せば、線型計画問題は整数計画問題となる。従来の線型計画解法流れからでは、これら両問題を統一的に取り扱うことが可能とは限らない。整数制約を追加した場合、線型計画問題の解頂点xの近傍に位置する整数格子点が、当該整数計画問題の最適点とは限らないからである。
整数計画問題は組合せ問題(ＮＰ問題)に発展することもあり、一段と困難な問題ともみなされ、整数計画法と整数計画問題との間に一線が画されてきた。所謂、分枝限定法(branch and bound method)や切除平面法(cutting plane method)に代表される工夫の流れに、整数計画法の独自性をみることができる。しかしながら、整数計画法と線型計画法をより統一的に取扱う技法が望まれる。
【００１５】
本発明は上記課題に鑑みなされたものであり、
（ａ）スラック変数の導入を回避して未知ベクトルの次元数を低減すること、即ち問題のパラメータ変数の数を減らし、簡単な許容領域で問題を扱うこと、
（ｂ）不要な拘束条件を予め除去して、拘束条件数を低減すること
（ｃ）拘束条件が形成する凸多角形領域を、高次元空間内の非負領域で考えるのではなく、高次元空間内の半空間領域で考えること。
（ｄ）凸多角形領域の稜辺(高次元の場合は高次元凸多角形領域の“稜面”)を辿るという、分かり難さを克服して、計算の効率・質の向上に貢献すること
（ｅ）整数計画法と線型計画法をより統一的に取扱い、この従来課題を克服して、整数計画法問題を当該線型計画法問題に連動させて解くこと
を可能とする、拘束条件が過剰下における最適資源割当を行う設計支援方法及び設計支援装置を提供することを目的とする。
【課題を解決するための手段】
【００１６】
始めに、本願は例えばコンピュータを利用し、物理的乃至は経済的資源の配分を行う設計支援方法及び設計支援装置であるが、説明の冗長を避けるため、本明細書では、方法を核として、本発明を開示する。本願の本発明に係わる方法の各種手順(ステップ乃至プロセス)は、装置における手順実行手段(サブルーチン乃至ソフトウェア手段)であり、コンピュータに予め組み込んでもよいし、コンピュータ判読可能媒体あるいはネットワーク或いは通信手段を経由してコンピュータを作動させるようにしてもよい。また、コンピュータシステムは当然、出入力装置、すくなくも一つのCPUを含む演算装置、内外部記憶装置、ネットワークとのインターフェースを含む外部インターフェースを含んでいるものと考えてよい。該コンピュータシステム(設計支援装置)は、ポータブルなものであってもモバイルなものであってもよい。
【００１７】
本発明に係る設計支援方法は上記課題を解決するために、
物理的又は経済的資源の配分を行うための設計支援方法であって、
目的関数f(ｘ)が次元数ｎが2以上のｎ次元ユークリッド空間Enの中の実ベクトルx=[x1
x2 ・・・ xn]t∈Enとして表され、該ベクトルxのｎ個の成分x1,x2,・・・,xnは実の未知変数であり、該目的関数f(ｘ)は未知変数ベクトルxに関して極大化乃至極小化され、その際、ｎ以上の整数個数m1個の線型不等式拘束条件gi(ｘ)≧0あるいはgi(ｘ)≦0,(i=1,・・・,m1)が課せられ、該配分方法が、当該線型計画問題を解く、物理的乃至は経済的資源の配分を行う設計支援方法において、該方法が、
該極大化乃至極小化問題を、ヘッセの標準形表現を用いて、
不等式拘束条件    gi(ｘ)=<ni,x>≦pi  (i=1,・・・,m1)
が形成する共通領域の中で、
目的関数    f(ｘ)=<nf,x>=pf
を最大化させる問題へと書き直し、
ここに各pfは正として、集合{ｘ｜<nf,x>=pf}は該空間Enの中で(n-1)次元の超平面Πf(ｘ)={ｘ｜<nf,x>=pf}を形成し、方向余弦ベクトルnfは該空間Enの原点Ｏより該超平面Πf(ｘ)に向かって直交する方向の単位ベクトルであり、該nfの向きは該原点Ｏより該超平面Πf(ｘ)に向かう方向とし、pfは該原点Ｏと、該原点より該超平面Πf(ｘ)に下ろした垂線の足Ffとの正なる距離であり、該pfは拘束条件全てを満足する最小値となるよう探索され、一方、集合{ｘ｜<ni,x>=pi},(i=1,・・・,m1)は該空間Enの中で(n-1)次元の超平面Πi(ｘ)={ｘ｜<ni,x>=pi},(i=1,・・・,m1)を形成し、各方向余弦ベクトルniは該原点より該超平面Πi(ｘ)に向かって直交する方向の単位ベクトルであり、該niの向きは該原点Ｏより該超平面Πf(ｘ)に向かう方向とし、piは該原点Ｏと、該原点Ｏより該超平面Πi(ｘ)に下ろした垂線の足Fiとの正なる距離であって、上記規約の下に、当該線型計画問題を該ヘッセの標準形表現に書き改める、第1のステップと、
該拘束条件gi(ｘ)=<ni,x>≦pi,(i=1,・・・,m1)の各々に呼応して、各niとnｆとの内積<ni,nf>,(i=1,・・・,m1)の各々の正負を判定し、負となる拘束条件を除外して、拘束条件の数を減ずる第2のステップと
を備えたことを特徴とする。
【００１８】
上記のように、本発明による、コンピュータを利用し、物理的乃至は経済的資源の配分を行う設計支援方法によれば、不等式拘束条件をそのまま取り扱うことが可能となり、しかも各不等式拘束条件毎にスラック変数を導入して等式制約に置き換える必要がなくなる。従って、未知変数ベクトルxの次元数を増大することなく、線型計画問題を取り扱うことが可能となり、求解計算速度・効率を改善し、求解効率の向上が可能となる。
また、内積<ni,nf>,(i=1,・・・, m1)の各々の正負を判定し、正となる拘束条件を識別して,その該当条件数を絞り込むので(第2のステップ)、複数不等式拘束条件により構成される共通集合である、高次元ユークリッド空間Enの多面体内部凸領域を、pf=0としたときの超平面Πf(ｘ)={ｘ｜<nf,x>=pf,pf=0}が画定する該空間Enの半空間に限定できる。従って、もう一方の半空間側にて形成される該多面体内部凸領域を無視することが可能となる。つまり、そのもう一方の半空間側にて形成される該多面体内部凸領域を構成する不等式拘束条件は無視(除去)することが可能となる。従って、未知変数ベクトルxの次元数を増大することなく、線型計画問題を取り扱うことが可能となり、求解計算速度・効率を改善し、求解効率の向上が可能となる。
さらに、拘束条件数をm1個から、それより少ない、ある個数mへと減じて、ｎ個の拘束条件を選ぶ組合せ数をm1Cn個からmCn個へと減らすので、求解計算速度・効率を改善し、求解効率の著しい向上が可能となる。尚、スラック変数の導入する場合を想定すると、組合せ数はm1+nCn個からmCn個へと減ることになる(第1のステップ及び第2のステップ)。
しかも、上記のように低減された組合せ数mCn個について、その中から、一つ乃至幾つかのの拘束条件の組を取り上げ、それぞれの組でのｎ個の拘束条件からなる、連立方程式gi(ｘ)=<ni,x>=pi,(i=1,・・・,n)を解き、目的関数f(ｘ)を最大化させる解を与え得る、候補点xc=[x10x20・・・xno]tを求めることが可能となるので、求解計算速度・効率を高めながら、候補点xcと該候補点xcにおける目的関数f(xc)の評価が可能となる。
【００１９】
また、上記の本発明において、好ましくは、
該方法が、さらに、
(S3)残された拘束条件の中から、二つの互いに異なる拘束条件の任意の組｛gk(ｘ)=<nk,x>≦pk及びgl(ｘ)=<nl,x>≦pl｝を取り上げ、それぞれの組において、(1- 内積<nk,nl>)の値を算出し、該算出値が、予め定められた値より小さいか、pkとplの相対比が予め設定された範囲を逸脱する場合は、pkとplの大きい方に対応する拘束条件を取り除いて、さらに拘束条件の数を減ずる第3のステップS3を
更に備えたことを特徴とする。
【００２０】
上記の方法によれば、ｎ次元のユークリッド空間Enの中にて、厚みのない二つの超平面で、平行乃至平行に近いもの同士を取り上げて、Enの原点からの垂線距離が遠いものを、必須ならざる拘束条件として除去することが可能となる。こうして、拘束条件の全体の数を減らすと同時に、連立方程式の組数をへらすことが可能となる。従って、求解計算速度・効率を改善し、求解効率の向上が可能となる。
【００２１】
また、上記の本発明において、好ましくは、
該方法が、さらに、
(S4)残された拘束条件を改めて、等式条件と見なして
gi(ｘ)=<ni,x>=pi≧0,(i=1,・・・,m)
とし、m≧ｎなることを確認し、
残されたm個の拘束条件からｎ個の拘束条件を選ぶにあたり、垂線距離p1,p2,p3,・・・,pmの大小バランスがとれているときは、<ni,nf>が1に近い拘束条件を取り上げ、垂線距離p1,p2,p3,・・・,pmに大小バランスがとれてないときは、垂線距離の小さい方の拘束条件を含めて<ni,nf>が1に近い拘束条件を取り上げる、予め定められた選定基準により、mCn個の組合せの中から、少なくとも一つの組を取り上げる第4のステップS4と
(S5)選定された一つの組の、ｎ元ｎ次の連立方程式
gpi(ｘ)=<npi,x>=ppi≧0,(pi=p1,p2,・・・・・・,pn)
を解き、解頂点候補を求めるにあたって、対応する方向余弦ベクトルの組
npi,(pi=p1,p2,・・・・・・,pn)
が、前記空間Enの中でその原点を起点として形成するn次元ピラミッド錘をなし、該ピラミッド錘が凸錐であり、且つ、該ピラミッド錘内部に、該原点を起点として置かれた前記方向余弦ベクトルnｆが含まれることを確認する第5のステップS5とを
更に備えたことを特徴とする。
なお上記第4のステップと第5のステップは第3のステップに続けても、第3のステップをスキップして、第1のステップと第2のステップに続けてもよい。垂線距離間の大小バランスは、後記で説明される。また、ｎ元ｎ次の連立方程式
gpi(ｘ)=<npi,x>=ppi≧0,(pi=p1,p2,・・・・・・,pn)
を解くにあたっては、従来の連立方程式解法によってもよく、後記の手法部分空間の最短距離点到達手法や上記部分空間の最短距離点標高評価手法によってもよいことは当然である。
【００２２】
また、上記の方法によれば、ｎ個以上の多数の拘束条件からｎ個の拘束条件を選ぶにあたり、垂線距離p1,p2,p3,・・・,pmの大小バランスがとれているときは、<ni,nf>が1にちかい拘束条件を取り上げ、垂線距離p1,p2,p3,・・・,pmに大小バランスがとれてないときは、垂線距離の小さい方の拘束条件を含めて<ni,nf>が1にちかい拘束条件を取り上げる、予め定められた選定基準により、拘束条件の組を選びだすので、対象とすべき、ピラミッド錘の数を減らすことが可能となる。従って、求解計算速度・効率を改善し、求解効率の向上が可能となる(第5のステップ)。
また、上記の方法によれば、ｎ個の方向余弦ベクトルが形成するピラミッド錘の頂点が、解頂点候補を形成するか否かを、該ピラミッド錘が凸錐であるか否か、並びに、原点Ｏを通過するnf軸方向の直線を該ピラミッド錘が内包するか否かによって、判定して、対象とすべき、ピラミッド錘の数を減らすことが可能となる。従って、求解計算速度・効率を改善し、求解効率の向上が可能となる(第5のステップ)。
【００２３】
また、上記の本発明において、好ましくは、
(請求項1に記載の方法において)該方法が第1のステップと第2のステップの他に、さらに、
(S6)前記m1個の超平面Πk,(k=1,・・・,m1)の中からｎ個の超平面の組を一つ取り上げ、該組の超平面Πi,(i=1,・・・,n)が形成するピラミッド錘の頂点座標を計算するにあたって、
超平面Π1,Π2の交叉から始めて、段階的に超平面を追加して都度の交叉、即ち、Π1∩Π2∩・・・∩Πj,(j=2からn-1まで)の交叉空間段階ごとにおける、原点Ｏからの最短距離点Ｓjを求め、最終的にΠ1∩Π2∩・・・∩Πnの交叉空間における、原点Ｏからの最短距離点Ｓnを求める第6のステップS6を
備えたことを特徴とする。
【００２４】
上記の方法によれば、超平面Π1,Π2の交叉から始めて、段階的に超平面を追加して都度の交叉、即ち、Π1∩Π2∩・・・∩Πj,(j=2からn-1まで)の交叉空間段階ごとにおける、原点Ｏからの最短距離点Ｓjを求め、最終的にΠ1∩Π2∩・・・∩Πnの交叉空間における、原点Ｏからの最短距離点Ｓnを求める。つまり、ｎ次元のユークリッド空間Enの中にて、該ｎ元ｎ次の連立方程式の解xを原点Ｏからの最短距離点Ｓj，(j=2からn-1まで及びj=n)の点列探査として求める。その際、シュミットの直交化法の流儀を用いる。そこで、現れる除算はシュミットの直交化法の流儀において、追加される、直交独立ベクトルが正規化できないときであり、gi(ｘ)=<ni,x>=pi,(i=1,・・・,j)の組において、{ni｜i=1,・・・,j-1}が最早線型独立系でないことを意味する。このようなとき、旧来の掃出し法やベクトル収束計算法による線型連立方程式解法では、オーバーフローや不定・巡回の問題に対する対策が厄介であるが、上記の方法によれば、簡単に対策を講ずることが可能となる。従って、当該線型計画問題の解に到達する上で、求解計算速度・効率が高められる。しかも、質の高い計算方法を提供することが可能である。
【００２５】
また、上記の本発明において、好ましくは、
該方法が第1のステップと第2のステップの他に、さらに、
(S7)前記m1個の超平面Πk,(k=1,・・・,m1)の中からｎ個の超平面の組を一つ取り上げ、該組の超平面Π10,Π20,・・・,Πn0が形成するピラミッド錘の頂点ＳP0を求め、頂点ＳP0の前記nｆ軸への正射影標高をＨP0とし、この頂点ＳP0を出発点として、段階ごとに、異なるピラミッド錘頂点へ移動する、頂点間移動追跡を行うに当たって、
第j回目移動後の頂点をＳPj,該頂点ＳPjの該標高をＨPjとし、また、第j回目移動時のｎ個の超平面の組をΠ1j,Π2j,・・・,Πnjとし、ここに該組をΠ1j,Π2j,・・・,Πnjは、当該段までに用いられていない、超平面の一つをもって、該組をΠ1j,Π2j,・・・,Πnjの一つと置き換えて、次段の超平面の組Π1,j+1,Π2,j+1,・・・,Πn,j+1が構成され、その頂点をＳP,j+1,該頂点ＳP,j+1の該標高をＨP,j+1とし、
ここで、次の(j+1)段の組の構成は標高の正なる増大代(ＨP,j+1-ＨPj)が最小なるように、超平面の組Π1,j+1,Π2,j+1,・・・,Πn,j+1が選定され、前段の増大代を下回る組が枯渇したとき頂点間移動追跡を終了して、線型計画問題の解を探査する、第7のステップS7を
備えたことを特徴とする。
【００２６】
上記の方法によれば、一つのピラミッド錘の頂点から、別のピラミッド錘頂点への移動を追跡することができ、その際、移動前ピラミッド錘を形成するｎ個の超平面の中の(ｎ-1)個の超平面と、移動後のピラミッド錘を形成するｎ個の超平面の中の(ｎ-1)個の超平面とが共通である。この共通する(ｎ-1)個の超平面が交叉する部分空間における、原点Ｏからの最短距離点を介して、ピラミッド錘頂点間の移動を行うことが可能となる。さらに、頂点間の移動に際して、頂点の該標高も評価され、前段から当該段への標高増大代が、前前段から前段への標高増大代を上回らない。しかも、手発点の超平面の組は、ステップ1及び2により、限定された、ピラミッド錘の頂点から、出発することが可能である。従って、有限回の昇段移動にて、最高標高点、すなわち、解頂点に到達する確度が高い。つまり、当該線型計画問題の解に到達する上で、求解計算速度・効率が高められる。しかも、質の高い計算方法を提供することが可能となる。
【００２７】
また、上記の本発明において、好ましくは、
該方法が、第1のステップと第2のステップの他に、さらに、
(S8)前記m1個の超平面Πk,(k=1,・・・,m1)の中からｎ個の超平面の組を一つ取り上げ、そのｎ個の組Πi(ｘ)={ｘ｜<ni,x>=pi},(i=1,・・・,n)が形成する、解頂点候補点が計算されたとき、該ｎ個の組の超平面Πi,(i=1,・・・,n)が形成するピラミッド錘が凸錐であることと、ピラミッド錘に、該解頂点候補点を通過して(−nf)軸方向直線が内包されていることとを確認する、第8のステップS8を
備えたことを特徴とする。
【００２８】
上記の方法によれば、解頂点候補としてのピラミッド錘が凸錐であることと、ピラミッド錘に、該解頂点候補点を通過して(−nf)軸方向直線が内包されていることとを確認されるので、該ピラミッド錘の頂点が、解頂点候補であることを、確実に確認できる。線型計画問題の最終解に到達する上で、求解計算速度・効率が高められる。しかも、質の高い計算方法を提供することが可能となる。
【００２９】
また、上記の本発明において、好ましくは、
該方法が、第8のステップの後、さらに、
(S9)取り上げられた、そのｎ個の組Πi(ｘ)={ｘ｜<ni,x>=pi},(i=1,・・・,n)の超平面が形成するピラミッド錘が凸錐であり、該凸ピラミッド錘に、該解頂点候補点を通過して(−nf)軸方向直線が内包されているとき、前記nf軸に直交し、前記超平面Πf(ｘ)={ｘ｜<nf,x>=pf}に平行な超平面の一つを以って、該凸ピラミッド錘をカットして該凸ピラミッド錘の底面を作り、ピラミッド錘体を形成し、該ピラミッド錘体内部に限定される高次元整数格子点それぞれの、前記nｆ軸への正射影標高を評価し、最大標高を探索する、第9のステップS9を
備えたことを特徴とする。
【００３０】
上記の方法によれば、解頂点候補点を形成する凸ピラミッドについて、ピラミッド錘頂点の近傍に底面をとり、ピラミッド錘体を設けて、該錐体内部にある高次元整数格子点の数を限定することができる。それら、高次元整数格子点それぞれの、前記nｆ軸への正射影標高を評価し、最大標高を探索することが可能となる。線型計画問題に連動して、対応する整数計画門題の解探査が容易に可能となる。従って、線型計画問題並びに、それに連動する整数計画門題の解探査に関する、求解計算速度・効率が高められる。しかも、質の高い計算方法を提供することが可能となる。
【００３１】
また、上記の本発明において、好ましくは、該ピラミッド錘体の頂点と該ピラミッド錘体の底面との距離を、SQRT(n)以下に設定することを特徴とする。
【００３２】
上記の方法によれば、整数計画門題の解探査に関する、ピラミッド錘体内部にある高次元整数格子点の数を限定することが可能となり、すくなくも1個の格子点を該ピラミッド錘体内部に含めることが可能となる。従って、線型計画問題に連動する整数計画門題の解探査に関する、求解計算速度・効率が高められる。
【発明の効果】
【００３３】
本発明は、コンピュータを利用し、線型計画問題或いはそれと連動する整数計画問題を扱い、物理的乃至は経済的資源の配分を行う方法及び装置にあって、ヘッセの標準形表現を用いて、複数の等式拘束条件が形成する高次元空間の凸多面体が囲む許容定義領域の中で目的関数を最大化させる問題へと書き直し、該領域を該空間の半空間領域で扱い、該半空間領域の形成に寄与せぬ拘束条件を除去し、また、不要な拘束条件を除去し、複数の等式拘束条件が形成する高次元空間のピラミッド錐の解頂点形成条件を明確化し、該条件適合判定演算時間を短縮し、適合解頂点絞り込み乃至は該解頂点への到達時間の高速化を図り、大規模・高速演算の応用範囲を拡大し、更には、整数計画問題解法への連動応用性を確保する効果を奏する。
【図面の簡単な説明】
【００３４】
【図１】本発明の基本概念・技法を説明する線型計画問題の第1例である。
【図２】本発明の基本概念・技法を説明する線型計画問題の第2例である。
【図３】第2の説明例に係わる図2を変数変換して表したものである。
【図４】パラメータ数が2個、拘束制約が6の場合を取り上げ、頂点数6C2=15個形成される例を用いて本発明の観点を説明する図である。
【図５】本発明の基本観点から線型計画問題を説明する図である。
【図６】本発明の基本観点から、不要な拘束条件例を説明する図である。
【図７】本発明の基本観点から、ほぼ平行な2直線(2平面)の一方を除去する技法を説明する図である。
【図８】本発明の基本観点から、ｎ個の拘束条件を選定する基準の例に関する説明を与える。
【図９】本発明の観点に基づき、凸多角形領域(凸多面体領域)の構成を説明する図である(また、その半空間で形成される領域を示す図である)。
【図１０】本発明の観点により、2次元空間において、2直線の交点を、逆格子ベクトルを用いて表現する手法を説明する図である。
【図１１】本発明の観点により、3次元のピラミッド錐(3角錐)を紙面に描画する図である。
【図１２】本発明の観点により、4次元のピラミッド錐(ピラミッド錐体)紙面に描画する図である。
【図１３】(a)は、本発明の観点により、3次元の空間において、平面Π1,Π2の交叉空間(Π1∩Π2)が別の平面Π3と交差して、共通集合(Π1∩Π2∩Π3)を形成する様子を示しており、(b)は、本発明の観点により、n次元の空間において、(n-1)次元のj個の超平面Π1、Π2、Π3、・・・、Πjの交叉空間(Π1∩Π2∩・・・∩Πj)が別の(n-1)次元の超平面Πj+1と交差して、共通集合(Π1∩Π2∩・・・∩Πj∩Πj+1)を形成する様子を示す。
【図１４】本発明の観点が応用する、多角形が凸領域を形成するか否かの判定法の例を説明する図である。
【図１５】本発明の観点により、凸高次元ピラミッド錐の頂点を通過する、nf軸方向の直線が、該ピラミッド錐内部を通過するか否かの判定条件を説明する。
【図１６】本発明の観点により、整数計画法問題に対処する技法を説明する図である。
【図１７】(a)は、従来の単体法の解探索経路を説明する模式図であり、(b)は、従来の内点法の解探索経路を説明する模式図である。
【図１８】従来の単体法の解探索経路を、2次元面内で、説明する説明図である。
【図１９】従来の内点法の解探索経路を、2次元面内で、説明する説明図である。
【図２０】従来からの最適化問題及び線型計画問題の分野を説明する図(資料)である。
【発明を実施するための形態】
【００３５】
以下、本発明を図に示した実施例を用いて詳細に説明する。但し、この実施例に記載されている構成要素の大きさ(規模)、形状、特性その相対配置あるいは並べ順などは特に特定的な記載がない限り、この発明の範囲をそれのみに限定する趣旨ではなく、単なる説明例にすぎない。
【００３６】
ここから、本願で使用する記号・数式・用語について必要と思われる説明を行いながら、本発明を図に示した実施例を用いて詳細に説明する。また、本発明を開示するのに要するコンセプトや語彙で、従来からの通常の定義では不十分と考えられる事項についても説明する。必要に応じて従来の含意を拡張し、語彙の再定義をあたえる。尚、数理工学的な原理・内容であっても、本発明独自の創意工夫が含まれていることを付記しておく。
本明細書に係わる、数理工学的用語は、大学課程の標準的なテキスト（例えば、斉藤正彦「線型代数入門」、笠原皓司「線型代数と固有値問題」）に準拠するが、より一般的用語については岩波書店・数学辞典（第4版）を参考とする。但し、ベクトルｘおよびｙの内積はブラ・ケット表示<x,y>を使用する。ベクトルｘは縦ベクトル基準とし,その転置ベクトルは、ｘtをもって横ベクトルとする.例えば、横ベクトルpt=[p1 p2 p3・・・pn-1 pn]のような表記を使用する。行列Aやベクトルｘを転置したものをそれぞれ、At、ｘtと書く。
尚、本願における高次元ベクトル空間は実ベクトル計量空間であり内積及び2乗ノルムが定義されている高次元ユークリッド(Euclid)空間と考えてよい(n次元のユークリッドをEnと表現することが多い)。
【００３７】
上記に従って、ｎ個のパラメータx1,x2,x3,・・・xn-1,xnを成分とするベクトルをｘとするとは,
x=[x1 x2 x3・・・xn-1 xn]t          (1)
を意味する。該ｘの実質的に1個の目的関数f(ｘ)が線型関数であるとは,
f(ｘ)=a1x1+a2x2+a3x3+・・・+an-1xn-1+anxn-c        (2)
の形であることを意味する。ここでベクトルaを
a=[a1 a2 a3 ・・・an-1 an]t                (3)
とすれば,上記f(ｘ)は
f(ｘ)=<a,x>-c                      (4)
と表現される。尚、上式(4)の右辺の内、f(ｘ)の最大・最小に関与するのは<a,x>の部分であるから、定数項-cの表記を省略することもある。
一方,一般に,n個より大きい個数m個の拘束条件式g1(ｘ),g2(ｘ),g3(ｘ),・・・gm-1(ｘ),gm(ｘ)が線型不等式制約を構成するとは,
g1(ｘ)=a11x1+a12x2+a13x3+・・・+a1,n-1xn-1+a1nxn≦c1        (51)
g2(ｘ)=a21x1+a22x2+a23x3+・・・+a2,n-1xn-1+a2nxn≦c2        (52)
g3(ｘ)=a31x1+a32x2+a33x3+・・・+a3,n-1xn-1+a3nxn≦c3        (53)
・
・
gi(ｘ)=ai1x1+ai2x2+ai3x3+・・・+ai,n-1xn-1+ainxn≦ci        (5i)
・
gm-1(ｘ)=am-1,1x1+am-1,2x2+am-1x3+・・・+am-1,n-1xn-1+am-1,nxn≦cm-1    (5m-1)
gm(ｘ)=am1x1+am2x2+am3x3+・・・+am,n-1xn-1+amnxn≦cm        (5m)
なることを意味する。
【００３８】
式(51)から(5m)は、内積記号を用いて式(4)と同様の形式を用いて、
g1(ｘ)=<a1,x>≦c1                (61)
g2(ｘ)=<a2,x>≦c2                (62)
g3(ｘ)=<a3,x>≦c3                (63)
・
・
gi(ｘ)=<ai,x>≦                  (6i)
・
gm-1(ｘ)=<am-1,x>≦cm-1            (6m-1)
gm(ｘ)=<am,x>≦cm                (6m)
のように書くことができる。
【００３９】
さらに、式(61)から(6m)の内積記号内のベクトルaiはそのノルム‖ai‖で除して,正規化されたベクトルniを
ni=±ai/‖ai‖                    (7)
のように取る。ここで式(7)を式(6i)に代入して
<‖ai‖ni,x>=±ci                    (8)
つまり,式(6i)は
<ni,x>=±ci/‖ai‖                    (9)
のように書くことができる。ここで上記式(7),(8)及び(9)に現れた復号は,式(9)右辺の±ci/‖ai‖(=pi≧0とする)が非負となるようにniの方向を決めるものとする。こうして,式(6i),(i=1,・・・,m)の線型拘束式の不等式部分は改めて,
<ni,x>≦pi(≧0)                  (10)
なる形で表現される。また、当該線型拘束式の等式部分を指すためには、<ni,x>=pi(≧0)なる表現を用いることができる。
【００４０】
式(10)の<ni,x>=piなる方程式の表現は式(6i)の<ai,x>=ciに対するヘッセ(Hesse)標準形と呼ばれる。一般に,このヘッセ標準形は2次元乃至3次元のユークリッド空間での解析幾何構造を扱う場合に用いられることがある。本願では、4次元以上の高次元空間の場合にも使用できるものとする。
また、式(10)の<ni,x>=piなる方程式を満足するベクトルxの集合Πi(ｘ)を
Πi(ｘ)={ｘ｜<ni,x>=pi}          (11)
と定義する。式(11)を以って集合Πi(ｘ)を定義すると、2次元空間の場合はΠi(ｘ)は直線、niは、原点Oから該直線に直交する方向の方向余弦ベクトル、piは原点Ｏから,該原点より該直線に下ろした垂線の足までの距離(垂線距離と呼ぶ)となる。3次元空間の場合はΠi(ｘ)は平面であり、niは、原点Ｏから該平面に直交する方向の方向余弦ベクトル、piは原点Ｏから,原点より該平面に下ろした垂線の足までの距離となる。方向余弦ベクトルniは方向を逆にすると、該垂線距離piの正負が反転し、piが負になることもあるので、これを避けるために、<ni,x>=piが非負となるように方向余弦ベクトルniの向きは決めることとする。尚、垂線距離piがゼロの場合は、上式(11)の集合Πi(ｘ)が原点Ｏを通過する(含む)ことを意味している。
【００４１】
4次元以上のｎ次元高次元空間の場合、集合Πi(ｘ)は(ｎ-1)次元の部分空間となる。ここで注意すべきは、この(ｎ-1)次元の部分空間はｎ次元空間の原点Oを含んでいない(一般にpi≠0)が、商空間の意味でｎ次元空間の部分空間であり、しかも、該(ｎ-1)次元の部分空間はｎ次元空間から見れば、厚みを有していない。この意味において、該(ｎ-1)次元の部分空間はｎ次元空間内の超平面とよばれる。つまり、原点より集合Πi(ｘ)に属する任意点へ向かうベクトルxと方向余弦niとの内積が常に一定値piであり,この集合Πi(ｘ)に属する任意点のベクトルxの方向余弦ni方向への正射影が常に一定値piであり、集合Πi(ｘ)と、方向余弦ni方向の原点Ｏを通過する直線とは一点で交叉している。
更に注意しておくと、該(ｎ-1)次元の部分空間はｎ次元空間から見れば、厚みを有していないが、更なる内部の部分空間、例えば、(ｎ-2)次元の部分空間から見れば、該(ｎ-1)次元の部分空間はボリュームを有している。
【００４２】
上記のように、厚みのない超平面Πi(ｘ)を式(11)
Πi(ｘ)={ｘ｜<ni,x>=pi}
で定義すると、前記ｎ次元高次元空間はこの超平面によって、二つの領域（例えば上側領域と下側領域）に二分される。二分された領域のそれぞれを、該ｎ次元高次元空間の半空間とよんでいる。これら半空間の集合をΠiＵ(ｘ)、ΠiＬ(ｘ)と書くこととすれば、集合記号表現では下記のようになる。
ΠiU(ｘ)={ｘ｜<ni,x>≧pi}
ΠiL(ｘ)={ｘ｜<ni,x>≦pi}
このように、ヘッセ標準形を利用すると、方向余弦ベクトルniと垂線距離piとの2個の特性で超平面及び半空間を表現することが可能となる。また、ｎ次元高次元空間の中で、厚みのない超平面Πi(ｘ)と平行な超平面のそれぞれに関して、原点より該超平面に下ろした垂線の足までの距離が、各超平面毎に一定であり、言わば、ni方向基準で各々(平行な超平面の各々)の標高が与えられる。さらに言うと、当該ｎ次元高次元空間の中における任意の一点から、該平行超平面に沿ってni軸方向の直線に垂線の足をおろせば、該垂線の足の位置座標(ni軸方向の直線に関する1次元パラメータ指標)が標高であると考えてもよい。
また、後述の通り、本発明において、この標高評価が線型計画問題の最大値評価に関連する。この標高を評価する基準は、平行超平面群に直交する直線でなくともよく、平行超平面群に斜交する直線であっても良い。斜交する直線上の単位長さの方向ベクトルと、平行超平面群に直交する直線上の単位長さの方向ベクトルとで交角が決まり、斜交する直線と平行超平面群に直交する直線との間に一対一の対応をつけることが可能なためである。
【００４３】
線型計画法の課題は、複数不等式拘束条件の各々が指定する半空間の共通集合としての凸集合(凸多面体で囲まれた領域)とその頂点を探索することに帰着する。ヘッセ標準形を利用して、幾何構造解析感覚を犠牲にすることなく、該凸集合とその頂点を探索可能とすることも本発明は意図している。感覚的に分かり易いことは、コンピュータソフトウェアの開発上も、ソフトウェアの使い勝手の上でも改善が期待可能ともなる。
【００４４】
ここからは、一般のn次元空間における逆格子ベクトル系(双対基底系とも言う)の再定義を与える。後述の部分空間の最短距離点到達手法や部分空間の最短距離点標高評価手法の基本コンセプトを明示する上で必要なためである。
まず、n元ｎ次の線型連立方程式をヘッセの標準形を用いて次のように与える。
<n1,x>=p1                    (151)
<n2,x>=p2                    (152)
<n3,x>=p3                    (153)
・
・
<ni,x>=pi                    (15i)
・
<nn-1,x>=pn-1                  (15ｎ-1)
<nn,x>=pn                    (15ｎ)
ここで、方向余弦ベクトルni(i=1からｎ)は単位長さの斜交軸ベクトル基底系{n1,n2,n3,・・・,ni,・・・,nn-1,nn}を形成している。この斜交軸ベクトル基底系{n1,n2,n3,・・・,ni,・・・,nn-1,nn}に対応して、単位長さの斜交軸ベクトル基底系{r1,r2,r3,・・・,ri,・・・,rn-1,rn}が存在して、各riは各niにそれぞれ対応し、
<ri,nj>=0    (i≠j)          (16)
<ri,nj>=cos(φij)    (i=j)          (17)
となるとき、斜交軸ベクトル基底系{r1,r2,r3,・・・,ri,・・・,rn-1,rn}を斜交軸ベクトル基底系{n1,n2,n3,・・・,ni,・・・,nn-1,nn}の逆格子ベクトル系と呼ぶ。また、各riは各niに対する逆格子ベクトルと呼んでいる。ここでcos(φij)はriとniとの内積でありφijはriとniとの交角である。上式から分かるように、riはi≠jなるすべてのnjに直交している。また逆に,niはi≠jなるすべてのrjに直交している。ここで,行列Nを
N=[n1n2n3・・・ni・・・nn-1nn]          (18)
また,行列Rを
R=[r1r2r3・・・ri・・・rn-1rn]          (20)
また,対角行列Dを
D=diag[cos(φ11)cos(φ22)・・・cos(φii)・・・cos(φnn)]        (21)
と定義すれば,
NtR=RtN=D          (22)
なる関係が得られるので,逆格子ベクトル基底系が知れれば,実質的に,行列Nの逆行列を求める必要はなくなる。即ち,前記式(15)の方程式系は,逆行列計算やガウスの掃出し法や基本変形あるいは反復収束計算やその他の旧来手法に依らず,解くことが可能になる。本発明は副次的に、独自の逆格子ベクトル系による算定技法も提供する。
【００４５】
ここでは、本願で工夫された、逆格子ベクトル系{r1,r2,r3,・・・,ri,・・・,rn-1,rn}の求解法を示しておく。
まず、前記斜交軸ベクトル基底系{n1,n2,…,nn-1,nn}の順序を固定しておく。
(これはｎ次元空間での右手系左手系の区別を明確化するため)
n1,n2,…,nn-1のサイクルの順にシュミットの直交化法を用いてn1,n2,…,nn-1の全てに直交する、単位ベクトルvnを計算する。なお、シュミットの直交化法を如何に応用するかについては後述するが、nnベクトルのni,(i=1,・・・,n-1)方向への正射影成分をnnベクトルから減じて正規化(単位ベクトル化)してベクトルvnが得られる。以下でも同様である。
n2,n3,…,nnのサイクルの順にシュミットの直交化法を用いてn2,n3,…,nnの全てに直交する、単位ベクトルv１を計算する。
引き続きサイクリックに、
nj＋１,nj+２,…,nn,n1,…nj-2,nj-1のサイクルの順にシュミットの直交化法を用いてnj＋１,nj+２,…,nn,n1,…nj-2,nj-1の全てに直交する、単位ベクトルvｊを計算する。
こうして得られた単位ベクトルvj,(j=1,・・・,n)の組{v1,v2,v3,・・・,vi,・・・,vn-1,vn}が逆格子ベクトル系{r1,r2,r3,・・・,ri,・・・,rn-1,rn}になっている(証明省略)。尚、後で触れるように、該逆格子ベクトル系が、連立方程式(15)の解xを頂点とするｎ次元ピラミッド錐のｎ本の稜線（該頂点を通過する実質1次元の直線）の方向となる。また、斜交軸ベクトル基底系{n1,n2,…,nn-1,nn}の各ベクトルnjについて、<nf,nj>≧0が成立するときは、<nf,rj>≦0となるように、各逆格子ベクトルrjの向きを考えるのが、本明細書での基本である(つまり、vjをrjとする際に、符号を反転させるかさせないかに注意する)。
【００４６】
上記のアルゴリズム(逆格子ベクトル系の計算)は単純であるが記載された文献は発見できないでいる。恐らく、逆格子ベクトルとシュミットの直交化法をリンクさせる必要性に迫られた技術者や科学者はいなかったものと考えられる。一方、シュミットの直交化法ｎ回繰返す点はやや冗長ではあるが、斜交軸ベクトル基底系{n1,n2,n3,・・・,ni,・・・,nn-1,nn}がたとえ線型従属の場合でも、計算途上で認識可能となる(ベクトルvｊがほぼ零ベクトルとなる)。計算機のアベント停止回避策も組込易くなる。また、内点法のように、ベクトル収束計算を行う場合は、もし方程式系が線型従属のとき収束不能となるが、そうした不具合を回避することが可能となる。
【００４７】
上記のように、逆格子ベクトル系{r1,r2,r3,・・・,ri,・・・,rn-1,rn}が得られているときは、
連立方程式(15)の解ｘは
ｘ=p1(cosφ11)-1r1+p２(cosφ22)-1r２+・・・+pn(cosφnn)-1rn          (23)
となる。ここで、(cosφ22)は内積<ri,nj>より計算される。
また、式(22)を参照して、式(23)が正しいことを確認してもよいし、式(15)と連立合同方程式とのアナロジーから導くこともできる(証明省略)。尚、ここで合同方程式とは次の式のようなものである(次の連立方程式においては、xは未知整数、b1,b2,b3,・・・bn-1,bnは所与の整数、m1,m2,m3,・・・mn-1,mnは互いに素な所与の整数[素数]である)。
ｘ≡b1  (mod m1)                        (241)
ｘ≡b2  (mod m2)                        (242)
ｘ≡b3  (mod m3)                        (243)
・
・
ｘ≡bi  (mod mi)                        (24i)
・
ｘ≡bn-1  (mod mn-1)                     (24ｎ-1)
ｘ≡bn  (mod mn)                         (24n)
上記合同方程式と連立方程式(15)は類似の代数構造を有していると考えてよく、該連立合同方程式の一般解は上記式(23)と対応可能な形に纏めることができる(詳細省略)。尚、このアナロジー(線型連立方程式系(151から15n)と上記合同方程式(241から24n)の間のアナロジー)も、既存文献で開示されたものは見出されてはいない。
(実質0次元点・実質1次元の線・実質2次元の面)
【００４８】
ここでは、実質0次元点・実質1次元の線・実質2次元の面について定義を与える。
前記の通り、n次元空間の超平面は(n-1)次元の部分空間を形成する。該超平面を余次元1(元来は位相空間論関連分野の用語)の部分空間とも呼ぶこととする。この(n-1)次元の部分空間の該超平面は(n-1)個の線型独立基底の線型結合として表現できる。3次元ユークリッド空間において、その内部の平面が,2個の線型独立基底の線型結合として表現でき、そのような平面が該3次元ユークリッド空間には無数に含まれている。3次元ユークリッド空間における、2個の線型独立基底の線型結合として表現できる(あるいは2個の実数パラメータで表現可能な)平面を実質2次元の面と呼ぶこととして、高次元の(n-1)次元超平面と峻別する。例えば、3次元ユークリッド空間では超平面の次元も、実質2次元平面の次元も共に2次元で一致するが、4次元以上のユークリッド空間では超平面の次元と、実質2次元平面の次元とは一致しない。
【００４９】
また、例えば、７次元のユークリッド空間では超平面の次元は6次元（若しくは6次元以下）であり、実質2次元平面の次元の2次元とは全く異なる。更にまた、自然科学としての幾何学では、超平面に対応して、超辺・超点なども定義される。n次元空間における、超辺とは、(n-１)次元(若しくはそれより低次元)の超平面と(n-１)次元(若しくはそれより低次元)の超平面の交叉であって、(n-2)次元(若しくはそれより低次元)の部分空間を指している。一方3次元空間における辺あるいは稜、即ち、通常の感覚での辺あるいは稜を、本願では実質１次元の辺と呼び超辺と区別する。また、自然科学としての幾何学では、n次元空間における超点とは、(n-2)次元(若しくはそれより低次元)の超辺と(n-2)次元(若しくはそれより低次元)の超辺の交叉であって、(n-3)次元(若しくはそれより低次元)の部分空間を指している。一方3次元空間における点とは、０次元空間であるから、本願では、実質０次元の点と呼び超点と区別する。
【００５０】
上記のように平面・辺(直線)・点の次元数を明確化させるために実質と言う形容詞を使うことにする。重要なことは、実質0次元点・実質1次元の線・実質2次元の面という実体(部分空間)は4次元以上のユークリッド空間でも認識できることである。一方、例えば、4次元のユークリッド空間で実質3次元の超平面を考えても、視覚認識可能ではない(実質2次元の面に射影しようにも像が得られない)。
特許文献3の選択図（図17(a)及び17(ｂ)として再掲）見ると、高次元空間の超平面、超辺（稜）、超点を形成する超多面体が模式的に描かれている。この図は、線型計画法や高次元幾何学の分野で、従来から用いられている模式の典型で、高次元多面体を3次元空間の多面体に擬えた表記である。しかしながら、こうした表記の高次元多面体は、本来は、実質0次元点・実質1次元の線・実質2次元の面という実体を勘案して描かれるべきである。
(高次元多面体頂点座標の計算)
【００５１】
n元ｎ次の線型連立方程式(15)の解xを逆格子ベクトル系{r1,r2,r3,・・・,ri,・・・,rn-1,rn}を用いて計算する方法を前記した。単に、解xを計算するのであれば、r1,r2,r3,・・・,ri,・・・,rn-1,rnの全てを計算しなくてもよいことを、ここで示す。線型連立方程式(15)の各々はそれぞれ(ｎ-1)次元の超平面Πi(ｘ)={ｘ｜<ni,x>=pi},(i=1,・・・,n)に対応している。解xはこれら超平面Πi(ｘ),(i=1,・・・,n)の共通集合であり、実質0次元の点(ｎ次元空間において)である。手順の概要は以下の通りである。
最初に、超平面Π1と超平面Π1との交叉について考える。この交叉は(ｎ-2)次元の部分空間であり、(ｎ-2)の自由度があるから、一意には(実質0次元点の点としては)定まらない。しかしながら、当該n次元空間の座標原点Ｏより該(ｎ-2)次元の部分空間へ垂線の足を下ろすことが可能であり、この垂線の足(実質0次元点の点)は該(ｎ-2)次元の部分空間(交叉)の中で、n次元空間の原点からの最短距離に位置する点となっている。
【００５２】
図10は超平面Π1と超平面Π２との交叉について、n1軸とn2軸を含む実質2次元の平面でカットした断面を示している。上記の、交叉における最短距離点はこの断面内に存在し、図10では点Ｓ2として示されている。まず、この点Ｓ2の座標の(本願に係わる)算定手順を示す。
図10において点Ｓ1は原点Ｏより超平面Π1へ下ろした垂線の足である。ベクトル(ＯＳ1)はp1n1となる。更に、点Ｓ１より超平面Π２へ垂線の足Ｆ2を下ろす。暫定的に座標原点を点Ｓ1に平行移動して、超平面Π２の方程式(式(152)が該当)を書き換えれば(ここもヘッセ標準形で)、距離(Ｓ１Ｆ2)は求まる。ここでベクトル(Ｓ1Ｆ2)はn2軸と平行である。
一方、ベクトル(Ｓ1Ｓ2)の方向はn１軸と(上記の実質2次元の断面内にて)直交する方向であり、これはシュミットの直交化法の流儀に従い、
v1=n2-<n2,n1>n1                (25)
と、ベクトルn2からn2のn1方向成分を除去してn１に直交するベクトルv1を求め、それを単位長さに正規化した
v1n=v1/‖v1‖            (26)
を算定すれば、v1nはベクトル(Ｓ1Ｓ2)方向の単位ベクトルとなる。
【００５３】
さらにここで、直角3角形Ｓ1Ｆ2Ｓ2に着目する。角Ｓ1Ｆ2Ｓ2は直角であり、距離(Ｓ１Ｆ2)は既知となっている。斜辺Ｓ1Ｓ2と辺Ｓ1Ｆ2とがなす交角は,単位ベクトルv1nと単位ベクトルn2の内積を計算することで求まる。従って、斜辺Ｓ1Ｓ2の長さも把握でき、ベクトル(Ｓ1Ｓ2)が計算できて、それをベクトル(ＯＳ1)即ちp1n1に加算すればベクトル(ＯＳ2)が求まる。こうして実質0次元点の点Ｓ2の位置がきまる。
【００５４】
次に、数学的帰納法の流儀に従い、ｎ以下のｊ個の(n-1)次元の超平面Π1,Π2,・・・,Πjの交叉空間(これも一つの超平面である)についての、原点Ｏよりの最短距離点Ｓjはすでに確定している前提に立ち、超平面Π1,Π2,・・・,Πjに超平面Πj+1を付け加えた(j+1)個の超平面の交叉空間について考える。
図13に示すように、点Ｓjから超平面Πj+1へ垂線の足Ｆj+1を下ろす。暫定的に座標原点を点Ｓjに平行移動して、超平面Πj+1の方程式を書き換えれば(ここもヘッセ標準形で)、距離(ＳjＦj+1)は求まる。ここでベクトル(ＳjＦj+1)はnj軸と平行である。
一方、ベクトル(ＳjＳj+1)の方向はn1,n2,・・・,njのすべてと直交する方向であり、これはシュミットの直交化法の流儀に従い、
vj=nj+1-<nj+1,n1>n1-<nj+1,n2>n2-・・・-<nj+1,nj>nj            (27)
と、ベクトルnj+1からnj+1のn1,n2,・・・,njのすべての方向成分を除去してn1,n2,・・・,njのすべてに直交するベクトルvjを求め、それを単位長さに正規化した
vjn=vj/‖vj‖            (28)
を算定すれば、vjnはベクトル(ＳjＳj+1)方向の単位ベクトルとなる。
【００５５】
さらにここで、直角3角形ＳjＦj+1Ｓj+1に着目する。ＳjＦj+1Ｓj+1は直角であり、距離(ＳjＦj+1)は既知となっている。斜辺ＳjＳj+1と辺ＳjＦj+1とがなす交角は,単位ベクトルvjnと単位ベクトルnj+1の内積を計算することでもとまる。従って、斜辺ＳjＳj+1の長さも把握でき、ベクトル(ＳjＳj+1)が計算できて、それをベクトル(ＯＳj)に加算すればベクトル(ＯＳj+1)が求まる。こうして実質0次元点の点Ｓj+1の位置がきまる。
【００５６】
上記のように、超平面Π1,Π2の交叉から始めて、段階的に超平面を追加して都度の交叉、即ち、Π1∩Π2∩・・・∩Πj,(j=2からn-1まで)の交叉空間における、原点Ｏからの最短距離点Ｓjが求まる。最後にΠnを追加してΠ1∩Π2∩・・・∩Πnの交叉空間における、原点Ｏからの最短距離点Ｓnを求めれば点Ｓnが連立方程式(15)の解xとなる。このように、逆格子ベクトル系{r1,r2,r3,・・・,ri,・・・,rn-1,rn}の、r1,r2,r3,・・・,ri,・・・,rn-1,rnの全てを計算しなくても解xは算定可能となる。このアルゴリズムを本願では部分空間の最短距離点到達手法と呼ぶ。
また、上記に関連して、n1,n2,・・・,nn-1のすべてと直交するベクトルvｎ及びvnnを
vn=nn-<nn,n1>n1-<nn,n2>n2-・・・-<nn,nn-1>nn-1            (29)
vnn=vn/‖vn‖                                          (30)
と算定すれば、この単位ベクトルvnnは斜交軸ベクトル基底系{n1,n2,…,nn-1,nn}に対する逆格子ベクトル系{r1,r2,r3,・・・,ri,・・・,rn-1,rn}におけるベクトルrnに対応している。但し、Π1∩Π2∩・・・∩Πj,(j=2からn-1まで)の交叉空間の最短距離点を算定する際に現れた、途上のベクトルvjnは逆格子ベクトルr1,r2,r3,・・・,ri,・・・,rn-1,rnの何れとも一致しないことには留意が必要である。
【００５７】
この段落もまだ、本願の数理記法及び数理工学的原理について記述している。しかしながら、上述の逆格子ベクトル計算法も部分空間最短距離(原点よりの距離)探索手順は、本発明者による創意工夫であって、従来技術の文献に記載は見当たらないことを付言しておく。また、上記において、n1,n2,・・・,njのすべてと直交するベクトルvj及びそれを単位長さに正規化した
vjn=vj/‖vj‖
を算定した。n1,n2,・・・,njのすべてと直交する意味において、ベクトルvj及びvjnはある種の外積(n1,n2,・・・,njに関する)とみなせることを指摘しておく。材料・結晶関連の技術者や結晶学者も4次元以上の空間で逆格子ベクトルを考察することはなく、逆格子ベクトルとシュミットの直交化法をリンクさせる必要性もなく、4次元以上の空間でのベクトル外積演算を考える必要性も、いままでのところ、なかったものと考えられる。
(高次元ピラミッド錐)
【００５８】
本発明を構成するコンセプトの一つは高次元の多面体の一つである、高次元ピラミッド錐の捉え方である。ここで高次元ピラミッド錐に関して、本願における認識手法について言及する。
前記連立方程式系(15)の解ｘはn次元空間においての角錐(ピラミッド錐あるいはn次元ピラミッド錐と呼ぶこととする)の頂点となる。また、錐とは底面を特に配慮しない場合に用い、底面を配慮した幾何構造を考える場合は、錐体という語を用いてもよいこととする。
前記連立方程式系の式(151)から(15n)のn個の方程式の中から(n-1)個の方程式を採り上げる組合せはnCn-1=nC1=n組存在する。これらn組の各々の組は実質1次元の直線を形成する。形成されるn本の実質1次元の直線は何れも該ピラミッド錐の頂点を通過する。図11及び図12)はそれぞれ3次元ピラミッド錐及び4次元ピラミッド錐(体)を示している。
【００５９】
n次元ピラミッド錐においては、n本の実質1次元の直線は頂点を通過して、該ピラミッド錐の実質1次元の稜線を形成する。図11及び図12が示すように、ピラミッド錐を2次元の紙面に描画できるのは、各稜線(辺)が実質1次元の線であることに依存している。従って、図11及び図12における稜線(辺)は所謂超辺とは異なる。また、頂点を通過するn本の実質1次元の直線の方向は、全体として、前記逆格子ベクトル系{r1,r2,r3,・・・,ri,・・・,rn-1,rn}の方向と一致する(証明省略)。図11の3次元ピラミッド錐の、頂点を通過する3本の稜線の方向は、全体として、該3次元空間の斜交軸ベクトル基底系{n1,n2,n3}に対する逆格子ベクトルr1,r2,r3の方向である。図12の4次元ピラミッド錐体の頂点を通過する4本の稜線の方向は、全体として、斜交軸ベクトル基底系{n1,n2,n3,n4}に対する逆格子ベクトルr1,r2,r3,r4の方向と一致する。尚、図12の4次元ピラミッド錐体の底面の4角形1-2-3-4が紙面に描画できるのは、ピラミッド錐をカットする底面として、実質2次元の面を想定していて、該4角形がその実質2次元の面にあるためとみなしてよい。また、該4角形1-2-3-4の角の点1,2,3及び4は実質0次元の点であり認識可能であると言ってよい。
【００６０】
特許文献3(US4744028)の図1(本願にて図17(a)として再掲)及び特許文献3(US4744028)の図3(本願にて図17(b)として再掲)に、高次元多面体の模式図が与えられている。その図1は単体法の説明に用いられ、その図3は内点法の説明に用いられている。しかしながら、特許文献3及び従来技術においては、本願上記で定義した実質0次元の点、実質1次元の線、実質2次元の面に関する言及(あるいは点・線・平面と超点・超線・超平面との峻別に関する言及)がないから、この意味で、特許文献3(US4744028)の図1や図3は、あくまでも(感覚的な)模式図にすぎない。
(高次元ピラミッド錐の凸性)
【００６１】
また、図12の4次元ピラミッド錐体の底面の4角形1-2-3-4が、当該実質2次元の面の中で、凸4角形を形成するとき、該4次元ピラミッド錐は凸錐であると考えてよい。逆に、該4次元ピラミッド錐が凸錐であるならば、底面の4角形1-2-3-4(実質2次元の面内にある)は凸4角形を形成するとみなしてよい。同様に、n次元ピラミッド錐体の底面(実質2次元の面)のn多角形1-2-・・・-nが凸多角形を形成するとき、該n次元ピラミッド錐は凸錐であると考えてよい。逆に、該n次元ピラミッド錐が凸錐であるならば、底面のn多角形1-2-・・・-n(実質2次元の面内にある)は凸多角形を形成するとみなしてよい。
図14(a)は実質2次元の面内のn多角形を一つ取り上げたとき、それが凸多角形を形成するか否かの判定法を例示している。図14(a)において、n多角形の角を構成すべきn個の点1,2,・・・及びnを改めて、それぞれP1,P2,・・・及びPnとする。一つの点PP1から始めて、例えば、反時計回りに全ての点を通過して一巡することを考える。PP1から始めて反時計回りに進めるとき、進行方向最も右側に来る点を次のPP２とする。順次、反時計回りに進めて、進行方向最も右側に来る点通過しながら、点列PP1,PP２,PP３・・・を形成する。この点列が前記P1,P2,・・・及びPnを全て包含し、点列PP1,PP２,PP３・・・,PPnとなり、最後にPPnから反時計回りに進めて、進行方向最も右側に来る点がPP1となれば、n多角形1-2-・・・-nは凸多角形であると考えてよい。すべてn個の点を通過せず一巡し、多角形内部にP1,P2,・・・及びPnのいずれかが残留すれば(図14(b)参照)、その多角形は凸ではない。この判定方法はコンピュータ判定手順として組み込むことは難しくない。ここは、凸多角形を形成するか否かの判定法についての実施可能性を記述したものであって、勿論、数学的定義(凸性の)に遡って、別途の判定法を構築してもよい。また、計算判定途上で、n多角形を確認したいときは、適宜対話型処理手順を組み込んでもよい。
(高次元の凸多面体内部領域)
【００６２】
上記のように、高次元ピラミッド錐の凸性判定をコンピュータに実行させ得ることも本発明は利用する。線型計画法の問題の拘束条件式(61)から(6m)のm個の超平面Π1,Π2,Π3,・・・,Πmに囲まれる高次元の多面体内部凸領域とは、前記半空間の集合に関する記号
ΠiU(ｘ)={ｘ｜<ni,x>≧pi}                        (31)
ΠiL(ｘ)={ｘ｜<ni,x>≦pi}                        (32)
を用いれば、
ΠiU(ｘ)={ｘ｜<ni,x>≦pi},(i=1からm)            (33)
についての共通集合
Π1U∩Π2U∩・・・∩ΠmU,(i=1からmまで)              (34)
或いは
ΠiL(ｘ)={ｘ｜<ni,x>≧pi},(i=1からm)            (35)
についての共通集合
Π1L∩Π2L∩・・・∩ΠmL,(i=1からmまで)              (36)
が形成する凸多面体内部領域を意味する。共通集合として前者のΠ1L∩Π2L∩・・・∩ΠmL,(i=1からmまで)の場合も、適正な座標1次変換で、Π1U∩Π2U∩・・・∩ΠmU,(i=1からmまで)のように、表記可能となる。また、ここまで通り{ｘ｜<ni,x>≦pi},(i=1からmまで)なる半空間で考えて、原点を、前記nf軸の正方向側から、原点を覆う凸多面体領域を考えるものとする。つまり、該凸多面体内部領域にn次元空間の原点を取るものとする。このように考えて一般性は失われない。
【００６３】
こうして、式(5)のような拘束条件下で式(4)のような目的関数を最大・最小化させる線型計画法問題は、
目的関数  <nf,x>=pf≧0                        (37)
を不等式拘束条件
<n1,x>≦p1                        (381)
<n2,x>≦p2                        (382)
<n3,x>≦p3                        (383)
・
・
<ni,x>≦pi                        (38i)
・
<nm-1,x>≦pn-1                      (38m-1)
<nm,x>≦pn                        (38m)
の下で最大化させる問題と等価であることが明確化した。つまり、共通集合
Π1U∩Π2U∩・・・∩ΠmU,(i=1からmまで)
が形成する凸多面体の一つの頂点が作る一つのある高次元ピラミッド錐の頂点に超平面
Πf(ｘ)={ｘ｜<nf,x>=pf}                        (39)
が接するようにして、pfが最大になるようにしてよいことになる。
【００６４】
上記のように定式化して、線型計画問題に臨み求解できれば、スラック変数を導入して、問題の次元数(パラメータ数)を増大させる必要はなくなる。従来、スラック変数を導入するプラクティスが一般的であったのは、高次元の多面体内部凸領域を幾何学的に捉えることが困難であったためと考えてよい。パラメータ数が2個の場合は、拘束条件数が沢山あっても幾何学的に問題を例示できてきた。後述で、本発明の実施例の説明をするにあたっては、パラメータ数が2個の場合をベースとして、如何に高次元の場合に敷衍できるかを、具体的に示す。
(高次元の凸多面体頂点標高追跡)
【００６５】
前述したように、超平面(部分空間)Π1,Π2の交叉から始めて、段階的に超平面を追加して都度の交叉、即ち、Π1∩Π2∩・・・∩Πjなる交叉空間における、原点Ｏからの最短距離点Ｓjは、該交叉空間の次元自体は1次元以上であっても、実質0次元の点として求まった。つまり、点Ｓjの座標が確定する。従って、ベクトル(ＯＳj)とベクトルnfとの内積を評価して、ベクトル(ＯＳj)のnf軸への正射影を求めることができる。この正射影の値を点Ｓjのnf軸に関する標高と呼ぶこととする。つまり、実質0次元の点Ｓjを通過しnf軸に直交する、厚みのない超平面（Πf(ｘ)={ｘ｜<nf,x>=pf}に平行な一つの超平面）が該nf軸と交わる点までの原点よりの距離が、この標高である。この交叉空間列において、この標高の評価を行いながら、原点Ｏからの最短距離点Ｓjに関する点列を追跡するアルゴリズムを、本願では、部分空間の最短距離点標高評価手法と呼ぶ。
上記の線型問題（拘束不等式(381)から(38m)の条件下で目的関数式(37)を最大化）はm個の拘束不等式の中からn個の拘束不等式を選定する際の、mCn個の組合せ数のピラミット錐の頂点のなかで、該標高の最も小さくなる頂点を決定し、その標高値を決める問題とみなしてよい。
また、前記高次元多面体頂点座標の計算の所では、n個の拘束条件に対する超平面Π1,Π2,・・・,Πnが与えられたとき、部分空間の最短距離点到達手法を用いて、対応するｎ元ｎ次の連立方程式が解き得ることを記述した。一方、n個の拘束条件に対する超平面Π1,Π2,・・・,Πnが与えられていなくとも、上記部分空間の最短距離点標高評価手法と絡めて、解候補(解頂点候補)を求めることができるので、補足する。
超平面はn個以上あるとして、垂線距離piの最も小さい超平面Πi(これをここではΠP1とする)から始めて、超平面の列ΠP1,ΠP2,・・・,ΠPnを考える。ΠP2は、部分空間(ΠP1∩ΠP2)についての、原点Ｏよりの最短距離点Ｓ2の標高が最小となるように、決める。ΠP3は部分空間(ΠP1∩ΠP2∩ΠP2)についての、原点Ｏよりの最短距離点Ｓ3の標高が最小となるように、決める。さらに、順次続けて、部分空間(ΠP1∩ΠP2∩ΠP2∩・・・∩ΠPj)についての、原点Ｏよりの最短距離点Ｓjの標高が最小となるように、決める。最終的に、部分空間(ΠP1∩ΠP2∩ΠP2∩・・・∩ΠPn)についての、原点Ｏよりの最短距離点Ｓnの標高が最小となるように、超平面の列ΠP1,ΠP2,・・・,ΠPnを取り上げれば、n個の組の超平面を決定すると同時に、該ｎ元ｎ次の連立方程式の解候補(解頂点候補)が求まったと考えることができる。本願では、連立方程式の解法に関しては、従来手法の他に、記述した、部分空間の最短距離点到達手法や上記部分空間の最短距離点標高評価手法を含めて考えている。
【００６６】
また、mCn個の組合せ数のピラミット錐なかで、該標高の最も小さくなるピラミット錐(頂点)を決めるのにmCn個の組合せ数のピラミット錐をすべて、吟味する必要はない。上記の部分空間最短距離点標高評価法を応用することができる。
その前に、ｎ次元の一つのピラミット錐頂点から、該ピラミット錐頂点に連結する、別のピラミッド錐頂点へ移動する手法について考察する。前述のように、Π1∩Π2∩・・・∩Πn-1の交叉空間における原点Ｏからの最短距離点Ｓn-1からvnn方向(rnの逆方向)に走る直線が、超平面Πnを貫通する実質0次元の点Ｓnは、Π1∩Π2∩・・・∩Πnの交叉点(実質0次元の点)であった。逆に、該点Ｓnが知れているとき、逆格子ベクトルrnが既知とすれば、Π1∩Π2∩・・・∩Πn-1の交叉空間における原点Ｏからの最短距離点Ｓn-1を求めることができる。これは、3角形ＳnＳn-1Ｏが直角3角形をなし、距離(ＯＳn)は計算可能で、角度（ＯＳnＳn-1）もベクトル(ＯＳn)と逆格子ベクトルrnとの内積から計算可能なことから、明らかである。
また、該点Ｓnが、超平面の組Ａ0=｛Π1,Π2,・・・,Πα-1,Πα,Πα+1,・・・,Πn-1,Πn｝の合併集合Ｘ0=Π1∩Π2∩・・・∩Πα-1∩Πα∩Πα+1∩・・・∩Πn-1∩Πnの交叉点として、知れていて、当該の逆格子ベクトル系{r1,r2,r3,・・・,rα-1,rα,rα-1,・・・,rn-1,rn}全体も既知とすれば、当該の超平面の組の中の任意の超平面Παを、当該の超平面の組から抜き去って構成された部分空間Ｘ0-=Π1∩Π2∩・・・∩Πα-1∩Πα+1∩・・・∩Πn-1∩Πnに関する、原点Ｏからの最短距離点Ｓn-1を計算することが可能である。理由は上記と同様で、3角形ＳnＳn-1Ｏが直角3角形をなし、距離(ＯＳn)は計算可能で、角度（ＯＳnＳn-1）もベクトル(ＯＳn)と逆格子ベクトルrαとの内積から計算可能なためである。なお、部分空間Ｘ0-に対する超平面の組｛Π1,Π2,・・・,Πα-1,Πα+1,・・・,Πn-1,Πn｝を記号Ａ0-で表すこととする。
ここで、超平面の組Ａ0=｛Π1,Π2,・・・,Πα-1,Πα,Πα+1,・・・,Πn-1,Πn｝に現れていない(用いられていない)超平面Πβを以って、超平面Παと置き換え、ｎ個の超平面の組Ａ1=｛Π1,Π2,・・・,Πα-1,Πβ,Πα+1,・・・,Πn-1,Πn｝を作る。該組Ａ1から、超平面Πβを取り除いた、(n-1)個の超平面の組Ａ0-(とする)は、この段階では、Ａ0-と同じである。
超平面の組Ａ1が形成するピラミッド錐の頂点(Ｖ1とする)は、該組Ａ1の合併集合Ｘ1=Π1∩Π2∩・・・∩Πα-1∩Πβ∩Πα+1∩・・・∩Πn-1∩Πnの交叉点であり、(n-1)次元の部分空間Ｘ0-=Π1∩Π2∩・・・∩Πα-1∩Πα+1∩・・・∩Πn-1∩Πnと超平面Πβとの交差点として、比較的簡単にもとめることができる(前記部分空間の最短距離点到達手法により)。
上記の手順を続けて、
ｎ個の超平面の組の列Ａ1,Ａ2,Ａ3,・・・・・・
(n-1)個の超平面の組の列Ａ1-,Ａ2-,Ａ3-,・・・・・・
合併集合Ｘ1の列Ｘ1,Ｘ2,Ｘ3,・・・・・・
(n-1)次元の部分空間の列Ｘ1-,Ｘ2-,Ｘ3-,・・・・・・
ピラミッド錐の頂点の列Ｖ1,Ｖ2,Ｖ3,・・・・・・
が形成される。ここで、隣り合う超平面の組Ａk,Ａk+1では(n-1)個の超平面を共有するが、Ａk+1で新たに置き換えられた超平面はＡk以前の組には現れていない(用いられていない)。また、Ａk+1で新たに置き換えられた(加えられた)超平面と前段の(n-1)次元の部分空間Ｘk-との交差が新たなピラミッド錐の頂点Ｖk+1となり、前段のピラミッド錐の頂点Ｖkと連結する。ここで、Ａk+1で新たに置き換えられた(加えられた)超平面と前段の(n-1)次元の部分空間Ｘk-との交差を計算するには、前記部分空間の最短距離点到達手法を用いればよい。
さらに、ピラミッド錐の頂点の列Ｖ1,Ｖ2,Ｖ3,・・・・・・の各々の、前記nｆ軸への正射影標高をＨ1,Ｈ2,Ｈ3,・・・・・・とする。ここで、Ａk+1で新たに超平面を置き換える(加える)にあたっては、標高増大代(Ｈk+1-Ｈk)が恒に正で且つ前段の標高増大代(Ｈk-Ｈk-1)を恒に下回るように、置き換える(加える)超平面を選定するとよい。こうすれば、、当該線型計画問題の拘束条件(例えば、式(61)から(6m))が形成する凸多面体の頂点の何処かに到達するとみなしてよい。また、正値としての標高増大代(Ｈk+1-Ｈk)が標高増大代(Ｈk-Ｈk-1)を下回ることがなくなった場合は、当該線型計画問題の解頂点に到達している可能性が極めて高い。
以上で、本願に係わる数理記法及び数理工学的原理(本願に伴う固有のコンセプト開示を含む)を説明した。更に、要する説明は都度記述する
【００６７】
図1は本発明の基本概念・技法を説明する線型計画問題の第1例であり、図2は本発明の基本概念・技法を説明する線型計画問題の第2例である。
図1における線型計画問題は、ある工場での二つの製品(ディーゼルエンジン[DE]プラントとガスエンジン[GE]プラント)の生産計画に係わるものである。当該工場のある一定生産期間に、DEプラント及びGEプラントをそれぞれx単位(例えば1単位はαkW分のように考える)及びy単位(例えば1単位はβkW分のように考える)分を製作し、粗利を最大化する問題がある。このとき、下記のデータは与えられているものとする。
【表１】
2012203710.tif 000003
【００６８】
上記の生産計画問題を定式化すれば、下記のようになる。
目的関数:f(x,y)=0.8x+0.5y→最大化
拘束条件:g1(x,y)=6x+3y≦60                    〔1〕
g2(x,y)=5x+4.5y≦62                  〔2〕
g3(x,y)=0.4x+y≦12                    〔3〕
g4(x,y)=6x+y≦54                      〔4〕
この問題は、目的関数式、各拘束条件式における独立変数がx,yの2個であり、2次元の図式解法が可能であり、従来手法と本発明の技法との間の相異を説明する好適な例題でもある。
【００６９】
図1に示したように、2次元のx-y座標平面の中で、各拘束条件はそれぞれに対応する直線の、座標原点側の領域に対応している。所謂ヘッセの標準形で書き直せば、目的関数式、拘束条件式は下記のようになる。
xcosθf+ysinθf≦pf 
xcosθ1+ysinθ1≦p1          〔1〕
xcosθ2+ysinθ2≦p2          〔2〕
xcosθ3+ysinθ3≦p3          〔3〕
xcosθ4+ysinθ4≦p4          〔4〕
ここで、具体的数値を付記すると、
θf≒32.0°,θ1≒26.6°,θ2≒41.9°,θ3≒68.2°,θ4≒9.5°,
pf→最大化,p1≒13.4,p2≒11.1,p3≒9.2,p4≒8.9
である。
【００７０】
上記で更に、x,yが非負とすると、図1において、上記の各拘束不等式の不等号を等式に置き換えた各式が表す直線とx軸及びy軸とが囲む多角形OPxP14P12P23PyOの内部がベクトル[xy]tの存在可能な許容定義領域になっている。ここで、点Oは座標の原点、点Pxはx軸と拘束条件の直線〔4〕との交点、点P14は拘束条件の直線〔4〕と拘束条件の直線〔1〕との交点、点P12は拘束条件の直線〔1〕と拘束条件の直線〔2〕との交点、点P23は拘束条件の直線〔2〕と拘束条件の直線〔3〕との交点、点Pyはy軸と拘束条件の直線〔3〕との交点となっている。
一方、目的関数に関する方向余弦[cosθfsinθf]t(前記のベクトルnfに対応している)に垂直な平行線群を想定し、その平行線の一つが該多角形の一つの頂点に、外側から外接するとき、目的関数は、該拘束条件下で、最大化される。
図1の問題では、目的関数を最大化させるのは、目的関数の直線群xcosθf+ysinθf=pfが頂点P12(座標は[7.06.0]t)を通過するときであり、このとき、pf≒9.116となる。このpf≒9.116が取り得る目的関数の最大値である。因みに、この最大値pf≒9.116を与える取り得る,方向余弦[cosθfsinθf]t方向上の座標[xy]tはほぼ[7.7304.8321]tである。座標[7.06.0]tも座標[7.7304.8321]tも直線の方程式xcosθf+ysinθf=pf≒9.116を満足する。
【００７１】
背景技術の所で前記したように、従来技術の単体法や内点法の解探索経路を説明する模式図については、それぞれ、図17(a)及び図17(b)がある。本願の数理記法及び数理工学的原理に関連して、記述したように、4次元以上の高次元空間の多面体構造を認識するには、実質0次元点・実質1次元の線・実質2次元の面を定義した上での考察が不可欠であり、従来技術箱の認識において、明瞭さが不足している。つまり、模式図の範囲を超えない。従って、従来技術の単体法や内点法の解法アルゴリズムは、幾何学的イメージを十分に伴ったものではなく、主に代数演算操作(掃出し枢軸計算や逆行列計算等)あるいはベクトル収束計算に依存したものである。本発明は、代数演算操作(掃出し枢軸計算や逆行列計算等)あるいはベクトル収束計算に依存するが故の、ややもすれば、分かり難い点を克服し、コンピュータ計算のソフトウェア並びにそれを実行する、コンピュータシステム(設計支援装置)の質と効率を向上させる。
【００７２】
また、図18あるいは図19はそれぞれ、図17(a)あるいは図17(b)に対応して、2次元のパラメータ変数の線型計画問題について、解探索経路を説明している。図18は単体法による線型計画法の概略を2次元のモデルで示したものである。所謂、主問題(プライマリー)標準形
目的:    ctx→最大化                    (導入式3)
条件:    Ax=b,x≧0                    (導入式4)
なる最適化問題であって、c,xは2行1列ベクトル、Aはｍ行2列の行列、bはｍ行1列のベクトルである。ここで、ｍは拘束条件数で一般に2以上が想定される。また、変数xには非負条件x≧0が課せられている。つまり、
x=[x1x2]t
とすれば,x1軸x2軸平面の第一象限内にて,ｍ個の方程式Ax=bが表わす直線群と該x1軸及びx2軸とによって囲まれる凸領域(凸多角形領域)を直線ctx=c(cはパラメータ)が過ぎるものとして,該パラメータcを最大化する問題である。単体法では,該多角形の一つの頂点から出発して,単体表(説明省略)を作成の上,凸多角形領域の辺を辿りながら,多角形の頂点を次々と登りつめ,該パラメータcを最大化させる頂点に辿り着かせる手法である。
【００７３】
しかしながら、上記のように凸多角形領域の辺を辿る操作は必須であろうか。図1の例題において、目的関数の超平面(ここでは直線)が該凸多角形領域に外接する解頂点は、最終的に2本の拘束条件の直線で決まってしまう。最初から解頂点を構成する拘束条件の組を選定乃至絞り込むことができれば、他の拘束条件は全く不要とも言える。図1の例題は、ヘッセ標準形に書き改められた拘束条件式の組に関して、θi,(i=1から4)、pi,(i=1から4)の大小バランスが良い例ではあるが、目的関数の直線群の一つが該凸多角形領域に外接する解頂点は、目的関数直線群に垂直な方向余弦角θf≒32.0°を挟む(囲む)θ1≒26.6°及びθ2≒41.9°に対応する直線〔1〕及び直線〔2〕の交点となっている。このような図1の例題では、方向余弦ベクトルnfを近傍で挟む(囲む)ピラミッド錐(この場合は原点を頂点とし、ある二つの方向余弦ベクトルnk及びnlが形成する三角形)を確定すれば、解頂点は決まる。また、決定された解頂点のnf軸方向への正射影(正射影標高とも表現する)を計算すれば、該正射影点までの原点よりの距離が、目的関数を最大値pf(pfの取り得る最大値)となる。
【００７４】
上記は、解頂点を構成する拘束条件の組を、一気に決定することのできる例であるが、そこまではできなくとも、真の解頂点の近傍にある、（許容定義領域を構成する）凸多面体(ここでは凸多角形領域)の頂点の一つを形成する拘束条件の組を確定できれば、たとえ、稜辺を辿るにせよ、真の解頂点に到達する上で、計算の効率は著しく向上する。
本発明は図1の2次元のパラメータ変数の線型計画問題の取扱技法を、更に、高次元の問題へと一般化する。また、図1に関する、上記の説明から分かるように、ヘッセ標準形に問題の定式化を書き改めるので、スラック変数は導入する必要はなくなる。従って、計算の規模は抑制されて、計算速度・効率ともに向上する。
【００７５】
図2における線型計画問題は、ある工場での工場弁当献立の計画に係わるものである。工場弁当の副食総菜Ｎ及びＳ(例えば肉と魚)についてある配食期間(例えば10日間)中に、総菜Ｎ及びＳをどのように献立に組み入れるかという問題がある。ここで、組み入れられた副食総菜全体から、摂取されるべき、栄養素A,B,C,D(例えば脂肪,蛋白,炭水化物,無機質等)の必要摂取量の下限は決められているものとする。その上で、総菜Ｎ及びＳの単価に応じて、弁当製作費は極力節約することを課題とする問題である。総菜Ｎ及びＳの所要仕入れ量(kg)をx及びyとする。このとき、下記のデータは与えられているものとする。
【表２】
2012203710.tif 000004
【００７６】
上記の工場弁当献立の計画問題を定式化すれば、下記のようになる。
目的関数:    f(x,y)=3x+4y→最小化          〔0〕
拘束条件:    g1(x,y)=4x+y≧80            〔1〕
g2(x,y)=2x+2y≧100            〔2〕
g3(x,y)=2x+3y≧120            〔3〕
g4(x,y)=x+3y≧90              〔4〕
この問題も、目的関数式、各拘束条件式における独立変数がx,yの2個であり、2次元の図式解法が、従来手法に従う意味においても、可能な例題である。拘束条件〔1〕から〔4〕が形成する凸(多角形)領域が、図2に示されている。
【００７７】
上記で更に、x,yが非負とすると、図2の第1象限において、折線SyS1S2Sxの上方側(原点より遠方側)が、該凸(多角形)領域となっている。この領域に、目的関数(直線)群の一つの直線が、下側(原点により近傍側)から外接するような多角形頂点を見出すことが課題になっている。ここで、点Oは座標の原点、点Syはy軸と拘束条件の直線〔1〕との交点、点S1は拘束条件の直線〔1〕と拘束条件の直線〔2〕との交点、点S2は拘束条件の直線〔2〕と拘束条件の直線〔3〕との交点(この例題では点S2は拘束条件の直線〔2〕と拘束条件の直線〔4〕との交点ともなっていて、直線〔2〕,〔3〕,〔4〕は全て点S2を通過している)、点Sxはx軸と拘束条件の直線〔4〕との交点である。
【００７８】
この例題2の最小化問題は、例題1と同様の原点側を囲む領域での最大化問題に帰着させることが可能である。例えば、X=100-x,Y=100-yのような変数変換を行う。これはコンピュータへの入力の際に実行してもよいし、ヘッセ標準形に書き直す際のソフトウェア側(プログラム内)で実行してもよい。拘束条件〔1〕から〔4〕は、この変換により次のようになる。
拘束条件:    4X+Y≦420          〔1’〕
2X+2Y≦300          〔2’〕
2X+3Y≦380          〔3’〕
X+3Y≦310          〔4’〕
さらに、ヘッセ標準形に書き直すと次のようになる。
Xcosθ1+Ysinθ1≦p1          〔1’〕
Xcosθ2+Ysinθ2≦p2          〔2’〕
Xcosθ3+Ysinθ3≦p3          〔3’〕
Xcosθ4+Ysinθ4≦p4          〔4’〕
尚、目的関数はfはX,Yの関数として改めて、
f(X,Y)=Xcosθf+Ysinθf=pf→最大化            〔0’〕
と書き直される(最大化問題に転換される)。
ここで、具体的数値を付記すると、
θf≒53.1°,θ1≒14.0°,θ2=45.0°,θ3≒56.3°,θ4≒71.6°,
pf→最大化,p1≒101.8,p2≒106.7,p3≒105.4,p4≒98.1
である。この変数変換された問題は、図3に示される。
【００７９】
図1のときと同様に、図3において、nf,n1,n2,n3,n4はそれぞれ対応する拘束条件の直線に向かって原点より垂線の足を下ろす方向の方向余弦ベクトルである。つまり、nf＝[cosθfsinθf]t,ni＝[cosθisinθi]t(i=1から4)である。また、各piは対応の直線〔i’〕の垂線距離(原点から垂線の足までの距離)である。
図3に示されたように、n2とn3とがnfを挟んで(囲んで)いて、n2とn3のそれぞれに対応する直線〔2’〕と〔3’〕との交点S23(座標[X0Y0]t)が目的関数の直線群の一つが凸多角形領域に外接する頂点(前記した通り解頂点と呼んでもよい)となっている。ただし、垂線距離p1,p2,p3,p4の相対バランスが変化して、例えば、p4が僅かに小さい方向に変化してくる(直線〔4’〕が原点寄りに僅かに平行移動する)と解頂点は直線〔2’〕と〔4’〕とによって形成されるようになる。
図3や図1の例において、解頂点を決定するのに、4個の直線の内2個を選ぶ組合せ、即ち、4C2=6通りの組合せがある。n1,n2,n3,n4はの中から2個(nj及びnkとし対応の垂線距離をpj及びpkとする)を選ぶ選定基準としては、次のような表現をしてもよい。即ち、nj及びnkとがnfを挟んで(囲んで)いて,且つpj及びpkの一方は低いレベルになるようにするとよい。
【００８０】
上記をより具体的にいうと、二つの直線を選ぶに際して、一つの直線(j)は垂線距離pjが小さい側のもの(最小のものとは限られないことに注意する)とし、他方の直線(k)はnj及びnkとがnfを挟む(囲む)ような直線(k)を取り上げるとよい。また、次のように言ってももよい。
二つの直線を選ぶに際して、一つの直線(j)は方向余弦njがnfに近い(内積<nf,nj>が1に近い)側のもの(最も近いものとは限られないことに注意する)とし、他方の直線(k)はnj及びnkとがnfを挟む(囲む)ような直線(k)を取り上げるとよい。
このように選定され二つの直線の組には線型計画問題の正解の解頂点を与える直線の組を含んでいる確度が高い。こうして、凸多角形の境界辺を辿らなくても正解候補の頂点を選び出し相互比較(目的関数値に関する)が可能となる。また、境界辺を辿る手順も組み込むにせよ、出発点としての頂点を効率よく選定することを可能にする。
【００８１】
上記の例題1及び2に関連して、導入された拘束条件の選定乃至絞り込む手法を高次元の問題に応用できるように、表現すると次のようになる。ここで、目的関数の表示は式(37)、拘束条件は式(381)から式(38m)に準拠することとする。つまり、拘束条件に関するmCnの組の中から、n個の拘束条件を絞り込む(選定する)基準を説明する。ここでも、一気に、解頂点を与えるn個の拘束条件を見出すというよりは、有望な解頂点候補を(n個の拘束条件の組を複数組)絞り込む技法を考える。つまり、m個の拘束条件をm’個に絞り込んで、検討すべきピラミッド錐の数をmCn個からm’Cn個に減らすことを考える。ここで、m個の拘束条件は超平面Π1,Π2,・・・,Πi・・・,Πmに対応する。また、各超平面Π1,Π2,・・・,Πi・・・,Πmのそれぞれに、それらの方向余弦ベクトルn1,n2,・・・,ni,・・・,nm並びに垂線距離p1,p2,p3,・・・,pi,・・・,pmが対応する。方向余弦ベクトルn1,n2,・・・,ni,・・・,nmのそれぞれが、nf方向となす交角をα1,α2,α3,・・・,αi,・・・,αmとする。各αiは0°から90°の範囲にある。尚、方向余弦ベクトルn1,n2,・・・,ni,・・・,nmのそれぞれが及びnfの起点は同一点としてピラミッド錐は形成されるものとする。
垂線距離p1,p2,p3,・・・,pmの大小バランスがとれているとき、つまり、ある距離参照値prefを設定して、min{pi/pref}からmax{pi/pref}までの範囲が所定の範囲内に納まるようなときは、
例えば、αiが小さい方の超平面Πiをm’個(勿論m≧m’≧nである)取り出して、m’Cn個のピラミッド錐の各々が凸錐を形成し、さらに、その凸錐がnf軸を囲む凸錐(超平面の組)のみに絞り込めばべばよい。この条件を満足する凸錐がないときはm’の数を増やせばよい。また、絞り込む凸錐の数は、複数個あり、相対的に頂点の標高比較ができることが望ましい。
また、垂線距離p1,p2,p3,・・・,pmの中の、小さい方の超平面Πiをm’個(勿論m≧m’≧nである)取り出して、m’Cn個のピラミッド錐の各々が凸錐を形成し、さらに、その凸錐がnf軸を囲む凸錐(超平面の組)のみに絞り込めばべばよい。この条件を満足する凸錐がないときはm’の数を増やせばよい。また、絞り込む凸錐の数は、複数個あり、相対的に頂点の標高比較ができることが望ましい。
上記は、解頂点候補を形成するピラミッド錘の数を限定する、選定基準を、予め、決定できることを述べている。勿論、当該線型計画問題の解析者が、経験的に知っている特定の必須拘束条件が含まれて、解頂点候補を形成するピラミッド錘の数が限定されるようにしてもよい。また、ピラミッド錘の数を限定する、選定基準の例については、後記の図8(a)及び図8(b)で補足される。
ここで、ピラミッド錐の凸性は、ピラミッド錐の底面(実質二次元の平面)をとり、底面ｎ多角形の凸性判定により可能であり、方向余弦ベクトルn1,n2,・・・,ni,・・・,nmがnfを囲むか否かは、該底面凸ｎ多角形内部の点をnf方向直線が貫通するか否かで判定可能である。ピラミッド錐乃至ピラミッド錐体については、前記しているが、さらに、後述される。
【００８２】
再度、2次元の問題に戻って、拘束条件が形成し得る頂点の数について、説明する。図4はパラメータ数が2個、拘束制約が6の場合を取り上げ、頂点数6C2=15個形成される例を示す。図4において、6本の直線i,j,k,l,m,nが凸多角形を形成している。ここで、6本の直線の内、2本の直線αとβの交点を(αβ)と書くこととすれば6C2=15個の頂点は、(ij),(ik),(il),(im),(in),(jk),(jl),(jm),(jn),(kl),(km),(kn),(lm),(ln),(mn)である。頂点の列(ij)(jk)(kl)(lm)(mn)が凸多角形を形成している。また、図3において、目的関数の直線群の一つをnfに垂直な直線としている。このnfに垂直な直線に平行な直線が該凸多角形に外接するのは頂点(jk)であることが分かる。この解頂点を決定しているのは直線jとkとの組であって、他の直線は元来無関係である。本発明では、この無関係な拘束条件(の直線乃至超平面)を最初から極力除外するものである。
一方、従来手法の場合、辺を辿る手間が必要なことのほかに、各拘束条件にスラック変数を導入するので、図4の2次元の問題を8次元の問題へと複雑化させている(形成される頂点数は8C2=28に増大する)。本発明はこの複雑化を回避することができる。
【００８３】
2次元の問題でさらに説明を続ける。図5(a)では、許容領域の辺を形成する、直線が6本（直線L1から直線L6まで）、即ち、拘束条件の数が6の場合の例を示している。交点P12,P23,P34,P45,P56が多角形（許容領域）の頂点を、また、辺R1,R2,R3,R4,R5,R6が稜(辺)を形成している。原点から各辺Ri(即ち直線Li)に向かう方向余弦ベクトルをniとする。原点よりまた、目的関数の直線群Lfに平行で、原点を通過する直線を、Lf0とし、原点より辺R1,R2,R3,R4,R5,R6の各々への垂線距離をp1,p2,p3,p4,p5,p6とする。該直線Lf0に直交して,該直線群Lfに向かう方向余弦ベクトル(単位ベクトル)をnfとする。図5(a)で、最適化解を与える頂点(目的関数を最大化させる解頂点)は、P34であり方向余弦ベクトルをn4とn5が最も近接して、直線群Lfに向かう方向余弦ベクトルnfを挟んでいる。この点に着眼すれば、当該の問題の解を探すのに、辺R1,R2,R5,R6は不要であることが分かる。しかも、該頂点P45の座標は方向余弦ベクトルn4とn5並びに,対応の垂線距離p4とp5に依って決まる。
【００８４】
また、図5(a)において、方向余弦ベクトルをni,(i=1から6)は、原点を通過してnfに直交する直線Lf0の上側(nf方向側)の半平面に存在している。仮に、方向余弦ベクトルniの一つが、反対側の半平面にあるとすると、当該の拘束条件不等式を満足する領域はnf方向側に無限に拡がるから、目的関数最大値を構成する条件から逸脱する。従って、この場合は、方向余弦ベクトルniは不要な拘束条件となる。
つまり、線型計画問題をヘッセ標準形を用いて、目的関数の表示は式(37)、拘束条件は式(381)から式(38m)のように書き改めておくと、無用な拘束条件を始めから除去することが可能となる。これはコンピュータ計算の速度・効率向上に寄与する。特に、高次元の一般の場合は、上記直線Lf0はnfに直交し原点を通過する超平面として、また半平面は高次元空間の半空間として敷衍される。つまり、高次元の一般の場合に通用する言い様をすれば、凸多面体領域は、目的関数の超平面群Πfに平行で、原点を通過する超平面を、Πf0として、Πf0により区切られるnf方向側の半空間の中でのみ考慮すればよい。
尚、拘束条件式の一つの方向余弦ベクトルniがnf方向の半平面乃至半空間にあるか否かは、内積<ni,nf>の正負により判定可能である。
尚、図5(a)において、pi,(i=1から6)には、突出して小さなpiが存在せず、バランスのよい例である。ベクトルniがnfとなす前記角度αiで見ると、α4,α3,α5,α2,α6,α3の順で、ベクトルniがnf軸に近い。αiが小さい方の直線Liをm’個選ぶとすればm’=3程度が適当であるとみなせる。実際、α4,α3,α5,に対応する直線L4,L3,L5の内、L4とL5が解頂点を形成している。図8(a)はこの状況を説明している。
【００８５】
さらに、不要な拘束条件の排除について、2次元の問題を用いて、説明を続ける。図6は不要な拘束条件例を説明する図である。図6において、直線L1,L2,L3,L4があり、L1,L2が互いに平行、また、L3,L４が互いに平行とする。目的線型関数式が表わす直線群に平行で、原点を通過する直線を、Lf0とする。前記と同様に、原点から各直線Liに向かう方向余弦ベクトルをni(i=1,・・・,4)とし各Liへの原点よりの垂線距離はpi(i=1,・・・,4)とする(図6においてniとpiは書込省略)。また、直線L1,L３の交点をP13,直線L2,L３の交点をP23,直線L1,L4の交点をP14とする。許容定義領域は、直線L1,L2,L3,L4の下側（直線Lf0側）の共通部分であり、この例では,許容定義領域は、L1-P13-L3の３角形の下側斜線部内部となる。従って、ここでは、直線L2,L4は許容定義領域を構成せず不要である。直線L1,L2のそれぞれの方向余弦ベクトルn1とn2は同一で、
n1=n2
であって
p2≧p1
であるから,直線L2は始めから除去されているべきであることが分かる。同様に,直線L3,L4についても,n3=n4且つp4≧p3であることから,直線L4は始めから除去されているべきであることが分かる。
上記は2次元の場合の説明であるが、ヘッセの標準形表示を用いる本発明では、当然のことながら、高次元の場合にも応用可能である。
【００８６】
図7(a)及び図7(b)はほぼ平行な2直線(2平面)の一方を除去する技法を説明する図である。図7(a)は、完全に平行ではないものの略平行な二直線に関して考察している。図７(a)において、直線L1,L2のそれぞれの方向余弦ベクトルn1とn2が僅かな交角2θをもって、原点から前記直線Lf0の上方(前記nf方向)半平面に延びている。ベクトルp1n1とp2n2との平均ベクトル(p1n1+p2n2)/2をベクトル(ＯＰ)とし、該nmの直線Lf0よりの回転角をαとする。
直線L1,L2の交点P12が下方(前記nf方向の逆方向)半平面に存在する条件は、近似的に,
{(p2-p1)/2}tan(0.5π-θ)≧{(p1+p2)/2}tan(α)          (106)
のように表現してもよい。このような判定式が満たされれば、該交点が最適化解を与える解頂点から十分離れているとみなせるので、直線L1に比較して原点より遠方の直線L2を除去してもよい。上式から、距離比p2/p1及び交角の半分θとの間にいかなる関係があればよいかが知れる。または,前記とが決まった際に、該距離比p2/p1がどの程度であれば,直線L2を除去してよいかの指針を予め作成することが可能となる。
【００８７】
図7(a)においてベクトルn1とn2との位置関係及びp1とp2が入れ替わった場合を図7(b)に示す。直線L1,L2の交点P12が上方(前記nf方向)半平面に存在する場合を図7(b)は示している。この場合は、該交点P12が下方半平面内には存在しないものの、上方半平面の左方遠方にnf軸から十分離れるので、解の核心から遠く,一方の直線L1の拘束条件は除去可能とみなしてよい。
図7(a)及び図7(b)は2次元の場合の説明であるが、高次元の場合にも応用可能である。高次元の場合も,二つのベクトルn1とn2はともに実質１次元の軸線であり、両者を含む実質２次元の面があり、その実質２次元の面で考えれば、図7(a)及び図7(b)と同様である。但し、直線L1,L2は超平面Π1、Π2に置き換えて考え、交点P12は超平面Π1、Π2の共通集合Π1∩Π2の原点よりの最短距離点に置き換えて考えることになる。原点よりの最短距離(共通集合Π1∩Π2に関する)が原点より十分遠方ならば超平面Π1、Π2の一方は、拘束条件から除去してよい。
【００８８】
本発明では、目的関数式及び複数個の拘束条件式を、高次元空間の場合に一般化されたヘッセの標準型に変換して表現することに基礎を置いている。前記（式8,9,10等）のように、垂線距離piは、非負となるよう方向余弦ベクトルniを向付けしている。許容定義領域が凸多角形（広くは凸多面体）の場合、座標原点は該凸多角形（凸多面体）の内部にあると一般化して考えて良い。
図9は、本発明の観点に基づき、凸多角形領域(凸多面体領域)の構成を説明する図である。図9において、辺R1,R2,R3,R4,R5,R6ので囲まれる凸６角形が、置かれている。座標原点は該凸６角形の中に置かれている。また、前記直線Lf0及び前記nf方向が示されている。原点から各辺(直線)Ri,(i=1,・・・,6)に向かう方向余弦ベクトルをni(i=1,・・・,6)とし、各辺(直線)Riへの原点よりの垂線距離はpi(i=1,・・・,6)としている。各方向余弦ベクトルni(i=1,・・・,6)の、nf方向基準よりの回転角度をθi(i=1,・・・,6)とする。
【００８９】
図9の例では、許容定義領域は該凸６角形内部の閉じた領域であるが、当該の目的関数の最大化を考える場合、許容定義領域は辺(直線)R1,R5,R6のみで構成されるだけでよく、辺(直線)R2,R3,R4は不要である。つまり、方向余弦nfと各辺に対する方向余弦niとの交角がπ/2(=90°)以上(内積<nf,ni>が負)となる拘束条件式は,予め除去してよい。また、閉じた許容定義領域で問題を考えたいときは、辺(直線)R1,R5,R6と半平面基準線である直線Lf0とに囲まれた多角形を想定すればよい。図9の中で、ハッチングされた小三角形部分は、該凸６角形の外部となるが、目的関数の最大化を考える場合には、該小三角形部分は解に影響しない。
図9の例を、高次元の問題の場合へ敷衍するには、各辺(直線)Ri,(i=1,・・・,ｍ)に替えて、超平面Πi,(i=1,・・・,ｍ)を対応させ、半平面基準線である直線Lf0に替えて、半空間基準超平面Πf0を考えればよい。
尚、上下限制約条件や非負条件が当該線型計画問題に含まれていても、本発明の観点からは、統一的な取り扱いが可能である。
【００９０】
次に、図5(a)の例で、拘束条件を一部変化させた例を図5(b)を用いて説明する。図5(b)は図5(a)の例における、辺R5(即ち直線L5)の垂線距離p5が著しく短くされた問題を扱っている。その他の条件は、図5(a)の例と同じである。図5(b)に示すように、図5(a)の辺R5を原点に向かって平行移動、即ち、n5を一定としたままp5を小さくすると、辺R3、R4、旧R５、R6は許容凸領域の形成に寄与せず無関係になる。図5(a)の状況での最適点(解頂点)P45は新たな最適点P25に移行する。この新最適点P25を決定しているのは、垂線距離が最も小さい辺R5と辺R2である。辺R5の方向余弦ベクトルn5と辺R2の方向余弦ベクトルn2は目的関数群の直線の方向余弦ベクトルnfを挟んでいる。辺R5の方向余弦ベクトルn5と辺R3の方向余弦ベクトルn3も目的関数群の直線の方向余弦ベクトルnfを挟んでいて、さらに、n3はn2よりnfの向きに近いが、交点P35のnf方向標高は、交点P25のnf方向標高より大きいので最適点はP25となる。
尚、図5(b)において、pi,(i=1から6)の中では、突出して小さなpiが突出して小さくなっている。pi,(i=1から6)を小さいものから並べれば、p5,p1,p2,p3,p4,p6の順であり、piが小さい方の直線Liをm’個選ぶとすればm’=3程度が適当であるとみなせる。実際、p5,p1,p2に対応する直線L5,L1,L2の内、L2とL5が解頂点を形成している。図8(b)はこの状況を説明している。また、L1とL5も解頂点候補となるが、nf軸への正射影標高比較からもL2とL5の交叉P25が解頂点であることも分かる。
【００９１】
図10は、本発明の観点により、2次元空間において、2直線の交点を、逆格子ベクトルを用いて表現する手法を説明する図である。数理記法及び数理工学的原理に関連して前記したように、斜交軸ベクトル基底系{n1,n2,n3,・・・,ni,・・・,nn-1,nn}に対する、逆格子ベクトル系{r1,r2,r3,・・・,ri,・・・,rn-1,rn}を計算すれば、連立方程式(15)の解ｘ(拘束条件n個の組が形成するピラミッド錐の頂点)は、前記の式(23)により、
ｘ=p1(cosφ11)-1r1+p２(cosφ22)-1r２+・・・+pn(cosφnn)-1rn          (23)
となることを示した。図10は、2次元の場合について、2直線L1,L2の交点S2の座標ｘが、
ｘ=p1(cosφ11)-1r1+p２(cosφ22)-1r２
となることを図解したものである(証明省略)。
ここでは、図10をn次元空間のn1軸,n2軸(共に実質1次元の軸線で原点を通過している)が形成する実質2次元の断面図と見立てよう。直線L1,L2はそれぞれ超平面Π1、Π2の中の直線であるとみなす。原点Ｏから超平面Π1、に下ろした垂線の足をＳ1、該点Ｓ1から超平面Π2に下ろした垂線の足をＦ2、該点Ｓ1を通過しn1軸に該2次元の断面内で直交する直線が超平面Π2を貫通する点をＳ2(上記で交点Sとした点に相応する)としている。ここで3角形Ｓ1Ｆ2Ｓ2は角Ｓ1Ｆ2Ｓ2を直角とする直角3角形である。線分(Ｓ1Ｆ2)はn2軸に平行で,線分(Ｓ1Ｆ2)の長さdd2は超平面Π2のヘッセ標準式を暫定的に原点をＳ1へ移動して書けば求まる。また、角Ｆ2Ｓ1Ｓ2は逆格子ベクトル系r2軸とn2軸とのなす角度φ22であり、これも知れる。従って、距離(Ｓ1Ｓ2)は決まり、一方Ｓ1Ｓ2の方向はr2軸の方向であるからベクトル(Ｓ1Ｓ2)が求まる。また、ベクトル(ＯＳ1)はp1n1であったから、原点Ｏから交点Ｓ2へのベクトル(ＯＳ2)即ち、上記ｘ=p1(cosφ11)-1r1+p２(cosφ22)-1r２が求まる。尚、該点Ｓ2は、超平面Π1、Π2の交叉空間(共通集合)への最短距離点(原点Ｏから距離が最短の点)である。
尚、数理記法及び数理工学的原理に関連して、高次元多面体頂点座標の計算の所で記述したように、ベクトル(Ｓ1Ｓ2)の方向即ち逆格子ベクトルr2軸の方向はシュミットの直交化法の流儀で説明した。高次元の場合に敷衍する上では、シュミットの直交化法の流儀に従ってもよい。
ここで、一つ注意すべきことがある。3次元空間の中で、斜交軸ベクトル基底系{n1,n2,n3}を取り、その逆格子ベクトル系{r1,r2,r3}を考えれば
ｘ=p1(cosφ11)-1r1+p２(cosφ22)-1r２+p3(cosφ33)-1r3
なる式が成立するが、ここでの逆格子ベクトルr1,r2は、2次元の場合の式ｘ=p1(cosφ11)-1r1+p２(cosφ22)-1r２における逆格子ベクトルr1,r2とは別物である。2次元の場合の逆格子ベクトルr1,r2は斜交軸ベクトルn1,n2の関数であり、ベクトルn3の関与を想定していないが、3次元の場合の逆格子ベクトルr1,r2,r3は斜交軸ベクトルn1,n2,n3の関数であり、ベクトルn3が関与していることからも明らかである(従来文献ではこうした注意・配慮が見当たらないので記述しておく)。
【００９２】
図11は、本発明の観点により、3次元のピラミッド錐(3角錐)を紙面に描画する図である。数理記法及び数理工学的原理に関連して、高次元ピラミッド錐の説明ところで、既に記述した。ここで、若干補足する。図11において、3次元のピラミッド錐即ち3角錐が平面(実質2次元の面)Π1、Π2、Π3により形成され、該平面Π1、Π2、Π3の交叉空間(実質０次元の点)x123が頂点となっている。原点Ｏよりの、各平面Π1、Π2、Π3へ垂線の足を下ろすと、各垂線距離はp1,p2,p3であり、各垂線の方向はn1,n2,n3である。このとき、該3次元のピラミッド錐即ち3角錐の頂点x123を通過する稜線の方向は、逆格子ベクトルr1,r2,r3の方向となっていると考えてよい。ベクトルr1方向に対応する稜線は平面Π2、Π3の交線、ベクトルr2方向に対応する稜線は平面Π3、Π1の交線、ベクトルr3方向に対応する稜線は平面Π1、Π2の交線であると考えてよい。尚、逆格子ベクトルr1,r2,r3の方向は、ピラミッド錐の頂点から、前記半空間基準面に向かう方向とする(高次元の場合も同様)。
【００９３】
図12は、本発明の観点により、4次元のピラミッド錐(ピラミッド錐体)を紙面に描画する図である。数理記法及び数理工学的原理に関連して、高次元ピラミッド錐の説明ところで、既に記述した。ここで、若干補足する。図12において、該4次元のピラミッド錐体の頂点はＳとして、超平面Π1、Π2、Π3、Π4によって形成される。また,頂点Ｓを通過する稜線Ｒ1、Ｒ2、Ｒ3、Ｒ4が底面の点Ｂ1、Ｂ2、Ｂ3、Ｂ4のそれぞれと連絡している。図12における面ＳＢ1Ｂ2、面ＳＢ2Ｂ3、面ＳＢ3Ｂ4、面ＳＢ4Ｂ1等は実質２次元の面であって,超平面Π1、Π2、Π3、Π4とは異なる点に注意を要する。超平面Π1、Π2、Π3、Π4は実質３次元の構造を有しているために,図12のような,実質２次元の紙面に描画することは、元来不可能である。
また、例えば、稜辺ＳＢ1(稜線Ｒ1)は3つ超平面Π2、Π3、Π4によって形成され実質1次元の構造として捉えられている。稜辺ＳＢ4(稜線Ｒ4)は3つ超平面Π2、Π3、Π4によって形成され実質1次元の構造として捉えられている。こうして、実質２次元の面面ＳＢ4Ｂ1が形成されている。尚、3次元のピラミッド錐の場合とは異なり、4次元以上のピラミッド錐(ピラミッド錐体)の場合は、面ＳＢ1Ｂ2、面ＳＢ2Ｂ3、面ＳＢ3Ｂ4、面ＳＢ4Ｂ1等の実質２次元の面と、法線ベクトルn1,n2,n3,,n4との関係を(図11に描画したように)描くことは、最早困難である。逆格子ベクトルri,(i=1,・・・,4)の軸線方向が稜線Ｒ1、Ｒ2、Ｒ3、Ｒ4の何れかの方向と一致することは言える。また、前述の通り、該4次元のピラミッド錐体の底面も実質２次元の面として捉えられている。図12では、底面の多角形Ｂ1Ｂ2Ｂ3Ｂ4は凸多角形の場合として描かれているが、何時も、このように描くことができる訳ではない。該4次元のピラミッド錐体の頂点はＳが、方程式系（連立方程式(15)で4元4次の場合）の解頂点[線型計画問題としての]であるためには、該4次元のピラミッド錐体は凸錐でなければならず、実質２次元の面内で捉えられた底面多角形は凸多角形でなければならない。ここでの4次元のピラミッド錐体の議論は、高次元のピラミッド錐体の議論として、敷衍可能である。
【００９４】
図13(a)及び図13(b)は、本発明の観点により、超平面の交叉列が形成する部分空間への、原点よりの最短距離点到達手法を説明する図である。数理記法及び数理工学的原理に関連して、高次元多面体頂点座標の計算の説明ところで、既に記述した。ここで、補足する。
前述では、本発明の観点から、数学的帰納法の流儀に従い、超平面Π1,Π2の交叉から始めて、段階的に超平面を追加して都度の交叉、即ち、Π1∩Π2∩・・・∩Πj,(j=2からnまで)の交叉空間における、原点Ｏからの最短距離点Ｓjが求まることを述べた。ここで、より詳しく、説明する。
【００９５】
図13(a)は、本発明の観点により、3次元の空間において、平面Π1,Π2の交叉空間(Π1∩Π2)が別の平面Π3と交差して、共通集合(Π1∩Π2∩Π3)を形成する様子を示す。図13(a)において、斜交軸ベクトル基底系{n1,n2,n3}があり、平面Π1、Π2、Π3は、それぞれ、
Πi(ｘ)={ｘ｜<ni,x>=pi},(i=1,2,3)
なる集合である。平面Π1,Π2の交叉空間(Π1∩Π2)は、3次元より2次元低い次元(即ち1次元)の、該3次元の空間内の部分空間(該3次元空間の原点は含まないが、商空間としての該3次元空間の部分空間)である。点Ｓ1は原点Ｏから平面Π1に下ろした垂線の足であり、該点Ｓ1から平面Π2に下ろした垂線の足がＦ2である。また、ベクトルn1及びn2の両者が張る実質2次元断面で該点Ｓ1を通過しn1軸に直交する方向の直線が、平面Π2を貫通する点をＳ2とする。図10の例と同様に、n1,n2,p1,p2から、点Ｆ2、点Ｓ2の該3次元空間での座標は求めることができる。ここで、距離(Ｓ1Ｆ2)をdd2として、ベクトル(Ｓ1Ｆ2)はdd2・n2であり、距離(ＯＳ2)をd2とし、ベクトル(ＯＳ2)をd2・w2として(つまり原点Ｏから点Ｓ2に向かっての単位ベクトルをw2としている)、dd2,d2,及びw2は既に得られている。
また、(点Ｓ2を通過して)ベクトルn1及びn2の両者が張る実質2次元断面に直交する、単位ベクトル(v2とする)は、シュミットの直交化法の流儀で計算可能なことは、前述した。また、ここで、点Ｓ2を通過して、ベクトル(ＯＳ2)つまりd2・w2に直交する2次元の平面をW2とすると、集合記号を用いて、
W2(x)={ｘ｜<w2,x>=d2}
である。この2次元の平面W2は、該3次元空間の商空間としての部分空間(該3次元空間の原点は含まないが)であり、平面Π1,Π2の交叉空間(Π1∩Π2)を内包している。更に、交叉空間(Π1∩Π2)は、点Ｓ2を通過してベクトルv2の方向に置かれた、実質1次元の直線を含んでいる。該実質1次元の直線上の、原点Ｏよりの最短距離はd2であり、またW2への原点Ｏからの最短距離もd2であり、両者は一致している。従って、交叉空間(Π1∩Π2)への、原点Ｏからの最短距離もd2である。もし、交叉空間(Π1∩Π2)に、原点Ｏより最短距離の点が点Ｓ2以外にあると矛盾が生じる。本発明の観点では、交叉空間列の共通集合の中で、原点よりの最短距離を次々探索するので、このアルゴリズムを、本出願では、部分空間の最短距離点到達手法と呼ぶ。
【００９６】
さらに、図13(a)において、点Ｓ2を通過してベクトルv2の方向に置かれた、実質1次元の直線が平面Π3に貫通する点を点Ｓ3とし、点Ｓ2から平面Π3に下した垂線の足をＦ3とする。前述のように、3角形Ｓ2Ｆ3Ｓ3は直角3角形を形成する(実質2次元の面内の3角形として)。また、暫定的に座標原点を点Ｓ2に平行移動して、超平面Π3の方程式(式(152)が該当)を書き換えれば(ここもヘッセ標準形で)、垂線距離(Ｓ2Ｆ3)は求まる。ここでベクトル(Ｓ2Ｆ3)はn3軸と平行である。この垂線距離(Ｓ2Ｆ3)をdd3として、ベクトル(Ｓ2Ｆ3)はdd3・n3であり、線分(Ｓ2Ｆ3)と線分(Ｓ2Ｓ3)との交角も内積<n3,v2>の計算を介して求めることができる。したがって、ベクトル(Ｓ2Ｓ3)が計算され、点Ｓ2の座標は前段で既知であるので、点Ｓ3の該3次元空間での座標も知れる。こうして、ベクトル(ＯＳ3)をd3・w3として(つまり原点Ｏから点Ｓ3に向かっての単位ベクトルをw3としている)、d3,及びw3が知れる。また、ここで、点Ｓ3を通過して、ベクトル(ＯＳ3)つまりd3・w3に直交する2次元の平面をW3とすると、集合記号を用いて、
W3(x)={ｘ｜<w3,x>=d3}
である。当然のことながら、点Ｓ3は実質0次元の点である。これは、該点Ｓ3が3次元の空間の中の、平面Π1、Π2、Π3の交差空間だからと言うよりは、該点Ｓ3が実質1次元の直線Ｓ2Ｓ3及び実質1次元の直線Ｆ3Ｓ3の交点だからと考えた方が分かり易い。ここも、本発明の観点の一つである、前記最短距離探査手法を理解し易くなる。さらに、ここで、該最短距離探査手法の数学的帰納法的手法を分り易くするために、実質0次元の点Ｓ3が平面Π1、Π2、Π3の交差空間の点であることを、別角度から見ておく。該点Ｓ3は直線Ｓ2Ｓ3上の点であるから、交叉空間(Π1∩Π2)に含まれる。一方、該点Ｓ3は直線Ｆ3Ｓ3上の点であるから、平面Π3にも含まれている。従って、該点Ｓ3は平面Π1、Π2、Π3のすべてに含まれている。こうして、
(点Ｓ3)⊂(Π1∩Π2∩Π3)
なる関係が成立する。ここでは、3次元の空間を前提として考えているので、部分空間(Π1∩Π2∩Π3)の次元も0次元であり、実は、(点Ｓ3)＝(Π1∩Π2∩Π3)である。
また、部分空間としての(点Ｓ3)も部分空間(Π1∩Π2∩Π3)も部分空間W3も点Ｓ3を通過する、商空間としての部分空間(該3次元の空間から見ると厚みやボリュームのない部分空間)である。ここで、部分空間(Π1∩Π2∩Π3)の次元は部分空間W3の次元より低い。従って、
(点Ｓ3)⊂(Π1∩Π2∩Π3)⊂W3
である。該3次元の空間の原点Ｏから、部分空間としての(点Ｓ3)への最短距離はd3であり、原点Ｏから、部分空間W3への最短距離もd3であり、両者は一致する。従って、交叉空間(Π1∩Π2∩Π3)への、原点Ｏからの最短距離もd3である。
【００９７】
図13(b)は本発明の観点により、n次元の空間において、(n-1)次元のj個の超平面Π1、Π2、Π3、・・・、Πjの交叉空間(Π1∩Π2∩・・・∩Πj)が別の(n-1)次元の超平面Πj+1と交差して、共通集合(Π1∩Π2∩・・・∩Πj∩Πj+1)を形成する様子を示す。該n次元の空間において、斜交軸ベクトル基底系{n1,n2,n3,・・・,ni,・・・,nn-1,nn}の中から、(n-1)次元のj個の斜交軸ベクトルベクトルni,(i=1,・・・,j)並びに垂線距離pi,(i=1,・・・,j)が取り上げられていて、対応する超平面Πi,(i=1,・・・,j)は、それぞれ、
Πi(ｘ)={ｘ｜<ni,x>=pi},(i=1,・・・,j)
である。数学的帰納法の流儀に従い、該n次元の空間において、(n-1)次元の該j個の超平面Π1、Π2、Π3、・・・、Πjの交叉空間(Π1∩Π2∩・・・∩Πj)に関して、(該n次元の空間の)原点Ｏよりの最短距離点Ｓjの座標は決定されているものとする。従って、ベクトル(ＯＳj)をdj・wjとして(つまり原点Ｏから点Ｓjに向かっての単位ベクトルをwjとしている)、dj及びwjは既に得られているとする。
図13(b)に示すように、j個の超平面Πi,(i=1,・・・,j)に続く、(j+1)番目の超平面Πj+1が取り上げられ、Πj+1も
Πi(ｘ)={ｘ｜<ni,x>=pi},(i=j+1)
なる集合である。
図13(b)において、(点Ｓjを通過して)ベクトルn1,n2,n3,・・・,njに直交する、単位ベクトル(vjとする)は、シュミットの直交化法の流儀で計算可能なことは、前述した。また、ここで、点Ｓjを通過して、ベクトル(ＯＳj)つまりdj・wjに直交する(n-1)次元の超平面をWjとすると、集合記号を用いて、
Wj(x)={ｘ｜<wj,x>=dj}
である。また、点Ｓjを通過して、ベクトルvj方向に置かれた直線が超平面Πj+1を貫通する点をＳj+1とし、点Ｓjから超平面Πj+1に下した垂線の足をＦj+1とする。図13(a)の議論と同様に、3角形ＳjＦj+1Ｓj+1は直角三角形を形成し、角度ＳjＦj+1Ｓj+1は直角である。また、角度Ｓj+1ＳjＦj+1は内積<vj,nj+1>を算定して知れる。こうして、ベクトル(ＳjＳj+1)が求められ、ベクトル(ＯＳj+1)が得られ、点Ｓj+1の座標(前記n次元の空間における)が確定する。
尚、交叉空間(Π1∩Π2∩・・・∩Πj)において、点Ｓjが原点Ｏから最短の距離にあることに言及する。点Ｓjを通過して、ベクトルvj方向に置かれた直線をLj,交叉空間(Π1∩Π2∩・・・∩Πj)をVjとする。直線Ljも交叉空間Vjも超平面をWjも、点Ｓjを通過する、前記n次元空間の部分空間(該n次元空間の原点Ｏは含まない商空間としての)である。直線Ljの次元は1次元、交叉空間Vjの次元は(n-j)次元、超平面Wjの次元は(n-j)次元であり、
直線Lj⊂交叉空間Vj⊂超平面Wj
なる抱合関係がある。点Ｓjは直線Ljの中で原点Ｏから最短距離にあり、また、超平面Wj中で最短距離にある。両者の距離は共に、djあり一致している。従って、点Ｓjは直線交叉空間Vjの中でも、原点Ｏから最短距離ある点で、その距離はdjである。
【００９８】
上記の本発明の観点による、数学的帰納法的な流儀に基づく最短距離点到達手法においては、n次元の空間において、(n-1)次元のj個の超平面Π1、Π2、Π3、・・・、Πjの交叉空間(Π1∩Π2∩・・・∩Πj)即ち部分空間Vjが別の(n-1)次元の超平面Πj+1と交差して、共通集合(Π1∩Π2∩・・・∩Πj∩Πj+1)即ち部分空間Vj+1を形成するとき、該部分空間の列Vi,(i=1,・・・,j)に対応して、前記最短距離点の点列Ｓi,(i=1,・・・,j)が得られ、最終的に交叉空間(Π1∩Π2∩・・・∩Πn)即ち、方程式系(15)の解ｘ(拘束条件n個の組が形成するピラミッド錐の頂点)に到達できることを示した。
この本発明の観点も重要且つ有用である。当該の線型計画問題において、目的関数のn個のパラメータに関するm個の線型拘束条件式が課せられている(ここでm≧nである)。このとき、正解ｘを形成する、n個の線型拘束条件の組がm個の線型拘束条件の中に存在するならば、mCn個の組合せ数のピラミット錐なかで、該標高の最も小さくなるピラミット錐(頂点)を決めるのにmCn個の組合せ数のピラミット錐をすべて、吟味する必要はない。この点に関しては、数理記法及び数理工学的原理に関連して、部分空間の最短距離点到達手法及び部分空間の最短距離点標高評価手法の所で記述した。
図4において、解頂点は点(jk)であるが、例えば、解頂点候補を点(lm)を出発点として、次の解頂点候補点(kl)を経由して、解頂点(jk)に到達することができる。出発点は、拘束条件全体が形成する凸多面体(凸多角形)の頂点でなくとも、その凸多面体(凸多角形)近傍の頂点(lm)としても、解頂点(jk)に到達することができる。さらに、本発明による、部分空間の最短距離点到達手法及び部分空間の最短距離点標高評価手法は、図4の2次元の場合に限定されない。また、本発明では、不要な拘束条件を予め、取り除き、且つ、解頂点候補構成のピラミッド錘を絞り込むことができるので、真の解頂点を算定する上で、計算の効率と質が向上する。
【００９９】
図14(a)及び14(b)は、本発明の観点が応用する、多角形が凸領域を形成するか否かの判定法の例を説明する図である。この点については、数理記法及び数理工学的原理に関連して、高次元ピラミッド錐のの凸性説明ところで、既に記述した。ここで、若干補足する。まず、n次元の空間において、厚みのない、(n-1)次元の超平面のなかで、実質2次元の平面を如何に取り上げることができるかを説明する。例えば、超平面
Πi(ｘ)={ｘ｜<ni,x>=pi}
の中に(ここで、niはn1,n2とは異なるものとして置く)、n1,niと直交する、実質1次元であるベクトルvαを取ることができる。これは図13(a)及び図13(b)の議論と同様である。また、
同様に、該超平面Πiの中にn2,niと直交する、実質1次元であるベクトルvβを取ることができる。ベクトルvα,vβとは該超平面Πiの中に、実質2次元の平面が張られている。これら二つの斜交ベクトルvα,vβから直交座標軸を容易に形成可能である。ピラミッド錐の頂点を通過する稜線が、この張られた2次元の平面を、貫通する点も容易に計算可能で、ピラミッド錐の底面多角形を該2次元の平面の中で描画することが可能である。その底面多角形がn多角形のとき、それが凸多角形を形成するか否かの判定法を、図14(a)及び14(b)は示している。
【０１００】
図15は、本発明の観点により、凸高次元ピラミッド錐の頂点を通過する、nf軸方向の直線が、該ピラミッド錐内部を通過するか否かの判定条件を説明する。
例えば、斜交軸ベクトル基底系{n1,n2,n3,・・・,ni,・・・,nn-1,nn}のそれぞれが、n次元の空の原点Ｏを通過して、凸ピラミッド錐を形成して、目的関数に関するnf軸(これも原点Ｏを通過するとする)を囲んでいるいるとしよう。このとき、nf軸に直交して垂線距離がpfである超平面の中の2次元平面Wf2を考える。原点Ｏを通過する、ベクトルn1,n2,n3,・・・,ni,・・・,nn-1,nnの方向の直線は、該2次元平面Wf2を貫通し、該2次元平面Wf2とP1,P2,P3,・・・,Pi,・・・,Pn-1,Pnで交叉し、原点Ｏを通過するベクトルnfは点Pfで交叉しているものとする。該2次元平面Wf2内に形成された、多角形P1P2P3・・・Pi・・・Pn-1Pnが、図14(a)の判定法で、凸n多角形であると判定される場合は、該ピラミッド錐が凸頂点を形成していて、該ピラミッド錐は凸ピラミッド錐であるとみなしてよい。
さらに、凸n多角形P1P2P3・・・Pi・・・Pn-1Pnが点Pfを囲んでいる場合は、ベクトルn1,n2,n3,・・・,ni,・・・,nn-1,nnにより形成される該ピラミッド錐(既に凸であると判定された前提にたって)が、nf軸(これも原点Ｏを通過するとする)を囲んでいるいるとみなしてよい。図15はこのことについても説明している。つまり、多角形P1P2P3・・・Pnは、凸n多角形を形成していると判断されたとき、該凸n多角形が点Pfを囲んでいるか否かの判定手法について、図15は示している。該2次元平面Wf2の中で、2次元座標系をとることができるから、該点Pfを、該2次元平面Wf2の中の原点として、適当な2次元座標系を採る。さらに、P1,P2,P3,・・・,Pi,・・・,Pn-1,Pnを、2次元極座標で表すことができる。つまり、Pi,(i=1,・・・,n)の座標を点Pfを基準(原点)として、(ri,θi)のように書くことができる。図15の判定時に、P1P2P3・・・PnP1の点列は多角形内部を常に時計回りか反時計回りに見るように回っているので、θi,(i=1,・・・,n,n+1)は単調に増大若しくは減少しながら、360°進むか戻る。つまり、該凸n多角形が点Pfを囲んでいる場合は、θi,(i=1,・・・,n,n+1)が単調に増大若しくは減少しながら、点列Pi,(i=1,・・・,n,n+1)は元の点へもどる。一方、点Pfがn多角形P1P2P3・・・Pi・・・Pn-1Pnの外にある場合では、θi,(i=1,・・・,n,n+1)は360°未満の増加(減少)のあと、同じ角度だけ減少(増加)して点列Pi,(i=1,・・・,n,n+1)は元の点へもどる。上記のアルゴリズムを、コンピュータ判定手順として組み込むことは可能である。ここでは、凸n多角形P1P2P3・・・Pi・・・Pn-1Pnがある点Pfを囲んでいるか否かの判定法についての実施可能性を記述したものである。凸n多角形領域の内外部の判定を数学的に考慮して、別途の判定法を構築してもよいことは当然である。
【０１０１】
図16は、本発明の観点により、整数計画法問題に対処する技法を説明する図である。図16では、2次元の例で説明を与えるが、まず、その前に高次元の場合の本発明によるコンセプトをレビューしておく。
本発明による線型計画問題解法では、ヘッセの標準形を用いて、拘束条件及び目的関数を書き改めた。即ち、
拘束条件      gi(ｘ)=<ni,x>≦pi      (i=1,・・・,m)
の下に、
目的関数      f(ｘ)=<nf,x>≦pf
を最大化させる問題へと書き直すことができることを利用している。ここで各pi及びpfは非負、未知実数ベクトルｘの次元はnで拘束条件数m以下である。なお、整数計画法問題では該線型計画問題での未知実数ベクトルｘが未知整数ベクトルであるという制約が課せられるものと、理解してもよい。従って、まず、未知ベクトルｘが実数ベクトルとしたまま、本発明による線型計画問題解法のコンセプトをレビューする。
目的関数を最大化させるベクトルｘは高次元凸ピラミッド錘の頂点ｘ(解頂点ｘとも呼んだ)を形成している。また、該解頂点が決定されたとは、それを決定する、n個の拘束条件(の線型方程式)
gpi(ｘ)=<npi,x>=ppi,  (pi=p1,・・・,pn)
が決まっている。また、該解頂点ｘにおいて、目的関数f(ｘ)は最大となり、超平面
Πf(ｘ)={ｘ｜<nf,x>=pf}
が、該ピラミッド錘に接している。尚、この超平面Πfも、前記のように、当該n次元空間において、(n-1)次元の超平面であり、当該n次元空間の中では厚みのない部分空間(商空間としての)であり、実質0次元の解頂点ｘを通過している。
また,超平面Πfに平行な超平面で,当該n次元空間の原点Ｏを通過する超平面をここで,
Πf0(ｘ)={ｘ｜<nf,x>=0}
とすると、超平面Πf及びΠf0は共に、nf軸に直交している。また、方向余弦ベクトルnpi,(pi=p1,・・・,pn)が形成する、斜交軸ベクトル基底系{np1,np2,npi,・・・,npi,・・・,np,n-1,npn}に対する、逆格子ベクトル系を{rp1,rp2,rpi,・・・,rpi,・・・,rp,n-1,rpn}とする。該解頂点ｘをを通過し、逆格子ベクトルrpi,(pi=p1,・・・,pn)の方向に置かれた、n本の直線が当該ピラミッド錘を形成する。
一方、当該n次元空間の原点Ｏを起点とする、方向余弦ベクトルnpi,(pi=p1,・・・,pn)の方向に置かれた,n本の直線が形成するピラミッド錘の内部を、該原点Ｏを起点とするnf軸方向の直線が通過する。つまり、原点Ｏを起点とする、方向余弦ベクトルnpi,(pi=p1,・・・,pn)の方向線が、上記超平面Πf(ｘ)内の実質2次元平面と交叉して形成するn多角形の内部を、原点Ｏを起点とする、方向余弦ベクトルnpfの方向の直線が通過すると考えてよい。
将に上記と光と陰の関係のように(双対的な議論として)、解頂点を起点とする、方向余弦ベクトルrpi,(pi=p1,・・・,pn)の方向に置かれた,n本の直線が形成するピラミッド錘の内部を、該解頂点を通過しnf軸方向と平行に置かれた直線が通過する。つまり、解頂点を起点とする、方向余弦ベクトルrpi,(pi=p1,・・・,pn)の方向線が、上記超平面Πf0(ｘ)内の実質2次元平面と交叉して形成するn多角形の内部を、該解頂点を通過しnf軸方向と平行に置かれた直線が通過すると考えてよい。
【０１０２】
本発明の観点により、整数計画法問題に対処する技法においては、実数ベクトルｘとして解かれた解頂点を構成するピラミッド内の整数格子点(高次元の整数格子点)の一つの格子点を確定する問題として、整数計画法問題を認識する。しかしながら、ピラミッド錘内部の多数存在する整数格子点の中で、解頂点に最も近い点が,当該の整数計画法問題の解としての整数ベクトルになるとは限らない。このため、分枝限定法(branch and bound method)や切除平面法(cutting plane method)等の手法が開発されてきたものの、整数計画法問題と対応する線型計画問題との間で、扱い方の脈絡は希薄になりがちであり、より統一性のある手法が期待されてきた。
より具体的に、本発明の観点では、上述の解頂点を形成する該ピラミッド錘に、底面を構成するように、該ピラミッド錘を適切な(n-1)次元の超平面でカットする。該ピラミッド錘の稜線は実質1次元の直線であるから、n本の稜線が該適切な(n-1)次元の超平面を、n個の点で貫通し、実質0次元のn個の点が確定できる。ここで、適切な(n-1)次元の超平面とは、例えば、上記の超平面Πf及びΠf0に平行な超平面が好ましいが、nf軸方向の直線に斜交する超平面であっても、該ピラミッド錘の底面を構成するものであってもよい。また、適切な(n-1)次元の超平面とは、該超平面内の実質2次元の平面であってもよい。
【０１０３】
上記のように、当該n次元空間にピラミッド錘体が形成され、解頂点と底面の頂点(角点)の計(n+1)個の点Qiの座標[qi1qi2・・・qin]t,(i=1,・・・,n,n+1)が確定する。第j番目(j=1,・・・,n)の要素(ベクトル成分)qij,(j=1,・・・,n)につき、全てのi,(i=1,・・・,n,n+1)に亘っての比較即ち(n+1)個の点すべてに亘っての比較を行い、実数としての最大値MAX(j)及び最小値MIN(j),(j=1,・・・,n)が確定する。つまり、各j番目の要素として許容される整数の範囲が確定する。こうして、当該n次元空間の該ピラミッド錐体の内部に存在する、有限個の格子点がすべてきまる。該有限個の格子点の各々から超平面Πfへ下ろした垂線距離は、求めることが可能であり、求められた該有限個の垂線距離のうち最小となるものが、当該整数計画法問題の目的関数を最大化させる整数格子点であると考えてよい。
なお,有限個の格子点の個数を抑制して計算をさらに効率化したい場合は、ピラミッド錘体の底面を、解頂点に近づけたものとすればよい。ピラミッド錘体の底面を、解頂点に近づけたものとする際、少なくも1個の格子点が該ピラミッド錘体の内部に残るようにすればよい。例えば、特に、該底面の超平面Πf0dを、超平面Πf及びΠf0の間に平行に取り、Πf0d(ｘ)={ｘ｜<nf,x>=pf0d=pf-η≧0}のようにして、超平面Πf及びΠf0dの平行面間距離をηとなし、該平行面間距離ηを短くすれば、該ピラミッド錘体の内部に残る格子点数を減らすことができる。特に、該平行面間距離ηをSQRT(n)となるようにすれば(ここに、nは当該ユークリッド空間の次元数)、少なくも1個の格子点が該ピラミッド錘体の内部に残るようにするようなことも可能である。このようにすれば、格子点の各々から超平面Πfへ下ろした垂線距離をもとめる場合の数を圧縮できるので、計算の効率をさらに向上することが可能となる。
【０１０４】
図15は、2次元の例で、本発明の観点により、整数計画法問題に対処する技法を説明する。図15において、該ピラミッド錘体は3角形、解頂点は該3角形の頂点、底面は該3角形の底辺として描画された例である。前記Πf及びΠf0の記号は超平面を表す記号として定義されたが、図15においては、3角形(2次元ピラミッド錐としての)の底辺(底面)あるいは該底辺に平行な、原点を通過する直線の意味で使用されている。図15から、分るようにピラミッド錘体としての3角形の底辺(底面)を、解頂点に近づけて、ピラミッド錘体内の格子点の数を減ずることが可能となる。こうして、該ピラミッド錘体の内部に残る、有限個の格子点の各々から、超平面Πfへ下ろした垂線距離の計算を行う際の手間(計算時間)を抑制することができる。このように整数計画法問題の処理と対応する線型計画問題解法との脈絡も従来に比べ、確実に明確化する。線型計画法で解かれた解頂点とそれを構成するピラミッド錘体を用いて、線型計画問題の解を示すことが可能となる。
【産業上の利用可能性】
【０１０５】
本発明は、コンピュータを利用し、線型計画問題或いはそれと連動する整数計画問題を扱い、物理的乃至は経済的資源の配分を行う方法・装置にあって、ヘッセの標準形表現を用いて、複数の等式拘束条件が形成する高次元空間の凸多面体が囲む許容定義領域の中で目的関数を最大化させる問題へと書き直し、該領域を該空間の半空間領域で扱い、該半空間領域の形成に寄与せぬ拘束条件を除去し、また、不要な拘束条件を除去し、複数の等式拘束条件が形成する高次元空間のピラミッド錐の解頂点形成条件を明確化し、解適合性判定演算時間を短縮し、適合解頂点絞り込み乃至は該解頂点への到達時間の高速化を図り、大規模・高速演算の応用範囲を拡大し、更には、整数計画問題解法への連動応用性を確保した。
よって、本発明は、物理的乃至は経済的資源の配分を行う問題解決を求める、産業上の要求に応えて、有益に利用可能である。
【図１】
2012203710.tif 000005
【図２】
2012203710.tif 000006
【図３】
2012203710.tif 000007
【図４】
2012203710.tif 000008
【図５】
2012203710.tif 000009
【図６】
2012203710.tif 000010
【図７】
2012203710.tif 000011
【図８】
2012203710.tif 000012
【図９】
2012203710.tif 000013
【図１０】
2012203710.tif 000014
【図１１】
2012203710.tif 000015
【図１２】
2012203710.tif 000016
【図１３】
2012203710.tif 000017
【図１４】
2012203710.tif 000018
【図１５】
2012203710.tif 000019
【図１６】
2012203710.tif 000020
【図１７】
2012203710.tif 000021
【図１８】
2012203710.tif 000022
【図１９】
2012203710.tif 000023
【図２０】
2012203710.tif 000024