シンプレックス法解き方

シンプレックス法をシンプレックス表で解く方法を勉強しており、
http://zeus.mech.kyushu-u.ac.jp/~tsuji/java_edu/ …
このサイトを参考にして解いていますが、
(2)その交差する要素2をピボットとして掃き出しを行う。その後同様に最上段の最小なもの-1/2があるｘ１の列を列選択し、最小な1/(1/2)=2がある行を行選択する。
と言うところの表のx3の行はどうやって計算して出されているのでしょうか？
計算式など教えていただけると幸いです。
ご教授よろしくお願いします。

No.2 回答者： queuerev2 回答日時： 2012/11/15 12:34

No.1です。

文章ばかりでわかりにくかったようで失礼致しました。
今回は式中心にして、(1)から(2)へ変換する掃き出しの部分のみを説明します。

１．掃き出し法について
計算の説明の前に、質問者様は掃き出し法をご存知でしょうか。
連立方程式を解く方法としてよく使われるもので、おおざっぱに言えば今回も使用している掃き出しの手順を繰り返すものです。
ただ、今回のシンプレックス表を使うシンプレックス法では、ピボットの選び方、基底変数の把握、計算終了の判定が通常の連立方程式と異なるようです。

２．(1)から(2)への掃き出しの説明
２－１．初期状態
表(1)ですが、初期状態からピボットを選択しただけの状態です
念のため初期のシンプレックス表を示します。
基底変数　ｘ１　　ｘ２　　ｘ３　　ｘ４　　ｘ５　定数項
Ｚ　　　　－２　　－３　　　０　　　０　　　０　　　０
ｘ２　　　　１　　　２　　　１　　　０　　　０　　１４
ｘ４　　　　１　　　１　　　０　　　１　　　０　　　８
ｘ５　　　　３　　　１　　　０　　　０　　　１　　１８

ここで列を選び定数項/列要素を比較した結果、２行目のｘ２の項である２がピボットになります。
２行目の式は以下の式１のとおりと初期状態のままです。
ｘ１＋２・ｘ２＋ｘ３　＝　１４　　　　式１
（式の書き方はこのようにしますがよろしいでしょうか）

２－２．第１段階（ピボットのある行の式）
掃き出しの第１段階として、ピボットを１にします。方法は、式１の両辺をピボットで割ります。
（ｘ１＋２・ｘ２＋ｘ３）／２　＝　１４／２
１／２・ｘ１＋ｘ２＋１／２・ｘ３　＝　７　　　　式２
なお、基底変数はｘ２になります。（理由ですが、項が１になったからというより、ピボットだからと考えた方がよさそうです。）

式２によって表の２行目は表(2)の値に更新され、他の行は表(1)のままとなります。
つまり、表は以下のようになります。
基底変数　ｘ１　　ｘ２　　ｘ３　　ｘ４　　ｘ５　定数項
Ｚ　　　　－２　　－３　　　０　　　０　　　０　　　０
ｘ２　　　１／２　　１　　１／２　　０　　　０　　　７
ｘ４　　　　１　　　１　　　０　　　１　　　０　　　８
ｘ５　　　　３　　　１　　　０　　　０　　　１　　１８

（質問者様がお持ちの疑問はこのあたりでしょうか）

２－３．第２段階その１（１行目の式）
掃き出しの第２段階として、他の行のｘ２の項を０にします。
方法は、連立方程式の加減法と同じです。
つまり、他の行のｘ２の項を２行目の式（式２）の両辺に掛け、それを引きます。
（１行目のｘ２の項は－３なので－３を掛けます）
１行目の場合を示すと以下のようになります。
１行目のｘ２の項は－３なので－３を掛けます
（１／２・ｘ１＋ｘ２＋１／２・ｘ３）・（－３）　＝　７・（－３）
－３／２・ｘ１－３・ｘ２－３／２・ｘ３　＝　－２１　　　　式３

式３を１行目の式から引きます。
　　Ｚ　　－２・ｘ１－３・ｘ２　　　　　　　　＝　　　０　　（１行目の式）
－）　－３／２・ｘ１－３・ｘ２－３／２・ｘ３　＝　－２１　　　（式３）
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
　　Ｚ－１／２・ｘ１　　　　　＋３／２・ｘ３　＝　　２１　　　　式４

式４により表の１行目が表(2)の値に更新されます。
基底変数　ｘ１　　ｘ２　　ｘ３　　ｘ４　　ｘ５　定数項
Ｚ　　　－１／２　　０　　３／２　　０　　　０　　２１
ｘ２　　　１／２　　１　　１／２　　０　　　０　　　７
ｘ４　　　　１　　　１　　　０　　　１　　　０　　　８
ｘ５　　　　３　　　１　　　０　　　０　　　１　　１８

２－４．第２段階その２（３行目、４行目の式）
同様に３行目、４行目についてもｘ２の項を０にします。
（式２に掛ける値はどちらも１です）
これですべての項が表(2)の値に更新されます。
結果のみ（というか単に表(2)から定数項/列要素を除いたものですが）を示します。
基底変数　ｘ１　　ｘ２　　ｘ３　　ｘ４　　ｘ５　定数項
Ｚ　　　－１／２　　０　　３／２　　０　　　０　　２１
ｘ２　　　１／２　　１　　１／２　　０　　　０　　　７
ｘ４　　　１／２　　０　－１／２　　１　　　０　　　１
ｘ５　　　５／２　　０　－１／２　　０　　　１　　１１

以上で１回目の掃き出しは完了です。


３．次の処理
この状態ではまだ終了条件になっていません。
そこでこのあと列選択、定数項/列要素の比較を行い次のピボットを選びます。


いかがでしょうか。ご質問や他の説明のご希望等ありましたら補足いただければと思います。

No.1 回答者： queuerev2 回答日時： 2012/11/13 23:35

シンプレックス法はまったくわからないのですが、リンク先の内容の数値だけを追ってみました。

x3の行というのは行を基底変数で区別しているのですが、基底変数は変わるので２行目と呼ぶことにします。（リンク先の丸付き数字は質問者様にならいかっこ付き数字にします）


(1)でx2の列が最大である２行目を選んでいますが、その行・列の交差するところの要素が2であるので、それで２行目の全要素を割っています。その結果x2の要素が1になり同じ行の他の要素は1以外になるので、基底変数がx3からx2に変わっているのだと思います。
次に、他の行のx2の要素が0になるように、他の行に対して２行目を加算又は減算します。（加算又は減算は、x1から定数項までの６個の項について行います。）
１行目に対しては、３倍して加算、３行目と４行目についてはそのまま減算します。
（たとえば３行目の定数項は２行目の定数項をそのまま減算するので8-7=1となります。
　また、１行目のx1の要素は、-2+1/2×3=-1/2となります。）
これで(2)の下の表のとおりの数値になります。
ここまでが掃き出しです。

あとは、説明の通りに列と行を選択します。
x1列の選択は説明の通りと思います。
行の選択ですが、定数項/列要素の値（定数項を選択した列の要素で割ったもの）を比較します。
３行目の場合、定数項が１、x1の要素が1/2なので1/(1/2)=2というのは説明の通りです。
定数項/列要素は 14, 2, 22/5 となるので、2、つまり３行目を選択します。
(2)の下の表の色が選択結果を表しています。

この回答へのお礼

ありがとうございます。
しかし、如何せん頭が固くなっており、文字だけだとピンと来ません・・・。
よろしかったら方程式を書いていただけませんでしょうか？
すみません、よろしくお願いします。

お礼日時：2012/11/15 03:55