《线性规划－程－2次》PPT课件

《《线性规划－程－2次》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第一章线性规划程斌Email:qccbxn@sina.com本章主要内容线性规划问题及其建模线性规划问题几何求解与解情况分析线性规划标准型线性规划问题求解——单纯形法灵敏度分析运输问题计算机求解一、线性规划问题的提出在生产管理和经营活动中经常提出一类问题，即如何合理地利用有限的人力、物力、财力等资源，以便得到最好的经济效果。线性规划是由丹捷格（G.B.Dantzig）在1947提出的，并提出了求解线性规划的单纯形法，成为运筹学的标志性成就，被誉为「线性规划」之父。1939年前苏联学者康托洛维奇在解决工业生产组织和规划问题时，已提出类似线性规划的模型，并给出“解乘数法”的求解方

2、法。1960年再次发表《最佳资源利用的经济计算》,获经济学诺贝尔奖。例题1：生产计划问题引例某厂生产两种产品，需要三种资源，已知各产品的利润、各资源的限量和各产品的资源消耗系数如下表：问题：如何安排生产计划，使得获利最多？产品A产品B资源限量劳动力设备原材料9434510360200300利润元/kg70120解题步骤：1、确定决策变量：设生产A产品X1kg,B产品X2kg2、确定目标函数：maxZ=70X1+120X23、确定约束条件：人力约束9X1+4X2≤360设备约束4X1+5X2≤200原材料约束3X1+10X2≤300非负性约束X1≥0X2≥0综上所述，该问题的数

3、学模型表示为：问题一：任务分配问题：某车间有甲、乙两台机床，可用于加工三种工件.假定这两台车床的可用台时数分别为800和900，三种工件的数量分别为400、600和500，且已知用三种不同车床加工单位数量不同工件所需的台时数和加工费用如下表.问怎样分配车床的加工任务，才能既满足加工工件的要求，又使加工费用最低？例题2：车床加工安排问题解题步骤：1、确定决策变量：在甲车床上加工工件1、2、3的数量分别为x1、x2、x3，在乙车床上加工工件1、2、3的数量分别为x4、x5、x62、确定目标函数：minz=13x1+9x2+10x3+11x4+12x5+8x63、确定约束条件：工件

4、1、2、3约束X1+X4=400甲车床台时数约束0.4X1+1.1X2+x3≤800乙车床台时数约束0.5X1+1.2X2+1.3x3≤900非负性约束Xi≥0i=1..6综上所述，该问题的数学模型表示为：目标函数：Max(Min)z=c1x1+c2x2+…+cnxn约束条件：a11x1+a12x2+…+a1nxn≤(=,≥)b1a21x1+a22x2+…+a2nxn≤(=,≥)b2...am1x1+am2x2+…+amnxn≤(=,≥)bmx1，x2，…，xn≥0线性规划的一般形式二.线性规划问题的图解法若有线性规划问题：注：此方法只使用于两个决策变量的情况12341234

5、4x1=164x2=12x1+2x2=8Q1Q2Q3Q4可行域可行域与等值线123412344x1=164x2=12x1+2x2=8Q1Q2(4,2)Q3Q4可行域可行域：阴影区域中的每一个点（包括边界点）都是这个线性规划问题的解（称可行解），此区域是线性规划问题的解的集合，称为可行域。等值线最优方案，最大利润为14元x1x2最优解个数情况1.无穷多最优解上例中求解得到问题最优解是唯一的，但对一般线性规划问题，求解结果可能出现以下几种情况：1、无穷多最优解（多重最优解）若将上例中的目标函数变为maxz=2x1+4x2，目标函数中以参数z的这族等值线与约束条件x1+2x2≤8的

6、边界线平行。当z值由小变大时，将与线段Q2Q3重合。线段Q2Q3上任意一点都使z取得相同的最大值，故这个线性规划问题有无穷多最优解（多重最优解）。（4,2）（4,0）（0,0）（2,3）用图解法解下面的例子Maxz=2X1+4X2X1+2X2≤8(1)4X1≤16（2）4X2≤12（3）X1，X2≥0（4）无穷多最优解注意：多重解产生的原因，是因为目标函数线与第（1）条约束条件边界线的斜率相等。(1)(2)(3)(8,0)(0,4)2、无界解Maxz=x1+x2-2x1+x2≤4（1）x1－x2≤2（2）x1,x2≥0（3）（2，0）（0，4）（0，0）无界解（不等于无可行解

7、）在这里需要注意的是，可行域无界不等于问题无界，这要看目标函数的情况。如把该问题中目标函数x1的系数由原来的1改为－3/2时，该问题有最优解Z(0,4)＝4。3、无可行解Maxz=2x1+3x2x1+2x2≤8(1)4x1≤16(2)4x2≤12(3)-2x1+x2≥4(4)x1,x2≥0(5)（-2，0）（0，4）（4，0）（4，2）无可行解（约束条件无共同区域）图解法总结从图解法中直观地见到，当线性规划问题的可行域非空时，它是有界区域或无界凸多边形区域。若线性规划问题存在唯一最优解，它一定在有界可行