运筹学——线性规划的对偶理论

《运筹学——线性规划的对偶理论》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第2章线性规划的对偶理论及其应用线性规划最重要的理论之一进行经济分析的重要工具上堂课的主要内容：1、对称型对偶问题：2、标准型的对偶问题：则对偶问题（D）为：原问题对偶问题目标函数max目标函数min目标函数系数约束方程常数列约束方程常数列目标函数系数变量个数n约束方程个数n约束方程个数m变量个数m约束方程≤变量≥0≥≤0=无符号约束变量≥0约束方程≥≤0≤无符号约束=系数矩阵A3、混合型对偶问题§2.2对偶线性规划解的理论最优单纯形表：对偶问题剩余变量对偶问题的变量最优单纯形表：原问题的松弛变量原问题的变量常数项010-1/43/

2、23/21001/4-1/27/20015/4-15/215/2000-1/4-1/2Z-17/2y1y2y3y4y5常数项-15/200-7/2-3/2y2-5/410-1/41/41/4y315/2011/2-3/21/2最优值Z*=17/2最优值W*=17/2最优解（7/2，3/2）最优解（0，1/4，1/2）定理2.1对偶问题的对偶就是原问题。（即互为对偶规划）一、对称定理：设原问题（P）对偶问题（D）二、弱对偶性定理：推论2、若原问题（P）和其对偶问题（D）都存在可行解，则（P）和（D）都存在最优解推论1：若（P）有可行解，

3、但无上界，则（D）无可行解。若（D）有可行解，但无下界，则（P）无可行解定理2.3原线性规划（P）与其对偶规划（D）存在以下对应关系：（1）（P）有最优解的充要条件是（D）有最优解（2）若X*和Y*分别是（P）和（D）的可行解，则X*和Y*分别是（P）和（D）的最优解的充要条件是：CX*=Y*b三、对偶性定理：由定理2.2的推论2知：（D）有最优解充分性：由定理2.1知，（P）与（D）互为对偶，充分性同理证明（1）（P）有最优解的充要条件是（D）有最优解B为最优基（2）若X*和Y*分别是（P）和（D）的可行解，则X*和Y*分别是（P）

4、和（D）的最优解的充要条件是CX*=Y*b证明：必要性，设X*和Y*分别是（P）和（D）的最优解，由定理2.2,必有CX*≤Y*b设（P）的最优解X*对应的最优基为B所以CX*=Y*b充分性，设X*和Y*分别是（P）和（D）的可行解，且CX*=Y*b证：设X是（P）的任一可行解，由定理2.2，必有CX≤Y*b=CX*所以X*是（P）的最优解同理可证Y*（D）的最优解要证X*和Y*分别是（P）和（D）的最优解定理2.3原问题（P）与其对偶问题（D）存在以下对应关系：（1）（P）有最优解的充要条件是（D）有最优解（2）若X*和Y*分别是（

5、P）和（D）的可行解，则X*和Y*分别是（P）和（D）的最优解的充要条件是CX*=Y*b推论：1、若（P）有可行解而(D)无可行解，则(P)无界。若（D）有可行解而(P)无可行解，则(D)无界。3：若（P）存在最优解X*，则（D）一定存在最优解Y*，且2、原问题（P）与其对偶问题（D）最优值相同只需求出（P）或(D)中一个的最优解和最优值，即可得另一个的最优解和最优值0–1/21–1/41/41/41201/2-3/21/20–1/20-11/4–9/4Z+31/4X1X2X3X4X5常数项的最优单纯形表为：求其对偶问题的最优解和最优

6、值解：对偶问题的最优值W*=-31/4最优解推论3*：若（P）（D）为对称型对偶问题，且（P）存在最优解X*，则（D）一定存在最优解Y*，且（-1）Y*是（P）的标准型的最优单纯形表检验行中松弛变量的系数设最优基为B,X1X2X3X4X5Z25000Z-0X4101004X5010103X6120018X1X2X3X4X5Z200-50Z-15X4101004X2010103X6100-212X1X2X3X4X5Z000-1-2Z-19X4001202X2010103X1100-212最优值Z=19松弛变量X3X4X5的检验数为0，-

7、1，-2（D）的最优解Y0=（0，1，2）最优值S0=19推论2、若原问题（P）和其对偶问题（D）都存在可行解，则（P）和（D）都存在最优解推论1：若（P）有可行解，但无上界，则（D）无可行解。若（D）有可行解，但无下界，则（P）无可行解定理2.3原问题（P）与其对偶问题（D）存在以下对应关系：（1）（P）有最优解的充要条件是（D）有最优解（2）若X*和Y*分别是（P）和（D）的可行解，则X*和Y*分别是（P）和（D）的最优解的充要条件是CX*=Y*b推论：1、若（P）有可行解而(D)无可行解，则(P)无界。若（D）有可行解而(P)无

8、可行解，则(D)无界。3：若（P）存在最优解X*，则（D）一定存在最优解Y*，且2、原问题（P）与其对偶问题（D）最优值相同原问题与对偶问题解的关系：对偶问题原问题有最优解无界无可行解有最优解无界无可行解一定不可能不可能