第三章 线性规划的对偶理论

1、第 三 章 对 偶 理 论 (Duality Theory) 线性规划对偶问题的提出 线性规划的矩阵表示 对偶问题的性质 对 偶 单 纯 形 法 灵 敏 度 分 析 应用实例 2.对偶问题： Max z = 30 x1 + 25x2 s.t. 2x1 + 4x2 40 3x1 + 2x2 30 x1 ,x2 0 A：x1公斤； B：x2 公斤。 若第二章例1中制药厂的设备都用 于外协加工，即该厂的决策者不是 考虑自己生产甲、乙两种产品，而 是将厂里的现有资源用于接受外来 加工任务，工厂只收取加工费。试 问：设备甲、乙每工时各应如何收 费才最有竞争力？ 下面从另一个角度来讨论这个问题： 分析问题

2、： 1.每种资源收回的费用不能低于自己生产时的可获利润； 2.定价又不能太高，要使对方能够接受。 每一个线性规划（ LP ）必然有与之相伴而生的另一个线性规划问题，其中的一个问 题叫“原问题”，记为“LP”，另一个称为“对偶问题”，记为“DP”。 对称形式： 互为对偶 (LP) Max = (DP) Min = T s.t. s.t. T 0 0 “Max - ” “Min- ” (2)从约束系数矩阵看：一个模型中为， 则另一个模型中为AT。一个模型是m个约束， n个变量，则它的对偶模型为n个约束，m个 变量。 (3)从数据b、C的位置看：在两个规划模型 中，b和C的位置对换。 (4)两个规划

3、模型中的变量皆非负。 1 对偶规划问题 P. 44 任一L.P.问题，都有一个与之密切相关的L.P.问题， 叫对偶问题。 给定一个L.P.问题，如何引出其对 偶问题？见P.52 . 表 31。 x1 x2 . xn 原关系 Min y1 a 11 a 12 . a 1n b1 y2 a 21 a 22 . a 2n b2 . . . . . . . . . . ym a m1 a m2 . a mn bm 对偶关系 . (X0,Y0,) Max Z c1 c2 . cn 横向组合得原问题： Max Z= c1 x1 + c2 x2 + . + cn xn a 11 x1 + a 12x2 +

4、. + a 1n xnb1 a 21 x1 + a 22x2 + . + a 2n xnb2 . . . . . . . a m1 x1 + a m2x2 + . + a mn xnbm X 0 纵向组合得对偶问题： Min = b1y1 +b2y2 + . +bmym a 11 y1 + a 21 y2 + . + a m1 ym c1 a 12 y1 + a 22 y2 + . + a m2 ym c2 . . . . . . . . a 1n y1 + a 2n y2 + . + a mn ym cn Y 0 若写成矩阵形式，可得： 原问题： 对偶问题： Max Z=CX Min =bT

5、Y AX b AT Y CT X 0 Y 0 注意：其中C是行向量，X、Y与b是 列向量，Amn为aij所构成的矩阵。 2 3 4 1 其矩阵形式为： 对偶（原）问题为 : 以下举例说明对偶问题的作法，见 P.52 例 2 原（对偶）问题： Min Z=2x1+5x2 y1 x1 4 y2 x2 3 y3 x1+2x2 8 x1 , x2 0 x1 x2 1 0 1 0 1 2 y1 y2 y3 对偶（原）问题为： MaxW=4y1 +3 y2 +8y3 y1 +y3 2 x1 y2 +2y3 5 x2 y10,y20,y30 2 5 1 0 0 1 1 2 4 3 8 x1 x2 y1 y2

6、 y3 Xo Yo Max W=(4 , 3 , 8 ) 原（对偶）问题： Min Z=(2,5) ： 1. 0, 564 3 7 3 2 532 . . 432max 321 321 321 321 321 xxx xxx xxx xxx ts xxxZ 2. Min w = 12y1+ 8y2+ 16y2+ 12y2 s.t. 2y1+ y2+ 4y3 2 2y1+2y2+ 4y4 3 y1, y2 , y3 , y4 0 解：2.首先将原式变形 0, 5 64 3 7 3 2532 432max 321 321 321 32 321 xxx xxx xxx xxx xxxZ 0, 467

7、5 343 232 532min 321 321 321 321 321 yyy yyy yyy yyy yyyW 对偶问题： 解：1. 例如：对约束条件是等式的LP问题 max z=CX s.t. AX=b X0 AX=b AX=b AXb -AX-b 所以，原问题可化为 max z=CX s.t. AXb -AX-b X0 A b X -A -b 解： 首先将原问题化 成 对称形式，令 x2=x3-x4, x30， x40， 原问题化为 max z=4x1+5x3-5x4 s.t. 3x1+2x3-2x4 20 -4x1+3x3-3x4 - 10 x1+ x3x4 5 -x1- x3+ x

8、4 -5 x1 ，x3 ，x4 0 将对称形式线性规划问题化为对偶问题如 下 Min W =20w1-10w2+5w3-5w4 s.t. 3w1-4w2+w3-w44 2w1+3w2+w3-w45 -2w1-3w2-w3+w4-5 w1，w2，w3，w40 -1，得 2w1+3w2+w3-w4 5 令y1=w1，y2=w2，y3=w3-w4，得 Min W =20y1-10y2+5y3 s.t. 3y1-4y2+y3 4 2y1+3y2+y3 =5 y1，y20 ,y3符号不限 原规划与对偶规划的线性关系 56 表33 原（对偶）规划对偶（原）规划 目标 max zmin f 目标 约束 m个

9、 = m个 0 0 自由 变量 变量 n个 0 0 自由 n个 = 约束 限制向量b 价值向量C 系数矩阵A 价值向量C 限制向量b 系数矩阵AT （3）若原规划的某个约束条件为等式约束， 则在对偶规划中与此约束对应的那个变量取 值没有非负限制； （4）若原规划的某个变量的值没有非负限 制，则在对偶问题中与此变量对应的那个约 束为等式。 没有非负限制 3214 321 431 4321 4321 , 0,105 30422 60272 2523 75max xxxx xxx xxx xxxx xxxxz 解：先将约束条件变形为如下形式 再根据非对称形式的对应关系，直接写出对偶规划 没有非负限制

10、 4321 4 4 321 431 4321 ,0,0 5 10 30422 60272 2523 xxxx x x xxx xxx xxxx 0,0, 72 5472 123 122 510306025min 43521 5421 321 31 321 54321 yyyyy yyyy yyy yy yyy yyyyyf 没有非负限制 max z=x1-x2+5x3-7x4 解答： 1 Min W =15y1+20y2 s.t. 2y1+4y2 4 y1+3y2 3 y1符号不限，y2 0 2 Min W =-5y1+14y2+3y3 s.t. Y1 +3y2-4y3 3 2y1-y2-5y

11、3 -6 -3y1+y2+3y3 =5 -y1-7y2+2y3 =4 y20 ，y3 0 ，y1符号不限 25 无约束、， 4321 4321 432 4321 4321 321 321 321 321 321 ,00 24732 543 3432 s.t. 4323min2 0, 564 37 3 2532 s.t. 422min.1 xxxx xxxx xxx xxxx xxxxZ. xxx xxx xxx xxx xxxZ 0.yy0,y 46y7y5y 24yy 3y 2y 3y2y s.t. 532max.1 321 321 321 321 321 yyyW 无约束 321 321

12、321 321 31 321 y0,y0,y 44y4y4y 37y3y3y 23yy 2y 32y y s.t. 253max.2 yyyW 答案： 四、线性规划的矩阵表示 0, . . max INB INB IINNBB XXX bIXNXBXts XCXCXCz 0, ,. . ,max INB I N B I N B INB XXX b X X X INBts X X X CCCz 0 . . max X bAXts CXz 0, . . max I I II XX bIXAXts XCCXz 0, . . )()(max 111 111 INB INB IBINBNB XXX bB

13、IXBNXBXt s XIBCCXNBCCbBCz 0, . . max INB INB IINNBB XXX bIXNXBXts XCXCXCz 0, . . max 111 INB INB IINNBB XXX IXBNXBbBXt s XCXCXCz XB Xj 请分别指出， B-1， B-1， CN-CB B-1 N， CI-CB B-1 习题：一个极大化（目标函数为max Z）的线 性规划问题，有三个非负变量x1,x2,x3，两个 “”型约束条件，x4,x5是松弛变量，用单纯形 法计算时得到的初始单纯型表及最终单纯型表 如下，最优单纯型表中，x1、x5为基变量，请 将表中空白处数字填

14、上。 1 0 0 1 1 3 6 10 1 1 0-3-1-20 33 性质一、对称性定理：对偶问题的对偶是原问题。 第二节 对偶问题的性质 max z=-CTX s.t. -AX-b X 0 min y =-bTW s.t. -ATW-C W 0 max y=bTW s.t. ATWC W 0 min z=CTX s.t. AXb X 0 对偶的定义 对偶的定义 其他形式问题的对偶其他形式问题的对偶 min z=CTX s.t.AXb X 0 max y=bTW s.t. ATWC W 0 min z=CTX s.t.AX=b X 0 max y=bTW s.t. ATWC W ：unr 弱

15、对偶定理说明：如果原问题是最大化问题， 则它的任一可行解对应的目标函数值不大与 其对偶问题（最小化问题）的可行解对应的 目标函数值。 性质三 （最优性判定定理 ）可行解是最优解时的性质 当X* 是原问题（Max）的可行解，Y* 是其对偶问题（Min）的可行解时，若 CX*=Y*b，则 X*与 Y* 是各自问题的最优解。 证明 ： 设X* 是原问题的任意一个可行解，由性质 2即弱对偶定理可知， CX* Y*b， 又由 CX*=Y*b知: CX* Y*b = CX*, 就是说,X* 使目标函数所达到的值比其它任何可行解使目标函数所达到的值不会小， 所以X* 是最优解。 同理（设Y*b CX* =Y

16、*b ） ，Y* 是其对偶问题的最优解。 证毕。 性质四 （强对偶定理）若原问题有最优解，则对偶问题也有最优解，且目标函 数最优值相等。 证明 设原问题的形式为：Max Z=CX，AX b; X 0 ，于是AX+XS=b，即 （A，I） =b，其中A为 m x n 矩阵，I为 m 阶单位矩阵，XS为m 维列向量。 既知有最优解，必有最优基变量对应的矩阵，记之为 B，那么，在最终单纯形表 中，检验数所形成的行向量为： （C- CBB-1A，- CBB-1） 0，于是 C- CBB-1A0 ，即 CBB-1A C （YA C） 令 Y*= CBB-1 ，又 - CBB-10，即 CBB-1 0 ，

17、可得 Y*= CBB-1 0 ，则 YA C, Y*是对偶问题 （ Min W=Yb; YA C; Y 0）的可行解，而 W =Y* b =CB B-1b。因 为 B 是最优基变量对应的矩阵，所以 Zmax=CX=CB B-1b = Y*b， 由性质3 ，定理获证。 X XS 对 偶 性 质 4 性质五 （52页）互补松驰定理 若X*与Y*分别为原问题和对偶问题的可行解，那 么Y*XS=0和 YSX*=0的充分必要条件是 X*、Y* 为最优解。 XS与 YS分别为原问题 和对偶问题的松弛变量和剩余变量。 Max Z=CX AX+XS=b X 0 Min W=Yb YA -YS=C Y 0 证明

18、 必要性：设原问题和对偶 问题的标准形式分别为： 和 于是 C=YA -YS，b= AX+XS， 所以Z（X）=CX=（ YA -YS ）X=YAX- YS X， 而 W（Y）=Y b=Y（ AX+XS）=YAX+YXS 可见,若 Y*XS= YSX*=0 ,则 Z（X*）=Y*AX*=W（ Y* ）,由性质3知 X*,Y* 为最 优解。必要性获证。以下证充分性。 若X*与Y*分别为原问题和对偶问题的最优解，由性质4可知 Z（X*）= Y*AX* - YS X* = Y*AX* +Y*XS= W（Y*）。又由于X*与Y*为可行解，存在X*、Y* 、XS， YS 0， 则必有YSX*0 ， Y*

19、XS0， 于是由上式知 Y*XS= YSX*=0，充分性获证， 完！ 原始问题和对偶问题最优解之间的互补松弛关系 min z=CTX s.t. AX-XS=b X, XS0 max y=bTW s.t. ATW+WS=C W, WS0 min z=CTX s.t. AXb X 0 max y=bTW s.t. ATWC W0 对偶对偶 引进剩余变量引进剩余变量 引进松弛变量引进松弛变量 XWS=0 WXS=0 互补松弛关系 X，XsW，Ws 设有L.P.问题 Max Z=x1+2x2+3x3+4x4 x1+x2+2x3+3x4 20 2 x1+ x2+3 x3+2 x420 xj 0, 1 j

20、 4 已知其对偶问题的最优解为：y1* =1.2, y2* =0.2, 相应的目标函数值W* =28, 试用对 偶理论求原问题的解。 解： 其对偶问题为： Min W=20 y1 +20 y2 y1 +2 y21 2y1 + y2 2 2y1 +3 y2 3 3y1 + 2y2 4 y1 , y2 0 x1 x2 x3 x4 Max Z=x1+2x2+3x3+4x4 x1+x2+2x3+3x4 +u1*=20 2 x1+ x2+3 x3+2 x4+u2*=20 Min W=20 y1 +20 y2 y1 +2 y2 -v1*=1 2y1 + y2 -v2*=2 2y1 +3 y2 -v3*=3

21、 3y1 + 2y2 -v4*=4 y1 , y2 0 x1 x2 x3 x4 将y1* =1.2, y2* =0.2 代入对偶问题的约束条件，得（1），（2）为严格不等 式，所以v1* 0 ， v2* 0 ；由互补松弛性得 x1* v1* =x2* v2* =0 ，所以 x1*=x2*=0 。又因为； y1* 0, y2* 0,所以 u1*= u2*= 0,即原问题的两个约束条件 为等式约束，故得方程组： 2x3*+ 3x4* = 20 3x3*+ 2x4*= 20 解之得 x3*=x4*=4 ；而W*=Z*=28。 故原问题的 最优解为： X*=（0，0，4，4）T，W*=28。 （1）

22、（2） （3） （4） 练习题： 设有L.P.问题 ，已知原问题的最优 解为X* =（0.0.4），Z=12 试求对 偶问题的最优解。 无无约约束束 321 321 321 321 321 , 0, 0 4 16 3 2532 34max xxx xxx xxx xxx xxxZ 解：其对偶问题为： 无约束无约束 321 321 321 321 321 , 0, 0 365 4 3 132 42min yyy yyy yyy yyy yyyW 将X* =（0 . 0 . 4）代入原问题中，有下式： 4 4 1 246 3 220532 321 321 321 xxx xxx xxx 无约束无约

23、束 321 321 321 321 321 , 0, 0 365 4 3 132 42min yyy yyy yyy yyy yyyW （1） （2） （3） 将X* =（0 . 0 . 4）代入原问题中，有下式： 4 4 1 246 3 2 20532 321 321 321 xxx xxx xxx 所以，根据互补松弛条件y1* xs1 = y2* xs2 = 0 ，必有 y1*= y2*=0， 代入对偶问题 （3）式， y3*=3。 因此，对偶问题的最优解为 Y*=（0 . 0 . 3）， W=12。 性质六 （62页）原问题的检验数对应于对偶问题的一个基本解。 Max Z=CX AX+X

24、S=b; X 0 Min W=Yb YA -YS=C Y 0 A=(B,N)；C=（CB,CN）；Y(B,N)（CB,CN）；Y0 或YB-Ys1=CB； YN-Ys2=CN；Y0，Ys10，Ys20。 Ys1,Ys2分别对应原问题基变量和非基变量的检验数； 假设原问题找到了一个基本可行解（XB,0），对应的检验数 （0，CN-CBB-1N，CI-CBB-1），分别令检验数的相反数为： Ys1 =0 Ys2=-( CN-CBB-1N) Y=CBB-1 将其带入约束条件式，满足上式，则说明原问题的检验数的相反数是其对偶问题 的一个解，得证。 设原问题为：Max Z=CX; AX+XS=b （ 0

25、 ）, X 0 , XS 0 ; 对偶问题为： Min W=Yb; YA YS=C; Y 0; YS 0 。 则原问题单纯形表的检验数行，对应于其对偶问题的一个基解。 性质6的意思究竟是什么？先列出原问题的单纯形表： 表中给出了对偶问题的变量与原问题各检验数的对应关系。当给出了原问题的一 个基后，算出各检验数，反号之后，就得到对偶问题的一个基本解。 (X,Xs)中的： 基变量、非基变量 分别对应于 (Ys,Y)中的： 非基变量、基变量。 性 质 6 x1 x2 xn xs1 xs2 xsm a11 a12 a1n 1 0 0 a21 a22 a2n 0 1 0 am1 am2 amn 0 0

26、1 (-) 1 2 n n+1 n+2 n+m ys1 ys2 ysn y1 y2 ym Z= 7.5 Z= XB Xj -15/8-35/4Z=337.5 2/3-20/3Z=60 XB Xj Z=66 （诊疗问题）教材第37页，试分别 对这三个表指出其对偶问题的解。 其他性质 无界性 若原问题（对偶问题）为无界解，则其对偶问题（原问题） 为无可行解。 证明：若原问题为最大化问题，由题意 CX* +，所以若对偶问题（最小化） 有可行解 Y*，根据性质 2 , C X* Y* b，于是 CX* 将有上界，与 CX* 无界矛盾。 证毕。 若原问题为最小化问题，由题意 Y*b -，所以若对偶问题（

27、最大化）有可行 解 X* ，根据性质 2 , C X* Y* b，于是 Y*b 将有下界，与 Y*b 无界矛盾。 证毕。 注意：本性质的逆不成立。当原问题（对偶问题）无可行解时，其对偶问题 （原问题）可以没有可行解（见下例）, 也可以是无界解，但决没有最优解。 综上所述，互为对偶的线性规划原问题与对偶 问题，它们之间解的对应关系仅仅存在下面的 三种可能： 1.两个问题都有可行解，则他们都存在最优解， 且他们的最优解的目标函数值相等； 2.一个问题有无界可行解，而另一个问题无可 行解； 3.两个问题均无可行解。 习题 判断下列说法是否正确，为什么？ （1）如线性规划的原问题存在可行解，则其对偶规

28、划问题也一定存在可行解； （2）如线性规划的对偶问题无可行解，则原问题也一定无可行解； 错；当原问题有无界解时（此时当然有可行解）， 其对偶问题无可行解。 （2）答： （1）答： 错；原问题可以有无界解时（此时当然有可行解）， 也可以无可行解。 资源影子价格：对偶问题是资源定价问题，对偶问题的最优解y1、y2、.、ym称为 m种资源的影子价格（Shadow Price） 影子价格越大，说明这种资源越是相对紧缺； 影子价格越小，说明这种资源相对不紧缺； 如果最优生产计划下某种资源有剩余，这种资源的影子价格一定等于0 （互补 松弛定理）。 种资源的边际利润第 种资源的增量第 最大利润的增量 i i

29、b z y i i mmii ybybybybwz 2211 mmiii ybybbybybzz)( 2211 ii ybz 资源效益分析和影子价格 原始和对偶问题都取得最优解时，最大利润 max z=min w 种资源的边际利润第 种资源的增量第 最大利润的增量 i ib z y i i 项目项目 放射科业务放射科业务 X X线平片检查线平片检查CTCT检查检查磁共振检查磁共振检查 平均每人次检查时平均每人次检查时 间（小时间（小时/ /次）次） 0.10.10.250.250.50.5 每月机器实际可使每月机器实际可使 用时间（小时）用时间（小时） 300300120120120120 平

30、均每人次检查利平均每人次检查利 润（元润（元/ /次）次） 表3-13 放射科3项检查资源需求、资源限制 及利润 A医院放射科目前可以开展X线平片检查、CT检查 和磁共振检查业务，经过资料收集和信息处理，A 医院估计今后放射科如果开展此3项业务，在现有 放射科医务人员力量和病人需求的情况下，每月此 3项业务的最多提供量为1800人次。平均每人次检 查时间、每月机器实际可使用时间、平均每人次检 查利润如表3-13 。 应用实例（教材第75-79页） XB Xj 模 型max Z = 20 x1 + 60 x2 +10 x3 x1 , x2 , x3 0 s.t. 0.1x1 300 0.25x2

31、 120 0.5x3120 x1 + x2+ x31800 每月业务量 X线：x1次； CT ：x2 次； 磁共振：x3次。 问题：（1） A医院从放射 科收益的角度 考虑，如何开 展最优业务量？ （2）在最优 业务安排情况 下，A医院如 何利用影子价 格进行决策？ （1）该线性规划模型的最优解 X*=（1320,480,0,168,0,120,0）T，最优值 Z*=55200。则A医院从放射科收益的角度考虑，在每月X线平片检查和CT检查业 务量各为1320人次和480人次，且不开展磁共振检查业务时，放射科利润最大， 达55200元。 （2）该对偶规划的最优解为Y*=(0,160,0,20)，

32、即对应于原问题资源约束的影子 价格。 X线y1*=0，xs1=x4=168 CT检查y2*=160，xs2=x5=0 磁共振机y3*=0 ，xs3=x6=120 放射科服务量y4*=20，xs4=x7=0。 )( o iii yyb 一、对偶单纯形法的基本思想 设有标准型的线性规划模型 Max Z=CX， AX =b; X 0 ， 上一章讨论的单纯形法基本思想是从某 一基本可行解出发，B-1b0, 在初始单纯形表中，检验数C- CBB-1A0 不一定成立，在保持B-1b0成立的条件下， 经过逐步换基迭代，使检验数C- CBB-1A0 成立，从而得到最优解或判断无最优解。 如果求解线性规划时，是

33、否可以这样 来进行，某个初始基本解使得检验数C- CBB-1A0一定成立，B-1b0不成立，我们 能否对约束等式和目标函数进行适当的行初 等变换使条件C- CBB-1A0始终成立，直至 B-1b0成立，从而求得最优解或判断无最优 解。这就是对偶单纯形法的基本思想。 对偶单纯形法的基本思想：求解一 般的线性规划问题时，由满足C- CBB-1A0 的对偶可行解出发，逐次换基迭代，但始终 保持对偶可行性成立，也即C- CBB-1A0成 立，直至B-1b0成立，从而求得最优解或判 断无最优解。 第三节 对偶单纯形法 二、对偶单纯形法求解线性规划问题 的一般步骤和过程： 三、对偶单纯形法求解线性规划问题

34、的一般步骤和过程： 三 单纯形法与对偶单纯形法计 算步骤的对比 单纯形法单纯形法 （极大化）（极大化） 对偶单纯形法对偶单纯形法 （极大化）（极大化） 前提条件前提条件b列所有元素列所有元素bi0 所有检验数所有检验数 cj-Zj0 最优性检验最优性检验 所有检验数所有检验数 cj-Zj0 b列所有元素列所有元素bi0 换入、换出换入、换出 变量的确定变量的确定 先确定换入变量先确定换入变量 再确定换出变量再确定换出变量 先确定换出变量先确定换出变量 再确定换入变量再确定换入变量 解的变化解的变化可行可行最优最优非可行非可行最优最优 四、表解形式对偶单纯形法求解实例 初始可行基 （大M法） 将

35、约束条件等式的两边都乘以-1，得到 MaxZ = -1600 x1 - 2500 x2 -400 x3 s.t. - x1 - 5 x2 - x3+ x4 = -4 -2x1 - 2.5x2 +x5= -3 x1 , x2 , x3 , x4 , x5 0 ， 四、表解形式对偶单纯形法求解实例 XB Xj 对偶问题的 初始可行基 建立此问题的初始单纯形表如下： 800500400 XB Xj 400200 200400 XB Xj 原问题的最优解为（1，0.4，0，0，0），最优值为2600。对偶问题的最优解 为（200，600，0，0，200），最优值为2600。 最优解 五、对偶单纯形法的

36、优缺点及用途 对偶单纯形法的优点： 1.初始解可以是非可行解，避免加入人工变量， 简化运算； 2.对变量多于约束条件时的LP问题，直接用对 偶单纯形法求解，对变量少于约束条件的LP问 题，可先将其转化为对偶问题，再用对偶单纯 形法运算求解，可减少迭代次数，简化计算； 3.在灵敏度分析中，有时需要用对偶单纯形法 处理简化。 对偶单纯形法缺点： 在初始单纯形表中对偶问题是基可行解，这点 对多数线性规划问题很难做到。 14/3 8/5 Y=（8/5 , 1/5），Ys = （0，0，9/5） X=（11/5 ， 2/5 ， 0，0，0）， Z =28/5 3 1 1 1 -1 0 1 1 0 1 2

37、 -1 = B-1= B-1 1 -1 -2 0 1/2 1/2 0 -1/2 1/2 = B-1P3 1 -1 -2 0 1/2 1/2 0 -1/2 1/2 = 1 1/2 -3/2 10 15 5 已知线性规划问题用单纯形法计算时得到 的初始单纯型表及最终单纯型表如表318， 请将表中空白处数字填上。 0 1 0 0 10 15 1 1/2 00-3/20-3/2 015-3/2 -1/2 灵敏度分析的目的在于，当求解 L.P.问题，且已获最优解之后，再假定原问题 中某参数如 bi 或 cj 或 aij 发生变化，或增加一个变量，或增加一个约束条件后， 于是得到一个新的L.P.问题，这样

38、一个新的L.P.问题对原L.P.问题的最优解和最优 值产生什么样的影响？ 希望从原来的最终单纯形表出发，经少量运算而获得新问题的最终（优）单纯 形表；或确定参数的变化范围，使原L.P.问题的最优解或最优基变量不变。（既然 参数发生变化，或增加一个变量，或增加一个约束条件后，当然可以重新从头求 解） 灵 敏 度 分 析 第四节 线性规划的灵敏度分析 0 b max X AX CXzj=cjCBB 1Pj j P b =B 1Pj =B 1b 第四节 灵 敏度分析 关于灵敏度分析，我们讨论如下 五种情况： 1. 目标函数系数cj的灵敏度分析； 2. 约束条件的常数项bi的灵敏度分析； 3.分析参数

39、aij的变化； 4.增加新变量xij的灵敏度分析； 5. 添加一个新的约束条件的灵敏度分析。 一、目标函数中价值系数Cj发生变化的分析 （1）若cj不是基变量的系数, 这种情形最为容易。由检验数的计算公式： 由j = cj - CB B-1Pj知， 若cj 变为cj +cj ，则j变为cj+cj - CB B-1Pj 。 若cj +cj - CB B-1Pj 0(1 j n)， cj -j那么原最优解不变； 否则须从原最终单纯形表出发继续迭代,至新的j 0。 （2）若cj是基变量 Xj的系数,这种情形较为复杂。 因 cj CB（设cj为 CB 的第s个分量），故当cj 变为cj +cj时, C

40、B将变为CB +CB ， cj变化后最终单纯形表中检验数那一行将变为： C-（CB +CB）B-1A= C-CBB-1A -CB B-1A =（C-CBB-1A)-(0,0,cj,0,.,0)B-1A =（C-CB B-1A）- cj(as1,as2,.,asn). （cj变化前最终单纯形表中的第S行） 即新的检验数行等于原来检验数行减去cj 乘原来最终单纯形表的第S行（Xj的检验数 除外，应全为0）。 以下举例说明。 第S个 问应如何安排生产使制药公司获利最多？ 产品 原料 1.若第3种药品的单位利润c3发生变化，那么c3 在什么范围内变化时，原问题的最优解不变？ 2.基本变量x1的系数c1

41、=5有改变量，那么c1在 什么范围内变化时，原问题的最优解不变？ 表3-9 初始单纯形表和最终单纯形表 解： CB cj5+c18600 b x1x2x3x4 x5 5+c1x11002-14 8x2011-118 Cj00-2-2-2-3+Z=84+4c1 XB Xj 表3-10 基本变量x1的系数c1=5改变c1对最 优解影响 1.若非基变量c4有改变量c4，那么c4在何范围内 变化时，问题的最优解不变？2.若基变量c2有改变量 c2，那么c2在何范围内变化时，问题的最优解不 变？最优值为多少？ 解： 二、右端项 b 发生变化 b=第i个分量 灵 敏 度 分 析 第四节 灵敏度分析 假定

42、bi 发生变化，设分量bi 获得增量 bi 而变为 bi+bi ,则 b 将获得增量b,根 据单纯形法矩阵表示式的讨论，最优解的基本变量 xB = B-1b， B-1b将获得增量B- 1b 而变为B-1b+ B-1b ，即基本变量保持不变，只有最优值的变化；否则，需要 利用对偶单纯形法继续计算。 只要B-1b+ B-1b 0，则在原最终单纯形表中只要用 B-1b+ B-1b 代替 B-1b 这 一列，就可获得新最终单纯形表。此处： 0 . . 0 bi 0 . . . 0 例10以例9为例： （1）若b1=12有改变，为使最优基本变量x1、x2地位不变，求b1的变化范围。 （2）若b1的变化超

43、出了所允许的范围，如b1=9，试求取新的最优解？ 由表 3-9 最后二列（因最终单纯形表之最后二列x4,x5构成单位矩阵）知 B-1= ，而b= 易见由 B-1b+ B-1b= + 知 -2 b1 8，当 b1 在此范围内变化时，只须修改表 3-9 的B-1b列即可获得新问题 的最终单纯形表！ 2 -1 -1 1 b1 0 4 8 0 0 4+2b1 8-b1 = 2 -1 -1 1 b1 0 XB Xj 若b1的变化超出了所允许的范围，如b1=9， 最优解的基本变量发生变化，此时检 验数不变，需用对偶单纯形法求出新的最优解。 表3-11 b1改变量b1=9时对最优解影响 2 -200-4Z=

44、100-5 三、技术系数aij的变化 XB Xj 00-2-2-3Z=84 Z=80 00 -10/3 0-11/3 0 2/3 -2/3 B-1b 习题二第5题：给出线性规划问题及其最优单 纯型表如下： max z=6x1+2x2+12x3 s.t. 4x1+x2+3x324 2x1+6x2 +3x330 xj 0,j=1,2,3 （1）试求出最优解不变的c3变化范围； （2）试求出最优基变量不变的b2变化范围； （3）在原线性规划的约束条件上，增加下 面的约束条件： x1+2x2+2x312，其最优解 是否变化，如变化，试求出最优解。 （2）B-1= ， 而b= 易见由 B-1b+ B-1

45、b = + = 知 6+b2 0，当 b2 -6， b224 时，只须修改表的B-1b列即可获得新问题的最 终单纯形表！ 1/3 0 -1 1 0 b2 8 6 8 6+b2 （1）若是最优解不变，则必须满足下式 6 -4c3/30 2 c3/ 30 - c3/ 30 （1） （2） （3） c39/2 c36 c30 c36 0 b2 解： 习题：对上述最大化的线性规划问题，已知其初始和 最优单纯形表：（1）请填写最优表中空白处的数字； （2）写出原线性规划问题；（3）写出其对偶规划及其 最优解；（4）当b变为b+b， b=1，-1，0T，问 在何范围内变化，原最优性不变；（5）目标函数x2

46、的 系数c2从-1变 为-2，原最优性是否改变？求出c2=-2时最优解的最 优目标函数值。 （1）、请填写最优表中空白处的数字； 0 1/2 00 1 0 0 0 0 1 0 0 -3/2 1 -3/2 -1/2 -3/2 1 (4)-5 30 (5)-2 c20b1=60,b2=10,b3=20 1. 解： 将y*1 =4/5, y*2 =3/5 代入对偶问题的约束条 件，得（2），（3）（4) 为严格不等式，所 以ys2 0 ， ys3 0 ， ys4 0 ；由互补松弛 性得 x*2 ys2 =x*3 ys3=x*4 y s4=0 所以 x*2=x*3=x*4=0 。又因为； y*1 0,

47、 y*2 0, 所以 x*s1= x*s2= 0,即原问题的两个约束条件 为等式约束，故得方程组： x*1+3 x*5= 4 2x*1+x*5= 3 解之得 x*1= x*5=1；而W*=Z*=5。 故原问题 的最优解为： X*=（1，0，0，0，1）T， W*=5。 其对偶问题为 Max Z=4 y1 +3 y2 y1 +2 y22 y1 - y2 3 2 y1 +3 y2 5 y1 + y22 3 y1 + y2 3 y1 , y2 0 Min W=2x1+3x2+5x3+2x4+3x5 s.t. x1+x2+2x3+x4+3x54 2 x1- x2+3 x3+ x4+ x53 xj 0,

48、 1 j 5 （1） （2） （3） （4） （5） 原（对偶）规划对偶（原）规划 目标函数max z=目标函数min f= 约束条件 有m个（i=1,.m)m个 0 0 自由 变量 变量 n个 0 0 自由 n个 约束条件 本章内容小结 1、原对偶问题关系 对称形式： 互为对偶 (LP) Max = T (DP) Min =T s.t. s.t. T 0 0 “Max - ” “Min- ” 2、 资源影子价格 对偶问题是资源定价问题，对偶问题的最优解w1、w2、.、wm称为m种 资源的影子价格（Shadow Price） 影子价格越大，说明这种资源越是相对紧缺 影子价格越小，说明这种资源相对不紧缺 如果最优生产计划下某种资