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

《第2章__线性规划的图解法.ppt》由会员分享，可在线阅读，更多相关《第2章__线性规划的图解法.ppt（63页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、上页上页上页上页下页下页下页下页返回返回返回返回第二章线性规划的图解法第二章线性规划的图解法1 1问题的提出问题的提出2 2图解法图解法3 3图解法的灵敏度分析图解法的灵敏度分析v线性规划问题的提出线性规划问题的提出v 线性规划的基本概念线性规划的基本概念v 线性规划的数学模型线性规划的数学模型v 线性规划问题的标准形式线性规划问题的标准形式继续继续继续继续返回返回返回返回第一节第一节线性规划问题线性规划问题及其数学模型及其数学模型上页上页上页上页下页下页下页下页返回返回返回返回问题的提出问题的提出例1:生产计划问题上页上页上页上页下页下页下页下页返回返回返回返回产品产品I产品产品2如何安排生

2、产如何安排生产使利润最大使利润最大？上页上页上页上页下页下页下页下页返回返回返回返回决策变量（决策变量（决策变量（决策变量（Decision variablesDecision variables）目标函数（目标函数（目标函数（目标函数（Objective functionObjective function）约束条件（约束条件（约束条件（约束条件（Constraint conditionsConstraint conditions）可行域（可行域（可行域（可行域（Feasible region)Feasible region)最优解（最优解（最优解（最优解（Optimal solution)

3、Optimal solution)基本概念基本概念问题中要确定的未知量，表问题中要确定的未知量，表问题中要确定的未知量，表问题中要确定的未知量，表明规划中的用数量表示的方明规划中的用数量表示的方明规划中的用数量表示的方明规划中的用数量表示的方案、措施，可由决策者决定案、措施，可由决策者决定案、措施，可由决策者决定案、措施，可由决策者决定和控制。和控制。和控制。和控制。它是决策变量的函数它是决策变量的函数它是决策变量的函数它是决策变量的函数指决策变量取值时受到的指决策变量取值时受到的指决策变量取值时受到的指决策变量取值时受到的各种资源条件的限制，通各种资源条件的限制，通各种资源条件的限制，通各种

4、资源条件的限制，通常表达为含决策变量的等常表达为含决策变量的等常表达为含决策变量的等常表达为含决策变量的等式或不等式。式或不等式。式或不等式。式或不等式。满足约束条件的决满足约束条件的决满足约束条件的决满足约束条件的决策变量的取值范围策变量的取值范围策变量的取值范围策变量的取值范围可行域中使目标可行域中使目标可行域中使目标可行域中使目标函数达到最优的函数达到最优的函数达到最优的函数达到最优的决策变量的值决策变量的值决策变量的值决策变量的值上页上页上页上页下页下页下页下页返回返回返回返回是问题中要确定的未知量，是问题中要确定的未知量，是问题中要确定的未知量，是问题中要确定的未知量，表明规划中的用

5、数量表示表明规划中的用数量表示表明规划中的用数量表示表明规划中的用数量表示的方案、措施，可由决策的方案、措施，可由决策的方案、措施，可由决策的方案、措施，可由决策者决定和控制。者决定和控制。者决定和控制。者决定和控制。第第1步步-确定决策变量确定决策变量设设 I的产量的产量 II的产量的产量 利润利润上页上页上页上页下页下页下页下页返回返回返回返回第第2步步-定义目标函数定义目标函数MaxZ=x1+x2决策变量决策变量上页上页上页上页下页下页下页下页返回返回返回返回MaxZ=50 x1+100 x2价值系数价值系数第第2步步-定义目标函数定义目标函数上页上页上页上页下页下页下页下页返回返回返回

6、返回对我们有对我们有何限制何限制?上页上页上页上页下页下页下页下页返回返回返回返回第第3步步-表示表示约束条件约束条件 x1+x2 3002x1+x2 400 x2 250 x1、x2 0 0上页上页上页上页下页下页下页下页返回返回返回返回该计划的数学模型该计划的数学模型目标函数目标函数MaxZ=50 x1+100 x2约束条件约束条件x1+x2 3002x1+x2 400 x2 250 x1、x2 0 0 x1x2上页上页上页上页下页下页下页下页返回返回返回返回 例2:某工厂拥有A、B、C 三种类型的设备，生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三

7、种设备可利用的时数如下表所示：产品甲产品乙设备能力/h设备A3 32 26565设备B2 21 14040设备C0 03 37575利润/（元/件）1500150025002500上页上页上页上页下页下页下页下页返回返回返回返回 问题：工厂应如何安排生产可获得最大的总利润？解：设变量 xi 为第 i 种（甲、乙）产品的生产件数（i1，2）。根据题意，我们知道两种产品的生产受到设备能力（机时数）的限制。对设备A：两种产品生产所占用的机时数不能超过65，于是我们可以得到不等式：3 x1+2 x2 65；对设备B：两种产品生产所占用的机时数不能超过40，于是我们可以得到不等式：2 x1+x2 40；

8、上页上页上页上页下页下页下页下页返回返回返回返回 对设备C：两种产品生产所占用的机时数不能超过75，于是我们可以得到不等式：3x2 75；另外，产品数不可能为负，即 x1,x2 0。同时，我我们们有有一一个个追追求求目目标标，即即获获取取最最大大利利润润。于是可写出目标函数z为相应的生产计划可以获得的总利润：z=1500 x1+2500 x2 综合上述讨论，在加工时间以及利润与产品产量成线性关系的假设下，把目标函数和约束条件放在一起，可以建立如下的线性规划模型：上页上页上页上页下页下页下页下页返回返回返回返回目标函数目标函数 Max Max z=1500 x1+2500 x2约束条件约束条件

9、s.t.s.t.3x1+2x2 652x1+x2 403x2 75x1,x2 0上页上页上页上页下页下页下页下页返回返回返回返回线性规划问题的共同特征线性规划问题的共同特征一组决策变量一组决策变量X X表示一个方案表示一个方案,一般一般X X大大于等于零。于等于零。约束条件是线性等式或不等式。约束条件是线性等式或不等式。目标函数是线性的，求目标函数最大目标函数是线性的，求目标函数最大化或最小化化或最小化上页上页上页上页下页下页下页下页返回返回返回返回建模过程建模过程1.理解要解决的问题，了解解题的目标和条件；2.定义决策变量（x1，x2，xn），每一组值表示一个方案；3.用决策变量的线性函数形

10、式写出目标函数，确定最大化或最小化目标；4.用一组决策变量的等式或不等式表示解决问题过程中必须遵循的约束条件上页上页上页上页下页下页下页下页返回返回返回返回线性规划模型的一般形式线性规划模型的一般形式 上页上页上页上页下页下页下页下页返回返回返回返回线性规划问题的标准形式线性规划问题的标准形式标准形式为标准形式为:目标函数最大目标函数最大约束条件等式约束条件等式决策变量非负决策变量非负右端项非负右端项非负上页上页上页上页下页下页下页下页返回返回返回返回 标准形式可以简写为标准形式可以简写为上页上页上页上页下页下页下页下页返回返回返回返回线性规划的标准形式有如下四个特点：目标最大化；目标最大化；

11、约束为等式；约束为等式；决策变量均非负；决策变量均非负；右端项非负右端项非负。对于各种非标准形式的线性规划问题，我们总可以通过以下变换，将其转化为标准形式:上页上页上页上页下页下页下页下页返回返回返回返回1 1、极小化目标函数的问题：、极小化目标函数的问题：设目标函数为 Min f=c1x1+c2x2+cnxn 则可以令z z -f-f，该极小化问题与下面的极大化问题有相同的最优解，即 Max z=-c1x1-c2x2-cnxn 但必须注意，尽管以上两个问题的最优解相同，但他们最优解的目标函数值却相差一个符号，即 Min f -Max z一般线性规划问题的标准形化一般线性规划问题的标准形化上页

12、上页上页上页下页下页下页下页返回返回返回返回2 2、约束条件不是等式的问题、约束条件不是等式的问题 “”约束：加入非负松驰变量约束：加入非负松驰变量例：例：目标函数目标函数目标函数目标函数MaxMaxZ Z=2=2x x1 1+3+3x x2 2约束条件约束条件约束条件约束条件x1+2x2 84x1 164x2 12 x1、x2 0 0上页上页上页上页下页下页下页下页返回返回返回返回例：例：上页上页上页上页下页下页下页下页返回返回返回返回例：将以下线性规划问题转化为标准形式例：将以下线性规划问题转化为标准形式 Min Min f=3.6x1-5.2x2+1.8x3 s.t.s.t.2.3x1+

13、5.2x2-6.1x315.74.1x1 +3.3x38.9x1+x2+x3=38x1,x2,x3 0解：首先解：首先,将目标函数转换成极大化：将目标函数转换成极大化：令令 z=-f=-3.6x1+5.2x2-1.8x3当当“”约束：约束：减去非负剩余变量减去非负剩余变量；上页上页上页上页下页下页下页下页返回返回返回返回其其次次考考虑虑约约束束，有有2 2个个不不等等式式约约束束，引引进进松弛变量松弛变量x x4 4 0，剩余变量，剩余变量x x5 5 00。于是，我们可以得到以下标准形式：于是，我们可以得到以下标准形式：Max Max z=-3.6x1+5.2x2-1.8x3s.t.s.t.

14、2.3x1+5.2x2-6.1x3+x4 =15.74.1x1 +3.3x3 -x5=8.9x1+x2+x3 =38x1,x2,x3,x4,x50上页上页上页上页下页下页下页下页返回返回返回返回3.3.变量无符号限制的问题：变量无符号限制的问题：在在标标准准形形式式中，必须每一个变量均有非负约束。当某一个变量xj没有非负约束时，可以令 xj=xj-xj”其中 xj0，xj”0即用两个非负变量之差来表示一个无符号限制的变量，当然xj的符号取决于xj和xj”的大小。上页上页上页上页下页下页下页下页返回返回返回返回 例例例例 ：Max上页上页上页上页下页下页下页下页返回返回返回返回 解解 ：标准形为

15、上页上页上页上页下页下页下页下页返回返回返回返回4.4.右端项有负值的问题：右端项有负值的问题：在标准形式中，要求右端项必须每一个分量非负。当某一个右端项系数为负时，如bi0，则把该等式约束两端同时乘以-1，得到：-ai1 x1-ai2 x2-ain xn=-bi。上页上页上页上页下页下页下页下页返回返回返回返回练习题：将以下线性规划问题转化为标准形式练习题：将以下线性规划问题转化为标准形式 Min Min f=-3x1+5x2+8x3-7x4s.t.s.t.2x1-3x2+5x3+6x4284x1+2x2+3x3-9x4396x2+2x3+3x4-58x1,x3 ,x40上页上页上页上页下页

16、下页下页下页返回返回返回返回解：首先，将目标函数转换成极大化：令 z=-f=3x15x28x3+7x4；其次考虑约束，有3个不等式约束，引进松弛变量x5,x6,x7 0；由于x2无非负限制，可令x2=x2-x2”,其中x20，x2”0；由于第3个约束右端项系数为-58，于是把该式两端乘以-1。于是，我们可以得到以下标准形式的线性规划问题：上页上页上页上页下页下页下页下页返回返回返回返回 Max z=3x15x2+5x2”8x3+7x4 s.t.2x13x2+3x2”+5x3+6x4+x5=28 4x1+2x2-2x2”+3x3-9x4-x6=39 -6x2+6x2”-2x3-3x4-x7=58

17、 x1,x2,x2”,x3,x4,x5,x6,x7 0上页上页上页上页下页下页下页下页返回返回返回返回例：将以下线性规划问题转化为标准形式Minf=2x1-3x2+4x3s.t.3x1+4x2-5x362x1+x38x1+x2+x3=-9x1,x2,x3 0上页上页上页上页下页下页下页下页返回返回返回返回解：首先,将目标函数转换成极大化：令 z=-f=-2x1+3x2-4x3 其次考虑约束，有2个不等式约束，引进松弛变量x4，x5 0。第三个约束条件的右端值为负，在等式两边同时乘-1。上页上页上页上页下页下页下页下页返回返回返回返回通过以上变换，可以得到以下标准形式的线性规划问题：Max Ma

18、x z z=-2=-2x x1 1+3+3x x2 2-4-4x x3 3 s.ts.t.3.3x x1 1+4+4x x2 2-5-5x x3 3+x x4 4 =6=6 2 2x x1 1 +x x3 3 -x x5 5=8=8 -x x1 1 -x x2 2 -x x3 3 =9=9 x x1 1,x,x2 2,x,x3 3,x,x4 4,x,x5 5 0 0上页上页上页上页下页下页下页下页返回返回返回返回练习建立练习建立LPLP数学模型数学模型有两个煤厂有两个煤厂A A、B B，每月分别供应三个居民每月分别供应三个居民区区X X、Y Y、Z Z。求运费最少的方案。求运费最少的方案。上页

19、上页上页上页下页下页下页下页返回返回返回返回例1.目标函数：Maxz=50 x1+100 x2约束条件：s.t.x1+x2300(A)2x1+x2400(B)x2250(C)x10(D)x20(E)得到最优解：x1=50，x2=250最优目标值z=275002图图解解法法 对于只有两个决对于只有两个决策变量的线性规划问策变量的线性规划问题，可以在平面直角题，可以在平面直角坐标系上作图表示线坐标系上作图表示线性规划问题的有关概性规划问题的有关概念，并求解。念，并求解。下面通过例下面通过例1 1详细详细讲解其方法：讲解其方法：上页上页上页上页下页下页下页下页返回返回返回返回2图图解解法法 (1)(

20、1)分别取决策变量分别取决策变量X X1 1,X,X2 2 为坐标向量建为坐标向量建立直角坐标系。在直角坐标系里，图上任意立直角坐标系。在直角坐标系里，图上任意一点的坐标代表了决策变量的一组值，例一点的坐标代表了决策变量的一组值，例1 1的每个约束条件都代表一个半平面。的每个约束条件都代表一个半平面。上页上页上页上页下页下页下页下页返回返回返回返回x2x1X20X2=0 x2x1X10X1=0上页上页上页上页下页下页下页下页返回返回返回返回（2 2）对每个不等式）对每个不等式(约束条件约束条件)，先取其等式在坐标，先取其等式在坐标系中作直线，然后确定不等式所决定的半平面。系中作直线，然后确定不

21、等式所决定的半平面。上页上页上页上页下页下页下页下页返回返回返回返回100200300100200300 x1+x2300 x1+x2=3001001002002x1+x24002x1+x2=400300200300400上页上页上页上页下页下页下页下页返回返回返回返回100100 x2250 x2=250200300200300上页上页上页上页下页下页下页下页返回返回返回返回（3）把五个图合并成一个图，取各约束条件的公共部分，如图所示。上页上页上页上页下页下页下页下页返回返回返回返回x1x2x2=0 x1=0 x2=250 x1+x2=3002x1+x2=400上页上页上页上页下页下页下页下

22、页返回返回返回返回（4）目标函数z=50 x1+100 x2，当z取某一固定值时得到一条直线，直线上的每一点都具有相同的目标函数值，称之为“等值线”。平行移动等值线，当移动到B点时，z在可行域内实现了最大化。A，B，C，D，E是可行域的顶点，对有限个约束条件则其可行域的顶点也是有限的。上页上页上页上页下页下页下页下页返回返回返回返回x1x2z=20000=50 x1+100 x2z=27500=50 x1+100 x2z=0=50 x1+100 x2z=10000=50 x1+100 x2CBADE上页上页上页上页下页下页下页下页返回返回返回返回重要结论：如果线性规划有最优解，则一定有一个可行

23、域的顶点对应一个最优解；无穷多个最优解无穷多个最优解。若将例1中的目标函数变为maxz=50 x1+50 x2，则线段BC上的所有点都代表了最优解；上页上页上页上页下页下页下页下页返回返回返回返回无界解无界解。即可行域的范围延伸到无穷远，目标函数值可以无穷大或无穷小。一般来说，这说明模型有错，忽略了一些必要的约束条件；无可行解无可行解。若在例1的数学模型中再增加一个约束条件4x1+3x21200，则可行域为空域，不存在满足约束条件的解，当然也就不存在最优解了。上页上页上页上页下页下页下页下页返回返回返回返回可行域是有界或无界的凸多边形。可行域是有界或无界的凸多边形。可行域是有界或无界的凸多边形

24、。可行域是有界或无界的凸多边形。若线性规划问题存在最优解，它一定可以在若线性规划问题存在最优解，它一定可以在若线性规划问题存在最优解，它一定可以在若线性规划问题存在最优解，它一定可以在可行域的顶点得到。可行域的顶点得到。可行域的顶点得到。可行域的顶点得到。若两个顶点同时得到最优解，则其连线上的若两个顶点同时得到最优解，则其连线上的若两个顶点同时得到最优解，则其连线上的若两个顶点同时得到最优解，则其连线上的所有点都是最优解。所有点都是最优解。所有点都是最优解。所有点都是最优解。解题思路：找出凸集的顶点，计算其目标函解题思路：找出凸集的顶点，计算其目标函解题思路：找出凸集的顶点，计算其目标函解题思

25、路：找出凸集的顶点，计算其目标函数值，比较即得。数值，比较即得。数值，比较即得。数值，比较即得。上页上页上页上页下页下页下页下页返回返回返回返回例例2 2 某公司由于生产需要，共需要A，B两种原料至少350吨（A，B两种材料有一定替代性），其中A原料至少购进125吨。但由于A，B两种原料的规格不同，各自所需的加工时间也是不同的，加工每吨A原料需要2个小时，加工每吨B原料需要1小，而公司总共有600个加工小时。又知道每吨A原料的价格为2万元，每吨B原料的价格为3万元，试问在满足生产需要的前提下，在公司加工能力的范围内，如何购买A，B两种原料，使得购进成本最低？上页上页上页上页下页下页下页下页返回

26、返回返回返回解：目标函数：Minf=2x1+3 x2 约束条件：s.t.x1+x2 350 x1 125 2x1+x2 600 x1 ,x2 0 采用图解法。如下图：得Q点坐标（250，100）为最优解。上页上页上页上页下页下页下页下页返回返回返回返回100200300400500600100200300400600500 x1=125x1+x2=3502x1+3x2=8002x1+3x2=9002x1+x2=6002x1+3x2=1200 x1 x2 Q上页上页上页上页下页下页下页下页返回返回返回返回3图解法的灵敏度分析图解法的灵敏度分析灵敏度分析灵敏度分析：建立数学模型和求得最优解后，研究

27、线性规划的一个或多个参数（系数）ci,aij,bj变化时，对最优解产生的影响。上页上页上页上页下页下页下页下页返回返回返回返回(1)(1)目标函数中的系数目标函数中的系数ci的灵敏度分析的灵敏度分析考虑例考虑例1 1的情况，的情况，c ci i 的变化只影响目标函数等的变化只影响目标函数等值线的斜率，目标函数值线的斜率，目标函数 z=50 xz=50 x1 1+100 x+100 x2 2 在在z=xz=x2 2(x(x2 2=z=z斜率为斜率为0 0 )到到z=xz=x1 1+x+x2 2(x(x2 2=-x=-x1 1+z+z斜斜率为率为-1)-1)之间时，原最优解之间时，原最优解x x1

28、 1=50=50，x x2 2=100 =100 仍是最优解。仍是最优解。上页上页上页上页下页下页下页下页返回返回返回返回一般情况：一般情况：z=c1x1+c2x2写成斜截式写成斜截式x2=-(c1/c2)x1+z/c2，目标函数等值线的斜率为，目标函数等值线的斜率为-(c1/c2)，当当-1-(c1/c2)0（*）时，原最优时，原最优解仍是最优解。解仍是最优解。上页上页上页上页下页下页下页下页返回返回返回返回假设产品假设产品的利润的利润100元不变，即元不变，即c2=100，代到式（代到式（*）并整理得）并整理得0 c1 100假设产品假设产品的利润的利润50元不变，即元不变，即c1=50，

29、代代到式（到式（*）并整理得）并整理得50 c2+上页上页上页上页下页下页下页下页返回返回返回返回假若产品、的利润均改变，则可直接用式（*）来判断。假设产品、的利润分别为60元、55元，则-2-(60/55)-1那么，最优解为z=x1+x2和z=2x1+x2的交点x1=100，x2=200。上页上页上页上页下页下页下页下页返回返回返回返回(2)(2)约束条件中右边系数约束条件中右边系数 b bj j 的灵敏度分析的灵敏度分析 当约束条件中右边系数当约束条件中右边系数 b bj j 变化时，线性规划变化时，线性规划的可行域发生变化，可能引起最优解的变化。的可行域发生变化，可能引起最优解的变化。考

30、虑例考虑例1 1的情况：的情况：假设设备台时增加假设设备台时增加1010个台时，即个台时，即 b b1 1变化为变化为310310，这时可行域扩大，这时可行域扩大，最优解为最优解为x x2 2=250=250和和x x1 1+x+x2 2=310=310的交点的交点x x1 1=60=60，x x2 2=250=250。上页上页上页上页下页下页下页下页返回返回返回返回变化后的总利润变化后的总利润-变化前的总利润变化前的总利润=增加的利润增加的利润 (50(5060+10060+100250)-(50250)-(5050+10050+100250)=500 250)=500，500/10=50

31、500/10=50 元元 说明在一定范围内每增加（减少）说明在一定范围内每增加（减少）1 1个台个台时的设备能力就可增加（减少）时的设备能力就可增加（减少）5050元利润，称元利润，称为该约束条件的为该约束条件的对偶价格对偶价格。上页上页上页上页下页下页下页下页返回返回返回返回假设原料假设原料A A增加增加1010千克时，即千克时，即 b2b2变化为变化为410410，这时可行域扩大，但，这时可行域扩大，但最优解仍为最优解仍为x x2 2=250=250和和x x1 1+x+x2 2=300=300的交点的交点x x1 1=50=50，x x2 2=250=250。此变化对总利。此变化对总利润

32、无影响，该约束条件的对偶价格为润无影响，该约束条件的对偶价格为 0 0。上页上页上页上页下页下页下页下页返回返回返回返回解释：解释：原最优解没有把原料原最优解没有把原料 A A 用尽，有用尽，有5050千克的千克的剩，因此增加剩，因此增加1010千克值增加了库存，而不会增千克值增加了库存，而不会增加利润。加利润。上页上页上页上页下页下页下页下页返回返回返回返回 在一定范围内，当约束条件右边常数增加在一定范围内，当约束条件右边常数增加1 1个单位时：个单位时：（1 1）若约束条件的对偶价格大于）若约束条件的对偶价格大于0 0，则其最优，则其最优目标函数值得到改善（变好）；目标函数值得到改善（变好）；（2 2）若约束条件的对偶价格小于）若约束条件的对偶价格小于0 0，则其最优，则其最优目标函数值受到影响（变坏）；目标函数值受到影响（变坏）；（3 3）若约束条件的对偶价格等于）若约束条件的对偶价格等于0 0，则最优目，则最优目标函数值不变。标函数值不变。