第2章 线性规划的图解法-new.ppt

《第2章 线性规划的图解法-new.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第二章线性规划的图解法§1问题的提出§2图解法§3图解法的灵敏度分析1第二章线性规划的图解法在管理中一些典型的线性规划应用合理利用线材问题：如何在保证生产的条件下，下料最少配料问题：在原料供应量的限制下如何获取最大利润投资问题：从投资项目中选取方案，使投资回报最大产品生产计划：合理利用人力、物力、财力等，使获利最大劳动力安排：用最少的劳动力来满足工作的需要运输问题：如何制定调运方案，使总运费最小2线性规划的组成：目标函数maxf或minf约束条件s.t.(subjectto)满足于决策变量用符号来表示可控制的因素§1问题的提出3例1.某工厂在计划期内要安排Ⅰ、Ⅱ两种产品的生产

2、，已知生产单位产品所需的设备台时及A、B两种原材料的消耗、资源的限制，如下表：问题：工厂应分别生产多少单位Ⅰ、Ⅱ产品才能使工厂获利最多？线性规划模型：目标函数：maxz=50x1+100x2约束条件：s.t.x1+x2≤3002x1+x2≤400x2≤250x1,x2≥0§1问题的提出建模过程1.理解要解决的问题，明确在什么条件下，要追求什么目标；2.定义决策变量（x1，x2，…，xn），每一组值表示一个方案；3.用决策变量的线性函数形式写出目标函数，确定最大化或最小化目标；4.用一组决策变量的等式或不等式表示解决问题过程中必须遵循的约束条件一般形式目标函数：max（min）

3、z=c1x1+c2x2+…+cnxn约束条件：s.t.a11x1+a12x2+…+a1nxn≤（=,≥）b1a21x1+a22x2+…+a2nxn≤（=,≥）b2…………am1x1+am2x2+…+amnxn≤（=,≥）bmx1，x2，…，xn≥04例1.目标函数：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=275005§2图解法对于只有两个决策变量的线性规划问题，可以在平面直角坐标系上作图表示线性规划问题的有关概念，并求解。下

4、面通过例1详细讲解其方法：§2图解法(1)分别取决策变量X1,X2为坐标向量建立直角坐标系。在直角坐标系里，图上任意一点的坐标代表了决策变量的一组值，例1的每个约束条件都代表一个半平面。6x2x1X2≥0X2=0x2x1X1≥0X1=0§2图解法（2）对每个不等式(约束条件)，先取其等式在坐标系中作直线，然后确定不等式所决定的半平面。7100200300100200300x1+x2≤300x1+x2=3001001002002x1+x2≤4002x1+x2=400300200300400x1x1x2x2§2图解法（3）把五个图合并成一个图，取各约束条件的公共部分，如图2-1所

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

6、2CBADE§2图解法线性规划的标准化内容之一：——引入松驰变量（含义是资源的剩余量）例1中引入s1，s2，s3模型化为目标函数：maxz=50x1+100x2+0s1+0s2+0s3约束条件：s.t.x1+x2+s1=3002x1+x2+s2=400x2+s3=250x1,x2,s1,s2,s3≥0对于最优解x1=50x2=250，s1=0s2=50s3=0说明：生产50单位Ⅰ产品和250单位Ⅱ产品将消耗完所有可能的设备台时数及原料B，但对原料A则还剩余50千克。10§2图解法重要结论：如果线性规划有最优解，则一定有一个可行域的顶点对应一个最优解；无穷多个最优解。若将例1中

7、的目标函数变为maxz=50x1+50x2，则线段BC上的所有点都代表了最优解；无界解。即可行域的范围延伸到无穷远，目标函数值可以无穷大或无穷小。一般来说，这说明模型有错，忽略了一些必要的约束条件；无可行解。若在例1的数学模型中再增加一个约束条件4x1+3x2≥1200，则可行域为空域，不存在满足约束条件的解，当然也就不存在最优解了。11图解法–无界解线性规划存在无界解，即无最优解的情况。对下述线性规划问题：约束条件：maxz=x1+x2；x1-x2≤1-3x1+2x2≤6x1≥0,x2≥012图解法–