运筹学习题集(第二章)

1、判断题判断正误，如果错误请更正第二章 线形规划的对偶理论1. 原问题第 i 个约束是 <= 约束 ,那么对偶变量 yi>=0.2. 互为对偶问题 ,或那么同时都有最优解 ,或那么同时都无最优解 .3. 原问题有多重解 ,对偶问题也有多重解 .4. 对偶问题有可行解 ,原问题无可行解 ,那么对偶问题具有无界解 .5. 原问题无最优解 ,那么对偶问题无可行解 .6. 设 X,Y 分别为 minZ=CX| AX>=b,X>=0和 maxw=Yb| YA<=C,Y>=0 的可行解,那么有(1) CX<=Yb;(2) CX 是 w 的上界 ;(3) 当 X,Y

2、为最优解 ,CX=Yb;(4) 当 CX=Yb 时,有 YXs+YsX=0;(5) X 为最优解且 B 是最优基时 ,那么 Y=CBB-1 是最优解 ;(6) 松弛变量Ys的检验数是入s,那么X=-入s是根本解，假设Ys是最优解，那么X=-入s是最 优解 ., 那么都有最优解 .8. 原问题具有无界解 , 那么对偶问题可行 .9. 假设 X,Y 是原问题与对偶问题的最优解 . 那么 X=Y.10. 假设某种资源影子价格为 0, 那么该资源一定有剩余 .11 影子价格就是资源的价格 .12. 原问题可行对偶问题不可行 , 可用对偶单纯形法计算 .13. 对偶单纯形法比值失效说明原问题具有无界解

3、.14. 对偶单纯形法是直接解对偶问题的一种解法 .15. 减少一个约束 , 目标值不会比原来变差 .16. 增加一个约束 , 目标值不会比原来变好 .17 增加一个变量 , 目标值不会比原来变差 .18. 减少一个非基变量 , 目标值不变 .19. 当Cj(j=1,2,3,n)在允许的最大范围内同时变化时，最优解不变。选择题在以下各题中，从 4 个备选答案中选出一个或从5 个备选答案中选出25 个正确答案。第二章 线性规划的对偶理论1. 如果断策变量数列相等的两个线规划的最优解相同，那么两个线性规划A 约束条件相同B 目标函数相同 C 最优目标函数值相同 D 以上结论都不对2. 对偶单纯形法

4、的最小比值规那么是为了保证 A 使原问题保持可行 B 使对偶问题保持可行 C 逐步消除原问题不可行性D 逐步消除对偶问题不可行性3. 互为对偶的两个线性规划问题的解存在关系 A 假设最优解存在， 那么最优解相同 B 原问题无可行解， 那么对偶问题也无可行解C 对偶问题无可行解， 原问题可能无可行解 D 一个问题无界，那么另一个问题无可行解E 一个问题无可行解，那么另一个问题具有无界解4. 标准形式原问题max的最优表中的检验数为入 1,入2,入n，松弛变量的检验数为入n+1,入n+2, 入n+m,那么对偶问题的最优解为A 入1，入2,入 nB 入 1，入 2,入 nC 入 n+1,入 n+2,

5、入 n+mD D入 n+1,入 n+2,入 n+m5. 原问题与对偶问题都有可行解，那么A原问题有最优解，对偶问题可能没有最优解B原问题与对偶问题可能都没有最优解C可能一个问题有最优解，另一个问题具有无界解D原问题与对偶问题都有最优解计算题线性规划问题和对偶问题2.1对于如下的线性规划问题min z = 3xi + 2x2 +xas.t. x1 + x2+ x315(1)2x1 - x2+ x39-x1 + 2x2+2x38x1 x2x301、写出题目中线性规划问题的对偶问题；2、分别求出原始问题和对偶问题的最优解求解的次序和方法不限 解答：1、写出题目中线性规划问题的对偶问题；解：max w

6、 = 15y1+ 9y 2 + 8y 3s.t. y1 + 2y2 - y 33(1)y1 - y2 + 2y 32y1 + y2 + 2y 31y10、y 20、y302、分别求出原始问题和对偶问题的最优解求解的次序和方法不限解：先将原问题化成以下形式，那么有min z=3x1+ 2x 2+ x3s.t. x1+ x 2+ x 3+ x 4=15(1)-2x1+ x 2-x3+ x 5=-9-x1+ 2x 2+2x 3+x 6=8x1x 2 x 3 X4x 5 x 60X1X2为X5X6右端z-3-2-1000X411110015X5-21-1010-9X6-1：22001:8X1X2用为X

7、5X6右端z-1：-300-10:9X4-1201106X32-110-109X6-540021P-10X1XX3%X5X右端z0-19/500-7/5-1/511X40：6/5013/5-1/5:8关03/510-1/52/55X1-4/500-2/5-1/52原始问题的最优解为Xi X2 X3 X4 X5 X6=2, 0, 5, 8, 0, 0，minz=11对偶问题的最优解为yi y 2 y 3 y 4 y 5 y 6= 0, 7/5 , -1/5 , 0, 19/5 , 0，maxw=112.2对于以下线性规划问题max z = -X1- 2x 2s.t. -2x1 + 3x 212(

8、1)-3x1 + x 26x1 + 3x 23x10 , x 201、写出标准化的线性规划问题；2、用单纯形表求出这个线性规划问题的最优解和最优的目标函数值；3、写出这个极大化线性规划问题的对偶问题；4、求出对偶问题的最优解和最优解的目标函数值；5、第2个约束右端常数 b2=6在什么范围内变化，最优解保持不变。解答：1、写出标准化的线性规划问题:令 X1 =:-X1max z*=X1-2x 2s.t.2x1* + 3x 2+ x 3=12(1)3x*1+ x 2+ x4=6-x1* + 3x 2-x5 = 3x*1 x 2 x 3X4 x 502、 6分用单纯形表求出这个线性规划问题的最优解和

9、最优的目标函数值*X1X2关XX5R右端Z'1-M3M-200-M03MX323100012%3101006R-1300-113*X1KX3为X5R右端Z'1/3000-2/32/3-M2%01019Xi10/30011/3-1/35茨-1/3100-1/3I 1/31*X1茨X3XX5R右端Z'000-1/10-7/1021/30-M3/2001-9/109/2*X1003/101/10-1/103/20101/103/2此时最优解为X、Xz、X3、X4 X5=-3/2 , 3/2 , 9/2 , 0 , 0maxz=-3/2 3、写出这个极大化线性规划问题的对偶问题

10、；min w = 12y1+ 6y 2 + 3y 3s.t. -2y1 - 3y 2 + y 3-1(1)3y1 + y 2 + 3 y 3-2(2)yi0、y20、y304、求出对偶问题的最优解和最优解的目标函数值；此时最优解为yi、y2、y3、y4 y 5= 0, 1/10,-7/10, 0, 0minw =-3/25、那么有1 b211，最优解不变。2.3LP问题：max z =X1+ 2x 2 +3x3 + 4x 4s.t. x1+ 2x 2 + 2x 3 + 3x 420(1)2x1+ x 2 + 3x 3 + 2x 420(2)x1、X 2、 X3、 x 40的最优解为0，0,4,

11、4T，最优值为Z=28。请用互补松弛定理计算其对偶问题的最优解。解答：首先写出此LP问题的对偶问题为:min w =20y1+ 20y 2s.t. y1+ 2y 21(1)2y1+ y 222y1+ 3y 233y 1+ 2y 24y 1、y 2、0将上述对偶问题的化成标准型，取松弛变量分别为V1、V2、 V3、V4,那么有min w = 20y1+ 20y 2s.t. y1+ 2y 2 -V1=12y1+ y 2 -V2=22y1+ 3y 2-V3=33y 1+ 2y 2 -V4=4(8)y1、y 2、0利用互补松弛定理可知:X3 = 4 > 0 ,又有 X 3 V3 = 0，所以有V

12、3 = 0代入式X4 = 4 > 0，又有 X 4 V4= 0所以有V4 = 0代入(8)式，那么有2y1+ 3y 2=:3(9)3y1+ 2y 2=:4(10)从中可计算出y1 = 6/5、y2 =1/5，那么w* =282.4 一个工厂用四种原料生产三种产品，生产每种产品要消耗的各种原料 数量表中“一表示相应的产品不需要这种原料、各种产品的利润以及各种原料的限量如下表所示。1、写出原料限制条件下利润最大化的线性规划模型；2、写出以上问题的对偶问题；3、 利润最大的线性规划问题的最优解是产品A生产120件，产品B不生产，产品C生产52件，用互补松弛关系求四种原料的影子价格。原料消耗吨/

13、件产品A产品B产品C原料限量吨原料甲128102400原料乙610151500原料丙15181800原料丁20222000产品利润120180210万元/件解答：一个工厂用四种原料生产三种产品，生产每种产品要消耗的各种原料 数量表中“一表示相应的产品不需要这种原料、各种产品的利润以及各种原料的限量如下表所示。1.写出原料限制条件下利润最大化的线性规划模型;max z =120X1+ 180X2 +210X3s.t. 12x1 +8x 2+10X32400(1)6x1 +10X 2+15X3150015x1 +18x 2180020x2+ 22x32000X10， X 20 X 302.写出以上

14、问题的对偶问题；min w =:2400y1 + 1500 y2 +1800 y3+2000y4s.t. 12y1 + 6y 2 +15y3120(1)8y1 + 10y 2 + 18 y3 + 20 y18010y1 + 15y 2+22y4210y 10 ， y 20 y 30 y403.利润最大的线性规划问题的最优解是产品A生产120件，产品B不生产，产品C生产52件，用互补松弛关系求四种原料的影子价格。maxz =120X1 +180X2+210 X3s.t. 12x1+8x2 +10X3+X4=2400(1)6x1+10x2 +15X3+x5 =150015x1+18x2+X6=180020x2 + 22x3+X7 =:20001 0， X 20X 30X 40 x50 X 60 X70X4 =440 X5 =0 X6 =0 X7 =856min w=2400y1 + 1500 y2+1800y3 +2000y4s.t. 12y1 + 6y2 +15y3-屮=120 (1)8y1 + 10y2 +18 y3+ 20 y4