清华 运筹学ppt课件

1、1 1 线性规划问题及其数学模型线性规划问题及其数学模型1.1 1.1 问题的提出问题的提出 eg.1 eg.1 消费方案问题消费方案问题 问：产品问：产品、各消费多少件，各消费多少件， 使利润最大？使利润最大？ 限制 设备台时128台时 材料A4016kg材料B0412kg23 分析： 设：产品生产x1件， 产品生产x2件。这里z为利润函数， max z:表示求z的最大值。目标函数： max z = 2x1 + 3x2约束条件： 1x1 + 2x2 8 4x1 16 4x2 12 x1，x2 0 1eg.2eg.2污水处置问题污水处置问题 环保要求河水含污低于环保要求河水含污低于22，河水可

2、本身净化，河水可本身净化20%20%。 问：化工厂问：化工厂1 1、2 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元/万m32线性规划的数学模型：线性规划的数

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

4、用图解法求用图解法求eg.1eg.1。 max z = 2x1 + 3x2 max z = 2x1 + 3x2 1x1 + 2x2 8 1x1 + 2x2 8 4x1 16 4x1 16 4x2 12 4x2 12 x1 x1，x2 0 x2 0 解： (1)建立x1 - x2坐标；x2x1 (2)约束条件的几何表示； Q1Q2Q3Q4 (3)目的函数的几何表示； * z = 2x1 + 3x2 o43zxx3132125 首先取z = 0，然后，使z逐渐增大，直至找到最优解所对应的点。* 可见，在Q2点z取到最大值。 因此， Q2点所对应的解为最优解。 Q2点坐标为(4，2)。 即: x1

5、= 4，x2 = 2 由此求得最优解：x1* = 4 x2* = 2 最大值：max z = z* = 2x1 + 3x2 = 14(元)x2x1Q1Q2(4,2)Q3Q4*436讨论： (1)独一最优解 max z = z*时，解独一，如上例。 (2)无穷多最优解 eg.4 对eg.1，假设目的函数 z = 2x1 + 4x2，此时表示 目的函数的直线与表示 条件的直线平行， 最优点在线段Q3Q2上。 即存在无穷多最优解。x2x1Q1 Q2(4,2)Q3(2,3)Q4o43*7 (3)无界解 eg.5 max z = 2x1 + 3x2 4x1 16 x1，x2 0 那么x2 ，z 。 即存

6、在无界解。 在实践问题中，能够 是短少约束条件。o2241x2x8(4)无可行解 eg.6 max z = 2x1 + 3x2 2x1 + 4x2 8 x1 + x2 1 x1，x2 0 无公共部分，无可行域。 即无可行解。 在实践问题中，能够是关系错。1124x1x291.3 1.3 线性规划的规范型线性规划的规范型 1 1、规范型、规范型 max z = c1x1 + c2x2 + + cnxn max z = c1x1 + c2x2 + + cnxn a11x1 + a12x2 + + a1nxn = b1 a11x1 + a12x2 + + a1nxn = b1 a21x1 + a22

7、x2 + + a2nxn = b2 a21x1 + a22x2 + + a2nxn = b2 am1x1 + am2x2 + + amnxn = bm am1x1 + am2x2 + + amnxn = bm x1 x1，x2x2，xn 0 xn 0 njxmibxaxczjinjjijnjjj, 10, 1 max11 ，简记：10用向量表示 njxbxptsCXzjnjjj, 1, 0 .max1TmjTmjjjjnTnbbbbxaaapcccCxxxX) ( :) ( ) ( ) (:21212121 的系数列向量其中11 用矩阵描画为： max z = CX AX = b X 0 其中

8、: X = (x1,x2,xn)T C = (c1,c2,cn) b = (b1,b2,bm)T 为系数矩阵 212222111211 mnmmnnaaaaaaaaaA122 2、规范型的化法、规范型的化法 (1)minmax min z = cx = -max(-z) (1)minmax min z = cx = -max(-z) max(-z) = -min z = -cx max(-z) = -min z = -cx 令令z = -z z = -z 那么那么max z = -cxmax z = -cx (2)不等式(，) 对于“情况：在“左边加上一个松弛变量非负，变为等式； 对于“情况：

9、在“左边减去一个剩余变量非负，变为等式。 留意：松弛变量、剩余变量在目的函数中的价值系数为0。 (3)无约束变量 令xk = xk - xk，xk,xk 0，代入即可。 13eg.7eg.7将下述问题化为规范型将下述问题化为规范型 min z = -x1+2x2-3x3 min z = -x1+2x2-3x3 x1+ x2+ x3 7 x1+ x2+ x3 7 x1- x2+ x3 2 x1- x2+ x3 2 -3x1+ x2+2x3 = 5 -3x1+ x2+2x3 = 5 x1,x2 0 x1,x2 0，x3x3无约束无约束 解：令解：令x3 = x3x3 = x3-x3-x3，x3x3

10、,x3,x3 0 0； 式加上一个松弛变量式加上一个松弛变量x4x4；式减去一个剩余变量；式减去一个剩余变量x5x5； 令令z z = -z = -z max zmax z = x1- 2x2 + 3(x3 = x1- 2x2 + 3(x3 - x3 - x3) + 0 x4 + 0 x5) + 0 x4 + 0 x5 x1 + x2 + (x3 x1 + x2 + (x3 - x3 - x3) + x4 = 7) + x4 = 7 x1 - x2 + (x3 x1 - x2 + (x3 - x3 - x3) - x5 = 2) - x5 = 2 -3x1 + x2 + 2(x3 -3x1 +

11、 x2 + 2(x3 - x3 - x3) = 5) = 5 x1,x2,x3 x1,x2,x3,x3,x3,x4,x5 0 ,x4,x5 0 141.4 1.4 线性规划解的概念线性规划解的概念 设线性规划为设线性规划为 max z = CX max z = CX AX = b AX = b X 0 X 0 A A为为m m n n矩阵矩阵, n m, Rank A = m (A, n m, Rank A = m (A为行满秩矩阵为行满秩矩阵 1、可行解：满足条件、的X； 2、最优解：满足条件的可行解； 3、基：取B为A中的m m子矩阵，Rank B = m，那么称B为线性规 划问题的一个基

12、。 取B = (p1,p2,pm) pj = (a1j,a2j,amj)T 那么称x1,x2,xm为基变量，其它为非基变量。154 4、基解：取、基解：取B = (p1,p2,pm)B = (p1,p2,pm) a11,a1m x1 a1m+1,a1n xm+1 b1 a11,a1m x1 a1m+1,a1n xm+1 b1 + = + = am1,amm xm amm+1,amn xn bm am1,amm xm amm+1,amn xn bm 基基 基变量基变量 非基非基 非基变量非基变量 令令 xm+1 = = xn = 0 ( xm+1 = = xn = 0 (非基变量为非基变量为0)

13、0) 那么那么 BXB = b BXB = b )!( !mnmnCmn基解个数TmnmTmBxxxXxxxbBX)0 , 0,(),(m )0()0(2)0(1)0()0(2)0(11 个个基解：165、基可行解 满足式要求的基解。 如右图所示，各边交点O,Q1,Q2,Q3,Q4均为基可行解；而其延伸线的交点Q5为基解，但不是基可行解。O(0,0)O(0,0)Q1(4,0)Q1(4,0)Q2(4,2)Q2(4,2)Q4(0,3)Q4(0,3)Q3(2,3)Q3(2,3)Q5(4,3)Q5(4,3)6、可行基 基可行解对应的B为可行基。可行解可行解基可行解基可行解非可行解非可行解基解基解172

14、 2 线性规划问题的几何意义线性规划问题的几何意义2.1 2.1 根本概念根本概念 1 1、凸集：设、凸集：设K K为为En(nEn(n维欧式空间维欧式空间) )的一点集，的一点集，X(1)KX(1)K，X(2)KX(2)K。假设假设X(1)+(1-)X(2)KX(1)+(1-)X(2)K，那么称，那么称K K为凸集。为凸集。0101 非凸集X(1X(1) )X(1X(1) )X(2X(2) )X(2X(2) )凸集X(1X(1) )X(2X(2) )X(2X(2) )X(1X(1) )18 2、顶点：XK，X(1)K，X(2)K (恣意两点)。假设X不能用X(1)+(1-)X(2)表示，那么

15、称X为K的一个顶点。(01) 注：顶点所对应的解是基可行解。 3、凸组合：设X(i)En，假设存在0i1，i = 1,2,k，使 ,那么称X为X(i)(i=1,2,k)的凸组合。1k1iik1i) i (iXX2.2 2.2 根本定理根本定理 1 1、定理、定理1 1 假设线性规划存在可行域，那么假设线性规划存在可行域，那么: : 可行域可行域 D = X|AX = b,X 0 D = X|AX = b,X 0为凸集。为凸集。19 证明： 设 X(1)=(x1(1),x2(1),xn(1)T D； X(2)=(x1(2),x2(2),xn(2)T D； (X(1) X(2) 有 AX(1) =

16、 b， AX(2) = b 令 X = X(1) + (1 - )X(2) (0 0 1 0 X 0， 即D为凸集 2、定理2 线性规划的基可行解对应于可行域的顶点。 3、定理3 假设线性规划有解，那么一定存在基可行解为最优解。203 3 单纯形法单纯形法 根本思绪：从可行域的一个顶点到另一个顶点迭代求最优解。根本思绪：从可行域的一个顶点到另一个顶点迭代求最优解。3.1 3.1 初始基可行解确实定初始基可行解确实定 1 1、松弛基松弛变量对应的、松弛基松弛变量对应的B B eg.8max z = x1 + 3x2 eg.8max z = x1 + 3x2 x1 + 2x2 3 x1 + 2x2

17、 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 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则系数矩阵21 2、察看法 eg.9max z = x1 + 3x2 + 2x3 + x4 x1 + 2x2 + 3x3 = 3 3x2 + x3 + x4 = 4 x1,x2,

18、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 :414321ppppppA则解223、人工基 eg.10max z = x1 + 2x2 + 3x3 x1 + 3x2 + 2x3 = 3 2x1 + x2 + x3 = 4 x1,x2,x3 0 分析： A = 1 3 2 2 1 1 找不到单位矩阵基 引入人工变量为初始基变量2个233.2 3.2 最优性的检验与解的判别最优性的检验与解的判别 mnjxmibxxaxcxczjnjiinjijmiininnjjj, 1 0,

19、 1 max 111对于代入目标函数为非基变量可行为基变量设 , 1, , 1, 1 njjijiinjinxabxnjxmix24那么njjjnjjjjnjmijijinjmiiinnjminjjijiinjjxZxzcZxaccbcxabcxcz1010111111 )( )( )(miijinjjjjmiiinaczzcbcZ110 , , 其中25解的判别：1. 假设 ，那么此时的基可行解为最优解；2. 假设存在某个非基变量 的检验数 ，且 ，那么该线性规划问题具有无界解或称无最优解；3. 假设一切 ，又，对于某个非基变量 有 ，那么该线性规划问题具有无穷多最优解。. .的检验数为称j

20、jxkx0knjj, 1, 0 0kp0j0kkx26 为主元出基行对应的变量则若、出基变量 0minmin02lkllklikikiiiiikikiiaxlabaabaab为入基变量。则，若、入基变量kkjjx 0max13.3 3.3 基变换基变换273.4 3.4 旋转运算消元运算旋转运算消元运算 a1k a1k 0 0 al-1k al-1k 0 0 pk pk = = alkalk 1 1 al+1k al+1k 0 0 amk amk 0 0 得到基可行解，反复得到基可行解，反复3.23.43.23.4， 求出最优解。求出最优解。283.5 3.5 单纯形表单纯形表 展开如下：展开

21、如下： a11x1 + a12x2 + + a1nxn + xn+1 = b1 - cn+1 a11x1 + a12x2 + + a1nxn + xn+1 = b1 - cn+1 a21x1 + a22x2 + + a2nxn + xn+2 = b2 - cn+2 a21x1 + a22x2 + + a2nxn + xn+2 = b2 - cn+2 am1x1 + am2x2 + + amnxn + xn+m = bm - cn+m am1x1 + am2x2 + + amnxn + xn+m = bm - cn+m c1x1 + c2x2 + + cnxn + cn+1xn+1 + + cn

22、+mxn+m - z = 0 c1x1 + c2x2 + + cnxn + cn+1xn+1 + + cn+mxn+m - z = 0 1x1 + 1x1 + 2x2 + + 2x2 + + nxn + 0 xn+1 + + 0 xn+m - z = Z0 nxn + 0 xn+1 + + 0 xn+m - z = Z0mn, 2 , 1j0 xbxxaxczmaxjiinn1jjijmn1jjj，设29 建立单纯形表cBxBbc1cncn+1cn+mx1xnxn+1xn+mcn+1xn+1b1a11a1n101cn+mxn+mbmam1amn01m -z -z01 n 00j eg.11用单

23、纯形法求解 max z = x1 + 3x2 x1 + 2x2 8 4x1 16 4x2 12 x1,x2 030 解：规范化，建立单纯形表 引入松弛变量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) = 031 解的

24、判别 1=1 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/41300032此时的解：x(1)=(0 3 2 16 0)Tz(1)=9x(1)非最优x1入基 x3出基0 x321010-1/22/10 x4164001016/43x2301001/4-1000-3/41x121010-1/2

25、0 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* = 1133X(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)344 4 单纯形法的进一步讨论单纯形法的进一步讨论4.1 4.1 人工变量法人工变量法 1 1、大、大M M法法M M为很大的正数为很大的正数 法那么：对于法那么：对于maxmax问题，人工变量在目的函数中的价值系数为问题，人工变量在目的函数中的价值系数为