最適化の計算問題なんですが

質問

はじめまして
最適化のレポート問題なのですが
目的 ：z = 3x1 － 5x2 → Max
制約 ：x1 + 2x2 ≤ 7 (i)
－4x1 + 3x2 ≤ 5 (ii)
x1, x2 ≥ 0
を考える 。 以下の各問いに答えよ 。
(1) 最適解および最適値を求めよ 。
(2) 最適基底行列およびその逆行列は何か 。

という問題で、(1)はシンプレックスタブロー法で
x1=7, x2=0, x3=0, x4=33
最適値=21
と求まったのですが
最適基底行列とはなんですか？
教えて頂きたいです。
お願いしますm(__)m

回答No.1

muturajcp · ベストアンサー

(1)
x3=7-x1-2x2
x4=5+4x1-3x2
とすると
x1+2x2≦7
-4x1+3x2≦5
だから基底変数はx3,x4,zで連立方程式は
x1+2x2+x3 =7……(x3行)
-4x1+3x2 +x4 =5……(x4行)
-3x1+5x2 +z=0……(z行)
x1≧0,x2≧0,x3≧0,x4≧0
シンプレックス表で
1)
z行で最も小さい負の値-3を持つ列(x1列)に対応する非基底変数x1を新たに基底に入れる変数に選ぶ。
2)
z行を除く各行において(定数項の値)/(新たに基底に入れることになった変数x1の係数)を計算する。
x3行は7
x4行は-5/4
その値を増加限界と呼ぶ。
z行を除く各行の増加限界の中で非負で最小の値(7)を取った行(x3行)に対応する変数x3を追い出す変数に決める。
3)
新たに基底に加える変数x1の列と基底から追い出す変数x3の行との交点の係数1をピボットにする。
ピボット(x3行x1列)ピボットを中心に掃き出しを行う
4)
連立方程式を解く
各行からピボットの行を何倍かして引くことにより、ピボット列の数字がピボット以外0になるようにする。
x1+2x2 +x3 =7……(x3行)
11x2+4x3+x4 =33……(x4行+(x3行)*4)
11x2+3x3 +z=21……(z行+(x3行)*3)
5)
zの行を見ると負の値は無い。
つまり,これ以上基底を変更してもよりよい目的関数値は得られない。
よって、現在得られている解が最適である。
x2=x3=0のとき
x1=7
x4=33
z=21

(2)
最適基底はx1,x4,zだから
連立方程式から作った最初のシンプレックス表で
(列はx1列,x4列,z列,行はx3行,x4行,z行の順に並べると)
最適基底行列は
(1 ,0,0)
(-4,1,0)
(-3,0,1)
その逆行列は
(1,0,0)
(4,1,0)
(3,0,1)
となる
逆行列*定数項列=解
(1,0,0)(7)=(7)
(4,1,0)(5).(33)
(3,0,1)(0).(21)
となる