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

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

2、 设 y1 ，y2 ，y3 分别为每工时设备 A、B、C 的收取费用。 线性规划问题的对偶与灵敏度分析5 线性规划原问题线性规划原问题 例2.1:某工厂拥有A、B、C三种类型的 设备，生产甲、乙两种产品。每件产品在 生产中需要占用的设备机时数，每件产品 可以获得的利润以及三种设备可利用的时 数如下表所示。求获最大利润的方案。 产品甲产品乙设备能力 （h） 设备A3 32 26565 设备B2 21 14040 设备C0 03 37575 利润（元/件）1500150025002500 线性规划问题的对偶与灵敏度分析6 Max z = 1500 x1 + 2500 x2 s.t. 3x1 + 2

3、x2 65 2x1 + x2 40 原问题原问题 3x2 75 x1 ,x2 0 Min f = 65y1+ 40y2 + 75y3 s.t. 3y1+2y2 1500 （不少于甲产品的利润） 2y1+y2+3y3 2500 对偶问题对偶问题 （不少于乙产品的利润） y1, y2 , y3 0 线性规划问题的对偶与灵敏度分析7 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- ” 线性规划问题的对偶与灵敏度分析8 一对对称形式的对偶规划之间具有 下

4、面的对应关系。 (1)若一个模型为目标求“极大”， 约束为“小于等于”的不等式，则它的 对偶模型为目标求“极小”，约束是 “大于等于”的不等式。即“max，” 和“min，”相对应。 线性规划问题的对偶与灵敏度分析9 (2)从约束系数矩阵看：一个模型中 为，则另一个模型中为AT。一个模型 是m个约束，n个变量，则它的对偶模型 为n个约束，m个变量。 (3)从数据b、C的位置看：在两个规 划模型中，b和C的位置对换。 (4)两个规划模型中的变量皆非负。 线性规划问题的对偶与灵敏度分析10 非对称形式的对偶规划 一般称不具有对称形式的一对线性规划为 非对称形式的对偶规划。 对于非对称形式的规划，可

5、以按照下面 的对应关系直接给出其对偶规划。 （1）将模型统一为“max，”或“min， ” 的形式，对于其中的等式约束按下面 （2）、（3）中的方法处理； （2）若原规划的某个约束条件为等式约束， 则在对偶规划中与此约束对应的那个变量取值 没有非负限制； 1 x2x3x0 j x 1 y11a12a13a 1 b2y21a22a23a 2 b 3 y31a32a33a3b 4 y41a42a43a4b 0 j y 1 c2c3c 1 x2x3x0 j x 1 y11a12a13a 1 b2y21a22a23a 2 b 3 y31a32a33a3b 4 y41a42a43a4b 0 j y 1

6、c2c3c 1 x2x3x0 j x 1 y11a12a13a 1 b2y21a22a23a 2 b 3 y31a32a33a3b 4 y41a42a43a4b 0 j y 1 c2c3c 线性规划问题的对偶与灵敏度分析11 （3）若原规划的某个变量的值没有非负限 制，则在对偶问题中与此变量对应的那个 约束为等式。 下面对关系（2）作一说明。对于关系（3） 可以给出类似的解释。 设原规划中第一个约束为等式： a11x1 + + a1nxn = b1 那么，这个等式与下面两个不等式等价 线性规划问题的对偶与灵敏度分析12 11111 11111 . . bxaxa bxaxa nn nn 这样，

7、原规划模型可以写成 mjx bxaxa bxaxa bxaxa xcxcZ j mnmnm nn nn nn , 2 , 1, 0 max 11 11111 11111 11 线性规划问题的对偶与灵敏度分析13 此时已转化为对称形式，直接写出对偶规划 没有非负限制 1211 1111 22112112 11111111 221111 ,0, , min yyyyy cyayaya cyayaya cyayaya ybybybybf m nmmnnn mm mm mm 这里，把 y 1 看作是 y 1 = y 1 - y1， 于是 y1 没有非负限制，关系（2）的说明 完毕。 线性规划问题的对偶

8、与灵敏度分析14 例3.1 写出下面线性规划的对偶规划 模型 解 先将约束条件变形为“”形式 没有非负限制 3214 321 431 4321 4321 , 0,105 30422 60272 2523 75max xxxx xxx xxx xxxx xxxxZ 线性规划问题的对偶与灵敏度分析15 没有非负限制 4321 4 4 321 431 4321 ,0,0 5 10 30422 60272 2523 xxxx x x xxx xxx xxxx 再根据非对称形式的对应 关系，直接写出对偶规划 线性规划问题的对偶与灵敏度分析16 0, 72 5472 123 122 510306025mi

9、n 54321 5421 321 31 321 54321 yyyyy yyyy yyy yy yyy yyyyyf 没有非负限制 线性规划问题的对偶与灵敏度分析17 (原问题与对偶问题解的关系） 考虑（LP）和（DP） 定理3-1 (弱对偶定理） 若 x, y 分别为（LP) 和（DP） 的可行解，那么cTx bTy。 推论 若（LP）可行，那么（LP） 无有限最优解的充分必要条件是（LD） 无可行解。 线性规划问题的对偶与灵敏度分析18 定理3-2 (最优性准则定理) 若x,y分别(LP),(DP)的可行解,且 cTx=bTy ，那么x,y分别为(LP)和(DP) 的最优解。 定理3-3

10、(主对偶定理) 若(LP)和(DP)均可行 那么(LP)和 (DP)均有最优解,且最优值相等。 以上定理、推论对任意形式的相 应性规划的对偶均有效 线性规划问题的对偶与灵敏度分析19 是一个向量，它的分量表示最优目 标值随相应资源数量变化的变化率。 若x*,y* 分别为（LP）和（DP）的最优解， 那么， cT x* = bT y* 。 根据 f = bTy*=b1y1*+b2y2*+bmym* 可知 f / bi = yi* yi* 表示 bi 变化1个单位对目标 f 产生 的影响，称 yi* 为 bi的影子价格。 注意：注意：若 B 是最优基， y* = (BT)-1 cB 为影子价格向量

11、。 线性规划问题的对偶与灵敏度分析20 影子价格的经济含义 (1)影子价格是对现有资源实现最 大效益时的一种估价 企业可以根据现有资源的影子价 格，对资源的使用有两种考虑：第一， 是否将设备用于外加工或出租，若租 费高于某设备的影子价格，可考虑出 租该设备，否则不宜出租。第二，是 否将投资用于购买设备，以扩大生产 能力，若市价低于某设备的影子价格， 可考虑买进该设备，否则不宜买进。 线性规划问题的对偶与灵敏度分析21 （2） 影子价格表明资源增加对总效益 产生的影响。根据推论推论“设x0和y0分别为原 规划（P）和对偶规划（D）的可行解，当 cx0=bTy0时，x0、y0分别是两个问题的最优

12、解”可知，在最优解的情况下，有关系 因此，可以将z*看作是bi,i=1,2， ,m的 函数，对bi求偏导数可得到 这说明，如果右端常数增加一个单位，则目 标函数值的增量将是 * 22 * 11 * mmy bybybfZ miy b Z i i ,2,1, * * miy i ,2,1, * 线性规划问题的对偶与灵敏度分析22 影子价格反映了不同的局部或个 体的增量可以获得不同的整体经济效 益。如果为了扩大生产能力，考虑增 加设备，就应该从影子价格高的设备 入手。这样可以用较少的局部努力， 获得较大的整体效益。 线性规划问题的对偶与灵敏度分析23 需要指出，影子价格不是固定不变 的，当约束条件

13、、产品利润等发生变化 时，有可能使影子价格发生变化。另外， 影子价格的经济含义（2），是指资源在 一定范围内增加时的情况，当某种资源 的增加超过了这个“一定的范围”时， 总利润的增加量则不是按照影子价格给 出的数值线性地增加。这个问题还将在 灵敏度分析一节中讨论。 线性规划问题的对偶与灵敏度分析24 标准形式： Max z = 50 x1 + 100 x2 s.t. x1 + x2 + x3 = 300 2x1 + x2 + x4 = 400 x2 + x5 = 250 x1 ,x2 ,x3 ,x4 ,x5 0 线性规划问题的对偶与灵敏度分析25 50100000 CBXBx1x2x3x4x5

14、 i 0 x330011100300 0 x440021010400 0 x52500(1)001250 -z050100*000 0 x350(1)010-150 0 x41502001-175 100 x225001001 -z -25000 50*000-100 50 x1501010-1 0 x45000-211 100 x225001001 -z -27500 00-500-50 -c-cB BT TB B-1 -1 I I B B=(p p1 1, p, p4 4,p,p2 2 ) oT B B-1 -1 最优解 x1 = 50 x2 = 250 x4 = 50 影子价格影子价格

15、y y1 1 = 50 = 50 y y2 2 = 0 = 0 y y3 3 = 50 , = 50 , B B-1 -1对应的检验数 对应的检验数 T T = = c cB BT TB B-1 -1 。 。 线性规划问题的对偶与灵敏度分析26 对偶单纯形法的基本思想 对偶单纯形法的基本思想是： 从原规划的一个基本解基本解出发，此基本 解不一定可行，但它对应着一个对偶对偶 可行解可行解（检验数非正），所以也可以 说是从一个对偶可行解出发；然后检 验原规划的基本解是否可行，即是否 有负的分量，如果有小于零的分量， 则进行迭代，求另一个基本解，此基 本解对应着另一个对偶可行解（检验 数非正）。 线

16、性规划问题的对偶与灵敏度分析27 如果得到的基本解的分量皆 非负则该基本解为最优解。也就 是说，对偶单纯形法在迭代过程 中始终保持对偶解的可行性（即 检验数非正），使原规划的基本 解由不可行逐步变为可行，当同 时得到对偶规划与原 规划的可行解时，便 得到原规划的最优解。 线性规划问题的对偶与灵敏度分析28 对偶单纯形法在什么情况下使用 ： 应用前提：有一个基，其对应的基满 足: 单纯形表的检验数行全部非正（对 偶可行）； 变量取值可有负数（非可行解）。 注：通过矩阵行变换运算，使所有相 应变量取值均为非负数即得到最优单纯形 表。 线性规划问题的对偶与灵敏度分析29 w 1.建立初始对偶单纯形表

17、,对应一个基本解, 所有检验数均非正,转2； 2.若b0,则得到最优解,停止;否则,若有 bk0则选k行的基变量为出基变量,转3 3.若所有akj0( j = 1,2,n )，则原 问题无可行解,停止;否则,若有akj0 则选 =minj / akjakj0=r/akr那么 xr为进基变量,转4； 4.以akr为转轴元,作矩阵行变换使其变为1, 该列其他元变为0,转2。 对偶单纯形法求解线性规划问题对偶单纯形法求解线性规划问题 过程：过程： 线性规划问题的对偶与灵敏度分析30 例3.2：求解线性规划问题：求解线性规划问题： 标准化：标准化： Max z = - 2x1 - 3x2 - 4x3

18、s.t. -x1-2x2-x3+x4= -3 -2x1+x2-3x3+x5= -4 x1,x2,x3,x4,x5 0 Min f = 2x1 + 3x2 + 4x3 S.t. x1 + 2x2 + x3 3 2x1 - x2 + x3 4 x1 , x2 , x3 0 线性规划问题的对偶与灵敏度分析31 w表格对偶单纯形法 C I -2-3-400 C B X B bX 1 X 2 X 3 X 4 X 5 0 X4 -3-1-2-110 0 X5 -4-21-301 j -2-3-400 0 X4 -10-5/21/21-1/2 -2 X1 21-1/23/20-1/2 j 0-4-10-1

19、-3 X2 2/501-1/5-2/51/5 -2 X1 11/ 5 107/5-1/5-2/5 j 00-9/5-8/5-1/5 线性规划问题的对偶与灵敏度分析32 单纯形法和对偶单纯形法步骤 是 是 是是 否否 否否 所有所有 得到 最优解 计算计算 典式对应原规划的 基本解是可行的 典式对应原规划的 基本解的检验数 所有所有 计算计算 以为中心元素进行迭代以为中心元素进行迭代 停 没 有 最 优 解 没 有 最 优 解 单纯形法对偶单纯形法 0 j 0 i b 0max jjk 0min iie bbb 0 ik a0 lj a ek e ik ik i a b a a b 0min e

20、k k ej ej i a a a 0min0csMinj/asjasj0br Min-bi/airair0 线性规划问题的对偶与灵敏度分析47 例3.5: 上例最优单纯形表如下 C i 23000 C B X B BX 1 X 2 X 3 X 4 X 5 2 X 1 41001/40 0 X 5 400-21/21 3 X 2 2011/2-1/80 j 00-1.5-1/80 线性规划问题的对偶与灵敏度分析48 0 0.25 0 这里 B 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* = 17 线性规划问题的对偶与灵敏度分析49 增加一个变量 增加变量 xn+1 则有相应的 pn+1 ,cn+1 。 那么 计算出B B-1pn+