第二章 线性规划习题(附答案)
- 格式：doc
- 大小：1.03 MB
- 文档页数：23
1 习题
2-1 判断下列说法是否正确：
（1） 任何线性规划问题存在并具有惟一的对偶问题；
（2） 对偶问题的对偶问题一定是原问题；
（3） 根据对偶问题的性质，当原问题为无界解时，其对偶问题无可行解，反之，当对偶问题无可行解时，其原问题具有无界解；
（4） 若线性规划的原问题有无穷多最优解，则其对偶问题也一定具有无穷多最优解；
（5） 若线性规划问题中的bi，cj值同时发生变化，反映到最终单纯形表中，不会出现原问题与对偶问题均为非可行解的情况；
（6） 应用对偶单纯形法计算时，若单纯形表中某一基变量xi<0，又xi所在行的元素全部大于或等于零，则可以判断其对偶问题具有无界解。
（7） 若某种资源的影子价格等于k，在其他条件不变的情况下，当该种资源增加5个单位时，相应的目标函数值将增大5k；
（8） 已知yi为线性规划的对偶问题的最优解，若yi>0，说明在最优生产计划中第i种资源已经完全耗尽；若yi=0，说明在最优生产计划中的第i种资源一定有剩余。
2-2将下述线性规划问题化成标准形式。
无约束43214321432143214321,0,,232142224.5243max)1(xxxxxxxxxxxxxxxxstxxxxz无约束321321321321,0,0624.322min2xxxxxxxxxstxxxz
解：(1)令'''444xxx，增加松弛变量5x，剩余变量6x，则该问题的标准形式如下所示：
'''12344'''12344'''123445'''123446'''1234456max342554222214..232,,,,,,0zxxxxxxxxxxxxxxxxstxxxxxxxxxxxxx
(2)令'zz，'11xx，'''333xxx，增加松弛变量4x，则该问题的标准形式如下所示： 2 '''''1233''''1233''''12334''''12334max22334..26,,,,0zxxxxxxxxstxxxxxxxxxx
2-3分别用图解法和单纯形法求解下述线性规划问题，并对照指出单纯形表中的各基可行解对应图解法中可行域的哪一顶点。
0,825943.510max121212121xxxxxxstxxz0,24261553.2max221212121xxxxxxstxxz
解：(1)图解法
最优点为B点，最优解为x1=1,x2=3/2，最优值为35/2。
单纯形表计算过程：
初始单纯形表（对应O点）
z’ x1 x2 x3 x4 RHS
z’ 1 -10 -5 0 0 0
x3 0 3 4 1 0 9 9/3
x4 0 [5] 2 0 1 8 8/5
第一次迭代（对应A点）
z’ x1 x2 x3 x4 RHS
z’ 1 0 -1 0 2 16
x3 0 0 [14/5] 1 -3/5 21/5 21/5/14/5
x1 10 1 2/5 0 1/5 8/5 8/5/4/5 5x1+2x2=8x2x1O(0,0)A(8/5,0)B(1,3/2)3x1+4x2=9
第二次迭代（对应B点，即最优解）
z’ x1 x2 x3 x4 RHS
z’ 1 0 0 5/14 25/14 35/2
x2 5 0 1 5/14 -3/14 3/2
x1 10 1 0 -1/7 2/7 1
(2)图解法
最优点为B点，最优解为x1=15/4,x2=3/4，最优值为33/4。
单纯形表计算过程：
初始单纯形表（对应O点）
z’ x1 x2 x3 x4 RHS
z’ 1 -2 -1 0 0 0
x3 0 3 5 1 0 15 15/3
x4 0 [6] 2 0 1 24 24/6
第一次迭代（对应A点）
z’ x1 x2 x3 x4 RHS
z’ 1 0 -1/3 0 1/3 8
x3 0 0 [4] 1 -1/2 3 3/4
x1 2 1 1/3 0 1/6 4 4/1/3
第二次迭代（对应B点，即最优解）
z’ x1 x2 x3 x4 RHS
z’ 1 0 0 1/12 7/24 33/4
x2 1 0 1 1/4 -1/8 3/4
x1 2 1 0 -1/12 5/24 15/4
6x1+2x2=24x2x1O(0,0)A (4,0)B(15/4,3/4)3x1+5x2=15 4 057234219532..5432154321jxxxxxxxxxxxts0226332..31434321421jxxxxxxxxxxxxts2-4已知线性规划问题，写出其对偶问题：
（1）
(2)
解：(1)原问题的对偶问题为：
12121212121212min19572104242320..3220525,0yyyyyyyystyyyyyy
(2)原问题的对偶问题为：
1234124122341231234max36223826..36,,,0yyyyyyyyystyyyyyyyyyy
2-5运用对偶理论求解以下各问题：
（1）已知线性规划问题：
543212520202410maxxxxxxz)5,4,3,2,1(j43216368minxxxxz)4,3,2,1(j32122minxxxz
无约束321321321,0,064..xxxkxxxxxxts
其最优解为
（a）求k的值；
（b）写出并求出其对偶问题的最优解。
解：原问题的对偶问题为：
1212121212max4621..20yyyyyystykyyy无约束，
设该对偶问题的三个人工变量为123,,sssyyy，由于原问题的最优解中的13,0xx，则根据互补松弛性，所增加的人工变量130,0ssyy，则：
122yy，122yky。
另外，原问题的最优值*123222(5)02(1)12zxxx，也为对偶问题的最优值，即：*124612yy。
结合上述三式可得：
*1*2021yyk
（2）已知线性规划问题：
其对偶问题的最优解为， 。 1235,0,1xxx4321432maxxxxxz0,,,2023220322..432143214321xxxxxxxxxxxxts2.11y2.02y 6 试根据对偶理论求出原问题的最优解。
解：首先写出原问题的对偶问题如下：
121212121212min20202122..233324,0yyyyyystyyyyyy
由于该对偶问题的最优解为**121.2,0.2yy，代入对偶问题的约束条件中可得
121.612.62..3344,0styy，即对偶问题中的松弛变量1234,0,,0ssssyyyy。则根据互补松弛性可知，原问题中的决策变量12,xx必为0。
将12,xx=0代入原问题中的约束条件，可得：
13423423203220ssxxxxxx。又因为**121.2,0.2yy均不为0，则同样根据互补松弛性可知，12,0ssxx。则有：343423203220xxxx。求解该方程组可得：344,4xx。
（3）已知线性规划问题:
0,,12.max32132132121xxxxxxxxxstxxz
试根据对偶问题性质证明上述线性规划问题目标函数值无界。
解：首先写出原问题的对偶问题如下：
1212121212min211..00yyyyyystyyyy，
由于该对偶问题中前两个约束条件所确定的可行域为空集，可知该对偶问题无解。则根据对偶性质可知，原问题无解可无界。
另外，(0,0,0)x必为原问题的解之一，则可证原问题无界。
2-6已知某求极大值线性规划问题用单纯形法求解时的初始单纯形表及最终单纯形表如表2-44所示，求表中各括弧内未知数的值。
表2-44 初始单纯形表及最终单纯形表
z x1 x2 x3 x4 x5 x6 RHS
z 1 -3 -2 -2 0 0 0 0
x4 0 1 1 1 1 0 0 （b）
x5 0 (a) 1 2 0 1 0 15
x6 0 2 (c) 1 0 0 1 20
：：
z x1 x2 x3 x4 x5 x6 RHS
z 1 0 （k） （g） 0 5/4 （j） 95/4
x4 0 0 0 （d） (l) -1/4 -1/4 5/4
x1 3 1 0 （e） 0 3/4 （i） 25/4
x2 2 0 1 （f） 0 （h） 1/2 5/2
解：由初始单纯形表中的基变量为456,,xxx可知，1B为最终单纯形表中456,,xxx所对应的消耗系数矩阵，即：
111/41/403/401/2Bih
则有：11110012102101dBaecf，可求得：2,3,1/4,5/4,acde
1/2,1/2,1/4fhi。
