第二章线性规划的图解法精选PPT.ppt

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

1、第二章 线性规划的图解法第1页，本讲稿共64页第二章：线性规划的图解法第二章：线性规划的图解法第一节：线性规划问题的提出第一节：线性规划问题的提出第二节：线性规划的图解法第二节：线性规划的图解法第三节：图解法的灵敏度分析第三节：图解法的灵敏度分析本章的重点和难点本章的重点和难点：2 2：图解法的灵敏度分析：图解法的灵敏度分析1 1：线性规划的图解法：线性规划的图解法第2页，本讲稿共64页线性规划的定义求线性目标函数在求线性目标函数在线性约束条件线性约束条件下的最大下的最大值或最小值的问题，统称为线性规划问值或最小值的问题，统称为线性规划问题。题。满足线性约束条件的解叫做满足线性约束条件的解叫做

2、可行解可行解，由所，由所有可行解组成的集合叫做有可行解组成的集合叫做可行域可行域。决策变决策变量、约束条件、目标函数量、约束条件、目标函数是线性规划的三是线性规划的三要素要素.第二章第二章 线性规划的图解法线性规划的图解法第3页，本讲稿共64页4 在管理中一些典型的线性规划应用在管理中一些典型的线性规划应用合理利用线材问题：如何在保证生产的条合理利用线材问题：如何在保证生产的条件下，下料最少件下，下料最少配料问题：在原料供应量的限制下如何获配料问题：在原料供应量的限制下如何获取最大利润取最大利润投资问题：从投资项目中选取方案，使投投资问题：从投资项目中选取方案，使投资回报最大资回报最大第二章第

3、二章 线性规划的图解法线性规划的图解法第4页，本讲稿共64页产品生产计划：合理利用人力、物力、财产品生产计划：合理利用人力、物力、财力等，使获利最大力等，使获利最大劳动力安排：用最少的劳动力来满足工作劳动力安排：用最少的劳动力来满足工作的需要的需要运输问题：如何制定调运方案，使总运费运输问题：如何制定调运方案，使总运费最小最小第二章第二章 线性规划的图解法线性规划的图解法第5页，本讲稿共64页问题问题1:1:某工厂计划生产甲、乙两种产品，某工厂计划生产甲、乙两种产品，生产生产1kg1kg的甲需耗煤的甲需耗煤9t9t、电力、电力4kw.h4kw.h、油、油3t3t；生产生产1kg1kg的乙需耗煤

4、的乙需耗煤4t4t、电力、电力5kw.h5kw.h、油、油10t10t；该厂现有煤该厂现有煤360t360t、电力、电力200kw.h200kw.h、油、油300t300t。已知甲产品每千克的售价为已知甲产品每千克的售价为7 7万元、乙产品每千克万元、乙产品每千克的售价为的售价为1212万元。万元。在上述条件下决定生产方案，使得总收入最大在上述条件下决定生产方案，使得总收入最大。第二章第二章 线性规划的图解法线性规划的图解法第6页，本讲稿共64页问题问题1具体数据如表所示：具体数据如表所示：资源资源 产品产品单耗单耗资源资源甲甲 乙乙资源限量资源限量煤煤(t)电电(kw.h)油油(t)9 44

5、 5 3 10360200300单位产品价格单位产品价格 7 12提出和形成问题提出和形成问题建立模型建立模型求解求解结果的分析和应用结果的分析和应用第二章第二章 线性规划的图解法线性规划的图解法第7页，本讲稿共64页总收入记为总收入记为f,则则 f=7x1+12x2 ，为体现对其求极大化，在，为体现对其求极大化，在f 的前面冠以极大号的前面冠以极大号Max，也就是：也就是：甲、乙产品的计划产量，记为甲、乙产品的计划产量，记为x1，x2；在本例中在本例中资源煤、电、油的数量是有限的，对产品甲和乙资源煤、电、油的数量是有限的，对产品甲和乙的生产量构成了约束，表示为：的生产量构成了约束，表示为：决

6、策变量：目标函数：约束条件：Max（maximize最大化）最大化）Min(minimum)s.t.(subjectto受制于受制于)第二章第二章 线性规划的图解法线性规划的图解法第8页，本讲稿共64页解：设安排甲、乙产量分别为解：设安排甲、乙产量分别为x1，x2,总收入为总收入为 f ，则该问题的数学模型为：则该问题的数学模型为：第二章第二章 线性规划的图解法线性规划的图解法第9页，本讲稿共64页（1）决策变量：甲、乙产品的）决策变量：甲、乙产品的产量产量x1，x2线性规划模型的线性规划模型的三个基本要素：三个基本要素：（也是所有规划问题的三个基本要素）（也是所有规划问题的三个基本要素）：决

7、策变量：需要决策的量，即等待求解的未知数。决策变量：需要决策的量，即等待求解的未知数。目标函数：想要达到的目标，用决策变量目标函数：想要达到的目标，用决策变量的表达式表示。的表达式表示。约束条件：由于资源有限，为了实现目约束条件：由于资源有限，为了实现目标有哪些资源限制，用决策变量的等式标有哪些资源限制，用决策变量的等式或不等式表示。或不等式表示。（3）约束条件：）约束条件：（2）目标函数：总收入最大）目标函数：总收入最大，Max f=7x 1+12x 2 第二章第二章 线性规划的图解法线性规划的图解法第10页，本讲稿共64页什么是线性规划模型：什么是线性规划模型：决策变量为可控的连续变量。决

8、策变量为可控的连续变量。目标函数和约束条件都是线性的。目标函数和约束条件都是线性的。x 1 0，x 2 0 x 1=0,1,2,3n第二章第二章 线性规划的图解法线性规划的图解法第11页，本讲稿共64页例例2.2.某工厂在计划期内要安排某工厂在计划期内要安排、两种产两种产品的生产，已知生产单位产品所需的设备台品的生产，已知生产单位产品所需的设备台时及时及A A、B B两种原材料的消耗、资源的限制，两种原材料的消耗、资源的限制，如下表：如下表：问题：工厂应分别生产多少单位问题：工厂应分别生产多少单位、产品才能使工厂获利最多？产品才能使工厂获利最多？第二章第二章 线性规划的图解法线性规划的图解法第

9、12页，本讲稿共64页目标函数：目标函数：Maxz=50 x1+100 x2约束条件：约束条件：s.t.x1+x23002x1+x2400 x2250 x1,x20第二章 线性规划的图解法第13页，本讲稿共64页一般形式一般形式目标函数：目标函数：Max（Min）z=c1x1+c2x2+cnxn约束条件：约束条件：s.t.a11x1+a12x2+a1nxn（=,）b1a21x1+a22x2+a2nxn（=,）b2am1x1+am2x2+amnxn（=,）bm x1，x2，xn0 第二章第二章 线性规划的图解法线性规划的图解法第14页，本讲稿共64页对于只有两个变量的简单的线性规划问题，对于只有

10、两个变量的简单的线性规划问题，一般采用图解法求解。这种方法仅适用于只一般采用图解法求解。这种方法仅适用于只有两个变量的线性规划问题。它的特点是直有两个变量的线性规划问题。它的特点是直观而易于理解，但实用价值不大。观而易于理解，但实用价值不大。第二章第二章 线性规划的图解法线性规划的图解法第15页，本讲稿共64页1.1.基本概念基本概念（1 1）可行解：满足约束条件的决策变量的取值）可行解：满足约束条件的决策变量的取值（2 2）可行域：可行解的全体）可行域：可行解的全体（3 3）最优解：使目标函数取得最优值的可行解）最优解：使目标函数取得最优值的可行解（4 4）最优值：最优解代入目标函数所得到的

11、值）最优值：最优解代入目标函数所得到的值第二章第二章 线性规划的图解法线性规划的图解法第16页，本讲稿共64页例例3.3.用图解法对下列线性规划模型进行求解用图解法对下列线性规划模型进行求解。MaxZ=2x1+3x2 x1+2x28 4x116 x212 x1,x20s.t.第二章第二章 线性规划的图解法线性规划的图解法第17页，本讲稿共64页18 图解法求解的步骤：图解法求解的步骤：分别取决策变量分别取决策变量X X1 1,X,X2 2 为坐标向量建立为坐标向量建立直角坐标系。在直角坐标系里，图上任意一直角坐标系。在直角坐标系里，图上任意一点的坐标代表了决策变量的一组值。点的坐标代表了决策变

12、量的一组值。第二章 线性规划的图解法第18页，本讲稿共64页9 8 7 6 5 4 3 2 1 0 x2|123456789x1x1+2x2 84x1 164 x2 12 x1+2x2 8 4x1 16 4x2 12 x1、x2 0 0第二章第二章 线性规划的图解法线性规划的图解法第19页，本讲稿共64页9 8 7 6 5 4 3 2 1 0|123456789x1 x1+2x2 84x1 164 x2 12可行域可行域ABCDO可行解：满足约束条件的解。红色区可行解：满足约束条件的解。红色区域中的每一个点（包括边界点）都是域中的每一个点（包括边界点）都是可行解。此区域是就是可行域。可行解。此

13、区域是就是可行域。第20页，本讲稿共64页9 8 7 6 5 4 3 2 1 0 x2|123456789x1x1+2x2 84x1 164 x2 12ABCDO 目标函数目标函数 Z=2xZ=2x1 1+3x+3x2 2在这个坐标在这个坐标平面上，它可以表示以平面上，它可以表示以Z Z为参数、为参数、-2/32/3为斜率的一族平行线为斜率的一族平行线：位于同一直线位于同一直线上的点，具有上的点，具有相同的目标函相同的目标函数，称为数，称为“等等值线值线”。第21页，本讲稿共64页9 8 7 6 5 4 3 2 1 0 x2 当当Z Z值由小变大时，直线值由小变大时，直线 沿其法线方向向右上方

14、沿其法线方向向右上方移动。当移动到移动。当移动到C C时，时，Z Z值在可行域的值在可行域的边界上实现最大化。最优解（边界上实现最大化。最优解（4 4，2 2），），Z=14Z=14。|123456789x1x1+2x2 84x1 164 x2 12ABCDO最优解最优解最优解最优解 (4,2)(4,2)(4,2)(4,2)最优生产方案最优生产方案:产品产品1 1生产生产4kg4kg，产品，产品2 2生生产产2kg2kg，最大利，最大利润润1414元元(最优最优值）。值）。第22页，本讲稿共64页结论：结论：线性规划问题如果有最优解线性规划问题如果有最优解,则最优则最优解一定在可行域的边界上取

15、得解一定在可行域的边界上取得.第二章第二章 线性规划的图解法线性规划的图解法第23页，本讲稿共64页 无穷多最优解无穷多最优解 9 8 7 6 5 4 3 2 1 0 x2|123456789x1x1+2x2 84x1 164 x2 12O可行域可行域第二章第二章 线性规划的图解法线性规划的图解法第24页，本讲稿共64页当移动到当移动到ABAB线段时，线段时，Z Z值在线段值在线段CDCD上实现最上实现最大化。大化。线段线段CDCD上的任意一点上的任意一点都使都使Z Z取得相同的最大取得相同的最大值，这个线性规划问值，这个线性规划问题有无穷多最优解。题有无穷多最优解。9 8 7 6 5 4 3

16、 2 1 0 x2|123456789x1x1+2x2 84x1 164 x2 12ABCDO可行域可行域第二章第二章 线性规划的图解法线性规划的图解法第25页，本讲稿共64页无可行解无可行解可行域为空集，无可可行域为空集，无可行解，当然也无最优行解，当然也无最优解。解。9 8 7 6 5 4 3 2 1 0 x2|123456789x1Ol2l1第二章第二章 线性规划的图解法线性规划的图解法Maxz=x1+2x2s.t.x1+2x284x1164x212x13x2 3 第26页，本讲稿共64页 无界解无界解x1x201 2 3 4 5 6 7 8 9654321线性规划问题可行域无界，目标函

17、数可以增大到无穷大线性规划问题可行域无界，目标函数可以增大到无穷大第二章第二章 线性规划的图解法线性规划的图解法第27页，本讲稿共64页该问题如果求目标函数的最小值，由下图可以看出在顶点该问题如果求目标函数的最小值，由下图可以看出在顶点B B取得最优解：取得最优解：x1x201 2 3 4 5 6 7 8 9654321B（1，0）第二章第二章 线性规划的图解法线性规划的图解法第28页，本讲稿共64页唯一解唯一解无穷多解无穷多解无有限最优解无有限最优解无可行解无可行解有最优解无最优解 求解一个线性规划问题就是要判断该问题属于那求解一个线性规划问题就是要判断该问题属于那种情况，当问题有最优解时，

18、还需要在可行区域中求出种情况，当问题有最优解时，还需要在可行区域中求出使目标函数达到最优值的点，也就是最优解，以及目标使目标函数达到最优值的点，也就是最优解，以及目标函数的最优值。函数的最优值。第二章第二章 线性规划的图解法线性规划的图解法第29页，本讲稿共64页练习题：练习题：1.考虑下面线性规划问题考虑下面线性规划问题：Maxz=2x1+3x2s.t.x1+2x265x1+3x215x1,x20（1）画出其可行域）画出其可行域（2）当）当Z=6时，画出等值线时，画出等值线2x1+3x2=6（3）用图解法求出其最优解以及最优目标函）用图解法求出其最优解以及最优目标函数值数值第二章第二章 线性

19、规划的图解法线性规划的图解法第30页，本讲稿共64页31 例例2 2：.某公司由于生产需要，共需要某公司由于生产需要，共需要A A，B B两种原料至少两种原料至少350350吨（吨（A A，B B两种材料有一定替代性），其中两种材料有一定替代性），其中A A原料至少购进原料至少购进125125吨。但由于吨。但由于A A，B B两种原料的规格不同，各自所需的加工两种原料的规格不同，各自所需的加工时间也是不同的，加工每吨时间也是不同的，加工每吨A A原料需要原料需要2 2个小时，加工每吨个小时，加工每吨B B原料需要原料需要1 1小时，而公司总共有小时，而公司总共有600600个加工小时。又知道个

20、加工小时。又知道每吨每吨A A原料的价格为原料的价格为2 2万元，每吨万元，每吨B B原料的价格为原料的价格为3 3万元，试万元，试问在满足生产需要的前提下，在公司加工能力的范围问在满足生产需要的前提下，在公司加工能力的范围内，如何购买内，如何购买A A，B B两种原料，使得购进成本最低？两种原料，使得购进成本最低？第二章第二章 线性规划的图解法线性规划的图解法第31页，本讲稿共64页32解：目标函数：解：目标函数：Minf=2x1+3x2约束条件：约束条件：s.t.x1+x2350 x11252x1+x2600 x1,x20采用图解法。如下图：得采用图解法。如下图：得Q点坐标（点坐标（250

21、，100）为最优解。）为最优解。第二章第二章 线性规划的图解法线性规划的图解法第32页，本讲稿共64页得得Q点坐标（点坐标（250，100）为最优）为最优解解X1=250,x2=100时时minf=800100200300400500600100200300400600500 x1=125x1+x2=3502x1+x2=600 x1 x2 Q第二章第二章 线性规划的图解法线性规划的图解法第33页，本讲稿共64页例例1.某工厂在计划期内要安排某工厂在计划期内要安排、两种产品的两种产品的生产，已知生产单位产品所需的设备台时及生产，已知生产单位产品所需的设备台时及A、B两种原材料的消耗、资源的限制，

22、如下表：两种原材料的消耗、资源的限制，如下表：问题：工厂应分别生产多少单位问题：工厂应分别生产多少单位、产品才能使产品才能使工厂获利最多？工厂获利最多？第二章第二章 线性规划的图解法线性规划的图解法第34页，本讲稿共64页数学模型为数学模型为：求解得：x1=50,x2=250maxz=27500第二章第二章 线性规划的图解法线性规划的图解法第35页，本讲稿共64页36引入松驰变量（含义是资源的剩余量）引入松驰变量（含义是资源的剩余量）例例1中引入中引入s1，s2，s3模型化为模型化为Maxz=50 x1+100 x2+0s1+0s2+0s3s.t.x1+x2+s1=3002x1+x2+s2=4

23、00 x2+s3=250 x1,x2,s1,s2,s30对于最优解对于最优解x1=50 x2=250，s1=0s2=50s3=0说明：说明：生产生产50单位单位产品和产品和250单位单位产品将消耗完所有可能产品将消耗完所有可能的设备台时数及原料的设备台时数及原料B，但对原料，但对原料A则还剩余则还剩余50千克。千克。第二章第二章 线性规划的图解法线性规划的图解法第36页，本讲稿共64页松弛变量和剩余变量松弛变量和剩余变量松弛变量松弛变量：在线性规划中，对于：在线性规划中，对于“”约束条件中没有使用的资源或能力称之约束条件中没有使用的资源或能力称之为松弛变量。为松弛变量。剩余变量剩余变量：在线性

24、规划中，对于：在线性规划中，对于“”约约束条件，可以增加一些代表最低限约束的束条件，可以增加一些代表最低限约束的超过量，称之为剩余变量。超过量，称之为剩余变量。第二章第二章 线性规划的图解法线性规划的图解法第37页，本讲稿共64页38线性规划的标准化线性规划的标准化一般形式一般形式目标函数目标函数:Max（Min）z=c1x1+c2x2+cnxn约束条件：约束条件：s.t.a11x1+a12x2+a1nxn（=,）b1a21x1+a22x2+a2nxn（=,）b2am1x1+am2x2+amnxn（=,）bm x1，x2，xn0第二章第二章 线性规划的图解法线性规划的图解法第38页，本讲稿共6

25、4页标准形式标准形式目标函数：目标函数：Maxz=c1x1+c2x2+cnxn约束条件：约束条件：s.t.a11x1+a12x2+a1nxn=b1a21x1+a22x2+a2nxn=b2am1x1+am2x2+amnxn=bm x1，x2，xn0，bi0第二章第二章 线性规划的图解法线性规划的图解法第39页，本讲稿共64页40 可以看出，线性规划的标准形式有如下四个特点：可以看出，线性规划的标准形式有如下四个特点：目标最大化；目标最大化；约束为等式；约束为等式；决策变量均非负；决策变量均非负；右端项非负。右端项非负。第二章第二章 线性规划的图解法线性规划的图解法第40页，本讲稿共64页411.

26、1.极小化目标函数的问题：极小化目标函数的问题：设目标函数为设目标函数为:Minf=c1x1+c2x2+cnxn (可以可以)令令 z-f ，则该极小化问题与下面的极大化问题有相同的最优解则该极小化问题与下面的极大化问题有相同的最优解即即 Maxz=-c1x1-c2x2-cnxn 但但必必须须注注意意，尽尽管管以以上上两两个个问问题题的的最最优优解解相相同同，但但它它们们最最优优解解的目标函数值却相差一个符号，即的目标函数值却相差一个符号，即 Minf-Maxz第二章第二章 线性规划的图解法线性规划的图解法第41页，本讲稿共64页422、约束条件不是等式的问题、约束条件不是等式的问题：设约束条

27、件为设约束条件为ai1x1+ai2x2+ainxnbi可以引进一个新的变量可以引进一个新的变量s，使它等于约束右边与左边之差，使它等于约束右边与左边之差s=bi(ai1x1+ai2x2+ainxn)显然，显然，s也具有非负约束，即也具有非负约束，即s0，这时新的约束条件成为这时新的约束条件成为ai1x1+ai2x2+ainxn+s=bi第二章第二章 线性规划的图解法线性规划的图解法第42页，本讲稿共64页43当约束条件为当约束条件为ai1x1+ai2x2+ainxnbi时，时，类似地令类似地令s=(ai1x1+ai2x2+ainxn)-bi显显然然，s也也具具有有非非负负约约束束，即即s0，这

28、这时时新新的约束条件成为的约束条件成为ai1x1+ai2x2+ainxn-s=bi第二章第二章 线性规划的图解法线性规划的图解法第43页，本讲稿共64页3.3.右端项有负值的问题：右端项有负值的问题：在标准形式中，要求右端项必须每一个分在标准形式中，要求右端项必须每一个分量非负。当某一个右端项系数为负时，如量非负。当某一个右端项系数为负时，如 bi0，则把该等式约束两端同时乘以，则把该等式约束两端同时乘以-1-1，得，得到：到：-ai1x1-ai2x2-ainxn=-bi。第二章第二章 线性规划的图解法线性规划的图解法第44页，本讲稿共64页4.4.变量无符号限制的问题变量无符号限制的问题*在

29、在标标准准形形式式中中，必必须须每每一一个个变变量量均均有有非非负负约约束束。当当某某一一个个变变量量x xj j没没有有非非负负约约束束时时，可可以令以令 xj=xj-xj”其中其中xj0，xj”0 即即用用两两个个非非负负变变量量之之差差来来表表示示一一个个无无符符号号限限制制的的变变量量，当当然然x xj j的的符符号号取取决决于于x xj j和和x xj j”的大小。的大小。第二章第二章 线性规划的图解法线性规划的图解法第45页，本讲稿共64页46例例1：将以下线性规划问题转化为标准形式：将以下线性规划问题转化为标准形式Minf=2x1-3x2+4x3s.t.3x1+4x2-5x362

30、x1+x38x1+x2+x3=-9x1,x2,x3 0第二章第二章 线性规划的图解法线性规划的图解法第46页，本讲稿共64页47通通过过以以上上变变换换，可可以以得得到到以以下下标标准准形形式式的的线线性规划问题：性规划问题：Maxz=-2x1+3x2-4x3+0s1+0s2s.t.3x1+4x2-5x3+S1 =62x1 +x3 -S2=8-x1 -x2 -x3 =9x1,x2,x3,s1,s20第二章第二章 线性规划的图解法线性规划的图解法第47页，本讲稿共64页练习题：练习题：1.将以下线性规划问题转化为标准形将以下线性规划问题转化为标准形式式Minf=-x1-2x2s.t.3x1+5x

31、270-2x1-5x2=50-3x1+2x230 x10,-x2+第二章第二章 线性规划的图解法线性规划的图解法第48页，本讲稿共64页2.2.考虑下面线性规划问题考虑下面线性规划问题：Maxz=10 x1+5x2s.t.3x1+4x295x1+x28x1,x20(1)(1)用图解法求解。用图解法求解。（2 2）写出此线性规划问题的标准形式。）写出此线性规划问题的标准形式。（3 3）求出此线性规划问题的两个松弛变量的）求出此线性规划问题的两个松弛变量的值。值。第二章第二章 线性规划的图解法线性规划的图解法第49页，本讲稿共64页50图解法的灵敏度分析图解法的灵敏度分析 灵敏度分析灵敏度分析：建

32、立数学模型和求得最优：建立数学模型和求得最优解后，研究线性规划的一个或多个参解后，研究线性规划的一个或多个参数（系数）数（系数）ci,aij,bj 变化时，对最优变化时，对最优解产生的影响。解产生的影响。第二章第二章 线性规划的图解法线性规划的图解法第50页，本讲稿共64页3.1目标函数中的系数目标函数中的系数ci的灵敏度分析的灵敏度分析考虑例考虑例1的情况，的情况，ci的变化只影响目标函数的变化只影响目标函数等值线的斜率等值线的斜率目标函数目标函数z=50 x1+100 x2在在z=x2(x2=z斜率为斜率为0)到到z=x1+x2(x2=-x1+z斜率为斜率为-1)之间时，之间时，原最优解原

33、最优解x1=50，x2=100仍是最优解。仍是最优解。第二章第二章 线性规划的图解法线性规划的图解法第51页，本讲稿共64页一般情况：一般情况：z=c1x1+c2x2写成斜截式写成斜截式x2=-(c1/c2)x1+z/c2目标函数等值线的斜率为目标函数等值线的斜率为-(c1/c2)，当当-1-(c1/c2)0（*）时，时，原最优解仍是最优解。原最优解仍是最优解。第二章第二章 线性规划的图解法线性规划的图解法第52页，本讲稿共64页53假设产品假设产品的利润的利润100元不变，即元不变，即c2=100，代到式（代到式（*）并整理得）并整理得0 c1 100假设产品假设产品的利润的利润50元不变，

34、即元不变，即c1=50，代到式（代到式（*）并整理得）并整理得50 c2+第二章第二章 线性规划的图解法线性规划的图解法第53页，本讲稿共64页假若产品假若产品、的利润均改变，则可直接用的利润均改变，则可直接用式（式（*）来判断）来判断假设产品假设产品、的利润分别为的利润分别为60元、元、55元，元，则则-2-(60/55)-1已经不满足条件了。已经不满足条件了。B点已经不是最优解了。点已经不是最优解了。第二章第二章 线性规划的图解法线性规划的图解法第54页，本讲稿共64页553.2约束条件中右边系数约束条件中右边系数bj的灵敏度分析的灵敏度分析当约束条件中右边系数当约束条件中右边系数bj变化

35、时变化时,线性规划线性规划的可行域发生变化，可能引起最优解的变的可行域发生变化，可能引起最优解的变化。化。第二章第二章 线性规划的图解法线性规划的图解法第55页，本讲稿共64页考虑例考虑例1的情况：的情况：假设设备台时增加假设设备台时增加1个台时，即个台时，即b1变化为变化为301，这时可行域扩大，这时可行域扩大，最优解为最优解为x2=250和和x1+x2=301的交点的交点x1=51，x2=250。变化后的总利润变化后的总利润-变化前的总利润变化前的总利润=增加增加的利润的利润(5051+100250)-(5050+100250)=50第二章第二章 线性规划的图解法线性规划的图解法第56页，

36、本讲稿共64页x2CBADE目标函数：目标函数：Maxz=50 x1+100 x2约束条件：约束条件：s.t.x1+x23102x1+x2400 x2250 x1,x20最优解最优解x1=60 x2=250第二章第二章 线性规划的图解法线性规划的图解法第57页，本讲稿共64页约束条件的对偶价格约束条件的对偶价格:在约束条件常数项在约束条件常数项中增加中增加1个单位而使最优目标函数值得个单位而使最优目标函数值得到改进的数量称之为这个到改进的数量称之为这个约束条件的对约束条件的对偶价格偶价格.b1=301时的对偶价格为：时的对偶价格为：(5051+100250)-(5050+100250)=50第

37、二章第二章 线性规划的图解法线性规划的图解法第58页，本讲稿共64页59假设原料假设原料A增加增加1千克时，即千克时，即b2变化为变化为401，这时可行域扩大，但，这时可行域扩大，但最优解仍为最优解仍为x2=250和和x1+x2=300的交点的交点x1=50，x2=250。此变化对总利润无影响，。此变化对总利润无影响，该约束条件的对偶价格为该约束条件的对偶价格为0。解释：解释：原最优解没有把原料原最优解没有把原料A用尽，有用尽，有50千千克的剩余，因此增加克的剩余，因此增加1千克值增加了库存，千克值增加了库存，而不会增加利润。而不会增加利润。第二章第二章 线性规划的图解法线性规划的图解法第59

38、页，本讲稿共64页在一定范围内，当约束条件右边常数增加在一定范围内，当约束条件右边常数增加1个单位时个单位时:（1）若约束条件的对偶价格大于）若约束条件的对偶价格大于0，则其最，则其最优目标函数值得到改善（变好）；优目标函数值得到改善（变好）；（2）若约束条件的对偶价格小于）若约束条件的对偶价格小于0，则其最，则其最优目标函数值受到影响（变坏）；优目标函数值受到影响（变坏）；（3）若约束条件的对偶价格等于）若约束条件的对偶价格等于0，则最优，则最优目标函数值不变。目标函数值不变。第二章第二章 线性规划的图解法线性规划的图解法第60页，本讲稿共64页例题：考虑下面的线性规划问题例题：考虑下面的线

39、性规划问题Maxz=2x1+3x2s.t.x1+x2102x1+x24x1+3x2242x1+x216x1,x20第二章第二章 线性规划的图解法线性规划的图解法第61页，本讲稿共64页(1)(1)用图解法求解用图解法求解.(2)(2)假定假定c2c2值不变值不变,求出使其最优解不变的求出使其最优解不变的c1c1值值的变化范围的变化范围.(3)(3)假定假定c1c1值不变值不变,求出使其最优解不变的求出使其最优解不变的c2c2值值的变化范围的变化范围.(4)(4)当当c1c1值从值从2 2变为变为4,c24,c2值不变时值不变时,求出新的最求出新的最优解优解.(5)(5)当当c1c1不变不变,c

40、2,c2值从值从3 3变为变为1 1时时,求出新的最优求出新的最优解解.第二章第二章 线性规划的图解法线性规划的图解法第62页，本讲稿共64页第二章第二章 线性规划的图解法线性规划的图解法246810246810 x1+3x2=242x1+x2=4x1+x2=1024x2 162x1+x2=16A A第63页，本讲稿共64页2.某某农农户户计计划划用用12公公顷顷耕耕地地生生产产玉玉米米，大大豆豆和和地地瓜瓜，可可投投入入48个个劳劳动动日日，资资金金360元元。生生产产玉玉米米1公公顷顷，需需6个个劳劳动动日日，资资金金36元元，可可获获净净收收入入200元元；生生产产1公公顷顷大大豆豆，需需6个个劳劳动动日日，资资金金24元元，可可获获净净收收入入150元元；生生产产1公公顷顷地地瓜瓜需需2个个劳劳动动日日，资资金金18元元，可可获获净净收收入入1200元元，问问怎怎样样安安排排才才能能使使总总的的净收入最高。净收入最高。第二章第二章 线性规划的图解法线性规划的图解法第64页，本讲稿共64页