线性规划的对偶理论与灵敏度分析习题

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

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

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

第二章.对偶理论与灵敏度分析1. 已知线性规划问题： 332211m ax x 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.'max 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、研究线性规划对偶问题的经济意义何在？因为线性规划往往解决原料、设备、资金、人力等资源的最优配置问题，因此了解资源在最优配置下所创造的（边际）价值即机会成本或机会收益对于成本分析、资源计划、投资计划等都有较重要的作用。

此外，对偶规划也常和对资源的灵敏度分析联系在一起，对于更好地在变化环境中配置资源有一定的指导意义。

2、已知原线性规划问题如何写出其对偶问题？（1）如果原问题是MAX问题，则其对偶问题是MIN问题。

按下表可将其对偶问题写出。

（2）如果原问题是MIN问题，则其对偶问题是MAX问题。

按下表可将其对偶问题写出。

3、如何写出下述线性规划问题的对偶模型？min z=2x1+2x2+4x3x1+3x2+4x3≥22x1+x2+3x3≤3x1+4x2+3x3＝5x1≥0, x2≥0, x3无约束。

答：其对偶模型如下，max z=2y1+3y2+5y3y1+2y2+y3≤23y1+y2+4y3≤24y1+3y2+3y3＝4y1≥0, y2≤0, y3无约束。

4、如何快速求出以下只有一个约束方程的线性规划的对偶问题的最优解？Max Z=c1x1＋c1x2＋…＋c n x na1x1＋a1x2＋…＋a n x n≤bx1, x2,…, x n≥0a i, c i, b>0, i=1, 2, …, n.答：利用原问题与对偶问题间的相互转换关系，写出其对偶问题的模型如下，Min f=bya1y≥c1a2y≥c2……a n y≥c ny≥0因为，y≥, i=1, 2, …, n. 所以，其对偶问题的最优解y*=.5、如果原问题是如下所示的追求利润最大的生产计划问题，那么它的对偶问题中变量有何经济含义？原问题的模型形式如下。

其中，变量x j, j=1, 2,…, n, 是每种产品的产量；c j, j=1, 2,…, n, 是每种产品的单位利润；b i, i=1, 2,…, m, 是每种资源的总量，a ij表示生产第j种产品一个单位所消耗的第i种资源的量，i=1, 2,…, m, j=1, 2,…, n.答：其对偶问题即有如下形式，对偶问题中的变量y k, k=1, 2,…, m, 可具有发现某种资源所创造的单位价值并对某种资源定价的经济含义。

第二章 对偶问题与灵敏度分析一、写出下列线性规划的对偶问题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 时可保持最优解不变。

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 第一章例1中美佳公司利用该公司资源生产两种家电产品时，其线性规划问题为： (LP 1) max z ＝2x l +x 2⎪⎪⎩⎪⎪⎨⎧≥≤+≤+≤0,524261552121212x x x x x x x现从另一角度提出问题。

假定有另一公司想把美佳公司的资源收买过来，它至少应付出多大代价，才能使美佳公司愿意放弃生产活动，出让自己的资源.显然美佳公司愿出让自己资源的条件是,出让代价应不低于用同等数量资源由自己组织生产活动时获取的盈利.设分别用y 1、y 2、和y 3代表单位时间(h ）设备A 、设备B 和调试工序的出让代价。

因美佳公司用6小时设备A 和1小时调试可生产一件家电I ，盈利2元；用5小时设备A,2小时设备B 及1小时调试可生产一件家电Ⅱ，盈利1元。

由此y1，y2，y3的取值应满足 6y 2+y 3≥25y 1+2y 2+y 3≥1 （2。

1) 又另一公司希望用最小代价把美佳公司的全部资源收买过来，故有min z ＝15y 1+24y 2+5y 3 （2。

2） 显然y i ≥0(i ＝l ，2，3），再综合（2。

1)，(2。

2)式有。

(LP 2) min ω＝15y 1+24y 2+5y 3⎪⎩⎪⎨⎧≥≥+≥+0,,125263212132y y y y y y y上述LP 1和LP 2是两个线性规划问题,通常称前者为原问题，后者是前者的对偶问题。

二、对称形式下对偶问题的一般形式定义：满足下列条件的线性规划问题称为具有对称形式：其变量均具有非负约束，其约束条件当目标函数求极大时均取“≤"号，当目标函数求极小时均取“≥”号’.对称形式下线性规划原问题的一般形式为:max z=c 1x 1+c 2x 2+…+c n x n ⎪⎪⎪⎩⎪⎪⎪⎨⎧=≥≤+⋅⋅⋅++≤+⋅⋅⋅++≤+⋅⋅⋅++),,1(022112222212111212111n j x bx a x a x a b x a x a x a b x a x a x a j mn mn m m n n n n（2.3)用y i （i=1，…,m ）代表第i 种资源的估价，则其对偶问题的一般形式为：min w=b 1y 1+b 2y 2+…+b m y m⎪⎪⎪⎩⎪⎪⎪⎨⎧⋅⋅⋅=≥≥+⋅⋅⋅++⋅⋅⋅⋅⋅⋅⋅⋅⋅≥+⋅⋅⋅++≥+⋅⋅⋅++),,1(022112222212111212111m i y cy a y a y a c y a y a y a c y a y a y a y i nm mn n n m m m m (2。

对偶问题例题1：某养鸡场所用的混合饲料由n 种天然饲料配合而成。

要求在这批配合饲料中必须含有m 种不同的营养成分，且第i 种营养成分的含量不低于bi 。

已知第i 种营养成分在每单位第j 种天然饲料中的含量为a ij ，每单位第j 天然饲料的价格为c j 。

试问，应如何对这n 种饲料配方，使这批饲料的费用最小? 解 设x j 为第j 种天然饲料的用量。

显然，a ij x j 即为所用第j 种天然饲料中第i 种营养成分的含量，1nij j j a x =∑为这批混合饲料中第i 种营养成分的总含量；它不应低于bi 。

于是，我们得下列线性规划模型(1—1)：1min nj jj f c x ==∑11,,..01,,nij j i j j a x b i m s t x j n=⎧≥=⎪⎨⎪≥=⎩∑现设想有一个饲料加工厂欲把这m 种营养成分分别制成m 种营养丸。

设第i 种营养丸的价格为ui(i ＝1，…，m)。

则养鸡场采购一个单位的第j 种天然饲料，就相当于对这m 种营养丸分别采购数量a 1j ，…a mj ，所化费用为1mij ii a u =∑养鸡场自然希望在用营养丸代替天然饲料时，在价格上能相对地比较便宜，故而饲料加工厂为了能与天然饲料供应者竞争，在制订价格时必然满足下述条件：11,,mij ij i a uc j n =≤=∑另一方面，养鸡场如果全部采购营养丸来代替天然饲料进行配料，则第i 种营养丸就需采购bi 个单位，所化费用为b i u i ，总费用为z=∑b i u i饲料加工厂面临的问题是：应把这m 种营养丸的单价ui(f=1，…，m)定为多少，才能使养鸡场乐意全部采用该厂生产的营养丸来取代这批天然饲料，且使本厂在竞争中得到最大收益。

为该问题建立数学模型，即得如下线性规划(1—2)：1max mi i i z b u ==∑11,,..01,,mij i j i ia u c j n s t u i m =⎧≤=⎪⎨⎪≥=⎩∑我们称问题(1—2)为原有问题 (1—1)的对偶问题(记为(D))。

一、填空题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、线性规划灵敏度分析的主要功能是分析线性规划参数变化对（）的影响。

对偶理论及灵敏度分析习题1. 什么是对偶理论？对偶理论是线性规划中的一种方法，它是将一个线性规划问题转化为另一个等价的线性规划问题。

这个等价问题被称为原问题的对偶问题，原问题和对偶问题之间存在着一种对偶关系。

2. 什么是灵敏度分析？灵敏度分析是一种方法，用于评估一个线性规划问题的解对输入数据的变化的敏感程度。

它涉及到对线性规划问题的目标函数系数、约束条件常数、以及右手边向量的变化进行分析，以确定线性规划问题在输入数据变化下的解的变化情况。

3. 对偶问题和原问题之间有什么关系？对偶问题和原问题之间存在着一种对偶关系，即两个问题中的变量和约束条件互相对应。

对原问题的对偶问题的目标函数系数就是原问题的约束条件系数，而对原问题的每个变量的约束条件对应着对偶问题的每个变量的目标函数系数。

4. 什么是原问题？原问题是一个线性规划问题，它包括在一组约束条件下最大化或最小化一个线性目标函数的问题。

原问题通常表示为标准形式或规范形式。

5. 什么是对偶问题？对偶问题是一个等价的线性规划问题，它与原问题共享相同的约束条件，但目标函数和约束条件的系数经过了转换。

对偶问题可以用来评估原问题的最优解并提供其他信息，如原问题的灵敏度分析和可行性分析。

6. 什么是灵敏度分析中的“影响范围”？灵敏度分析中的“影响范围”指输入参数发生变化时，该变化对解决方案的影响的程度范围。

影响范围可以用来确定哪些输入参数对问题的解决非常敏感，以及如何调整这些参数以最大程度地减少对解决方案的影响。

7. 在灵敏度分析中，什么是“松弛变量”的作用？在灵敏度分析中，“松弛变量”用于评估一个约束条件的“松弛度”，即约束条件与等式相差多少。

这个信息可以用来确定输入参数值的变化可以多少，以使某个约束条件的松弛度保持不变。

8. 什么是敏感性分析？敏感性分析是一种评估线性规划问题解决方案的稳定性的方法。

它涉及到对输入参数的变化进行分析，以确定对线性规划问题最优解的影响程度。

《运筹学》第三章线性规划对偶理论与灵敏度分析习题及答案一、填空题1. 在线性规划问题中，若原问题存在最优解，则其对偶问题也一定存在最优解，这是线性规划的基本性质之一，称为______。

答案：对偶性2. 在线性规划问题中，若原问题与对偶问题均存在可行解，则它们均有______。

答案：最优解3. 对于线性规划问题，若原问题约束条件系数矩阵为A，目标函数系数向量为c，则其对偶问题的目标函数系数向量是______。

答案：c的转置（c^T）二、选择题1. 线性规划的原问题与对偶问题之间的关系是：A. 原问题的最优解和对偶问题的最优解相同B. 原问题的最优解是对偶问题的最优解的负数C. 原问题的最优解与对偶问题的最优解互为对偶D. 原问题的最优解和对偶问题的最优解没有关系答案：C2. 在线性规划中，若原问题不可行，则其对应的对偶问题：A. 可行B. 不可行C. 无界D. 无法确定答案：B三、判断题1. 线性规划的原问题和对偶问题具有相同的可行解。

（）答案：错误2. 若线性规划的原问题存在唯一最优解，则其对偶问题也一定存在唯一最优解。

（）答案：正确四、计算题1. 已知线性规划问题：max z = 3x1 + 2x2s.t.x1 + 2x2 ≤ 42x1 + x2 ≤ 5x1, x2 ≥ 0求该问题的对偶问题，并求解原问题和对偶问题的最优解。

答案：对偶问题为：min w = 4y1 + 5y2s.t.y1 + 2y2 ≥ 32y1 + y2 ≥ 2y1, y2 ≥ 0原问题和对偶问题的最优解如下：原问题最优解：x1 = 2, x2 = 1，最大利润z = 8对偶问题最优解：y1 = 2, y2 = 1，最小成本w = 82. 某工厂生产甲、乙两种产品，生产一件甲产品需要2小时的机器时间和3小时的工人劳动时间，生产一件乙产品需要1小时的机器时间和1小时的工人劳动时间。

工厂每周最多能使用12小时的机器时间和9小时的工人劳动时间。