运筹学习题集(第二章)

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

2、)X为最优解且B是最优基时,则Y=CBB-1是最优解;(6)松弛变量Ys的检验数是s,则X=-s是基本解,若Ys是最优解, 则X=-s是最优解.7.原问题与对偶问题都可行,则都有最优解.8.原问题具有无界解,则对偶问题可行.9.若X,Y是原问题与对偶问题的最优解.则X=Y.10.若某种资源影子价格为0,则该资源一定有剩余.11影子价格就是资源的价格.12.原问题可行对偶问题不可行,可用对偶单纯形法计算.13.对偶单纯形法比值失效说明原问题具有无界解.14.对偶单纯形法是直接解对偶问题的一种解法.15.减少一个约束,目标值不会比原来变差.16.增加一个约束,目标值不会比原来变好.17增加一个变量

3、, 目标值不会比原来变差.18.减少一个非基变量, 目标值不变.19.当Cj(j=1,2,3,，n)在允许的最大范围内同时变化时，最优解不变。选择题在下列各题中，从4个备选答案中选出一个或从5个备选答案中选出25个正确答案。第二章 线性规划的对偶理论1. 如果决策变量数列相等的两个线规划的最优解相同，则两个线性规划 A约束条件相同 B目标函数相同 C最优目标函数值相同 D以上结论都不对2. 对偶单纯形法的最小比值规则是为了保证 A使原问题保持可行 B使对偶问题保持可行 C逐步消除原问题不可行性 D逐步消除对偶问题不可行性 3. 互为对偶的两个线性规划问题的解存在关系 A若最优解存在，则最优解相

4、同 B原问题无可行解，则对偶问题也无可行解 C对偶问题无可行解，原问题可能无可行解 D一个问题无界，则另一个问题无可行解 E一个问题无可行解，则另一个问题具有无界解4. 已知规范形式原问题（max）的最优表中的检验数为（1，2，n），松弛变量的检验数为（n+1,n+2,n+m）,则对偶问题的最优解为 A（1，2，n） B （1，2，n） C （n+1,n+2,n+m）D（n+1,n+2,n+m）5. 原问题与对偶问题都有可行解，则 A原问题有最优解，对偶问题可能没有最优解B原问题与对偶问题可能都没有最优解 C可能一个问题有最优解，另一个问题具有无界解D原问题与对偶问题都有最优解计算题 线性规划

5、问题和对偶问题2.1 对于如下的线性规划问题 min z = 3x1 + 2x2 +x3s.t. x1 + x2 + x3 15 (1) 2x1 - x2 + x3 9 (2) -x1 + 2x2 +2x3 8 (3) x1 x2 x3 0 1、写出题目中线性规划问题的对偶问题； 2、分别求出原始问题和对偶问题的最优解（求解的次序和方法不限）； 解答：1、写出题目中线性规划问题的对偶问题； 解：max w = 15y1 + 9y2 + 8y3s.t. y1 + 2y2 - y3 3 (1) y1 - y2 + 2y3 2 (2) y1 + y2 + 2y3 1 (3) y1 0、 y2 0、y

6、3 0 2、分别求出原始问题和对偶问题的最优解（求解的次序和方法不限）； 解：先将原问题化成以下形式，则有 min z = 3x1 + 2x2 + x3s.t. x1 + x2 + x3 + x4 = 15 (1) -2x1 + x2 - x3 + x5 = -9 (2) -x1 + 2x2 +2x3 +x6 = 8 (3) x1 x2 x3 x4 x5 x6 0X1X2X3X4X5X6右端z-3-2-1000X411110015X5-21-1010-9X6-1220018X1X2X3X4X5X6右端z-1-300-109X4-1201106X32-110-109X6-540021-10X1X

7、2X3X4X5X6右端z0-19/500-7/5-1/511X406/5013/5-1/58X303/510-1/52/55X11-4/500-2/5-1/52 原始问题的最优解为（X1 X2 X3 X4 X5 X6）=（2，0，5，8，0，0），minz=11 对偶问题的最优解为（y1 y2 y3 y4 y5 y6）=（0，7/5，-1/5，0，19/5，0），maxw=112.2 对于以下线性规划问题 max z = -x1 - 2x2s.t. -2x1 + 3x2 12 (1) -3x1 + x2 6 (2) x1 + 3x2 3 (3) x1 0， x2 01、写出标准化的线性规划问题

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

9、R右端Z1-M3M-200-M03MX323100012X43101006R-1300-113x1*X2X3X4X5R右端Z1/3000-2/32/3-M2X330101-19X410/30011/3-1/35X2-1/3100-1/31/31x1*X2X3X4X5R右端Z000-1/10-7/1021/30-M3/2X3001-9/109/2X1*1003/101/10-1/103/2X20101/103/2 此时最优解为（X1、X2、X3、X4 X5）=（-3/2，3/2，9/2，0，0）maxz=-3/23、写出这个（极大化）线性规划问题的对偶问题； min w = 12y1 + 6y2

10、 + 3y3s.t. -2y1 - 3y2 + y3 -1 (1) 3y1 + y2 + 3 y3 -2 (2) y1 0、 y2 0、y3 04、求出对偶问题的最优解和最优解的目标函数值； 此时最优解为（y1、y2、y3、y4 y5）=（0，1/10,-7/10，0，0）minw =-3/25、则有1b211，最优解不变。2.3 已知LP问题： max z = x1 + 2x2 +3x3 + 4x4s.t. x1 + 2x2 + 2x3 + 3x4 20 (1) 2x1 + x2 + 3x3 + 2x4 20 (2) x1 、 x2 、 x3 、 x4 0的最优解为（0，0，4，4）T，最优

11、值为Z=28。请用互补松弛定理计算其对偶问题的最优解。解答：首先写出此LP问题的对偶问题为： min w = 20y1 + 20y2s.t. y1 + 2y2 1 (1)2y1 + y2 2 (2) 2y1 + 3y2 3 (3) 3y1 + 2y2 4 (4) y1 、 y2 、 0 将上述对偶问题的化成标准型，取松弛变量分别为v1 、v2、 v3 、v4，则有 min w = 20y1 + 20y2s.t. y1 + 2y2 - v1 = 1 (5)2y1 + y2 - v2 = 2 (6) 2y1 + 3y2 - v3 = 3 (7) 3y1 + 2y2 - v4 = 4 (8) y1

12、、 y2 、 0利用互补松弛定理可知：x3 = 4 > 0 ,又有 x3 v3 = 0 ， 所以有 v3 = 0 代入(7)式x4 = 4 > 0，又有 x4 v4= 0 ， 所以有 v4 = 0 代入(8)式，则有2y1 + 3y2 = 3 (9) 3y1 + 2y2 = 4 (10) 从中可计算出y1 = 6/5 、 y2 = 1/5，则 w* =28 2.4 一个工厂用四种原料生产三种产品，生产每种产品要消耗的各种原料数量（表中“”表示相应的产品不需要这种原料）、各种产品的利润以及各种原料的限量如下表所示。1、 写出原料限制条件下利润最大化的线性规划模型；2、 写出以上问题的

13、对偶问题；3、 已知利润最大的线性规划问题的最优解是产品A生产120件，产品B不生产，产品C生产52件，用互补松弛关系求四种原料的影子价格。原料消耗（吨/件）产品A产品B产品C原料限量（吨）原料甲128102400原料乙610151500原料丙15181800原料丁20222000产品利润（万元/件）120180210解答：一个工厂用四种原料生产三种产品，生产每种产品要消耗的各种原料数量（表中“”表示相应的产品不需要这种原料）、各种产品的利润以及各种原料的限量如下表所示。1. 写出原料限制条件下利润最大化的线性规划模型；max z = 120x1 + 180 x2 +210 x3s.t. 12

14、x1 + 8x2 +10 x3 2400 (1) 6x1 + 10x2 +15 x3 1500 (2) 15x1 + 18x2 1800 (3) 20x2 + 22x3 2000 (4) x1 0， x2 0 x3 02. 写出以上问题的对偶问题； min w = 2400y1 + 1500 y2 +1800 y3 +2000 y4s.t. 12y1 + 6y2 + 15y3 120 (1) 8y1 + 10y2 + 18 y3 + 20 y4 180 (2) 10y1 + 15y2 +22y4 210 (3) y1 0， y2 0 y3 0 y4 03. 已知利润最大的线性规划问题的最优解是

15、产品A生产120件，产品B不生产，产品C生产52件，用互补松弛关系求四种原料的影子价格。 max z = 120x1 + 180 x2 +210 x3s.t. 12x1 + 8x2 +10 x3 +x4 = 2400 (1) 6x1 + 10x2 +15 x3 + x5 = 1500 (2) 15x1 + 18x2 + x6 = 1800 (3) 20x2 + 22x3 + x7 = 2000 (4) x10， x2 0 x3 0 x4 0 x5 0 x6 0 x7 0x4 =440 x5 =0 x6 =0 x7 =856 min w = 2400y1 + 1500 y2 +1800 y3 +2000 y4s.t. 12y1 + 6y2 + 15y3 - y5 = 120 (1) 8y1 + 10y2 + 18 y3 + 20 y4 - y6 = 180 (2) 10y1 + 15y