第二章对偶理论与灵敏度分析练习题答案

i i ii第二章 线性规划的对偶理论和灵敏度分析自测题1. 判断下述说法是否正确(1) 任何线性规划问题存在并具有唯一的对偶问题。

(2) 线性规划原问题的对偶问题的对偶是原问题本身。

(3) 原问题的任一可行解对应的目标函数值都不超过其对偶问题的任一可行解对应的目标函数值。

(4) 已知对偶问题的最优解中， y * > 0 ，则原问题中在资源最优配置下，第i 种资源已完全消 耗殆尽。

(5) 已知对偶问题的最优解中， y * = 0 ，则原问题中在资源最优配置下，第 i 种资源一定未 完全消耗。

(6) 影子价格就是市场价格。

(7) 若第 i 种资源的影子价格为 y * > 0 ，则在保持原问题中其它条件不变时，在资源最优配置下，当第i 种资源增加10个单位时，最优值将一定增加10 y * .(8) 在应用对偶单纯形法计算时，若在某一个单纯形表中，出现某行除该行对应的基变量值小于0外，该行其余元素全部大于或等于0，则可以判断该线性规划问题无最优解。

(9) 在应用对偶单纯形法计算时，若在某一个单纯形表中，出现某行除该行对应的基变量值小于0外，该行其余元素全部小于或等于0，则可以判断该线性规划问题的对偶问题无最优解。

(10)线性规划的原问题和其对偶问题的最优值如果存在，则必然相等。

(11)线性规划问题的最终单纯形表中，当仅某一非基变量在目标函数中的系数变化时，线性规划问题的最优解一定不改变。

(12)线性规划问题的最终单纯形表中，当仅有某一基变量在目标函数中的系数变化时，线性规划问题的最优解一定不改变。

(13)线性规划问题的最终单纯形表中，当仅有某一非基变量在系数矩阵中的列变化时，线性规划问题的最优解一定不改变。

(14)线性规划问题的最终单纯形表中，当仅有某一基变量在系数矩阵中的列变化时，线性规划问题的最优解一定不改变。

(15)线性规划问题的最终单纯形表中，当仅有某种资源的数量变化时，线性规划问题的最优值一定改变。

第一章 线性规划及单纯形法（作业）1.4 分别用图解法和单纯型法求解下列线性规划问题，并对照指出单纯形表中的各基可行解对应图解法中可行域的哪一顶点。

（1）Max z=2x 1+x 2St.⎪⎩⎪⎨⎧≥≤+≤+0,24261553212121x x x x x x 解：①图解法：由作图知，目标函数等值线越往右上移动，目标函数越大，故c 点为对应的最优解，最优解为直线⎩⎨⎧=+=+242615532121x x x x 的交点，解之得X=(15/4,3/4)T 。

Max z =33/4. ② 单纯形法：将上述问题化成标准形式有： Max z=2x 1+x 2+0x 3+0x 4St. ⎪⎩⎪⎨⎧≥≤++≤++0,,,242615535421421321x x x x x x x x x x其约束条件系数矩阵增广矩阵为：P 1 P 2 P 3 P 4⎥⎦⎤⎢⎣⎡241026150153 P 3,P 4为单位矩阵，构成一个基，对应变量向，x 3,x 4为基变量，令非基变量x 1,x 2为零，找到T 优解，代入目标函数得Max z=33/4.1.7 分别用单纯形法中的大M 法和两阶段法求解下列线性规划问题，并指出属哪一类。

（3）Min z=4x 1+x 2⎪⎪⎩⎪⎪⎨⎧=≥=++=-+=+)4,3,2,1(0426343342132121j xj x x x x x x x x 解：这种情况化为标准形式： Max z ＇=-4x 1-x 2⎪⎪⎩⎪⎪⎨⎧=≥=++=-+=+)4,3,2,1(0426343342132121j xj x x x x x x x x 添加人工变量y1,y2Max z ＇=-4x 1-x 2+0x 3+0x 4-My 1-My 2⎪⎪⎩⎪⎪⎨⎧≥=≥=++=+-+=++0,).4,3,2,1(04263433214112321121y y j xj x x x y x x x y x x(2) 两阶段法： Min ω=y 1+y 2St.⎪⎪⎩⎪⎪⎨⎧≥=≥=++=+-+=++0,).4,3,2,1(04263433214112321121y y j xj x x x y x x x y x x第二阶段，将表中y 1,y 2去掉，目标函数回归到Max z ＇=-4x 1-x 2+0x 3+0x 4第二章 线性规划的对偶理论与灵敏度分析（作业）2.7给出线性规划问题：Max z=2x 1+4x 2+x 3+x 4⎪⎪⎪⎩⎪⎪⎪⎨⎧=≥≤++≤++≤+≤++)4,3,2,1(096628332143221421j x x x x x x x x x x x x j要求：（1）写出其对偶问题；（2）已知原问题最优解为X *=(2,2,4,0),试根据对偶理论，直接求出对偶问题的最优解。

第一部分绪论第二部分线性规划与单纯形法1 判断下列说法是否正确：(a)图解法同单纯形法虽然求解的形式不同,但从几何上理解,两者是一致的；(b)线性规划模型中增加一个约束条件,可行域的范围一般将缩小,减少一个约束条件,可行域的范围一般将扩大；(c)线性规划问题的每一个基解对应可行域的一个顶点；(d)如线性规划问题存在可行域,则可行域一定包含坐标的原点；(e)对取值无约束的变量x i,通常令其中,在用单纯形法求得的最优解中有可能同时出现(f)用单纯形法求解标准型的线性规划问题时,与对应的变量都可以被选作换入变量；(g)单纯形法计算中,如不按最小比值原则选取换出变量,则在下一个解中至少有一个基变量的值为负；(h)单纯形法计算中,选取最大正检验数δk对应的变量x k作为换入变量,将使目标函数值得到最快的增长；(i)一旦一个人工变量在迭代中变为非基变量后,则该变量及相应列的数字可以从单纯形表中删除,而不影响计算结果；(j)线性规划问题的任一可行解都可以用全部基可行解的线性组合表示；(k)若x1,x2分别是某一线性规划问题的最优解,则也是该线性规划问题的最优解,其中λ1,λ2可以为任意正的实数；(1)线性规划用两阶段法求解时,第一阶段的目标函数通常写为X ai为人工变量),但也可写为,只要所有k i均为大于零的常数；(m)对一个有n个变量、m个约束的标准型的线性规划问题,其可行域的顶点恰好为个；(n)单纯形法的迭代计算过程是从一个可行解转转换到目标函数值更大的另一个可行解；(o)线性规划问题的可行解如为最优解,则该可行解一定是基可行解；(p)若线性规划问题具有可行解,且其可行域有界,则该线性规划问题最多具有有限个数的最优解；(q)线性规划可行域的某一顶点若其目标函数值优于相邻的所有顶点的目标函数值,则该顶点处的目标函数值达到最优；(r)将线性规划约束条件的“≤”号及“≥”号变换成“＝”号,将使问题的最优目标函数值得到改善；(s)线性规划目标函数中系数最大的变量在最优解中总是取正的值；(t)一个企业利用3种资源生产4种产品,建立线性规划模型求解得到的最优解中,最多只含有3种产品的组合；(u)若线性规划问题的可行域可以伸展到无限,则该问题一定具有无界解；(v)一个线性规划问题求解时的迭代工作量主要取决于变量数的多少,与约束条件的数量关系相对较小。

第二章 对偶理论与灵敏度分析练习题答案1．判断下列说法是否正确：(1) 任何线性规划问题存在并具有惟一的对偶问题；(✓)(2) 根据对偶问题的性质，当原问题为无界解时，其对偶问题无可行解，反之，当对偶问题无可行解时，其原问题具有无界解；(✗)(3) 设j ˆx ，i ˆy 分别为标准形式的原问题与对偶问题的可行解，*j x ，*i y 分别为其最优解，则恒有n n m m**j j j j i i i i j 1j 1i 1i 1ˆˆc x c x b y b y ====≤=≤∑∑∑∑；(✓)(4) 若线性规划的原问题有无穷多最优解，则其对偶问题也一定具有无穷多最优解；(✓)(5) 已知*i y 为线性规划的对偶问题的最优解，若*i y 0>，说明在最优生产计划中第i 种资源已完全耗尽；(✓)(6) 已知*i y 为线性规划的对偶问题的最优解，若*i y 0=，说明在最优生产计划中第i 种资源一定有剩余；(✗)(7) 若某种资源的影子价格等于k ，在其他条件不变的情况下，当该种资源增加5个单位时，相应的目标函数值将增大5k ；(✗)(8) 应用对偶单纯形法计算时，若单纯形表中某一基变量i x 0<，又x i 所在行的元素全部大于或等于零，则可以判断其对偶问题具有无界解；(✓)(9) 若线性规划问题中的b i ，c j 值同时发生变化，反映到最终单纯形表中，不会出现原问题与对偶问题均为非可行解的情况；(✗)(10) 在线性规划问题的最优解中，如某一变量x j 为非基变量，则在原来问题中，无论改变它在目标函数中的系数c j 或在各约束中的相应系数a ij ，反映到最终单纯形表中，除该列数字有变化外，将不会引起其他列数字的变化。

(✓)2．下表是某一约束条件用“≤”连接的线性规划问题最优单纯形表格，其中x 4、x 5为松弛变量。

要求：(1)(3)其它条件不变时，约束条件右端项b 1在何范围内变化，上述最优基不变。

第二章.对偶理论与灵敏度分析1. 已知线性规划问题：332211m a xx c x c x c z ++= ⎪⎩⎪⎨⎧=≥⎥⎦⎤⎢⎣⎡=⎥⎦⎤⎢⎣⎡+⎥⎦⎤⎢⎣⎡+⎥⎦⎤⎢⎣⎡+⎥⎦⎤⎢⎣⎡+⎥⎦⎤⎢⎣⎡)5,,1(01001.2154323132221212111 j x b b x x x a a x a a x a a st j 用单纯形法求解得最终单纯形表如下表所示： （a ） 求232221131211,,,,,a a a a a a 和21,b b321,,c c c 8,4,7,5,8,2,4,1,1,2/5,2/932121231322122111===========c c c b b a a a a a a2. 已知矩阵A 及其逆矩阵1-A 如下：⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡=104020012A ⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡--=-11202/1004/12/11A试根据改进单纯形法中求逆矩阵的方法原理求下述矩阵B 的逆矩阵1-B，已知⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡-=144210152B答：先设⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡-=144010052C ⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡--=⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡-∙-72/14/114151A∴⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡--=∙⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡--=--16201002/52/1114002002/11111A C ⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡-=144210152B 有 ⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡--=⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡∙-1322/111211C∴⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡-----=∙⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡--=--26/226/1226/426/426/226/826/1126/126/913/10013/21026/110111C B3. 已知线性规划的原问题与对偶问题分别为：（P ）原问题：CX z =max (D)对偶问题：Yb w =min⎩⎨⎧≥≤0.X b AX st ⎩⎨⎧≥≥0Y C YA st若*Y 为对偶问题最优解，又原问题约束条件右端项用b 替换之后其最优解为X ，试证明有b Y X C *≤证明：原问题右端项b 用b 替换后，新的原问题'P 及对偶问题'D 为：:'P ⎩⎨⎧≥≤=0.'m a x Z b AZ st CZz :'D ⎩⎨⎧≥≤=0.min 'Y C YA st bY w设'D 的最优解为Y ，因有b Y Z C =，有*Y 是'D 的可行解，故有b Y b Y *≤，由此b Y Z C *≤4. 已知下表为求解某线性规划问题的最终单纯形表，表中54,x x 为松弛变量，问题的约束(b) 直接由表写出对偶问题的最优解。

线性规划的对偶理论与灵敏度分析习题1第二章 线性规划的对偶理论与灵敏度分析习题1. 写出下列线性规划问题的对偶问题。

(1)⎪⎪⎩⎪⎪⎨⎧≥=++≤++≥++++=无约束321321321321321,0,534332243422min x x x x x x x x x x x x x x x z (2)⎪⎪⎩⎪⎪⎨⎧≤≥≤++≥-+-=++++=0,0,837435522365max 321321321321321x x x x x x x x x x x x x x x z 无约束(3)⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧==≥=====∑∑∑∑====),,1;,,1(0),,1(),,1(min 1111n j m i x n j b x m i a x x c z ij mi j ij nj i ij m i ijnj ij2(4)⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧=≥++==<=<=∑∑∑===),,,,1(0),,2,1(),,1(min 1211111n n j x m m m i b x a m m i b x a x c z j nj i j ij nj i j ij nj jj 无约束2. 判断下列说法是否正确，为什么? (1)如果线性规划的原问题存在可行解，则其对偶问题也一定存在可行解；(2)如果线性规划的对偶问题无可行解，则原问题也一定无可行解；( 3)在互为对偶的一对原问题与对偶问题中，不管原问题是求极大或极小，原问题可行解的目标函数值一定不超过其对偶问题可行解的目标函数值；(4)任何线性规划问题具有唯一的对偶问题。

3. 已知某求极大化线性规划问题用单纯形法求解时的初始单纯形表及最终单纯形表如下表所示，求表中各括弧内未知数的值。

3 2 2 0 0 03C B 基 B x 1 x 2 x 3 x 4 x 5 x 60 x 4 (b) 11 1 1 0 02 x 5 15 (a) 1 2 0 1 0 1 x 6 202 (c )1 0 01jj z c -0 2 0 0 00 x 4 5/4 0 0(d ) (l ) -1/4 -1/4 3 x 125/410 (e ) 0 3/4 (i ) 2 x 2 5/2 01 (f ) 0 (h ) 1/2 jj z c --1(k) (g)-5/4(j)4. 给出线性规划问题⎪⎩⎪⎨⎧=≥-≤+-+-≥++++++=)4,,1(0322326532min 432143214321 j x x x x x x x x x x x x x z j(1)写出其对偶问题；(2)用图解法求解对偶4问题；(3)利用(2)的结果及根据对偶问题性质写出原问题最优解。

一、填空题1、对偶问题的对偶问题是（）。

正确答案：原问题2、若X﹡和Y﹡分别是线性规划的原问题和对偶问题的最优解，则有CX﹡（）Y﹡b。

正确答案：=3、若X、Y分别是线性规划的原问题和对偶问题的可行解，则有CX（）Yb。

正确答案：<=4、若X﹡和Y﹡分别是线性规划的原问题和对偶问题的最优解，则有CX﹡（）Y*b。

正确答案：=5、设线性规划的原问题为maxZ=CX，Ax≤b，X≥0，则其对偶问题为（）。

正确答案：min=Yb YA>=c Y>=06、影子价格实际上是与原问题各约束条件相联系的（）的数量表现。

正确答案：对偶变量7、线性规划的原问题的约束条件系数矩阵为A，则其对偶问题的约束条件系数矩阵为（）。

正确答案：AT8、在对偶单纯形法迭代中，若某bi<0，且所有的aij≥0(j=1，2，…n)，则原问题（）。

正确答案：无解二、选择题1、线性规划原问题的目标函数为求极小值型，若其某个变量小于等于0，则其对偶问题约束条件为（）形式。

A. “≥”B. “≤”C. “>”D. “=”正确答案：A2、如果z*是某标准型线性规划问题的最优目标函数值，则其对偶问题的最优目标函数值w﹡满足（）。

A.W﹡=Z﹡B.W﹡≠Z﹡C.W﹡≤Z﹡D.W﹡≥Z﹡正确答案：A3、如果某种资源的影子价格大于其市场价格，则说明（）。

A.该资源过剩B.该资源稀缺C.企业应尽快处理该资源D.企业应充分利用该资源，开辟新的生产途径正确答案：B4、线性规划原问题的目标函数为求极小值型，若其某个变量小于等于0，则其对偶问题约束条件为（）形式。

A.≥B.≤C. >D. =正确答案：A5、对偶单纯形法的迭代是从（）开始的。

A.正则解B.最优解C.可行解D.可行解正确答案：A6、如果某种资源的影子价格大于其市场价格，则说明（）。

A.该资源过剩B.该资源稀缺C.企业应尽快处理该资源D.企业应充分利用该资源，开辟新的生产途径正确答案：B7、线性规划灵敏度分析的主要功能是分析线性规划参数变化对（）的影响。

第二章对偶理论与灵敏度分析A4第二章对偶理论与灵敏度分析本章内容重点：1、线性规划的对偶问题概念、理论及经济意义；2、线性规划的对偶单纯形法；3、线性规划的灵敏度分析。

线性规划有一个有趣的特性，就是每一个LP问题都存在一个与之相应的LP问题，我们称其中任一个为原问题（记为LP），另一个为对偶问题（记为DP）。

线性规划的这个特性称为对偶性。

线性规划有一个有趣的特性，就是每一个LP问题都存在一个与之相应的LP问题，我们称其中任一个为原始问题（记为LP），另一个为对偶问题（记为DP）。

线性规划的这个特性称为对偶性。

研究线性规划的对偶问题，不仅可以获得许多原始问题的知识，还可以得到原始问题不易直接弄清楚的问题，从而有利于原始问题的求解。

在这一章中，我们将从经济意义上研究线性规划的对偶问题，揭示原问题与对偶问题之间的关系，间接地获得更多的有用的信息，为企业经营决策提供更多的科学依据。

§1 线性规划的对偶问题一、 LP对偶问题的提出例1某工厂拥有A、B、C三种类型的设备，生产甲、乙两种产品。

每件产品在生产中需要占用的设备台时数，每件产品可获得的利润以及三种设备可利用的台时数如下表所示。

求获取利润最大的生产方案。

甲产品乙产品每天设备台时限制设备A0515设备B6224设备C115利润（万元/21吨）这个问题的数学模型与第一章例2类似，设x1, x2分别为产品甲、乙的计划日产量，则有：Max z = 2x1 + x2s.t. 5x2 ≤ 156x1 + 2x2 ≤ 24x1 + x2 ≤ 5x1 , x2 ≥ 0求解得每天最大利润8.5万元。

现在我们从另一个角度来考虑这个问题。

假如有另一个企业要求租用该厂的设备A、B、C，那么该厂的厂长应该如何来确定合理的租金呢？一般来说，有两点需要考虑，一是该厂出租设备要合算；二是要价合理。

所谓合算，就是出租的收入不少于生产利润8.5万元。

而要价合理，就是在合算的前提下，租金要尽量低，这样才能吸引求租者。