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

文档介绍：线性规划线性规划的对偶与对偶单纯形法例:某工厂拥有A、B、C三种类型的设备,生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数,每件产品可以获得的利润以及三种设备可利用的时数如下表所示。求获最大利润的方案。产品甲产品乙设备能力(h)设备A3265设备B2140设备C0375利润(元/件)+2y2≥15002y1+y2+3y3≥2500y1,y2,y3≥0maxz=1500x1++2x2≤652x1+x2≤403x2≤75x1,x2≥0对偶问题产品甲产品乙设备能力(h)设备A3265设备B2140设备C0375利润(元/件)15002500原问题(不少于甲产品的利润)(不少于乙产品的利润)产品的数量yi设备的租金minf=65y1+40y2+,称为Lagrange乘子,其Lagrange对偶问题是考虑经典的线性规划问题则Lagrange函数为其梯度为对偶问题为即如果有最优解则其对偶问题为得对偶问题为原始问题约束对偶问题变量=无限制考虑原始线性规划问题中变量的不同情况.