2022年线性规划的对偶原理共享 .pdf

《2022年线性规划的对偶原理共享 .pdf》由会员分享，可在线阅读，更多相关《2022年线性规划的对偶原理共享 .pdf（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、线性规划的对偶原理3.1 线性规划的对偶问题一、对偶问题的提出换位思考家具厂的线性规划问题，该问题站在家具厂管理者的角度追求销售收入最大213050maxxxz0,50212034212121xxxxxx某企业家有一批待加工的订单，有意利用该家具厂的木工和油漆工资源来加工他的产品。他需要与家具厂谈判付给该厂每个工时的价格。如果该企业家已对家具厂的经营情况有详细了解， 他可以构造一个数学模型来研究如何才能既让家具厂觉得有利可图，肯把资源出租给他，又使自己付的租金最少。目标 : 租金最少；1y- 付给木工工时的租金；2y- 付给油漆工工时的租金2150120minyyw所付租金应不低于家具厂利用这

2、些资源所能得到的利益1）支付相当于生产一个桌子的木工、油漆工的租金应不低于生产一个桌子的收入502421yy2）支付相当于生产一个椅子的木工、油漆工的租金应不低于生产一个椅子的收入30321yy3）付给每种工时的租金应不小于零0, 021yy二、原问题与对偶问题的数学模型1.对称形式的对偶名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 6 页 - - - - - - - - - 原问题和对偶问题只含有不等式约束时，一对对偶问题的模型是对称的，称为对称形式的对偶。原问题：0

3、minXbAXCXz对偶问题：0maxYCYAYbw2.非对称形式的对偶若原问题的约束条件全部是等式约束（即线性规划的标准型），即0minXbAXCXz则其对偶问题的数学模型为是自由变量YCYAYbwmax可把原问题写成其等价的对称形式：min z =CX AXb AXb X0 即 min z =CX AAXbbX0 设 Y1=(y1,y2, ,ym), Y2=(ym+1,ym+2, ,y2m) 。根据对称形式的对偶模型，写出上述问题的对偶问题：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - -

4、 - 第 2 页，共 6 页 - - - - - - - - - max w =(Y1,Y2) bb(Y1,Y2) AAC Y10 Y20 即 max w =( Y1-Y2) b ( Y1-Y2)AC Y10 Y20 令 Y= Y1-Y2,得对偶问题为： max w = Yb YA C Y是自由变量3.原问题与对偶问题的对应关系原问题（或对偶问题）对偶问题（或原问题）目标函数 min z 目标函数 max w n 个变量n 个约束变量0 约束变量0 约束自由变量约束 = m个约束m个变量约束变量0 约束变量0 约束 = 自由变量约束条件的限定向量目标函数的价值向量目标函数的价值向量约束条件的限

5、定向量原问题：无约束423143132143214321, 0,1432532maxxxxxxxxxxxxxxxxxxxz名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 6 页 - - - - - - - - - 对偶问题：0, 013312245min3213132121321321yyyyyyyyyyyyyyyyw无约束原问题：无约束3241432143243214321, 0, 02473254334324323minxxxxxxxxxxxxxxxxxxxz对偶问题

6、：无约束32132132132131321, 0, 04444373323232253maxyyyyyyyyyyyyyyyyyw3.2 对偶问题的基本性质和基本定理一、对称性定理对称性定理：对偶问题的对偶是原问题。二、弱对偶性定理弱对偶性定理：若X)0(和 Y)0(分别是原问题和对偶问题的可行解，则有C X)0(Y)0(b。三、最优性定理最优性定理：若X)0(和 Y)0(分别是原问题和对偶问题的可行解，且有C X)0(=Y)0(b，则 X)0(和 Y)0(分别是原问题和对偶问题的最优解。四、对偶定理名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - -

7、 - - - - 名师精心整理 - - - - - - - 第 4 页，共 6 页 - - - - - - - - - 对偶定理： 有一对对偶的线性规划问题，若其一有一个有限的最优解，则另一个也有最优解，且相应的目标函数值相等。若任一个问题具有无界解，则另一个问题无可行解。五、单纯型乘子Y的定理单纯型乘子Y的定理： 若线性规划原问题有一个对应于基B的最优基本可行解，则此时的单纯型乘子Y= CBB1是相应于对偶问题的一个最优解。六、对称形式对偶的互补松弛定理对称形式对偶的互补松弛定理：若 X)0(和 Y)0(分别是原问题和对偶问题的可行解，则 X)0(和Y)0(都是最优解的充要条件是，对所有i

8、和 j ，下列关系式成立：1.如果 x)0(j0，必有 Y)0(Pj=cj2.如果 Y)0( Pj0，必有 AiX)0(=bi4.如果 AiX)0(bi，必有 y)0(i=0 其中 Pj是 A的第 j 列， Ai是 A的第 i 行。互补松弛定理意味着：如果原问题最优解X)0(中第 j 个变量 x)0(j为正， 则其对偶问题中与之对应的第j 个约束式在最优情况下必呈严格等式（即其松弛变量为0）；而如果对偶问题中第 j 个约束式在最优情况下呈严格不等式，则原问题最优解X)0(中第 j 个变量 x)0(j必为 0。类似地， 如果对偶问题最优解Y)0(中第 i 个对偶变量y)0(i为正， 则其原问题中

9、与之对应的第i 个约束在最优情况下必呈严格等式（即其剩余变量为0）；而如果原问题中第i 个约束在最优情况下呈严格不等式，则对偶问题最优解Y)0(中第 i 个对偶变量y)0(i必为 0。互补松弛性：0SYX0XYSYX ,为最优解对一对对偶规划的最优解而言，如果对应某一约束条件的对偶变量的值为非零，则该约束条件取严格等式； 反之，如果某个约束条件取严格不等式，则其对应的对偶变量一定为零。七、非对称形式对偶的互补松弛定理非对称形式对偶的互补松弛定理：若 X)0(和 Y)0(分别是原问题和对偶问题的可行解，则 X)0(和 Y)0(都是最优解的充要条件是，对所有j ，下列关系式成立：1.如果 x)0(

10、j0，必有 Y)0(Pj=cj2.如果 Y)0( Pj cj，必有 x)0(j=0 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 6 页 - - - - - - - - - 例：已知线性规划问题0,122max32132132121xxxxxxxxxxxz试用对偶理论证明上述线性规划问题无最优解该问题存在可行解，如)0 ,0 ,0(X又对偶问题为0,01122min2121222121yyyyyyyyyyw由第一个约束条件知对偶问题无可行解，由此可知其原问题无最优解八、

11、最优对偶变量（影子价格）的经济解释由对偶定理可知，当达到最优解时，原问题和对偶问题的目标函数值相等。如果在得到最优解时，某种资源并未完全利用，其剩余量就是该约束中剩余变量的取值，那么该约束相对应的影子价格一定为零。因为在得到最优解时，这种资源并不紧缺，故此时再增加这种资源不会带来任何效益。反之， 如果某种资源的影子价格大于零，就说明再增加这种资源的可获量，还回带来一定的经济效益，即在原问题的最优解中，这种资源必定已被全部利用，相应的约束条件必然保持等式。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 6 页 - - - - - - - - -