运筹学 第一章 线性规划与单纯形法课件.ppt

《运筹学 第一章 线性规划与单纯形法课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第一章线性规划与单纯形法§1线性规划问题及其数学模型1.1问题的提出[eg.1]生产计划问题问：产品Ⅰ、Ⅱ各生产多少件，使利润最大？ⅠⅡ限制设备台时128台时材料A4016kg材料B0412kg利润23分析：设：产品Ⅰ生产x1件，产品Ⅱ生产x2件。这里z为利润函数，maxz:表示求z的最大值。目标函数：maxz=2x1+3x2约束条件：1x1+2x2≤84x1≤164x2≤12x1，x2≥01[eg.2]污水处理问题环保要求河水含污低于2‰，河水可自身净化20%。问：化工厂1、2每天各处理多少污水，使总费用最少？分析：化工

2、厂1处理污水x1万m3,化工厂2处理污水x2万m3。minz=1000x1+800x2(2-x1)/500≤2/1000[(1-0.2)(2-x1)+1.4-x2]/(500+200)≤2/1000x1≤2x2≤1.4x1，x2≥0这里minz:表示求z的最小值。200万m3500万m32万m31.4万m3化工厂1化工厂21000元/万m3800元/万m32线性规划的数学模型：max(min)z=c1x1+c2x2+···+cnxna11x1+a12x2+···+a1nxn≤(=,≥)b1a21x1+a22x2+···+a

3、2nxn≤(=,≥)b2┆┆am1x1+am2x2+···+amnxn≤(=,≥)bmx1，x2，···，xn≥03说明：(1)决策变量：x1，x2，···，xn。一组决策变量表示为问题的一个方案；(2)目标函数：max(min)zz为决策变量的线性函数;(3)约束条件一组线性不等式。cj为价值系数,bi为资源，aij为技术系数(i=1,…,m;j=1,…,n).41.2图解法[eg.3]用图解法求eg.1。maxz=2x1+3x21x1+2x2≤8①4x1≤16②4x2≤12③x1，x2≥0解：(1)建立x1-x2坐标；

4、x2x1(2)约束条件的几何表示；①②Q1Q2③Q3Q4(3)目标函数的几何表示；*z=2x1+3x2o435首先取z=0，然后，使z逐渐增大，直至找到最优解所对应的点。*可见，在Q2点z取到最大值。因此，Q2点所对应的解为最优解。Q2点坐标为(4，2)。即:x1=4，x2=2∴由此求得最优解：x1*=4x2*=2最大值：maxz=z*=2x1+3x2=14(元)x2x1①②Q1Q2(4,2)③Q3Q4*436讨论：(1)唯一最优解maxz=z*时，解唯一，如上例。(2)无穷多最优解[eg.4]对eg.1，若目标函数z=

5、2x1+4x2，此时表示目标函数的直线与表示条件①的直线平行，最优点在线段Q3Q2上。即存在无穷多最优解。x2x1②Q1Q2(4,2)③Q3(2,3)Q4o43*①7(3)无界解[eg.5]maxz=2x1+3x24x1≤16x1，x2≥0则x2→∞，z→∞。即存在无界解。在实际问题中，可能是缺少约束条件。o2248(4)无可行解[eg.6]maxz=2x1+3x22x1+4x2≥8x1+x2≤1x1，x2≥0无公共部分，无可行域。即无可行解。在实际问题中，可能是关系错。1124x1x291.3线性规划的标准型1、标准型m

6、axz=c1x1+c2x2+···+cnxna11x1+a12x2+···+a1nxn=b1a21x1+a22x2+···+a2nxn=b2┆┆am1x1+am2x2+···+amnxn=bmx1，x2，···，xn≥010用向量表示11用矩阵描述为：maxz=CXAX=bX≥0其中:X=(x1,x2,···,xn)TC=(c1,c2,···,cn)b=(b1,b2,···,bm)T122、标准型的化法(1)min→max∵minz=cx=-max(-z)∴max(-z)=-minz=-cx令z’=-z则maxz’=-cx

7、(2)不等式(≤，≥)对于“≤”情况：在“≤”左边加上一个松弛变量（非负），变为等式；对于“≥”情况：在“≥”左边减去一个剩余变量（非负），变为等式。注意：松弛变量、剩余变量在目标函数中的价值系数为0。(3)无约束变量令xk=xk’-xk”，xk’,xk”≥0，代入即可。13[eg.7]将下述问题化为标准型minz=-x1+2x2-3x3x1+x2+x3≤7①x1-x2+x3≥2②-3x1+x2+2x3=5③x1,x2≥0，x3无约束解：令x3=x3’-x3”，x3’,x3”≥0；①式加上一个松弛变量x4；②式减去一个剩余

8、变量x5；令z’=-zmaxz’=x1-2x2+3(x3’-x3”)+0x4+0x5x1+x2+(x3’-x3”)+x4=7x1-x2+(x3’-x3”)-x5=2-3x1+x2+2(x3’-x3”)=5x1,x2,x3’,x3”,x4,x5≥0141.4线性规划解的概念设线性规划为maxz=CX①A