运筹学与系统分析：第2章 线性规划的对偶理论与灵敏度分析

1、第2章 线性规划的对偶理论与灵敏度分析第2章 线性规划的对偶理论与灵敏度分析本章要点：线性规划对偶问题的提出线性规划问题的对偶理论对偶解的经济解释对偶单纯形法灵敏度分析2.1 线性规划的对偶问题一、对偶问题的提出例2.1 某家具公司(甲公司)生产桌子和椅子两种家具，有关资料如下表所示，问该公司应如何安排生产才能使每月的销售利润最大？桌子椅子可供工时量（小时/月）木工工时(小时/件)43120油漆工工时(小时/件)2150利润（元/件）5030家具加工时间加工工种设两种产品产量分别为x1,x2，则其线性规划模型为：Max2.1 线性规划的对偶问题假设现有乙公司准备租借 (或购买)该木器厂的木工和

2、油漆工两种劳力的劳务，现考虑这两种劳务以什么价格租入最为划算？同时甲公司要以什么条件才肯租让？设每个木工工时的租用价格为y1，每个油漆工工时的租用价格为y2，则乙公司希望以最小的费用租借，即：甲公司愿意出租的条件是出租收益用同等数量劳力资源由自己组织生产所创造的利润。即:Miny1,y20.2.1 线性规划的对偶问题因此有:MaxMin原问题（LP1）对偶问题（LP2）任何线性规划问题都有对偶问题，且都有相应的经济意义。二、对称形式下对偶问题的一般形式满足下列条件的线性规划问题称为具有对称形式： （1）变量均具有非负约束 （2）约束条件当目标函数求极大值时均取“”号 （3）约束条件当目标函数当

3、求极小值时均取“”号对称形式下线性规划原问题的一般形式为： 用 yi (i=1,m) 代表第 i种资源的估价，则其对偶问题的一般形式为：用矩阵形式表示MaxMin原问题：对偶问题：原问题与对偶问题的比较项目原问题对偶问题A约束系数矩阵约束系数矩阵的转置b约束条件的右端项向量目标函数中的价值系数向量C目标函数中的价值系数向量约束条件的右端项向量目标函数Max z=CXMin w=YTb约束条件AXbATYCT决策变量X 0Y 0表1 原-对偶问题比较对偶问题的对偶即是原问题！例：对偶问题 Min令可改写为Max将它作为原问题，写出其对偶对偶问题： Min再令可改写为Max三、非对称形式的原-对偶

4、问题关系例：求下面非对称形式规划问题的对偶问题Max(A)(B)(C)(D)（1）约束(B)先转换成两个约束条件解：先转换成对称形式，再写出对偶问题再转换为（2）约束(C)两端乘以（-1）得到（3）约束(D)中，令此时原问题转换成了如下对称形式：Max对偶变量设定对偶变量后，按表1写出对偶问题如下Min(E)(F)(G)(H)令且(F)式两端乘(-1)得Min总结：原问题与对偶问题的对应关系原问题（或对偶问题）对偶问题（或原问题）目标函数最大化（Max Z)目标函数最小化（Min w)n个变量n个约束m个约束m个变量约束条件限定向量（右边项）目标函数价值向量（系数）目标函数价值向量约束条件限定

5、向量（右边项）(参考运筹学教程表2-2)写出下列问题的对偶问题：MinMax-+-=-+-+-无约束321321321321,0,0832353410.xxxxxxxxxxxxts2.2 对偶问题的基本性质 本节基本性质讨论先假定原问题和对偶问题为对称形式线性规划问题，即：原问题：对偶问题：初始单纯形表一、单纯形法的矩阵描述对称形式线性规划问题加上松弛变量Xs后得到： 单纯形法计算时，总选取I为初始基，对应基变量为Xs，则初始单纯形表如下所示。设迭代若干步后基变量为XB，XB在初始单纯形表中的系数矩阵为B。N为A去掉B后剩余列构成的矩阵。CB和CN是与B和N对应的检验数。则可表示为：最终单纯形

6、表迭代后得到最终单纯形表如下图所示。（1）初始表中基变量对应的系数矩阵I，在最终表中变为B-1（2）初始表中基变量为Xs=b，最终表中基变量为XB=B-1b（3）初始表中的系数矩阵B和N，在最终表中变为I和B-1N（4）最终表中基变量XB的检验数全为0，XN、Xs的检验数分别变为CN-CBB-1N和-CBB-1min对偶变量y1y2y3对偶变量x1x2原问题P：对偶变量y1y2y3对偶问题D：例：原-对偶问题的变量与解的对应关系（分别加上松弛变量与剩余变量）max解：用单纯形法求解下面问题（原问题）同理可求出原问题的对偶问题最优解，与原问题的解进行比较：Cj原问题变量原问题松驰变量xBbx1x

7、2x3x4x5x315/20015/4-15/2x17/21001/4-1/2x23/2010-1/43/2cj-zj000-1/4-1/2对偶问题的剩余变量对偶问题变量y4y5y1y2y3Cj对偶问题变量对偶变量的剩余变量yBby1y2y3y4y5y21/4-5/410-1/41/4y31/215/2011/2-3/2cj-zj-15/200-7/2-3/2原问题松驰变量原问题变量x3x4x5x1x2原问题最优解得到时，也可从检验数行看到对偶问题最优解。线性规划对偶理论的主要基本定理：1.弱对偶性：设X和Y分别是原问题P和对偶问题D的可行解，则CXbTY 。推论1：P有最优解的充要条件是D有

8、最优解；推论2：若P无界则D无可行解，若D无界则P无可行解；2.最优性：若X*和Y*分别是P和D的可行解，则它们分别为P和D的最优解的充要条件是CX*=Y*b3.强对偶性：若P和D均具有可行解，则两者均具有最优解，且它们最优解的目标函数值相等。4.互补松弛性：获得最优解时，若对应某一约束条件的对偶变量值为非零，则该约束条件为严格等式，反之若该约束条件为严格不等式，则对应对偶变量为零。二、对偶问题的基本性质2.3 影子价格（对偶解的经济学解释）bi：原问题约束条件右端项，代表第 i 种资源拥有量；对偶变量yi*：资源最优利用下对每个单位的第 i 种资源的估价（非市场价格，是对最优方案的贡献值），

9、特称为影子价格（shadow price）； 当线性规划问题取得最优解xj*时，其对偶问题也取得最优解yi*，代入各自目标函数后相等：（1）资源的市场价格围绕实际价格波动，比较稳定。影子价格则取决于资源的利用情况，它会随不同企业或同一企业不同生产任务、不同产品结构而不同。（2）影子价格是一种边际价格。影子价格yi*的理论值等于资源得到最优利用的生产条件下，第 i种资源拥有量bi每增加一个单位时目标函数 z的增量。0 x1x2(3, 3)(7/2, 3/2)(15/4, 5/4)例：最优解(7/2, 3/2), 目标函数z*=17/2若第二约束条件b2增加1，即25，最优解变为(15/4, 5/

10、4), 目标函数z*=35/4, 目标函数增量为1/4, 故第二种资源的边际价格（影子价格）为1/4。同理，b3增加1，最优解(3,3), 目标函数增量(边际价格)为1/2（3）资源的影子价格实际上也是一种机会成本，当某资源的市场价格低于资源成本加上其影子价格时，可以买入，当资源的市场价格高于资源成本加上其影子价格时，可以卖出。（4）当某种资源 bi未得到充分利用时，它的影子价格为零，当影子价格不为零时，该资源在生产时已耗费完毕。（5）一个企业可借助影子价格确定有限资源的内部结算价格，以控制有限资源的使用。社会上对一些紧缺资源可借助影子价格确定使用一个单位资源必须上交的利润，以控制一些效益低的

11、企业自觉节约使用紧缺资源，使紧缺资源发挥更大的经济效益。一、对偶单纯形法的基本思路（1）单纯形法思路：对原问题的一个基可行解（此时所有右端项bi0） ，判别是否所有的检验数j0。若是且基变量中无人工变量，即找到了问题的最优解；若否，再找出相邻的目标函数值更大的基可行解， 继续判断检验数，直到找到最优解（如果存在）。（2）根据对偶原理性质可知，在同一个单纯形表中，如果原问题为可行解（此时所有右端项bi0），且所有检验数j0，则原问题和对偶问题都达到最优解。2.4 对偶单纯形法（3）对偶单纯法的基本思想是：先找出对偶问题的基可行解（单纯形表中所有的检验数j0），若此时原问题为非可行解（即不满足所有

12、右端项0），则一直保持对偶问题为可行解的条件下，利用对偶单纯法进行迭代，一直到原问题也为可行解（即满足所有右端项0），这时也就同时得到了原问题和对偶问题的最优解。注意：对偶单纯形法是利用对偶原理求解原问题的一种方法，而不是求解对偶问题解的单纯形法。（1）对于线性规划问题，列出初始单纯形表，要求所有的检验数j0，但b列不要求全为非负（即0 ） ；若b列的数字全为非负，则已得到最优解；若不全为非负则转下一步；（2）确定换出基变量xr；（3）确定换入基变量xs； ( xs必须是arj0，则按单纯形法继续迭代计算找出最优解。（三）增加一个变量 xj的分析解：假设生产该新产品的数量为x6（新增变量），c

13、63，P6=(3,4,2)T，根据步骤，先计算检验数和P6将其反映到最终单纯形表中得例：上例中，设美佳公司又计划推出新型号的家电III，生产一件所需设备A、设备B以及调试工序的时间分别为3h、4h、2h，该产品预期利润为3元/件，试分析该产品是否值得投产，若投产该公司的最优生产计划有什么变化？CBCj210003xBbx1x2x3x4x5x60 x315/20015/4-15/2-72x17/21001/4-1/201x23/2010-1/43/22cj-zj000-1/4-1/21有大于零的检验数，继续用单纯形法迭代，最终得到CBCj210003xBbx1x2x3x4x5x60 x351/4

14、07/213/8-9/402x17/21001/4-1/203x63/401/20-1/83/41cj-zj0-1/20-1/8-5/40故最优生产计划为每天生产7/2件家电I和3/4件家电III。解：先将生产工时变化后的新家电II看作是一种新产品，生产量为x2, 参考上例的步骤，计算检验数2和新增变量对应列向量P2，并反映到最终单纯形表中。其中：（四）分析参数aij的变化例2-4： 在例2-1中，若家电II每件需须设备A，B和调试工时变为8h、4h和1h，该产品的利润变为3元/件，试重新确定美佳公司最优生产计划。CBCj213000 xBbx1x2x2x3x4x50 x315/20011/2

15、15/4-15/22x17/2101/201/4-1/21x23/2011/20-1/43/2cj-zj003/20-1/4-1/2CBCj23000 xBbx1x2x3x4x50 x3-90014-242x121001/2-23x23010-1/23cj-zj0001/2-5 因x2已变换为x2，故上表用x2 替换基变量x2(非最小规则)并在下一个表中不再保留x2 ，得： 上一步的表中原问题与对偶问题均为非可行解，故先设法使原问题为可行解。表中第一行约束为：替换上表的第一行，重新计算检验数得:两端乘(-1)再加上人工变量x6得:92446543xxxx=+-9244543xxx-=-+CBCj23000-MxBbx1x2x3x4x5x6