运筹学06线性规划的灵敏度分析与对偶课件.ppt

《运筹学06线性规划的灵敏度分析与对偶课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第六章单纯型法灵敏度分析与对偶6.1单纯型表的灵敏度分析6.2线性规划的对偶问题6.3对偶规划的基本性质6.4对偶单纯型法6.2线性规划的对偶问题(1)对偶问题的提出例1、生产组织与计划问题A,B各生产多少,可获最大利润?可用资源煤劳动力仓库AB123202单位利润4050306024MaxZ=40x1+50x2x1+2x2303x1+2x2602x224x1，x20s.t目标函数约束条件如果因为某种原因，不愿意自己生产，而希望通过将现有资源承接对外加工来获得收益，那么应如何确定各资源的使用价格？Max

2、Z=40x1+50x2x1+2x2303x1+2x2602x224x1，x20s.t目标函数约束条件两个原则所得不得低于生产的获利要使对方能够接受设三种资源的使用单价分别为y1,y2,y3y1y2y3生产单位产品A的资源消耗所得不少于单位产品A的获利生产单位产品B的资源消耗所得不少于单位产品B的获利y1+3y2402y1+2y2+2y350通过使用所有资源对外加工所获得的收益W=30y1+60y2+24y3根据原则2，对方能够接受的价格显然是越低越好，因此此问题可归结为以下数学模型：MinW=30y

3、1+60y2+24y3y1+3y2402y1+2y2+2y350y1,y2,y30s.t目标函数约束条件原线性规划问题称为原问题，此问题为对偶问题，y1,y2,y3称为影子价格(2)对偶问题的形式定义设原线性规划问题为则称下列线性规划问题为其对偶问题，其中yi(i=1,2,…,m)称为对偶变量。上述对偶问题称为对称型对偶问题。原问题简记为(P)，对偶问题简记为(D)原始问题MaxZ=CXs.t.AX≤bX≥0bAC≤Maxnm对偶问题MinW=Ybs.t.YAT≥CY≥0≥MinCTATbTnm对偶规则给

4、每个原始约束条件定义一个非负对偶变量yi(i=1,2,…,m);使原问题的目标函数系数cj变为其对偶问题约束条件的右端常数；使原问题约束条件的右端常数bi变为其对偶问题目标函数的系数；将原问题约束条件的系数矩阵转置，得到其对偶问题约束条件的系数矩阵；改变约束条件不等号的方向，即将“=<”改为“>=”；原问题“max”型，对偶问题为“min”型．例2：求线性规划问题的对偶规划解：例3：求线性规划问题的对偶规划解：例4：求线性规划问题的对偶规划解：对偶关系对应表原问题对偶问题目标函数类型MaxMin目标函数系数目标

5、函数系数右边项系数与右边项的对应关系右边项系数目标函数系数变量数与约束数变量数n约束数n的对应关系约束数m变量数m原问题变量类型与0对偶问题约束类型变量0约束的对应关系无限制＝原问题约束类型与0对偶问题变量类型约束变量0的对应关系＝无限制6.3对偶问题的基本性质定理1对偶问题的对偶就是原问题(对称性)MaxW’=-Ybs.t.-YA≤-CY≥0MinZ’=-CXs.t.-AX≥-bX≥0MaxZ=CXs.t.AX≤bX≥0MinW=Ybs.t.YA≥CY≥0对偶的定义对偶的定义定理2(弱对偶定理

6、)分别为(P),(D)的可行解，则有CbX，yXy证明：由AXb,y0有yAXby由AyC,X0有yAXCX所以CXyAXyb推论2、(P)有可行解,但无有限最优解，则(D)无可行解。证明：对任X，有CXby=CXX最优推论1、(P),(D)都有可行解，则必都有最优解。定理3、yX,分别为(P),(D)的可行解，且XyC=b,则它们是(P),(D)的最优解。定理4(强对偶性)若一对对偶问题(P)和(D)都有可行解，则它们都有最优解，且目标函数的最优值必相等。证明：(1)当X*和Y*为原问题

7、和对偶问题的一个可行解有原问题目标函数值对偶问题目标函数值所以原问题的目标函数值有上界，即可找到有限最优解；对偶问题有下界，也存在有限最优解。(2)当X*为原问题的一个最优解，B为相应的最优基,通过引入松弛变量Xs,将问题(P)转化为标准型令令所以Y*是对偶问题的可行解，对偶问题的目标函数值为X*是原问题的最优解，原问题的目标函数值为推论：若一对对偶问题中的任意一个有最优解，则另一个也有最优解，且目标函数最优值相等。一对对偶问题的关系，有且仅有下列三种：都有最优解，且目标函数最优值相等；两个都无可行解；一个问题

8、无界，则另一问题无可行解。定理5（互补松弛性）若X,Y分别为(P),(D)的可行解，则X,Y为最优解的充要条件是：同时成立互补松弛关系（松紧关系）若原问题最优解第i个约束方程为严格的不等式，则对偶问题最优解中第i个对偶变量取值必为0松约束与紧约束把某一可行点处的严格不等式约束（包括对变量的非负约束）称为松约束不起作用约束把严格等式约束称为紧约束起作用约束结论即对于最优解X*和Y*而言，