线性规划对偶理论ppt课件.ppt
1,运筹学Operations Research,陈志松,2,线性规划对偶理论,线性规划对偶理论概述线性规划对偶问题提出线性规划对偶问题规范形式线性规划对偶问题一般形式线性规划对偶问题基本性质线性规划对偶问题的经济解释,3,线性规划对偶理论概述,线性规划对偶理论自1947年提出以来，已经有了很大发展，已成为线性规划的必不可少的重要基础理论。对偶理论是线性规划中的一个最重要的最有趣的概念。支持对偶理论的基本思想是，每一个线性规划问题都存在一个与其对偶的问题。在求出一个问题解的时候，也同时给出了另一问题的解。线性规划对偶问题以及对偶理论中对偶定理的运用是线性规划中主要考点。,4,对偶问题的提出,5,对偶问题的提出,6,对偶问题的提出,LP1与LP2 两个线性规划问题的表现形式和系数之间存在许多对应关系。 并且我们称前者为原问题，后者是前者的对偶问题。,7,规范形式下对偶关系的一般形式,8,规范形式下对偶关系的一般形式,9,规范形式原问题与对偶问题变换规则,10,线性规划问题对偶问题举例,例3.1 写出下列线性规划问题的对偶问题,11,非规范形式的对偶关系,12,如何直接写出非对称形式的对偶问题,13,如何直接写出非对称形式的对偶问题,14,表3-1,15,如何直接写出非对称形式的对偶问题,只要记住规范形式下的对偶关系以及上述规则，就可以准确无误并很快写出其对偶问题。,16,【例3.3】写出下列线性规划的对偶问题,【解】目标函数求最小值，应将表31的右边看作原问题，左边是对偶问题，原问题有3个约束4个变量，则对偶问题有3 个变量4个约束，对偶问题为：,=,y10，,y20，,y3无约束,17,线性规划对偶问题的基本性质,下面介绍对偶基本性质时，一般假定是如下规范对偶关系。,对偶问题是（记为DP）：,这里A是mn矩阵X是n1列向量，Y是1m行向量。假设Xs与Ys分别是（LP）与（DP）的松驰变量。,设原问题是（记为LP）：,18,【性质1】 对称性 对偶问题的对偶是原问题。,【证】设原问题是,它与下列线性规划问题是等价的：,再写出它的对偶问题。,它与下列线性规划问题是等价的,即是原问题。,可知，它的对偶问题是,19,【证】因为X、Y是可行解，故有AXb, X0及YAC，Y0,将不等式 AXb,【性质2】 弱对偶性 设X、Y分别为LP(max)与DP(min)的可行解，则,两边左乘Y，得Y0AXY0b,再将不等式YAC两边右乘X，得C XYAX,故 C XYAXYb,这一性质说明了两个线性规划互为对偶时，求最大值的线性规划的任意目标值都不会大于求最小值的线性规划的任一目标值，不能理解为原问题的目标值不超过对偶问题的目标值。,20,【性质3】 无界性 若原问题（对偶问题）有无界解，则其对偶问题（原问题）无可行解。,可理解为：在互为对偶的两个问题中，若一个问题可行且具有无界解，则另一个问题无可行解,证：假定原问题有无界解，对偶问题有可行解 Y， Yb 。原问题有无界解，即存在C X ，根据若对偶性有， Yb C X ，显然矛盾，故命题成立。,注意：（1）这个定理的逆定理不成立，即若一个问题无可行解，另一问题不一定有无界解，也可能无可行解； （2）若原问题可行且另一个问题不可行，则原问题具有无界解,21,例如：,无可行解，而对偶问题,有可行解，由性质（3）知必有无界解。,22,【性质4】最优性定理 设X0与Y0分别是（LP）与（DP）的可行解，则当C X0= Y0b 时，X0、Y0是（LP）与（DP）的最优解,【证】若C X0= Y0b ，由性质2，对偶问题的所有可行解Y都存在 Y b CX。因为C X0= Y0b ，所以Y b Y0b ，可见Y0是使目标函数取值最小的可行解，因而Y0是最优解。同理可证， X0是最优解,23,【性质5】 弱对偶性若互为对偶的两个问题其中一个有最优解，则另一个也有最优解，且最优值相同。,【证】设（LP）有最优解X0,那么对于最优基B必有C-CBB-1A0与CBB-10，即有YAC与Y0，这里Y= CBB-1 ，从而Y是可行解，对目标函数有,由性质4知Y是最优解。,由性质 5 还可推出另一结论：若（LP）与（DP）都有可行解，则两者都有最优解，若一个问题无最优解，则另一问题也无最优解。,24,【例3.4】 证明下列线性规划无最优解：,【证】容易看出X=（4，0，0）是一可行解，故问题可行。对偶问题,将三个约束的两端分别相加得而第二个约束有y21，矛盾，故对偶问题无可行解，因而原问题具有无界解，即无最优解。,25,【证】设X和Y是最优解,由性质4 ，C X0= Y0b，由于XS和YS是松弛变量，则有,A X0XSbY0AYS=C,将第一式左乘Y0，第二式右乘X0得,Y0A X0Y0XSY0bY0A X0YS X0=C X0,26,显然有,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,由性质4知Y与X是（LP）与（DP）的最优解。证毕。,27,性质6告诉我们已知一个问题的最优解时求另一个问题的最优解的方法，即已知Y*求X*或已知X*求Y*。,Y * XS=0和YS X * =0,两式称为互补松弛条件。将互补松弛条件写成下式,由于变量都非负，要使求和式等于零，则必定每一分量为零，因而有下列关系：,28,(1)当yi*0时， ,反之当 时yi*=0；,利用上述关系，建立对偶问题（或原问题）的约束线性方程组，方程组的解即为最优解。性质6的结论和证明都是假定（P）与（D）为对称形式，事实上对于非对称形式，性质6的结论仍然有效。,【例3.5】 已知线性规划,的最优解是 求对偶问题的最优解。,29,【解】对偶问题是,因为X10，X20，所以对偶问题的第一、二个约束的松弛变量等于零，即,解此线性方程组得y1=1,y2=1,从而对偶问题的最优解为Y=（1，1），最优值w=26。,30,【例3.6】 已知线性规划,的对偶问题的最优解为Y=（0，2），求原问题的最优解。,【解】对偶问题是,31,解方程组得：x 1=5,x 3=1, 所以原问题的最优解为X=（5，0，1），最优值Z=12。,因为y20，所以原问题第二个松弛变量 =0，由y1=0、y2=-2知，松弛变量 ，故x2=0，则原问题的约束条件为线性方程组：,32,33,34,35,36,37,【性质6】互补对偶性LP(max)的检验数的相反数对应于DP(min)的一组基本解. 其中第j个决策变量xj的检验数的相反数对应于（DP）中第j个松弛变量 的解，第i个松弛变量 的检验数的相反数对应于第i个对偶变量yi的解。反之，（DP）的检验数（注意：不乘负号）对应于（LP）的一组基本解。证明略。,38,【例3.9】 线性规划,（1）用单纯形法求最优解；（2）写出每步迭代对应对偶问题的基本解；（3）从最优表中写出对偶问题的最优解；,【解】（1）加入松弛变量x4、x5后，单纯形迭代如表2-2所示。,39,表3-1,40,最优解X=（4，6，0），最优值Z=6426=12；,（2）设对偶变量为y1、y2,松弛变量为y3、y4、y5,Y=（y1、y2、 y3、y4、y5），由性质6得到对偶问题的基本解 （y1、y2、 y3、y4、y5） =（4，5，1，2，3），即,表22（1）中=（6，2，1，0，0）， 则Y（1）=（0，0，-6，2，1）,表22（2）中=（0，1，5，3，0）， 则Y（2）=（3，0，0，1，5）,表22（3）中=（0，0，11，2，2）， 则Y（3）=（2，2，0，0，11）,（3）因为表31（3）为最优解，故 Y（3）=（2，2，0，0，11）为对偶问题最优解；,41,对偶问题的基本性质应用举例,42,对偶问题的基本性质应用举例,43,对偶问题的经济解释-影子价格,44,对影子价格的进一步讨论,45,对影子价格的进一步讨论,
