线性规划对偶理论.ppt

《线性规划对偶理论.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、运筹学OperationsResearch陈志松1线性规划对偶理论线性规划对偶理论概述线性规划对偶问题提出线性规划对偶问题规范形式线性规划对偶问题一般形式线性规划对偶问题基本性质线性规划对偶问题的经济解释2线性规划对偶理论概述线性规划对偶理论自1947年提出以来，已经有了很大发展，已成为线性规划的必不可少的重要基础理论。对偶理论是线性规划中的一个最重要的最有趣的概念。支持对偶理论的基本思想是，每一个线性规划问题都存在一个与其对偶的问题。在求出一个问题解的时候，也同时给出了另一问题的解。线性规划对偶问题以及对偶理论中对偶定理

2、的运用是线性规划中主要考点。3对偶问题的提出4对偶问题的提出5对偶问题的提出LP1与LP2两个线性规划问题的表现形式和系数之间存在许多对应关系。并且我们称前者为原问题，后者是前者的对偶问题。6规范形式下对偶关系的一般形式7规范形式下对偶关系的一般形式8规范形式原问题与对偶问题变换规则9线性规划问题对偶问题举例例3.1写出下列线性规划问题的对偶问题10非规范形式的对偶关系11如何直接写出非对称形式的对偶问题12如何直接写出非对称形式的对偶问题13原问题（或对偶问题）对偶问题（或原问题）目标函数max目标函数系数（资源限量）约束

3、条件系数矩阵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-114如何直接写出非对称形式的对偶问题只要记住规范形式下的对偶关系以及上述规则，就可以准确无误并很快写出其对偶问题。15【例3.3】写出下列线性规划的对偶问题【解】目标函数求最小值，应将表3－1的右边看作原问题，左边是对偶

4、问题，原问题有3个约束4个变量，则对偶问题有3个变量4个约束，对偶问题为：=≥≤≤y1≤0，y2≥0，y3无约束16线性规划对偶问题的基本性质下面介绍对偶基本性质时，一般假定是如下规范对偶关系。对偶问题是（记为DP）：这里A是m×n矩阵X是n×1列向量，Y是1×m行向量。假设Xs与Ys分别是（LP）与（DP）的松驰变量。设原问题是（记为LP）：17【性质1】对称性对偶问题的对偶是原问题。【证】设原问题是它与下列线性规划问题是等价的：再写出它的对偶问题。它与下列线性规划问题是等价的即是原问题。可知，它的对偶问题是18【证】因为

5、X°、Y°是可行解，故有AX°≤b,X°≥0及Y°A≥C，Y°≥0,将不等式AX°≤b【性质2】弱对偶性设X°、Y°分别为LP(max)与DP(min)的可行解，则两边左乘Y°，得Y0AX°≤Y0b再将不等式Y°A≥C两边右乘X°，得CX°≤Y°AX°故CX°≤Y°AX≤Y°b这一性质说明了两个线性规划互为对偶时，求最大值的线性规划的任意目标值都不会大于求最小值的线性规划的任一目标值，不能理解为原问题的目标值不超过对偶问题的目标值。19【性质3】无界性若原问题（对偶问题）有无界解，则其对偶问题（原问题）无可行解。可理解为：在

6、互为对偶的两个问题中，若一个问题可行且具有无界解，则另一个问题无可行解证：假定原问题有无界解，对偶问题有可行解Y°，Y°b≤∞。原问题有无界解，即存在CX°→∞，根据若对偶性有，Y°b≥CX°→∞，显然矛盾，故命题成立。注意：（1）这个定理的逆定理不成立，即若一个问题无可行解，另一问题不一定有无界解，也可能无可行解；（2）若原问题可行且另一个问题不可行，则原问题具有无界解20例如：无可行解，而对偶问题有可行解，由性质（3）知必有无界解。21【性质4】最优性定理设X0与Y0分别是（LP）与（DP）的可行解，则当CX0=Y0b时

7、，X0、Y0是（LP）与（DP）的最优解【证】若CX0=Y0b，由性质2，对偶问题的所有可行解Y’都存在Y’b≥CX’。因为CX0=Y0b，所以Y’b≥Y0b，可见Y0是使目标函数取值最小的可行解，因而Y0是最优解。同理可证，X0是最优解22【性质5】弱对偶性　若互为对偶的两个问题其中一个有最优解，则另一个也有最优解，且最优值相同。【证】设（LP）有最优解X0,那么对于最优基B必有C-CBB-1A≤0与－CBB-1≤0，即有Y°A≥C与Y°≥0，这里Y°=CBB-1，从而Y°是可行解，对目标函数有由性质4知Y°是最优解。由性

8、质5还可推出另一结论：若（LP）与（DP）都有可行解，则两者都有最优解，若一个问题无最优解，则另一问题也无最优解。23【例3.4】证明下列线性规划无最优解：【证】容易看出X=（4，0，0）是一可行解，故问题可行。对偶问题将三个约束的两端分别相加得而第二个约束有y2≥1，矛盾，故对偶问题无可