清华大学运筹学完整学习教案

1、会计学1清华大学清华大学(qn hu d xu)运筹学完整运筹学完整第一页，共211页。2 分析(fnx)： 化工厂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页第二页，共211页。3 x1，x2，xn 0第2页/共21

2、1页第三页，共211页。4 (1)决策变量：x1，x2，xn 。 一组决策变量表示为问题的一个方案(fng n)； (2)目标函数：max(min)z z为决策变量的线性函数; (3)约束条件 一组线性不等式。cj为价值系数, bi为资源， aij为技术系数(i=1,m;j=1,n).第3页/共211页第四页，共211页。5 解： (1)建立(jinl)x1 - x2坐标；x2x1 (2)约束条件的几何(j h)表示； Q1Q2Q3Q4 (3)目标函数(hnsh)的几何表示； * z z = 2x2x1 1 + + 3x3x2 2 o43zxx313212第4页/共211页第五页，共211页。

3、6* 可见，在Q2点z取到最大值。 因此， Q2点所对应(duyng)的解为最优解。 Q2点坐标为(4，2)。 即: x1 = 4，x2 = 2 由此求得最优解：x1* = 4 x2* = 2 最大值：max z = z* = 2x1 + 3x2 = 14(元)x2x1Q1Q2(4,2)Q3Q4*43第5页/共211页第六页，共211页。7 (2)无穷多最优解 eg.4 对eg.1，若目标函数 z = 2x1 + 4x2，此时(c sh)表示 目标函数的直线与表示 条件的直线平行， 最优点在线段Q3Q2上。 即存在无穷多最优解。x2x1Q1 Q2(4,2)Q3(2,3)Q4o43*第6页/共2

4、11页第七页，共211页。8o2241x2x第7页/共211页第八页，共211页。91124x1x2第8页/共211页第九页，共211页。10njxmibxaxczjinjjijnjjj, 10, 1 max11 ，简记：第9页/共211页第十页，共211页。11 njxbxptsCXzjnjjj, 1, 0 .max1TmjTmjjjjnTnbbbbxaaapcccCxxxX) ( :) ( ) ( ) (:21212121 的系数列向量其中第10页/共211页第十一页，共211页。12为系数矩阵 212222111211 mnmmnnaaaaaaaaaA第11页/共211页第十二页，共21

5、1页。13 (2)不等式(，) 对于“”情况：在“”左边(zu bian)加上一个松弛变量（非负），变为等式； 对于“”情况：在“”左边(zu bian)减去一个剩余变量（非负），变为等式。 注意：松弛变量、剩余变量在目标函数中的价值系数为0。 (3)无约束变量(binling) 令xk = xk - xk”，xk,xk” 0，代入即可。 第12页/共211页第十三页，共211页。14解：令解：令x3 = x3-x3”x3 = x3-x3”，x3,x3” 0 x3,x3” 0； 式加上一个式加上一个(y )(y )松弛变量松弛变量x4x4；式减去一个；式减去一个(y )(y )剩剩余变量余变量

6、x5x5； 令令z = -zz = -z max z = x1- 2x2 + 3(x3 - x3”) + 0 x4 + 0 x5max z = x1- 2x2 + 3(x3 - x3”) + 0 x4 + 0 x5 x1 + x2 + (x3 - x3”) + x4 = 7 x1 + x2 + (x3 - x3”) + x4 = 7 x1 - x2 + (x3 - x3”) - x5 = 2 x1 - x2 + (x3 - x3”) - x5 = 2 -3x1 + x2 + 2(x3 - x3”) = 5 -3x1 + x2 + 2(x3 - x3”) = 5 x1,x2,x3,x3”,x4,

7、x5 0 x1,x2,x3,x3”,x4,x5 0 第13页/共211页第十四页，共211页。15 1、可行(kxng)解：满足条件、的X； 2、最优解：满足条件的可行(kxng)解； 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 j = (a(a1j1j,a,a2j2j, ,a,amjmj) )T T 则称则称x x1 1,x,x2 2, ,x,xm m为基变量，其它为非基变量。为基

8、变量，其它为非基变量。第14页/共211页第十五页，共211页。16)!( !mnmnCmn基解个数TmnmTmBxxxXxxxbBX)0 , 0,(),(m )0()0(2)0(1)0()0(2)0(11 个个基解：第15页/共211页第十六页，共211页。17O(0,0)O(0,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、可行(kxng)基 基可行(kxng)解对应的B为可行(kxng)基。可行解可行解基可行解基可行解非可行解非可行解基解基解第16页/共211页第十七

9、页，共211页。18非凸集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)第17页/共211页第十八页，共211页。191k1iik1i) i (iXX2.2 2.2 基本基本(jbn)(jbn)定理定理 1 1、定理、定理1 1 若线性规划存在可行域，则若线性规划存在可行域，则: : 可行域可行域 D = X|AX = b,X 0 D = X|AX = b,X 0为凸集。为凸集。第18页/共211页第十九页，共211页。20 2、定理(dngl)2 线性规划的基可行解对应于可行域的顶点。 3、

10、定理3 若线性规划有解，则一定存在(cnzi)基可行解为最优解。第19页/共211页第二十页，共211页。213.1 3.1 初始初始(ch sh)(ch sh)基可行解的确基可行解的确定定 1 1、松弛基（松弛变量对应的、松弛基（松弛变量对应的B B） eg.8max z = x1 + 3x2 eg.8max z = x1 + 3x2 x1 + 2x2 3 x1 + 2x2 3 2x1 + 3x2 4 2x1 + 3x2 4 x1,x2 0 x1,x2 0max z = x1 + 3x2 + 0 x3 + 0 x4 x1 + 2x2 + x3 = 3 2x1 + 3x2 + x4 = 4 x

11、1,x2,x3,x4 0 化标准型 取x3、x4为基变量(binling),令非基变量(binling)x1= x2=0 初始基可行解：X(0) = (0 0 3 4)T B , 1 0 3 20 1 2 1 434321ppppppA则系数矩阵第20页/共211页第二十一页，共211页。22 选 XB = (x1 x4)T 令x2 = x3 = 0 则 初始(ch sh)基可行解：X(0) = (3 0 0 4)T B , 1 1 3 00 3 2 1 :414321ppppppA则解第21页/共211页第二十二页，共211页。23 分析(fnx)： A = 1 3 2 2 1 1 找不到单

12、位矩阵基 引入人工变量为初始基变量（2个）第22页/共211页第二十三页，共211页。24 mnjxmibxxaxcxczjnjiinjijmiininnjjj, 1 0, 1 max 111对于代入目标函数为非基变量可行为基变量设 , 1, , 1, 1 njjijiinjinxabxnjxmix第23页/共211页第二十四页，共211页。25njjjnjjjjnjmijijinjmiiinnjminjjijiinjjxZxzcZxaccbcxabcxcz1010111111 )( )( )(miijinjjjjmiiinaczzcbcZ110 , , 其中第24页/共211页第二十五页，共

13、211页。26. .的检验数为称jjxkx0knjj, 1, 0 0kp0j0kkx第25页/共211页第二十六页，共211页。27 为主元出基行对应的变量则若、出基变量 0minmin02lkllklikikiiiiikikiiaxlabaabaab为入基变量。则，若、入基变量kkjjx 0max13.3 3.3 基变换基变换(binhun)(binhun)第26页/共211页第二十七页，共211页。28第27页/共211页第二十八页，共211页。29mn, 2 , 1j0 xbxxaxczmaxjiinn1jjijmn1jjj，设第28页/共211页第二十九页，共211页。30cBxBbc

14、1cncn+1cn+mx1xnxn+1xn+mcn+1xn+1b1a11a1n101cn+mxn+mbmam1amn01m -z -z01 n 00j eg.11用单纯形法求解(qi ji) max z = x1 + 3x2 x1 + 2x2 8 4x1 16 4x2 12 x1,x2 0第29页/共211页第三十页，共211页。31cBxBbx1x2x3x4x5 13000cBxBbx1x2x3x4x5 0 x38121000 x416400100 x51204001此时(c sh)的解：x(0) = (0 0 8 16 12)Tz(0) = 0第30页/共211页第三十一页，共211页。3

15、2 1=1 2=3 0 x(0)非最优解 基变换(binhun) 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页第三十二页，共211页。330 x321010-1/22/10 x4164001016/43x2301001/4-1000-3/41x121010-1/20 x4800-4123x230

16、1001/400-10-1/413000此时(c sh)的解：x(2)=(2 3 0 8 0)Tz(2)=11x(2)为最优解 即： 最优解：x* = (2 3 0 8 0)T 最大值：z* = 11第32页/共211页第三十三页，共211页。34x2x1Q1Q2(4,2)Q3(2,3)Q4*O(0,0)第33页/共211页第三十四页，共211页。35第34页/共211页第三十五页，共211页。361500McBxBbx1x2x3x4x5 0 x36231006/2Mx51210-111/21-2M5-M0M0第35页/共211页第三十六页，共211页。371500McBxBbx1x2x3x4

17、x5 0 x350211-11x11/211/20-1/21/209/201/2M+1/21500McBxBbx1x2x3x4x5 0 x36231006/2Mx51210-111/21-2M5-M0M0第36页/共211页第三十七页，共211页。38第37页/共211页第三十八页，共211页。39 mnjxmibxxaxxwjiinnjjijmnn, 1, 0, 1,min11第38页/共211页第三十九页，共211页。40第39页/共211页第四十页，共211页。41CBXBb0 x10 x20 x30 x41x5i0 x36231006/21x51210-111/2-2-10100 x3

18、50211-10 x11/211/20-1/2-1/21/200001第40页/共211页第四十一页，共211页。42CBXBb1x15x20 x30 x40 x3502111x11/211/20-1/2-1/209/201/2第41页/共211页第四十二页，共211页。43。基一般选下标小的变量入基可任取其中一个变量入值，有两个或两个以上相同、检验数相同)(0max1jj有相同值，、最小比值相同0min2ikabiaiki第42页/共211页第四十三页，共211页。44., , 2 , 10,minmin3得问题的最优解时数满足当所有非基变量的检验问题对于问题最优解的判别、njzcjjj第二

19、章j与i的计算(j sun)同max问题。第43页/共211页第四十四页，共211页。450,24261553 2max) 1 (21212121xxxxxxxxz0,18231224 52max)2(21212121xxxxxxxxz第44页/共211页第四十五页，共211页。46NBNBCCCNBAXXX , ,0, maxNBNBNNBBXXbNXBXXCXCz第45页/共211页第四十六页，共211页。47bBCbBNBIBN111- 1 0 0 :矩阵单纯形表0zXCXCbNXBXNNBBNBbBCzXNBCCXbBNXBBXBBNBNBNB11111)(0bBCzXXbBNXBIX

20、BNNBNB1110第46页/共211页第四十七页，共211页。48bBCzXXbBNXBIXBNNBNB1110NBCCbBCzbBXXBNNBBN111 , , 0 得令.,0 !出则最优解直接由上式求若能找到最优为最优基的使注BBNbBCzbBXB11 0 目标函数基可行解第47页/共211页第四十八页，共211页。49.42 .,. 4. ,)()(0)()()(min ,)(0)(max . 3., 0. 2,. 111111111步直到求出结果重复的求出此得到新的出基行对应的则若入基则若基变换否则转下一步则得最优解若求取可行基BBBxlPBbBPBPBbBxNBCCBBllklik

21、ikiikkNjNjBNN第48页/共211页第四十九页，共211页。5032利润12kg40材料B16kg04材料A8台时 21设备台时限制 2 2 对偶问题的提出对偶问题的提出 eg.1 制定生产计划 M1: max z = 2x1 + 3x2 1x1 + 2x2 8 4x1 16 4x2 12 x1，x2 0 第49页/共211页第五十页，共211页。51 则M2为M1的对偶(du u)问题，反之亦然。M2: min w = 8y1 + 16y2 + 12y3 y1 + 4y2 2 2y1 + 4y3 3 y1,y2,y3 032利润12kg40材料B16kg04材料A8台时 21设备台

22、时限制 0,124 16 482 32max 212121211xxxxxxxxzM第50页/共211页第五十一页，共211页。52 对偶(du u)问题：min w = Yb YA C Y 0 比较(bjio)： max z min w 决策变量为n个 约束条件为n个 约束条件为m个 决策变量为m个 “” “”第51页/共211页第五十二页，共211页。53对偶：min w = 6y1 + 8y2 2y1 1 y1 + 2y2 2 y2 1 y1,y2 0第52页/共211页第五十三页，共211页。54对偶：min w = 3y1-3y1”+4y2 2y1-2y1”+ y2 1 y1- y1

23、”+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无约束一般，原问题(wnt)第i个约束取等式，对偶问题(wnt)第i个变量无约束。 2x1 + x2 + 3x3 3-2x1 - x2 - 3x3 -3第53页/共211页第五十四页，共211页。55对偶：min w = -3y1 + 4y2 -2y1 + y2 1 -y1 + 2y2 2 -3y1 + 5y2 4 y1,y2 0令y1 = -y1，则： min w = 3y1 + 4y2

24、2y1 + y2 1 y1 + 2y2 2 3y1 + 5y2 4 y1 0,y2 0-2x1 - x2 - 3x3 -3第54页/共211页第五十五页，共211页。56一般(ybn): max问题第i个约束取“”，则min问题第i个变量 0 ； min问题(wnt)第i个约束取“”，则max问题(wnt)第i个变量 0 ； 原问题第i个约束取等式，对偶(du u)问题第i个变量 无约束； max问题第j个变量 0 ,则min问题第j个约束取“” ； min问题第j个变量 0 ，则max问题第j个约束取“” ； 原问题第j个变量无约束，对偶问题第j个约束取等式。第55页/共211页第五十六页，

25、共211页。57对偶：max w = 5y1 + 4y2 + 6y3 y1 + y2 2 y1 + y3 3 -3y1 + 2y2 + y3 -5 y1 - y2 + y3 = 1 y1 0,y2 0,y3无约束 第56页/共211页第五十七页，共211页。58 1、对称性 对偶(du u)问题的对偶(du u)为原问题.0 )max(0;,min)max(YCYAYbwYCYACYAYbww即0)min(XbAXCXw0 , ,min 0 , ,maxYCYAYbwXbAXCXz第57页/共211页第五十八页，共211页。590)min(XbAXCXw证毕令0 max maxmax)min(

26、XbAXCXzwzCXwww第58页/共211页第五十九页，共211页。60.,:的可行解分别为原问题和对问题设证明YXXCXAYCAYCYAbYXAYbXAbAX证毕bYXCbYXAYXC bYXCYX ,. 2则存在为对偶问题的可行解为原问题的可行解设弱对偶性第59页/共211页第六十页，共211页。613、无界性 若原问题(对偶(du u)问题)为无界解，则对偶(du u)问题(原问题)为无可行解。注：该性质的逆不存在(cnzi)。若原(对偶)问题为无可行解，对偶(原问题)问题或为无界解，或为无可行解。第60页/共211页第六十一页，共211页。62 4、最优性 设X*，Y*分别(fnb

27、i)为原问题和对偶问题可行解，当 CX*=Y*b时， X*，Y*分别(fnbi)为最优解。证毕为最优解即为最优解即由弱对偶性题的任一可行解分别为原问题和对偶问设证明 * )2( ) 1 (.,:*YbYbYbYCXbYXCXXCCXbYXCYX第61页/共211页第六十二页，共211页。63 5、对偶定理(dngl) 若原问题有最优解，那么对偶问题也有最优解， 且目标值相等。*11*1*1*1*11*0)(:, 0.:wbYbBCbBCCCXzbBXbBCbYwYBCYCAYCABCABCCXBNBBBBB则其目标值为因原问题最优解则为对偶问题的可行解若其中全部检验数可表示为则其对应的基矩阵存

28、在为原问题的最优解设证明第62页/共211页第六十三页，共211页。646、松弛(sn ch)性 若X*，Y*分别为原问题及对偶问题的可行解， 那么Ys*X*=0，Y*Xs*=0，当且仅当X*，Y*分别为 最优解。证明(zhngmng)：0,0max:SSSXXbXAXXCXz设原问题为0,0min:SSSYYCYYAYYbw设对偶问题为第63页/共211页第六十四页，共211页。650,0maxSSSXXbXAXXCXz0,0minSSSYYCYYAYYbwXYYAXXYYACXzSS)(SSYXYAXXAXYYbw)(将b,C分别(fnbi)代入目标函数：;,0, 0,*为最优解时当为可行

29、解若YXzwXYXYYXSS证毕必有则分别为最优解若另一方面0 , 0,*SSXYXYzwYX第64页/共211页第六十五页，共211页。66TSmSSSTnxxxXxxxX) () (*2*1*2*1* ) ( ) ( *2*1*2*1*snSSSmyyyYyyyY 其中(qzhng)：用分量(fn ling)表示： mixynjxySiijSj, 2 , 1 , 0;, 2 , 1 , 0*第65页/共211页第六十六页，共211页。67 分析：max z = CX + 0Xs = (C 0)(X Xs)T AX + Xs = b X,Xs 0 min w = Yb + YS0 YA -

30、Ys = C Y,Ys 0 检验(jinyn)数： = (C 0)- CBB-1(A I) = (C- CBB-1A - CBB-1) = (c s) c = C - CBB-1A X对应的检验(jinyn)数 s = - CBB-1 Xs对应的检验(jinyn)数 第66页/共211页第六十七页，共211页。68 解：对偶问题 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* =

31、 0 ys2*x2* = 0 ys3*x3* = 0 ys4*x4* = 0第67页/共211页第六十八页，共211页。69 有 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*第68页/共211页第六十九页，共211页。70的影子价格为称i*i*ibzbyyi*x2x1Q2 eg.7 max z = 2x1 + 3x2 x1 + 2x2 8 4x1 16 4x2 12 x1,x2 0b1： 8 9 Q2

32、(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*Q2Q2”第69页/共211页第七十页，共211页。71 步骤：步骤：(1)(1)保持保持(boch)j 0(boch)j 0，j= 1,nj= 1,n，确定，确定XBXB，建立计算表格；建立计算表格； (2)判别XB = B-1b 0是否(sh fu)成立？ 若成立，XB为最优基变量； 若不成立，转(3)； 第70页/共211页第七十一页，共211

33、页。72 (4)消元运算(yn sun)，得到新的XB。(3)基变换(binhun) 出基变量， 出基；，则若lliiixmibbb, 10min入基变量(binling)， 入基。则若kaljajxalkkljj0min重复（2）-（4）步，求出结果。第71页/共211页第七十二页，共211页。73解：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页第七十三页，共211页。74-2-3-400CBXBbx1x

34、2x3x4X50 x4-10 x5-4出出出x4,x5 0 最优最优解：最优解：x1* = 2，x2* = 0，x3* = 0，x4* = 1，x5* = 0目标值：目标值：w* = -z* = 4第73页/共211页第七十四页，共211页。75njpBCcABCCNBCCjBjjBBNN, 2 , 1, 0 0 0 :111 或或最优性条件分析 变化对最优解的影响。j ,ijiacb0 :1bBXB可行性条件第74页/共211页第七十五页，共211页。76的变化资源ib 1 . 7TiTmiiiibbbbbbbbbbbb)0b 0 0() ( 21 bBbBbbBbBXB1111)(.,0

35、11这里用到可行性条件保持问题的最优性不变的变化范围求出由ibbBbB第75页/共211页第七十六页，共211页。770,124 164 82 00032max54321524132154321xxxxxxxxxxxxxxxxxz., ) 12使最优基不变的变化范围求 b. 4 )21时的最优解求b第76页/共211页第七十七页，共211页。780-1/8-3/2000-1/81/2102311/2-2004001/40014200032bBXBC5x4x3x2x1x1x5x2x14 Z)4 0 0 2 4(,*TX此时第77页/共211页第七十八页，共211页。7922216 1) :bbb

36、解08/12/112/1204/101B2441216808/12/112/1204/101*bBXB由最优单纯形表得:第78页/共211页第七十九页，共211页。80)(012bbBb221118/12/14/12440008/12/112/1204/10244)(bbbBbBbbB0008/22/44/4222bbb08/202/404/4222bbb.1682最优基不变b第79页/共211页第八十页，共211页。81TTbb)0 0 4()0 0 ( )214 44 28024400408/12/112/1204/10244)(111bBbBbbB不可行(kxng)!用对偶(du u)单

37、纯形法计算第80页/共211页第八十一页，共211页。82-3/4-1/20001/400103x23-1/2-1/41002x3001/40014x120-1/8-3/2000-1/81/2102+2311/2-2004-8x5001/40014+0 x12ix5x4x3x2x1bXBCB00032x23/4-2)(17 : . 0, 0, 2, 3, 4 :*5*4*3*2*1元目标值最优解zxxxxx第81页/共211页第八十二页，共211页。83的变化价值系数jc 2 . 7.01分两种情况讨论进行分析根据最优性条件NBCCBNN的变化非基变量价值系数kc. 1kBkkpBCc1:原检

38、验数/ :kkkkkccccc变化kkkBkkkcpBCcc1/., 0 :/此时最优解不变令kkkkkcc第82页/共211页第八十三页，共211页。840-1/8-3/2000-1/81/2102311/2-2004x5001/40014x12ix5x4x3x2x1bXBCB00032x204c8/1)8/1(8/1444c由解:. 8/1 4时最优解不变即c第83页/共211页第八十四页，共211页。85的变化基变量价值系数rc. 2NBCCBNN1 原BBBCCC 若NBCNBCNBCCNBCCCBNBBNBBNN1111/ )( 则分析(fnx):)0 0 0( ) ( :21 rB

39、mrBcCccccC其中.变化影响所有可见jrc第84页/共211页第八十五页，共211页。86方法(fngf):.0 1/的变化范围求出令rBNNcNBC例3 求例1 c2的变化(binhu)范围,使最优解不变.0-1/8-3/2000-1/81/2102311/2-2004x5001/40014x12ix5x4x3x2x1bXBCB00032x2第85页/共211页第八十六页，共211页。87解:0-1/8-3/2000-1/81/2102311/2-2004x5001/40014x12ix5x4x3x2x1bXBCB00032x2) 0 0( ),3 0 2(2cCCBB 1/8)- (

40、-3/2) (43N ) (/4/3/n44414/433313/3pcpBcpcpBcBBBB第86页/共211页第八十七页，共211页。8802232/120)c 0 0(232233/3cpcB08818/ 12/ 14/ 1)c 0 0(812244/4cpcB1322cc. 13 2时最优解不变即c第87页/共211页第八十八页，共211页。89的变化技术系数jia 3 . 7kBkkpBCc1 原T1k k k 0) a 0( ) ( , lkkTmklkkkkkklllpaaappppaaaa若分析(fnx):.k 的变化讨论非基变量技术系数la第88页/共211页第八十九页，共

41、211页。90lklkakBkBkkkBkKpBCpBCcppBCc111 )( 则TlkmlkkBkapBC)00)(11 0lklkka令., 最优解不变时当lkkla第89页/共211页第九十页，共211页。91例4 求例1 a24的变化(binhu)范围,使最优解不变.解:242424241, 1aaaa) (0) 1/8 2/3( 3) 0 2(32111BBCB24242448181aa08181 244a令. , 1 24此时最优解不变a第90页/共211页第九十一页，共211页。920,1234 1664 822 532max3213231321321xxxxxxxxxxxxx

42、z532利润12340料B16604料A8221设备b则有为新产品生产的件数设,3x第91页/共211页第九十二页，共211页。9331 )2pB计算25. 025 . 136208/12/112/1204/1031pB0453620 81 2353133pBCcB3 ) 1计算表明(biomng)生产新品有利。第92页/共211页第九十三页，共211页。94., )3331加入原最优表计算将pB2 ,53出基主元为入基 xx5/40-1/8-3/2001/40-1/81/21023211/2-2004x503/201/40014x12x5x4x3x2x1bXBCB500032x2ix3第93

43、页/共211页第九十四页，共211页。955/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*3*2*1元增加元zxxx第94页/共211页第九十五页，共211页。960 maxXbAXCXz1、对偶(du u)问题及其化法

44、0 minYCYAYbw原问题决策变量决定对偶(du u)问题约束条件关系原问题约束条件决定对偶问题决策变量取值方向。第95页/共211页第九十六页，共211页。972、检验(jinyn)数的计算方法njpCcpBCcjBjjBjj, 2 , 1 , 1 或NBCCBNN1 ABCCB1 或阶矩阵阶矩阵 :, :1mmBmnnmAjjpBp1第96页/共211页第九十七页，共211页。983、对偶(du u)问题的性质4、对偶(du u)单纯形法弱对偶性无界性最优性松弛(sn ch)性检验数与对偶问题的解第97页/共211页第九十八页，共211页。99njpBCcjBjj, 2 , 1, 01

45、 变化对最优解的影响分析ijjiacb,0 :1NBCCBNN最优性条件0 1ABCCB0 :1bBXB可行性条件5、灵敏度分析(fnx)第98页/共211页第九十九页，共211页。100的变化技术系数jia )3(的变化基变量价值系数rc 2的变化非基变量价值系数kc 1的变化价值系数jc )2(的变化资源ib ) 1 (的变化分析非基变量技术系数第99页/共211页第一百页，共211页。101货物m3/箱百斤/箱百元/箱甲5220乙4510限制2413 分析：设x1为甲货物托运箱数，x2为乙货物托运箱数。 则 max z = 20 x1 + 10 x2 5x1 + 4x2 24 2x1 +

46、 5x2 13 x1,x2 0 x1,x2取整数第100页/共211页第一百零一页，共211页。102x1x243210124.82.6(4,1) x1* = 4 x2* = 1 zI* = 90 第101页/共211页第一百零二页，共211页。103 对于(duy)max问题， zI* zl* 对于(duy)min问题， zI* zl* 数学模型：取整数jjnjiijijnjjjxnjxmibxaxcz, 10, 1max11第102页/共211页第一百零三页，共211页。104IP LP xl* 判别是否整数解xI* = xl*Yes去掉非整数域No多个LP第103页/共211页第一百零四

47、页，共211页。105A6A7A4A5A3A2A1最多选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南区西区东区(dn q)第104页/共211页第一百零五页，共211页。106 解：(1)观察一个(y )可行解x1 = 1 x2 = x3 = 0 此时，z = 3 (2)增加一个过滤条件 3x1-2x2+5x33 *第105页/共211页第一百零六页，共211页。107x1

48、x2x3*可行？zx1x2x3*可行？z000001010011100101110111x1x2x3*可行？z0000001010011100101110111x1x2x3*可行？z00000015-11015010011100101110111x1x2x3*可行？z00000015-11015010-2011100101110111x1x2x3*可行？z00000015-11015010-2011315100101110111x1x2x3*可行？z00000015-11015010-2011315100311103101110111x1x2x3*可行？z00000015-11015010-2

49、011315100311103101802118110111x1x2x3*可行？z00000015-11015010-20113151003111031018021181101111x1x2x3*可行？z00000015-11015010-20113151003111031018021181101111626 最优解：x1* = 1 x2* = 0 x3* = 1 此时，z* = 8第四章第106页/共211页第一百零七页，共211页。1081x2x0,8052)(max212121xxxxxxxf分析：设长为 米，宽为 米，则有1x2x f(x)为非线性函数(hnsh)第107页/共211页

50、第一百零八页，共211页。109txexxt321)(mittii, 2 , 1,)( 值时的求得,321xxx., 1321非负xxx第108页/共211页第一百零九页，共211页。110031)()()(min2112213xxxexxtxfmitxii分析(fnx)： f(x)为非线性函数(hnsh)，求最小。第109页/共211页第一百一十页，共211页。111 约束条件目标函数 (2) ,1,2,j , 0)( (1) )(minxgxfjTnjxxxxxgxf) ( )(),(:21 为非线性函数其中第110页/共211页第一百一十一页，共211页。112 (3) ,1,2,j ,

51、 0)( (2) , , 2 , 1 , 0)(1) )(minxgmixhxfji.)(),(),(:为非线性函数其中xgxhxfji第111页/共211页第一百一十二页，共211页。11306)2()2()(min212221xxxxxf解. 2)()(min, 3,),()(,)(*2*1xfxfxxDDcxfxf最小值得到最优解点在点等值线与直线相切于常数即的等值线作o2 22 26 66 61x2x) 3 , 3(D第112页/共211页第一百一十三页，共211页。114.)(min, 0)(, , 0)(, 2, 2, 06)(*2*121求得直接由事实上不起约束作用此时最优解位于

52、可行域内部若xfxxhxfxxxxxh 非线性规划的最优解可能(knng)在可行域的任一点达到。第113页/共211页第一百一十四页，共211页。115*) ()(0)()(,)(,)(, )( 121*xxnnxfxfxfxfxfxxfxfRxfEnR 这里的梯度在则必有局部极值为若上有一阶连续偏导数在上的某一开集维欧氏空间为设必要条件定理第114页/共211页第一百一十五页，共211页。116.,.0)( .,)()()( *点但平稳点不一定是极值稳点在区内部极值点必为平称为平稳点或驻点的点满足最快沿这个方向函数值增加处的法线方向在线等值面的方向为xfxxfxf第115页/共211页第一百

53、一十六页，共211页。117. )(,)()(, 0)(,)(, )(2*的严格局部极小点为则正定处的海赛矩阵在且若上有二阶连续偏导数在上的某一开集维欧氏空间为设充分条件定理xfxxHxxfxfRxRxfEnRn第116页/共211页第一百一十七页，共211页。118*2222122222212212212212* )(xxnnnnnxfxxfxxfxxfxfxxfxxfxxfxfxH 这里第117页/共211页第一百一十八页，共211页。119120440 84 0 044 84 )( 204282)(min 2*2*1212111222121xxxxxxxfxfxfxxxxxfTTT解求例

54、第118页/共211页第一百一十九页，共211页。12010)(1, 2,)(, 0164 00 4, 0444 00 4 )(*2*1*222122212212*xfxxxHxfxxfxxfxfxHxx极小值为严格局部极小点正定而第119页/共211页第一百二十页，共211页。121.)()()1 ()()()1 () 1 , 0(, )2() 1 ()2() 1 ()2() 1 (上的凸函数为则称若及为凸集设RXfXfXfXfXfRXXR.)()()1 ()()()1 ()2() 1 ()2() 1 (上的严格凸函数为则称若RXfXfXfXfXf.)()()1 ()()()1 ()2()

55、1 ()2() 1 (上的凹函数为则称若RXfXfXfXfXf.)()()1 ()()()1 ()2() 1 ()2() 1 (上的严格凹函数为则称若RXfXfXfXfXf第120页/共211页第一百二十一页，共211页。122)(xf)()1 ()()2() 1 (xfxf)1 ()2() 1 (xxf) 1 (x)2(xo凸函数x非凸非凹函数) 1 (x)2(xox)(xfx)1 ()2() 1 (xxf)()1 ()()2() 1 (xfxf凹函数) 1 (x)2(xo)(xf第121页/共211页第一百二十二页，共211页。123)()()()( ,)(,)(,) 1 () 1 ()2

56、() 1 () 1 ()2()2() 1 ()2() 1 (XXXfXfXfXXRXXRxfRxfRT恒有任意凸函数的充要条件是对上为在则上有一阶连续偏导数在为开凸集设一阶条件.)()(.)()()(,)(, )2(上为严格凸函数在正定则若上处处半正定在的海赛矩阵凸函数的充要条件是上为在则上有二阶连续偏导数在为开凸集设二阶条件RXfXHRXHXfRxfRxfR第122页/共211页第一百二十三页，共211页。124.10223)( 222121的凸性判别函数xxxxXf.)( 4 00 6 )( 222122212212为严格凸函数正定用二阶条件解XfxfxxfxxfxfXH第123页/共21

57、1页第一百二十四页，共211页。125.)(,)(, 1, 0)()(min为凹函数为凸函数其中XgXfljXgXRXfjjRX 第124页/共211页第一百二十五页，共211页。126第125页/共211页第一百二十六页，共211页。1270,01)(02)(44)(min21221221112221xxxxXgxxXgxxxXf., 2 00 2 )( )( 222122212212凸函数正定的海赛矩阵解xfxxfxxfxfXHXff第126页/共211页第一百二十七页，共211页。128., 0 0 0 2- )( .)( , 0 00 0 )(222212222122212222212

58、1212211221121凹函数半负定函数凸凹xgxxgxxgxgXHxgxxgxxgxgXHgg)( , )(21XgXg所以(suy)，该问题为凸规划。第127页/共211页第一百二十八页，共211页。1298 . 3)()34. 1 58. 0( ) (*2*1*XfxxXTT1x2xo11224)34. 1 ,58. 0(C0)(1Xg0)(2Xg28 . 3)(Xf第128页/共211页第一百二十九页，共211页。130.)2(1, ),(, )5()()(, )4( ) 3( )2(., ., 0 , ) 1 () 1()() 1()()() 1()()()()0(步继续迭代转否则

59、令若是则停止迭代近似极小点为极小点若检查应有令确定步长确定搜索方向不是极小点则转下一步若得通过迭代检查是否为最小点令选定某一初始点kkXXfXfPXXPXXkXkkkkkkkkkkk第129页/共211页第一百三十页，共211页。1312)() 1(1)() 1(0)()( 1kkkkXfXfXX绝对误差4)()() 1(3)()() 1(0)()()( 2kkkkkkXfXfXfXXX相对误差5)(0( )( 3kXfXf的模.,54321正数为事先给定的足够小的其中第130页/共211页第一百三十一页，共211页。132.)()(min为非线性函数XfXfnEX第131页/共211页第一百

60、三十二页，共211页。1330 ,.,)( )()()()()(*kkkkkPXXPXkXXXf作射线沿方向在次近似表示极小点的第以为极小点一阶解连续偏导数设有0)(lim )()()()( )( 0)()()(ooXfXfXfXXfTkkk其中展开成泰勒级数在将第132页/共211页第一百三十三页，共211页。134只要, )()( , , )(1cos180 .)( cos)()( .)(.)(,)()( 0)( )()()()()(0)()()()()()()()()()()() 1()()()()()(kkkkkkkkkkTkkkTkkkkkkkkTkXfXfXfXfPPXfPXfPX