下载文档原格式
《运筹学》第三章线性规划对偶理论与灵敏度分析习题及答案一、填空题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小时的工人劳动时间。
第三章线性规划对偶理论与灵敏度分析习题 一、思考题1．对偶问题和对偶变量的经济意义是什么？2．简述对偶单纯形法的计算步骤。
它与单纯形法的异同之处是什么？3．什么是资源的影子价格？它和相应的市场价格之间有什么区别？4．如何根据原问题和对偶问题之间的对应关系，找出两个问题变量之间、解及检 验数之间的关系？5．利用对偶单纯形法计算时，如何判断原问题有最优解或无可行解？6．在线性规划的最优单纯形表中，松弛变量（或剩余变量）0>+k n x ，其经济意 义是什么？7．在线性规划的最优单纯形表中，松弛变量k n x +的检验数0>+kn σ（标准形为求最小值），其经济意义是什么？8．将i j ji bc a ,,的变化直接反映到最优单纯形表中，表中原问题和对偶问题的解 将会出现什么变化？有多少种不同情况？如何去处理？ 二、判断下列说法是否正确1．任何线性规划问题都存在且有唯一的对偶问题。
2．对偶问题的对偶问题一定是原问题。
3．若线性规划的原问题和其对偶问题都有最优解，则最优解一定相等。
4．对于线性规划的原问题和其对偶问题，若其中一个有最优解，另一个也一定 有最优解。
5．若线性规划的原问题有无穷多个最优解时，其对偶问题也有无穷多个最优解。
6．已知在线性规划的对偶问题的最优解中，对偶变量0>*i y ，说明在最优生产计 划中，第i 种资源已经完全用尽。
7．已知在线性规划的对偶问题的最优解中，对偶变量0=*i y ，说明在最优生产计 划中，第i 种资源一定还有剩余。
8．对于i j ji bc a ,,来说，每一个都有有限的变化范围，当其改变超出了这个范围 之后，线性规划的最优解就会发生变化。
9．若某种资源的影子价格为u ，则在其它资源数量不变的情况下，该资源增加k 个单位，相应的目标函数值增加 u k 。
10．应用对偶单纯形法计算时，若单纯形表中某一基变量0<i x ，且i x 所在行的 所有元素都大于或等于零，则其对偶问题具有无界解。
第二章 线性规划的对偶理论与灵敏度分析主要内容 对偶问题、对偶基本性质、对偶单纯形方法、灵敏度分析、参数规划 讲授重点 对偶基本性质、对偶单纯形方法、灵敏度分析 讲授方式讲授式、启发式本章知识结构图第一节 线性规划的对偶问 题一、对偶问题的提出首先通过实际例子看对偶问题的经济意义。
例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。
4)用矩阵形式表示,对称形式的线形规划问题的原问题为：max z=CX⎩⎨⎧≥≤0X b AX （2。
5）其对偶问题为：min w=Y ’b⎩⎨⎧≥≥0'Y C Y A将上述对称形式下线性规划的原问题与对偶问题进行比较,可以列出如表2—1所示的对应关系。
上述对偶问题中令'ω= ω-，可改写为 max 'ω=-Y ’b⎩⎨⎧≥-≤-0''Y C Y A如将其作为原问题，并按表2—1所列对应关系写出它的对偶问题则有⎩⎨⎧≥-≥--=0min 'X bAX CXz再令z z -='则上式可改写为：⎩⎨⎧≥-≥--=0min X b AX CXz可见对偶问题的对偶即原问题。
三、非对称形式的原-对偶问题关系因为并非所有线性规划问题具有对称形式，故下面讨论一般情况下线性规划问题如何写出其对偶问题。
考虑下面的例子。
例2 写出下述线性规划问题的对偶问题32134m ax x x x z ++=⎪⎪⎩⎪⎪⎨⎧≤≥=++≥+-≤-+无约束3221321321321,0,041632532x x x x x x x x x x x x思路是先将其转换成对称形式，再按表2-1的对应关系来写。
下面将对称或不对称线性规划原问题同对偶问题的对应关系，统一归纳为表2-2所示形式。
第二节 对偶问题的基本性质本节的讨论先假定原问题及对偶问题为对称形式线性规划问题，即原问题为：⎪⎩⎪⎨⎧=≥=≤=∑∑==),,1(0),,1(max 11n j x m i b x a x c z jmj i j ij nj ji (2.9)其对偶问题为:⎪⎩⎪⎨⎧=≥=≥=∑∑==),,1(0),,1(min 11n j x m i c x a x b w jmi j i ij mi ii （2.10） 然后说明对偶问题的基本性质在非对称形式时也适用。
为本节讨论及后面讲述的需要,这里先介绍有关单纯形法计算的矩阵描述.一、单纯形法计算的矩阵描述对称形式线性规划问题(2.9)的矩阵表达式加上松弛变量后为：⎩⎨⎧≥≥=++=0,00max s s sX X b IX AX X Cx z （2.11）上式中X s 为松弛变量,X s =( x n+1,x n+2，…，x n+m ),I 为m ×m单位矩阵。
单纯形法计算时，总选取I 为初始基,对应基变量为X s 。
设迭代若干步后,基变量为X B ，X B 在初始单纯形表中的系数矩阵为B 。
将B 在初始单纯形表中单独列出，而A 中去掉后的若干列后剩下的列组成矩阵N ，这样(2.11）的初始单纯形表可列成如表2-3的形式。
B B 纯形法的迭代是对约束增广矩阵进行的行的初等变换,对应X s 的系数矩阵在新表中应为B -1.故当基变量为X B 时,新的单纯形表具有表2—4形式.B 数矩阵为B ,则有：(1)对应初始单纯形表中的单位矩阵I ，迭代后的单纯形表中为1-B ；(2)初始单纯形表中基变量s X ＝b ，，迭代后的表中B X ＝1-B b ，，（3)初始单纯形表中约束系数矩阵为［1-B A ，1-B I]＝［1-B B ，1-B N,1-BI]，迭代后的表中约束系数矩阵为[1-B A ，1-B I]＝[1-BB ，1-BN,1-BI ］＝[I ，1-BN ，1-B ］。
(4）若初始矩阵中变量jx 的系数向量为jP 迭代后为'j P ,则有jj P B P 1'-= （2.13）（5）当B 为最优解时,在表2—4中应有01≤--N B C C B N （2。
14）01≤--B C B （2。
15）因 B x 的检验数可写为0=⋅-I C C B B (2。
16）故（2.14)～（2.16） 式可重写为01≤--A B C C B （2.17）01≤--B C B (2。
18） 1-B C B 称为单纯乘子，若令1'-=B C Y B 则(2.17)、(2。
18)式可改写为⎩⎨⎧≥≥0''Y C Y A (2.19）看出这时检验数行，若取其相反数恰好是其对偶问题的一个可行解。
将这个解代入对偶问题的目标函数值，有z b B C b Y B ===-1'ω (2.20）由(2。
20)式看出,当原问题为最优解时，这时对偶问题为可行解，且两者具有相同的目标函数值.根据下一节讲述的对偶问题的基本性质,将看到这时对偶问题的解也为最优解。
下面通过例子说明两个问题的变量及解之间的对应关系,见例3。
例3 本章例1中列出了两个互为对偶的线性规划问题，两者分别加上松弛和剩余变量后为：543210002m ax x x x x x z ++++=⎪⎪⎪⎩⎪⎪⎪⎨⎧=≥-≤''+'-'+-≤++=++=+')5,,1(0442426155332152142132 j x x x x x x x x x x x x x j⎪⎩⎪⎨⎧=≥=-++=-+++++=)5,,1(0125260052415min 532143254321 i y y y y y y y y x x y y y iω用单纯形法和两阶段法求得两个问题的最终单纯形表分别见表2—5和表2—6。
从表2-5和表2-6，可以清楚看出两个问题变量之间的对应关系。
此处分析解的对应关系，并指出:只需求解其中一个问题，从最优解的单纯形表中能得到另一个问题的最优解。
二、对偶问题的基本性质1.弱对偶性。
如果),,1(n j x j =是原问题的可行解，),,1(m i y j =是其对偶问题的可行解,则恒有∑∑==≤nj mi ii j jy b x c11证明：由目标和约束不等式易得. 由弱对偶性，可得出以下推论:（1)原问题任一可行解的目标函数值是其对偶问题目标函数值的下界；反之对偶问题任一可行解的目标函数值是其原问题目标函数值的上界。
(2）如原问题有可行解且目标函数值无界(具有无界解)，则其对偶问题无可行解；反之对偶问题有可行解且目标函数值无界，则其原问题无可行解（注意:本点性质的逆不成立，当对偶问题无可行解时，其原问题或具有无界解或无可行解，反之亦然）。
（3)若原问题有可行解而其对偶问题无可行解，则原问题目标函数值无界；反之对偶问题有可行解而其原问题无可行解,则对偶问题的目标函数值无界。
2.最优性。
如果),,1(ˆn j xj =是原问题的可行解，),,1(ˆm i y i =是其对偶问题的可行解，且有∑∑===nj mi i i j jy b xc11ˆˆ则),,1(ˆn j x j =是原问题的最优解，),,1(ˆm i yi =是对偶问题的最优解。
3.强对偶性(或称对偶定理）.若原问题及其对偶问题均具有可行解，则两者均具有最优解，且它们最优解的目标函数值相等。
证 由于两者均有可行解，根据弱对偶性的推论(1),对原问题的目标函数值具有上界，对偶问题的目标函数值具有下界；因此两者均具有最优解.又由本节的公式（2.19）和(2。
20)知，当原问题为最优解时，其对偶问题的解为可行解，且有ω=z ，由最优性知，这时两者的解均为最优解。
4.互补松弛性。
在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式;反之如果约束条件取严格不等式，则其对应的对偶变量一定为零.也即若 0ˆ≥i y ， 则有∑==nj i j ij b xa 1ˆ, 即0ˆ=si x若∑=<nj j jb xc1ˆ ,即0ˆ>si x ，则有0ˆ=i y因此一定有0ˆˆ=⋅i si y x证 由弱对偶性知∑∑∑∑===-≤≤nj mi i i m i n j i j ij j jy b y x a xc1111ˆˆˆˆ （2.21)又根据最优性∑∑===nj mi i i j jy b xc11ˆˆ，故（2。
