线性规划对偶与对偶单纯形法课件.ppt

《线性规划对偶与对偶单纯形法课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、线性规划线性规划的对偶与对偶单纯形法例:某工厂拥有A、B、C三种类型的设备，生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示。求获最大利润的方案。产品甲产品乙设备能力（h）设备A3265设备B2140设备C0375利润（元/件）15002500s.t.3y1+2y2≥15002y1+y2+3y3≥2500y1,y2,y3≥0maxz=1500x1+2500x2s.t.3x1+2x2≤652x1+x2≤403x2≤75x1,x2≥0对偶问题产品甲产品乙设备能力（h）设备A3265设备B2140设备

2、C0375利润（元/件）15002500原问题（不少于甲产品的利润）（不少于乙产品的利润）产品的数量yi设备的租金minf=65y1+40y2+75y33.线性规划的对偶与对偶单纯形法考虑凸最优化问题其Lagrange函数为其中,称为Lagrange乘子，其Lagrange对偶问题是考虑经典的线性规划问题则Lagrange函数为其梯度为对偶问题为即如果有最优解则其对偶问题为得对偶问题为原始问题约束对偶问题变量=无限制考虑原始线性规划问题中变量的不同情况.于是相应的对偶问题为即原始问题变量对偶问题约束无限制=原始问题约束对偶问题变量=无限制原始问题变量对偶问题约

3、束无限制=原问题对偶问题m个原始非变量约束m个对偶变量n个原始变量n个对偶非变量约束原始非变量约束=对偶变量任意取值原始非变量约束≥对偶变量≥原始非变量约束≤对偶变量≤原始变量约束≥对偶非变量约束≤原始变量约束≤对偶非变量约束≥原始变量约束任意对偶非变量约束=例其对偶问题对偶对偶对偶的对偶还是原始问题.原问题与对偶问题的解之间只有以下3种可能的关系：（1）两个问题都有可行解，从而都有最优解.（2）一个问题为无界解，另一个问题必无可行解.（3）两个问题都无可行解.例求标准型线性规划问题的对偶.定理(弱对偶定理)设x和y分别是原始问题和对偶问题的可行解，则一个极小

4、化线性规划问题在其某一可行点处的目标函数值给出了另一个作为其对偶的极大化线性规划问题的目标函数值得一个上界；一个极大化线性规划问题在其某个可行点处的目标函数值给出了另一个作为其对偶的极小化线性规划问题的最优目标函数值的下界.两个互为对偶的线性规划问题中如果一个无有界的最优解，则另一个问题必不可行.推论推论设x*和y*分别是原始问题和对偶问题的可行解,且则x*和y*分别是原始问题和对偶问题的最优解.证明:对原始问题的任意可行解x,对对偶问题的任意可行解y,证明：反证法.假设原始问题无界,如果对偶问题可行，的目标函数提供了原始问题的最优目标函数值的一个下界，则对偶

5、问题矛盾.定理(强对偶定理)如果互为对偶的两个线性规划问题中一个有最优解,则另一个也有最优解,并且两者的最优目标函数值相等.证明：考虑标准形线性规划问题，设x*是一个最优解，则y*是对偶问题的最优解.表明：(1)如果一个线性规划问题有最优解，则在其最优解处，对偶间隙为零.(2)如果x*是原始问题的最优解，则(3)在单纯性迭代的每一步都要计算单纯形乘子向量由于在非最优解处，不成立，因而不成立从而不是对偶可行的.单纯形法的每次迭代产生一个基本可行解，它是对偶不可行的，逐次减少其对偶不可行性，一旦得到的基本可行解是对偶可行的，即已得到最优解，迭代终止.对偶单纯形法刚

6、好相反.每次迭代产生一个对偶可行的基本解(对原始问题不可行)，逐步增加其对原始问题的可行性，一旦在某步迭代得到一个对偶可行的基本可行解，即是最优解，迭代终止.例:某工厂拥有A、B、C三种类型的设备，生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示。求获最大利润的方案。产品甲产品乙设备能力（h）设备A3265设备B2140设备C0375利润（元/件）15002500minf=65y1+40y2+75y3s.t.3y1+2y2≥15002y1+y2+3y3≥2500y1,y2,y3≥0maxz=15

7、00x1+2500x2s.t.3x1+2x2≤652x1+x2≤403x2≤75x1,x2≥0对偶问题产品甲产品乙设备能力（h）设备A3265设备B2140设备C0375利润（元/件）15002500原问题（不少于甲产品的利润）（不少于乙产品的利润）例基变量x1x2x3x4x5x6右端项-f6.8300000x3-2.6-11000-800x4-3.8-30100-1000x5-1.6-10010-100x6-6-100001-6000k=1基变量x1x2x3x4x5x6右端项-f6.8300000x3-2.6-11000-800x4-3.8-30100-10

8、00x5-1.6-10010-100x