new对偶理论与灵敏度分析.ppt

Chapter 2对偶理论与灵敏度分析,上海工程技术大学管理学院,Chapter 2 灵敏度分析,对偶问题提出 问题一：某公司在计划期内要安排生产I、 II两种产品，已知生产单位产品所需的设备台时及A B两种原材料的消耗如表所示，该工厂每生产一件产品I可获利2元，每生产一件产品II可获利3元，问应该如何安排计划使该工厂获利最多？ 如何安排方案？,举例,有哪些 方面可以考虑呢？,Chapter 2 灵敏度分析,先根据图表来列出模型 Max Z= 2X1+3X2 X1+2X2 8 4X1 16 4X2 12 X1, X2 0,举例,我们从另一个角度来讨论这个问题.假如该工厂的决策者决定不生产产品I II，而将其所有资源出租或外售.这时工厂的决策者就要考虑给每种资源如何定价的问题.设用Y1, Y2, Y3分别表示出租单位设备台时的租金和出让单位原材料A,B的附加额.,从工厂决策者的角度来看f当然是越大越好,但从接受者眼光来说f是越少越好,所以工厂决策者只可以在满足 所有产品的利润条件下,使其总收入尽可能的小.因此可以列出如下线性规划问题 min f= 8Y1+16Y2+12Y3 Y1+4Y2 2 2Y1+4Y3 3 Yi 0, i = 1,2,3,Chapter 2 灵敏度分析,各模型中有关数据的“位置”示意图如下。,由上面的例子我们可以知道原问题与对偶问题的关系 1线性规划问题是对称形式 Max z = CX Min f = Yb s.t. Ax b s.t. YA c x 0 y 0 “Max - ” “Min- ”,Chapter 2 灵敏度分析,如上面例题所示一对对称形式的对偶规划之间具有下面的对应关系 (1)若一个模型为目标求“极大”，约束为“小于等于”的不等式，则它的对偶模型为目标求“极小”，约束是“大于等于”的不等式。即“max，”和“min，”相对应。,(2)从约束系数矩阵看：一个模型中为，则另一个模型中为AT。一个模型是m个约束，n个变量，则它的对偶模型为n个约束，m个变量。 (3)从数据b、C的位置看：在两个规划模型中，b和C的位置对换。 (4)两个规划模型中的变量皆非负。,Chapter 2 灵敏度分析,然而在一般线性规划问题中遇到非对称形式时我们的处理如下： 非对称形式的对偶规划一般称不具有对称形式的一对线性规划为非对称形式的对偶规划。 对于非对称形式的规划，可以按照下面的对应关系直接给出其对偶规划。 （1）将模型统一为“max，”或“min，” 的形式，对于其中的等式约束按下面（2）、（3）中的方法处理；,（2）若原规划的某个约束条件为等式约束，则在对偶规划中与此约束对应的那个变量取值没有非负限制； （3）若原规划的某个变量的值没有非负限制，则在对偶问题中与此变量对应的那个约束为等式。,Chapter 2 灵敏度分析,非对称型对偶问题,Chapter 2 灵敏度分析,举例,Chapter 2 灵敏度分析,Chapter 2 灵敏度分析,小练习,写出下列问题的对偶问题,Chapter 2 灵敏度分析,对偶问题的基本性质 性质1:对称性规范原始，对偶问题的对偶是原问题。 Max z = CX Min f = Yb s.t. AX b s.t. YA C X 0 Y 0 “Max - ” “Min- ”,Chapter 2 灵敏度分析,性质2:弱对偶原理（弱对偶性）：设 和 分别是 问题（P）和（D）的可行解，则必有,性质3:无界性 若原问题（对偶问题）的解为无界解，则其对偶问题（原问题）无可行解。（无界性）,性质4:可行解是最优解的性质： 若 X* 和 Y* 分别是 P 和 D 的可行解且 CX* = Y* b， 则X*. Y*分别是问题 P和D 的最优解。,Chapter 2 灵敏度分析,性质5:对偶定理 若原问题有最优解，那么对偶问题也有最优解，而且二者最优值相等。（强对偶性）,性质6:互补松弛定理 设X*和Y*分别是问题 P 和 D 的可行解，则它们分别是最优解的充要条件是,同时成立,Chapter 2 灵敏度分析,例题判断下例说法是否正确，为什么？ A 如果线性规划的原问题存在可行解，则其对偶 问题也一定存在可行解 B 如果线性规划的对偶问题无可行解，则原问题也一定无可行解。 C 在互为对偶的一对原问题和对偶问题中，不管原问题是求极大或者极小，原问题可行解的目标函数值都一定不超过其对偶问题可行解的目标函数值。,Chapter 2 灵敏度分析,解： A不对。因为原问题为无界解时（它当然有可行解），其对偶问题无可行解。 B此句为A的逆否命题，所以也不对。 C不对。因为哪个问题是原问题，哪个问题是对偶问题是相对而言的。,Chapter 2 灵敏度分析,例题:已知原问题的最优解为X* =（0,0,4），Z=12,试求对偶问题的最优解。,Chapter 2 灵敏度分析,解:,将X* =（0 , 0 , 4）代入原问题中，有下式：,Chapter 2 灵敏度分析,所以，根据互补松弛条件，必有y*1= y*2=0，代入对偶问题 （3）式， y3 =3。因此，对偶问题的最优解为 Y*=（0 . 0 . 3），W=12。,第二节 影子价格,Chapter 2 灵敏度分析,第三节 对偶单纯形法 对偶单纯形法是求解线性规划的另一的基本方法。它是根据对偶原理和单纯形法的原理而设计出来的，因此称为对偶单纯形法。对偶单纯形法并不是求解对偶问题解的方法，而是利用对偶理论求解原问题的解的方法。 由单纯形方法，我们可以得到，LP问题的最优解应该是可行的； 最优的；由对偶性可知， LP问题的最优性相当于DLP的可行性， LP问题的可行性相当于DLP的最优性.,(3) 对偶单纯形法,因此单纯形方法可以解释为它是在保持一个原始问题可行解的前提下，向对偶可行解的方向迭代.,原始算法,我们可以从一个对偶可行解开始，保持对偶问题的可行性，向原始可行解的方向迭代,对偶单纯形法,对偶单纯形法的基本思路,单纯形法的基本思路： 原问题基可行解 最优解判断,对偶问题的可行解,对偶问题 最优解判断,对偶单纯形法 基本思路,也就是说，求解原问题（P）时，可以从（P）的一个基本解（非基可行解）开始，逐步迭代，使目标函数值（Z=Y b= CB B-1b =CX）减少，当迭代到 XB=B-1b0时，即找到了（P）的最优解，这就是对偶单纯形法。,同原始单纯形求法一样，求解对偶问题（D），也可以从（D）的一个基本可行解开始，从一个基本可行解（迭代）到另一个基本可行解，使目标函数值减少。,4 对偶单纯形法,对偶单纯形法的基本思路是：,在迭代过程中，始终保持对偶问题解的可行性， 而原问题的解由不可行逐渐向可行性转化，一旦原 问题的解也满足了可行性条件,也就达到了最优解。 也即在保持正则解的正则性不变条件下，在迭代 过程中，使原问题解的不可行性逐步消失，一旦迭 代到可行解时，即达到了最优解。,这样的优点在于， 一是当问题的模型中存在“=”的约束条件时，不需要引入人工变量，只要在约束条件方程的两边乘以“-1”后加入松弛变量，再按单纯形法求解。 二是当约束条件方程个数m大于变量个数n的时候，将原问题变换成对偶问题求解，计算量一般会小些。,Chapter 2 灵敏度分析,对偶单纯形法求解线性规划问题过程： 1.建立初始对偶单纯形表,对应一个基本解,所有检验数均非正 ,转2； 2.若b0,则得到最优解,停止; 3.若有bi0, 换出变量：设minbi|bi0=bk,，则选k行的基变量为换出变量,转4,4.若所有akj0( j = 1,2,n )，则原问题无可行解,停止;否则,若有akj0 则选 =minj / akjakj0=r/akr那么xr为换入变量,转4； 5.以akr为主元素,作矩阵行变换使其变为1,该列其他元素变为0,转2。,例一、用对偶单纯形法求解：,解：将模型转化为,所以， X*=（2 . 2 . 2 . 0 . 0 . 0）， Z* =72， 原问题 Z* =72 其对偶问题的最优解为： Y*= (1/3 . 3 . 7/3)，W*= 72,4 对偶单纯形法,对偶单纯形法与原始单纯形法内在的对应关系,练习：,对偶单纯形法的优点： 不需要人工变量； 当变量多于约束时，用对偶单纯形法可减少迭代次数； 在灵敏度分析中，有时需要用对偶单纯形法处理简化。 对偶单纯形法缺点： 在初始单纯形表中对偶问题是基可行解，这点对多数线性规划问题很难做到。 因此，对偶单纯形法一般不单独使用。,用对偶单纯形法求解线性规划问题：,解：先将问题改写为：,Chapter 2 灵敏度分析,例题:用对偶单纯形法求解,Chapter 2 灵敏度分析,解:将上述模型转化为,Chapter 2 灵敏度分析,Chapter 2 灵敏度分析,Chapter 2 灵敏度分析,Chapter 2 灵敏度分析,Chapter 2 灵敏度分析,所以， X*=（0，3/2，1/8， 0 . 0 . 0） Z* =1400， 原问题 Z* =1400 其对偶问题的最优解为： Y*= (400，200)，W*= 1400,58,一个标准形式的线性规划问题可由约束矩阵，右端项向量b，和价值向量完全确定，假如一个线性规划问题对于给定的数据集合，b，有最优解，则最优解。最优目标函数值，其中为最优基。,第四节 灵敏度分析,但是线性规划问题所对应的数据集合，b，常常是通过预测或估计所得到的统计数据，在实际使用中，不免会有一定的误差。而且随着市场环境，工艺条件和资源数量的改变，这些数据完全可能发生变化。因此有必要来分析一下当这些数据发生波动时，对目前的最优解，最优值或者最优基会产生什么影响，这就是所谓的灵敏度分析。,Chapter 2 灵敏度分析,灵敏度分析的步骤可以归纳如下： 1) 将参数的改变计算反映到最终单纯形表上来; 具体的计算方法是，按照相关公式计算出由参数的变化而引起的最终单纯形表上有关数字的变化； 2) 检查原问题是否仍为可行解; 3) 检查对偶问题是否仍为可行解; 4) 我们可以按照书中表中罗列的几种情况得出结论和决定继续计算的步骤,总之,1)资源数量发生变化的分析(右端项向量b的改变) 当右端项向量b由时，改变的只是表中右端常数列。此时基变量，目标函数值。 而检验行的检验向量保持不变。 右端项向量b的波动会使最优解和最优目标函数值发生变化，但原最优解的检验向量仍能保持非正。为了使B可行，只要 或,若 ，因为检验向量仍保持非正，因此可用对偶单纯形法再次进行迭代，直到求得新最优解。 右端列向量b变化时，最优解 和最优值 一定改变。因此我们主要讨论右端列向量b变化时， 最优基是否改变.,Chapter 2 灵敏度分析,最优单纯形表中含有 B-1=( aij ）i=1,m; j=n+1,n+m 那么 新的xi=(B-1b)i+brair i=1, m 。 由此可得，最优基不变的条件是 Max -bi/airair0brMin-bi/airair0,Chapter 2 灵敏度分析,例题: 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,Chapter 2 灵敏度分析,最终单纯形表为:,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* = 17,Chapter 2 灵敏度分析,2)价值系数cj的变化分析 m 考虑检验数 j = cj - cri arij j =1,2,n i = 1 若ck是非基变量的系数： 设ck变化为 ck + ck k= ck + ck -cri arik = k+ ck 只要 k 0 ,即 ck - k ，则 最优解不变；否则，将最优单纯形表 中的检验数 k 用 k取代，继续单 纯形法的表格计算。,Chapter 2 灵敏度分析,例题: Max z = -2x1 - 3x2 - 4x3 S.t. -x1-2x2-x3+x4 = - 3 -2x1+x2-3x3+x5 = - 4 x1 ,x2 ,x3 ,x4 ,x5 0,Chapter 2 灵敏度分析,最优单纯形表:,从表中可得到c3 9/5 时，原最优解不变。,Chapter 2 灵敏度分析,若 cs 是基变量的系数： 设 cs 变化为 cs + cs ，那么 对所有非基变量，只要对所有非基变量 j 0 ，即 j cs asj ，则最优解 不变；否则，将最优单纯形表中的检验数 j 用 j取代，继续单纯形法的表格计算。 Maxj/asjasj0csMinj/asjasj0,Chapter 2 灵敏度分析,例题: 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,下表为最优单纯形表,考虑基变量系数c2发生变化,Chapter 2 灵敏度分析,从表中可得到 -3c21时，原最优解不变。,例：某企业利用三种资源生产两种产品的最优计划问题归结为下列线性规划,已知最优表如下。 （1）确定x2的系数c2的变化范围，使原最优解保持最优； （2）若c2=6，求新的最优计划。,一、 价值系数cj的变化分析,4 = c25 0 5 = 52c2 0 5/2 c2 5,最优解X*=（35，10，25，0，0）保持不变。,（1）,x1*=45/2，x2*=45/2，x4*=25/2，x3*= x5*=0，z*=495/2,（2）,XB= B1b,例：对于上例中的线性规划作下列分析： （1）b3在什么范围内变化，原最优基不变？ （2）若b3=55，求出新的最优解。,二、右端常数bi的变化分析,解得40b350，即当b340，50 时，最优基B 不变,（2）当 b3= 55 时,=,Shanghai University of Engineering Science,Thank You !,