シンプレックス法

シンプレックス法は、目的関数と制約条件が一次式で表される線形計画問題について、実行可能領域を構成する頂点から隣接頂点へ移り、目的関数を改善しながら最適解を求める代表的な解法です。

■ 試験で押さえるポイント

• 意思決定変数、最大化又は最小化する目的関数、資源制約、非負条件を定式化し、不等式へスラック変数などを加えて等式へ変換します。

• シンプレックス表で基底変数を入れ替え、目的関数が改善するピボット操作を反復し、これ以上改善できなければ最適と判定します。

• 線形計画の凸な実行可能領域では、有限最適解があれば少なくとも一つの頂点にあります。実行不能、非有界、複数最適の場合もあります。

• 変数が整数でなければならない問題に通常のシンプレックス法だけを使うと小数解になることがあり、整数計画法などが必要です。

■ 選択肢での判断ポイント

図で解ける2変数問題では、制約直線の交点である各頂点の目的関数値を比べると原理を確認できます。非線形問題の一般解法ではありません。

例: $3x+2y$を最大化し、$x+y\le4$、$x\le2$、$x,y\ge0$なら、頂点(0,0),(2,0),(2,2),(0,4)の値は0,6,10,8なので、最適解は$x=2$、$y=2$、最大値10です。