线性规划对偶理论

1运筹学OperationsResearch陈志松2线性规划对偶理论线性规划对偶理论概述线性规划对偶问题提出线性规划对偶问题规范形式线性规划对偶问题一般形式线性规划对偶问题基本性质线性规划对偶问题的经济解释3线性规划对偶理论概述线性规划对偶理论自1947年提出以来，已经有了很大发展，已成为线性规划的必不可少的重要基础理论。对偶理论是线性规划中的一个最重要的最有趣的概念。支持对偶理论的基本思想是，每一个线性规划问题都存在一个与其对偶的问题。在求出一个问题解的时候，也同时给出了另一问题的解。线性规划对偶问题以及对偶理论中对偶定理的运用是线性规划中主要考点。4对偶问题的提出某公司制造两种家电产品。假定：已知各制造一件时，分别占用的设备A、设备B的台时，调试时间以及设备A、设备B和调试工序每天的可用能力，产品的单件利润如表所示，要求确定A，B两种家电各多少件，获利为最大。产品产品1产品2每天可用能力设备A（h）0515设备B（h）6224调试工序115单件利润21这是一个典型的最优生产计划制定问题。制定获得最大利润生产计划的线性规划问题为：xxz212max（LP1）212121251562245,0xxxxxxx≤≤≤≥5对偶问题的提出再从另一个角度看问题。假定：有另一个公司想把该公司的资源收买下来，它至少应付多大的代价才能让该公司愿意放弃生产活动出让自己的资源。显然，该公司出让自己资源的条件是：出让价不低于同等资源由自己组织生产时获取的盈利。设yyy321,,分别代表单位时间)(h设备A，B及调试工序的出让代价，那么，yyy321,,的取值应满足：2312362521yyyyy≥，≥又另一个公司希望用最小代价把该公司的资源收买过来，故有yyyw32152415min显然，0,1,2,3iiy≥，综合上述，便有yyyw32152415minLP2）0,,1252632132132yyyyyyyy6对偶问题的提出LP1与LP2两个线性规划问题的表现形式和系数之间存在许多对应关系。并且我们称前者为原问题，后者是前者的对偶问题。wzminmaxxxz212max（LP1）212121251562245,0xxxxxxx≤≤≤≥yyyw32152415min（LP2）2312312362521,,0yyyyyyyy≥≥≥7规范形式下对偶关系的一般形式xcxcxcznn2211max1111221121122222112201,2,,nnnnmmmnnmjaxaxaxbaxaxaxbaxaxaxbjnx≤≥≤≤ybybybwmm2211min1121111212222212121201,2,,mmmmnnmnnmiyyyaaacyyaaaxcyyyaaacimy≥≥≥≥8规范形式下对偶关系的一般形式CXzmax0AXbX≤≥Ybwmin0YACY≥≥9规范形式原问题与对偶问题变换规则观察分析上述规范形式下线性规划的原问题及其对偶问题的模型形式，可发现，按如下规则，可从线性规划原问题得到其对偶问题：（1）目标函数由max型变为min型；（2）对应原问题，每个约束行有一个对偶变量,1,2,,iimy；（3）对偶问题约束为≥型，有n行；（4）原问题的价值系数C变换为对偶问题的右端项；（5）原问题的右端项b变换为对偶问题的价值系数；（6）原问题的系数矩阵A转置后成为对偶问题的系数矩阵。根据上述变换规则，可直接写出规范形式下线性规划问题对偶问题。10线性规划问题对偶问题举例1234123412341234max346442335356450zxxxxxxxxxxxxxxxx≤≤，，，≥例3.1写出下列线性规划问题的对偶问题11非规范形式的对偶关系例3.2写出如下线性规划问题的对偶问题xxxz32134max无约束xxxxxxxxxxxx321321321321,0,04163253212如何直接写出非对称形式的对偶问题首先，按对规范形式写出对偶关系的框架（不考虑符号），对上例有123123123123123max43235236140,0,zxxxxxxxxxxxxxxx≤≥≥≤无约束231123123123123min4223134563,,wyyyyyyyyyyyyyyy13如何直接写出非对称形式的对偶问题然后，将上述原问题与对称形式下原问题作对照。CXzmaxYbwmin0AXbX≤≥0YACY≥≥为了准确无误判断对偶问题中的待定符号，我们遵从如下规则：（1）约束为等式约束与变量无约束对应。（2）符号相同的变量、约束，其对偶问题的约束、变量符号也相同。符号相反的变量、约束，其对偶问题的约束、变量符号也相反。14原问题（或对偶问题）对偶问题（或原问题）目标函数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-115如何直接写出非对称形式的对偶问题只要记住规范形式下的对偶关系以及上述规则，就可以准确无误并很快写出其对偶问题。123123123123123min24231345630,0,wyyyyyyyyyyyyyyy无约束≥≤≥≤16【例3.3】写出下列线性规划的对偶问题0,,0,1482105618827945min43213214243214321xxxxxxxxxxxxxxxxxZ无约束【解】目标函数求最小值，应将表3－1的右边看作原问题，左边是对偶问题，原问题有3个约束4个变量，则对偶问题有3个变量4个约束，对偶问题为：123131231312max1810147226885wyyyyyyyyyyyy=≥≤≤1549y1≤0，y2≥0，y3无约束17线性规划对偶问题的基本性质下面介绍对偶基本性质时，一般假定是如下规范对偶关系。0maxXbAXCXZ对偶问题是（记为DP）：0minYCYAYbw这里A是m×n矩阵X是n×1列向量，Y是1×m行向量。假设Xs与Ys分别是（LP）与（DP）的松驰变量。设原问题是（记为LP）：18【性质1】对称性对偶问题的对偶是原问题。【证】设原问题是0,,maxXbAXCXZ0,,minYCYAYbw它与下列线性规划问题是等价的：0,,)max(YCYAYbw再写出它的对偶问题。0,,)min(XbAXCXw它与下列线性规划问题是等价的0,,maxXbAXCXZ即是原问题。可知，它的对偶问题是19【证】因为X°、Y°是可行解，故有AX°≤b,X°≥0及Y°A≥C，Y°≥0,将不等式AX°≤b【性质2】弱对偶性设X°、Y°分别为LP(max)与DP(min)的可行解，则bYCX00两边左乘Y°，得Y0AX°≤Y0b再将不等式Y°A≥C两边右乘X°，得CX°≤Y°AX°故CX°≤Y°AX≤Y°b这一性质说明了两个线性规划互为对偶时，求最大值的线性规划的任意目标值都不会大于求最小值的线性规划的任一目标值，不能理解为原问题的目标值不超过对偶问题的目标值。20【性质3】无界性若原问题（对偶问题）有无界解，则其对偶问题（原问题）无可行解。可理解为：在互为对偶的两个问题中，若一个问题可行且具有无界解，则另一个问题无可行解证：假定原问题有无界解，对偶问题有可行解Y°，Y°b≤∞。原问题有无界解，即存在CX°→∞，根据若对偶性有，Y°b≥CX°→∞，显然矛盾，故命题成立。注意：（1）这个定理的逆定理不成立，即若一个问题无可行解，另一问题不一定有无界解，也可能无可行解；（2）若原问题可行且另一个问题不可行，则原问题具有无界解21例如：0,22212min21212121xxxxxxxxz无可行解，而对偶问题0,221122max21212121yyyyyyyyw有可行解，由性质（3）知必有无界解。22【性质4】最优性定理设X0与Y0分别是（LP）与（DP）的可行解，则当CX0=Y0b时，X0、Y0是（LP）与（DP）的最优解【证】若CX0=Y0b，由性质2，对偶问题的所有可行解Y’都存在Y’b≥CX’。因为CX0=Y0b，所以Y’b≥Y0b，可见Y0是使目标函数取值最小的可行解，因而Y0是最优解。同理可证，X0是最优解23【性质5】弱对偶性若互为对偶的两个问题其中一个有最优解，则另一个也有最优解，且最优值相同。【证】设（LP）有最优解X0,那么对于最优基B必有C-CBB-1A≤0与－CBB-1≤0，即有Y°A≥C与Y°≥0，这里Y°=CBB-1，从而Y°是可行解，对目标函数有bYbBCXCCXBBB010由性质4知Y°是最优解。由性质5还可推出另一结论：若（LP）与（DP）都有可行解，则两者都有最优解，若一个问题无最优解，则另一问题也无最优解。24【例3.4】证明下列线性规划无最优解：3,2,1,0324min32131321jxxxxxxxxxZj【证】容易看出X=（4，0，0）是一可行解，故问题可行。对偶问题0,0121134max212122121yyyyyyyyyw将三个约束的两端分别相加得而第二个约束有y2≥1，矛盾，故对偶问题无可行解，因而原问题具有无界解，即无最优解。212y25【性质6】互补松弛定理设X0、Y0分别为（LP）与（DP）的可行解，XS和YS是它的松弛变量的可行解，则X0和Y0是最优解当且仅当YSX0=0和Y0XS=0【证】设X°和Y°是最优解,由性质4，CX0=Y0b，由于XS和YS是松弛变量，则有AX0＋XS＝bY0A－YS=C将第一式左乘Y0，第二式右乘X0得Y0AX0＋Y0XS＝Y0bY0AX0－YSX0=CX026显然有Y0XS=－YSX0又因为Y°、Xs、Ys、X°≥0，所以有Y°XS=0和YSX°=0成立。反之，当Y°XS=0和YSX°=0时，有Y°AX°＝Y°bY°AX°=CX°显然有Y0b=CX°,由性质4知Y°与X°是（LP）与（DP）的最优解。证毕。27性质6告诉我们已知一个问题的最优解时求另一个问题的最优解的方法，即已知Y*求X*或已知X*求Y*。Y*XS=0和YSX*=0两式称为互补松弛条件。将互补松弛条件写成下式*1*100ijmiSinSjjyxyx由于变量都非负，要使求和式等于零，则必定每一分量为零，因而有下列关系：28(1)当yi*0时，,反之当时yi*=0；0iSx0iSx**(2)00,00jjSjjSyxxy时反之当时利用上述关系，建立对偶问题（或原问题）的约束线性方程组，方程组的解即为最优解。性质6的结论和证明都是假定（P）与（D）为对称形式，事实上对于非对称形式，性质6的结论仍然有效。【例3.5】已知线性规划3,2,1,0162210243max321321321jxxxxxxxxxxzj的最优解是求对偶问题的最优解。TX)0,2,6(29【解】对偶问题是0,1422321610min2121212121yyyyyyyyyyw因为X1≠0，X2≠