线性规划的对偶理论与灵敏度分析

1、1 第二章第二章 线性规划的线性规划的 对偶理论与及灵敏度分析对偶理论与及灵敏度分析 Dual Theory and Sensitivity Analysis内容重点：内容重点：线性规划对偶问题的概念、理论及经 济意义；对偶单纯形法；灵敏度分析。学习要求：学习要求：掌握线性规划对偶理论及其经济意义；运用对偶理论对线性规划最优解进行分析；运用对偶理论对管理问题进行经济分析。2第一节第一节 线性规划的对偶问题线性规划的对偶问题一、对偶问题的提出例1 某厂有A、B、C三种类型的设备，生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如表：设变量x

2、i为第i种（甲、乙）产品的生产件数（i1，2） max z =1500 x1+2500 x2 s.t. 3x1+2x2652x1+ x240 3x275 x1 ,x2 0 产品甲 产品乙设备能力（h）设备A3 32 26565设备B2 21 14040设备C0 03 37575利润（元/件）1500150025002500 3若工厂的设备都用于出租，工厂收取出租费。试问：设备 A、B、C 每工时各如何收费才最有竞争力？ 设 y1 ，y2 ，y3 分别为每工时设备 A、B、C 的出租费用。min w = 65y1+ 40y2 + 75y3s.t. 3y1+2y2 1500 （不少于甲产品的利润）

3、2y1+y2+3y3 2500 （不少于乙产品的利润）y1, y2 , y3 04max z = 1500 x1 + 2500 x2 s.t. 3x1 + 2x2 65 2x1 + x2 40 原问题原问题 3x2 75 x1 , x2 0 min w = 65y1+ 40y2 + 75y3 s.t. 3y1+2y2 1500 2y1+y2+3y3 2500 对偶问对偶问题题y1, y2 , y3 05二、对称形式下对偶问题的一般形式对偶问题的定义对称形式：互为对偶 (LP) max z = c x (DP) min w= bT y s.t. Ax b s.t. AT y cT x 0 y 0

4、 记号约定：c 为行向量。6 对称形式的对偶规划之间具有下面的对应关系：(1)若一个模型为目标求“极大”，约束为“小于等于”的不等式，则它的对偶模型为目标求“极小”，约束是“大于等于”的不等式。即“max，”和“min，”相对应。(2)从约束系数矩阵看：一个模型中为，则另一个模型中为AT。一个模型是m 个约束，n 个变量，则它的对偶模型为n 个约束，m 个变量。(3)从数据b、c 的位置看：在两个规划模型中，b 和 c 的位置对换。(4)两个规划模型中的变量皆非负。7原问题（对偶问题）原问题（对偶问题）对偶问题（原问题）对偶问题（原问题）max z = c xmin w= bT yn个变量n个

5、约束xj 0a1jy1+a2jy2+a2jym cjxj 0a1jy1+a2jy2+a2jym cjxj 无约束a1jy1+a2jy2+a2jym = cjm个约束m个变量ai1x1+ai2x2+ainxn biyi0ai1x1+ai2x2+ainxn biyi0ai1x1+ai2x2+ainxn = biyi无约束三、非对称形式的原-对偶问题关系8例例2 2 写出右边写出右边线性规划问题线性规划问题的对偶问题。的对偶问题。0,3 22252 min21321321321321xxxxxxxxxxxxxxz 0,12121 3225 max21321321321321yyyyyyyyyyyyy

6、yw原问题：原问题：对偶问题：对偶问题：变成目标函变成目标函数的系数数的系数系数变成约束系数变成约束条件右侧值条件右侧值变成第一个变成第一个约束条件的约束条件的系数系数反过来，由下反过来，由下往上也是一样往上也是一样的。的。9第二节第二节 对偶问题的基本性质对偶问题的基本性质一一、单纯形法的矩阵描述、单纯形法的矩阵描述(LP)Max z = j=1,2,n cj xjs.t. j=1,2,n aij xj bi , i=1,2,m xj 0, j=1,2,n(DP)Min w = i=1,2,m bi yis.t. i=1,2,m aij yi cj , j=1,2,n yi 0, i=1,2

7、,m10 max z = c x 标准化 max z= c x+0 xs s.t. Ax b s.t. A x + I xs = b x 0 x, xs 0原问题最优单纯形表关于对偶问题最优解的信息： (LP) max z = cx (DP) min w= bT ys.t. Ax b s.t. AT y cT x 0 y 0 11 cB cN 0 cB xB b xB xN xS 0 xS b B N I 检验数行 cB cN 0 cB cN 0 cB xB b xB xN xS cB xB B-1b I B-1N B-1 检验数行 0cN cBB-1N cBB-1 经过若干次迭代（标准化）原

8、问题的初始单纯形表12 ( cB, cN, 0) - cBB-1(B, N, I)=(0, cN - cBB-1N, -cBB-1) 0令 yT=cBB-1, 易看出 AT y cTy 0又因为w=bTy=cBB-1b=z,根据强对偶理论知cBB-1为对偶问题的最优解。而它就是最优单纯形表中对应于松弛变量的检验数（仅对对称形式成立）。当单纯形表为最优表时，检验数行为：13加松弛变量得标准形式： 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

9、例3 max z = 50 x1 + 100 x2 s.t. x1 + x2 300 2x1 + x2 400 x2 250 x1 , x2 014-cBB-1IB=(p1, p4, p2)B-1最优解 x1 = 50 x2 = 250 x4 = 50对偶最优解 y1 = 50 y2 = 0 y3 = 50, B-1对应的检验数 T = cBB-1 。15二二、对偶问题的基本性质、对偶问题的基本性质对偶定理对偶定理(原问题与对偶问题解的关系）弱对偶定理 若 x, y 分别为（LP) 和（DP）的可行解，那么 cx bTy。推论 若（LP）可行，那么（LP）无有限最优解的 充分必要条件是（DP）

10、无可行解。最优性定理 若x*, y*分别(LP)和(DP)的可行解,且c x* = bTy*，那么 x*, y* 分别为(LP)和(DP)的最优解。强对偶定理 若(LP)和(DP)均可行，那么(LP)和(DP)均有最优解,且最优值相等。16互补松弛原理在线性规划问题（原问题和对偶问题）的最优解中：（1）如果对应某一约束的对偶变量取值非零，则该约束取严格等式；（2）如果某一约束取严格不等式，则其对应的对偶变量必取零。以上定理、推论对任意形式线性规划的对偶均有效。若x*,y* 分别为（LP）和（DP）的最优解，那么， c x* = bT y* 。根据 z* = w* = bTy*=b1y1*+b2

11、y2*+bmym* 可知 z / bi = yi* yi* 表示 bi 变化1个单位对目标 w 产生的影响，称为 bi的影子价格。注意：注意：若 B 是最优基，y*T= cBB-1 为影子价格向量。第三节第三节 影子价格影子价格18max z = 2x1 + x2 s.t. 5x2 15 6x1 + 2x2 24 x1 + x2 5 x1 , x2 0 max z = 2x1 + x2 s.t. 5x2 15 6x1 + 2x2 25 x1 + x2 5 x1 , x2 0 b2：24 25 z* ： 8.5 8.75 z / b2 = 0.25影子价格的经济含义影子价格的经济含义（1）影子价

12、格是对现有资源实现最大效益时的一种估价。企业可以根据现有资源的影子价格，对资源的使用有两种考虑： 第一，若租费高于某设备的影子价格，可考虑出租该设备；否则不宜出租。 第二，若市价低于某设备的影子价格，可考虑买进该设备，扩大生产；否则不宜买进。（2）影子价格表明资源增加对总效益产生的影响。影子价格反映了不同的局部或个体的增量可以获得不同的整体经济效益。如果为了扩大生产能力，考虑增加设备，就应该从影子价格高的设备入手。这样可以用较少的局部努力，获得较大的整体效益。（3）一种资源的影子价格，是指在其它条件都不变时，该种资源增加一个单位所产生的总利润增加量。当约束条件、产品利润等发生变化时，有可能使影

13、子价格发生变化。（4）影子价格的经济含义，是指资源在一定范围内增加时的情况，当某种资源的增加超过了这个“一定的范围”时，总利润的增加量则不是按照影子价格给出的数值线性地增加。一、对偶单纯形法的基本思路应用前提：有一个基，其对应的基满足: 单纯形表的检验数行全部非正（对偶可行）； 变量取值可有负数（非可行解）。 注：通过矩阵行变换运算，使所有相应变量取值均为非负数即得到最优单纯形表。第四节第四节 对偶单纯形法对偶单纯形法1.建立初始对偶单纯形表,对应一个基本解,所有检验数均非正,转步骤2；2.若b0,则得到最优解,停止;否则,若有bk0则选k行的基变量为出基变量,转步骤33.若所有akj0( j

14、 = 1,2,n )，则原问题无可行解,停止;否则,若有akj0 则选 =minj / akjakj0=r/akr那么 xr为进基变量,转步骤4；4.以akr为旋转元,作矩阵行变换使其变为1,该列其他元变为0,转步骤2。二二、对偶单纯形法的计算步骤对偶单纯形法的计算步骤例4 求解线性规划问题：求解线性规划问题： 标准化：标准化： max z = - 2x1 - 3x2 - 4x3 s.t. -x1- 2x2- x3+x4 = -3 -2x1+ x2-3x3+ x5= -4 x1,x2,x3,x4,x5 0min w = 2x1 + 3x2 + 4x3 s.t. x1 + 2x2 + x3 3

15、2x1 - x2 + x3 4 x1 , x2 , x3 0 表格对偶单纯形法是是是是否否否否所有所有得到最优解计算计算原规划的基解是可行的对偶问题的基解是可行的所有所有计算计算以旋转元素进行迭代以旋转元素进行迭代停无界解无可行解单纯形法对偶单纯形法0j0ib0maxjjk0miniiebbb0ika0ljaekeikikiabaab0minekkejejiaaa0min25例5 已知单纯形表：表中 a1 , a2 , a3 , b , 1 , 2 取值在什么范围可使：1、现可行解最优，且唯一（b0， 1 0, 2 0），何时不唯一（b0， 1 0, 2 0， 12 =0 ）；2、现基本解不可

16、行（b0）；3、问题无可行解（ b0， a10 , a2 0 ）；4、无有限最优解（ 2 0， a1 0， b0）；5、现基本解可行，由 x1 取代 x6 目标函数可改善 （ a30 , b0 , 10，a3 b12 ）。 CiCBXBbx1x2x3x4x5x6 x3b4a110a20 x42-1-501-10 x63a3-300-411200-30问题问题1 1：c ci , b bi，aij发生变化，问题的最优解变化如何？或者这些参数在多大的变化范围内，最优解仍然不变？问题2：增加或减少一个约束或变量，最优解如何变化？通过单纯形法计算可以得到最优基 B B 的逆矩阵 B B-1 ，B B-

17、1b b 以及 B B-1N N，检验数 j 等。第五节 灵敏度分析考虑标准化线性规划问题：考虑标准化线性规划问题：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 01. 若ck是非基变量的系数： 设ck变化为 ck + ck k= ck + ck -ci aik = k+ ck 只要 k 0 ,即 ck - k ，则最优解不变， 否则，将最优单纯形表中的检验数 k 用

18、k取 代，继续单纯形法的表格计算。例6 max z = -2x1 - 3x2 - 4x3 s.t. -x1 - 2x2 - x3 + x4 = - 3 -2x1 + x2- 3x3 + x5 = - 4 x1, x2, x3, x4, x5 0最优单纯形表 从3= c3+c3-(c2a13+c1a23 ) ，可得c3 9/5 时，原最优解不变。2. 若若 cs 是基变量的系数：是基变量的系数： 设 cs 变化为 cs + cs ，那么 j= cj -ci aij - ( cs + cs ) asj = j - cs asj ， i s 对所有非基变量，只要检验数 j 0 ， 即 j cs as

19、j ，则最优解不变； 否则，将最优单纯形表中的检验数 j 用 j取 代，继续单纯形法的表格计算。例7 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 易得：当 -3c21时，原最优解不变。 3.右端项右端项b b 发生变化发生变化 设分量br 变化为br+br ，最优解的基变量 xB = B B-1b 那么只要保持 B B-1(b + b) = B B-1b + B B-1b 0 则最优基不变，即基变量保持，只有值的变化；否则， 需要利用对偶单纯形法继续计算。 例8 例7 最优单纯形表如下 0 0.25 0 这里 B-1 = -2 0.5 1 0.5 -0.125 0 各列分别对应 b1、b2、b3 的单一变化因此，设 b1 增加 4，则 x1 ,x5