第2章线性规划对偶问题.ppt

《第2章线性规划对偶问题.ppt》由会员分享，可在线阅读，更多相关《第2章线性规划对偶问题.ppt（59页珍藏版）》请在三一办公上搜索。

1、第2章 对偶理论,线性规划续,知识点,了解对偶问题的特点，熟悉互为对偶的问题之间的关系；掌握对偶规划的理论和性质，如可逆性、弱对偶性、对偶定理、互补松驰定理等；掌握对偶单纯形法；,主要内容,一、对偶问题的基本概念二、对称的对偶线性规划三、对偶的基本性质四、对偶单纯形法,一、对偶问题的基本概念,传统的线性规划问题：在有限的资源下如何安排生产以获得最大利润,该问题的线性规划模型为：目标函数：max Z=4x1+3x2 约束条件：2x1 2x2 1600 5x1+2.5x2 2500 x1 400 x1 0,x2 0,现在的问题：如果工厂目前不再打算生产汽车，而是将钢材和座椅以比买价更高的价格卖出去

2、（加价），把生产能力以更高的工时费接受外协加工，那么材料和工时的定价应该是多少才是合算的？,假设y1表示出售单位钢材的利润，y2表示外协加工的工时利润，y3表示出售每套大轿车座椅的利润那么生产一辆载重汽车的材料销售利润和工时利润之和不应低于出售一辆载重汽车所得的利润，即：2y1+2.5y23同样有，2y1+5y2+y3 4,为了不亏本，各种材料的利润（加价）不能为负值，即：y1、y2、y3 0工厂的总利润是出售材料的利润、工时利润和座椅利润之和，即：W=1600y1+2500y2+400y3,从工厂决策者的角度看W越大越好。但为了在市场实现交易，在满足上述条件的基础上，W应尽可能小。从而得到如

3、下线性规划模型：Min W=1600y1+2500y2+400y32y1+2.5y23 s.t.2y1+5y2+y3 4y1、y2、y3 0,线性规划原问题和对偶问题,原问题：Max Z=c1x1+cnxn a11x1+a1nxnb1 a21x1+a2nxnb2s.t.am1x1+amnxn bm X1,xn0,对偶问题：Min W=b1y1+bmym a11y1+am1ym c1 a12y1+am2ym c2s.t.a1ny1+amnym cn y1,ym 0,矩阵表述,原问题：Max Z=CTX s.t.AXb X 0对偶问题：Min W=bTY s.t.ATY C Y 0,两个模型之间的

4、关系：原问题是求最大值，而对偶问题是求最小值；原问题的约束条件是“”，而对偶问题的约束条件是“”；原问题的目标函数系数是对偶问题的约束条件右端的常数项；原问题的约束条件右端的常数项是对偶问题目标函数的系数；原问题约束条件中xi的系数是对偶问题第i个约束条件的系数，原问题第i个约束条件的系数是对偶问题的约束条件中yi的系数。,对称的对偶线性规划,定义：如果一个线性规划具备下面两个条件，则称它具有对称形式：所有的变量都是非负的；所有的约束条件都是不等式，且在目标函数是求极大值的情况下，为“”型，求极小值时，为“”型。,非对称形式的对偶问题,在原线性规划问题为Max型，且变量非负的前提下：1.原问题

5、约束条件是“”型两边都乘以“-1”转化为“”型，得到对偶规划的变量约束为：yi0,例：Max Z=x1+2x2-3x3 S.t.x1+2x2+5x31 2x1-3x2-4x3 2 x1,x2,x3 0,Max Z=x1+2x2-3x3 S.t.-x1-2x2-5x3-1 2x1-3x2-4x3 2 x1,x2,x3 0,Min W=-y1+2y2 S.t.-y1+2y2 1-2y1-3y2 2-5y1-4y2-3 y1,y2 0,令y1=-y1，上述模型化为：Min W=y1+2y2 S.t.y1+2y2 1 2y1-3y2 2 5y1-4y2-3 y1 0,y2 0,例：Max Z=x1+2

6、x2-3x3 S.t.x1+2x2+5x3 1 2x1-3x2-4x3 2 x1,x2 0,x3 0,令x3=-x3，得：Max Z=x1+2x2+3x3 S.t.x1+2x2-5x3 1 2x1-3x2+4x3 2 x1,x2,x3 0,Min W=y1+2y2 S.t.y1+2y2 1 2y1-3y2 2-5y1+4y2 3 y1,y2 0,第三个方程两边同乘-1，得 Min W=y1+2y2 S.t.y1+2y2 1 2y1-3y2 2 5y1-4y2-3 y1,y2 0,2.原问题约束条件是“=”型看成两个约束条件：”+”组成，得到对偶规划的变量约束为：yi无非负约束（即可正可负）,例

7、：Max Z=x1+2x2-3x3 S.t.x1+2x2+5x3 1 2x1-3x2-4x3=2 x1,x2,x3 0,Max Z=x1+2x2-3x3 S.t.x1+2x2+5x3 1 2x1-3x2-4x3 2 2x1-3x2-4x3 2 x1,x2,x3 0,Min W=y1+2y2-2y3 S.t.y1+2y2-2y3 1 2y1-3y2+3y3 2 5y1-4y2+4y3-3 y1,y2,y3 0,Max Z=x1+2x2-3x3 S.t.x1+2x2+5x3 1 2x1-3x2-4x3 2-2x1+3x2+4x3-2 x1,x2,x3 0,令y4=y2-y3，得：Min W=y1+

8、2y4 S.t.y1+2y4 1 2y1-3y4 2 5y1-4y4-3 y1 0,y4无符号约束,原问题与对偶问题的对应关系,例：,写出下面线性规划问题的对偶问题：1.,解：根据上述对偶关系，可以写出原问题的对偶问题：,例：,写出下面线性规划问题的对偶问题：2.,解：根据上述对偶关系，可以写出原问题的对偶问题：,对偶的基本性质,原问题：Max Z=CTX s.t.AXb X0,对偶问题：Min W=bTY s.t.ATY C Y 0,对称性：对偶问题的对偶是原问题；弱对偶性：若X是原问题的可行解，Y是对偶问题的可行解，则CTX bTY,弱对偶性的证明：AX bXTAT bTXTATY bTY

9、所以：bTY XTATY XTC=CT X,无界性：若原问题（对偶问题）为无界解，则其对偶问题（原问题）无可行解。例：说明：无界性质并不存在逆（例见：P57）,可行解是最优解的条件：设X*是原问题的可行解，Y*是对偶问题的可行解，当CTX*=bTY*时，X*，Y*是最优解。证明：由弱对偶性，可知原问题的所有可行解X均满足 CT X bTY*又因为CTX*=bTY*，所以CT X CTX*，即：X*是使目标函数取值最大的可行解。因而是最优解。同理可证Y*也是最优解。,对偶定理：若原问题有最优解，则对偶问题也有最优解，且最优目标函数值相等。,证明：设X*是原问题的最优解，则其对应的基矩阵B必有：C

10、BTB-1A-CT0，（非基变量的检验数大于或等于0，基变量的检验数等于0）即：ATY*C，其中，Y*=CBTB-1T 故Y*是对偶问题的可行解，它使：W=bTY*=bTCBTB-1T=CBTB-1b 由于X*是原问题的最优解，使目标函数值Z=CTX*=CBTB-1b由此得到：bTY*=CBTB-1b=CTX*因此，Y*是对偶问题的最优解。,原规划的检验数对应于对偶规划的一个解；对偶规划的检验数对应于原规划的一个解。特别地，若原问题的最优基为B，则其对偶问题的最优解为Y*=CBTB-1,互补松驰定理：设原问题和对偶问题的标准型分别为：若X*，Y*分别是原问题和对偶问题的可行解，那么Y*TXs=

11、0和YsTX*=0当且仅当X*、Y*为最优解。,证明：原问题 对偶问题 Max Z=CX Min W=Yb AX+Xs=b YA-Ys=C X,Xs0 Y,Ys 0 Z=CX=(YA-Ys)X=YAX-YsX W=Yb=Y(AX+Xs)=YAX+YXs 充分性：P58 必要性：P58,该定理的隐含结论：当一对对偶规划达到最优时，若一个问题的某个变量为正数，则相应的另一个问题的约束必取等式；或者一个问题中的约束条件取不等式，则相应的另一个问题的变量必为零。理由：由于X*,Y*为最优，故YsTX*=0，Y*TXs=0。如果Xi*0，所以有Ysi=0，也就有对偶问题相应的约束条件为等式约束（因为X,

12、Y都是非负的）；如果Y*j0，所以有Xsj=0，也就有对偶问题相应的约束条件为等式约束。,设原问题是：max Z=CX;AX+Xs=b;X,Xs0 对偶问题是：min W=Yb;YA-Ys=C;Y,Ys0 则原问题单纯形表的检验数行对应于其对偶问题的一个基解，其对应关系为：,例：,已知线性规划问题 的最优解为X*=(0,0,4,4)T，最优值Z*28。试用互补松驰性找出其对偶问题的最优解。,解：写出该问题的对偶问题：Min W=20y1+20y2 S.t.y1+2y21 2y1+y2 2 2y1+3y2 3 3y1+2y2 4 yi 0,i=1,2,3,4 根据互补松驰性，可得：x3*=40,

13、则2y1+3y2=3x4*=40,则3y1+2y2=4解得：y1=6/5,y2=1/5满足对偶问题的前两个约束条件，所以它是对偶问题的可行解。其对应的目标函数W*=28=Z*，从而y1=6/5,y2=1/5为对偶问题的最优解。,例：,已知线性规划问题 试用对偶理论证明上述线性规划问题无最优解。,证明：首先看到该问题存在可行解，如X=(0,0,0)，而上述问题的对偶问题为：由第一个约束条件可知对偶问题无可行解，因原问题有可行解，故无最优解（若原问题有最优解，则对偶问题也有最优解）。,对偶单纯形法,对偶单纯形法是运用对偶原理求解原问题的一种方法，而不是求解对偶问题的单纯形法。正则解：检验数全部为非

14、负的基本解，叫正则解。正则解一般不可行。如果可行，即为最优解。原理：从一个正则解出发，用单纯形法进行迭代，迭代过程中始终保持解的正则性不变，使解的不可行性逐渐消失，所得第一个可行解即为最优解。,其与单纯形法的区别在于：单纯形法在整个迭代的过程中，始终保持原问题的可行性，即常数列非负，而检验数由有负分量逐步变为全部非负，即同时得到原问题和对偶问题的最优解。对偶单纯形法在整个迭代过程中，始终保持对偶问题的可行性，即全部检验数非负，而常数列由有负分量逐步变为全部非负，即同时得到原问题和对偶问题的最优解。,对偶单纯形法的步骤,确定换出变量：在负的基变量中选择最小的基变量为换出变量；确定换入变量：用换出

15、变量的那一行具有负值的系数分别去除同列的检验数，取绝对值最小者所对应的变量为换入变量；进行迭代变换（分别进行行、列变换）；进行最优性检验：如果所得的基本解都是非负的，则此解即为最优解，反之继续迭代，直至所有基变量为非负的数值为止。,对于生产汽车的例子：,Min W=1600y1+2500y2+400y3 2y1+5y2+y3 4 s.t.2y1+2.5y2 3 y1、y2、y3 0Max(-W)=-1600y1-2500y2-400y3-My5-My7 2y1+5y2+y3-y4+y5=4 s.t.2y1+2.5y2-y6+y7=3 y1 0,i=1,2,7,Min(-W)=-1600y1-2

16、500y2-400y3-2y1-5y2-y3-4 s.t.-2y1-2.5y2-3 y1、y2、y3 0Min(-W)=-1600y1-2500y2-400y3-2y1-5y2-y3+y4=-4 s.t.-2y1-2.5y2+y5=-3 y1、y2、y3 0,解的过程：见Word文档,对偶单纯形法的优点及用途,初始可行解可以是非可行解，当检验数都是正值时，就可以进行基变换，这样就避免了增加人工变量，使运算简化；对变量较少，而约束条件很多的线性规划问题，可先将其变为对偶问题，再用对偶单纯形法求解，简化计算；可用于灵敏度分析。,影子价格影子价格代表单位资源在最优利用的条件下所产生的经济效果；影子价

17、格给出了应当购进某种资源，以增加生产量，从而获得更多利润的价格标准。,影子价格,对偶变量yi的意义是在当前的基解中对一个单位的第i种资源的估价。这种估价不是资源的市场价格，而是根据资源在生产中做出的贡献而作出的估价，我们称之为影子价格。yi=W/bi影子价格是一种动态价格，也是一种机会成本。,当bi变为bi+bi 时，,（由于，Z=CBTB-1b，故有：CBTB-1=Y*T）,影子价格的经济意义是在其它条件不变的情况下，单位资源变化所引起的目标函数最优值的变化，即对偶变量就是第个约束条件的影子价格。影子价格是针对某一具体的约束条件而言的，而问题中所有其他数据都保持不变，因此影子价格也可以理解为

18、目标函数最优值对资源的一阶偏导数。,影子价格，又称为Lagrange乘子或灵敏率系数，通常指线性规划对偶模型中对偶变量的最优解。如果原规划模型属于在一定资源约束条件下，按一定的生活消耗生产一组产品并寻求总体效益目标函数最大化问题，那么其对偶模型属于对本问题中每一资源以某种方式进行估值以便得出与最优生产计划相一致的一个企业的最低总价值。该对偶模型中资源的估价表现为相应资源的影子价格。,当所有资源按最优方式分配时，第i种资源的影子价格yi给出了第i种资源（单位）追加量的边际利润。即，在原规划模型最优基保持不变的前提下，增加（减少）单位第i种资源，原规划模型的目标函数值将增加或减少一个yi值，因此，

19、人们可以根据yi的大小，对第i种资源紧缺程度和经济效果作出判断，探讨资源的优化利用，为企业决策服务。,影子价格yi随着目标函数、约束条件的经济意义和测度单位不同而有种种不同的具体内容。如：将yi视为第i种资源的边际值。它反映了一定条件下，增加（减少）单位第i种资源占用量对目标函数增加或减少的影响程度。将yi视为第i种资源机会成本或机会损失，它反映了企业若放弃单位第i种资源的利用，将失去一次获利机会，其损失价值为yi；若增加单位第i种资源的利用，企业将赢得一次增值为yi的获利机会。,将yi看作一种附加值或附加价格，它取决于企业对第i种资源使用效果的一种评价。若第i种资源的单位市场价格为mi，当y

20、i mi时，企业愿意购进这种资源。也就是说，如果第i种资源追加一单位，作最优分配时所得利润yi比成本mi要大，单位纯利润为yi-mi，购进这种资源有利可图；如果yimi，企业愿意有偿转让这种资源，可获单位纯利 mi-yi，否则，企业将无利可图，甚至亏损。,影子价格在经济管理中的应用影子价格能指示企业内部挖潜的方向它能指出各种资源在实现企业最优目标时的影响作用：影子价格愈高的资源，表明它对目标增益的影响愈大，同时也表明这种资源对该企业来说愈稀缺和愈贵重，企业的管理者应该更加重视对这种资源的管理。对影子价格为零的资源，则考虑如何加以利用，或转让，或充分利用,影子价格在企业经营决策中的作用影子价格不

21、同市场价格，它是根据企业本身的资源情况、资源消耗系数、产品价值系数计算出来的一种价格，是新增资源所创造的价值，是边际价格。不同的企业，即使是相同的资源，其影子价格也不一定相同。同一个企业不同生产周期，资源的影子价格也不完全一样。因此，企业的决策者可以把本企业资源的影子价格与市场价格进行比较：影子价格高于市价时，可以买进；反之，则卖出,其中，cj表示单位第j种产品的利润，而iaijyj表示生产第 j 种产品所消耗的各项资源的影子价格的总和，它可以称为第 j 种产品的单位隐含成本。检验数j又可以称为是第 j 种产品的相对价值系数,影子价格在新产品开发决策中的应用企业在新产品投产前，可以利用影子价格，通过分析新产品使用资源的经济效果，以决定新产品是否应该投产。利用影子价格分析现有产品价格变动对资源紧缺情况的影响（即系数c变动对y的影响）,