線形計画法を2段階シンプレックス法を用いて解く

質問

次の問いを2段階法を用いて解けというものなのですが

(1)
x0 = 4x1 - 2x2 + x3 → 最大化
2x1 + x2 + x3 ≦ 6
4x1 - 2x2 + x3 ≦ -4
x1, x2, x3 ≧ 0

(2)
x0 = 3x1 + 2x2 → 最大化
x1 + 2x2 ≦ 20
7x1 + 6x2 ≧ 84
x1 - x2 ≦ 8
x1, x2 ≧0

(1)に関しては人為変数が不要なのでそもそも2段階法で解けるのでしょうか？
(2)は
x1 + 2x2 +x3 = 20
7x1 + 6x2 - x4 = 84
x1 - x2 +x5 = 8
とした後に人為変数x6を用いて
x1 + 2x2 +x3 = 20
7x1 + 6x2 - x4 +x6 = 84
x1 - x2 +x5 = 8
として解いていったのですがシンプレックス表で解いている途中で詰まってしまいます。

(1), (2)ともにある程度の途中計算を交えて教えてくださると助かります。
よろしくお願いします。

回答No.1

muturajcp

(1)
x0=4x1-2x2+x3→最大化
2x1+x2+x3≦6
4x1-2x2+x3≦-4
x1,x2,x3≧0

x4=6-(2x1+x2+x3)
x5=-4-(4x1-2x2+x3)
とすると

2x1 +x2+x3+x4=6…………(a)
4x1-2x2+x3+x5=-4………(b)
x0-4x1+2x2-x3 =0…………(c)
x1,x2,x3,x4,x5≧0

x1 +x2/2+x3/2+x4/2 =3………(d)=(a)/2
-4x2 -x3 -2x4+x5=-16………(e)=(b)-(a)*2
x0 +4x2 +x3 +2x4 =12…………(f)=(c)+(a)*2

x1 +3x3/8+x4/4+x5/8=1………(g)=(d)-(h)/2
x2+x3/4+x4/2-x5/4=4………(h)=-(e)/4
x0 +x5=-4……………(i)=(f)+(e)

x3=x4=x5=0とすると
x0=-4
x1=1
x2=4
x3=0

(2)
x0=3x1+2x2→最大化
x1+2x2≦20
7x1+6x2≧84
x1-x2≦8
x1,x2≧0

x3=20-(x1+2x2)
x4=7x1+6x2-84
x5=8-x1+x2
とすると

x1+2x2+x3 =20…………(j)
7x1+6x2 -x4 =84…………(k)
x1 -x2 +x5=8…………(l)
x0-3x1-2x2 =0…………(m)
x1,x2,x3,x4,x5≧0

x1+2x2+x3 =20
8x2+7x3+x4 =56…………(n)=7*(j)-(k)
3x2+x3 -x5=12…………(o)=(j)-(l)
x0 +4x2+3x3 =60…………(p)=(m)+3*(j)

x1 +x3/3 +2x5/3=12…………(s)=(j)-2*(q)
13x3/3+x4+8x5/3=24…………(r)=(n)-8*(q)
x2 +x3/3 -x5/3=4…………(q)=(o)/3
x0 +5x3/3 +4x5/3=44…………(t)=(p)-4*(q)

x3=x5=0とすると
x4=24
x0=44
x1=12
x2=4