平成 26 年度 練習問題解答
平成 26 年 6 月 10 日（火） 13:00-14:30
数理計画 ・火曜日3時限・担当教員: 小野廣隆(TA:土中哲秀)
注意.
1. 解答用紙は2枚ある. (i)-(iii)を1枚目, (iv)-(vi)を2枚目に解答すること.
2. 解答は結果だけでなく, それに至る過程を記述すること. 問題にもよるが, 結果のみの解答の 場合, 正解であってもその問の得点は0点とする場合がある.
3. tは行列の転置, 0を適当なサイズのゼロ要素からなるベクトルを表すものとする. [1]
(i)
max 168x1+ 60x2+ 222x3
subject to 7x1+ 2x2+ 14x3 ≤90 8x1+ 4x2+ 8x3 ≤120
x1, x2, x3 ≥0. (ii)
min −168x1−60x2−222x3
subject to 7x1+ 2x2+ 14x3+ x4 = 90 8x1+ 4x2+ 8x3+ x5 = 120
x1, x2, x3, x4, x5 ≥0. (iii)
-168 -222 -60 0 0 0
x4 7 14 2 1 0 90
x5 8 8 4 0 1 120
-48 -102 0 0 15 1800
x4 3 10 0 1 -1/2 30
x3 2 2 1 0 1/4 30
0 58 0 16 7 2280
x1 1 10/3 0 1/3 -1/6 10 x3 0 -14/3 1 -2/3 7/12 10
xB = (x1, x3) = (10, 10) xN = (x2, x4, x5) = (0, 0, 0)
1
(iv)
min 90y1+ 120y2
subject to 7y1+ 8y2 ≥168 2y1+ 4y2 ≥60 14y1+ 8y2 ≥222
y1, y2 ≥0.
(v)
min 90y1+ 120y2
subject to 7y1+ 8y2−y3 = 168 2y1+ 4y2−y4 = 60 14y1+ 8y2−y5 = 222
y1, y2, y3, y4, y5 ≥0.
(vi) まず,初期解を求めるために以下の補助問題を解く. min y6+ y7+ y8
subject to 7y1+ 8y2−y3+ y6 = 168 2y1+ 4y2−y4+ y7 = 60 14y1+ 8y2−y5+ y8 = 222 y1, y2, y3, y4, y5, y6, y7, y8 ≥0.
0 0 0 0 0 1 1 1 0
y6 7 8 -1 0 0 1 0 0 168
y7 2 4 0 -1 0 0 1 0 60
y8 14 8 0 0 -1 0 0 1 222
-23 -20 1 1 1 0 0 0 -450
y6 7 8 -1 0 0 1 0 0 168
y7 2 4 0 -1 0 0 1 0 60
y8 14 8 0 0 -1 0 0 1 222
-13 0 1 -4 1 0 5 0 -150
y6 3 0 -1 2 0 1 -2 0 48
y2 1/2 1 0 -1/4 0 0 1/4 0 15
y8 10 0 0 2 -1 0 -2 1 102
2
-7 0 -1 0 1 1 1 0 -54 y4 3/2 0 -1/2 1 0 1/2 -1 0 24 y2 7/8 1 -1/8 0 0 1/8 0 0 21
y8 7 0 1 0 -1 -1 0 1 54
0 0 0 0 0 0 1 1 0
y4 0 0 -5/7 1 3/14 5/7 -1 -3/14 87/7 y2 0 1 -1/4 0 1/8 1/4 0 -1/8 57/4 y1 1 0 1/7 0 -1/7 -1/7 0 1/7 54/7
したがって,初期解は
(y1, y2, y4) = (54/7, 57/4, 87/7). 初期解をもとに元問題を解く.
90 120 0 0 0 0
y4 0 0 -5/7 1 3/14 87/7 y2 0 1 -1/4 0 1/8 57/4 y1 1 0 1/7 0 -1/7 54/7
0 0 120/7 0 -15/7 -16830/7 y4 0 0 -5/7 1 3/14 87/7 y2 0 1 -1/4 0 1/8 57/4 y1 1 0 1/7 0 -1/7 54/7
0 0 10 10 0 -2280
y5 0 0 -10/3 14/3 1 58 y2 0 1 1/6 -7/12 0 7 y1 1 0 -1/3 2/3 0 16
ゆえに,双対問題の最適解は,
(y1, y2, y5) = (16, 7, 58) (y3, y4) = (0, 0) 目的関数値は2280. これは,元問題の目的関数値に等しい.
3
