线性规划对偶理论ppt课件

1、运筹学Operations Research王慧王慧东南大学经济管理学院电子商务系暨管理工程研究 wh_whq126线性规划对偶理论p线性规划对偶理论概述p线性规划对偶问题提出p线性规划对偶问题规范形式p线性规划对偶问题一般形式p线性规划对偶问题基本性质p线性规划对偶问题的经济解释线性规划对偶理论概述 p线性规划对偶理论自1947年提出以来，已经有了很大发展，已成为线性规划的必不可少的重要基础理论。p对偶理论是线性规划中的一个最重要的最有趣的概念。支持对偶理论的基本思想是，每一个线性规划问题都存在一个与其对偶的问题。在求出一个问题解的时候，也同时给出了另一问题的解。p

2、线性规划对偶问题以及对偶理论中对偶定理的运用是线性规划中主要考点。对偶问题的提出 对偶问题的提出对偶问题的提出pLP1与与LP2 两个线性规划问题的两个线性规划问题的表现形式和系数之间存在许多对表现形式和系数之间存在许多对应关系。应关系。p 并且并且p我们称前者为原问题，后者是前我们称前者为原问题，后者是前者的对偶问题。者的对偶问题。wzminmax规范形式下对偶关系的一般形式 规范形式下对偶关系的一般形式 规范形式原问题与对偶问题变换规则 线性规划问题对偶问题举例 例例3.1 写出下列线性规划问题的对偶问题写出下列线性规划问题的对偶问题非规范形式的对偶关系 如何直接写出非对称形式的对偶问题如

3、何直接写出非对称形式的对偶问题原问题（或对偶问题）原问题（或对偶问题）对偶问题（或原问题）对偶问题（或原问题） 目标函数目标函数max目标函数系数（资源限量）目标函数系数（资源限量）约束条件系数矩阵约束条件系数矩阵A(AT) 目标函数目标函数min资源限量（目标函数系数）资源限量（目标函数系数）约束条件系数矩阵约束条件系数矩阵AT(A)变变量量n个变量个变量第第j个变量个变量0第第j 个变量个变量0第第j个变量无约束个变量无约束约约束束 n个约束个约束第第j个约束为个约束为第第j个约束为个约束为第第j个约束为个约束为=约约束束m个约束个约束第第i个约束个约束第第i个约束个约束第第i个约束为个约

4、束为=变变量量m个变量个变量第第i个变量个变量0第第i个变量个变量0第第i个变量无约束个变量无约束 表表3-1如何直接写出非对称形式的对偶问题只要记住规范形式下的对偶关系以及上述规则，就可以准确只要记住规范形式下的对偶关系以及上述规则，就可以准确无误并很快写出其对偶问题。无误并很快写出其对偶问题。 【例【例3.3】写出下列线性规划的对偶问题】写出下列线性规划的对偶问题 0, 0,1482105618827945min43213214243214321xxxxxxxxxxxxxxxxxZ无约束【解】目标函数求最小值，应将【解】目标函数求最小值，应将表表31的右边看作原问题，左边的右边看作原问题，

5、左边是对偶问题，原问题有是对偶问题，原问题有3个约束个约束4个变量，则对偶问题有个变量，则对偶问题有3 个变量个变量4个约束，对偶问题为：个约束，对偶问题为：123131231312max1810147226885wyyyyyyyyyyyy=1549y10，y20，y3无约束线性规划对偶问题的基本性质 下面介绍对偶基本性质时，一般假定是如下规范对偶关系。下面介绍对偶基本性质时，一般假定是如下规范对偶关系。0maxXbAXCXZ对偶问题是记为对偶问题是记为DP）：）：0minYCYAYbw这里这里A是是mn矩阵矩阵X是是n1列向量，列向量，Y是是1m行向量。假设行向量。假设Xs与与Ys分别是分别

6、是LP与与DP的松驰变量。的松驰变量。设原问题是记为设原问题是记为LP）：）： 【性质【性质1】 对称性对称性 对偶问题的对偶是原问题。对偶问题的对偶是原问题。 【证】设原问题是【证】设原问题是0,maxXbAXCXZ0,minYCYAYbw它与下列线性规划问题是等价的：它与下列线性规划问题是等价的：0,)max(YCYAYbw再写出它的对偶问题。再写出它的对偶问题。0,)min(XbAXCXw它与下列线性规划问题是等价的它与下列线性规划问题是等价的0,maxXbAXCXZ即是原问题。即是原问题。 可知，它的对偶问题是可知，它的对偶问题是 【证】因为【证】因为X、Y是可行解，故有是可行解，故有

7、AXb, X0及及YAC，Y0,将不等式将不等式 AXb【性质【性质2】 弱对偶性弱对偶性 设设X、Y分别为分别为LP(max)与与DP(min)的可行解，那么的可行解，那么 bYCX00两边左乘两边左乘Y，得，得Y0AXY0b再将不等式再将不等式YAC两边右乘两边右乘X，得，得C XYAX故故 C XYAXYb这一性质说明了两个线性规划互为对偶时，求最大值的线性这一性质说明了两个线性规划互为对偶时，求最大值的线性规划的任意目标值都不会大于求最小值的线性规划的任一目规划的任意目标值都不会大于求最小值的线性规划的任一目标值，不能理解为原问题的目标值不超过对偶问题的目标值。标值，不能理解为原问题的

8、目标值不超过对偶问题的目标值。【性质【性质3】 无界性无界性 若原问题对偶问题有无界若原问题对偶问题有无界解，则其对偶问题原问题无可行解。解，则其对偶问题原问题无可行解。 可理解为：在互为对偶的两个问题中，若一个问题可行且具有无可理解为：在互为对偶的两个问题中，若一个问题可行且具有无界解，则另一个问题无可行解界解，则另一个问题无可行解证：假定原问题有无界解，对偶问题有可行解证：假定原问题有无界解，对偶问题有可行解 Y， Yb 。原问题有无界解，即存在。原问题有无界解，即存在C X ，根据若，根据若对偶性有，对偶性有， Yb C X ，显然矛盾，故命题成立。，显然矛盾，故命题成立。注意：（注意：

9、（1这个定理的逆定理不成立，即若一个问题无可这个定理的逆定理不成立，即若一个问题无可行解，另一问题不一定有无界解，也可能无可行解；行解，另一问题不一定有无界解，也可能无可行解； （2若原问题可行且另一个问题不可行，则原问题具若原问题可行且另一个问题不可行，则原问题具有无界解有无界解例如：例如：0,22212min21212121xxxxxxxxz无可行解，而对偶问题无可行解，而对偶问题0,221122max21212121yyyyyyyyw有可行解，由性质有可行解，由性质3知必有无界解。知必有无界解。【性质【性质4】最优性定理】最优性定理 设设X0与与Y0分别是分别是LP与与DP的可的可行解，

10、则当行解，则当C X0= Y0b 时，时，X0、Y0是是LP与与DP的最优的最优解解【证】若【证】若C X0= Y0b ，由性质，由性质2，对偶问题的所有可行解，对偶问题的所有可行解Y都存在都存在 Y b CX。因为。因为C X0= Y0b ，所以，所以Y b Y0b ，可，可见见Y0是使目标函数取值最小的可行解，因而是使目标函数取值最小的可行解，因而Y0是最优解。是最优解。同理可证，同理可证， X0是最优解是最优解【性质【性质5】 弱对偶性若互为对偶的两个问题其中一个有弱对偶性若互为对偶的两个问题其中一个有最优解，则另一个也有最优解，且最优值相同。最优解，则另一个也有最优解，且最优值相同。【

11、证】设【证】设LP有最优解有最优解X0,那么对于最优基那么对于最优基B必有必有C-CBB-1A0与与CBB-10，即有，即有YAC与与Y0，这里，这里Y= CBB-1 ，从而，从而Y是可行解，对目标函数有是可行解，对目标函数有bYbBCXCCXBBB010由性质由性质4知知Y是最优解。是最优解。由性质由性质 5 还可推出另一结论：假设还可推出另一结论：假设LP与与DP都有可行解，都有可行解，则两者都有最优解，若一个问题无最优解，则另一问题也无最优则两者都有最优解，若一个问题无最优解，则另一问题也无最优解。解。【例【例3.4】 证明下列线性规划无最优解：证明下列线性规划无最优解：3 , 2 ,

12、1, 0324min32131321jxxxxxxxxxZj【证】容易看出【证】容易看出X=（4，0，0是一可行解，故问题可行。对是一可行解，故问题可行。对偶问题偶问题0, 0121134max212122121yyyyyyyyyw将三个约束的两端分别相加得将三个约束的两端分别相加得而第二个约束有而第二个约束有y21，矛盾，故对偶问，矛盾，故对偶问题无可行解，因而原问题具有无界解，题无可行解，因而原问题具有无界解，即无最优解。即无最优解。 212y【性质【性质6】互补松弛定理】互补松弛定理 设设X0、Y0分别为分别为LP与与DP的可的可行解，行解，XS和和YS是它的松弛变量的可行解，则是它的松

13、弛变量的可行解，则X0和和Y0是最优解当是最优解当且仅当且仅当YSX0=0和和Y0XS=0【证】设【证】设X和和Y是最优解是最优解,由性质由性质4 ，C X0= Y0b，由于，由于XS和和YS是松弛变量，则有是松弛变量，则有A X0XSbY0AYS=C将第一式左乘将第一式左乘Y0，第二式右乘，第二式右乘X0得得Y0A X0Y0XSY0bY0A X0YS X0=C X0显然有显然有 Y0XS=YS X0又因为又因为Y、Xs、Ys、X0，所以有，所以有YXS=0和和YS X=0成立。成立。反之，反之， 当当YXS=0和和YS X=0时，有时，有YA XYbYA X=C X显然有显然有Y0b=C X

14、,由性质由性质4知知Y与与X是是LP与与DP的的最优解。证毕。最优解。证毕。性质性质6告诉我们已知一个问题的最优解时求另一个问题的最优解告诉我们已知一个问题的最优解时求另一个问题的最优解的方法，即已知的方法，即已知Y*求求X*或已知或已知X*求求Y*。Y * XS=0和和YS X * =0两式称为互补松弛条件。将互补松弛条件写成下式两式称为互补松弛条件。将互补松弛条件写成下式*1*100ijmiSinSjjy xy x由于变量都非负，要使求和式等于零，则必定每一分量为零，由于变量都非负，要使求和式等于零，则必定每一分量为零，因而有下列关系：因而有下列关系：(1)当yi*0时， ,反之当 时yi

15、*=0；0iSx0iSx*(2)00,00jjSjjSyxxy时反之当时利用上述关系，建立对偶问题或原问题的约束线性方程组，利用上述关系，建立对偶问题或原问题的约束线性方程组，方程组的解即为最优解。方程组的解即为最优解。性质性质6的结论和证明都是假定的结论和证明都是假定P与与D为对称形式，事实为对称形式，事实上对于非对称形式，性质上对于非对称形式，性质6的结论仍然有效。的结论仍然有效。【例【例3.5】 已知线性规划已知线性规划3 , 2 , 1, 0162210243max321321321jxxxxxxxxxxzj的最优解是的最优解是 求对偶问题的最优解。求对偶问题的最优解。TX)0 , 2

16、 , 6(【解】对偶问题是【解】对偶问题是0,1422321610min2121212121yyyyyyyyyyw因为因为X10，X20，所以对偶问题的第，所以对偶问题的第一、二个约束的松弛变量等于零，即一、二个约束的松弛变量等于零，即422322121yyyy解此线性方程组得解此线性方程组得y1=1,y2=1,从而对偶问题的最优解为从而对偶问题的最优解为Y=（1，1），最优值），最优值w=26。【例【例3.6】 已知线性规划已知线性规划 无约束321321321321, 0, 06422minxxxxxxxxxxxxz的对偶问题的最优解为的对偶问题的最优解为Y=（0，2），求原问题的最），求

17、原问题的最优解。优解。【解】对偶问题是【解】对偶问题是021264max2121212121yyyyyyyyyyw无约，解方程组得：解方程组得：x 1=5,x 3=1, 所以原问题的最优解所以原问题的最优解为为X=（5，0，1），最优值），最优值Z=12。643131xxxx因为因为y20，所以原问题第二个松弛变量，所以原问题第二个松弛变量 =0，由，由y1=0、y2=-2知，松弛变量知，松弛变量 ，故故x2=0，则原问题的约束条件为线性方程组：，则原问题的约束条件为线性方程组： 0, 1, 0321SSSyyy2Sx【性质【性质7】互补对偶性】互补对偶性LP(max)的检验数的相反的检验数的

18、相反数对应于数对应于DP(min)的一组基本解的一组基本解. 其中第其中第j个决策变量个决策变量xj的检验数的相反数对应于的检验数的相反数对应于DP中第中第j个松弛变量个松弛变量 的解，第的解，第i个松弛变个松弛变量量 的检验数的相反数对应于第的检验数的相反数对应于第i个对偶变量个对偶变量yi的解。反之，（的解。反之，（DP的检验数注意：不乘负的检验数注意：不乘负号对应于号对应于LP的一组基本解。的一组基本解。互补的两个基解所对应的目标值相等。互补的两个基解所对应的目标值相等。证明略。证明略。jSyiSx【例【例3.9】 线性规划线性规划0,442226max32131321321xxxxxxxxxxxz（1用单纯形法求最优解；用单纯形法求最优解；（2写出每步迭代对应对偶问题的基本解；写出每步迭代对应对偶问题