《第二章线性规划问题的对偶与灵敏度分析》由会员分享，可在线阅读，更多相关《第二章线性规划问题的对偶与灵敏度分析（47页珍藏版）》请在金锄头文库上搜索。
1、第二章 线性规划的对偶与灵敏度分析 1 线性规划的对偶问题 2 对偶问题的基本性质 4 对偶单纯形法 5 灵敏度分析Date1 线性规划的对偶问题概念、理论及经济意义 线性规划的对偶单纯形法 线性规划的灵敏度分析本章内容重点Date21 线性规划的对偶问题提出 问题(LP1) max z = 2x1+x2st. 5x2156x1+2x2 24x1+x2 5x1, x20一个公司要收 购美佳公司的 资源(设备)，问 它至少要付出 多大的代价？设备A 设备B 调试工序假设y1、y2、y3分别代表单位时 间设备A、设备B、调试工序的出 让价y1y2y3Date3美佳出价：出让价应不低于用同等数量的资
2、源由自己 组织生产活动时所获得的利润6y2+y325y1+2y2+y31y1, y2, y30买家还价：买家在满足上述条件的前提下，希望用最 小的代价获得美佳公司的全部资源Min 15y1+24y2+5y3Date4(LP2) Min 15y1+24y2+5y3 st. 6y2+y325y1+2y2+y31y1, y2, y3 0一个新的 线性规划称(LP1)为原问题，(LP2)为对偶问题当LP中的变量均具有非负约束，其约束条件当目 标函数求极大时均取“”号，而当目标函数求极小 时均取“”时，则称这样的LP问题具有对称形式Date5一般规律(1) 原问题有n个变量，m个约束，对偶问题有m个变
3、量，n个约束。原问题的目标函数求极大，对偶问题 的目标函数求极小(2) 原问题的目标函数中变量的系数为对偶问题的约 束条件的常数项，反之亦然(3) 原问题与对偶问题的约束方程的系数矩阵互为转 置Date6(LP1) Max z = CX s.t. AX b X 0 (LP2) Min = bT Ys.t. AT Y CTY 0 非对称形式的对偶问题一般称不具有对称形式的一对线性规划为非对称 形式的对偶规划。对于非对称形式的规划，一般事先转换成对称形 式，然后按对应规则写出其对偶问题Date7Max z = x1 + 4x2 + 3x3 St. 2x1 + 3x2 5x3 23x1 x2 + 6
4、x3 1x1+x2+x3=4x10, x20, x3无约束y1y3y2Max z = x1 + 4x2 + 3x3 St. 2x1 + 3x2 5x3 23x1 x2 6x3 1x1+x2+x3 4x1x2x3 4x10, x20, x3无约束Max z = x1 4x2 + 3x33x3St. 2x1 3x2 5x3 +5x3 23x1 x2 6x36x3 1x1x2+x3 x3 4x1+x2x3 + x34x1 , x2 , x3, x30y3每个约束方程对应一个对 偶变量。原则：是“”的方 程直接对应y；是“”的对 应y；是“”的分别对应y, yDate8Min =2y1-y2+4y3-
5、4y3St. 2y1-3y2+y3-y31-3y1-y2-y3+y3 -4-5y1-6y2+y3-y3 35y1+6y2-y3+y3 -3y1, y2, y3, y3 0 Min =2y1+y2+4y3St. 2y1+3y2+y313y1-y2+y3 4-5y1+6y2+y3 = 3y1 0, y20, y3无约束令 y2= y2y3= y3y3Max z = x1 + 4x2 + 3x3 St. 2x1 + 3x2 5x3 23x1 x2 + 6x3 1x1+x2+x3=4x10, x20, x3无约束原 问 题对 偶 问 题Date9也可以直接利用对应关系写出线性规划问题的对偶问题Max
6、z = 5x1 6x2 7x3St. x1 + 5x2 3x3 155x1 6x2 + 10x3 20x1x2x3 =5x1 0, x2 0, x3无约束Min = 15y1+ 20y25y3St. y15y2+ y355y16y2y3 63y1+ 10y2 y3 = 7y1 0, y2 0, y3无约束掌握两者之间的对应系： 对偶问题的变量对应原问题 的约束方程，对偶问题的约 束方程对应原问题的变量（ 见表2-2）y1 y2 y3x1x2x3Date10 2 对偶问题的基本性质一、单纯形法计算的矩阵表示 松弛 变量 mm单位 矩阵单纯形法计算时，总取I为初始基，对应的基变 量为Xs。迭代若干
7、步后基变量为XB, XB在初始单纯形 表中的系数矩阵为B，将A中去掉B后的剩余部分记为 N(具体情况见下表)Date11非基变量基变量0 Xs bXB XN B NXs I jcB cN0初始 单纯 形表迭 代 若 干 步基变量非基变量cB XB B1 bXB IXN Xs B1 N B1 j0cNcBB1 N - cBB1最终 单纯 形表Date122 1 0 0 0x1 x2 x3 x4 x5cj CB 基(变量) bx3 x4 x50 0 015 24 50 5 1 0 06 2 0 1 01 1 0 0 1j2 1 0 0 0cj 2 1 0 0 0CB 基(变量) b x1 x2 x
8、3 x4 x50 x3 15/2 0 0 1 5/4 15/22 x1 7/2 1 0 0 1/4 1/21 x2 3/2 0 1 0 1/4 3/2j 0 0 0 1/4 1/2B-1BDate13五点结论（2）初始单纯形表中的常数项是b，最终单纯形表 中B1b（3）初始单纯形表中系数矩阵为A , I=B, N, I， 最终单纯形表中系数矩阵B1A , B1=B1B, B1N, B1I=I, B1N, B1（1）对应初始单纯形表中的单位矩阵I，最终单纯 形表中为B1(非常重要的指标)Date14（4）初始单纯形表中变量Xj的系数向量为Pj，最终单纯形 表中为Pj = B1Pj (1)（5）当
9、B为最优基时，在最终单纯形表中应有cNcBB1N0 (2) cBB1 0 (3) 因为XB的检验数可写为cBcBI=cB- cBB-1B=0 (4)故（4）（2）可以合并写成(5)，(3)直接写成(6)ccBB1 A0 (5)cBB10 (6)Date15如果令YT=cBB1(单纯形乘子)，则(5)、(6)可写为(7)原问题的 对偶问题从(7)式可以看出，此时原问题的最优解对应的 单纯形表中，检验数若取相反数恰好是其对偶问题 的一个可行解！而且有原问题的 最优解当原问题为最优解时，这时其对偶问题有 可行解，且两者具有相同的目标函数值Date16项项目原问题变问题变 量原问题问题 松弛变变量x1
10、 x2 x3 x4 x5x3 15/2 x1 7/2 x2 3/20 0 1 0 0 11 5/4 -15/2 0 1/4 -1/2 0 -1/4 3/2j0 0 0 -1/4 -1/2对对偶问题问题 的松弛变变量对对偶问题变问题变 量y4 y5y1 y2 y3项项目对对偶问题变问题变 量对对偶问题问题 松弛变变量y1 y2 y3 y4 y5y2 1/4 y3 1/2-5/4 1 015/2 0 1-1/4 1/4 1/2 -3/2j 15/2 0 0 7/2 3/2原问题问题 松弛变变量原问题变问题变 量x3 x4 x5x1 x2Date17定理1 (弱对偶定理）若 x, y 分别为原问题与
11、对偶问题的可行解则恒有cTx bTy二、对偶问题的基本性质定理2 (最优性定理)若x, y分别原问题与对偶问题的可行解,且cTx=bTy ， 那么x, y分别为原问题与对偶问题的最优解。Date18定理3 (对偶定理)若原问题与对偶问题均有可行解，那么它们均有最 优解,且最优解的函数值相等。定理4 (互补松弛性定理)(比较重要)若在线性规划问题的最优解中,若对应某一约束条件 的对偶变量值为非零，则约束方程取严格等式；反 之若约束方程取严格不等式，则其对应的对偶变量 一定为零。Date19对偶单纯形法的基本思想从对偶问题的可行解出发，去寻求原问题 的最优解，此时根据对偶定理，原对偶问题 均有最优
12、解 4 对偶单纯形法Date20对偶单纯形法的基本思路从原问题的一个基解出发，此基解不一定可行 ，但它对应着一个对偶可行解（检验数非正），所 以也可以说是从一个对偶可行解出发；然后检验原问题的基解是否可行，即是否有负 的分量？如果有小于零的分量，则进行迭代，求另 一个基解，此基解又对应着另一个对偶可行解（检 验数非正）。如果得到的基解的分量皆非负，则该 基解为最优解。也就是说，对偶单纯形法在迭代过 程中始终保持对偶解的可行性（即检验数非正）， 使原问题的基解由不可行逐步变为可行。当同时得到对偶问题与原问题的可行解时，便 得到原问题的最优解。Date21对偶单纯形法在什么情况下使用 ：应用前提：有一个基，其对应的基满足: 单纯形表的检验数全部非正（对偶可行） 变量取值可有负数（非可行解）。注：通过矩阵行变换运算，使所有相应变量取 值均为非负数即得到最优单纯型表。Date221.建立初始对偶单纯形表,对应一个
