资源描述：
《第二章线性规划问题的对偶与灵敏度分析教材ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第二章线性规划的对偶与灵敏度分析§1线性规划的对偶问题§2对偶问题的基本性质§4对偶单纯形法§5灵敏度分析10/5/20211线性规划的对偶问题概念、理论及经济意义线性规划的对偶单纯形法线性规划的灵敏度分析本章内容重点10/5/20212§1线性规划的对偶问题提出问题(LP1)maxz=2x1+x2st.5x2≤156x1+2x2≤24x1+x2≤5x1,x2≥0一个公司要收购美佳公司的资源(设备)，问它至少要付出多大的代价？设备A设备B调试工序假设y1、y2、y3分别代表单位时间设备A、设备B、调试工序的出让价y1y2y310/5/20213美佳出价：出让价应不低于用
2、同等数量的资源由自己组织生产活动时所获得的利润6y2+y3≥25y1+2y2+y3≥1y1,y2,y3≥0买家还价：买家在满足上述条件的前提下，希望用最小的代价获得美佳公司的全部资源Minω＝15y1+24y2+5y310/5/20214(LP2)Minω＝15y1+24y2+5y3st.6y2+y3≥25y1+2y2+y3≥1y1,y2,y3≥0一个新的线性规划称(LP1)为原问题，(LP2)为对偶问题当LP中的变量均具有非负约束，其约束条件当目标函数求极大时均取“≤”号，而当目标函数求极小时均取“≥”时，则称这样的LP问题具有对称形式10/5/20215一般规律(1
3、)原问题有n个变量，m个约束，对偶问题有m个变量，n个约束。原问题的目标函数求极大，对偶问题的目标函数求极小(2)原问题的目标函数中变量的系数为对偶问题的约束条件的常数项，反之亦然(3)原问题与对偶问题的约束方程的系数矩阵互为转置10/5/20216(LP1)Maxz=CXs.t.AX≤bX≥0(LP2)Minω=bTYs.t.ATY≥CTY≥0非对称形式的对偶问题一般称不具有对称形式的一对线性规划为非对称形式的对偶规划。对于非对称形式的规划，一般事先转换成对称形式，然后按对应规则写出其对偶问题10/5/20217Maxz=x1+4x2+3x3St.2x1+3x2－5x
4、3≤23x1－x2+6x3≥1x1+x2+x3=4x1≥0,x2≤0,x3无约束y1y3’y2’Maxz=x1+4x2+3x3St.2x1+3x2－5x3≤2－3x1＋x2－6x3≤－1x1+x2+x3≤4－x1－x2－x3≤－4x1≥0,x2≤0,x3无约束Maxz=x1－4x’2+3x’3－3x’’3St.2x1－3x’2－5x’3+5x’’3≤2－3x1－x2－6’x3＋6x’’3≤－1x1－x2+x’3－x’’3≤4－x1+x2－x’3+x’’3≤－4x1,x’2,x’3,x’’3≥0y3’’每个约束方程对应一个对偶变量。原则：是“≤”的方程直接对应y；是“≥”
5、的对应y’；是“＝”的分别对应y’,y’’10/5/20218Minω=2y1-y’2+4y’3-4y’’3St.2y1-3y’2+y’3-y’’3≥1-3y1-y’2-y’3+y’’3≥-4-5y1-6y’2+y’3-y’’3≥35y1+6y’2-y’3+y’’3≥-3y1,y’2,y’3,y’’3≥0Minω=2y1+y2+4y3St.2y1+3y2+y3≥13y1-y2+y3≤4-5y1+6y2+y3=3y1≥0,y2≤0,y3无约束令y2=－y’2y3=y’3－y’’3Maxz=x1+4x2+3x3St.2x1+3x2－5x3≤23x1－x2+6x3≥1x1+x
6、2+x3=4x1≥0,x2≤0,x3无约束原问题对偶问题10/5/20219也可以直接利用对应关系写出线性规划问题的对偶问题Maxz=－5x1－6x2－7x3St.－x1+5x2－3x3≥15－5x1－6x2+10x3≤20x1－x2－x3=－5x1≤0,x2≥0,x3无约束Minω=15y1+20y2－5y3St.－y1－5y2+y3≥－55y1－6y2－y3≤－6－3y1+10y2－y3=－7y1≤0,y2≥0,y3无约束掌握两者之间的对应系：对偶问题的变量对应原问题的约束方程，对偶问题的约束方程对应原问题的变量（见表2-2）y1y2y3x1x2x310/5/202
7、110§2对偶问题的基本性质一、单纯形法计算的矩阵表示松弛变量m×m单位矩阵单纯形法计算时，总取I为初始基，对应的基变量为Xs。迭代若干步后基变量为XB,XB在初始单纯形表中的系数矩阵为B，将A中去掉B后的剩余部分记为N(具体情况见下表)10/5/202111非基变量基变量0XsbXBXNBNXsIσjcBcN0初始单纯形表迭代若干步基变量非基变量cBXBB－1bXBIXNXsB－1NB－1σj0cN－cBB－1N-cBB－1最终单纯形表10/5/20211221000x1x2x3x4x5cjCB基(变量)bx3x4x5000152450
