|
線形計画法（LP : Linear Programming）とは、制約式（制約条件）と呼ばれるいくつかの1次式を満たす変数の値の中で、
目的関数と呼ばれる1次関数を最大化または最小化する値を求める方法である。
この目的式の最大値、及びそれを実現する変数を求める問題が線形計画問題である。
また、線形計画問題を解く手法の一つとしてシンプレックス法がある。
解き方の説明（シンプレックス法）
問題
ある会社が、A、Bという製品を売り出している。 それらを製作するための材料はプラスチック、アルミ、ゴムである。
それぞれ１個を製作するために必要な材料の量は下の表のとおりである。
| 製品材料 |
プラスチック |
アルミ |
ゴム |
単価 |
| A |
1ｋｇ |
1ｋｇ |
3ｋｇ |
２万円 |
| B |
2ｋｇ |
1ｋｇ |
1ｋｇ |
３万円 |
| 材料の量 |
14ｋｇ |
8ｋｇ |
18ｋｇ |
|
このとき、手持ちの材料の範囲内で売上高を最大にするためには、A、Bをそれぞれいくつ作ったらよいか？
連立法定式
最大値 ：２０Ｘ１ ＋ ３０Ｘ２
制約条件：Ｘ１ ＋ ２Ｘ２ ≦ ８００
３Ｘ１ ＋ ４Ｘ２ ≦ １８００
３Ｘ１ ＋ Ｘ２ ≦ １５００ Ｘ１、Ｘ２ ≧ ０
シンプレックス法を適用するための準備
与えられた線形計画問題を正規形に変形する。正規形に変形された問題の目的関数をZとおく。
最大値：Ｚ
制約条件： Ｘ１ ＋ ２Ｘ２ ＋ Ｓ１ ＝ ８００
３Ｘ１ ＋ ４Ｘ２ ＋ Ｓ２ ＝ １８００
３Ｘ１ ＋ Ｘ２ ＋ Ｓ３ ＝ １５００
Ｚ － ２０Ｘ１ － ３０Ｘ２ ＝ ０ Ｘ１、Ｘ２ 、Ｓ１、Ｓ２、Ｓ３ ≧ ０
シンプレックス法の手順
ステップ１：シンプレックス表を作成する。
| 基底変数 |
Ｚ |
Ｘ１ |
Ｘ２ |
Ｓ１ |
Ｓ２ |
Ｓ３ |
定数項 |
| Ｓ１ |
０ |
１ |
２ |
１ |
０ |
０ |
８００ |
| Ｓ２ |
０ |
３ |
４ |
０ |
１ |
０ |
１８００ |
| Ｓ３ |
０ |
３ |
１ |
０ |
０ |
１ |
１５００ |
| Ｚ |
１ |
－２０ |
－３０ |
０ |
０ |
０ |
０ |
ステップ２：ピポットを計算する。
-
Ｚ行で最も小さい負の値を持つ列に対応する非基底変数を新たに基底に入れる変数に選ぶ。（Ｘ２列）
-
各行（Ｚの行は除く）において（定数項の値）÷（新たに基底に入れることになった変数の係数）を計算する。
その値を増加限界と呼ぶ。
各行の増加限界の中で非負で最小の値を取った行に対応する変数を追い出す変数に決める。（Ｓ１行）
-
新たに基底に加える変数の列と基底から追い出す変数の行との交点の係数をピボットにする。
ピボット（Ｓ１行、Ｘ２列）ピボットを中心に掃き出しを行う。
| 基底変数 |
Ｚ |
Ｘ１ |
Ｘ２ |
Ｓ１ |
Ｓ２ |
Ｓ３ |
定数項 |
増加限界 |
| Ｓ１ |
０ |
１ |
２ |
１ |
０ |
０ |
８００ |
４００ |
| Ｓ２ |
０ |
３ |
４ |
０ |
１ |
０ |
１８００ |
４５０ |
| Ｓ３ |
０ |
３ |
１ |
０ |
０ |
１ |
１５００ |
１５００ |
| Ｚ |
１ |
－２０ |
－３０ |
０ |
０ |
０ |
０ |
|
ステップ３：連立方程式の解を解く
-
ピボットが1になるように，ピボットのある行のすべての数字をピボットの数字で割る。
-
各行からピボットの行を何倍かして引くことにより、ピボット列の数字がピボット以外０になるようにする。
| 基底変数 |
Ｚ |
Ｘ１ |
Ｘ２ |
Ｓ１ |
Ｓ２ |
Ｓ３ |
定数項 |
計算 |
| Ｓ１ |
０ |
０．５ |
１ |
０．５ |
０ |
０ |
４００ |
（ピポット行）÷２ |
| Ｓ２ |
０ |
１ |
０ |
－２ |
１ |
０ |
２００ |
Ｓ２行－（ピポット行）Ｘ４ |
| Ｓ３ |
０ |
２．５ |
０ |
－０．５ |
０ |
１ |
１１００ |
Ｓ３行－（ピポット行）Ｘ４ |
| Ｚ |
１ |
－５ |
０ |
１５ |
０ |
０ |
１２０００ |
Ｚ行－（ピポット行）Ｘ（－３０） |
ステップ４：連立方程式の解を評価する。
現在の基底変数から得られた連立方程式の解が最適かどうか吟味する。
Zの行を見るとｘ1の列に負の値がある．よって，現在得られている解は最適ではない。
ステップ3
より良い目的関数値を持つ解を見つけるように基底変数と非基底変数の組合せを変更する。
ステップ２に戻り、ピポットを計算する。計算により、ピボットは計算により（Ｓ２行、Ｘ１列）として、ピボットを中心に掃き出しを行う。
| 基底変数 |
Ｚ |
Ｘ１ |
Ｘ２ |
Ｓ１ |
Ｓ２ |
Ｓ３ |
定数項 |
増加限界 |
| Ｓ１ |
０ |
０．５ |
１ |
０．５ |
０ |
０ |
４００ |
８００ |
| Ｓ２ |
０ |
１ |
０ |
－２ |
１ |
０ |
２００ |
２００ |
| Ｓ３ |
０ |
２．５ |
０ |
－０．５ |
０ |
１ |
１１００ |
４４０ |
| Ｚ |
１ |
－５ |
０ |
１５ |
０ |
０ |
１２０００ |
|
ステップ５：連立方程式の解を解く（ステップ３と同様に行う）
| 基底変数 |
Ｚ |
Ｘ１ |
Ｘ２ |
Ｓ１ |
Ｓ２ |
Ｓ３ |
定数項 |
増加限界 |
| Ｓ１ |
０ |
０ |
１ |
１．５ |
－０．５ |
０ |
３００ |
Ｓ１行ー（ピポット行）Ｘ０．５ |
| Ｓ２ |
０ |
１ |
０ |
－２ |
１ |
０ |
２００ |
Ｓ２行÷１ |
| Ｓ３ |
０ |
０ |
０ |
４．５ |
－２．５ |
１ |
６００ |
Ｓ３行ー（ピポット行）Ｘ２．５ |
| Ｚ |
１ |
０ |
０ |
５ |
５ |
０ |
１３０００ |
Ｚ行ー（ピポット行）Ｘ（－５） |
ステップ６：連立方程式の解を評価する。
Zの行を見ると負の値はない．
つまり，これ以上基底を変更してもより良い目的関数値は得られない.よって，現在得られている解が最適である。
※線形計画の問題を解く方法としてMicroSoft Excelのソルバーを使って解く方法があります。参考にして下さい。
Excelで線形計画の問題を解く方法
|