大连海事大学物流运筹学全册配套精品完整课件3.ppt

1、大连海事大学物流运筹学全册大连海事大学物流运筹学全册 配套精品完整课件配套精品完整课件 2 1 1 线性规划问题及其数学模型线性规划问题及其数学模型 1.1 1.1 问题的提出问题的提出 eg.1 生产计划问题 问：产品、各生产多少件， 使利润最大？ 限制 设备台时128台时 材料A4016kg 材料B0412kg 利润23 分析： 设：产品生产x1件， 产品生产x2件。 这里z为利润函数， max z:表示求z的最大值。 目标函数： max z = 2x1 + 3x2 约束条件： 1x1 + 2x2 8 4x1 16 4x2 12 x1，x2 0 3 eg.2 污水处理问题 环保要求河水含污

2、低于2，河水可自身净化20%。 问：化工厂1、2每天各处理多少污水，使总费用最少？ 分析： 化工厂1处理污水x1万m3, 化工厂2处理污水x2万m3。 min z = 1000 x1 + 800 x2 (2 - x1)/500 2/1000 (1 - 0.2)(2 - x1) + 1.4 - x2/(500 + 200) 2/1000 x1 2 x2 1.4 x1，x2 0 这里min z:表示求z的最小值。 200万m3 500万m3 2万m3 1.4万m3 化工厂1 化工厂21000元/万m3 800元/万m3 4 线性规划的数学模型：线性规划的数学模型： max (min)z = c1x

3、1 + c2x2 + + cnxn a11x1 + a12x2 + + a1nxn (=, ) b1 a21x1 + a22x2 + + a2nxn (=, ) b2 am1x1 + am2x2 + + amnxn (=, ) bm x1，x2，xn 0 5 说明： (1)决策变量：x1，x2，xn 。 一组决策变量表示为问题的一个方案； (2)目标函数：max(min)z z为决策变量的线性函数; (3)约束条件 一组线性不等式。 cj为价值系数, bi为资源， aij为技术系数(i=1,m;j=1,n) . 6 1.2 1.2 图解法图解法 eg.eg.33用图解法求用图解法求eg.eg.

4、1 1。 max max z z = 2x2x1 1 + + 3x3x2 2 1x 1x1 1 + + 2x2x2 2 8 8 4x 4x1 1 16 16 4x4x2 2 12 12 x x1 1，x x2 2 0 0 解： (1)建立x x1 1 - - x x2 2坐标； x2 x1 (2)约束条件的几何表示； Q1 Q2 Q3Q4 (3)目标函数的几何表示； * z z = 2x2x1 1 + + 3x3x2 2 o 4 3 zxx 3 1 3 2 12 7 首先取z = 0，然后，使z逐 渐增大，直至找到最优解所对 应的点。 * 可见，在Q2点z取到最大值。 因此， Q2点所对应的解

5、为最优解。 Q2点坐标为(4，2)。 即: x1 = 4，x2 = 2 由此求得最优解：x x1 1* * = 4 x4 x2 2* * = 2 2 最大值：maxmax z z = z z* * = 2x2x1 1 + + 3x3x2 2 = 14(14(元元) ) x2 x1 Q1 Q2(4,2) Q3Q4 * 4 3 8 讨论： (1)唯一最优解 maxmax z z = z z* *时，解唯一，如上例。 (2)无穷多最优解 eg.4 对eg.1，若目标函数 z z = 2x2x1 1 + + 4x4x2 2，此时表示 目标函数的直线与表示 条件的直线平行， 最优点在线段Q3Q2上。 即

6、存在无穷多最优解。 x2 x1 Q1 Q2(4,2) Q3(2,3)Q4 o 4 3 * 9 (3)无界解 eg.5 max z = 2x1 + 3x2 4x1 16 x1，x2 0 则x2 ，z 。 即存在无界解。 在实际问题中，可能 是缺少约束条件。 o 2 2 41 x 2 x 10 (4)无可行解 eg.6 max z = 2x1 + 3x2 2x1 + 4x2 8 x1 + x2 1 x1，x2 0 无公共部分，无可行域。 即无可行解。 在实际问题中，可能是关系错。 1 1 2 4 x1 x2 11 1.3 1.3 线性规划的标准型线性规划的标准型 1、标准型 max z = c1x

7、1 + c2x2 + + cnxn a11x1 + a12x2 + + a1nxn = b1 a21x1 + a22x2 + + a2nxn = b2 am1x1 + am2x2 + + amnxn = bm x1，x2，xn 0 njx mibxa xcz j i n j jij n j jj , 10 , 1 max 1 1 ， 简记： 12 用向量表示 njx bxp ts CXz j n j jj , 1, 0 . max 1 T m j T mjjjj n T n bbbb xaaap cccC xxxX ) ( :) ( ) ( ) (: 21 21 21 21 的系数列向量 其中

8、 13 用矩阵描述为： max z = CX AX = b X 0 其中: X = (x1,x2,xn)T C = (c1,c2,cn) b = (b1,b2,bm)T 为系数矩阵 21 22221 11211 mnmm n n aaa aaa aaa A 14 2 2、标准型的化法标准型的化法 (1) (1)minmax min zminmax min z = cxcx = -max(-z)-max(-z) max(-z) max(-z) = -min z-min z = -cx-cx 令令z z = -z -z 则则max zmax z = -cx-cx (2)(2)不等式不等式(，) 对

9、于对于“”情况：在情况：在“”左边加上一个松弛变量（非左边加上一个松弛变量（非 负）负），变为等式；变为等式； 对于对于“”情况：在情况：在“”左边减去一个剩余变量（非左边减去一个剩余变量（非 负），变为等式。负），变为等式。 注意：松弛变量、剩余变量在目标函数中的价值系数为注意：松弛变量、剩余变量在目标函数中的价值系数为0 0。 (3)(3)无约束变量无约束变量 令令x xk k = x xk k - - x xk k”，x xk k,x,xk k” 0 0，代入即可。代入即可。 15 eg.eg.77将下述问题化为标准型将下述问题化为标准型 min zmin z = -x-x1 1+2x+

10、2x2 2-3x-3x3 3 x x1 1+ x+ x2 2+ x+ x3 3 7 7 x x1 1- x- x2 2+ x+ x3 3 2 2 -3x-3x1 1+ x+ x2 2+2x+2x3 3 = 5 5 x x1 1,x,x2 2 0 0，x x3 3无约束无约束 解：令解：令x x3 3 = x x3 3-x-x3 3”，x x3 3,x,x3 3” 0 0； 式加上一个松弛变量式加上一个松弛变量x x4 4；式减去一个剩余变量式减去一个剩余变量x x5 5； 令令z z = -z-z max zmax z = x x1 1- - 2x2x2 2 + + 3(x3(x3 3 - -

11、 x x3 3”) ) + + 0 x0 x4 4 + + 0 x0 x5 5 x x1 1 + + x x2 2 + (x+ (x3 3 - - x x3 3”) ) + + x x4 4 = 7 7 x x1 1 - - x x2 2 + (x+ (x3 3 - - x x3 3”) ) - - x x5 5 = 2 2 -3x -3x1 1 + + x x2 2 + + 2(x2(x3 3 - - x x3 3”) ) = 5 5 x x1 1,x,x2 2,x,x3 3,x,x3 3”,x,x4 4,x,x5 5 0 0 16 1.4 1.4 线性规划解的概念线性规划解的概念 设线性规

12、划为 maxmax z z = CX CX AX AX = b b X X 0 0 A A为为m m n n矩阵矩阵, , n n m, Rankm, Rank A A = m (Am (A为行满秩矩阵）为行满秩矩阵） 1 1、可行解：满足条件、可行解：满足条件、的的X X； 2 2、最优解：满足条件的可行解；、最优解：满足条件的可行解； 3 3、基：取、基：取B B为为A A中的中的m m m m子矩阵，子矩阵，RankRank B B = m m，则称则称B B为线性为线性 规规 划问题的一个基。划问题的一个基。 取取B B = (p(p1 1,p,p2 2, ,p,pm m) p) pj

13、 j = (a(a1j 1j,a ,a2j 2j, ,a ,amj mj) )T T 则称则称x x1 1,x,x2 2, ,x,xm m为基变量，其它为非基变量。为基变量，其它为非基变量。 17 4 4、基解：取、基解：取B B = (p(p1 1,p,p2 2, ,p,pm m) ) a a11 11, ,a ,a1m 1m x x1 1 a a1m+1 1m+1, ,a ,a1n 1n x xm+1 m+1 b b1 1 + + = a am1 m1, ,a ,amm mm x xm m a amm+1 mm+1, ,a ,amn mn x xn n b bm m 基基 基变量基变量 非

14、基非基 非基变量非基变量 令令 x xm+1 m+1 = = x xn n = 0 ( 0 (非基变量为非基变量为0)0) 则则 BXBXB B = b b )!( ! ! mnm n C m n 基解个数 T mn m T mB xxxX xxxbBX )0 , 0,( ),( m )0()0( 2 )0( 1 )0()0( 2 )0( 1 1 个 个 基解： 18 5、基可行解 满足式要求的基解。 如右图所示，各边交点O,QO,Q1 1,Q,Q2 2,Q,Q3 3,Q,Q4 4 均为基可行解；而其延长线的交点Q5为 基解，但不是基可行解。 O(0,0)O(0,0) Q Q1 1(4,0)(

15、4,0) Q Q2 2(4,2)(4,2) Q Q4 4(0,3)(0,3)Q Q3 3(2,3)(2,3)Q Q5 5(4,3)(4,3) 6、可行基 基可行解对应的B为可行基。 可行解可行解 基可行解基可行解非可行解非可行解 基解基解 19 2 2 线性规划问题的几何意义线性规划问题的几何意义 2.1 2.1 基本概念基本概念 1 1、凸集：设、凸集：设K K为为E En n(n(n维欧式空间维欧式空间) )的一点集，的一点集，X X(1) (1) K K，X X(2) (2) K K。 若若XX(1) (1)+(1-)X +(1-)X(2) (2) K K，则称则称K K为凸集。（为凸集

16、。（0 01 1） 非凸集 X X(1) (1) X X(1) (1) X X(2) (2) X X(2) (2) 凸集 X X(1) (1) X X(2) (2) X X(2) (2) X X(1) (1) 20 2 2、顶点：、顶点：X XK K，X X(1) (1) K K，X X(2) (2) K (K (任意两点任意两点) )。若。若X X不能用不能用 XX(1) (1)+(1-)X +(1-)X(2) (2)表示，则称 表示，则称X X为为K K的一个顶点。的一个顶点。(0(01)1) 注：顶点所对应的解是基可行解。注：顶点所对应的解是基可行解。 3 3、凸组合：设、凸组合：设X

17、X(i) (i) E En n，若存在若存在0 0i i1 1，i i = 1,2,1,2,k,k， 使使 , ,则称则称X X为为X X(i) (i)(i=1,2, (i=1,2,k),k)的凸组合。的凸组合。 1 k 1i i k 1i ) i ( iX X 2.2 2.2 基本定理基本定理 1 1、定理、定理1 1 若线性规划存在可行域，则若线性规划存在可行域，则: : 可行域可行域 D D = X|AXX|AX = b,Xb,X 00为凸集。为凸集。 21 证明：证明： 设设 X X(1) (1)=( =(x1 1(1) (1), ,x2 2(1)(1), , ,xn n(1)(1)

18、)T T D D； X X(2) (2)=( =(x1(2) (2), ,x2 2(2)(2), , ,xn n(2)(2) )T T D D； (X (X(1) (1) X X(2)(2) ) 有有 AXAX(1) (1) = b b， ， AX AX(2) (2) = b b 令令 X X = XX(1) (1) + + (1 (1 - - )X)X(2) (2) (0(0 0 10 1 0 0 X X 0 0， 即即D D为凸集为凸集 2、定理2 线性规划的基可行解对应于可行域的顶点。 3、定理3 若线性规划有解，则一定存在基可行解 为最优解。 22 3 3 单纯形法单纯形法 基本思路：

19、基本思路：从可行域的一个顶点到另一个顶点迭代求最优解。 3.1 3.1 初始基可行解的确定初始基可行解的确定 1、松弛基（松弛变量对应的B） eg.8 max z = x1 + 3x2 x1 + 2x2 3 2x1 + 3x2 4 x1,x2 0 max z = x1 + 3x2 + 0 x3 + 0 x4 x1 + 2x2 + x3 = 3 2x1 + 3x2 + x4 = 4 x1,x2,x3,x4 0 化标准型 取x3、x4为基变量,令非基变量x1= x2=0 初始基可行解：X(0) = (0 0 3 4)T B , 1 0 3 2 0 1 2 1 434321 ppppppA 则系数矩

20、阵 23 2、观察法 eg.9 max z = x1 + 3x2 + 2x3 + x4 x1 + 2x2 + 3x3 = 3 3x2 + x3 + x4 = 4 x1,x2,x3,x4 0 选 XB = (x1 x4)T 令x2 = x3 = 0 则 初始基可行解：X(0) = (3 0 0 4)T B , 1 1 3 0 0 3 2 1 : 414321 ppppppA 则 解 24 3、人工基 eg.10 max z = x1 + 2x2 + 3x3 x1 + 3x2 + 2x3 = 3 2x1 + x2 + x3 = 4 x1,x2,x3 0 分析： A = 1 3 2 2 1 1 找不

21、到单位矩阵基 引入人工变量为初始基变量（2个） 25 3.2 3.2 最优性的检验与解的判别最优性的检验与解的判别 mnjx mibxxa xcxcz j n j iinjij m i inin n j jj , 1 0 , 1 max 1 11 对于 代入目标函数 为非基变量 可行为基变量设 , 1, , 1, 1 n j jijiin j in xabx njx mix 26 则 n j jj n j jjj n j m i jijinj m i iin n j m i n j jijiinjj xZ xzcZ xaccbc xabcxcz 1 0 1 0 111 111 )( )( )(

22、 m i ijinjjjj m i iin aczzcbcZ 11 0 , , 其中 27 解的判别： 1. 若 ，则此时的基可行解为最优解； 2. 若存在某个非基变量 的检验数 ，且 ， 则该线性规划问题具有无界解（或称无最优解）； 3. 若所有 ，又，对于某个非基变量 有 ， 则该线性规划问题具有无穷多最优解。 . .的检验数为称 jj x k x0 k nj j , 1, 0 0 k p 0 j 0 k k x 28 为主元 出基行对应的变量则 若 、出基变量 0minmin0 2 lk l lk l ik ik i i i i ik ik i i a xl a b a a b a a

23、b 为入基变量。则，若 、入基变量 kkj j x 0max 1 3.3 3.3 基变换基变换 29 3.4 3.4 旋转运算（消元运算）旋转运算（消元运算） a1k 0 al-1k 0 pk = （alk） （1） al+1k 0 amk 0 得到基可行解，重复3.23.4， 求出最优解。 30 3.5 3.5 单纯形表单纯形表 展开如下： a11x1 + a12x2 + + a1nxn + xn+1 = b1 - cn+1 a21x1 + a22x2 + + a2nxn + xn+2 = b2 - cn+2 am1x1 + am2x2 + + amnxn + xn+m = bm - cn+

24、m c1x1 + c2x2 + + cnxn + cn+1xn+1 + + cn+mxn+m - z = 0 1x1 + 2x2 + + nxn + 0 xn+1 + + 0 xn+m - z = Z0 mn, 2 , 1j0 x bxxa xczmax j iin n 1j jij mn 1j jj ， 设 31 建立单纯形表 cBxBb c1cncn+1cn+m x1xnxn+1xn+m cn+1xn+1b1a11a1n101 cn+mxn+mbmam1amn01m -z -z01 n 00j eg.11 用单纯形法求解 max z = x1 + 3x2 x1 + 2x2 8 4x1 16

25、 4x2 12 x1,x2 0 32 解：标准化，建立单纯形表 引入松弛变量x3，x4，x5为初始基变量 max z = x1 + 3x2 + 0 x3 + 0 x4 + 0 x5 x1 + 2x2 + x3 = 8 4x1 + x4 = 16 4x2 + x5 = 12 x1,x2,x3,x4,x5 0 cBxBbx1x2x3x4x5 13000 cBxBbx1x2x3x4x5 0 x3812100 0 x41640010 0 x51204001 此时的解： x(0) = (0 0 8 16 12)T z(0) = 0 33 解的判别 1=1 2=3 0 x(0)非最优解 基变换 max1,

26、2 = 3 = 2 x2入基 min8/2,-,12/4 = 12/4 x5出基 13000 cBxBbx1x2x3x4x5 0 x3812100 0 x41640010 0 x51204001 13000 cBxBbx1x2x3x4x5 0 x38121008/2 0 x41640010- 0 x5120400112/4 13000 34 此时的解： x(1)=(0 3 2 16 0)T z(1)=9 x(1)非最优 x1入基 x3出基 0 x321010-1/22/1 0 x4164001016/4 3x2301001/4- 1000-3/4 1x121010-1/2 0 x4800-41

27、2 3x2301001/4 00-10-1/4 13000 此时的解： x(2)=(2 3 0 8 0)T z(2)=11 x(2)为最优解 即： 最优解：x* = (2 3 0 8 0)T 最大值：z* = 11 35 X(0)=(0 0 8 16 12)T O(0,0) X(1)=(0 3 2 16 0)T Q4(0,3) X(2)=(2 3 0 8 0)T Q3(2,3) x2 x1 Q1 Q2(4,2) Q3(2,3)Q4 * O(0,0) 36 4 4 单纯形法的进一步讨论单纯形法的进一步讨论 4.1 4.1 人工变量法人工变量法 1、大M法（M为很大的正数） 法则：对于max问题，

28、人工变量在目标函数中的价值系数为-M； 对于min问题，人工变量在目标函数中的价值系数为M。 eg.12 min z = x1 + 5x2 + 0 x3+0 x4 2x1 + 3x2 + x3 = 6 2x1 + x2 x4 = 1 x1,x2,x3, x4 0 解：min z = x1 + 5x2 + 0 x3 + 0 x4 +Mx5 ：x5为人工变量 2x1 + 3x2 + x3 = 6 2x1 + x2 x4 + x5 = 1 x1,x2,x3,x4,x5 0 列单纯形表求解。 37 min z = x1 + 5x2 + 0 x3 + 0 x4 +Mx5 2x1 + 3x2 + x3 =

29、 6 2x1 + x2 x4 + x5 = 1 x1,x2,x3,x4,x5 0 对于min问题，若 minj0中，选下标小的非基变量入基； 对相同的最小比值，选下标小的基变量出基。 ., , , 2 , 10 ,min min3 得问题的最优解时 数满足当所有非基变量的检验问题对于 问题最优解的判别、 njzc jjj 第二章 j与i的计算同max问题。 46 习题 P45，1.4分别用图解法和单纯形法求解下列线性规划, 并指出单纯形法迭代的每一步相当于图形上的哪一个 顶点？ 0, 2426 1553 2max) 1 ( 21 21 21 21 xx xx xx xxz 0, 1823 12

30、2 4 52max)2( 21 21 2 1 21 xx xx x x xxz 47 对偶理论与灵敏度分析对偶理论与灵敏度分析 1 1 单纯形法的矩阵描述单纯形法的矩阵描述 设max z = CX AX = b X 0 A为mn阶矩阵 RankA=m ,取B为可行基, N为非基， NB N B CCCNBA X X X , , 0, max NB NB NNBB XX bNXBX XCXCz 48 bBC bBNBI BN 1 11 - 1 0 0 : 矩阵单纯形表 0 zXCXC bNXBX NNBB NB bBCzXNBCCX bBNXBBXB BNBNB NB 11 111 )(0 bB

31、CzXX bBNXBIX BNNB NB 1 11 0 49 bBCzXX bBNXBIX BNNB NB 1 11 0 NBCC bBCz bBX X BNN B B N 1 1 1 , , 0 得 令 ., ,0 ! 出则最优解直接由上式求若能找到最优 为最优基的使注 B B N bBCz bB X B 1 1 0 目标函数 基可行解 50 求解步骤： .42 .,. 4 . , )( )( 0)( )( )( min ,)(0)(max . 3 ., 0. 2 ,. 1 1 1 1 1 1 1 1 1 步直到求出结果重复 的求出此得到新的 出基行对应的则 若 入基则若 基变换 否则转下一

32、步则得最优解若 求取可行基 BBB xl PB bB PB PB bB x NBCC BB l lk l ik ik i i kkNjN j BNN 51 32利润 12kg40材料B 16kg04材料A 8台时 21设备台时 限制 2 2 对偶问题的提出对偶问题的提出 eg.1 制定生产计划 M1: max z = 2x1 + 3x2 1x1 + 2x2 8 4x1 16 4x2 12 x1，x2 0 52 现在出租，设y1为设备单位台时的租金 y2,y3为材料A、B转让附加费(kg-1) 则M2为M1的对偶问题， 反之亦然。 M2: min w = 8y1 + 16y2 + 12y3 y1

33、 + 4y2 2 2y1 + 4y3 3 y1,y2,y3 0 32利润 12kg40材料B 16kg04材料A 8台时 21设备台时 限制 0, 124 16 4 82 32max 21 2 1 21 211 xx x x xx xxzM 53 一般的，原问题：max z = CX AX b X 0 对偶问题：min w = Yb YA C Y 0 比较： max z min w 决策变量为n个 约束条件为n个 约束条件为m个 决策变量为m个 “” “” 54 3 3 对偶问题的化法对偶问题的化法 1、典型情况 eg.2 max z = x1 + 2x2 + x3 2x1 + x2 6 2x

34、2 + x3 8 x1,x2,x3 0 对偶：min w = 6y1 + 8y2 2y1 1 y1 + 2y2 2 y2 1 y1,y2 0 55 2、含等式的情况 eg.3 max z = x1 + 2x2 + 4x3 2x1 + x2 + 3x3 = 3 x1 + 2x2 + 5x3 4 x1,x2,x3 0 对偶：min w = 3y1-3y1”+4y2 2y1-2y1”+ y2 1 y1- y1”+2y2 2 3y1-3y1”+5y2 4 y1,y1”,y2 0 令y1=y1-y1”,则： min w = 3y1+4y2 2y1 + y2 1 y1 +2y2 2 3y1 +5y2 4

35、y2 0，y1无约束 一般，原问题第i个约束取等式，对偶问题第i个变量无约束。 2x1 + x2 + 3x3 3 -2x1 - x2 - 3x3 -3 56 3、含“”的max问题 eg.4 max z = x1 + 2x2 + 4x3 2x1 + x2 + 3x3 3 x1 + 2x2 + 5x3 4 x1,x2,x3 0 对偶：min w = -3y1 + 4y2 -2y1 + y2 1 -y1 + 2y2 2 -3y1 + 5y2 4 y1,y2 0 令y1 = -y1，则： min w = 3y1 + 4y2 2y1 + y2 1 y1 + 2y2 2 3y1 + 5y2 4 y1 0

36、,y2 0 -2x1 - x2 - 3x3 -3 57 一般: max问题第i个约束取“”，则min问题第i个变量 0 ； min问题第i个约束取“”，则max问题第i个变量 0 ； 原问题第i个约束取等式，对偶问题第i个变量 无约束； max问题第j个变量 0 ,则min问题第j个约束取“” ； min问题第j个变量 0 ，则max问题第j个约束取“” ； 原问题第j个变量无约束，对偶问题第j个约束取等式。 58 eg.5 min z = 2x1 + 3x2 - 5x3 + x4 x1 + x2 - 3x3 + x4 5 2x1 + 2x3 - x4 4 x2 + x3 + x4 = 6 x

37、1 0,x2,x3 0,x4无约束 对偶：max w = 5y1 + 4y2 + 6y3 y1 + y2 2 y1 + y3 3 -3y1 + 2y2 + y3 -5 y1 - y2 + y3 = 1 y1 0,y2 0,y3无约束 59 4 4 对偶问题的性质对偶问题的性质 1、对称性 对偶问题的对偶为原问题. 0 )max( 0; ,min)max( Y CYA Ybw YCYACYA Ybww 即 0 )min( X bAX CXw 0 , ,min 0 , ,max YCYAYbw XbAXCXz 60 0 )min( X bAX CXw 证毕 令 0 max maxmax)min(

38、X bAX CXz wz CXwww 61 ., : 的可行解分别为原问题和对问题设 证明 YX XCXAYCAYCYA bYXAYbXAbAX 证毕 bYXC bYXAYXC bYXC YX , . 2 则存在为对偶问题的可行解为原问题的可行解设 弱对偶性 62 推论： (1) max问题任一可解的目标值为min问题目标值的一个下界； (2) min问题任一可解的目标值为max问题目标值的一个上界。 3、无界性 若原问题(对偶问题)为无界解，则对偶问题(原问题)为 无可行解。 注：该性质的逆不存在。若原(对偶)问题为无可行解，对偶( 原问题)问题或为无界解，或为无可行解。 63 4、最优性

39、设X*，Y*分别为原问题和对偶问题可行解，当 CX*=Y*b时， X*，Y*分别为最优解。 证毕 为最优解 即 为最优解 即 由弱对偶性 题的任一可行解分别为原问题和对偶问设 证明 * )2( ) 1 ( ., : * * * Y bYbYbYCXbY X CXXCCXbYXC YX 64 5、对偶定理 若原问题有最优解，那么对偶问题也有最优解， 且目标值相等。 *1 1 * 1* 1* 1* 11 * 0 )( :, , 0 . : wbYbBC bB CCCXz bBX bBCbYwY BCYCAY CABCABCC X BNB B B BB 则其目标值为因原问题最优解 则为对偶问题的可行

40、解若 其中 全部检验数可表示为 则其对应的基矩阵存在为原问题的最优解设 证明 65 Y*为对偶问题的最优解，且原问题和对偶问题 的目标值相等。 证毕 6、松弛性 若X*，Y*分别为原问题及对偶问题的可行解， 那么Ys*X*=0，Y*Xs*=0，当且仅当X*，Y*分别为 最优解。 证明： 0, 0max : S S S XX bXAX XCXz 设原问题为 0, 0min : S S S YY CYYA YYbw 设对偶问题为 66 0, 0max S S S XX bXAX XCXz 0, 0min S S S YY CYYA YYbw XYYAXXYYACXz SS )( SS YXYAXX

41、AXYYbw)( 将b,Cb,C分别代入目标函数： ;, ,0, 0, * * 为最优解 时当为可行解若 YX zwXYXYYX SS 证毕 必有 则分别为最优解若另一方面 0 , 0 , * * SS XYXY zwYX 67 T SmSSS T n xxxX xxxX ) ( ) ( * 2 * 1 * * 2 * 1 * ) ( ) ( * 2 * 1 * * 2 * 1 * snSSS m yyyY yyyY 其中： 用分量表示： mixy njxy Sii jSj , 2 , 1 , 0 ;, 2 , 1 , 0 * * 68 7、检验数与解的关系 (1)原问题非最优检验数的负值为对

42、偶问题的一个基解。 (2)原问题最优检验数的负值为对偶问题的最优解。 分析：max z = CX + 0Xs = (C 0)(X Xs)T AX + Xs = b X,Xs 0 min w = Yb + YS0 YA - Ys = C Y,Ys 0 检验数： = (C 0)- CBB-1(A I) = (C- CBB-1A - CBB-1) = (c s) c = C - CBB-1A X对应的检验数 s = - CBB-1 Xs对应的检验数 69 eg.6 已知：min w = 20y1 + 20y2 的最优解为y1*=1.2,y2*=0.2 -ys1 y1 + 2y2 1 试用松弛性求对偶

43、 -ys2 2y1 + y2 2 问题的最优解。 -ys3 2y1 + 3y2 3 -ys4 3y1 + 2y2 4 y1,y2 0 解：对偶问题 max z = x1 + 2x2 + 3x3 + 4x4 x1 + 2x2 + 2x3 + 3x4 20 +xs1 2x1 + x2 + 3x3 + 2x4 20 +xs2 x1,x2,x3,x4 0 y1*xs1* = 0 y2*xs2* = 0 ys1*x1* = 0 ys2*x2* = 0 ys3*x3* = 0 ys4*x4* = 0 70 y1*=1.2,y2*0.2 0 xs1* = xs2* = 0 由 y1* + 2y2* = 1.

44、6 1 ys1* 0 x1* = 0 由 2y1* + y2* = 2.6 2 ys2* 0 x2* = 0 由 2y1* + 3y2* = 3 =右边 ys3* = 0 x3*待定 由 3y1* + 2y2* = 4 =右边 ys4* = 0 x4*待定 有 2x3* + 3x4* = 20 3x3* + 2x4* = 20 x3* = 4 x4* = 4 最优解：x1* = 0 x2* = 0 x3* = 4 x4* = 4 xs1* = 0 xs2* = 0 最大值：z* = 28 = w* 71 5 5 对偶问题的经济含义对偶问题的经济含义影子价格影子价格 最优情况：z* = w* =

45、 b1y1* + + biyi* + + bmym* 的影子价格为称 i * i * ib z byy i * x2 x1 Q2 eg.7 max z = 2x1 + 3x2 x1 + 2x2 8 4x1 16 4x2 12 x1,x2 0 b1： 8 9 Q2(4，2.5) z* = 15.5 z* = z*- z* = 3/2 = y1* b2：16 17 Q2”(4.25，1.875) z*” = 14.125 z* = z*”- z* = 1/8 = y2* b3：12 13 z* = 0 = y3* Q2 Q2” 72 6 6 对偶单纯形法对偶单纯形法 单纯形法：由 XB = B-1

46、b 0，使j 0，j = 1,m 对偶单纯形法：由j 0(j= 1,n)，使XB = B-1b 0 步骤：步骤：(1)保持j 0，j= 1,n，确定XB，建立计算表格 ； (2)判别XB = B-1b 0是否成立？ 若成立，XB为最优基变量； 若不成立，转(3)； 73 (4)消元运算，得到新的XB。 (3)基变换 出基变量， 出基；，则若 llii i xmibbb, 10min 入基变量， 入基。则若 k a lj a j xa lk k lj j 0min 重复（2）-（4）步，求出结果。 74 eg.8 用对偶单纯形法求解 min w = 2x1 + 3x2 + 4x3 x1 + 2x

47、2 + x3 1 2x1 - x2 + 3x3 4 x1,x2,x3 0 解：max z = -2x1 - 3x2 - 4x3 + 0 x4 + 0 x5 - x1 - 2x2 - x3 + x4 = -1 -2x1 + x2 - 3x3 + x5 = -4 x1,x2,x3,x4,x5 0 75 -2-3-400 CBXBbx1x2x3x4X5 0 x4-1 0 x5-4 出出出 x4,x5 0 最优 最优解：最优解：x1* = 2，x2* = 0，x3* = 0，x4* = 1，x5* = 0 目标值：目标值：w* = -z* = 4 76 7 7 灵敏度分析灵敏度分析 njpBCc AB

48、CC NBCC jBjj B BNN , 2 , 1, 0 0 0 : 1 1 1 或 或 最优性条件 分析 变化对最优解的影响。 j , iji acb 0 : 1 bBX B 可行性条件 77 的变化资源 i b 1 . 7 T i T mi iii b bbbbb bbb bbb )0b 0 0( ) ( 21 bBbBbbBbBX B 1111 )( . ., 0 11 这里用到可行性条件 保持问题的最优性不变的变化范围求出 由 i b bBbB 78 例1 已知下述问题的最优解及最优单纯形表, 0, 124 164 82 00032max 54321 52 41 321 54321

49、xxxxx xx xx xxx xxxxxz ., ) 1 2 使最优基不变的变化范围求 b . 4 )2 1 时的最优解求b 79 最优单纯形表如下: 0-1/8-3/200 0-1/81/21023 11/2-20040 01/400142 00032 b B X B C 5 x 4 x 3 x 2 x 1 x 1 x 5 x 2 x 14 Z)4 0 0 2 4(, * T X此时 80 222 16 1) :bbb解 08/12/1 12/12 04/10 1 B 2 4 4 12 16 8 08/12/1 12/12 04/10 1* bBX B 由最优单纯形表得: 81 )(0 1

50、 2 bbBb 22 111 8/1 2/1 4/1 2 4 4 0 0 08/12/1 12/12 04/10 2 4 4 )( bb bBbBbbB 0 0 0 8/2 2/4 4/4 2 2 2 b b b 08/2 02/4 04/4 2 2 2 b b b . 168 2 最优基不变 b 82 TT bb)0 0 4()0 0 ( )2 1 4 4 4 2 8 0 2 4 4 0 0 4 08/12/1 12/12 04/10 2 4 4 )( 111 bBbBbbB 不可行! 用对偶单纯形法计算 83 -3/4-1/2000 1/400103 x2 3 -1/2-1/41002 x