线性规划模型ppt课件.ppt

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

1、第1节线性规划问题与模型一、线性规划模型从招聘总经理谈起1泰山工厂生产状况泰山工厂可以生产两种产品出售，需要三种资源，已知各产品的利润、各资源的限量和各产品的资源消耗系数如下表：目前生产现状：不生产产品A，生产产品B每天30，获利3600产品A产品B资源限量设备劳动力原材料9434510360200300利润元/kg701202招聘总经理！约翰：我应聘！在现有资源状况下，我可以使利润达到4280！方案是：生产A产品20，生产B产品24可行性：9*20+4*24=276<3604*20+5*24=2003*20+10*24=3003怎么达到的？约翰使

2、用了运筹学中的线性规划模型问题：如何安排生产计划，使得获利最多？步骤：1、确定决策变量：设生产A产品x1kg,B产品x2kg2、确定目标函数：maxZ=70X1+120X23、确定约束条件：设备约束9X1+4X2≤360人力约束4X1+5X2≤200原材料约束3X1+10X2≤300非负性约束X1≥0X2≥04线性规划图解法由数学知识可知：y=ax+b是一条直线，同理：Z=70x1+120x2→x2=70/120x1-Z/120也是一条直线，以Z为参数的一族等值线。9x1+4x2≤360→x1≤360/9-4/9x2是直线x1=360/9-4/9x

3、2下方的半平面。所有半平面的交集称之为可行域，可行域内的任意一点，就是满足所有约束条件的解，称之为可行解。5例1图示.9080604020020406080100x1x29x1+4x2≤3604x1+5x2≤2003x1+10x2≤300ABCDEFGHIZ=70x1+120x26最优解：X1=20,x2=24对应的生产方案：生产A产品20生产B产品24获利：70*20+120*24=42807约翰就任泰山工厂总经理！8二、线性规划图解法例2.某工厂在计划期内要安排Ⅰ、Ⅱ两种产品的生产，已知生产单位产品所需的设备台时及A、B两种原材料的消耗、资源的

4、限制，如下表：问题：工厂应分别生产多少单位Ⅰ、Ⅱ产品才能使工厂获利最多？线性规划模型：目标函数：Maxz=50x1+100x2约束条件：s.t.x1+x2≤3002x1+x2≤400x2≤250x1,x2≥09例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=27500图解法对于只有两个决策变量的线性规划问题，可以在平面直角坐标系上作图表示线性规划问题的有关概念，并求解。下面通过例1详细讲解

5、其方法：10线性规划图解法（续）(1)分别取决策变量X1,X2为坐标向量建立直角坐标系。在直角坐标系里，图上任意一点的坐标代表了决策变量的一组值，例1的每个约束条件都代表一个半平面。x2x1X2≥0X2=0x2x1X1≥0X1=011线性规划图解法（续）（2）对每个不等式(约束条件)，先取其等式在坐标系中作直线，然后确定不等式所决定的半平面。100200300100200300x1+x2≤300x1+x2=3001001002002x1+x2≤4002x1+x2=40030020030040012线性规划图解法（续）（3）把五个图合并成一个图，取各

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

7、z=0=50x1+100x2z=10000=50x1+100x2CBADE14线性规划图解法（续）重要结论：如果线性规划有最优解，则一定有一个可行域的顶点对应一个最优解；无穷多个最优解。若将例1中的目标函数变为maxz=50x1+50x2，则线段BC上的所有点都代表了最优解；无界解。即可行域的范围延伸到无穷远，目标函数值可以无穷大或无穷小。一般来说，这说明模型有错，忽略了一些必要的约束条件；无可行解。若在例1的数学模型中再增加一个约束条件4x1+3x2≥1200，则可行域为空域，不存在满足约束条件的解，当然也就不存在最优解了。15线性规划图解法（续

8、）例2某公司由于生产需要，共需要A，B两种原料至少350吨（A，B两种材料有一定替代性），其中A原料至少购进125吨。但由