运筹学课件2012 第02章 线性规划的图解法.ppt

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

1、第二章线性规划的图解法1山西大学管理学院范建平博士在管理中一些典型的线性规划应用合理利用线材问题：如何在保证生产的条件下，下料最少配料问题：在原料供应量的限制下如何获取最大利润投资问题：从投资项目中选取方案，使投资回报最大产品生产计划：合理利用人力、物力、财力等，使获利最大劳动力安排：用最少的劳动力来满足工作的需要运输问题：如何制定调运方案，使总运费最小2山西大学管理学院范建平博士§1问题的提出例1.某工厂在计划期内要安排Ⅰ、Ⅱ两种产品的生产，已知生产单位产品所需的设备台时及A、B两种原材料的消耗、资源的限制，如下表：问题：工厂应分别生产多少单位Ⅰ、Ⅱ产品才能使工厂获利最多？线性规划模型：目标

2、函数：Maxz=50x1+100x2约束条件：s.t.x1+x2≤3002x1+x2≤400x2≤250x1,x2≥0ⅠⅡ资源限制设备11300台时原料A21400千克原料B01250千克单位产品获利50元100元3山西大学管理学院范建平博士基本概念线性规划：模型的目标函数与约束条件都为决策变量的线性函数。可行解：所有满足约束条件的解最优解：使目标函数值最大（小）的解。4山西大学管理学院范建平博士线性规划的三个要素决策变量决策问题待定的量值取值要求非负约束条件任何管理决策问题都是限定在一定的条件下求解把各种限制条件表示为一组等式或不等式称约束条件约束条件是决策方案可行的保障约束条件是决策变量的

3、线性函数目标函数衡量决策优劣的准则，如时间最省、利润最大、成本最低目标函数是决策变量的线性函数有的目标要实现极大，有的则要求极小5山西大学管理学院范建平博士§1问题的提出1.理解要解决的问题，了解解题的目标和条件；2.定义决策变量（x1，x2，…，xn），每一组值表示一个方案；3.用决策变量的线性函数形式写出目标函数，确定最大化或最小化目标；4.用一组决策变量的等式或不等式表示解决问题过程中必须遵循的约束条件建模过程6山西大学管理学院范建平博士模型隐含假定（1）线性化假定函数关系式f(x)=c1x1+c2x2+…+cnxn，称线性函数。建模技巧：将非线性的函数进行分段线性化。（2）同比例假定决

4、策变量变化引起目标函数和约束方程的改变量比例。（3）可加性假定决策变量对目标函数和约束方程的影响是独立于其他变量的。目标函数值是决策变量对目标函数贡献的总和。（4）连续性假定决策变量取值连续。（5）确定性假定所有参数都是确定的，不包含随机因素。7山西大学管理学院范建平博士线性规划模型的一般形式目标函数：Max（Min）z=c1x1+c2x2+…+cnxn约束条件：s.t.a11x1+a12x2+…+a1nxn≤（=,≥）b1a21x1+a22x2+…+a2nxn≤（=,≥）b2…………am1x1+am2x2+…+amnxn≤（=,≥）bmx1，x2，…，xn≥08山西大学管理学院范建平博士例1

5、.目标函数：Maxz=50x1+100x2约束条件：s.t.x1+x2≤300(A)2x1+x2≤400(B)x2≤250(C)x1≥0(D)x2≥0(E)得到最优解：x1=50，x2=250最优目标值z=27500§2图解法对于只有两个决策变量的线性规划问题，可以在平面直角坐标系上作图表示线性规划问题的有关概念，并求解。下面通过例1详细讲解其方法：9山西大学管理学院范建平博士§2图解法(1)分别取决策变量X1,X2为坐标向量建立直角坐标系。在直角坐标系里，图上任意一点的坐标代表了决策变量的一组值，例1的每个约束条件都代表一个半平面。x2x1X2≥0X2=0x2x1X1≥0X1=010山西大学

6、管理学院范建平博士§2图解法（2）对每个不等式(约束条件)，先取其等式在坐标系中作直线，然后确定不等式所决定的半平面。100200300100200300x1+x2≤300x1+x2=3001001002002x1+x2≤4002x1+x2=40030020030040011山西大学管理学院范建平博士§2图解法（3）把五个图合并成一个图，取各约束条件的公共部分，如图2-1所示。100100x2≤250x2=250200300200300x1x2x2=0x1=0x2=250x1+x2=3002x1+x2=400图2-1可行域，是凸集12山西大学管理学院范建平博士§2图解法（4）目标函数z=50x

7、1+100x2，当z取某一固定值时得到一条直线，直线上的每一点都具有相同的目标函数值，称之为“等值线”。平行移动等值线，当移动到B点时，z在可行域内实现了最大化。A，B，C，D，E是可行域的顶点，对有限个约束条件则其可行域的顶点也是有限的。x1x2z=20000=50x1+100x2图2-2z=27500=50x1+100x2z=0=50x1+100x2z=10000=50x1+100x2CBAD