2段階線形計画問題に対する2-レベル分割解法
スポンサーリンク
概要
- 論文の詳細を見る
連結変数・連結行列によってつな二がれた2つの部分線形計画問題から構成される計画問題を、(1)連結変数の値を1つの暫定値に固定することによって2つの部分計画問題に分離し、それぞれを最適化する、(2)それらの結果を用いて連結変数値をさらに良い方向に調整する、という2一レベル・プロセスによる分割解法が提示され、解法の有限性の証明と数値計算経験の結果が示される。この解法は冬期問計画に対する巣作り型逐次分割アプローチ〔3〕のために開発されたもので、次のような特徴をもつ:(1)たとえば繰越在庫量のような、連結変数の初期値として経験、上あるいは環境の概略的な状況把握から"良好"と思われる傾向値を与えることが容易である。(2)2つの部分計画問題の行列構造および目的関数は、計算過程で不変に保たれる。(3)計算経験によると、全体最適化のために必要な調整回数(サイクル数)が、列生成を伴うDantzig&Wo1fe型分割法に比べて著るしく少くてすみ、1〜3回程度である。(4)部分計画の実行可能解を改善していくという方法をとるので(3)の特薇と併せて途中打切りの方法が有効に利用できる。(5)2つの部分計画の目的関数値の問に明示的な形では与えられないような効用関数が存在する場合に、対話的最適化の方法〔7〕をこの解法の中に取り入れることが容易である。解法の考え方は、Bea1e〔4〕に類似するが、計算プロセスは、部分問題と調整問題を解くことの2つの段階に完全分離されるため、計算手続はBea1eの方法よりも系統的でプログラム化が容易、しかも計算実験結果によると調整回数(サイクル数)、CPU計算時間の両面においても少なくなることが示された。生産計画などの冬期問計画を行う場合には計画対象期間の終端の条件、たとえば期末在庫量次ど、をある前提にもとづいて一定値に設定してしまうのが普通である。これは本来のモデルを縮少化する必要からのスプリットが狙いの場合もあれば、他のマクロ計画との単なる境界条件として与えられる場合もあろう。この解法の特徴を利用すると、この終端条件と連結している次の計画対象期問に対する(イ)同位レベルにある同種の計画モデル、あるいは(口)もっと高位のレベルにあるマクロ計画モデル、と当該計画モデルを連結し、全体的にさらに望ましい方向に計画を改善することが容易となる。この場合に、2つの計画対象期間の中にある不確実さの違いから全体的な計画評価関数が2つの計画の評価値の単純和としては表わせない場合に特徴(5)が有効である。また(ロ)の場合のように異った組織単位に属している2つの計画を組織内コンピュータ・ネットワークを利用して仮定条件を再調整する場合には、特徴(2)(3)(4)が有効に働くであろう。