清华运筹学学习教案

1、会计学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页/共45页第二页，编辑于星期二：二点 四十六分。3第2页/共45页第三页，编辑于星期二：二点 四十六分

2、。4 (1)决策变量：x1，x2，xn 。 一组决策变量表示为问题的一个方案； (2)目标函数：max(min)z z为决策变量的线性函数; (3)约束条件 一组线性不等式。cj为价值系数, bi为资源， aij为技术系数(i=1,m;j=1,n).第3页/共45页第四页，编辑于星期二：二点 四十六分。5 解： (1)建立x x1 1 - - x x2 2坐标；x2x1 (2)约束条件的几何表示； Q1Q2Q3Q4 (3)目标函数的几何表示； * z z = 2x2x1 1 + + 3x3x2 2 o43zxx313212第4页/共45页第五页，编辑于星期二：二点 四十六分。6* 可见，在Q2

3、点z取到最大值。 因此， 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页/共45页第六页，编辑于星期二：二点 四十六分。7 (2)无穷多最优解 eg.4 对eg.1，若目标函数 z z = 2x2x1 1 + + 4x4x2 2，此时表示 目标函数的直线与表示 条件的直线平行， 最优点在线段Q3Q2上。 即存在无穷

4、多最优解。x2x1Q1 Q2(4,2)Q3(2,3)Q4o43*第6页/共45页第七页，编辑于星期二：二点 四十六分。8o2241x2x第7页/共45页第八页，编辑于星期二：二点 四十六分。91124x1x2第8页/共45页第九页，编辑于星期二：二点 四十六分。10njxmibxaxczjinjjijnjjj, 10, 1 max11 ，简记：第9页/共45页第十页，编辑于星期二：二点 四十六分。11 njxbxptsCXzjnjjj, 1, 0 .max1TmjTmjjjjnTnbbbbxaaapcccCxxxX) ( :) ( ) ( ) (:21212121 的系数列向量其中第10页/共

5、45页第十一页，编辑于星期二：二点 四十六分。12为系数矩阵 212222111211 mnmmnnaaaaaaaaaA第11页/共45页第十二页，编辑于星期二：二点 四十六分。13 (2)(2)不等式不等式(，) 对于对于“”情况：在情况：在“”“”左边加上一个松弛变量（非负）左边加上一个松弛变量（非负），变为等式；变为等式； 对于对于“”“”情况：在情况：在“”“”左边减去一个剩余变量（非负），变为等左边减去一个剩余变量（非负），变为等式。式。 注意：松弛变量、剩余变量在目标函数中的价值系数为注意：松弛变量、剩余变量在目标函数中的价值系数为0 0。 (3)(3)无约束变量无约束变量 令令x

6、 xk k = x xk k - - x xk k”，x xk k,x,xk k” 0 0，代入即可。代入即可。 第12页/共45页第十三页，编辑于星期二：二点 四十六分。14解：令解：令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 + +

7、 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 第13页/共45页第十四页，编辑于星期二：二点 四十六分。15 1 1、可行解：满足条件、可行解：满足条件、的的X X； 2 2、最优解：满足、最优解：满足条件条件

8、的可行解；的可行解； 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为基变量，其它为非基变量。为基变量，其它为非基变量。第14页/共45页第十五页，编辑于星期二：二点 四十六分。16)!( !mnmnCmn基解个数TmnmTmBxxxXxxxbBX)0 , 0,

9、(),(m )0()0(2)0(1)0()0(2)0(11 个个基解：第15页/共45页第十六页，编辑于星期二：二点 四十六分。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、可行基 基可行解对应的B为可行基。可行解可行解基可行解基可行解非可行解非可行解基解基解第16页/共45页第十七页，编辑于星期二：二点 四十六分。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)(

10、2)X X(1)(1)第17页/共45页第十八页，编辑于星期二：二点 四十六分。191k1iik1i) i (iXX2.2 2.2 基本定理基本定理 1 1、定理、定理1 1 若线性规划存在可行域，则若线性规划存在可行域，则: : 可行域可行域 D D = X|AXX|AX = b,Xb,X 00为凸集。为凸集。第18页/共45页第十九页，编辑于星期二：二点 四十六分。20 2、定理2 线性规划的基可行解对应于可行域的顶点。 3、定理3 若线性规划有解，则一定存在基可行解为最优解。第19页/共45页第二十页，编辑于星期二：二点 四十六分。213.1 3.1 初始基可行解的确定初始基可行解的确定

11、 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 = 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页/共45页第二十一页，编辑于星期二：二点 四十六分。22 选 XB = (x1 x4)T 令x2 = x3

12、 = 0 则 初始基可行解：X(0) = (3 0 0 4)T B , 1 1 3 00 3 2 1 :414321ppppppA则解第21页/共45页第二十二页，编辑于星期二：二点 四十六分。23 分析： A = 1 3 2 2 1 1 找不到单位矩阵基 引入人工变量为初始基变量（2个）第22页/共45页第二十三页，编辑于星期二：二点 四十六分。24 mnjxmibxxaxcxczjnjiinjijmiininnjjj, 1 0, 1 max 111对于代入目标函数为非基变量可行为基变量设 , 1, , 1, 1 njjijiinjinxabxnjxmix第23页/共45页第二十四页，编辑于

13、星期二：二点 四十六分。25njjjnjjjjnjmijijinjmiiinnjminjjijiinjjxZxzcZxaccbcxabcxcz1010111111 )( )( )(miijinjjjjmiiinaczzcbcZ110 , , 其中第24页/共45页第二十五页，编辑于星期二：二点 四十六分。26. .的检验数为称jjxkx0knjj, 1, 0 0kp0j0kkx第25页/共45页第二十六页，编辑于星期二：二点 四十六分。27 为主元出基行对应的变量则若、出基变量 0minmin02lkllklikikiiiiikikiiaxlabaabaab为入基变量。则，若、入基变量kkjj

14、x 0max13.3 3.3 基变换基变换第26页/共45页第二十七页，编辑于星期二：二点 四十六分。28第27页/共45页第二十八页，编辑于星期二：二点 四十六分。29mn, 2 , 1j0 xbxxaxczmaxjiinn1jjijmn1jjj，设第28页/共45页第二十九页，编辑于星期二：二点 四十六分。30cBxBbc1cncn+1cn+mx1xnxn+1xn+mcn+1xn+1b1a11a1n101cn+mxn+mbmam1amn01m -z -z01 n 00j eg.11 用单纯形法求解 max z = x1 + 3x2 x1 + 2x2 8 4x1 16 4x2 12 x1,x

15、2 0第29页/共45页第三十页，编辑于星期二：二点 四十六分。31cBxBbx1x2x3x4x5 13000cBxBbx1x2x3x4x5 0 x38121000 x416400100 x51204001此时的解：x(0) = (0 0 8 16 12)Tz(0) = 0第30页/共45页第三十一页，编辑于星期二：二点 四十六分。32 1=1 2=3 0 x(0)非最优解 基变换 max1,2 = 3 = 2 x2入基 min8/2,-,12/4 = 12/4 x5出基13000cBxBbx1x2x3x4x5 0 x38121000 x416400100 x5120400113000cBxB

16、bx1x2x3x4x5 0 x38121008/20 x41640010-0 x5120400112/413000第31页/共45页第三十二页，编辑于星期二：二点 四十六分。330 x321010-1/22/10 x4164001016/43x2301001/4-1000-3/41x121010-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页/共45页第三十三页，编辑于星期二：二点 四十六分。34x2x1Q1

17、Q2(4,2)Q3(2,3)Q4*O(0,0)第33页/共45页第三十四页，编辑于星期二：二点 四十六分。35第34页/共45页第三十五页，编辑于星期二：二点 四十六分。361500McBxBbx1x2x3x4x5 0 x36231006/2Mx51210-111/21-2M5-M0M0第35页/共45页第三十六页，编辑于星期二：二点 四十六分。371500McBxBbx1x2x3x4x5 0 x350211-11x11/211/20-1/21/209/201/2M+1/21500McBxBbx1x2x3x4x5 0 x36231006/2Mx51210-111/21-2M5-M0M0第36页

18、/共45页第三十七页，编辑于星期二：二点 四十六分。38第37页/共45页第三十八页，编辑于星期二：二点 四十六分。39 mnjxmibxxaxxwjiinnjjijmnn, 1, 0, 1,min11第38页/共45页第三十九页，编辑于星期二：二点 四十六分。40第39页/共45页第四十页，编辑于星期二：二点 四十六分。41CBXBb0 x10 x20 x30 x41x5i0 x36231006/21x51210-111/2-2-10100 x350211-10 x11/211/20-1/2-1/21/200001第40页/共45页第四十一页，编辑于星期二：二点 四十六分。42CBXBb1x15x20 x30 x40 x3502111x11/211/20-1/2-1/209/201/2第41页/共45页第四十二页，编辑于星期二：二点 四十六分。43。基一般选下标小的变量入基可任取其中一个变量入值，有两个或两