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

《第3章线性规划问题的对偶与灵敏度分析课件.ppt》由会员分享，可在线阅读，更多相关《第3章线性规划问题的对偶与灵敏度分析课件.ppt（53页珍藏版）》请在三一办公上搜索。

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

2、2 ，y3 分别为每工时设备 A、B、C 的收取费用。,1.线性规划对偶问题,4,1.对偶问题： 若第二章例2.1问题的设备都,线性规划原问题,例2.1:某工厂拥有A、B、C三种类型的设备，生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示。求获最大利润的方案。,5,线性规划原问题 例2.1:某工厂拥有A、B、C三种类,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.

3、3y1+2y2 1500 （不少于甲产品的利润） 2y1+y2+3y3 2500 对偶问题 （不少于乙产品的利润） y1, y2 , y3 0,1.线性规划对偶问题,6,Max z = 1500 x1 + 2500,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.线性规划对偶问题,7,2、对偶定义1.线性规划对偶问题7,一对对称形式的对偶规划之间具有下面的对应关系。 (1)若一个模型为目标求“极大”，约束为“小于等于”的不等式，则它的对偶

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

5、接给出其对偶规划。 （1）将模型统一为“max，”或“min，” 的形式，对于其中的等式约束按下面（2）、（3）中的方法处理； （2）若原规划的某个约束条件为等式约束，则在对偶规划中与此约束对应的那个变量取值没有非负限制；,1.线性规划对偶问题,10,非对称形式的对偶规划1.线性规划对偶问题10,（3）若原规划的某个变量的值没有非负限 制，则在对偶问题中与此变量对应的那个 约束为等式。 下面对关系（2）作一说明。对于关系（3） 可以给出类似的解释。 设原规划中第一个约束为等式： a11x1 + + a1nxn = b1 那么，这个等式与下面两个不等式等价,1.线性规划对偶问题,11,（3）若原

6、规划的某个变量的值没有非负限 1.线性规,1.线性规划对偶问题,这样，原规划模型可以写成,12,1.线性规划对偶问题这样，原规划模型可以写成12,1.线性规划对偶问题,此时已转化为对称形式，直接写出对偶规划,这里，把 y1 看作是 y1 = y1 - y1，于是 y1 没有非负限制，关系（2）的说明完毕。,13,1.线性规划对偶问题 此时已转化为对称形式，直接写出对,1.线性规划对偶问题,例3.1 写出下面线性规划的对偶规划模型,解 先将约束条件变形为“”形式,14,1.线性规划对偶问题 例3.1 写出下面线性规划的对偶,1.线性规划对偶问题,再根据非对称形式的对应关系，直接写出对偶规划,15

7、,1.线性规划对偶问题 再根据非对称形式的对应关,1.线性规划对偶问题,16,1.线性规划对偶问题16,3.对偶定理(原问题与对偶问题解的关系）考虑（LP）和（DP）,定理3-1 (弱对偶定理） 若 x, y 分别为（LP) 和（DP）的可行解，那么cTx bTy。,推论 若（LP）可行，那么（LP）无有限最优解的充分必要条件是（LD）无可行解。,1.线性规划对偶问题,17,3.对偶定理 定理3-1 (弱对偶定理）,定理3-2 (最优性准则定理) 若x,y分别(LP),(DP)的可行解,且cTx=bTy ，那么x,y分别为(LP)和(DP)的最优解。,定理3-3 (主对偶定理) 若(LP)和(

8、DP)均可行 那么(LP)和(DP)均有最优解,且最优值相等。,以上定理、推论对任意形式的相应性规划的对偶均有效,1.线性规划对偶问题,18,定理3-2 (最优性准则定理) 定理3-3 (,4.影子价格 是一个向量，它的分量表示最优目标值随相应资源数量变化的变化率。 若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 为影

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

10、对偶规划（D）的可行解，当cx0=bTy0时，x0、y0分别是两个问题的最优解”可知，在最优解的情况下，有关系 因此，可以将z*看作是bi,i=1,2， ,m的函数，对bi求偏导数可得到 这说明，如果右端常数增加一个单位，则目标函数值的增量将是,21,1.线性规划对偶问题 （2） 影子价格表明资源增加对,影子价格反映了不同的局部或个体的增量可以获得不同的整体经济效益。如果为了扩大生产能力，考虑增加设备，就应该从影子价格高的设备入手。这样可以用较少的局部努力，获得较大的整体效益。,1.线性规划对偶问题,22,影子价格反映了不同的局部或个体的增量可以获得不同,需要指出，影子价格不是固定不变的，当约

11、束条件、产品利润等发生变化时，有可能使影子价格发生变化。另外，影子价格的经济含义（2），是指资源在一定范围内增加时的情况，当某种资源的增加超过了这个“一定的范围”时，总利润的增加量则不是按照影子价格给出的数值线性地增加。这个问题还将在灵敏度分析一节中讨论。,1.线性规划对偶问题,23,需要指出，影子价格不是固定不变的，当约束条件、产,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 0,1.线性规划

12、对偶问题,24,5.由最优单纯形表求对偶问题最优解1.线性规划对偶,-cBTB-1,I,B=(p1, p4,p2 ),oT,B-1,最优解 x1 = 50 x2 = 250 x4 = 50影子价格 y1 = 50 y2 = 0 y3 = 50 , B-1对应的检验数 T = cBTB-1 。,1.线性规划对偶问题,25,-cBTB-1IB=(p1, p4,p2 )oTB-1最优解,对偶单纯形法的基本思想 对偶单纯形法的基本思想是：从原规划的一个基本解出发，此基本解不一定可行，但它对应着一个对偶可行解（检验数非正），所以也可以说是从一个对偶可行解出发；然后检验原规划的基本解是否可行，即是否有负的

13、分量，如果有小于零的分量，则进行迭代，求另一个基本解，此基本解对应着另一个对偶可行解（检验数非正）。,2.对偶单纯形法,26,对偶单纯形法的基本思想2.对偶单纯形法26,如果得到的基本解的分量皆非负则该基本解为最优解。也就是说，对偶单纯形法在迭代过程中始终保持对偶解的可行性（即检验数非正），使原规划的基本解由不可行逐步变为可行，当同时得到对偶规划与原 规划的可行解时，便 得到原规划的最优解。,2.对偶单纯形法,27,如果得到的基本解的分量皆非负则该基本解为最优解。,对偶单纯形法在什么情况下使用 ： 应用前提：有一个基，其对应的基满足: 单纯形表的检验数行全部非正（对偶可行）； 变量取值可有负数

14、（非可行解）。 注：通过矩阵行变换运算，使所有相应变量取值均为非负数即得到最优单纯形表。,2.对偶单纯形法,28,对偶单纯形法在什么情况下使用 ：2.对偶单纯形法2,1.建立初始对偶单纯形表,对应一个基本解,所有检验数均非正,转2； 2.若b0,则得到最优解,停止;否则,若有bk0则选k行的基变量为出基变量,转3 3.若所有akj0( j = 1,2,n )，则原问题无可行解,停止;否则,若有akj0 则选 =minj / akjakj0=r/akr那么 xr为进基变量,转4； 4.以akr为转轴元,作矩阵行变换使其变为1,该列其他元变为0,转2。,对偶单纯形法求解线性规划问题过程：,2.对偶

15、单纯形法,29,1.建立初始对偶单纯形表,对应一个基本解,所有检,例3.2：求解线性规划问题：,2.对偶单纯形法,30,例3.2：求解线性规划问题： 标准化：Min f =,表格对偶单纯形法,2.对偶单纯形法,31,表格对偶单纯形法2.对偶单纯形法31,单纯形法和对偶单纯形法步骤,32,单纯形法和对偶单纯形法步骤是是是是否否否否所有所有得到计算计,对偶单纯形法的适用范围 对偶单纯形法适合于解如下形式的线性规划问题,2.对偶单纯形法,33,对偶单纯形法的适用范围2.对偶单纯形法33,在引入松弛变量化为标准型之后，约束等式两侧同乘-1，能够立即得到检验数全部非正的原规划基本解，可以直接建立初始对偶

16、单纯形表进行求解，非常方便。 对于有些线性规划模型，如果在开始求解时不能很快使所有检验数非正，最好还是采用单纯形法求解。因为，这样可以免去为使检验数全部非正而作的许多工作。从这个意义上看，可以说，对偶单纯形法是单纯形法的一个补充。除此之外，在对线性规划进行灵敏度分析中有时也要用到对偶单纯形方法，可以简化计算。,2.对偶单纯形法,34,在引入松弛变量化为标准型之后，约束等式两侧同乘-,单纯形表的理解（例题）,上表中6个常数 a1 , a2 , a3 , b , 1 , 2 取值在什么范围可使1、现可行解最优，且唯一？何时不唯一？2、现基本解不可行；3、问题无可行解；4、无有限最优解；5、现基本解

17、可行，由 x1 取代 x6 目标函数可改善。,35,单纯形表的理解（例题）上表中6个常数 a1 , a2 ,进一步理解最优单纯性表中各元素的含义考虑问题 Max z = c1 x1 + c2 x2 + + cn xn s.t. a11x1 + a12x2 + + a1nxn = b1 a21x1 + a22x2 + + a2nxn = b2 . . . am1x1 + am2x2 + + amnxn = bm x1 ，x2 ， ，xn 0,3.灵敏度分析,36,进一步理解最优单纯性表中各元素的含义考虑问题3.,3、灵敏度分析,无防设，xj = 0 j = m+1, , n ; xi = bi

18、i = 1 , , m 是基本可行解, 对应的目标函数典式为：z = -f + m+1xm+1+ nxn以下是初始单纯形表： m m其中：f = - ci bi j = cj - ci aij 为检验数。 向量 b = B-1 b i = 1 i = 1 A= p1, p2, , pn , pj = B-1 pj, pj = ( a1j , a2j , , amj )T ， j = m+1, , n,37,3、灵敏度分析无防设，xj = 0 j = m+1, ,ci , bj发生变化 本段重点 增加一约束或变量及A中元素发生变化通过例题学会处理,对于表格单纯形法，通过计算得到最优单纯形表。 应

19、能够找到最优基 B 的逆矩阵 B-1 ， B-1b 以及 B-1N，检验数 j 等。,3.灵敏度分析,38,ci , bj发生变化 本段重点 对于表格单纯形法,价值系数c发生变化： m 考虑检验数 j = cj - cri arij j =1,2,n i = 1,1. 若ck是非基变量的系数： 设ck变化为 ck + ck k= ck + ck -cri arik = k+ ck 只要 k 0 ,即 ck - k ，则 最优解不变；否则，将最优单纯形表 中的检验数 k 用 k取代，继续单 纯形法的表格计算。,3.灵敏度分析,39,价值系数c发生变化：,例3.3: Max z = -2x1 -

20、3x2 - 4x3 S.t. -x1-2x2-x3+x4 = - 3 -2x1+x2-3x3+x5 = - 4 x1 ,x2 ,x3 ,x4 ,x5 0,3.灵敏度分析,40,例3.3:3.灵敏度分析40,例：最优单纯形表,从表中看到3= c3+c3-(c2a13+c1a23 ) 可得到c3 9/5 时，原最优解不变。,3.灵敏度分析,41,例：最优单纯形表 从表中看到3= c3+,2、若 cs 是基变量的系数： 设 cs 变化为 cs + cs ，那么 j= cj -cri arij - ( cs + cs ) asj = j - cs asj ， i s,对所有非基变量，只要对所有非基变量

21、 j 0 ，即 j cs asj ，则最优解 不变；否则，将最优单纯形表中的检验数 j 用 j取代，继续单纯形法的表格计算。 Maxj/asjasj0csMinj/asjasj0,3.灵敏度分析,42,2、若 cs 是基变量的系数： 对所有,例3.4: Max z = 2x1 + 3x2 + 0 x3 + 0 x4+ 0 x5,s.t. x1 + 2x2 + x3 = 8 4x1 + x4 = 16 4x2 + x5 = 12 x1 , x2 , x3 , x4 , x5 0,3.灵敏度分析,43,例3.4: s.t. x1 + 2x2 + x3,例: 下表为最优单纯形表,考虑 基变量系数c2

22、发生变化,从表中看到j=cj-(c1a1j+c5 a5j+(c2+c2) a2j)j=3,4可得到 -3c21时，原最优解不变。,3.灵敏度分析,44,例: 下表为最优单纯形表,考虑从表中看到3.灵敏,右端项 b 发生变化 设分量 br 变化为 br + br ，根据第1章的讨论，最优解的基变量 xB = B-1b，那么只要保持 B-1(b + b) 0 ，则最优基不变，即基变量保持，只有值的变化；否则，需要利用对偶单纯形法继续计算。 对于问题 (LP) Max z = cT x s.t. Ax b x 0,3.灵敏度分析,45,右端项 b 发生变化3.灵敏度分析45,最优单纯形表中含有B-1

23、=( aij ）i=1,m; j=n+1,n+m 那么新的xi=(B-1b)i+brair i=1, m 。由此可得，最优基不变的条件是Max -bi/airair0brMin-bi/airair0,3.灵敏度分析,46,最优单纯形表中含有3.灵敏度分析46,例3.5: 上例最优单纯形表如下,3.灵敏度分析,47,例3.5:3.灵敏度分析47,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用对偶单纯形法

24、进一步求解，可得：x* = ( 4, 3, 2, 0, 0 )T f* = 17,3.灵敏度分析,48,各列分别对应 b1、b2、b3 的单一变化3.灵敏度分析48,增加一个变量 增加变量 xn+1 则有相应的pn+1 ,cn+1 。 那么 计算出B-1pn+1 , n+1=cn+1-cri ari n+1 填入最优单纯形表, 若 n+1 0 则 最优解不变； 否则，进一步用单纯形法求解。,3.灵敏度分析,49,增加一个变量3.灵敏度分析49,例3.6:例3.4增加x6 , p6=( 2, 6, 3 )T, c6=5 计算得到,用单纯形法进一步求解，可得：x* = ( 1,1.5,0,0,0,

25、2 )T f* = 16.5,3.灵敏度分析,50,例3.6:用单纯形法进一步求解，可得：3.灵敏度分析50,增加一个约束 增加约束一个之后，应把最优解带入新的约束，若满足则最优解不变，否则填入最优单纯形表作为新的一行，引入一个新的非负变量（原约束若是小于等于形式可引入非负松弛变量，否则引入非负人工变量），并通过矩阵行变换把对应基变量的元素变为0，进一步用单纯形法或对偶单纯形法求解。,3.灵敏度分析,51,增加一个约束3.灵敏度分析51,例3.7:例3.4增加3x1+ 2x215，原最优解不满足这个约束。于是,3.灵敏度分析,经对偶单纯形法一步，可得最优解为（3.5, 2.25, 0, 0, 3, 2 )T，最优值为 13. 75,52,例3.7:3.灵敏度分析经对偶单纯形法一步，可得最优解为（3,A中元素发生变化(只讨论 N 中某一列变化情况） 与增加变量 xn+1 的情况类似，假设 pj 变化 。那么，重新计算出 B-1pj j = cj - cri ari j 填入最优单纯形表，若 j 0 则最 优解不变；否则，进一步用单纯形法求解。（例子从略）,3.灵敏度分析,53,A中元素发生变化(只讨论 N 中某一列3.灵敏度分析,