《线性规划的图解法》PPT课件.ppt

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

1、第二章线性规划的图解法一、线性规划问题及其数学模型二、图解法三、线性规划问题的一般形式和标准形式四、图解法的灵敏度分析本章主要内容一、线性规划问题及其数学模型（1）实际模型：建筑设计师运用小型模型帮助他们设计新大楼；汽车设计师建立新型汽车的模型来检测设计指标，或用撞车试验来模拟乘车人在汽车事故中所受的影响等。（2）数学模型：运筹学模型是数学模型或计算机模型。在运筹学模型中，反映现实世界的关系用数学等式或逻辑描述表示。（3）线性规划模型：属于最优化模型。最优化模型解决求最大利润、最小成本、最大回报率等问题。例如：P11的例1。1、关于模型2.几个概念：（1）线性——变量之间呈正比例关系

2、或一次相加关系；如：y=2x；y=x+6；y=5x1+9x2等。（2）函数——两个变量x和y，对于某一范围内的、x的每一个取值，y都有一个或几个值和它对应，y就是x的函数。（3）目标函数——问题中要确定的未知量（称决策变量）的函数关系式；如：maxz=2x1+x2（4）约束条件——决策变量取值时受到的各种资源条件的限制，通常表达为含决策变量的线性方程或不等式。（1）由决策变量构成，反映决策的目标是线性函数；3.线性规划模型的特征（2）一组由决策变量的线性等式或不等式构成约束条件；（3）对决策变量取值范围加以限制的非负约束。4.建立一个问题的线性规划模型的一般步骤（1）确定决策变量；（

3、2）确定目标函数；（3）确定约束条件；（4）确定变量是否有非负约束。练习1：资源利用问题单件消耗产品Ⅰ产品Ⅱ现有量资源12212资源2128资源34016资源40412单件利润（万元）23要求：在资源有限情况下求总利润最大的生产计划。解：设产品Ⅰ、Ⅱ各生产x1、x2件，总利润Z；MaxZ=2x1+3x22x1+2x2≤12x1+2x2≤84x1≤164x2≤12x1，x2≥0（资源1）（资源2）（资源3）（资源4）目标函数约束条件练习2：污水处理问题清500万M3/天清200万M3/天甲污2万M3/天A(1000元/万M3)乙污1.4万M3/天B(800元/万M3)污水进入河道后20

4、%自然净化，要求污水含量≤2‰求总费用最少的处理方案。解：设甲乙厂各处理x1、x2万M3/天；总费用Z元/天；考虑A、B两点：则有：目标函数MinZ=1000x1+800x2x1≥1（A点）0.8x1+x2≥1.6（B点）x1≤2（甲排放量限制）x2≤1.4（乙排放量限制）x1，x2≥0约束条件练习3：生产计划问题某车间在每个生产期5天所需要的某种刀具的统计资料如下：日期12345刀具数12085160145300每一把刀具成本为0.6元，用过的刀具送到机修车间研磨，每把刀具需要花费0.2元（考虑内部核算）。刀具每天用过后，如果立即送去磨，第三天可以磨好送回，供当天的需用。第五天后，

5、刀具应全部换新，每期开始时，该车间没有任何刀具。问这个车间需要多少刀具才能应付需要，而成本又最低？试建立其线性规划模型。解：设决策变量xi(i=1,2,3,4,5)为第i天使用的新刀具，yj(j=1,2,3)为第j天送去研磨的刀具数；Z为刀具所花的成本。考虑送去研磨的刀具第三天才能使用：第1、2天所使用的只能是新刀具，从第三天起，每天使用的刀具可以是新的，也可以是磨好后送回的，所以：x1=120，x2=85，x3+y1=160，x4+y2=145，x5+y3=300则有：约束条件目标函数minZ=0.6(x1+x2+x3+x4+x5)+0.2(y1+y2+y3)X1=120X2=85

6、x3+y1=160x4+y2=145y1≤120y2≤85+(120-y1)y3≤160+(120-y1)+(85-y2)xi≥0(I=1,2,3,4,5)且均为整数yj≥0（j=1,2,3）且均为整数x5+y3=300MaxZ=2x1+3x22x1+2x2≤12x1+2x2≤84x1≤164x2≤12x1，x2≥0只适用于n=2的情况。二、图解法例：1.几个名词：图解法——通过在平面上作图求解的方法；可行解——满足约束条件（包括非负条件）的解，即可行方案；可行域——全体可行解；最优解——使目标函数取得最优的可行解。（1）在直角坐标系中分别作出各约束条件，从而确定可行域；2.图解法步

7、骤：（2）作出一条目标函数等值线；（3）将目标函数等值线沿目标函数值增大（或减小）方向移动，以求得最优解或确定线性规划无解。例1：求最优解：教材第13-14页例2：(0.5,0.5)01.50.752x+4y=311x+y=1MinZ=x+2yyx可行解例3：用图解法求最优解0x1x20.81.60.8x1+x2=1.61.412A可行解MinZ=1000x1+800x2=1640...解：1.无可行解（约束方程组矛盾），也就无最优解；2.有可行解，但目标