运筹学 第2章线性规划的图解法.ppt

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

1、管理运筹学朱晓辉管理科学与工程2-1第二章线性规划的图解法教学目标：掌握线性规划的数学模型，能够结合问题列出模型理解图解法求解了解图解法的灵敏度分析2-2第二章线性规划的图解法§1问题的提出§2图解法§3图解法的灵敏度分析2-3第二章线性规划的图解法在管理中一些典型的线性规划应用:合理利用线材问题：如何在保证生产的条件下，下料最少配料问题：在原料供应量的限制下如何获取最大利润投资问题：从投资项目中选取方案，使投资回报最大产品生产计划：合理利用人力、物力、财力等，使获利最大劳动力安排：用最少的劳动力来满足工作的需要

2、运输问题：如何制定调运方案，使总运费最小2-4线性规划的组成：目标函数MaxF或MinF约束条件s.t.(subjectto)满足于决策变量用符号来表示可控制的因素§1问题的提出2-5例1.某工厂在计划期内要安排Ⅰ、Ⅱ两种产品的生产，已知生产单位产品所需的设备台时及A、B两种原材料的消耗、资源的限制，如下表：问题：工厂应分别生产多少单位Ⅰ、Ⅱ产品才能使工厂获利最多？线性规划模型：目标函数：Maxz=50x1+100x2约束条件：s.t.x1+x2≤3002x1+x2≤400x2≤250x1,x2≥0把满足所有约束

3、条件的解称为该线性规划的可行解。把使得目标函数值最大（即利润最大）的可行解称为该线性规划的最优解，此目标函数值称为最优目标函数值，简称最优值。2-6§1问题的提出建模过程1.理解要解决的问题，了解解题的目标和条件；2.定义决策变量（x1，x2，…，xn），每一组值表示一个方案；3.用决策变量的线性函数形式写出目标函数，确定最大化或最小化目标；4.用一组决策变量的等式或不等式表示解决问题过程中必须遵循的约束条件一般形式:目标函数：Max（Min）z=c1x1+c2x2+…+cnxn约束条件：s.t.a11x1+a1

4、2x2+…+a1nxn≤（=,≥）b1a21x1+a22x2+…+a2nxn≤（=,≥）b2…………am1x1+am2x2+…+amnxn≤（=,≥）bmx1，x2，…，xn≥02-7练习题：某公司由于生产需要，共需要A，B两种原料至少350吨(A，B两种原料有一定替代性)，其中原料A至少购进125t．但由于A，B两种原料的规格不同，各自所需的加工时间也是不同的，加工每吨原料A需要2小时，加工每吨原料B需要1小时，而公司总共有600个加工时数．又知道每吨原料A的价格为2万元，每吨原料B的价格为3万元，试问在满足生

5、产需要的前提下，在公司加工能力的范围内，如何购买A，B两种原料，使得购进成本最低?2-8例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=275002-9§2图解法对于只有两个决策变量的线性规划问题，可以在平面直角坐标系上作图表示线性规划问题的有关概念，并求解。下面通过例1详细讲解其方法：§2图解法(1)分别取决策变量X1,X2为坐标向量建立直角坐标系。在

6、直角坐标系里，图上任意一点的坐标代表了决策变量的一组值，例1的每个约束条件都代表一个半平面。2-10x2x1X2≥0X2=0x2x1X1≥0X1=0§2图解法（2）对每个不等式(约束条件)，先取其等式在坐标系中作直线，然后确定不等式所决定的半平面。2-11100200300100200300x1+x2≤300x1+x2=3001001002002x1+x2≤4002x1+x2=400300200300400§2图解法（3）把五个图合并成一个图，取各约束条件的公共部分(包括五条边界线)，如图2-1所示。2-1210

7、0100x2≤250x2=250200300200300x1x2x2=0x1=0x2=250x1+x2=3002x1+x2=400图2-1可行域可行域的几何形状由于问题不同可以千变万化，但可行域的几何结构是凸集要求集合中的任何两点的连线段落在这个集合中2-13§2图解法（4）目标函数z=50x1+100x2，当z取某一固定值时得到一条直线，直线上的每一点都具有相同的目标函数值，称之为“等值线”。平行移动等值线，当移动到B点时，z在可行域内实现了最大化。A，B，C，D，E是可行域的顶点，对有限个约束条件则其可行域的

8、顶点也是有限的。2-14x1x2z=20000=50x1+100x2图2-2z=27500=50x1+100x2z=0=50x1+100x2z=10000=50x1+100x2CBADE§2图解法重要结论：如果线性规划有最优解，则一定有一个可行域的顶点对应一个最优解；无穷多个最优解。若将例1中的目标函数变为maxz=50x1+50x2，则线段BC上的所有点都代表了最优解；