13节线性规划对偶理论.pptx

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