[OCN光]Twitterキャンペーン開催中!

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

教えて!goo グレード

A 回答 (2件)

No.1です。


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

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

2.(1)から(2)への掃き出しの説明
2-1.初期状態
表(1)ですが、初期状態からピボットを選択しただけの状態です
念のため初期のシンプレックス表を示します。
基底変数 x1  x2  x3  x4  x5 定数項
Z    -2  -3   0   0   0   0
x2    1   2   1   0   0  14
x4    1   1   0   1   0   8
x5    3   1   0   0   1  18

ここで列を選び定数項/列要素を比較した結果、2行目のx2の項である2がピボットになります。
2行目の式は以下の式1のとおりと初期状態のままです。
x1+2・x2+x3 = 14    式1
(式の書き方はこのようにしますがよろしいでしょうか)

2-2.第1段階(ピボットのある行の式)
掃き出しの第1段階として、ピボットを1にします。方法は、式1の両辺をピボットで割ります。
(x1+2・x2+x3)/2 = 14/2
1/2・x1+x2+1/2・x3 = 7    式2
なお、基底変数はx2になります。(理由ですが、項が1になったからというより、ピボットだからと考えた方がよさそうです。)

式2によって表の2行目は表(2)の値に更新され、他の行は表(1)のままとなります。
つまり、表は以下のようになります。
基底変数 x1  x2  x3  x4  x5 定数項
Z    -2  -3   0   0   0   0
x2   1/2  1  1/2  0   0   7
x4    1   1   0   1   0   8
x5    3   1   0   0   1  18

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

2-3.第2段階その1(1行目の式)
掃き出しの第2段階として、他の行のx2の項を0にします。
方法は、連立方程式の加減法と同じです。
つまり、他の行のx2の項を2行目の式(式2)の両辺に掛け、それを引きます。
(1行目のx2の項は-3なので-3を掛けます)
1行目の場合を示すと以下のようになります。
1行目のx2の項は-3なので-3を掛けます
(1/2・x1+x2+1/2・x3)・(-3) = 7・(-3)
-3/2・x1-3・x2-3/2・x3 = -21    式3

式3を1行目の式から引きます。
  Z  -2・x1-3・x2        =   0  (1行目の式)
-) -3/2・x1-3・x2-3/2・x3 = -21   (式3)
-----------------------------
  Z-1/2・x1     +3/2・x3 =  21    式4

式4により表の1行目が表(2)の値に更新されます。
基底変数 x1  x2  x3  x4  x5 定数項
Z   -1/2  0  3/2  0   0  21
x2   1/2  1  1/2  0   0   7
x4    1   1   0   1   0   8
x5    3   1   0   0   1  18

2-4.第2段階その2(3行目、4行目の式)
同様に3行目、4行目についてもx2の項を0にします。
(式2に掛ける値はどちらも1です)
これですべての項が表(2)の値に更新されます。
結果のみ(というか単に表(2)から定数項/列要素を除いたものですが)を示します。
基底変数 x1  x2  x3  x4  x5 定数項
Z   -1/2  0  3/2  0   0  21
x2   1/2  1  1/2  0   0   7
x4   1/2  0 -1/2  1   0   1
x5   5/2  0 -1/2  0   1  11

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


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


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

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



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


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

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

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

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

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!


人気Q&Aランキング