new v2第二章 对偶问题与灵敏度分析

1、对偶理论与灵敏度分析v线性规划的对偶问题v对偶问题的基本性质v影子价格v对偶单纯形法v灵敏度分析v参数线性规划2.1 线性规划的对偶问题一、问题的提出回顾例题1例1 某工厂在计划期内要安排生产A、B两种产品（假定产品畅销）。已知生产单位产品的利润与所需的劳动力、设备台时及原材料的消耗，如表1.1所示问该厂应如何安排生产使获利最大？表1-1其对应的数学模型为：2112070maxxxZ121212129436045200. .310300,0 xxxxstxxxx现从另一个角度提出问题。假定有某个公司想把该工厂的资源收买过来，它至少应付出多大代价，才能使这个工厂放弃生产活动，出让自己的资源。显然

2、该工厂愿出让自己资源的条件是，出让价格应不低于用同等数量资源由自己组织生产活动时获取的盈利。价格底线表1-1设单位劳动力出让价格y1元，单位设备台时出让价格y2元，单位原材料出让价格y3元。出让收入应不低于自己生产收入：123123943704510120yyyyyy该公司希望用最小代价把这个工厂的全部资源收买过来：123min360200300yyy综上所述，我们得到如下数学模型：123123123123min36020030094370. . 4510120,0yyyyyystyyyyyy2112070maxxxZ121212129436045200. .310300,0 xxxxstxx

3、xx原问题对偶问题二、对称形式下对偶问题的一般形式定义：满足下列条件的线性规划问题称为具有对称形式：其变量均具有非负约束，其约束条件当目标函数求极大时取“”号，当目标函数求极小时均取“”号。下面是对称形式下线性规划原问题的一般形式：1 122maxnnZc xc xc x11 11221121 1222221 122.0,(1,2, )nnnnmmmnnmja xa xa xba xa xa xbsta xaxaxbxjn112211121211121222221122min. .0 (1,. )mmmmmmnnmnmnib yb yb ya ya yayca ya yaycsta yayay

4、cyim用yi(i=1,.,m)代表第i种资源的估价，则其对偶问题的一般形式为：若用矩阵表示：max.0ZCXAXbstXmin.0Y bA YCstY对称形式下的原问题对称形式下的对偶问题将上述对称形式下线性规划的原问题与对偶问题进行比较，可列出下表所示的对应关系1234123412341234max3752256403250232200,1,2,3,4jZxxxxxxxxxxxxxxxxxj写出下面线性规划的对偶规划模型课堂练习解：按照对称形式的对偶关系，其对偶模型为123123123123122123m in4050202335227563221,0yyyyyyyyyyyyyyyyyy原

5、问题有m个约束条件，对偶问题有m个变量原问题有n个变量，对偶问题有n个约束条件原问题的价值系数对应对偶问题的右端项原问题的右端项对应对偶问题的价值系数原问题的系数矩阵转置后为对偶问题系数矩阵原问题的约束条件与对偶问题方向相反原问题与对偶问题优化方向相反小结小结相关证明：对偶问题的对偶即原问题max.0ZCXAXbstXmin.0Y bA YCstY令 = max.0Y bA YCstY 对偶问题min.0ZCXAXbstX 对偶问题令Z = Z 三、非对称形式下原对偶问题关系原问题和对偶问题有很多内在联系，它们之间存在着严格的对应关系：目标函数类型之间的对应关系目标函数系数与右边项的对应关系约

6、束系数矩阵之间的对应关系约束类型与变量类型之间的对应关系并非所有线性规划问题具有对称形式，故下面讨论一般情况下线性规划问题如何写出其对偶问题：由于前面三个对应关系与对称形式下的对应关系一致，故我们只需讨论约束类型与变量类型之间的对应关系:综上所述，其变换形式归纳如下：综上所述，其变换形式归纳如下：例 写出下列线性规划问题的对偶问题123512345134124512345min326243724.32,00Zxxxxxxxxxxxxstxxxxxxxxx无限制解：123123131212313123max7422332426.03100yyyyyyyyyystyyyyyyyy 无约束SSSSS

7、SOOBBSSOOBB例 写出下列线性规划问题的对偶问题课堂练习1234123412412341234max2354325327423460,0Zxxxxxxxxxxxstxxxxxxxx无约束12312312313123123min5464322233.3452710,0,yyyyyyyyystyyyyyyyy 无约束答案：答案：课堂练习12312312312312312341234234123412341.min22423523 73 465,02min3234 2343 345 2374200, Zxxxxxxxxxxxxxxx.Zxxxxxxxxxxxxxxxxxxx ，、无约束123

8、1231231231231231312312311 . m a x2352 y3 y y23 y y4 y2 5 y7 y6 y4y0 ,y.y0 2 . m a x352 y 2 y32 y y3 y2 3 y3 y7 y3 4 y4WyyyWyyy 答 案 ：23123y4 y4y0 ,y0 ,y无 约 束对偶理论与灵敏度分析v线性规划的对偶问题v对偶问题的基本性质v影子价格v对偶单纯形法v灵敏度分析2.2 对偶问题的基本性质一、单纯形法计算的矩阵描述对称形式线性规划问题的矩阵表达式加上松驰变量X后为：max0.0,0sssZCXXAXIXbstXX单纯行法计算时，总选取为初始基，对应基变

9、量Xs举例：12345132412512345max350008212. .3436,0Zxxxxxxxxxstxxxxxxxx设迭代若干步后，基变量为XB, XB在初始 单纯行表中的系数矩阵为B。将B在初始单纯行表中单独列出，而A中去掉B的若干列后剩下的列组成N。于是其初始单纯行表可表示成如下形式表2.4当迭代若干步后，基变量为XB时，该步的单纯行表中由XB系数组成的矩阵为 (单位矩阵)。又因单纯行法的迭代是对增广矩阵进行的初等变换，对应Xs的系数矩阵在新表中应为B-1; 对应XN的系数矩阵在新表中应为B-1N于是迭代后的单纯行表可表示成如下形式：表2.5初始单纯行表:B-1112.nBp

10、pp表2.5CB课堂练习 2-110 0 0111201/21/201/21/2B1112311*01/21/211201/21/2111001101/2013/2AB A由可知：11126010*01/21/2101501/2 1/2205bB b*11()BjBjCC BAICC B A检验数的求解：*11()BjBjCC BAICC BA3110211/23/23/2 56100211/ 23/ 21/ 21/ 2 当B为最优基时，其所有检验数应小于零（j 0 )于是对应于表2.5有：110(1)0(2)NBBCC B NC B而对于XB的检验数可写为：10(3)BBCC B B由此，（

11、1）（2）（3）式可重新表示为：1100BBCC B AC B1100BBCC B AC B若令Y= CB B-1 ,则上式可表达为：0A YCY这时可以看出检验数行,若取其相反数恰好是其对偶问题的可行解。min.0Y bA YCstY为什么？由于对偶问题的限制条件是的形式，则标准形式是在左边减去一个剩余变量的基础上得到的，这个剩余变量为111()mijijBjjjBjjia ycC B ACCC B A 1BY bC B bZ可以看出，当原问题为最优解时，其对偶问题为可行解，且两者具有相同的目标函数值。后面我们将看到，这时对偶问题的解也为最优解将这个解代入对偶问题的目标函数，有:由上面的推导

12、知，我们可以从线性规划问题的最终单纯中直接读出其对偶问题的最优解。注：Cj Zj为检验数，需对其取反z1-c1 z2-c2 zn-cnym+1 ym+2 ym+n松弛变量Xs更一般的结论：用单纯形法求解线性规划问题时，迭代的每一步在得到原问题一个基可行解的同时，其检验行（行0）中的 yi和zjcj值是其对偶问题的一个基解112212(,.,.)nnmzc zczcy yy举例：下面是两个互为对偶的线性规划问题：122121212max25156224.5,0Zxxxxxstxxxx12323123123min1524562. 521,0yyyyystyyyyyy原问题对偶问题将上面两个线性规划

13、问题加入松弛和剩余变量后，得到如下形式：1234523124125max20005156224.50(1,.,5)jZxxxxxxxxxxstxxxxj123452341235max152450062.5210 (1,.,5)iyyyyyyyystyyyyyiy1y2y3对偶变量对偶变量对偶变量对偶变量x1x2用单纯形法和对偶单纯型法求得两个问题的最终单纯形表如下：原问题变量原问题松弛变量对偶问题的剩余变量对偶问题变量原问题最终单纯形表对偶问题最终单纯形表对偶问题变量对偶问题剩余变量原问题松弛变量原问题变量从上面两个表可以清楚的看出两个问题变量之间的对应关系。同时看出只需求解其中一个问题，从最

14、优的单纯形表中同时得到另一个问题的最优解二、对偶问题的基本性质【定义2.1】（弱对偶性）如果xj (j=1,.n)是原问题的可行解，yi (i=1,m)是其对偶问题的可行解，则恒有11nmjjiijic xb y证明：11111()nnmmnjjijijijjijjiijc xa y xa x y11111()mmnmniiijjiijjiiijijb ya xya x y 由弱对偶性，可得出以下结论：1、原问题任一可行解的目标函数值是其对偶问题目标函数值的下界；反之对偶问题任一可行解的目标函数值是其原问题目标函数值的上界2、如原问题有可行解且目标函数值无界（具有无界解），则其对偶问题无可行解

15、；反之对偶问题有可行解且目标函数值无界，则其原问题无可行解。注意：本点性质的逆不成立，即当对偶问题无可行解时，其原问题或具有无界解或无可行解；反之亦然3、若原问题有可行解而其对偶问题无可行解，则原问题目标函数值无界；反之对偶问题有可行解而其原问题无可行解，则对偶问题的目标函数值无界。【定理2.2】（最优性）如果xj (j=1,n) 是原问题的可行解，yi (i= 1,m)是其对偶问题的可行解，且有 11nmjjiijic xby则xj (j=1,n)是原问题的最优解，yi (i=1,m)是其对偶问题的最优解证明：设xj*(j=1,n)是原问题的最优解，yi*(i=1,.,m)是对偶问题的最优解

16、。由弱对偶性质有：*1111nnmmjjjjiiiijjiicxcxbyby，*1111nnmmj jj ji ii ijjiicxcxbyby又知：11nmj ji ijicxby*1111nnmmj jj ji ii ijjiicxcxbyby【定理2.3】（强对偶性） 若原问题及其对偶问题均具有可行解，则两者均具有最优解，且它们最优解的目标函数值相等证明：由于两者均有可行解，根据弱对偶性，对原问题的目标函数具有上界，对偶问题的目标函数具有下界，因此两者具有最优解。由矩阵描述一节可知，当原问题为最优解时，其对偶问 题的解为可行解，且有Z=,由定理2.2可知，这时两者均为最优解Primal

17、problemDual problemOptimal Z*Optimal W*【定理2.4】（互补松弛性） 在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式；反之，如果约束条件取严格不等式，则其对应的对偶变量一定为零，也即：0, 0,)(0, 0*1*1*isinjjijsiinjjijiyxbxaxbxay则有即若松弛变量即则有若以前面例子说明互补松弛定理：1221212max25156224.50(1,.,5)jZxxxxxstxxxjy1y2y3对偶变量对偶变量1234523124125max20005156224.50(1,.,5)jZxxxxx

18、xxxxxstxxxxjy1y2y3互补松弛定理（说明续）：原问题变量原问题松弛变量对偶问题的剩余变量对偶问题变量原问题最终单纯形表已知线性规划问题 min = 2x1 + 3x2 + 5x3 + 2x4 + 3x5 x1 + x2 + 2x3 + x4 + 3x5 4 2x1 x2 + 3x3 + x4 + x5 3 xj 0 (j = 1, 2, , 5)对偶问题的最优解为y1* = 4/5, y2* = 3/5, Z=5,试找出原问题的最优解。课堂举例st.分析：先写出其对偶问题 max Z = 4y1 + 3y2 y1 + 2 y2 2 y1 - y2 3 2y1 + 3y2 5 y1

19、 + y2 2 3y1 + y2 3x1x2x3x4x5将y1*、y2* 的值带入约束条件，得到24个约束条件为严格不等式；由互补松弛性得x2* =x3*=x4*=0.因y1*、y2*0;原问题的两个约束条件应取等式： x1* + 3x5* = 4 2x1* + x5* = 3求解后得到x1*= 1, x5*=1,故原问题最优解x*=(1,0,0,0,0,1)T; *=5课堂练习已知原问题123123123123123max432352.36140,0,Zxxxxxxstxxxxxxxxx无约束的最优解为X*=(0,0,4)T,最优值为Z*=12.试用对偶理论求对偶问题的最优解将X*=(0,

20、0, 4)T ,代入原问题的三个约束条件可知：*123*123*123235202362414xxxxxxxxx 由松弛互补定理可知，必有y1*=y2*=0，代入对偶问题得y3*=3y1y2y3对偶变量对偶变量解：原问题的对偶问题为：123123123123123min2423134.5630,0,Wyyyyyyyyystyyyyyy无限制Y*=(0,0,3),最优值为最优值为W*=12对偶理论与灵敏度分析v线性规划的对偶问题v对偶问题的基本性质v影子价格v对偶单纯形法v灵敏度分析当线性规划原问题求得最优解xj*(j=1,2n)时，其对偶问题也得到最优解yi*(i=1,.,m),代入各自的目标

21、函数后有：*11nmjjiijiZc xby3.3.1其中，bi代表第i种资源的拥有量，对偶变量yi*的意义代表在资源最优利用条件下对单位资源i的估价。这种估计不是资源的市场价格，而是根据在生产中做出的贡献而作的估价，为区别一般意义的价格，我们将其（yi*）称为影子价格（shadow price）2.3 影子价格（对偶最优解的经济解释）影子价格的几点说明1 资源的市场价格是已知数，相对比较稳定，而它的影子价格则有赖于资源的利用情况，是未知数。因企业生产任务、产品结构等情况发生变化，资源的影子价格也随之改变。2 影子价格是一种边际价格，在3.31式中对Z求bi的偏导数得*iiybZ这说明yi*的

22、值相当于在资源得到最优利用的生产条件下，bi每增加一个单位时目标函数Z的增量关于第2点的说明12121212max354212. .321800Zxxxxs txxxx最终单纯形表y1y2y3对偶变量对偶变量y1 y2 y3关于第2点的说明X 1X2(2,6)(5/3,13/2)Z1=3(2)+5(6)=362x2=122x2=13Z2=3(5/3)+5(13/2)=37.5Z=Z2 Z1= 3/2 = y*23 资源的影子价格实际上又是一种机会成本。在纯市场经济条件下，当某一资源的市场价格低于该影子价格时，可以买进这种资源；相反，当市场价格高于影子价格时，就会卖出这种资源。随着资源的买进卖出

23、，它的影子价格也将随之发生变化，一直到影子价格与市场价格保持同等水平时，才处于平衡状态。4、在上一节对偶问题的互补松弛性质中有0, 0,)(0, 0*1*1*isinjjijsiinjjijiyxbxaxbxay则有即若松弛变量即则有若这表明生产过程中如果某资源bi未得到充分利用，则该种资源的影子价格为零；又当某资源的影子价格不为零时，表明该种资源已消耗完毕。(互补松弛定理的经济解释)5 对单纯形表的检验数miiijjjBjjyacPBCc11Cj代表第j种产品的单位产值， aijyi是生产单位该种产品所消耗各项资源的影子价格的总和。当产品单位产值大于隐含成本时，表明生产该项产品有利，可在计划

24、中安排生产，否则用这些资源来生产别的产品更为有利，就不安排生产。（检验数的经济解释）6 一般说来，对线性规划问题的求解是确定资源的最优分配方案，而对于对偶问题的求解则是确定对资源的恰当估价，这种估计直接涉及资源的最有效利用。 例如，在一个大公司内部，可借助资源的影子价格确定一些内部结算价格，以便控制有限资源的使用和考核下属企业经营的好坏。 又如，在社会上可对一些最紧缺的资源，借助影子价格规定使用这种单位资源时必须上交的利润额，以控制一些经济效益低的企业自觉地节约使用紧缺资源，使有限资源发挥更大的经济效益。对偶理论与灵敏度分析v线性规划的对偶问题v对偶问题的基本性质v影子价格v对偶单纯形法v灵敏

25、度分析2.4 对偶单纯形法一、对偶单纯形法的基本思路对原问题的一个基可行解，判别是否所有检验数，若是，又基变量中无非零人工变量，即找到了问题的最优解；若为否，再找出相邻的目标函数值更大的基可行解，并继续判别，只要最优解存在，就一直循环进行到找出最优解为止。0jjjcz求解线性规划的单纯形法的思路是：对偶单纯形法的基本思路是：从原问题的一个基本解出发，此基本解不一定可行（即b中有负数），但它对应着一个对偶可行解（检验数非正），所以此时也可以说是从一个对偶可行解出发；然后检验原问题的基本解是否可行，即b是否有为负的分量,若是，则进行迭代，求解另一个基本解，此基本解对应着另一个对偶可行解（保持检验数

26、非正）。如果得到的基本解的分量皆非负，则该基本解为最优解。根据对偶问题的性质，因为Cj Zj = Cj CBB-1Pj , 当Cj Zj 0 (j=1,2,n), 即有YPj Cj 或aijyi Cj (j=1,2,n)也即其对偶问题的解为可行解。i=1m也就是说，对偶单纯形法在迭代过程中始终保持对偶解的可行性（即检验数非正），使原问题的基本解由不可行逐步变为可行。当同时得到对偶问题与原问题的可行解时，便得到了原问题的最优解。单纯形法与对偶单纯形法之间的比较二、对偶单纯形法的计算步骤1 根据线性规划问题，列出初始单纯形表，检查b列的数字，若都为非负，检验数都为非正，则已得到最优解，停止计算。若

27、检查b列的数字时，至少有一个负分量，所有检验数保持非正，那么进行以下计算2 确定换出基的变量 按 对应的基变量xr为换出基的变量riibbbMin 0|确定换入变量 在单纯形表中检查xr所在行的各系数arj(j=1,2,n) 若所有arj 0，则原问题无可行解xr + ar,m+1xm+1 + arn xn = br因为arj 0 (j=m+1,.,n), 又br0, 故不可能存在xj 0 (j=1,2.n)，故原问题无可行解。若存在arj 0(j =1,2n), 则按最小比值原则计算|0minjjssrjrjrsjczczaaa称ars为主元素（枢轴元素），xs为换入基的变量4 以ars为主

28、元素，进行高斯消元，得到新的计算表 重复14的步骤123123123123m in91 21 5221 0231 2 51 40 (1, 2, 3)jZxxxxxxxxxxxxxj解：将模型转化为 01451232102215129max61632153214321321xxxxxxxxxxxxxxxxZ 三、对偶单纯形法举例(-9/-1, -12/-1, -15/-5)(-30/-9,-45/-14,-15/-1)(-3/-9, -45/-9, -33/-1)四、对偶单纯形法的应用时机1 对偶单纯形法的优点是，初始解可以是非可行解，不需要加入人工变量2 对一个线性规划问题，即可以用单纯形法求

29、解，也可以用对偶单纯形法求解。具体采用那种方法，由当前情况（计算表）决定。使用那种方法比较方便，就使用那种方法3 求目标函数最大化时，在单纯形表中： 如果检验数均非正，而b列中有负值，这时使用对偶单 纯形法； 如果所有bi 0, 检验数有正值，使用单纯形法 如果b列中有负值，且检验数中有正值，这时必须引入 人工变量，建立新的单纯形表，重新计算用对偶单纯法求解下述线性规划问题：12323123123min1524562. 521,0yyyyystyyyyyy分析：先将问题改写为最大化形式，然后在约束条件两端乘“1”后，加入相应的松弛变量得：123452341235max152450062.521

30、0(1,.,5)iyyyyyyyystyyyyyi课堂练习列出单纯形表，并用上述对偶单纯形法求解步骤进行计算-24/-6 1.5，而家电II的利润12，美佳公司最优生产计划有何变化(2) 若家电I的利润不变，则家电II的利润在什么范围内变化时，则该公司的最优生产计划不发生变化分析：(1)最终单纯形表j = Cj - CBB-1pj ,其中B-1pj可从最终单纯形表读得0 0 0 1/8 -9/4因变量x4的检验数大于零，故需继续用单纯形法迭代614即美佳公司随家电利润的变化应调整为生产I 2件，生产II 3 件分析：(2) 设家电II的利润为(1+)元，反映到最终单纯形表中，得下表：0 0 0

31、 -1/4+1/4 -1/2-3/2为使上表的解仍为最优解，应有： -1/4 + 1/4 0 ; -1/2 2/3 0解得： -1/3 1即家电II的利润c2的变化范围应满足 ： 2/3 c2 2二、分析bi的变化右端项bi的变化在实际问题中反映为可用资源数量的变化。由于bi变化反映到最终单纯形表上仅引起b列数字的变化，故解的最优性不受影响（对偶问题可行），我们只需要判断解的可行性即可。若该解可行，则最优基不变若该解不可行，则使用对偶单纯形法迭代直到找到最优解在上述美佳公司的例子中：（1）若设备A和调试工序的每天能力不变，而设备B每天的能力增加到32h，分析公司最优计划的变化（2）若设备A和设

32、备B每天可用能力不变，则调试工序能力在什么范围变化时，问题的最优基不变分析： (1)因为 ，于是有：080b 115/415/201001/41/28201/43/202bBb 将计算结果反映到最终单纯形表中去,有：原最终单纯形表由于原问题为非可行解，故用对偶单纯形法继续计算得下表由此，美佳公司的最优计划改变为只生产家电 5件分析： （2）设调试工序每天可用能力为（ 5 + ）h,因此有：115/415/2015/201/41/201/201/43/23/2b15/15/2127/23/23/2/2bBbb 将其反映到最终单纯形表中，其 列数字为：当b 0时问题的最优基不变，解得 -1 1由此，此调试工序的能力应在46h之间三、增加一个变量xj的变化增加一个变量在实际问题中反映为增加一种新的产品，其分析步骤为：1、计算2、计算1jjPB P 3、若0j ，则原最优解不变，只需将计算得到的jjP和直接写入最终单纯形表中即可；若存在0j , 则按单纯形法继续迭代计算找出最优解。1*1mjjBjjijiiCC BPCa y美佳公司又计划推出新型号的家电III，生产一件所需设备A、B及调试工序的时间分别为3h, 4h, 2h，该产品的预期盈利为3元/件， 试分析该种产品是否值得投产；如投产，对该公司的最优生产计划有何变化