清华大学《运筹学》教材相应的授课文档.第一章.ppt

1、1,第一章线性规划与单纯形法,1 线性规划问题及其数学模型 1.1 问题的提出 eg.1 生产计划问题 问：产品、各生产多少件， 使利润最大？,2,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的最小值。,

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

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

4、： (1)唯一最优解 max z = z*时，解唯一，如上例。,(2)无穷多最优解 eg.4 对eg.1，若目标函数 z = 2x1 + 4x2，此时表示 目标函数的直线与表示 条件的直线平行， 最优点在线段Q3Q2上。 即存在无穷多最优解。,8,(3)无界解 eg.5 max z = 2x1 + 3x2 4x1 16 x1，x2 0 则x2 ，z 。 即存在无界解。 在实际问题中，可能 是缺少约束条件。,9,(4)无可行解 eg.6 max z = 2x1 + 3x2 2x1 + 4x2 8 x1 + x2 1 x1，x2 0 无公共部分，无可行域。 即无可行解。 在实际问题中，可能是关系错

5、。,10,1.3 线性规划的标准型 1、标准型 max z = c1x1 + c2x2 + + cnxn a11x1 + a12x2 + + a1nxn = b1 a21x1 + a22x2 + + a2nxn = b2 am1x1 + am2x2 + + amnxn = bm x1，x2，xn 0,11,用向量表示,12,用矩阵描述为： max z = CX AX = b X 0 其中: X = (x1,x2,xn)T C = (c1,c2,cn) b = (b1,b2,bm)T,13,2、标准型的化法 (1)minmax min z = cx = -max(-z) max(-z) = -m

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

7、4；式减去一个剩余变量x5； 令z = -z max z = x1- 2x2 + 3(x3 - x3”) + 0 x4 + 0 x5 x1 + x2 + (x3 - x3”) + x4 = 7 x1 - x2 + (x3 - x3”) - x5 = 2 -3x1 + x2 + 2(x3 - x3”) = 5 x1,x2,x3,x3”,x4,x5 0,15,1.4 线性规划解的概念 设线性规划为 max z = CX AX = b X 0 A为m n矩阵, n m, Rank A = m (A为行满秩矩阵）,1、可行解：满足条件、的X；,2、最优解：满足条件的可行解；,3、基：取B为A中的m m

8、子矩阵，Rank B = m，则称B为线性规 划问题的一个基。 取B = (p1,p2,pm) pj = (a1j,a2j,amj)T 则称x1,x2,xm为基变量，其它为非基变量。,16,4、基解：取B = (p1,p2,pm) a11,a1m x1 a1m+1,a1n xm+1 b1 + = am1,amm xm amm+1,amn xn bm 基 基变量 非基 非基变量 令 xm+1 = = xn = 0 (非基变量为0) 则 BXB = b ,17,5、基可行解 满足式要求的基解。 如右图所示，各边交点O,Q1,Q2,Q3,Q4 均为基可行解；而其延长线的交点Q5为 基解，但不是基可行

9、解。,O(0,0),Q1(4,0),Q2(4,2),Q4(0,3),Q3(2,3),Q5(4,3),6、可行基 基可行解对应的B为可行基。,18,2 线性规划问题的几何意义 2.1 基本概念 1、凸集：设K为En(n维欧式空间)的一点集，X(1)K，X(2)K。 若X(1)+(1-)X(2)K，则称K为凸集。（01）,19,2、顶点：XK，X(1)K，X(2)K (任意两点)。若X不能用X(1)+(1-)X(2)表示，则称X为K的一个顶点。(01) 注：顶点所对应的解是基可行解。 3、凸组合：设X(i)En，若存在0i1，i = 1,2,k， 使 ,则称X为X(i)(i=1,2,k)的凸组合。

10、,2.2 基本定理 1、定理1 若线性规划存在可行域，则: 可行域 D = X|AX = b,X 0为凸集。,20,证明： 设 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) = b， AX(2) = b 令 X = X(1) + (1 - )X(2) (0 0 1 0 X 0， 即D为凸集,2、定理2 线性规划的基可行解对应于可行域的顶点。,3、定理3 若线性规划有解，则一定存在基可行解为最优解。,21,3 单纯形法 基本思路：从可行域的一个顶点到另一个顶点迭代求最优解。,3.1 初始基可行

11、解的确定 1、松弛基（松弛变量对应的B） eg.8max 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,22,2、观察法 eg.9max z = x1 + 3x2 + 2x3 + x4 x1 + 2x2 + 3x3 = 3 3x2 + x3 + x4 = 4 x1,x2,x3,x4 0,选 X

12、B = (x1 x4)T 令x2 = x3 = 0 则 初始基可行解：X(0) = (3 0 0 4)T,23,3、人工基 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个）,24,3.2 最优性的检验与解的判别,25,则,26,解的判别： 1. 若 ，则此时的基可行解为最优解； 2. 若存在某个非基变量 的检验数 ，且 ，则该线性规划问题具有无界解（或称无最优解）； 3. 若所有 ，又，对于某个非基变量

13、 有 ，则该线性规划问题具有无穷多最优解。,27,3.3 基变换,28,3.4 旋转运算（消元运算） a1k 0 al-1k 0 pk = （alk） （1） al+1k 0 amk 0 得到基可行解，重复3.23.4， 求出最优解。,29,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+m c1x1 + c2x2 + + cnxn + cn+1xn+1 + +

14、 cn+mxn+m - z = 0 1x1 + 2x2 + + nxn + 0 xn+1 + + 0 xn+m - z = Z0,30,建立单纯形表,eg.11用单纯形法求解 max z = x1 + 3x2 x1 + 2x2 8 4x1 16 4x2 12 x1,x2 0,31,解：标准化，建立单纯形表 引入松弛变量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,此时的解： x(0) = (0 0 8 16 1

15、2)T z(0) = 0,32,解的判别,1=1 2=3 0 x(0)非最优解,基变换 max1,2 = 3 = 2 x2入基 min8/2,-,12/4 = 12/4 x5出基,33,此时的解： x(1)=(0 3 2 16 0)T z(1)=9 x(1)非最优 x1入基 x3出基,此时的解： x(2)=(2 3 0 8 0)T z(2)=11 x(2)为最优解,即： 最优解：x* = (2 3 0 8 0)T 最大值：z* = 11,34,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

16、,3),35,4 单纯形法的进一步讨论 4.1 人工变量法 1、大M法（M为很大的正数） 法则：对于max问题，人工变量在目标函数中的价值系数为-M； 对于min问题，人工变量在目标函数中的价值系数为M。 eg.12min 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 列单纯形表求解。,

17、36,min z = x1 + 5x2 + 0 x3 + 0 x4 +Mx5 2x1 + 3x2 + x3 = 6 2x1 + x2 x4 + x5 = 1 x1,x2,x3,x4,x5 0 对于min问题，若 minj0= k ,则xk为入基变量。 这里：x1为入基变量， x5为出基变量，a21=2为主元。,37,进一步迭代,38,因为所有j0 ，于是得问题的最优解： 最优解：X*=(x1 x2 x3 x4 x5)T =(1/2 0 5 0 0)T 目标函数最小值：Z*=1/2 2. 两阶段法 由于大M不是一个确定的数，所以大M法适宜于手工 计算，而不适合求解。为此，引入两阶段法。 第一阶段

18、： 给线性规划加入人工变量，并构造辅助规划。辅助 规划的目标函数为 min w =xn+1+xn+m 这里 xn+1,xn+m为人工变量。,39,以人工变量为初始基变量,列表计算。若本阶段无最优解，表示原线性规划无解，停止计算；若有最优解，则转第二阶段。 第二阶段： 在第一阶段最优表中，去掉人工变量，换上原问题目标函数，作为本阶段初始表，以此用单纯形法进行迭代运算，求出结果。,40,例13 用两阶段法求解 min z = x1 + 5x2 2x1 + 3x2 6 2x1 + x2 1 x1,x2 0 解：第一阶段： 将问题化为等式约束 引进人工变量x5得辅助规划： min z = x1 + 5x2+0 x3+0 x4 min w = x5 2x1 + 3x2 +x3 = 6 2x1 + 3x2 +x3 = 6 2x1 + x2 x4 = 1 2x1 + x2 x4 +x5 = 1 x1,x2 ,x3,x4 0 x1,x2,x3,x4,x5 0,41,min w = x5 2x1 + 3x2 +x3 = 6 2x1 + x2 x4 +x5 = 1 x1,x2,x3,x4,x5 0,42,第一阶段有最优解。 第二阶