解答(2015/5/18)

解答 (2015/5/18)
(iii) 双対問題は
1. 次の線形計画問題を解け。
ay1 + 3y2 → min
− 2x1 − x2 → min
y1 + 3y2 ≥ 2
x1 + x2 ≤ a
y1 + y2 ≥ 1
3x1 + x2 ≤ 3
y1 ≥ 0, y2 ≥ 0
x1 ≥ 0, x2 ≥ 0
ただし，1 < a < 2 とする．
(i) この問題を標準形に帰着させよ．
(ii) 標準形に帰着させた問題をシンプレック
ス法で解け．
(iii) この問題の双対問題を示し，2 段階法で
解くためのシンプレックス表の最初の部
分を示せ．その後の計算は不要である．
(解答)
標準形については略す．答案では省略せずに
明記すること．
(ii)
基底
−z
x3
x4
−z
x1
−2
1
3
x3
x1
−z
x2
x1
1
x2
−1
1
1
− 13
x3
2
3
1
3
1
1
1
x4
1
1
1
2
3
2
− 21
2
3
− 13
1
3
1
2
− 12
1
2
定数
0
a
3
2
a−1
1
a+3
2
3(a−1)
2
3−a
2
目的関数の係数がすべて非負となったので，
最適である．最適解は x1 = 3−a
, x2 = 3(a−1)
2
2
(x3 = 0, x4 = 0) , z = − a+3
.
2
2 段階法の途中のプロセスについては省略（答
案では省略しないこと）．シンプレックス表
の最初の部分は，
基底
−w
−z
x5
x6
y1 y2 y3 y4 定数
−2 −4
1
1
−3
a
3
0
1
3 −1
2
1
1
−1
1
2. 線形計画問題
c1 x1 + c2 x2 → max
αx1 + βx2 ≤ b1
γx1 + δx2 = b2
x1 , x 2 ≥ 0
の双対問題を示せ．ただし，変数 y1 , y2 を用
い，目的関数が b1 y1 + b2 y2 → min となるよ
うに変形すること．
(解答) 標準形は
[−c1 , −c2 , 0][x1 , x2 , x3 ]⊤ → min
 
[ ]
[
] x
1
b1
−α −β −1  
x2  = −
b2
−γ −δ 0
x3
[x1 , x2 , x3 ]⊤ ≥ 0
この双対問題は
− b1 y1 − b2 y2 → max




−c1
−α −γ [ ]


 y1

≤ −c2 
−β −δ 
y2
0
−1 0
標準形と人工変数の導入については略し，シ
ンプレックス表のみ記す．答案では省略せず
に明記すること．
これを整理すると
b1 y1 + b2 y2 → min
αy1 + γy2 ≥ c1
βy1 + δy2 ≥ c2
基底
y1 y2 y3 y4 定数
−w −4 −5
1
1 −3
−z 10 16
0
y5 3
2 −1
2
y6
1
3
−1
1
1 − 31
−w
− 73 − 13
y1 ≥ 0
3. 線形計画問題
z = 2x1 + x2 → max
3x1 + x2 ≤ 10
2x1 + 3x2 ≤ 16
−z
y1
x1 , x 2 ≥ 0
およびその双対問題をともに解いて，それら
の解の間の関係を述べよ．
(解答)
y6
−w
−z
y1
y2
標準形については略す．答案では省略せずに
明記すること．
基底
x1 x 2
−z −2 −1
x3 3
1
2
3
x4
−z
− 13
x1
1
x3
−z
x1
x2
1
3
7
3
1
1
x3
1
2
3
1
3
− 23
4
7
3
7
2
−7
x4 定数
0
10
1
16
1
20
3
10
3
28
3
1
7
1
−7
3
7
8
2
4
1
28
3
2
3
7
3
1
1
10
3
− 31
1
3
− 20
3
−1
2
3
1
3
2
4
0
−8
− 37
1
7
- 37
4
7
1
7
1
7
目的関数 w = 0 となったので，もとの問題は
実行可能．かつ，z の係数がすべて非負となっ
たので，最適である．最適解 y1 = 47 , y2 = 17 ,
(y3 = y4 = 0), z = 8．
もとの問題と双対問題の最適値が 8 と一致す
る．また，それぞれの最適解が対応する他の
問題の目的関数の係数に現れていることに注
意する．
目的関数の係数がすべて非負となったので，
最適である．最適解は x1 = 2, x2 = 4 (x3 = 0,
x4 = 0) , z = −8. もとの問題の最適値は 8．
双対問題は栄養問題で
z = 10y1 + 16y2 → min
3y1 + 2y2 ≥ 2
y1 + 3y2 ≥ 1
y1 , y 2 ≥ 0
2

Download Report