线性规划问题的对偶与灵敏度分析ppt课件

1、第二章 线性规划问题的对偶与灵敏度分析w线性规划的对偶问题概念、实际及经济意义w线性规划的对偶单纯形法w线性规划的灵敏度分析本章内容重点1.1.线性规划对偶问题线性规划对偶问题 对偶原理 对偶问题定义 线性规划问题写出其对偶问题，要掌握在对称方式和非对称情况下由原问题写出对偶问题的方法。 对偶定理 只需了解原问题与对偶问题解的关系，证明从略。 1.对偶问题： 假设第二章例2.1问题的设备都用于外协加工，工厂收取加工费。试问：设备 A、B、C 每工时各如何收费才最有竞争力？ 设 y1 ，y2 ，y3 分别为每工时设备 A、B、C 的收取费用。1.1.线性规划对偶问题线性规划对偶问题线性规划原问题

2、线性规划原问题 例2.1:某工厂拥有A、B、C三种类型的设备，消费甲、乙两种产品。每件产品在消费中需求占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示。求获最大利润的方案。 产品甲产品乙设备才干h设备A3 32 26565设备B2 21 14040设备C0 03 37575利润元/件1500150025002500 Max z = 1500 x1 + 2500 x2 s.t. 3x1 + 2x2 65 2x1 + x2 40 原问题 3x2 75 x1 ,x2 0 Min f = 65y1+ 40y2 + 75y3 s.t. 3y1+2y2 1500 不少于甲产品的利

3、润 2y1+y2+3y3 2500 对偶问题 不少于乙产品的利润 y1, y2 , y3 01.1.线性规划对偶问题线性规划对偶问题 2、对偶定义 对称方式： 互为对偶 (LP) Max z = cT x (DP) Min f = bT y s.t. Ax b s.t. AT y c x 0 y 0 “Max - “Min- 1.1.线性规划对偶问题线性规划对偶问题 一对对称方式的对偶规划之间具有下面的对应关系。 (1)假设一个模型为目的求“极大，约束为“小于等于的不等式，那么它的对偶模型为目的求“极小，约束是“大于等于的不等式。即“max，和“min，相对应。1.1.线性规划对偶问题线性规划

4、对偶问题 (2)从约束系数矩阵看：一个模型中为，那么另一个模型中为AT。一个模型是m个约束，n个变量，那么它的对偶模型为n个约束，m个变量。 (3)从数据b、C的位置看：在两个规划模型中，b和C的位置对换。 (4)两个规划模型中的变量皆非负。1.1.线性规划对偶问题线性规划对偶问题 非对称方式的对偶规划 普通称不具有对称方式的一对线性规划为非对称方式的对偶规划。 对于非对称方式的规划，可以按照下面 的对应关系直接给出其对偶规划。 1将模型一致为“max，或“min， 的方式，对于其中的等式约束按下面2、3中的方法处置； 2假设原规划的某个约束条件为等式约束，那么在对偶规划中与此约束对应的那个变

5、量取值没有非负限制；1.1.线性规划对偶问题线性规划对偶问题 3假设原规划的某个变量的值没有非负限 制，那么在对偶问题中与此变量对应的那个 约束为等式。 下面对关系2作一阐明。对于关系3 可以给出类似的解释。 设原规划中第一个约束为等式： a11x1 + + a1nxn = b1 那么，这个等式与下面两个不等式等价1.1.线性规划对偶问题线性规划对偶问题1.1.线性规划对偶问题线性规划对偶问题1111111111.bxaxabxaxannnn这样，原规划模型可以写成mjxbxaxabxaxabxaxaxcxcZjmnmnmnnnnnn, 2 , 1, 0max111111111111111.1

6、.线性规划对偶问题线性规划对偶问题 此时已转化为对称方式，直接写出对偶规划没有非负限制121111112211211211111111221111,0, , minyyyyycyayayacyayayacyayayaybybybybfmnmmnnnmmmmmm这里，把 y1 看作是 y1 = y1 - y1，于是 y1 没有非负限制，关系2的阐明终了。1.1.线性规划对偶问题线性规划对偶问题 例3.1 写出下面线性规划的对偶规划模型解 先将约束条件变形为“方式没有非负限制321432143143214321, 0,1053042260272252375maxxxxxxxxxxxxxxxxxxx

7、Z1.1.线性规划对偶问题线性规划对偶问题没有非负限制4321443214314321,0,051030422602722523xxxxxxxxxxxxxxxx 再根据非对称方式的对应关系，直接写出对偶规划1.1.线性规划对偶问题线性规划对偶问题0,725472123122510306025min5432154213213132154321yyyyyyyyyyyyyyyyyyyyyyf没有非负限制 3.对偶定理(原问题与对偶问题解的关系思索LP和DP 定理3-1 (弱对偶定理 假设 x, y 分别为LP) 和DP的可行解，那么cTx bTy。 推论 假设LP可行，那么LP无有限最优解的充分必要

8、条件是LD无可行解。1.1.线性规划对偶问题线性规划对偶问题 定理3-2 (最优性准那么定理) 假设x,y分别(LP),(DP)的可行解,且cTx=bTy ，那么x,y分别为(LP)和(DP)的最优解。 定理3-3 (主对偶定理) 假设(LP)和(DP)均可行 那么(LP)和(DP)均有最优解,且最优值相等。 以上定理、推论对恣意方式的相应性规划的对偶均有效1.1.线性规划对偶问题线性规划对偶问题 4. 4.影子价钱影子价钱 是一个向量，它是一个向量，它的分量表示最优目的值随相应资源数量的分量表示最优目的值随相应资源数量变化的变化率。变化的变化率。 假设假设x x* *,y,y* * 分别为分

9、别为LPLP和和DPDP的最的最优解，优解， 那么，那么， cT x cT x* * = bT y = bT y* * 。 根据根据 f = bTy f = bTy* *=b1y1=b1y1* *+b2y2+b2y2* *+ +bmym+bmym* * 可知可知 f / f / bi = yibi = yi* * yi yi* * 表示表示 bi bi 变化变化1 1个单位对目的个单位对目的 f f 产产生的影响，称生的影响，称 yi yi* * 为为 bi bi的影子价钱。的影子价钱。 留意：假设留意：假设 B B 是最优基，是最优基， y y* * = (BT)-1 cB = (BT)-1

10、 cB 为影子价钱向量。为影子价钱向量。1.1.线性规划对偶问题线性规划对偶问题 影子价钱的经济含义 (1)影子价钱是对现有资源实现最大效益时的一种估价 企业可以根据现有资源的影子价钱，对资源的运用有两种思索：第一，能否将设备用于外加工或出租，假设租费高于某设备的影子价钱，可思索出租该设备，否那么不宜出租。第二，能否将投资用于购买设备，以扩展消费才干，假设市价低于某设备的影子价钱，可思索买进该设备，否那么不宜买进。1.1.线性规划对偶问题线性规划对偶问题1.1.线性规划对偶问题线性规划对偶问题 2 影子价钱阐明资源添加对总效益产生的影响。根据推论“设x0和y0分别为原规划P和对偶规划D的可行解

11、，当cx0=bTy0时，x0、y0分别是两个问题的最优解可知，在最优解的情况下，有关系 因此，可以将z*看作是bi,i=1,2， ,m的函数，对bi求偏导数可得到 这阐明，假设右端常数添加一个单位，那么目的函数值的增量将是*22*11*mmybybybfZmiybZii,2,1,*miyi,2,1,* 影子价钱反映了不同的部分或个体的增量可以获得不同的整体经济效益。假设为了扩展消费才干，思索添加设备，就应该从影子价钱高的设备入手。这样可以用较少的部分努力，获得较大的整体效益。1.1.线性规划对偶问题线性规划对偶问题 需求指出，影子价钱不是固定不变的，当约束条件、产品利润等发生变化时，有能够使影

12、子价钱发生变化。另外，影子价钱的经济含义2，是指资源在一定范围内添加时的情况，当某种资源的添加超越了这个“一定的范围时，总利润的添加量那么不是按照影子价钱给出的数值线性地添加。这个问题还将在灵敏度分析一节中讨论。1.1.线性规划对偶问题线性规划对偶问题 5.由最优单纯形表求对偶问题最优解 规范方式： Max z = 50 x1 + 100 x2 s.t. x1 + x2 + x3 = 300 2x1 + x2 + x4 = 400 x2 + x5 = 250 x1 ,x2 ,x3 ,x4 ,x5 01.1.线性规划对偶问题线性规划对偶问题50100000CBXBx1x2x3x4x5i0 x33

13、00111003000 x4400210104000 x52500(1)001250-z050100*0000 x350(1)010-1500 x41502001-175100 x225001001-z-2500050*000-10050 x1501010-10 x45000-211100 x225001001-z-2750000-500-50-cBTB-1-cBTB-1I IB=(p1, B=(p1, p4,p2 )p4,p2 )oTB-1B-1最优解 x1 = 50 x2 = 250 x4 = 50影子价钱 y1 = 50 y2 = 0 y3 = 50 , B-1对应的检验数 T = cB

14、TB-1 。 1. 1.线性规划对偶问题线性规划对偶问题 对偶单纯形法的根本思想 对偶单纯形法的根本思想是：从原规划的一个根本解出发，此根本解不一定可行，但它对应着一个对偶可行解检验数非正，所以也可以说是从一个对偶可行解出发；然后检验原规划的根本解能否可行，即能否有负的分量，假设有小于零的分量，那么进展迭代，求另一个根本解，此根本解对应着另一个对偶可行解检验数非正。2.2.对偶单纯形法对偶单纯形法 假设得到的根本解的分量皆非负那么该根本解为最优解。也就是说，对偶单纯形法在迭代过程中一直坚持对偶解的可行性即检验数非正，使原规划的根本解由不可行逐渐变为可行，当同时得到对偶规划与原 规划的可行解时，

15、便 得到原规划的最优解。2.2.对偶单纯形法对偶单纯形法 对偶单纯形法在什么情况下运用 ： 运用前提：有一个基，其对应的基满足: 单纯形表的检验数行全部非正对偶可行； 变量取值可有负数非可行解。 注：经过矩阵行变换运算，使一切相应变量取值均为非负数即得到最优单纯形表。2.2.对偶单纯形法对偶单纯形法w 1.建立初始对偶单纯形表,对应一个根本解,一切检验数均非正,转2；w 2.假设b0,那么得到最优解,停顿;否那么,假设有bk0那么选k行的基变量为出基变量,转3w 3.假设一切akj0( j = 1,2,n )，那么原问题无可行解,停顿;否那么,假设有akj0 那么选 w =minj / akj

16、akj0=r/akr那么 w xr为进基变量,转4；w 4.以akr为转轴元,作矩阵行变换使其变为1,该列其他元变为0,转2。 对偶单纯形法求解线性规划问题对偶单纯形法求解线性规划问题过程：过程：2.2.对偶单纯形法对偶单纯形法例3.2：求解线性规划问题： 规范化：规范化： Max z = - 2x1 - 3x2 - 4x3 Max z = - 2x1 - 3x2 - 4x3 s.t. -x1-2x2-x3+x4= -3 s.t. -x1-2x2-x3+x4= -3 -2x1+x2-3x3+x5= -4 -2x1+x2-3x3+x5= -4 x1,x2,x3,x4,x5 0 x1,x2,x3,

17、x4,x5 0Min f = 2x1 + 3x2 + 4x3 S.t. x1 + 2x2 + x3 3 2x1 - x2 + x3 4 x1 , x2 , x3 0 2.2.对偶单纯形法对偶单纯形法w表格对偶单纯形法CI-2-3-400CBXBbX1X2X3X4X50 X4-3-1-2-1100 X5-4-21-301j-2-3-4000 X4-10-5/21/21-1/2-2 X121-1/23/20-1/2j0-4-10-1-3 X22/501-1/5-2/51/5-2 X111/5107/5-1/5-2/5j00-9/5-8/5-1/52.2.对偶单纯形法对偶单纯形法单纯形法和对偶单纯形

18、法步骤是是是是否否否否一切一切得到最优解计算计算典式对应原规划的根本解是可行的典式对应原规划的根本解的检验数一切一切计算计算以为中心元素进展迭代以为中心元素进展迭代停没有最优解没有最优解单纯形法对偶单纯形法0j0ib0maxjjk0miniiebbb0ika0ljaekeikikiabaab0minekkejejiaaa0min0csMinj/asjasj0brMin-bi/airair03.3.灵敏度分析灵敏度分析 例3.5: 上例最优单纯形表如下 C i23000CBX BBX 1X 2X 3X 4X 52 X 141001/400 X 5400-21/213 X 22011/2-1/80

19、j00-1.5-1/803.3.灵敏度分析灵敏度分析 0 0.25 0 这里 B-1 = -2 0.5 1 0.5 -0.125 0 各列分别对应 b1、b2、b3 的单一变化因此，设 b1 添加 4，那么 x1 ,x5 ,x2分别变为：4+04=4, 4+(-2)4=-40, 2+0.54=4用对偶单纯形法进一步求解，可得：x* = ( 4, 3, 2, 0, 0 )T f* = 173.3.灵敏度分析灵敏度分析 添加一个变量 添加变量 xn+1 那么有相应的pn+1 ,cn+1 。 那么 计算出B-1pn+1 , n+1=cn+1-cri ari n+1 填入最优单纯形表, 假设 n+1 0 那么 最优解不变； 否那么，进一步用单纯形法求解。3.3.灵敏度分析灵敏度分析例3.6:例3.4添加x6 , p6=( 2, 6, 3 )T, c6=5 计算得到Ci230005CBXBbX1X2X3X4X5X62 X141001/401.50 X5400-21/2123