清华大学运筹学完整PPT课件

1、1 eg.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万m3500万m32万m31.4万m3化工厂1化工厂21000元/万m3800元/万m3第1页/共211页2线性规划的数学模型： max

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

3、eg.33用图解法求eg.eg.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坐标；x2x1 (2)约束条件的几何表示； Q1Q2Q3Q4 (3)目标函数的几何表示； * z z = 2x2x1 1 + + 3x3x2 2 o43zxx313212第4页/共211页5 首先取z = 0，然后，使z逐渐增大，直至找到最优解所对应的点。* 可见，在Q2点z取到最大值。 因此，

4、 Q2点所对应的解为最优解。 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(元) )x2x1Q1Q2(4,2)Q3Q4*43第5页/共211页6讨论： (1)唯一最优解 maxmax z z = z z* *时，解唯一，如上例。 (2)无穷多最优解 eg.4 对eg.1，若目标函数 z z = 2x2x1 1 + + 4x4x2 2，此时表示 目标函数的直线与表示 条件的直线平行， 最优点在线段Q

5、3Q2上。 即存在无穷多最优解。x2x1Q1 Q2(4,2)Q3(2,3)Q4o43*第6页/共211页7 (3)无界解 eg.5 max z = 2x1 + 3x2 4x1 16 x1，x2 0 则x2 ，z 。 即存在无界解。 在实际问题中，可能 是缺少约束条件。o2241x2x第7页/共211页8(4)无可行解 eg.6 max z = 2x1 + 3x2 2x1 + 4x2 8 x1 + x2 1 x1，x2 0 无公共部分，无可行域。 即无可行解。 在实际问题中，可能是关系错。1124x1x2第8页/共211页91.3 1.3 线性规划的标准型 1、标准型 max z = c1x1

6、+ c2x2 + + cnxn a11x1 + a12x2 + + a1nxn = b1 a21x1 + a22x2 + + a2nxn = b2 am1x1 + am2x2 + + amnxn = bm x1，x2，xn 0 njxmibxaxczjinjjijnjjj, 10, 1 max11 ，简记：第9页/共211页10 用向量表示 njxbxptsCXzjnjjj, 1, 0 .max1TmjTmjjjjnTnbbbbxaaapcccCxxxX) ( :) ( ) ( ) (:21212121 的系数列向量其中第10页/共211页11 用矩阵描述为： max z = CX AX =

7、b X 0 其中: X = (x1,x2,xn)T C = (c1,c2,cn) b = (b1,b2,bm)T 为系数矩阵 212222111211 mnmmnnaaaaaaaaaA第11页/共211页122 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)不等式(，) 对于“”情况：在“”左边加上一个松弛变量（非负），变为等式； 对于“”情况：在“

8、”左边减去一个剩余变量（非负），变为等式。 注意：松弛变量、剩余变量在目标函数中的价值系数为0 0。 (3)(3)无约束变量 令x xk k = x xk k - - x xk k”，x xk k,x,xk k” 0 0，代入即可。 第12页/共211页13 eg.eg.77将下述问题化为标准型 min zmin z = -x-x1 1+2x+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

9、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 - - 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

10、 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 第13页/共211页141.4 1.4 线性规划解的概念 设线性规划为 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

11、中的m m m m子矩阵，RankRank B B = m m，则称B B为线性规 划问题的一个基。 取B B = (p(p1 1,p,p2 2, ,p,pm m) p) pj j = (a(a1j1j,a,a2j2j, ,a,amjmj) )T T 则称x x1 1,x,x2 2, ,x,xm m为基变量，其它为非基变量。第14页/共211页154 4、基解：取B B = (p(p1 1,p,p2 2, ,p,pm m) ) a a1111, ,a,a1m1m x x1 1 a a1m+11m+1, ,a,a1n1n x xm+1m+1 b b1 1 + + = a am1m1, ,a,am

12、mmm x xm m a amm+1mm+1, ,a,amnmn x xn n b bm m 基 基变量 非基 非基变量 令 x xm+1m+1 = = x xn n = 0 (0 (非基变量为0)0) 则 BXBXB B = b b )!( !mnmnCmn基解个数TmnmTmBxxxXxxxbBX)0 , 0,(),(m )0()0(2)0(1)0()0(2)0(11 个个基解：第15页/共211页165、基可行解 满足式要求的基解。 如右图所示，各边交点O,QO,Q1 1,Q,Q2 2,Q,Q3 3,Q,Q4 4均为基可行解；而其延长线的交点Q5为基解，但不是基可行解。O(0,0)O(0

13、,0)Q Q1 1(4,0)(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为可行基。可行解基可行解非可行解基解第16页/共211页172 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为凸集。（0 01 1） 非凸集X X(1)(1)X X(1)(1)X X(2)(2)X X(2

14、)(2)凸集X X(1)(1)X X(2)(2)X X(2)(2)X X(1)(1)第17页/共211页18 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 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)的凸组合。1k1iik1i) i (iXX2.2

15、 2.2 基本定理 1 1、定理1 1 若线性规划存在可行域，则: : 可行域 D D = X|AXX|AX = b,Xb,X 00为凸集。第18页/共211页19 证明： 设 X X(1)(1)=(=(x1 1(1)(1), ,x2 2(1)(1), , ,xn n(1)(1) )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 -

16、 - )X)X(2)(2) (0(0 0 10 1 0 0 X X 0 0， 即D D为凸集 2、定理2 线性规划的基可行解对应于可行域的顶点。 3、定理3 若线性规划有解，则一定存在基可行解为最优解。第19页/共211页203 3 单纯形法 基本思路：从可行域的一个顶点到另一个顶点迭代求最优解。3.1 3.1 初始基可行解的确定 1、松弛基（松弛变量对应的B） eg.8 max z = x1 + 3x2 x1 + 2x2 3 2x1 + 3x2 4 x1,x2 0max z = x1 + 3x2 + 0 x3 + 0 x4 x1 + 2x2 + x3 = 3 2x1 + 3x2 + x4 =

17、 4 x1,x2,x3,x4 0 化标准型 取x3、x4为基变量,令非基变量x1= x2=0 初始基可行解：X(0) = (0 0 3 4)T B , 1 0 3 20 1 2 1 434321ppppppA则系数矩阵第20页/共211页21 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 00 3 2 1 :414321pppppp

18、A则解第21页/共211页223、人工基 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 找不到单位矩阵基 引入人工变量为初始基变量（2个）第22页/共211页233.2 3.2 最优性的检验与解的判别 mnjxmibxxaxcxczjnjiinjijmiininnjjj, 1 0, 1 max 111对于代入目标函数为非基变量可行为基变量设 , 1, , 1, 1 njjijiinjinxabxnjxmix第23页/共211页24 则njjjnjj

19、jjnjmijijinjmiiinnjminjjijiinjjxZxzcZxaccbcxabcxcz1010111111 )( )( )(miijinjjjjmiiinaczzcbcZ110 , , 其中第24页/共211页25 解的判别： 1. 若 ，则此时的基可行解为最优解； 2. 若存在某个非基变量 的检验数 ，且 ，则该线性规划问题具有无界解（或称无最优解）； 3. 若所有 ，又，对于某个非基变量 有 ，则该线性规划问题具有无穷多最优解。. .的检验数为称jjxkx0knjj, 1, 0 0kp0j0kkx第25页/共211页26 为主元出基行对应的变量则若、出基变量 0minmin0

20、2lkllklikikiiiiikikiiaxlabaabaab为入基变量。则，若、入基变量kkjjx 0max13.3 3.3 基变换第26页/共211页273.4 3.4 旋转运算（消元运算） a1k 0 al-1k 0 pk = （alk） （1） al+1k 0 amk 0 得到基可行解，重复3.23.4， 求出最优解。第27页/共211页283.5 3.5 单纯形表 展开如下： a11x1 + a12x2 + + a1nxn + xn+1 = b1 - cn+1 a21x1 + a22x2 + + a2nxn + xn+2 = b2 - cn+2 am1x1 + am2x2 + +

21、amnxn + xn+m = bm - cn+m c1x1 + c2x2 + + cnxn + cn+1xn+1 + + cn+mxn+m - z = 0 1x1 + 2x2 + + nxn + 0 xn+1 + + 0 xn+m - z = Z0mn, 2 , 1j0 xbxxaxczmaxjiinn1jjijmn1jjj，设第28页/共211页29 建立单纯形表cBxBbc1cncn+1cn+mx1xnxn+1xn+mcn+1xn+1b1a11a1n101cn+mxn+mbmam1amn01m -z -z01 n 00j eg.11 用单纯形法求解 max z = x1 + 3x2 x1

22、+ 2x2 8 4x1 16 4x2 12 x1,x2 0第29页/共211页30 解：标准化，建立单纯形表 引入松弛变量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 0cBxBbx1x2x3x4x5 13000cBxBbx1x2x3x4x5 0 x38121000 x416400100 x51204001此时的解：x(0) = (0 0 8 16 12)Tz(0) = 0第30页/共211页31 解的判别 1=1

23、 2=3 0 x(0)非最优解 基变换 max1,2 = 3 = 2 x2入基 min8/2,-,12/4 = 12/4 x5出基13000cBxBbx1x2x3x4x5 0 x38121000 x416400100 x5120400113000cBxBbx1x2x3x4x5 0 x38121008/20 x41640010-0 x5120400112/413000第31页/共211页32此时的解：x(1)=(0 3 2 16 0)Tz(1)=9x(1)非最优x1入基 x3出基0 x321010-1/22/10 x4164001016/43x2301001/4-1000-3/41x121010

24、-1/20 x4800-4123x2301001/400-10-1/413000此时的解：x(2)=(2 3 0 8 0)Tz(2)=11x(2)为最优解 即： 最优解：x* = (2 3 0 8 0)T 最大值：z* = 11第32页/共211页33 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)x2x1Q1Q2(4,2)Q3(2,3)Q4*O(0,0)第33页/共211页344 4 单纯形法的进一步讨论4.1 4.1 人工变量法 1、大M法（M为很大的正数） 法则：对于max问题

25、，人工变量在目标函数中的价值系数为-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 列单纯形表求解。第34页/共211页35 min z = x1 + 5x2 + 0 x3 + 0 x4 +Mx5 2x1 +

26、3x2 + x3 = 6 2x1 + x2 x4 + x5 = 1 x1,x2,x3,x4,x5 0 对于min问题，若 minj0中，选下标小的非基变量入基； 对相同的最小比值，选下标小的基变量出基。., , 2 , 10,minmin3得问题的最优解时数满足当所有非基变量的检验问题对于问题最优解的判别、njzcjjj第二章j与i的计算同max问题。第43页/共211页44 习题 P45，1.4分别用图解法和单纯形法求解下列线性规划,并指出单纯形法迭代的每一步相当于图形上的哪一个顶点？0,24261553 2max) 1 (21212121xxxxxxxxz0,18231224 52max)

27、2(21212121xxxxxxxxz第44页/共211页45对偶理论与灵敏度分析1 1 单纯形法的矩阵描述 设max z = CX AX = b X 0 A为mn阶矩阵 RankA=m ,取B为可行基, N为非基， NBNBCCCNBAXXX , ,0, maxNBNBNNBBXXbNXBXXCXCz第45页/共211页46bBCbBNBIBN111- 1 0 0 :矩阵单纯形表0zXCXCbNXBXNNBBNBbBCzXNBCCXbBNXBBXBBNBNBNB11111)(0bBCzXXbBNXBIXBNNBNB1110第46页/共211页47bBCzXXbBNXBIXBNNBNB1110

28、NBCCbBCzbBXXBNNBBN111 , , 0 得令.,0 !出则最优解直接由上式求若能找到最优为最优基的使注BBNbBCzbBXB11 0 目标函数基可行解第47页/共211页48 求解步骤：.42 .,. 4. ,)()(0)()()(min ,)(0)(max . 3., 0. 2,. 111111111步直到求出结果重复的求出此得到新的出基行对应的则若入基则若基变换否则转下一步则得最优解若求取可行基BBBxlPBbBPBPBbBxNBCCBBllklikikiikkNjNjBNN第48页/共211页4932利润12kg40材料B16kg04材料A8台时 21设备台时限制 2 2

29、 对偶问题的提出 eg.1 制定生产计划 M1: max z = 2x1 + 3x2 1x1 + 2x2 8 4x1 16 4x2 12 x1，x2 0 第49页/共211页50 现在出租，设y1为设备单位台时的租金 y2,y3为材料A、B转让附加费(kg-1) 则M2为M1的对偶问题，反之亦然。M2: min w = 8y1 + 16y2 + 12y3 y1 + 4y2 2 2y1 + 4y3 3 y1,y2,y3 032利润12kg40材料B16kg04材料A8台时 21设备台时限制 0,124 16 482 32max 212121211xxxxxxxxzM第50页/共211页51 一般

30、的，原问题：max z = CX AX b X 0 对偶问题：min w = Yb YA C Y 0 比较： max z min w 决策变量为n个 约束条件为n个 约束条件为m个 决策变量为m个 “” “”第51页/共211页523 3 对偶问题的化法 1、典型情况 eg.2 max z = x1 + 2x2 + x3 2x1 + x2 6 2x2 + x3 8 x1,x2,x3 0对偶：min w = 6y1 + 8y2 2y1 1 y1 + 2y2 2 y2 1 y1,y2 0第52页/共211页53 2、含等式的情况 eg.3 max z = x1 + 2x2 + 4x3 2x1 +

31、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 y2 0，y1无约束一般，原问题第i个约束取等式，对偶问题第i个变量无约束。 2x1 + x2 + 3x3 3-2x1 - x2 - 3x3 -3第53页/共211页54 3、含“”的max问题 eg.4 max z = x1 + 2x2

32、 + 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,y2 0-2x1 - x2 - 3x3 -3第54页/共211页55一般: max问题第i个约束取“”，则min问题第i个变量 0 ； min问题第i个约束取“”，则max问题第i个变量 0 ； 原问题第i个约束取等式，对偶问

33、题第i个变量 无约束； max问题第j个变量 0 ,则min问题第j个约束取“” ； min问题第j个变量 0 ，则max问题第j个约束取“” ； 原问题第j个变量无约束，对偶问题第j个约束取等式。第55页/共211页56 eg.5 min z = 2x1 + 3x2 - 5x3 + x4 x1 + x2 - 3x3 + x4 5 2x1 + 2x3 - x4 4 x2 + x3 + x4 = 6 x1 0,x2,x3 0,x4无约束对偶：max w = 5y1 + 4y2 + 6y3 y1 + y2 2 y1 + y3 3 -3y1 + 2y2 + y3 -5 y1 - y2 + y3 =

34、1 y1 0,y2 0,y3无约束 第56页/共211页574 4 对偶问题的性质 1、对称性 对偶问题的对偶为原问题.0 )max(0;,min)max(YCYAYbwYCYACYAYbww即0)min(XbAXCXw0 , ,min 0 , ,maxYCYAYbwXbAXCXz第57页/共211页580)min(XbAXCXw证毕令0 max maxmax)min(XbAXCXzwzCXwww第58页/共211页59.,:的可行解分别为原问题和对问题设证明YXXCXAYCAYCYAbYXAYbXAbAX证毕bYXCbYXAYXC bYXCYX ,. 2则存在为对偶问题的可行解为原问题的可行

35、解设弱对偶性第59页/共211页60推论：(1) max问题任一可解的目标值为min问题目标值的一个下界；(2) min问题任一可解的目标值为max问题目标值的一个上界。3、无界性 若原问题(对偶问题)为无界解，则对偶问题(原问题)为无可行解。注：该性质的逆不存在。若原(对偶)问题为无可行解，对偶(原问题)问题或为无界解，或为无可行解。第60页/共211页61 4、最优性 设X*，Y*分别为原问题和对偶问题可行解，当 CX*=Y*b时， X*，Y*分别为最优解。证毕为最优解即为最优解即由弱对偶性题的任一可行解分别为原问题和对偶问设证明 * )2( ) 1 (.,:*YbYbYbYCXbYXCX

36、XCCXbYXCYX第61页/共211页62 5、对偶定理 若原问题有最优解，那么对偶问题也有最优解， 且目标值相等。*11*1*1*1*11*0)(:, 0.:wbYbBCbBCCCXzbBXbBCbYwYBCYCAYCABCABCCXBNBBBBB则其目标值为因原问题最优解则为对偶问题的可行解若其中全部检验数可表示为则其对应的基矩阵存在为原问题的最优解设证明第62页/共211页63Y*为对偶问题的最优解，且原问题和对偶问题的目标值相等。证毕6、松弛性 若X*，Y*分别为原问题及对偶问题的可行解， 那么Ys*X*=0，Y*Xs*=0，当且仅当X*，Y*分别为 最优解。证明：0,0max:SS

37、SXXbXAXXCXz设原问题为0,0min:SSSYYCYYAYYbw设对偶问题为第63页/共211页640,0maxSSSXXbXAXXCXz0,0minSSSYYCYYAYYbwXYYAXXYYACXzSS)(SSYXYAXXAXYYbw)(将b,Cb,C分别代入目标函数：;,0, 0,*为最优解时当为可行解若YXzwXYXYYXSS证毕必有则分别为最优解若另一方面0 , 0,*SSXYXYzwYX第64页/共211页65TSmSSSTnxxxXxxxX) () (*2*1*2*1* ) ( ) ( *2*1*2*1*snSSSmyyyYyyyY 其中：用分量表示： mixynjxySi

38、ijSj, 2 , 1 , 0;, 2 , 1 , 0*第65页/共211页66 7、检验数与解的关系 (1)原问题非最优检验数的负值为对偶问题的一个基解。 (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对应的检验数 第66页/共2

39、11页67 eg.6 已知：min w = 20y1 + 20y2 的最优解为y1*=1.2,y2*=0.2-ys1 y1 + 2y2 1 试用松弛性求对偶-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

40、ys3*x3* = 0 ys4*x4* = 0第67页/共211页68 y1*=1.2,y2*0.2 0 xs1* = xs2* = 0 由 y1* + 2y2* = 1.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* =

41、 4 xs1* = 0 xs2* = 0 最大值：z* = 28 = w*第68页/共211页695 5 对偶问题的经济含义影子价格 最优情况：z* = w* = b1y1* + + biyi* + + bmym*的影子价格为称i*i*ibzbyyi*x2x1Q2 eg.7 max z = 2x1 + 3x2 x1 + 2x2 8 4x1 16 4x2 12 x1,x2 0b1： 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

42、*b3：12 13 z* = 0 = y3*Q2Q2”第69页/共211页706 6 对偶单纯形法 单纯形法：由 XB = B-1b 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)； 第70页/共211页71 (4)消元运算，得到新的XB。(3)基变换 出基变量， 出基；，则若lliiixmibbb, 10min入基变量， 入基。则若kaljajxalkkljj0min重复（2）-（4）步，求出

43、结果。第71页/共211页72 eg.8 用对偶单纯形法求解 min w = 2x1 + 3x2 + 4x3 x1 + 2x2 + 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第72页/共211页73-2-3-400CBXBbx1x2x3x4X50 x4-10 x5-4出出出x4,x5 0 最优最优解：x1* = 2，x2* = 0，x3* = 0，x4* =

44、 1，x5* = 0目标值：w* = -z* = 4第73页/共211页747 7 灵敏度分析njpBCcABCCNBCCjBjjBBNN, 2 , 1, 0 0 0 :111 或或最优性条件分析 变化对最优解的影响。j ,ijiacb0 :1bBXB可行性条件第74页/共211页75的变化资源ib 1 . 7TiTmiiiibbbbbbbbbbbb)0b 0 0() ( 21 bBbBbbBbBXB1111)(.,0 11这里用到可行性条件保持问题的最优性不变的变化范围求出由ibbBbB第75页/共211页76例1 已知下述问题的最优解及最优单纯形表,0,124 164 82 00032ma

45、x54321524132154321xxxxxxxxxxxxxxxxxz., ) 12使最优基不变的变化范围求 b. 4 )21时的最优解求b第76页/共211页77最优单纯形表如下:0-1/8-3/2000-1/81/2102311/2-2004001/40014200032bBXBC5x4x3x2x1x1x5x2x14 Z)4 0 0 2 4(,*TX此时第77页/共211页7822216 1) :bbb解08/12/112/1204/101B2441216808/12/112/1204/101*bBXB由最优单纯形表得:第78页/共211页79)(012bbBb221118/12/14/

46、12440008/12/112/1204/10244)(bbbBbBbbB0008/22/44/4222bbb08/202/404/4222bbb.1682最优基不变b第79页/共211页80TTbb)0 0 4()0 0 ( )214 44 28024400408/12/112/1204/10244)(111bBbBbbB不可行!用对偶单纯形法计算第80页/共211页81-3/4-1/20001/400103x23-1/2-1/41002x3001/40014x120-1/8-3/2000-1/81/2102+2311/2-2004-8x5001/40014+0 x12ix5x4x3x2x1

47、bXBCB00032x23/4-2)(17 : . 0, 0, 2, 3, 4 :*5*4*3*2*1元目标值最优解zxxxxx第81页/共211页82的变化价值系数jc 2 . 7.01分两种情况讨论进行分析根据最优性条件NBCCBNN的变化非基变量价值系数kc. 1kBkkpBCc1:原检验数/ :kkkkkccccc变化kkkBkkkcpBCcc1/., 0 :/此时最优解不变令kkkkkcc第82页/共211页83例2 求例1 c4的变化范围,使最优解不变.0-1/8-3/2000-1/81/2102311/2-2004x5001/40014x12ix5x4x3x2x1bXBCB000

48、32x204c8/1)8/1(8/1444c由解:. 8/1 4时最优解不变即c第83页/共211页84的变化基变量价值系数rc. 2NBCCBNN1 原BBBCCC 若NBCNBCNBCCNBCCCBNBBNBBNN1111/ )( 则分析:)0 0 0( ) ( :21 rBmrBcCccccC其中.变化影响所有可见jrc第84页/共211页85方法:.0 1/的变化范围求出令rBNNcNBC例3 求例1 c2的变化范围,使最优解不变.0-1/8-3/2000-1/81/2102311/2-2004x5001/40014x12ix5x4x3x2x1bXBCB00032x2第85页/共211

49、页86解:0-1/8-3/2000-1/81/2102311/2-2004x5001/40014x12ix5x4x3x2x1bXBCB00032x2) 0 0( ),3 0 2(2cCCBB 1/8)- (-3/2) (43N ) (/4/3/n44414/433313/3pcpBcpcpBcBBBB第86页/共211页8702232/120)c 0 0(232233/3cpcB08818/12/14/1)c 0 0(812244/4cpcB1322cc. 13 2时最优解不变即c第87页/共211页88的变化技术系数jia 3 . 7kBkkpBCc1 原T1k k k 0) a 0( )

50、( , lkkTmklkkkkkklllpaaappppaaaa若分析:.k 的变化讨论非基变量技术系数la第88页/共211页89lklkakBkBkkkBkKpBCpBCcppBCc111 )( 则TlkmlkkBkapBC)00)(11 0lklkka令., 最优解不变时当lkkla第89页/共211页90例4 求例1 a24的变化范围,使最优解不变.解:242424241, 1aaaa) (0) 1/8 2/3( 3) 0 2(32111BBCB24242448181aa08181 244a令. , 1 24此时最优解不变a第90页/共211页91 例5 在例1的基础上，企业要增加一个

51、新产品,每件产品需2个台时，原材料A 6kg，原材料B 3kg，利润 5元/件，问如何安排各产品的产量，使利润最大？解：0,1234 1664 822 532max3213231321321xxxxxxxxxxxxxz532利润12340料B16604料A8221设备b则有为新产品生产的件数设,3x第91页/共211页9231 )2pB计算25. 025 . 136208/12/112/1204/1031pB0453620 81 2353133pBCcB3 ) 1计算表明生产新品有利。第92页/共211页93., ) 3331加入原最优表计算将pB2 ,53出基主元为入基 xx5/40-1/8

52、-3/2001/40-1/81/21023211/2-2004x503/201/40014x12x5x4x3x2x1bXBCB500032x2ix3第93页/共211页945/40-1/8-3/2001/40-1/81/21023211/2-2004x503/201/40014x12x5x4x3x2x1bXBCB500032x28/34/28ix320-5/8-7/16-1/4000-1/8-3/163/4103/2311/21/4-10020-3/4-1/83/2011x12x5x4x3x2x1bXBCB500032x2ix3x35)(5 . 2 )(5 .16 . 2 , 2/3 , 1*

53、3*2*1元增加元zxxx第94页/共211页95小结0 maxXbAXCXz1、对偶问题及其化法0 minYCYAYbw原问题决策变量决定对偶问题约束条件关系原问题约束条件决定对偶问题决策变量取值方向。第95页/共211页962、检验数的计算方法njpCcpBCcjBjjBjj, 2 , 1 , 1 或NBCCBNN1 ABCCB1 或阶矩阵阶矩阵 :, :1mmBmnnmAjjpBp1第96页/共211页973、对偶问题的性质4、对偶单纯形法弱对偶性无界性最优性松弛性检验数与对偶问题的解第97页/共211页98njpBCcjBjj, 2 , 1, 01 变化对最优解的影响分析ijjiacb

54、,0 :1NBCCBNN最优性条件0 1ABCCB0 :1bBXB可行性条件5、灵敏度分析第98页/共211页99的变化技术系数jia )3(的变化基变量价值系数rc 2的变化非基变量价值系数kc 1的变化价值系数jc )2(的变化资源ib ) 1 (的变化分析非基变量技术系数第99页/共211页100整数规划Integer Programming1 1 问题的提出 eg.1 用集装箱托运货物 问：甲乙货物托运多少箱，使总利润最大？货物m3/箱百斤/箱百元/箱甲5220乙4510限制2413 分析：设x1为甲货物托运箱数，x2为乙货物托运箱数。 则 max z = 20 x1 + 10 x2

55、5x1 + 4x2 24 2x1 + 5x2 13 x1,x2 0 x1,x2取整数第100页/共211页101图解法：x1x243210124.82.6(4,1) x1* = 4 x2* = 1 zI* = 90 第101页/共211页102 一般，整数规划的最优解不会优于相应线性规划的最优解。 对于max问题， zI* zl* 对于min问题， zI* zl* 数学模型：取整数jjnjiijijnjjjxnjxmibxaxcz, 10, 1max11第102页/共211页1032 2 分枝定界法 用单纯形法，去掉整数约束IP LP xl* 判别是否整数解xI* = xl*Yes去掉非整数域

56、No多个LP第103页/共211页1043 0-13 0-1规划（x xi i = 0 0或1 1的规划） eg.2 选择投资场所 Ai投资Bi元，总投资B， 收益Ci元. 问：如何选择Ai，使收益最大？A6A7A4A5A3A2A1最多选2个最少选1个最少选1个 分析：引入 xi = 1 Ai选中 0 Ai落选 max z = C1x1 + C2x2 + + C7x7 x1 + x2 + x3 2 x4 + x5 1 x6 + x7 1 B1x1 + B2x2 + + B7x7 B xi = 0或1南区西区东区第104页/共211页105 eg.3 求解如下0-1规划 max z = 3x1

57、- 2x2 + 5x3 x1 + 2x2 - x3 2 x1 + 4x2 + x3 4 x1 + x2 3 4x2 + x3 6 x1,x2,x3 = 0或1 解：(1)观察一个可行解x1 = 1 x2 = x3 = 0 此时，z = 3 (2)增加一个过滤条件 3x1-2x2+5x33 *第105页/共211页106(3)列表计算x1x2x3*可行？zx1x2x3*可行？z000001010011100101110111x1x2x3*可行？z0000001010011100101110111x1x2x3*可行？z00000015-11015010011100101110111x1x2x3*可

58、行？z00000015-11015010-2011100101110111x1x2x3*可行？z00000015-11015010-2011315100101110111x1x2x3*可行？z00000015-11015010-2011315100311103101110111x1x2x3*可行？z00000015-11015010-2011315100311103101802118110111x1x2x3*可行？z00000015-11015010-20113151003111031018021181101111x1x2x3*可行？z00000015-11015010-20113151003

59、111031018021181101111626 最优解：x1* = 1 x2* = 0 x3* = 1 此时，z* = 8第四章第106页/共211页107非线性数规划 Nonlinear Programming1 1 问题的提出 eg.1 某单位拟建一排厂房，厂房建筑平面如图所示。由于资金及材料的限制，围墙及隔墙的总长度不能超过80米。为使建筑面积最大，应如何选择长宽尺寸？1x2x0,8052)(max212121xxxxxxxf分析：设长为 米，宽为 米，则有1x2x f(x)为非线性函数第107页/共211页108例2 设某物理过程具有如下规律 用试验法 。 现要确定参数 使所得试验点

60、构成的曲线与理论曲线误差平方和为最小，且满足 txexxt321)(mittii, 2 , 1,)( 值时的求得,321xxx., 1321非负xxx第108页/共211页109非线性规划： 目标函数或（和）约束条件为非线性函数的规划。031)()()(min2112213xxxexxtxfmitxii分析： f(x)为非线性函数，求最小。第109页/共211页1102 2 基本概念2.1非线性规划的数学模型数学模型的一般描述 约束条件目标函数 (2) ,1,2,j , 0)( (1) )(minxgxfjTnjxxxxxgxf) ( )(),(:21 为非线性函数其中第110页/共211页1