运筹学（第三版）：第2章 对偶理论和灵敏度分析

1、清华大学出版社 1 二 线性规划与目标规划 n第第1 1章章 线性规划与单纯形法线性规划与单纯形法 n第2章 对偶理论与灵敏度分析 n第3章 运输问题 n第4章 目标规划 清华大学出版社 2 第2章 对偶理论和灵敏度分析 n第1节 单纯形法的矩阵描述 n第2节 改进单纯形法 n第3节 对偶问题的提出 n第4节 线性规划的对偶理论 n第5节 对偶问题的经济解释影子价格 n第6节 对偶单纯形法 n第7节 灵敏度分析 n第8节* 参数线性规划 清华大学出版社清华大学出版社 3 第1节 单纯形法的矩阵描述 设线性规划问题可以用如下矩阵形式表示： 目标函数 max z=CX 约束条件 AXb 非负条件

2、X0 清华大学出版社清华大学出版社 4 第1节 单纯形法的矩阵描述 将该线性规划问题的约束条件加入松弛变量后，得到标 准型： max z=CX+0Xs AX+IXs=b X，X s0 其中I 是mm单位矩阵。 清华大学出版社清华大学出版社 5 第1节 单纯形法的矩阵描述 若以Xs为基变量，并标记成XB，可将系数矩阵（A，I） 分为（B，N）两块。B是基变量的系数矩阵，N是非基 变量的系数矩阵。并同时将决策变量也分为两部分： 相应地可将目标函数系数C分为两部分：CB和CN，分别 对应于基变量XB和非基变量XN，并且记作 C=（CB, CN） N B X X X 清华大学出版社清华大学出版社 6

3、第1节 单纯形法的矩阵描述 若经过迭代运算后，可表示为： 相应有 ; X X X X X X S N N S B B 2 1 1 1 非基变量： 变量可包含原基变量和松弛 基变量 非基变量 基变量 松弛变量： 其中系数矩阵 2 1 2 1 S S S X X X ; S N N; N B A 清华大学出版社清华大学出版社 7 第1节 单纯形法的矩阵描述 线性规划问题可表示为： B B B max z(,C )=C(32) ( , )BX(33) X ,0(34) B BNBNN N B N N N X CXC X X X B NNXb X X 目标函数 约束条件 非负条件 清华大学出版社清华大

4、学出版社 8 第1节 单纯形法的矩阵描述 将（3-3）式移项及整理后得到： 11 11 11 ; () () BN BN BNNN BNBN BXbNX XB bB NX zCB bB NXC X C B bCC B N X 目标函数： 清华大学出版社清华大学出版社 9 第1节 单纯形法的矩阵描述 令非基变量XN =0，由上式得到： bB ; bB X )( 1 B 1 1 Cz 0 目标函数的值 基可行解 清华大学出版社清华大学出版社 10 第1节 单纯形法的矩阵描述 （1）非基变量的系数表示为： 1 j 11 BB () c(1,2, ) C-C-C NB j CC B N zjn B A

5、B 对应已用的检验数符号 检验数也可表示为： 与 清华大学出版社清华大学出版社 11 第1节 单纯形法的矩阵描述 （2）规则表示为： RHS值 表示选用0的分量 换入变量的系数向量 ij i ij ij i )PB( )bB( )PB( )PB( )bB( min 1 1 1 1 1 0 将公式（2-4）式，（2-5)式改写成 清华大学出版社清华大学出版社 12 12 112 111 1 111 1 () BNS NBNBSB XB N XB XB b zCC B N XC B XC B b 清华大学出版社清华大学出版社 13 第1节 单纯形法的矩阵描述 （3）单纯形表与矩阵表示的关系 )(

6、bBC bB X X X z BCNBCC BNB B N N B BBN 72 01 10 1 1 1 1 1 1 1 1 2 1 清华大学出版社清华大学出版社 14 第1节 单纯形法的矩阵描述 单纯形表中的数据 基变量 非基变量等式右边 系数矩阵 检验数 0 1 1 BB XB 111 111 Ns NBBB XXRHS B NBB b CC B NC BC B b 11 11 () () BNNN BNBN zCB bB NXC X C B bCC B N X 清华大学出版社清华大学出版社 15 小结 1）掌握矩阵的运算； 2）理解基矩阵的作用； 3）了解矩阵运算与单纯表的关系。 清华大

7、学出版社清华大学出版社 16 第2节 改进单纯形法 求解线性规划问题的关键是计算B-1 ，以下介绍一 种比较简便的计算B-1的方法。 清华大学出版社清华大学出版社 17 第2节 改进单纯形法 设mn系数矩阵为A，求其逆矩阵时，可先从第1列开始。 mmmm m m aaa aaa aaa A 21 22221 11211 清华大学出版社清华大学出版社 18 第2节 改进单纯形法 以a11为主元素, 进行变换 )( a/a a/a a/ a a a P mm 1 1 111 1121 11 1 1 12 11 1 主元素 清华大学出版社清华大学出版社 19 第2节 改进单纯形法 然后构造构造含有（

8、1）列，而其他列都是单位列的矩阵 1/ 1/ 00/1 111 1121 11 1 aa aa a E m 清华大学出版社清华大学出版社 20 第2节 改进单纯形法 可得到 )( mm )( m )( m )( )( m )( aa aa aa AE;PE 11 2 1 2 1 22 1 1 1 12 111 0 0 1 0 0 1 11 21 1222 11 21 1121 a a aa a a aa 清华大学出版社清华大学出版社 21 第2节 改进单纯形法 )( a 1 22 而后以第2列的 为主元素，进行变换 )( a/a a/ a/a P )()( m )( )()( )( 2 1 1

9、 22 1 2 1 22 1 22 1 12 2 1 2 清华大学出版社清华大学出版社 22 第2节 改进单纯形法 10 010 01 1 22 1 2 1 22 1 22 1 12 2 )()( m )( )()( a/a a/ a/a E 然后构造构造含有（2）列，而其他列都是单位列的矩阵 可得到 )( mm )( m )( m )( m )( )( a a a a a a AEE 2 2 2 2 1 2 3 2 23 2 13 12 00 10 01 清华大学出版社清华大学出版社 23 第2节 改进单纯形法 重复以上的步骤，直到获得 21 1 1 1 m EE E AI 可见EnE2E1

10、=A-1。用这方法可以求得单纯形法的基矩阵B的 逆矩阵B-1 清华大学出版社清华大学出版社 24 第2节 改进单纯形法 以例1为例进行计算。 124 164 82 00032 52 41 321 54321 xx xx xxx xxxxxzmax 清华大学出版社清华大学出版社 25 第2节 改进单纯形法 第1步：确定初始基，初始基变量;确定换入，换出变量 （1）确定初始基和初始基变量： （2）计算非基变量的检验数，确定换入变量。 5 4 3 5430 0 1 1 1 x x x X;P,P,PB B 换入变量 对应 注意： 21 2100 1 0 32 4 0 2 0 4 1 100 010

11、001 00032 000 x ,x, ),(, )P,PN(NBCC BNN 清华大学出版社清华大学出版社 26 第2节 改进单纯形法 (3) 确定换出变量 5 1 0 1 02 1 02 min0 812 min, ,3 24 i i B b B P B P x 对应 表示选择0的元素 清华大学出版社清华大学出版社 27 第2节 改进单纯形法 （4）基变换计算 将新的基 单位矩阵。计算： 243 P,P,P 41 01 211 41 0 21 4 0 2 112 / / E / / P；构造 主元素 41 01 211 1 1 1 41 01 211 1 01 1 1 / / / / BE

12、B 清华大学出版社清华大学出版社 28 第2节 改进单纯形法 （5）计算非基变量的系数矩阵 （6）计算RHS 41 0 21 4 1 1 4 1 41 01 211 1 4 1 1 1 11 / / / / NBN 3 16 2 12 16 8 41 01 211 1 1 / / bB 清华大学出版社清华大学出版社 29 第2节 改进单纯形法 第1步计算结束后的结果 ),(),(C,CC ;x ,xX ;x ,x ,xX ;P,P,PB NB T N T B 02300 11 1 1 51 243 2431 价值系数 非基变量 基变量 基 清华大学出版社清华大学出版社 30 第2节 改进单纯形

13、法 计算非基变量的检验数，确定换入变量 换入变量 对应 注意： 51 5111 1 1 432 1 0 0 0 4 1 4100 010 2101 30002 111 x ,x/, / / ),(, )P,PN(NBCC BNN 清华大学出版社清华大学出版社 31 第2节 改进单纯形法 确定换出变量 1 1 1 1 11 1 11 min0 2 16 min,2 14 i i B b B P B P x 对应 清华大学出版社清华大学出版社 32 第2节 改进单纯形法 由此得到新的基 4100 214 2101 4100 010 2101 100 014 001 100 014 001 0 4

14、1 0 4 1 1 12 1 2 21 2412 / / / / BEB EP P,P,PB 2 主元素 清华大学出版社清华大学出版社 33 第2节 改进单纯形法 计算RHS 3 8 2 12 16 8 4100 214 2101 1 2 / / bB 清华大学出版社清华大学出版社 34 第2节 改进单纯形法 第2步计算结束后的结果 ),(),(C,CC ;x ,xX ;x ,x ,xX ;P,P,PB NB T N T B 00302 22 2 2 53 241 2412 价值系数 非基变量 基变量 基 清华大学出版社清华大学出版社 35 第2节 改进单纯形法 第3步：计算非基变量（x3,

15、x5）的检验数 换入变量正检验数 对应 注意： 53 5322 1 2 412 1 0 0 0 0 1 4100 314 2101 30200 222 x ,x/, / / ),(, )P,PN(NBCC BNN 清华大学出版社清华大学出版社 36 第2节 改进单纯形法 确定换出变量 4 4 41 3 2 8 21 2 0 5 1 2 5 1 2 1 2 x / , / min PB PB bB min i i 对应 清华大学出版社清华大学出版社 37 第2节 改进单纯形法 新的基 主元素 的系数向量是换入变量 4/1 2 2/1 1 0 0 4/100 214 2/101 ;, 5 1 2

16、5 2513 PB x PPPB 清华大学出版社清华大学出版社 38 第2节 改进单纯形法 计算B的逆矩阵 1810 0210 0411 81 21 41 33 / / / E / / / 构造 08121 1212 0410 4100 214 2101 1810 0210 0411 1 23 1 3 / / / / / / / / BEB 清华大学出版社清华大学出版社 39 第2节 改进单纯形法 计算非基变量的检验数 已无正检验数 注意： 8123 0 1 0 0 0 1 08121 1212 0410 30200 4333 1 3 333 /,/ / / / ),(, P,PNNBCC B

17、NN 清华大学出版社清华大学出版社 40 第2节 改进单纯形法 得到最优解： 1 *1 53 2 01/ 4084 21/ 21164 1/ 21/80122 x XxB b x 14 2 4 4 302 1 3 ,bBCz B * 目标函数的最优值为： 清华大学出版社清华大学出版社 41 第3节 对偶问题的提出 v什么是对偶？ 对同一事物（或问题），从不同的角度（或立场） 提出相对的两种不同的表述。 v例如：在平面内，矩形的面积与其周长之间 的关系，有两种不同的表述方法。 周长一定，面积最大的矩形是正方形。 面积一定，周长最短的矩形是正方形。 v这种表述有利于加深对事物的认识和理解。 v线性

18、规划问题也有对偶关系。 清华大学出版社清华大学出版社 42 第3节 对偶问题的提出 v对第1章例1从对偶的角度进行表述。 假设该工厂的决策者决定不生产产品、，而将其所 有资源出租或外售。这时工厂的决策者就要考虑给每种 资源如何定价的问题。设用y1，y2，y3分别表示出租单 位设备台时的租金和出让单位原材料A，B的附加额。 他在做定价决策时，做如下比较：若用1个单位设备台 时和4个单位原材料A可以生产一件产品，可获利2元， 那么生产每件产品的设备台时和原材料出租或出让的 所有收入应不低于生产一件产品的利润，这就有 y1+4y22 清华大学出版社清华大学出版社 43 第3节 对偶问题的提出 v对第

19、1章例1从对偶的角度进行表述。 同理将生产每件产品的设备台时和原材料出租或出让 的所有收入应不低于生产一件产品的利润，这就有 2y1+4y33 把工厂所有设备台时和资源都出租或出让，其收入为 w = 8y1+16y2+12y3 从工厂的决策者来看当然w愈大愈好；但受到接受方的 制约，从接受者来看他的支付愈少愈好，所以工厂的决 策者只能在满足大于等于所有产品的利润条件下，提出 一个尽可能低的出租或出让价格，才能实现其原意，为 此需解如下的线性规划问题： 清华大学出版社清华大学出版社 44 第3节 对偶问题的提出 称这个线性规划问题为例1线性规划问题(这里称为 原问题)的对偶问题。这就是从另一角度

20、提出的线性 规划问题。 min w=8y1+16y2+12y3 y1+4y2 2 2y1 +4y33 yi0，i=1,2,3 (2-8) 清华大学出版社清华大学出版社 45 第3节 对偶问题的提出 进一步来讨论它们之间的关系。 从第1节得到检验数的表达式是 CNCBB-1N与CBB-1 由第1章已知：当检验数 CNCBB-10 (2-9) CBB-10 (2-10) 时，表示线性规划问题已得到最优解。这也是最优解 的判断条件。 清华大学出版社清华大学出版社 46 第3节 对偶问题的提出 现在讨论这两个条件。 v(1) 由于(2-9)式，(2-10)式中都有乘子CBB-1，称它为单纯形乘 子，用

21、符号Y= CBB-1表示。由(2-10)式，得到Y0 v(2) 对应基变量XB的检验数是0，CBCBB-1B=0。包括基变量 在内的所有检验数可用C CBB-1A0表示。 从此可得CCBB-1A=CYA0，移项后，得到YAC v(3) Y由(2-10)式，得到 Y= CBB-1 (2-11) 将(2-11)式两边右乘b，得到 Yb= CBB-1b (2-12) Yb= CBB-1b=z，因Y的上界为无限大，所以只存在最小值。 清华大学出版社清华大学出版社 47 第3节 对偶问题的提出 现在讨论这两个条件。 v(4) 从这里可以得到另一个线性规划问题 min w=Yb YAC Y0 称它为原线性

22、规划问题max z=CXAXb，X0的对偶规 划问题 。 清华大学出版社清华大学出版社 48 第3节 对偶问题的提出 对偶规划问题 oy,y,y yy yy y,y,yY Y ,Y yyymin,Ymin T 321 31 21 321 321 342 24 0 32 4 0 2 0 4 1 1216812168 约束条件： 目标函数： 清华大学出版社清华大学出版社 49 第4节 线性规划的对偶理论 4.1 原问题与对偶问题的关系 4.2 对偶问题的基本性质 清华大学出版社清华大学出版社 50 4.1 原问题与对偶问题的关系 v原问题（LP）： 1 122 1 111211 2 12 12 m

23、ax ,0 nn n mmmnm n n zc xc xc x x aaab x aaab x x xx 清华大学出版社清华大学出版社 51 4.1 原问题与对偶问题的关系 v对偶问题(DP) 0, , min 21 21 21 11211 21 m2211 n n mnmm n m m yyy ccc aaa aaa yyy bybyby 清华大学出版社清华大学出版社 52 4.1 原问题与对偶问题的关系 v标准型原问题与对偶问题的关系 12 1111211 2212222 12 12 min maxzmaxzmin j n i n n mmmmnm n x xxx y yaaab yaaa

24、b yaaab ccc 原关系 对偶关系 清华大学出版社清华大学出版社 53 4.1 原问题与对偶问题的关系 v例2 根据表2-3写出原问题与对偶问题的表达式 x y x1x2 b y1128 y24016 y30412 c23 清华大学出版社清华大学出版社 54 4.1 原问题与对偶问题的关系 v下列形式的变换关系为对称形式 原问题 （LP） 对偶问题(DP) 0 32 24 0 124 164 82 1216832 321 31 21 21 2 1 21 32121 y,y,y yy yy x ,x x x xx yyyminxxzmax 清华大学出版社清华大学出版社 55 4.1 原问题

25、与对偶问题的关系 v非对称形式的变换关系 原问题的约束条件中含有等式约束条件时， 按以下步骤处理。 设等式约束条件的线性规划问题为 n ,j ,x m,i,bxa xczmax j n j ijij n j jj 210 21 1 1 清华大学出版社清华大学出版社 56 4.1 原问题与对偶问题的关系 v非对称形式的变换关系 第一步：先将等式约束条件分解为两个不等 式约束条件 1 1 1 1 max ,1,2,2 13 ,1,2, 0,1,2, ,1,2,2 14 n jj j n ijji n j ijji j n j ijji j zc x a xbim a xbim xjn a xbim

26、 清华大学出版社清华大学出版社 57 4.1 原问题与对偶问题的关系 v非对称形式的变换关系 第二步：按对称形式变换关系可写出它的对 偶问题 o设yi是对应(2-13)式的对偶变量，yi是对应(2-14) 式的对偶变量，i=1,2,，m m,i,y,y n,j ,cyaya ybybmin i i m i j m i iij iij m i m i ii ii 210 21 11 11 清华大学出版社清华大学出版社 58 4.1 原问题与对偶问题的关系 0 21 1 1 i i i ii m i j i iij m i i ii y,y,yyy n ,j,cyya yybmin 令 将上述规划

27、问题的各式整理后得到 m,.iy n ,j,cya ybmin i m i jiij m i ii 21 21 1 1 ，为无约束 清华大学出版社清华大学出版社 59 4.1 原问题与对偶问题的关系 综合上述，线性规划的原问题与对偶问题的关系可表示为： maxzmin nn 0 0 m 0 0 RHS RHS m 原问题对偶问题 目标函数目标函数 约个个 束变 条量 件无约束 约个个 束变 条量 件无约束 约束条件目标函数变量的系数 目标函数变量系数约束条件的 清华大学出版社清华大学出版社 60 4.1 原问题与对偶问题的关系 例3 试求下述线性规划原问题的对偶问题 无约束 4321 3432

28、 2431 14321 4321 00 36 2422 153 532 x,x ,x,x yxxx yxxx yxxxx xxxxzmin 清华大学出版社清华大学出版社 61 4.1 原问题与对偶问题的关系 由表2-4中原问题和对偶问题的对应关系，可以直接写出上述 问题的对偶问题， 无约束 321 321 321 31 21 321 00 1 523 3 22 645 y,y,y yyy yyy yy yy yyyzmax 清华大学出版社清华大学出版社 62 4.2 对偶问题的基本性质 v(1) 对称性：对偶问题的对偶是原问题 ; v(2)弱对偶性：若X是原问题的可行解，Y是对偶问题的可行 解

29、。则存在CXYb; v(3) 无界性：若原问题(对偶问题)为无界解，则其对偶问题 (原问题)无可行解; v(4) 可行解是最优解时的性质 ; v(5) 对偶定理：若原问题有最优解，那么对偶问题也有最优 解；且目标函数值相等; v(6) 互补松弛性 ; v(7) 原问题检验数与对偶问题解的关系。 清华大学出版社清华大学出版社 63 4.2 对偶问题的基本性质 v(1) 对称性： 对偶问题的对偶是原问题。 证明：设原问题是 max z=CX; AXb； X0 根据对偶问题的对称变换关系，可以找到它的对偶问题是 min w=Yb; YAC； Y0 若将上式两边取负号，又因min w=max(-)可得

30、到 max(w)=Yb; YA C； Y0 根据对称变换关系，得到上式的对偶问题是 min( w)= CX； AX b; X0 又因 min(w)=max w，可得 Max w=max z=CX； AXb; X0 这就是原问题。 清华大学出版社清华大学出版社 64 4.2 对偶问题的基本性质 bYXC YX 则存在 是对偶问题的可行解是原问题的可行解，若 v(2)弱对偶性 , :min;0 ,. . max zCX;AXb;X0 X AXb YY YAXYb Yb YAC Y YYAC XYAXCX CXYAXYb 设原问题是 因 是原问题的可行解，所以满足约束条件 即 若 是对偶问题的可行解

31、，将 左乘上式，得到 原问题的对偶问题是 因 是对偶问题的可行解，所以满足 将 右乘上式 得到 于是得到证毕 清华大学出版社清华大学出版社 65 4.2 对偶问题的基本性质 是不可能成立。,XCbY v(3) 无界性 若原问题(对偶问题)为无界解，则其对偶问题 (原问题)无可行解。 证：由性质（2）可知， 例： 1212 1212 1212 1212 : maxmin42 2421 21 ,0,0 LPDP zxxyy xxyy xxyy x xy y 清华大学出版社清华大学出版社 66 4.2 对偶问题的基本性质 v从两图对比可明显看到原问题无界， 其对偶问题无可行解 y1 y2 0 1 1

32、2 21 21 21 y,y yy yy 0 2 42 21 21 21 x ,x xx xx 清华大学出版社清华大学出版社 67 4.2 对偶问题的基本性质 v(4) 可行解是最优解时的性质 设 是原问题的可行解， 是对偶问题的可行解， 当 时， 是最优解。 证明证明: X bY X CY ,X Y 证毕。所以是最优解存在 ，的所有可行解同理可证明，对原问题 因而是最优解 最小的可行解，可见是使目标函数取值所以 因都存在所有可行解 可知，对偶问题的，根据性质证：若 是最优解时，当 是对偶问题的可行解是原问题的可行解，设： ., . . , ; 2 . , X XCbYXC X bYbY bY

33、XCXCbYY bYXC YXbYXC Y 清华大学出版社清华大学出版社 68 4.2 对偶问题的基本性质 .BCY ,CAY ,ABCC ,BX BB 11 0 其中即得到必存在 对应的基矩阵是原问题的最优解，它证：设 v(5) 对偶定理 若原问题有最优解，那么对偶问题也有最优 解；且目标函数值相等。 是对偶问题的最优解。可见 由此，得到 取值是最优解，使目标函数因原问题的 使得是对偶问题的可行解，若 Y X CbBCbY bBCX CzX bBCbY Y B B B 1 1 1 清华大学出版社清华大学出版社 69 4.2 对偶问题的基本性质 为最优解。当且仅当，和那么 题的可行解，分别为原

34、问题和对偶问若 Y ,X ;X YXY Y ,X SS 00 v(6) 互补松弛性 00 SS SS Y ,YX,X CYYAbXAX YbminCXzmax 对偶问题原问题 题的标准关系是证：设原问题和对偶问 清华大学出版社清华大学出版社 70 4.2 对偶问题的基本性质 v(6) 互补松弛性 将原问题目标函数中的系数向量C用C=YA-YS代替后，得到 z=(YA YS)X=YAX YSX (2-15) 将对偶问题的目标函数中系数列向量b，用b=AX+XS代替后， 得到 w=Y(AX+XS)=YAX+YXS (2-16) ;, 4, 5 2 152 16 0,0 SS SS Y X0,YX0

35、YbYAXCX X Y CXYAXYb YXY X 若则 由性质（ ），可知是最优解。 又若分别是原问题和对偶问题的最优解， 根据性质（ ），则有 由（），（）式可知，必有 清华大学出版社清华大学出版社 71 4.2 对偶问题的基本性质 v(7) 原问题检验数与对偶问题解的关系 设原问题是 max z=CX; AX+XS=b; X,XS0 它的对偶问题是 min w=Yb; YA YS=C; Y,YS0 则原问题单纯形表的检验数行对应其对偶问题的一个基解， 其对应关系见表2-5。 清华大学出版社清华大学出版社 72 4.2 对偶问题的基本性质 v(7) 原问题检验数与对偶问题解的关系 11 1

36、2 0 BNS NBB SS XXX CC B NC B YYY YS1是对应原问题中基变量XB的剩余变量， YS2是对应原问题中非基变量XN的剩余变量。 原问题的变量原问题的变量 对偶问题的变量对偶问题的变量 基变量基变量 非基变量非基变量 非基变量非基变量 基变量基变量 清华大学出版社清华大学出版社 73 4.2 对偶问题的基本性质 v(7) 原问题检验数与对偶问题解的关系 证: 设B是原问题的一个可行基，于是A=(B,N)；原问题可 改写为 max z=CBXB+CNXN BXB+NXN+XS=b XB，XN，XS0 相应地对偶问题可表示为 min w=Yb YB YS1=CB (2-1

37、7) YN YS2=CN (2-18) Y，YS1,YS20 这里YS=(YS1，YS2)。 清华大学出版社清华大学出版社 74 4.2 对偶问题的基本性质 v(7) 原问题检验数与对偶问题解的关系 当求得原问题的一个解：XB=B-1b,其相应的检验数为 CN CBB-1N 与 CBB-1 现分析这些检验数与对偶问题的解之间的关系：令Y=CBB-1,将 它代入(2-17)式，(2-18)式得 YS1=0, YS2=CN CBB-1N 证毕。 清华大学出版社清华大学出版社 75 4.2 对偶问题的基本性质 v例4 已知线性规划问题 max z=x1+x2 -x1+x2+x32 -2x1+x2-x

38、31 x1,x2,x30 试用对偶理论证明上述线性规划问题无最优解。 清华大学出版社清华大学出版社 76 4.2 对偶问题的基本性质 v上述问题的对偶问题为 min w=2y1+y2 -y1-2y21 y1+ y21 y1- y20 y1，y20 由第1约束条件，可知对偶问题无可行解；原问题虽然有 可行解，但无最优解。 清华大学出版社清华大学出版社 77 4.2 对偶问题的基本性质 v例5 已知线性规划问题 min w=2x1+3x2+5x3+2x4+3x5 x1+x2+2x3+x4+3x54 2x1-x2+3x3+x4+x53 xj0，j=1，2，5 已知其对偶问题的最优解为y1*=4/5，

39、y2*=3/5；z=5。试 用对偶理论找出原问题的最优解 。 清华大学出版社清华大学出版社 78 4.2 对偶问题的基本性质 v例5 已知线性规划问题 解：先写出它的对偶问题 max z=4y1+3y2 y1+2y22 y1-y23 2y1+3y25 y1+y22 3y1+y23 y1，y20 清华大学出版社清华大学出版社 79 4.2 对偶问题的基本性质 v例5 已知线性规划问题 将y1* =4/5,y2* =3/5的值代入约束条件， 得=1/53，=17/55，=7/52 它们为严格不等式；由互补松弛性得 x2*=x3*=x4*=0。 因y1，y20；原问题的两个约束条件应取等式，故有 x

40、1*+3x5*=4，2x1*+x5*=3 求解后得到x1*=1,x5*=1；故原问题的最优解为 X*=(1，0，0，0，1)T；w*=5 清华大学出版社清华大学出版社 80 第5节 对偶问题的经济解释影子价格 v在单纯形法的每步迭代中，目标函数取值z=CBB-1b，和检 验数CN CBB-1N中都有乘子Y=CBB-1，那么Y的经济意义是 什么? 设B是max z=CXAXb，X0的最优基，由(2-12)式可 知 z*=CBB-1b=Y*b 对z求偏导数，得 * B * YBC b z 1 由上式可知，变量yi*的经济意义是在其他条件不变的情况 下，单位资源变化所引起的目标函的最优值的变化。 清

41、华大学出版社清华大学出版社 81 第5节 对偶问题的经济解释 影子价格 v第1章中例1的影价格及其经济解释。 由表1-5可知 cj23000 CBXBbx1x2x3x4x5 2x141001/40 0 x5400-21/21 3x22011/2-1/80 -z-1400-3/2-1/80 y1*=1.5，y2*=0.125，y3*=0。 清华大学出版社清华大学出版社 82 第5节 对偶问题的经济解释 影子价格 v第1章中例1的影价格及其经济解释。 这说明是其他条件不变的情况下，若设备增加一台时，该厂 按最优计划安排生产可多获利1.5元；原材料A增加1kg，可 多获利0.125元；原材料B增加1

42、kg，对获利无影响。 从图2-1可看到，设备增加一台时，代表该约束条件的直线由 移至，相应的最优解由(4，2)变为(4，2.5)，目标函数 z=24+32.5=15.5，即比原来的增大1.5。又若原材料A增 加1kg时，代表该约束方程的直线由移至，相应的最优 解 从 ( 4 ， 2 ) 变 为 ( 4 . 2 5 ， 1 . 8 7 5 ) ， 目 标 函 数 z = 4.25+31.875=14.125。比原来的增加0.125。原材料B增 加1kg时，该约束方程的直线由移至，这时的最优解不 变。 清华大学出版社清华大学出版社 83 第5节 对偶问题的经济解释 影子价格 v第1章中例1的影价格

43、及其经济解释。 清华大学出版社清华大学出版社 84 第5节 对偶问题的经济解释 影子价格 vyi*的值代表对第i种资源的估价影子价格。 这种估价是针对具体工厂的具体产品而存在的一种特殊价 格，称它为“影子价格”。在该厂现有资源和现有生产方 案的条件下，设备的每小时租费为1.5元，1kg原材料A的 出让费为除成本外再附加0.125元，1kg原材料B可按原成 本出让，这时该厂的收入与自己组织生产时获利相等。影 子价格随具体情况而异，在完全市场经济的条件下，当某 种资源的市场价低于影子价格低于影子价格时，企业应买进该资源应买进该资源用于 扩大生产；而当某种资源的市场价高于企业影子价格高于企业影子价格

44、时， 则企业的决策者应把已有资源卖掉把已有资源卖掉。可见影子价格对市场 有调节作用。 清华大学出版社清华大学出版社 85 第6节 对偶单纯形法 v前节讲到原问题与对偶问题的解之间的对应关系时指出： 在单纯形表中进行迭代时，在b列中得到的是原问题的基 可行解，而在检验数行得到的是对偶问题的基解。 v通过逐步迭代，当在检验数行得到对偶问题的解也是基可 行解时，根据性质(2)、(3)可知，已得到最优解。即原问题 与对偶问题都是最优解。 v根据对偶问题的对称性，可以这样考虑：若保持对偶问题 的解是基可行解，即cjCBB-1Pj0，而原问题在非可行解的 基础上，通过逐步迭代达到基可行解，这样也得到了最优

45、 解。其优点是原问题的初始解不一定是基可行解，可从非 基可行解开始迭代。 清华大学出版社清华大学出版社 86 第6节 对偶单纯形法 v设原问题为 max z=CX AX=b X0 又设B是一个基。不失一般性，令B=(P1，P2，Pm)， 它对应的变量为 XB=(x1，x2，,xm)。当非基变量都为零时， 可以得到XB=B-1b。若在B-1b中至少有一个负分量，设(B-1b)i 0，并且在单纯形表的检验数行中的检验数都为非正， 即对偶问题保持可行解，它的各分量是 (1) 对应基变量x1，x2，,xm的检验数是 i=ci zi=ci CBB-1Pj=0，i=1,2,m (2) 对应非基变量xm+1

46、，xn的检验数是 j=cj zj=cj CBB-1Pj0，j=m+1,n 清华大学出版社清华大学出版社 87 第6节 对偶单纯形法 v每次迭代是将基变量中的负分量xl取出，去替换非基变量 中的xk，经基变换，所有检验数仍保持非正所有检验数仍保持非正。从原问题来 看，经过每次迭代，原问题由非可行解往可行解靠近经过每次迭代，原问题由非可行解往可行解靠近。当当 原问题得到可行解时，便得到了最优解。原问题得到可行解时，便得到了最优解。 清华大学出版社清华大学出版社 88 第6节 对偶单纯形法 v对偶单纯形法的计算步骤如下： (1) 根据线性规划问题，列出初始单纯形表。检查b列的数字， 若都为非负，检验

47、数都为非正，则已得到最优解。停止计算。 若检查b列的数字时，至少还有一个负分量，检验数保持非正， 那么进行以下计算。 (2) 确定换出变量。按min(B-1b)i(B-1b)i0(B-1b)l对应的基 变量xi为换出变量 (3) 确定换入变量。在单纯形表中检查xl所在行的各系数 lj(j=1,2,，n)。若所有lj0，则无可行解，停止计算。若存 在lj0 (j=1,2,，n), 计算 lk kk lj lj jj ja zc a a zc 0min 清华大学出版社清华大学出版社 89 第6节 对偶单纯形法 v对偶单纯形法的计算步骤如下： 按规则所对应的列的非基变量xk为换入变量，这样才能保持

48、得到的对偶问题解仍为可行解。 (4) 以lk为主元素，按原单纯形法在表中进行迭代运算，得到 新的计算表。 重复步骤(1)(4)。 清华大学出版社清华大学出版社 90 第6节 对偶单纯形法 v例6 用对偶单纯形法求解 min w=2x1+3x2+4x3 x1+2x2+x33 2x1x2+3x34 x1，x2，x30 解：解：先将此问题化成下列形式，以便得到对偶问题的初 始可行基 max z= 2x1 3x2 4x3 x1 2x2 x3+x4 = 3 2x1+x2 3x3 +x5= 4 xj0，j=1,2,5 清华大学出版社清华大学出版社 91 第6节 对偶单纯形法 v例6的初始单纯形表，见表2-

49、6。 cj -2 -3 -4 0 0 CB XB b x1 x2 x3 x4 x5 0 0 x4 x5 -3 -4 -1 -2 -2 1 -1 -3 1 0 0 1 cj-zj -2 -3 -4 0 0 从表2-6看到，检验数行对应的对偶问题的解是可行解。 因b列数字为负，故需进行迭代运算。 清华大学出版社清华大学出版社 92 第6节 对偶单纯形法 v换出变量的确定： v换入变量的确定：按上述对偶单纯形法计算步骤(3)，即在单 纯形表中检查xl所在行的各系数lj(j=1,2,，n)。若所有 lj0，则无可行解，停止 计算。 按上述对偶单纯形法计算步骤(2)，即按min(B-1b)i(B-1b)

50、i 0(B-1b)l对应的基变量xi为换出变量。计算 min( 3, 4)= 4 故x5为换出变量。 1 2 2 3 4 , 2 2 min 故x1为换入变量。换入、换出变量的所在列、行的交叉处“2” 为主元素。按单纯形法计算步骤进行迭代，得表2-7。 清华大学出版社清华大学出版社 93 第6节 对偶单纯形法 由表 2-7 看出，对偶问题仍是可行解，而 b 列中仍有负分量。 故重复上述迭代步骤，得表 2-8。 清华大学出版社清华大学出版社 94 第6节 对偶单纯形法 表2-8中，b列数字全为非负，检验数全为非正，故问题的最优解为 X*=(11/5，2/5，0，0，0)T 若对应两个约束条件的对

51、偶变量分别为y1和y2，则对偶问题的最优 解为 Y*=(y1*,y2*)=(8/5,1/5) 清华大学出版社清华大学出版社 95 第6节 对偶单纯形法 从以上求解过程可以看到对偶单纯形法有以下优点： l (1) 初始解可以是非可行解，当检验数都为负数时就可以进行基的变 换，这时不需要加入人工变量，因此可以简化计算。 l (2) 当变量多于约束条件，对这样的线性规划问题用对偶单纯形法计 算可以减少计算工作量，因此对变量较少，而约束条件很多对变量较少，而约束条件很多的线性规 划问题，可先将它变换成对偶问题，然后用对偶单纯形法求解。 l (3) 在灵敏度分析及求解整数规划的割平面法中，有时需要用对偶

52、单 纯形法，这样可使问题的处理简化。对偶单纯形法的局限性主要是， 对大多数线性规划问题，很难找到一个初始可行基，因而这种方法在 求解线性规划问题时很少单独应用很少单独应用。 清华大学出版社清华大学出版社 96 第7节 灵敏度分析 v以前讨论线性规划问题时，假定ij，bi, cj都是常数。但实 际上这些系数往往是估计值和预测值。 v如市场条件一变，cj值就会变化；ij往往是因工艺条件的 改变而改变；bi是根据资源投入后的经济效果决定的一种 决策选择。 v因此提出这样两个问题： (1)当这些系数有一个或几个发生变化时，已求得的线性规划问题的 最优解会有什么变化； (2)或者这些系数在什么范围内变化

53、时，线性规划问题的最优解或最 优基不变。 后一个问题将在第8节参数线性规划中讨论。 清华大学出版社清华大学出版社 97 第7节 灵敏度分析 v显然，当线性规划问题中某一个或几个系数发生变化后， 原来已得结果一般会发生变化。当然可以用单纯形法从从 头计算头计算，以便得到新的最优解。这样做很麻烦，而且也 没有必要。因在单纯形法迭代时，每次运算都和基变量 的系数矩阵B有关，因此可以把发生变化的个别系数，经 过一定计算后直接填入最终计算表中，并进行检查和分 析，可按表2-9中的几种情况 进行处理。 清华大学出版社清华大学出版社 98 7.1 资源数量变化的分析 v资源数量变化是指资源中某系数b r发生

54、变化，即 br=br+br。并假设规划问题的其他系数都不变。这样 使最终表中原问题的解相应地变化为 XB=B-1(b+b) v这里b=(0,，br,0,，0)T。只要XB0，因最终表 中检验数不变，故最优基不变，但最优解的值发生了 变化，所以XB为新的最优解。新的最优解的值可允许 变化范围用以下方法确定。 清华大学出版社清华大学出版社 99 7.1 资源数量变化的分析 mr ir r r rmr rir rr r r a a a b ba ba ba bB bBbBbBbBbbB 11 1 11111 0 0 0 0 )( 新的最优解的值可允许变化范围用以下方法确定。 清华大学出版社清华大学出

55、版社 100 7.1 资源数量变化的分析 在最终表中求得的经过变化后的 b 列的所有元素， 要求b i+ a irbr0，i=1,2,m。由此可得 a irbr-bi，i=1,2，m 当 a ir0 时，br-bi/ a ir； 当 a ir0 时，br-bi/ a ir；于是得到 新的最优解的值可允许变化范围用以下方法确定。 0min0max ir ir i i rir ir i i a a b ba a b 清华大学出版社清华大学出版社 101 7.1 资源数量变化的分析 例如求第1章例1中第二个约束条件b2的变化范围。 解：可以利用第1章例1的最终计算表中的数据： cj 2 3 0 0

56、0 CB XB b x1 x2 x3 x4 x5 2 x1 4 1 0 1 1/4 0 0 x5 4 0 0 -2 1/2 1 3 x2 2 0 1 1/2 -1/8 0 -z -14 0 0 -3/2 -1/8 0 清华大学出版社清华大学出版社 102 7.1 资源数量变化的分析 可计算b2： 0 0 0 8/1 2/1 4/1 2 4 4 0 0 08/12/1 12/12 04/10 2 4 4 0 0 2 22 11 b bbBbB 由上式，可得 b24/0.25=16，b24/0.5=8，b22/0.125=16。所以b2的 变化范围是8，16；显然原b2 =16，加它的变化范围后，

57、 b2的变化范围是8，32。 清华大学出版社清华大学出版社 103 7.1 资源数量变化的分析 2 8 0 0 0 4 0125. 05 . 0 15 . 02 025. 00 1 bB 例7 从表1-5得知第1章例1中，每设备台时的影子价格为1.5元， 若该厂又从其他处抽调4台时用于生产产品，。求这时该厂 生产产品，的最优方案。 解：先计算B-1b,将结果反映到最终表1-5中，得表2-10。 cj 2 3 0 0 0 CB XB b x1 x2 x3 x4 x5 2 0 3 x1 x5 x2 4+0 4-8 2+2 1 0 0 0 0 1 0 -2 0.5 0.25 0.5 0.125 0

58、1 0 cj-zj 0 0 -1.5 -0.125 0 清华大学出版社清华大学出版社 104 7.1 资源数量变化的分析 由于表2-10中b列有负数，故用对偶单纯形法求新的最优解。计 算结果见表2-11。 cj 2 3 0 0 0 CB XB b x1 x2 x3 x4 x5 2 0 3 x1 x3 x2 4 2 3 1 0 0 0 0 1 0 1 0 0.25 -0.25 0 0 -0.5 0.25 cj-zj 0 0 0 -0.5 -0.75 即该厂最优生产方案应改为生产4件产品，生产3件产品， 获利 z*=42+33=17(元) 从表2.11 看出x3=2，即设备还有2小时未被利用。 清

59、华大学出版社清华大学出版社 105 7.2 目标函数中价值系数cj的变化分析 v可以分别就cj是对应的非基变量和基变量两种情况来讨论。 (1) 若cj是非基变量xj的系数，这时它在计算表中所对应的检 验数是 j=cjCBB-1Pj 或 当cj变化cj后，要保证最终表中这个检验数仍小于或等于零， 即 j=cjCBB-1Pj0 那么cj+cjYPj，即cj的值必须小于或等于YPjcj，才可以满 足原最优解条件。这就可以确定cj的范围了。 m i iijjj yac 1 清华大学出版社清华大学出版社 106 7.2 标函数中价值系数cj的变化分析 v可以分别就cj是对应的非基变量和基变量两种情况来讨

60、论。 (2) 若cr是基变量xr的系数。因crCB，当cr变化cr时，就引起 CB的变化，这时 (CB+CB)B-1A=CBB-1A+(0，cr，0)B-1A =CBB-1A+cr(r1,r2,，rn) 可见，当cr变化cr后，最终表中的检验数是 j=cjCBB-1Acr rj，j=1,2,，n 若要求原最优解不变，即必须满足j0。于是得到 a 清华大学出版社清华大学出版社 107 7.2 标函数中价值系数cj的变化分析 nj a ca a ca rj j rrj rj j rrj , 2 , 1 ;, 0;, 0 当当 cr可变化的范围是 0min0max rj rj j j rrj rj