清华大学运筹学全套课件完整版.ppt

1、运筹学运筹学（完整版）（完整版）12第一章第一章 线性规划与单纯形法线性规划与单纯形法1 1 线性规划问题及其数学模型线性规划问题及其数学模型1.1 1.1 问题的提出问题的提出 eg.1 生产计划问题 问：产品、各生产多少件，使利润最大？限制 设备台时128台时 材料A4016kg材料B0412kg利润23 分析：设：产品生产x1件，产品生产x2件。这里z为利润函数，max z:表示求z的最大值。目标函数：max z=2x1+3x2约束条件：1x1+2x2 8 4x1 16 4x2 12 x1，x2 0 3 eg.2 污水处理问题 环保要求河水含污低于2，河水可自身净化20%。问：化工厂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元/万m34线性规划的数学模型：线性规划的数学模型：max(min)z=c1x1+c2x2+cnxn a11x1+a12x2+a1nxn(=,)b1 a21x1+a22x2+a2nxn(=,)

3、b2 am1x1+am2x2+amnxn(=,)bm x1，x2，xn 05说明：(1)决策变量：x1，x2，xn。一组决策变量表示为问题的一个方案；(2)目标函数：max(min)z z为决策变量的线性函数;(3)约束条件 一组线性不等式。cj为价值系数,bi为资源，aij为技术系数(i=1,m;j=1,n).61.2 1.2 图解法图解法 eg.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 解：(

4、1)建立x x1 1-x x2 2坐标；x2x1 (2)约束条件的几何表示；Q1Q2Q3Q4 (3)目标函数的几何表示；*z z=2x2x1 1+3x3x2 2 o437 首先取z=0，然后，使z逐渐增大，直至找到最优解所对应的点。*可见，在Q2点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*438讨论：(1)唯一最优解 maxmax z z =z z*时，解唯

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

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

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

8、题化为标准型将下述问题化为标准型 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 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(

9、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 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 161.4 1.4 线性规划解的概念线性规划解的概念 设线性规划为 maxmax z z=CX CX AX AX=b b X X 0 0 A A为为m m n n矩阵矩阵,n

10、n m,Rankm,Rank A A=m(Am(A为行满秩矩阵）为行满秩矩阵）1 1、可行解：满足条件、可行解：满足条件、的的X X；2 2、最、最优优解：解：满满足足条件条件的可行解；的可行解；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为基变量，其它为非基变量。为基变量，其它为非基变量。17

11、4 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,ammmm 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 185、基可行解 满足式要求的基解。如右图所示，各边交点O,QO,Q1 1,Q,Q2 2,Q,Q3 3,Q,Q4 4均为基可行解；

12、而其延长线的交点Q5为基解，但不是基可行解。O(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为可行基。可行解可行解基可行解基可行解非可行解非可行解基解基解192 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-)

13、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)(2)凸集X X(1)(1)X X(2)(2)X X(2)(2)X X(1)(1)20 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

14、 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)的凸组合。的凸组合。2.2 2.2 基本定理基本定理 1 1、定理、定理1 1 若线性规划存在可行域，则若线性规划存在可行域，则:可行域可行域 D D=X|AXX|AX=b,Xb,X 00为凸集。为凸集。21 证明：证明：设设 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

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

16、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)T23 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)T243、人工基 eg.10 max z=x1+2x2+3x3 x1+3x2+2x3=3 2x1+x2+x3=4 x1,x

17、2,x3 0 分析：A=1 3 2 2 1 1 找不到单位矩阵基 引入人工变量为初始基变量（2个）253.2 3.2 最优性的检验与解的判别最优性的检验与解的判别26则27解的判别：1.若 ，则此时的基可行解为最优解；2.若存在某个非基变量 的检验数 ，且 ，则该线性规划问题具有无界解（或称无最优解）；3.若所有 ，又，对于某个非基变量 有 ，则该线性规划问题具有无穷多最优解。283.3 3.3 基变换基变换293.4 3.4 旋转运算（消元运算）旋转运算（消元运算）a1k 0 al-1k 0 pk=（alk）（1）al+1k 0 amk 0 得到基可行解，重复3.23.4，求出最优解。303

18、5 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+cn+mxn+m-z=0 1x1+2x2+nxn+0 xn+1 +0 xn+m-z=Z031 建立单纯形表cBxBbc1cncn+1cn+mx1xnxn+1xn+mcn+1xn+1b1a11a1n101cn+mxn+mbmam1amn01m -z -z01 n 00j eg.11 用单纯形法求解 max z

19、x1+3x2 x1+2x2 8 4x1 16 4x2 12 x1,x2 032 解：标准化，建立单纯形表 引入松弛变量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)=033 解的判别 1=1 2=3 0 x(0)非最优解 基变换 max1,2=3=2 x2入基

20、 min8/2,-,12/4=12/4 x5出基13000cBxBbx1x2x3x4x5 0 x38121000 x416400100 x5120400113000cBxBbx1x2x3x4x5 0 x38121008/20 x41640010-0 x5120400112/41300034此时的解：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/20 x4800-4123x2301001/400-10-1/413000此时的解：x(2)=(

21、2 3 0 8 0)Tz(2)=11x(2)为最优解 即：最优解：x*=(2 3 0 8 0)T 最大值：z*=1135X(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)364 4 单纯形法的进一步讨论单纯形法的进一步讨论4.1 4.1 人工变量法人工变量法 1、大M法（M为很大的正数）法则：对于max问题，人工变量在目标函数中的价值系数为-M；对于min问题，人工变量在目标函数中的价值系数为M。eg.12 min z=x1+5x2+

22、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 列单纯形表求解。37min 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中，选下标小的非基变量入基；对相同的最小比值，选下标小的基变量出基。第二章j与i的计算同max问题。46习题P45，1.4分别用图解

23、法和单纯形法求解下列线性规划,并指出单纯形法迭代的每一步相当于图形上的哪一个顶点？47第二章第二章对偶理论与灵敏度分析对偶理论与灵敏度分析1 1 单纯形法的矩阵描述单纯形法的矩阵描述 设max z=CX AX=b X 0 A为mn阶矩阵 RankA=m,取B为可行基,N为非基，484950求解步骤：5132利润12kg40材料B16kg04材料A8台时 21设备台时限制 2 2 对偶问题的提出对偶问题的提出 eg.1 制定生产计划 M1:max z=2x1+3x2 1x1+2x2 8 4x1 16 4x2 12 x1，x2 0 52 现在出租，设y1为设备单位台时的租金 y2,y3为材料A、B

24、转让附加费(kg-1)则M2为M1的对偶问题，反之亦然。M2:min w=8y1+16y2+12y3 y1+4y2 2 2y1 +4y3 3 y1,y2,y3 032利润12kg40材料B16kg04材料A8台时 21设备台时限制 53 一般的，原问题：max z=CX AX b X 0 对偶问题：min w=Yb YA C Y 0 比较：max z min w 决策变量为n个 约束条件为n个 约束条件为m个 决策变量为m个 “”“”543 3 对偶问题的化法对偶问题的化法 1、典型情况 eg.2 max z=x1+2x2+x3 2x1+x2 6 2x2+x3 8 x1,x2,x3 0对偶：m

25、in w=6y1+8y2 2y1 1 y1+2y2 2 y2 1 y1,y2 055 2、含等式的情况 eg.3 max z=x1+2x2+4x3 2x1+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-3x

26、3-356 3、含“”的max问题 eg.4 max z=x1+2x2+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-357一般:max问题第i个约束取“”，则min问题第i个变量 0；min问题第i个约束取“”，则max问题第i个变量 0；原问题第i个约束取等式，对偶问题第i个变量 无约束；max问题第j

27、个变量 0,则min问题第j个约束取“”；min问题第j个变量 0，则max问题第j个约束取“”；原问题第j个变量无约束，对偶问题第j个约束取等式。58 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=1 y1 0,y2 0,y3无约束 594 4 对偶问题的性质对偶问题的性质 1、对称性 对偶问题的对偶为原问题.606162推论：(1)max问题任一

28、可解的目标值为min问题目标值的一个下界；(2)min问题任一可解的目标值为max问题目标值的一个上界。3、无界性 若原问题(对偶问题)为无界解，则对偶问题(原问题)为无可行解。注：该性质的逆不存在。若原(对偶)问题为无可行解，对偶(原问题)问题或为无界解，或为无可行解。63 4、最优性 设X*，Y*分别为原问题和对偶问题可行解，当 CX*=Y*b时，X*，Y*分别为最优解。64 5、对偶定理 若原问题有最优解，那么对偶问题也有最优解，且目标值相等。65Y*为对偶问题的最优解，且原问题和对偶问题的目标值相等。证毕6、松弛性 若X*，Y*分别为原问题及对偶问题的可行解，那么Ys*X*=0，Y*X

29、s*=0，当且仅当X*，Y*分别为 最优解。证明：66将b,Cb,C分别代入目标函数：67其中：用分量表示：68 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对应的检验数 69 eg.6 已知：min w=20y1+20y2 的

30、最优解为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 ys3*x3*=0 ys4*x4*=070 y1*=1.2,y2*0.2 0 xs1*=xs2*=0 由 y1*+2y2*=1.6 1 ys1*

31、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*=4 xs1*=0 xs2*=0 最大值：z*=28=w*715 5 对偶问题的经济含义对偶问题的经济含义影子价格影子价格 最优情况：z*=w*=b1y1*+biyi*+bmym*x2x1Q2 eg.7 max z=2x1+3x2 x1+2x2 8 4x1 16 4x2 12

32、 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*b3：12 13 z*=0=y3*Q2Q2”726 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)；73(4)消元运算，得到新的XB。(3)基变换 出基变

33、量，入基变量，重复（2）-（4）步，求出结果。74 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 075-2-3-400CBXBbx1x2x3x4X50 x4-10 x5-4出出出x4,x5 0 最优最优解：最优解：x1*=2，x2*=0，x3*=0，x4*=1，x5*=0目标值：目标值：w*=-z*=4767 7 灵敏度分析灵敏度分析分析

34、变化对最优解的影响。7778例1 已知下述问题的最优解及最优单纯形表,79最优单纯形表如下:0-1/8-3/2000-1/81/2102311/2-2004001/4001420003280由最优单纯形表得:8182不可行!用对偶单纯形法计算83-3/4-1/20001/400103x23-1/2-1/41002x3001/40014x120-1/8-3/200 0-1/81/2102+2311/2-2004-8x5001/40014+0 x12ix5x4x3x2x1bXBCB00032x23/4-28485例2 求例1 c4的变化范围,使最优解不变.0-1/8-3/200 0-1/81/21

35、02311/2-2004x5001/40014x12ix5x4x3x2x1bXBCB00032x2解:86分析:87方法:例3 求例1 c2的变化范围,使最优解不变.0-1/8-3/200 0-1/81/2102311/2-2004x5001/40014x12ix5x4x3x2x1bXBCB00032x288解:0-1/8-3/200 0-1/81/2102311/2-2004x5001/40014x12ix5x4x3x2x1bXBCB00032x28990分析:9192例4 求例1 a24的变化范围,使最优解不变.解:93 例5 在例1的基础上，企业要增加一个新产品,每件产品需2个台时，原材

36、料A 6kg，原材料B 3kg，利润 5元/件，问如何安排各产品的产量，使利润最大？解：532利润12340料B16604料A8221设备b94表明生产新品有利。955/40-1/8-3/200 1/40-1/81/21023211/2-2004x503/201/40014x12x5x4x3x2x1bXBCB500032x2ix3965/40-1/8-3/200 1/40-1/81/21023211/2-2004x503/201/40014x12x5x4x3x2x1bXBCB500032x28/34/28ix320-5/8-7/16-1/400 0-1/8-3/163/4103/2311/21

37、/4-10020-3/4-1/83/2011x12x5x4x3x2x1bXBCB500032x2ix3x3597小结1、对偶问题及其化法原问题决策变量决定对偶问题约束条件关系原问题约束条件决定对偶问题决策变量取值方向。982、检验数的计算方法993、对偶问题的性质4、对偶单纯形法弱对偶性无界性最优性松弛性检验数与对偶问题的解1005、灵敏度分析101102第三章第三章 整数规划整数规划Integer Programming1 1 问题的提出问题的提出 eg.1 用集装箱托运货物 问：甲乙货物托运多少箱，使总利润最大？货物m3/箱百斤/箱百元/箱甲5220乙4510限制2413 分析：设x1为甲

38、货物托运箱数，x2为乙货物托运箱数。则 max z=20 x1+10 x2 5x1+4x2 24 2x1+5x2 13 x1,x2 0 x1,x2取整数103图解法：x1x243210124.82.6(4,1)x1*=4 x2*=1 zI*=90 104 一般，整数规划的最优解不会优于相应线性规划的最优解。对于max问题，zI*zl*对于min问题，zI*zl*数学模型：1052 2 分枝定界法分枝定界法 用单纯形法，去掉整数约束IP LP xl*判别是否整数解xI*=xl*Yes去掉非整数域No多个LP1063 0-13 0-1规划（规划（x xi i=0 0或或1 1的规划）的规划）eg.

39、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南区西区东区107 eg.3 求解如下0-1规划 max z=3x1-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)增

40、加一个过滤条件 3x1-2x2+5x33 *108(3)列表计算x1x2x3*可行？zx1x2x3*可行？z000001010011100101110111x1x2x3*可行？z0000001010011100101110111x1x2x3*可行？z00000015-11015010011100101110111x1x2x3*可行？z00000015-11015010-2011100101110111x1x2x3*可行？z00000015-11015010-2011315100101110111x1x2x3*可行？z00000015-11015010-201131510031110310111

41、0111x1x2x3*可行？z00000015-11015010-2011315100311103101802118110111x1x2x3*可行？z00000015-11015010-20113151003111031018021181101111x1x2x3*可行？z00000015-11015010-20113151003111031018021181101111626 最优解：x1*=1 x2*=0 x3*=1 此时，z*=8第四章109第四章第四章 非线性数规划非线性数规划 Nonlinear Programming1 1 问题的提出问题的提出 eg.1 某单位拟建一排厂房，厂房建筑

42、平面如图所示。由于资金及材料的限制，围墙及隔墙的总长度不能超过80米。为使建筑面积最大，应如何选择长宽尺寸？分析：设长为 米，宽为 米，则有 f(x)为非线性函数110例2 设某物理过程具有如下规律 用试验法 。现要确定参数 使所得试验点构成的曲线与理论曲线误差平方和为最小，且满足 111非线性规划：目标函数或（和）约束条件为非线性函数的规划。分析：f(x)为非线性函数，求最小。1122 2 基本概念2.1非线性规划的数学模型数学模型的一般描述113或1142.2非线性规划的图示例1 求解如下非线性规划问题o2 22 26 66 6115分析：非线性规划的最优解可能在可行域的任一点达到。116

43、2.3极值问题极值存在的条件1171181191201211222.4凸函熟与凸规划1、凸函熟与凹函熟123 函数f(x)图示1242、凸性的判别125例31263.凸函数的极值 对于定义在凸集上的凸函数，其极小点就是最小点，极小值就是最小值。4.凸规划 下述问题为凸规划.127 凸规划的局部最优解为全局最优解，当凸规 划的目标函数为严格凸函数时，若存在最优解，则最优解必定唯一。凸规划是一类比较简单而又具有重要理论意义的非线性规划。128例 如下非线性规划是否为凸规划：129 的海赛矩阵：所以，该问题为凸规划。130 如图所示，该问题最优解（最小点）在C点取得。1315.下降迭代算法 下降迭代

44、算法132几种终止迭代的准则：1333无约束非线性规划的解法无约束非线性规划的数学描述解法分类：解析法：用函数的解析性（一阶、二阶导数）。梯度法、共扼梯度法、变尺度法等。直接法：用问题的函数值。步长加速法。134梯度法1.基本原理135对于充分小的1362、求解步骤(1)137其中重复迭代，直至满足精度为止。138例139找下一点140于是141几何分析D D(1,1)(1,1)对于等值线为圆的无约束极小化问题，不管初始点选在哪里，只要一次迭代即可求得最优解。1424 有约束的非线性规划有约束非线性规划数学描述1434.1 库恩-塔克(Kuha-Tucker)条件1.几何说明144对于1452

45、库恩-塔克(Kuha-Tucker)条件 设146式中147例 用K-T条件求解如下非线性规划。148引入乘子149讨论：1504.2 二次规划二次规划的数学描述1511.二次规划的K-T条件求相应问题梯度152引拉格朗日乘子1532.线性规划描述引入松弛变量及人工变量154取155于是得到相应的线性规划问题。156 以157第五章 动态规划(Dynamic programming)1.引言 研究多阶段决策问题 R.E.Bellman 1951年提出动态规划。1957年出版Dynamic Programming 应用：最优调度、资源分配 最优路径、最优控制 设备更新、库存问题158 2.多阶

46、段决策问题例.某产品从A城运至F城，其间要经过若干 个城镇和若干条道路，路线结构如图所示，图中给出了每段道路的运费（元），试选 择一条合理的运输路线，使总运费最小？1591234分析：方案：AB1C1E1F 运费：26元 方案:AB3C3E3F 运费：22元 方案:AB2C1E2F 运费：18元 最优方案：方案160 3.基本概念1.阶段和阶段变量 阶段：过程的划分，包括时间、空间的划分，阶段数:n 阶段变量：描述阶段的变量用k 表示，k=1,2,.,n2.状态和状态变量状态：描述过程的必要信息。状态应具有无后效性:若给定了某阶段状态，则在这阶段以后过程的发展不受这阶段以前各阶段状态的影响.1

47、61状态变量：描述状态的变量，用s表示。1623.决策和决策变量决策：决定（选择），从一个阶段的状态到 下一个阶段状态的选择。决策变量：描述决策的变量，用u表示.1634.策略策略：决策按顺序构成的序列，用p表示。1641651661677.多阶段过程对于动态系统，12kn1688.多阶段决策过程 多阶段决策过程就是在各个阶段都要进行决策。12kn169数学描述1704 动态规划的基本方程4.1最优性原理1714.2基本方程设指标函数为172173174基本方程的解法17512kn逆推找决策划分阶段顺序定策略1761771781791801815 资源分配问题182183逆推求解184185

48、186187第六章 网络分析(Network Analysis)网络最大流问题1.问题的提出 交通系统：车辆流量 企业：物资流、信息流 信息系统（网络）：信息流 供水网络：水流量 金融系统：现金流188例：产品从产地 运往销售地点 ，图中给出了每段的运输能力，问：最大的运输能力为多少？(5,1)(3,3)(3,3)(2,2)(4,3)(2,1)(1,1)(1,1)分析：方案如图所示。流量=3+1=4 是否为最大？189 2 基本概念190191192193194195.3142 vvvvvvts196解：一.标号过程 197二.调整 198199200第七章 决策分析1 引言决策：从多个可行动

49、的方案中找出一个达到目标的最优解要素：1.决策者 2.方案（可控）3.事件（自然状态，不可控）4.准则 5.益损值2.风险决策201已知条件 事件出现的概率.方案.准则.益损值事件的概率益损值方案 202例.产品生产与销售 单位：万元203销量好 一般 差20412A10.31280.5200.213.614.8A10.316100.5160.2A10.312120.5120.2用决策树法决策 ：决策点,：方案,方案枝,概率枝 (1)画决策树，（2）用期望值准则决策。2053.不确定型决策事件出现的概率未知；方案、益损值、准则已知 1 乐观准则（maxmax）206例1.某产品每件成本价为0.5万元，正常售价为 0.7万元；若供大于求，则以0.4万元处理销售。拟定生产方案为100、200、300件，正常需求为100、200、300件。用乐观准则决策。解：求出益损值207208209210解：211212温馨提示：本PPT课件下载后，即可编辑修改，也可直接使用。（希望本课件对您有所帮助）