运筹学第2章-线性规划的对偶理论

1、7/25/2022第2章 线性规划的对偶理论1目录7/25/20222.1 线性规划的对偶问题2.2 对偶理论2.3 影子价格2.4 对偶单纯形法2.5 灵敏度分析 CONTENTS22.1 线性规划的对偶问题在第1章的例1.1中，我们讨论了如下的生产计划模型：假定现有一公司想把该工厂的生产资源收购过来，那么它至少应付出多大的代价，才能使该工厂愿意放弃生产活动，出让自己的资源？现在从另一个角度来讨论这个问题：7/25/20222.1.1 对偶问题的提出例1.1 生产计划问题问产品A, B各生产多少, 可获最大利润? A B 备用资源 钢材（吨） 1 2 30 劳动力（工时） 3 2 60特种设

2、备（台时） 0 2 24 利润（元/件） 40 504设用 y1, y2, y3 分别表示钢材、劳动力和特种设备这三种资源的单位定价。因为用1个单位的钢材和3个单位的劳动力可以生产一件产品A，从而获得40元利润。那么生产每件产品A的资源出让所得应不低于生产一件产品A的利润，即y1 + 3y2 40同理，将可以生产每件产品B的资源出让的所得应不低于生产一件产品B的利润，即2y1 + 2y2 + 2y3 507/25/20222.1.1 对偶问题的提出5要把所有的资源都收购需付出：W = 30y1 + 60y2 + 24y3当然收购公司希望用最小的代价把工厂的全部资源收买过来，故有：min W =

3、 30y1 + 60y2 + 24y3s.t. y1 + 3y2 40 2y1 + 2y2 + 2y3 50 y1 , y2 , y3 0对偶问题(DUAL)7/25/20222.1.1 对偶问题的提出6问最经济的配食方案是什么？维生素的销售商换个角度例1.2 混合配料问题 饲料 A B C 每单位成本 饲料1 4 1 0 2 饲料2 6 1 2 5 饲料3 1 7 1 6 饲料4 2 5 3 8 每天维生素 12 14 8 的最低需求维生素/mg2.1.1 对偶问题的提出7/25/20227“对称型”对偶问题 min w=bTyATy c y0A 矩阵y, b 列向量c 列向量max z=c

4、Tx Ax b x0A 矩阵x, b 列向量c 列向量原问题7/25/20222.1.2 线性规划原问题与对偶问题的表达形式87/25/2022原始问题max z=cTxs.t. Ax b x 0对偶问题min w=bTys.t. ATy c y 0maxbAcTmncATbTminmn2.1.2 线性规划原问题与对偶问题的表达形式9min z=-cTxs.t. -Ax -b x 0max w=-bTys.t. -ATy -cy 0min w=bTys.t. ATy c y 0max z=cTxs.t. Ax b x 0对偶的定义对偶的定义对偶问题的对偶就是原始问题！7/25/20222.1.

5、2 线性规划原问题与对偶问题的表达形式10“非对称型”2.1.2 线性规划原问题与对偶问题的表达形式2.1.2 线性规划原问题与对偶问题的表达形式012对偶关系对应表 （P） （D）目标函数maxmin目标系数Cb约束右端bC系数矩阵AAT函数约束与变量约束第k个约束 第k个变量约束个数=变量个数（非）规范约束 非负（正）变量等式约束 自由变量7/25/20222.1.2 线性规划原问题与对偶问题的表达形式13例2.1 写出对偶规划：min z= 4x1 +2x2 3x3 x1+2x2 62x1 +3x3 9 x1 +5x2 2x3 = 4x1自由, x2 0, x3 0 y1+2y2 + y

6、3 = 42y1 +5y3 2 3y2 2y3 3y1 0 , y2 0 , y3自由max w= 6y1 +9y2 +4y3 7/25/20222.1.2 线性规划原问题与对偶问题的表达形式142.2 对偶理论证明： 7/25/20222.2.1 弱对偶性16由弱对偶性，可得出以下的推论： 原问题有可行解且目标函数值无界，则其对偶问题无可行解；反之，对偶问题有可行解且目标函数值无界，则其原问题无可行解。（注意：逆命题不成立） 若原问题有可行解而对偶问题无可行解，则原问题目标函数值无界；反之，对偶问题有可行解而原问题无可行解，则对偶问题的目标函数值无界。7/25/20222.2.1 弱对偶性1

7、7证明： 再由弱对偶性：7/25/20222.2.2 最优性18若原问题与其对偶问题均具有可行解，则两者均具有最优解，且它们的最优解的目标函数值相等。证明：由于两者均有可行解，根据弱对偶性推论，原问题的目标函数值具有上界，对偶问题的目标函数值具有下界。因此，两者均具有最优解。由前面的讨论知，当原问题为最优解，即 B 为最优基时，YT = CBB-1 是其对偶问题的可行解，且两者目标函数值相等。由最优性条件，得此 Y 即为最优解。7/25/20222.2.3 强对偶性（对偶定理）19在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，则该约束条件条件取严格等式；反之，如果约束条件取

8、严格不等式，则其对应的对偶变量为零。原问题：max z=cTx Ax + xs =b x, xs 0 x =x1xnxs=xs1xsm7/25/20222.2.4 互补松弛性（松紧定理）20证明：7/25/20222.2.4 互补松弛性（松紧定理）217/25/20222.2.4 互补松弛性的应用例2.2 已知线性规划问题min z = 2x1+ 3x2 + 5x3 + 2x4 + 3x5 x1+ x2 + 2x3 + x4 +3x5 4 2x1- x2 + 3x3 + x4 + x5 3 x1, x2 , x3 , x4 , x5 0其对偶问题的最优解为 y1=4/5, y2=3/5，试应用

9、对偶理论求原问题的解。222.2.4 互补松弛性的应用将 y1=4/5, y2 =3/5的值代入，得知 为严格不等式，于是由互补松驰性，必有 x2= x3 = x4=0 解：写出对偶问题：Max S = 4y1+ 3y2 y1+ 2y2 2 y1- y2 3 2y1+ 3y2 5 y1+ y2 2 3y1+ y2 3 y1, y2 0又因 y1, y2 0，故原问题的两个约束条件必为紧约束，即有 x1+ 3x5 =4 2x1+ x5 =3 解得 x1=x5 =1 即 X*=(1,0,0,0,1)T, Z*=50237/25/20222.2.5 对偶问题解与原问题解的关系则原问题单纯形表的检验数

10、行对应其对偶问题的一个可行解设原问题：max z = cTxs.t. Ax+xs=b x, xs0其对偶问题： min w = bTy s.t. ATy- ys=c y, ys0 ys1 是对应原问题中基变量 XB 的剩余变量 ys2 是对应原问题中非基变量XN 的剩余变量XBXNXs0CN -CBB-1N-CBB-1-ys1-ys2-y松弛变量剩余变量检验数24项 目非基变量XB XN基变量Xs0 Xs bB NIcj - zjCB CN 0项 目基变量XB非基变量 XN XsCB XB B-1 bIB-1N B-1cj - zj0CN -CB B-1N -CB B-1初始单纯形表：当迭代后

11、基变量为 XB 时：当 B 为最优基时： 0 0CB CBB-1B= 02.2.5 对偶问题解与原问题解的关系025CB CBB-1B = 0CN -CB B-1N 0C - CB B-1A 0-CB B-1 0ATy C y 0令 yT = CBB-1由此可见，y 是对偶问题的一个可行解。将这个解代入对偶问题的目标函数，有w = bTy = yTb = CBB-1b = CBXB = z即当原问题为最优解时，这时对偶问题为可行解，且两者具有相同的目标函数值。7/25/20222.2.5 对偶问题解与原问题解的关系26产品A，B产量x1，x2，Z为利润3x1 +x2 +x3=483x1 +4x

12、2 +x4=120 x1 x40Max Z= 5x1 +6x2 3x1 +x2 483x1 +4x2 120 x1 , x2 0机器台时劳动工时7/25/20222.2.5 对偶问题解与原问题解的关系例：27X=(8,24)T Z =184 5 6 0 0 XB b x1 x2 x3 x40 x3 48 3 1 1 00 x4 120 3 (4) 0 1 0 5 6 0 00 x3 18 (9/4) 0 1 -1/46 x2 30 3/4 1 0 1/4 180 1/2 0 0 -3/25 x1 8 1 0 4/9 -1/96 x2 24 0 1 -1/3 1/3 184 0 0 -2/9 -

13、13/9B-1B0282.2.5 对偶问题解与原问题解的关系3y1+3y2 5 y1 +4y2 6 y1 , y2 0Min W=48y1+120y23y1+3y2 -y3+y5 =5 y1 +4y2 -y4+y6= 6Min W=48y1+120y2 +My5 +My6Max Z= 5x1 +6x2 3x1 +x2 483x1 +4x2 120 x1 , x2 0机器台时劳动工时对偶问题？0292.2.5 对偶问题解与原问题解的关系 48 120 0 0 M M yB y1 y2 y3 y4 y5 y6M y5 5 3 3 -1 0 1 0 M y6 6 1 4 0 -1 0 1 11M 4

14、8-4M 120-7M M M 0 0M y5 1/2 9/4 0 -1 3/4 1 -3/4120 y2 3/2 1/4 1 0 -1/4 0 1/4 180+1/2M 18-9/4M 0 M 30-3/4M 0 -30+7/4M48 y1 2/9 1 0 -4/9 1/3 4/9 -1/3120 y2 13/9 0 1 1/9 -1/3 -1/9 1/3y=(2/9,13/9), Z=184 184 0 0 8 24 M-8 M-240302.2.5 对偶问题解与原问题解的关系2.3 影子价格z= CBB-1b + (CN - CBB-1 N)XN ()z= z(b) b为资源数对()求偏

15、导： z b=CBB-1=YT对偶解Y b 的单位改变量所引起的目标函数值的改变量。7/25/20222.3.1 对偶解的经济意义32w = ( y1 ym )b1bm= b1 y1 + b2 y2 + + bm ymbi ：第 i 种资源的数量； yi ：对偶解；yi ：反映bi 的边际效益(边际成本)当 bi 增加 bi ,其它资源数量不变时,目标函数的增量Z =bi yi7/25/20222.3.1 对偶解的经济意义33由前面的经济解释可知，yi 的大小与系统内资源对目标的贡献有关，是资源的一种估价，称为影子价格。(Shadow Price)注：这种估价不是资源的市场价格。市场价格是已知

16、数，相对较稳定；而影子价格则有赖于资源的利用情况，是未知数。当企业的生产任务、产品结构等等发生变化时，资源的影子价格也会随之改变，它是一种动态价格。7/25/20222.3.2 影子价格34即某资源对偶解0，该资源有利可图，可增加此种资源量；某资源对偶解为0，则不增加此种资源量。 影子价格的大小客观地反映了资源在系统内的稀缺程度根据互补松弛定理的条件，如果某一资源在系统内供大于求，其影子价格就为零。即增加该资源的供应不会引起系统目标的任何变化。如果某一资源是稀缺资源（即相应约束条件的剩余变量为零），则影子价格必然大于零。影子价格越高，资源在系统中越稀缺。7/25/20222.3.2 影子价格的

17、应用35即直接用影子价格与市场价格相比较，进行决策，是否买入该资源。 影子价格实际上是一种机会成本在完全市场经济条件下，当某种资源的市场价格低于影子价格时，企业应买进该资源用于扩大再生产；而当某种资源的市场价格高于影子价格时，企业应卖掉已有资源。随着资源的买进卖出，其影子价格也将发生变化，一直到影子价格与市场价格保持同等水平时，才处于平衡。7/25/20222.3.2 影子价格的应用362.4 对偶单纯形法单纯形法的基本思路：找基 B，满足 B-1b 0，但 C - CBB-1 A（即检验数）不全 0。迭代保持 B-1b 0，使 C -CBB-1 A 0，即 CBB-1 A C对偶单纯形法的基

18、本思路：迭代保持 C -CBB-1 A 0，使 B-1b 0找基 B，满足 C - CBB-1 A 0，但 B-1b 不全 0。对偶问题的可行基7/25/20222.4.1 基本思路38(1) 作初始表，要求全部 cj - zj 0(2) 判定：B-1 b 全 0，停。否则，取其对应变量 xr 为换出基的变量。(3) 确定换入变量 若第 r 行的 arj 全 0 ，停，原问题无可行解。7/25/20222.4.2 计算步骤39 若第 r 行的 arj 有 arj 0 , 则求其对应变量 xs 为换入基的变量(3) 确定换入变量(4) 以 ars 为主元，换基迭代，得到新的单纯形表重复1-4的步

19、骤，直到找到最优解7/25/20222.4.2 计算步骤40关于的解释：第 r 个方程即0某 xj 从 0，xr不能变 007/25/20222.4.2 计算步骤步骤(3)的两个注释41关于的解释：下一个表中的检验数为为保持可行，必须(a) 对 arj 0, 因 cj zj 0 (b) 对 arj 0，需用单纯形法继续迭代求解。7/25/20222.5.2 价值系数cj的灵敏度分析 8 -4/3 -5/3 2/351为使表中的解仍为最优解，应有C2在什么范围变化的时候，最优解不变？2.5.2 价值系数cj的灵敏度分析052右端项 bi 的变化在实际问题中为可用资源数量的变化。bi 的变化反映到

20、最终单纯形表上将引起 b 列数字的变化，可能有下面两种情况：问题的最优基不变，变化后的 b 列值为最优解； （即生产产品的品种不变，但数量及最优值会变化）原问题不可行但对偶问题可行，用对偶单纯形继续迭代求最优解。B-1bB-1A-CB B-1bC -CB B-1A7/25/20222.5.3 资源系数bi的灵敏度分析5315-3初始表最终表75B-1b2.5.3 资源系数bi的灵敏度分析054B-1对偶单纯形2.5.3 资源系数bi的灵敏度分析15-3初始表最终表B-1B-1b若最优基不变，那么b2的变化范围是多少？2.5.3 资源系数bi的灵敏度分析056增加一个变量 xj 在实际问题中反映为增加一种新的产品。技术系数矩阵多增加一列 Pj检验数多增加一个 j最终单纯形表中它们的值如何得到？原最优解不变按单纯形法继续迭代计算找出最优解7/25/20222.5.4 增加一个决策变量xj的灵敏度分析57 2.5 x6 3 2 2.5若工厂计划推出一种新