对偶问题一般习题答案
● 一般题目
内容1：根据原规划，写出对偶规划 1.1 写出下面线性规划问题的对偶问题
(a.) 234
1234123412341
234m a x 2343567358
..12999200,0,0,z x x x x x x x x x x x x s t x x x x x x x x =+++-+--=⎧⎪
++-≥⎪⎨
--+≤⎪
⎪≥≥≤⎩无约束
(b.) 1
111
11111m a x (1,)(1)
..0(1,)1n
j j
j n
ij j i j n ij j i j j j
z c x a x b i m m m a x b m i m s t x j n n n x n j n === =
⎧
≤ ≤≤≤⎪⎪⎪⎪
= +≤≤⎨⎪
⎪≥ ≤≤≤⎪
+≤≤⎪⎩∑
∑∑无约束,当
内容2：根据对偶问题，判定原问题有最优解、无解、有无穷大解 2.1 应用对偶理论, 证明线性规划问题有最优解。

12
12121
2m a x 3224
3214
..301,2j
z x x x x x x s t x x x j =+-+≤⎧⎪
+≤⎪⎨
-≤⎪⎪≥ =⎩ 提示：找到原问题和对偶问题的一个可行解，那么就能说明原问题有最优解。

2.2 应用对偶理论, 证明线性规划问题是可行的，但无最优解。

123
13123m a x 4
..14
01,2,3j
z x x x x x s t x x x x j =-+⎧-≥⎪
-+≥⎨⎪
≥ =⎩
提示：说明对偶问题无解，再根据原问题有可行解，就说明原问题为无穷解，所以没有最优解。

2.3 应用对偶理论, 证明线性规划问题无解。

12
12121
2m a x 5241
..23101,2j
z x x x x x x s t x x x j =+-≥⎧⎪
+≤⎪⎨
-≤⎪⎪≥ =⎩ 提示：说明对偶问题有无穷解，就说明原问题无解。

内容3：由原问题的最优解得到对偶问题的最优解 3.1 课本2.11题。

（a ）写出最优单纯形表
由最优单纯形表
对于2x 有 []2311/2*(1/2)*4c c c -+-=- 对于2x 有 []43141/2*(1/6)*4(0)c c c c -+-=-= 对于5x 有 []53150*(1/3)*2(0)c c c c -+=-=
可得1c 、2c 和3c 的值
由于 11/201/6
1/3B -⎛⎫=
⎪-⎝⎭ 13
1123
21a a B a a ⎛⎫
= ⎪⎝⎭
且1*B B I -=
那么可求得11a 、21a 、13a 和23a
由于 121
221/2*1/2a B
a -⎛⎫⎛⎫= ⎪ ⎪-⎝
⎭⎝⎭ 那么可求得12a 和22a
3.2 原规划为
12
1212
m a x 332212416
..51501,2j
z x x x x x s t x x j =++≤⎧⎪
≤⎪⎨
≤⎪⎪≥ =⎩ 引入松弛变量后为 12
123142
5m a x 332212416
..51501,2,3,4,5j
z x x x x x x x s t x x x j =+++=⎧⎪
+=⎪⎨
+=⎪⎪≥ =⎩ 对偶规划为
123
1213m in 121615243..253
01,2,3j
w y y y y y s t y y y j =++⎧+≥⎪
+≥⎨⎪
≥ =⎩
已知对偶规划的最优解为(3/2, 0, 0), 试完成原规划的最优单纯形表(不用单纯形求解，并写出具体思路)。

第一步：先给出原问题的初始单纯形表
第二步：根据对偶问题的最优解(3/2, 0, 0)，得到下图
第三步：由于只能是5x 、1x 和2x 为基变量，那么3x 40x ==，立即可得
14x =，22x =，55x =，且可得下表
第四步：预指定1x 为第一行的基变量，那么2x 为第三行的基变量，有下表
检验1x 是否为第一行的基变量。

根据表3的第一行和14416x x +=，立即可验证1x 确实是第一行的基变量。

第五步：在表4中，对于4x 有0=0-(3*1/4+0*5/4+3*34a )，因而可得
第六步：根据1*B B I -=，可得
1
23
01/405/411/21/4
0B
a -⎛⎫ ⎪=
⎪ ⎪-⎝
⎭ 20240001
5B ⎛⎫
⎪= ⎪ ⎪⎝
⎭
内容4：计算影子价格和隐含成本 4.1 课本(2.12)。

（略）
内容5：会使用对偶单纯形法 5.1 用对偶单纯形法解下列问题
（a.） 1234
12342341
234m in 6735563412
5610
..25801,2,3,4j
z x x x x x x x x x x x s t x x x x x j =++++-+≥⎧⎪
+-≥⎪⎨
+++≥⎪⎪≥ =⎩
引入松弛变量转化为下式
123412345234612347m a x 67355634125610
..25801,2,3,4,5,6,7j
z x x x x x x x x x x x x x s t x x x x x x j =------+-+=-⎧⎪
--++=-⎪⎨
----+=-⎪
⎪≥ =⎩ （b ） 123
1231231
23m in 2242352373
..46501,2,3j
z x x x x x x x x x s t x x x x j =---++≥⎧⎪
++≤⎪⎨
++≤⎪⎪≥ =⎩
引入松弛变量转化为下式
123123412351
236m a x 2242352373
..46501,2,3j
z x x x x x x x x x x x s t x x x x x j =++---+=-⎧⎪
+++=⎪⎨
+++=⎪⎪≥ =⎩ 令1236546x x x x =---代入上式得
23623
236234236235m a x 2(546)242(546)352
..3(546)73
02,3,4,5,6j
z x x x x x x x x x x x s t x x x x x x x j =---++⎧------+=-⎪
---+++=⎨⎪
≥ =⎩ 即
236
23642365m a x 585728
..1111312
02,3,4,5,6j
z x x x x x x x s t x x x x x j =---⎧+++=⎪
---+=-⎨⎪
≥ =⎩ （c ） 123
123131231
3m in 2332384
..226
24701,2,3j z x x x x x x x x s t x x x x x x j =--+⎧--+≥-⎪
+≤⎪⎪
+-≤⎨⎪
+≤⎪⎪≥ =⎩
（略）
（d）
122
122
123
123
m in974
575
3484
..
2686
01,2,3
j
z x x x
x x x
x x x
s t
x x x
x j
=-+
++≤
⎧
⎪
++=
⎪
⎨
++≥
⎪
⎪≥ =
⎩
（略）
内容6：能进行敏感性分析
6.1 课本2.9题（略）
内容7：会解参数规划
7.1 课本2.10题中(a)和(d)（略）。