第二章对偶问题一般题答案

第2章 对偶问题判断下列说法是否正确：对偶问题的对偶问题一定是原问题；根据对偶问题的性质，当原问题为无界解时，其对偶问题无可行解，反之，当对偶问题无可行解时，其原问题具有无界解； 已知*i y 为线性规划的对偶问题的最优解，若*i y >0，说明在最优生产计划中的i 种资源已完全耗尽；已知*i y 为线性规划的对偶问题的最优解，若*i y ＝0，说明在最优生产计划中第i 种资源一定有剩余；若某种资源的影子价格等于k ，在其它条件不变的情况下，当改种资源增加5个单位时，相应的目标函数值将增大5k ； 在线性规划问题的最优解中，如某一变量j x 为非基变量，则在原来问题中，无论改变它在目标函数中的系数j c 或在各约束中的相应系数ij a ，反映到最终单纯形表中，除该列数字有变化外，将不会引起其它列数字的变化。

简答题、试述对偶单纯形法的优点及其应用上的局限性。

、试述对偶单纯形法的步骤。

、试解释对偶解的经济含义和影子价格在市场决策中的作用。

、什么是资源的影子价格？同相应的市场价格之间有何区别？以及研究影子价格的意义是什么？:判断下列说法是否正确，为什么？（a ）如果线性规划的原问题存在可行解，则其对偶问题也一定存在可行解； （b ）如果线性规划的对偶问题存在可行解，则其原问题也一定无可行解；（c ）在互为对偶的一对原问题和对偶问题中，不管原问题是求极大或极小，原问题可行解的目标函数都一定不超过其对偶问题可行解的目标函数。

若某种资源的影子价格等于k ，在其他条件不变的情况下，当该种资源增加5个单位时，相应的目标函数最大值将增加5k 吗？ 已知*i y 为某线性规划问题的对偶问题最优解中的第i 分量，若*i y ＝0，能否肯定在最优生产计划种第i 种资源一定有剩余？写出对偶问题写出下列线性规划问题的对偶问题123max 102Z x x x =++123123123420,,0x x x x x x ++≤≥写出下列线性规划问题的对偶问题1234max 23Z x x x x =+++12341231341324252341,0,,x x x x x x x x x x x x x x +++≤-+=--+≥≥无约束写出下列线性规划问题的对偶问题1234min 3234Z x x x x =+-+1234234123414232343345237420,0,,x x x x x x x x x x x x x x x -++≤++≥----=≥≤无约束写出下列线性规划问题的对偶问题123min 567Z x x x =---123123123123531556102050,0,x x x x x x x x x x x x -+-≥--+≤--=-≤≥无约束写出下列线性规划问题的对偶问题123max 25Z x x x =++12312313123235237365,,0x x x x x x x x x x x ++≤++≤+≤≥写出下列线性规划问题的对偶问题123max Z x x x =++1231312327664,,0x x x x x x x x ++=+≥≥写出下列线性规划问题的对偶问题123min 423Z x x x =++123123131232562742,0,0x x x x x x x x x x x ++≤++=+≥≤≥无约束写出下列线性规划问题的对偶问题：1231231231231232242352373..465,,0MinZ x x x x x x x x x s t x x x x x x =++++≥⎧⎪++≤⎪⎨++≤⎪⎪≥⎩写出下列线性规划问题的对偶问题：12312312312312323231325..34,,0,MinZ x x x x x x x x x s t x x x x x x =--+-=⎧⎪-+≥-⎪⎨-+≤⎪⎪≥⎩无限制写出下列线性规划问题的对偶问题：123123123131232423134..40,0,MaxZ x x x x x x x x x s t x x x x x =++++≥⎧⎪-+≤⎪⎨+=⎪⎪≥≤⎩无限制写出下列线性规划问题的对偶问题：1234512345123451~45275354625..232690,MaxZ x x x x x x x x x x s t x x x x x x x =++++++++=⎧⎪++++=⎨⎪≥⎩无限制写出下面线性规划问题的对偶问题12max 52z x x =-+1212123235,0x x x x x x -+≤-+≤≥写出下面线性规划问题的对偶问题12max 56z x x =+12122553x x x x +=-+≥1x 无限制2,0x ≥设有原始问题123max 325z x x x =++约束条件：12313121232560324204400,,0x x x x x x x x x x ++≤+≤+≤≥写出以上原始问题的对偶问题。

对偶问题习题● 证明题(选做)1． 证明下面的线性规划问题要么无解，要么最优目标函数值为零，其中C 为n 维向量，b 为m 维向量，A 为m n ⨯矩阵。

min ..0,0yb cxAx bs t yA c x y -≤⎧⎪≥⎨⎪≥≥⎩证明 把问题拆成两个问题(A)max ..0z cxAx b s t x =≤⎧⎨≥⎩ 和 (B)min ..0w ybyA c s t y =≥⎧⎨≥⎩显然两个问题为原问题和对偶问题，分四种情形讨论：情形1 如果两个问题都有可行解，那么两个问题都有最优解，且最优目标函数值相等。

根据对偶理论，由于有cx yb ≤，因此0yb cx -≥。

而**y b cx -=0，因而该情形下有解，且最优解为0。

情形2 如果问题A 有解但为无穷解，那么B 问题一定无解，也就是yA c ≥不成立，从而该情形下无解。

情形3 如果问题B 有解但为无穷解，那么A 问题一定无解，也就是Ax b ≤不成立，从而该情形下无解。

情形4 如果问题A 和问题B 均无解，那么Ax b ≤和yA c ≥都不成立，从而该情形下也无解。

综合上述，根据对偶理论只可能有如上情形，从而命题成立。

2． 设线性规划问题1是11max ..0(1)nj jj nij ji j jz c x a x b s t x j n 1== =⎧≤⎪⎨⎪≥≤≤⎩∑∑ 其中***12(,,,)m y y y 是其对偶问题的最优解。

又设线性规划问题2是11max ..0(1)nj jj nij ji i j jz c x a x b k s t x j n 2== =⎧≤+⎪⎨⎪≥≤≤⎩∑∑ 其中i k 是给定的常数，求证*211max()max()mi ii z z k y=≤+∑证明 问题1的对偶问题为11221min ...,1,2,...,..0m mmij i j i iw b y b y b y a y c j ns t y = =+++⎧≥=⎪⎨⎪≥⎩∑问题2的对偶问题为1112221min ()()...(),1,2,...,..0m m mmij i j i iw b k y b k y b k y a y c j ns t y = =++++++⎧≥=⎪⎨⎪≥⎩∑既然***12(,,,)m y y y 是问题1的对偶问题最优解，那么必有 ***11122max()...m mz b y b y b y =+++ 又由于***12(,,,)m y y y 是问题1的对偶问题的可行解，那么有***2111222******11221122***11122max()()()...() ...(...) max()(...)m m mm m m m m m z b k y b k y b k y b y b y b y k y k y k y z k y k y k y ≤++++++=+++++++=++++ 3． 设线性规划问题1是11min (1)..0(1)nj jj nij ji j jz c x a x b i m s t x j n 1== =⎧=≤≤⎪⎨⎪≥≤≤⎩∑∑ 又设线性规划问题2是*11min ()(1,)..0(1)nj k kj jj nij ji j jz c y a x a x b i m i k s t x j n 2== =-⎧≤≤≤≠⎪⎨⎪≥≤≤⎩∑∑ 设***12(,,,)n x x x 是线性规划问题1的最优解，***12(,,,)m y y y 为其对偶问题的最优解，请证明***12(,,,)n x x x 也是问题2的最优解。

第二章线性规划的对偶问题习题2.1写出下列线性规划问题的对偶问题(1)maxz＝10x1＋x2＋2x3(2)maxz＝2x1＋x2＋3x3＋x4st.x1＋x2＋2x3≤10st.x1＋x2＋x3＋x4≤54x1＋x2＋x3≤202x1－x2＋3x3＝－4x j ≥0（j＝1,2,3）x1－x3＋x4≥1xj≥0（j＝1,2,3,4）其对偶问题的最优解y1*=4；y2*=1，试根据对偶问题的性质，求出原问题的最优解。

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

2.6已知线性规划问题maxz＝10x1＋5x2st.3x1＋4x2≤95x1＋2x2≤8xj≥0（j＝1,2）（1）给出a，b，c，d，e，f，g的值或表达式；（2）指出原问题是求目标函数的最大值还是最小值；（3）用a+?a，b+?b分别代替a和b，仍然保持上表是最优单纯形表，求?a，?b满足的范围。

仅供个人学习参考仅供个人学习参考2.9某文教用品厂用原材料白坯纸生产原稿纸、日记本和练习本三种产品。

该厂现有工人100人，每月白坯纸供应量为30000千克。

已知工人的劳动生产率为：每人每月可生产原稿纸30捆，或日记本30打，或练习本30箱。

已知原材料消耗为：每捆原稿纸用白坯纸310千克，每打日记本用白坯纸340千克，每箱练习本用白坯纸380千克。

又知每生产一捆原稿纸可获利2元，生产一打日记本获利3元，生产一箱练习本获利1元。

试确定：（1）现有生产条件下获利最大的方案；（2）如白坯纸的供应数量不变，当工人数不足时可招收临时工，临时工工资支出为每人每月40元，则该厂要不要招收临时工？如要的话，招多少临时工最合适？2.10某厂生产甲、乙两种产品，需要A 、B 两种原料，生产消耗等参数如下表（表中2.12试从经济上解释对偶问题及对偶变量的含义。

第二章 对偶问题与灵敏度分析一、写出下列线性规划的对偶问题1、P89,2.1(a)321422m in x x x Z ++=s.t ⎪⎪⎩⎪⎪⎨⎧≥=++≤++≥++.,0,;534;332;243321321321321无约束x x x x x x x x x x x x解：原模型可化为321422m in x x x Z ++=s.t ⎪⎪⎩⎪⎪⎨⎧≥=++≥≥++.,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 +-=s.t ⎪⎪⎩⎪⎪⎨⎧≥≤+-≤+-≤+-.,0,;4334;243;22321321321321无约束y y y y y y y y y y y y2、P89,2.1(b)321365m ax x x x Z ++=s.t ⎪⎪⎩⎪⎪⎨⎧≤≥≤++≥-+-=++.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 '-+=s.t ⎪⎪⎩⎪⎪⎨⎧≥'≥≤'+≤'='+.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 +-=s.t ⎪⎪⎩⎪⎪⎨⎧≥-≥---≥+-=++.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, 2.11线性规划问题213m ax x x Z += s.t ⎪⎩⎪⎨⎧≥≤+≤+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) 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.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构成的就是初始正侧基。