运筹学第二章题解

判断题判断正误，如果错误请更正第二章线形规划的对偶理论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为最优解,CX=Yb;(4)当CX=Yb 时,有YXs+YsX=0;(5)X为最优解且B是最优基时,则Y=C B B-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增加一个变量, 目标值不会比原来变差.18.减少一个非基变量, 目标值不变.19.当Cj(j=1,2,3,……，n)在允许的最大范围内同时变化时，最优解不变。

选择题在下列各题中，从4个备选答案中选出一个或从5个备选答案中选出2~5个正确答案。

第二章线性规划的对偶理论1.如果决策变量数列相等的两个线规划的最优解相同，则两个线性规划 A约束条件相同 B目标函数相同 C最优目标函数值相同 D以上结论都不对2.对偶单纯形法的最小比值规则是为了保证 A使原问题保持可行 B使对偶问题保持可行 C逐步消除原问题不可行性 D逐步消除对偶问题不可行性3.互为对偶的两个线性规划问题的解存在关系 A若最优解存在，则最优解相同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原问题与对偶问题都有最优解计算题线性规划问题和对偶问题对于如下的线性规划问题min z = 3x1 + 2x2+x3. x1 + x2+ x3 ≤ 15 (1)2x1 - x2+ x3≥ 9 (2)-x1 + 2x2+2x3≤ 8 (3)x1 x2x3 ≥ 01、写出题目中线性规划问题的对偶问题；2、分别求出原始问题和对偶问题的最优解（求解的次序和方法不限）；解答：1、写出题目中线性规划问题的对偶问题；解：max w = 15y1 + 9y2 + 8y3. y1 + 2y2- y3 ≤ 3 (1)y1 - y2+ 2y3≤ 2 (2)y1 + y2+ 2y3≤ 1 (3)y1≤0、 y2 ≥0、y3 ≤02、分别求出原始问题和对偶问题的最优解（求解的次序和方法不限）；解：先将原问题化成以下形式，则有mi n z = 3x1 + 2x2 + x3. x1 + x2+ x3+ x4= 15 (1)-2x1 + x2- x3+ x5= -9 (2)-x1 + 2x2+2x3+x6= 8 (3)原始问题的最优解为（X1 X2 X3 X4 X5 X6）=（2，0，5，8，0，0），minz=11 对偶问题的最优解为（y1y2y3y4y5y6）=（0，7/5，-1/5，0，19/5，0），maxw=11 对于以下线性规划问题max z = -x1 - 2x2. -2x1 + 3x2≤ 12 (1)-3x1 + x2≤ 6 (2)x1 + 3x2≥ 3 (3)x1≤ 0， x2≥ 01、写出标准化的线性规划问题；2、用单纯形表求出这个线性规划问题的最优解和最优的目标函数值；3、写出这个（极大化）线性规划问题的对偶问题；4、求出对偶问题的最优解和最优解的目标函数值；5、第（2）个约束右端常数b2=6在什么范围内变化，最优解保持不变。

第二章习题12、对于下面的线性规划问题，以()632,,A A A B =为基写出相对应的典式。

⎪⎪⎪⎩⎪⎪⎪⎨⎧=≥=+++-=++-=++-+-61,0108341242723..2min 63215214321321 j x x x x x x x x x x x x t s x x x j 解：由题可以知：⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡---=100834010042001213A []000121-=TC取一个基()654A A AB =，即：⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡-=183004021B 且⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡---=834042213N[]012-=T B C []001=TN C在matlab 中可以计算得到：⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡--=-14740812104101B []T b B b 39531-==-1-=b C T B ⎥⎦⎤⎢⎣⎡-=--8321451T N T B C N B C 由()N TN T B T B x C N B C b C Z --=-1可得典式的目标函数：5418321451x x x Z +---=由b Nx B x N B =+-1可得：⎪⎪⎪⎩⎪⎪⎪⎨⎧-=+---=+++=++-3947422558121453412165415431521x x x x x x x x x x x 由此与题中线性规划问题相对应的典式为：⎪⎪⎪⎪⎪⎪⎩⎪⎪⎪⎪⎪⎪⎨⎧=≥-=+---=+++=++-+---=6,,1,039474225581214534121..8321451min 65415431521541 j x x x x x x x x x x x x t s x x x Z j14、用单纯形法求解线面的线性规划问题，并在平面上画出迭代点走过的路线。

⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧≥≤≤+≤+≤+--=0,10443186052..2min 21221212121x x x x x x x x x t s x x z 解：由题先将题中线性规划问题化为标准形：⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧=≥=+=++=++=++--=6,,1,010*********..2min 6252142132121 j x x x x x x x x x x x x t s x x z j 由此可写出A ，即为：⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=100010010*********000152A则可以得出()6543A A A AB =是一个单位矩阵，且()010441860＞Tb =，所以基B 是可行基，6543,,,x x x x 为基变量，21,x x 为非基变量。

习题二2.1 写出下列线性规划问题的对偶问题(1) max z ＝10x1＋x2＋2x3(2) max z ＝2x1＋x2＋3x3＋x4st. x1＋x2＋2 x3≤10 st. x1＋x2＋x3 ＋x4≤54x1＋x2＋x3≤20 2x1－x2＋3x3＝－4x j≥0 （j＝1,2,3）x1－x3＋x4≥1x1，x3≥0，x2，x4无约束(3) min z ＝3x1＋2 x2－3x3＋4x4(4) min z ＝－5 x1－6x2－7x3st. x1－2x2＋3x3＋4x4≤3 st. －x1＋5x2－3x3≥15x2＋3x3＋4x4≥－5 －5x1－6x2＋10x3≤202x1－3x2－7x3 －4x4＝2＝x1－x2－x3＝－5 x1≥0，x4≤0，x2，，x3无约束x1≤0，x2≥0，x3无约束2.2 已知线性规划问题max z＝CX，AX=b，X≥0。

分别说明发生下列情况时，其对偶问题的解的变化：（1）问题的第k个约束条件乘上常数λ（λ≠0）；（2）将第k个约束条件乘上常数λ（λ≠0）后加到第r个约束条件上；（3）目标函数改变为max z＝λCX（λ≠0）；'x代换。

（4）模型中全部x1用312.3 已知线性规划问题min z＝8x1＋6x2＋3x3＋6x4st. x1＋2x2＋x4≥33x1＋x2＋x3＋x4≥6x3 ＋x4＝2x1 ＋x3 ≥2x j≥0（j＝1,2,3,4）(1) 写出其对偶问题；(2) 已知原问题最优解为x*＝（1，1，2，0），试根据对偶理论，直接求出对偶问题的最优解。

2.4 已知线性规划问题min z＝2x1＋x2＋5x3＋6x4 对偶变量st. 2x1 ＋x3＋x4≤8 y12x1＋2x2＋x3＋2x4≤12 y2x j≥0（j＝1,2,3,4）对偶问题的最优解y1*=4；y2*=1，试对偶问题的性质，求出原问题的最优解。

2.5 考虑线性规划问题max z＝2x1＋4x2＋3x3st. 3x1＋4 x2＋2x3≤602x1＋x2＋2x3≤40x1＋3x2＋2x3≤80x j≥0 （j＝1,2,3）４７４８（1）写出其对偶问题（2）用单纯形法求解原问题，列出每步迭代计算得到的原问题的解与互补的对偶问题的解；（3）用对偶单纯形法求解其对偶问题，并列出每步迭代计算得到的对偶问题解及与其互补的对偶问题的解；（4）比较（2）和（3）计算结果。

运筹学作业2（第二章部分习题）答案2．1 题 （P . 77） 写出下列线性规划问题的对偶问题：（1）123123123123123m ax 224..34223343500,z x x x s t x x x x x x x x x x x x =++⎧⎪++≥⎪⎪++≤⎨⎪++≤⎪≥≥⎪⎩无约束，；解：根据原—对偶关系表，可得原问题的对偶规划问题为：123123123123123m ax 235..223424334,0,0w y y y s t y y y y y y y y y y y y =++⎧⎪++≤⎪⎪++≤⎨⎪++=⎪≥≤≤⎪⎩（2）1111m in ,1,,,1,,0,1,,;1,,m n ij ij i j n ij ij i j nij ij j j ij z c x c x a i m c x b j nx i m j n====⎧=⎪⎪⎪==⎪⎨⎪⎪==⎪⎪≥==⎪⎩∑∑∑∑ 解：根据原—对偶关系表，可得原问题的对偶规划问题为：11m ax 1,,;1,,m n i i j ji j i j ij i w a u b v u v c i m j n u ==⎧=+⎪⎪⎪+≤⎨⎪==⎪⎪⎩∑∑ j 无约束，v 无约束2．2判断下列说法是否正确，为什么？（1） 如果线性规划的原问题存在可行解，则其对偶问题也一定存在可行解； 答：错。

因为：若线性规划的原问题存在可行解，且其对偶问题有可行解，则原问题和可行问题都将有最优解。

但，现实中肯定有一些问题是无最优解的，故本题说法不对。

例如原问题1212212m ax 31..30,0z x x x x s t x x x =++≥⎧⎪≤⎨⎪≥≥⎩有可行解，但其对偶问题1211212m in 33..10,0w y y y s t y y y y =+≥⎧⎪+≥⎨⎪≤≥⎩无可行解。

（2） 如果线性规划的对偶问题无可行解，则原问题也一定无可行解；答：错，如（1）中的例子。

第二章 对偶问题与灵敏度分析一、写出下列线性规划的对偶问题1、P89,(a)321422m in x x x Z ++=⎪⎪⎩⎪⎪⎨⎧≥=++≤++≥++.,0,;534;332;243321321321321无约束x x x x x x x x x x x x解：原模型可化为321422m in x x x Z ++=⎪⎪⎩⎪⎪⎨⎧≥=++≥≥++.,0,;534;3-3--2-;243321321321321321无约束x x x y y y x x x x x x x x x 于是对偶模型为321532m ax y y y W +-=⎪⎪⎩⎪⎪⎨⎧≥≤+-≤+-≤+-.,0,;4334;243;22321321321321无约束y y y y y y y y y y y y2、P89,(b)321365m ax x x x Z ++=⎪⎪⎩⎪⎪⎨⎧≤≥≤++≥-+-=++.0,0,;8374;35;522321321321321x x x x x x x x x x x x 无约束解：令033≥-='x x 原模型可化为321365m ax x x x Z '-+=⎪⎪⎩⎪⎪⎨⎧≥'≥≤'+≤'='+.0,0,;83-74;3--5-;52-2321321321321321x x x y y y x x x x x x x x x 无约束于是对偶模型为321835m in y y y W +-=⎪⎪⎩⎪⎪⎨⎧≥-≥---≥+-=++.0,,;332;6752;54321321321321y y y y y y y y y y y y 无约束 或⎪⎪⎩⎪⎪⎨⎧≥≤++≥+-=++.0,,;332;6752;54321321321321y y y y y y y y y y y y 无约束二、灵敏度分析1、P92, 线性规划问题213m ax x x Z += ⎪⎩⎪⎨⎧≥≤+≤+0,1025;74212121x x x x x x最优单纯形表如下试用灵敏度分析的方法，分析：（1） 目标函数中的系数21,c c 分别在什么范围内变化，最优解不变（2） 约束条件右端常数项21,b b 分别在什么范围内变化，最优基保持不变解：（1） 1c 的分析：要使得最优解不变，则需⎪⎪⎩⎪⎪⎨⎧≤⨯-⨯+=≤⨯+⨯-=034131003513201413c c σσ 即 ⎪⎩⎪⎨⎧≤≥42511c c 所以：4251≤≤c 时可保持最优解不变。

2.1 用图解法求解下列线性规划问题，并指出各问题具有唯一最优解、无穷多最优解、无界解还是无可行解。

（1）⎪⎪⎩⎪⎪⎨⎧≥≤-≤+≤++=0,84821234..2max 2121212121x x x x x x x x t s x x z解：首先划出平面直角坐标系4 x 1 +3x 2X 1⎩⎨⎧=+=-1234842121x x x x 解：⎪⎩⎪⎨⎧=14921x x 所以：2111492max =+⨯=z 所以有唯一解(2)⎪⎪⎩⎪⎪⎨⎧≥≤-≤+≤+-+=0,414234223max 2121212121x x x x x x x x x x 解：2=41⎩⎨⎧=+=+-1423422121x x x x 解得：⎪⎪⎩⎪⎪⎨⎧==4132521x x 所以:144132253max =⨯+⨯=z 因为直线02321=+x x 与直线142321=+x x 平行， 所以有无穷多最优解，max z=14（3） ⎪⎩⎪⎨⎧≥≤+-≤-+=0,432..32max 21212121x x x x x x t s x x z 解：（4）⎪⎩⎪⎨⎧≥-≤-≥-+=0,330..max 21212121x x x x x x t s x x z解：2.2将下列线性规划问题化为标准形式(1) s.t.⎪⎩⎪⎨⎧≥≤≤-+-=++-+-=无约束321321321321,0,0624322min x x x x x x x x x x x x z (2)⎪⎪⎩⎪⎪⎨⎧≤≥-=-+-≤+-≥--+=0,0232132..23min 3213213132321x x x x x x x x x x t s x x x z 无约束， 解：（1）令011≥-=x x )0'','('''33333≥-=x x x x x则上述形式可化为：)'''(32'2m ax 3321x x x x z --+=⎪⎩⎪⎨⎧≥=+--+=-++0,'',',,'6)'''('24)'''('..43321433213321x x x x x x x x x x x x x x t s（2）⎪⎪⎩⎪⎪⎨⎧≤≥-=-+-≤+-≥--+=0,0232132..23min 3213213132321x x x x x x x x x x t s x x x z 无约束， 解：令33'x x -= )0','','(322≥x x x 则上述形式可化为：')'''(23m ax 3221x x x x z ----=⎪⎪⎩⎪⎪⎨⎧≥=---=+--=+---0,,','',',2')'''(321')'''(3')'''(2..543221322153224322x x x x x x x x x x x x x x x x x x t s 2.3. 在下列线性规划问题中，找出所有基解，指出哪些是基可行解并分别代入目标函数，比较找出最优解。

第二章线性规划的对偶理论2.1 写出下列线性规划问题的对偶问题max z=2x1+2x2－4x3x1 + 3x2 + 3x3 ≤304x1 + 2x2 + 4x3≤80x1、x2，x3≥0解：其对偶问题为min w=30y1+ 80y2y1+ 4y2≥23y1 + 2y2 ≥23y1 + 4y2≥－4y1、y2≥02.2 写出下列线性规划问题的对偶问题min z=2x1+8x2－4x3x1 + 3x2－3x3 ≥30－x1 + 5x2 + 4x3 = 804x1 + 2x2－4x3≤50x1≤0、x2≥0，x3无限制解：其对偶问题为max w=30y1+80 y2+50 y3y1－y2 + 4 y3≥23y1+5y2 + 2y3≤8－3y1 + 4y2－4y3 =－4y1≥0，y2无限制，y3≤02.3已知线性规划问题max z=x1+2x2+3x3+4x4x1 + 2x2 + 2x3 +3x4≤202x1 + x2 + 3x3 +2x4≤20x1、x2，x3，x4≥0其对偶问题的最优解为y1*=6/5，y2*=1/5。

试用互补松弛定理求该线性规划问题的最优解。

解：其对偶问题为min w=20y1+ 20y2y1 + 2y2≥1 （1）2y1 + y2 ≥2 （2）2y1 +3y2≥3 （3）3y1 +2y2≥4 （4）y1、y2≥0将y1*=6/5，y2*=1/5代入上述约束条件，得（1）、（2）为严格不等式；由互补松弛定理可以推得x1*=0，x2*=0。

又因y1*>0，y2*>0，故原问题的两个约束条件应取等式，所以2x3*+3x4* = 203x3* +2x4* = 20解得x3* = x4* = 4。

故原问题的最优解为X*=（0，0，4，4）T2.4用对偶单纯形法求解下列线性规划min z=4x1+2x2+6x32x1 +4x2 +8x3 ≥244x1 + x2 + 4x3≥8x1、x2，x3≥0解将问题改写成如下形式max（－z）=－4x1－2x2－6x3－2x1－4x2 －8x3 + x4=－24－4x1－x2－4x3+x5 =－8x1、x2，x3，x4，x5≥0显然，p4、p5可以构成现成的单位基，此时，非基变量在目标函数中的系数全为负数，因此p4、p5构成的就是初始正侧基。

第二章补充作业习题：用大M 法和两阶段法求解下面LP 问题：⎪⎪⎩⎪⎪⎨⎧≥≥+-≥-+=0,3232s.t.42min 21212121x x x x x x x x z解： 标准化为⎪⎪⎩⎪⎪⎨⎧≥=-+-=----=0,,,3232s.t.42max 432142132121x x x x x x x x x x x x z（1）大M 法引入人工变量65,x x ，得到下面的LP 问题⎪⎪⎪⎪⎨⎧=≥=+-+-=+------=6,,1,03232s.t.42max 642153216521 j x x x x x x x x x Mx Mx x x z j因为人工变量6x 为4>0，所以原问题没有可行解。

（2）两阶段法：增加人工变量65,x x ，得到辅助LP 问题⎪⎪⎩⎪⎪⎨⎧=≥=+-+-=+----=6,,1,03232s.t.max 6421532165 j x x x x x x x x x x x g j初始表因为辅助LP 问题的最优值为4>0，所以原问题没有可行解。

习2.1 解：设1x 为每天生产甲产品的数量，2x 为每天生产乙产品的数量，则数学模型为,5183202..200300max 211212121≥≤≤+≤++=x x x x x x x t s x x z最优解为：()TX 4.8,2.3*=，最优值为：z = 2640。

（1）最优解为：()TX 5.0,5.1*=，最优值为：z = 4.5。

（2）无可行解有无穷多最优解，其中一个为：TX⎪⎭⎫⎝⎛=0,310*1，另一个为：()TX10,0*2=，最优值为：z = 20。

（4）无界解解：A B 资源限额 会议室 1 1 5 桌子 3 2 12 货架 3 6 18 工资2522设1x 为雇佣A 的天数，2x 为雇佣B 的天数，则数学模型为,186312235..2225min 2121212121≥≥+≥+≥++=x x x x x x x x t s x x z最优解为：()TX3,2*=，最优值为：z = 116。

第二章线性规划的对偶理论2.1 写出下列线性规划问题的对偶问题max z=2x1+2x2－4x3x1 + 3x2 + 3x3 ≤304x1 + 2x2 + 4x3≤80x1、x2，x3≥0解：其对偶问题为min w=30y1+ 80y2y1+ 4y2≥23y1 + 2y2 ≥23y1 + 4y2≥－4y1、y2≥02.2 写出下列线性规划问题的对偶问题min z=2x1+8x2－4x3x1 + 3x2－3x3 ≥30－x1 + 5x2 + 4x3 = 804x1 + 2x2－4x3≤50x1≤0、x2≥0，x3无限制解：其对偶问题为max w=30y1+80 y2+50 y3y1－y2 + 4 y3≥23y1+5y2 + 2y3≤8－3y1 + 4y2－4y3 =－4y1≥0，y2无限制，y3≤02.3已知线性规划问题max z=x1+2x2+3x3+4x4x1 + 2x2 + 2x3 +3x4≤202x1 + x2 + 3x3 +2x4≤20x1、x2，x3，x4≥0其对偶问题的最优解为y1*=6/5，y2*=1/5。

试用互补松弛定理求该线性规划问题的最优解。

解：其对偶问题为min w=20y1+ 20y2y1 + 2y2≥1 （1）2y1 + y2 ≥2 （2）2y1 +3y2≥3 （3）3y1 +2y2≥4 （4）y1、y2≥0将y1*=6/5，y2*=1/5代入上述约束条件，得（1）、（2）为严格不等式；由互补松弛定理可以推得x1*=0，x2*=0。

又因y1*>0，y2*>0，故原问题的两个约束条件应取等式，所以2x3*+3x4* = 203x3* +2x4* = 20解得x3* = x4* = 4。

故原问题的最优解为X*=（0，0，4，4）T2.4用对偶单纯形法求解下列线性规划min z=4x1+2x2+6x32x1 +4x2 +8x3 ≥244x1 + x2 + 4x3≥8x1、x2，x3≥0解将问题改写成如下形式max（－z）=－4x1－2x2－6x3－2x1－4x2 －8x3 + x4=－24－4x1－x2－4x3+x5 =－8x1、x2，x3，x4，x5≥0显然，p4、p5可以构成现成的单位基，此时，非基变量在目标函数中的系数全为负数，因此p4、p5构成的就是初始正侧基。