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

管理运筹学,第二章：线性规划的图解法,第一节：线性规划问题的提出,第二节：线性规划的图解法,第三节：图解法的灵敏度分析,本章的重点和难点：,2：图解法的灵敏度分析,1：线性规划的图解法,线性规划的定义,求线性目标函数在线性约束条件下的最大值或最小值的问题，统称为线性规划问题。满足线性约束条件的解叫做可行解，由所有可行解组成的集合叫做可行域。决策变量、约束条件、目标函数是线性规划的三要素.,第二章线性规划的图解法,4,在管理中一些典型的线性规划应用合理利用线材问题：如何在保证生产的条件下，下料最少配料问题：在原料供应量的限制下如何获取最大利润投资问题：从投资项目中选取方案，使投资回报最大,第二章线性规划的图解法,产品生产计划：合理利用人力、物力、财力等，使获利最大劳动力安排：用最少的劳动力来满足工作的需要运输问题：如何制定调运方案，使总运费最小,第二章线性规划的图解法,问题1:某工厂计划生产甲、乙两种产品，生产1kg的甲需耗煤9t、电力4kw.h、油3t；生产1kg的乙需耗煤4t、电力5kw.h、油10t；该厂现有煤360t、电力200kw.h、油300t。已知甲产品每千克的售价为7万元、乙产品每千克的售价为12万元。在上述条件下决定生产方案，使得总收入最大。,第二章线性规划的图解法,问题1具体数据如表所示：,第二章线性规划的图解法,总收入记为f,则f=7x1+12x2，为体现对其求极大化，在f的前面冠以极大号Max，也就是：,甲、乙产品的计划产量，记为x1，x2；,在本例中,资源煤、电、油的数量是有限的，对产品甲和乙的生产量构成了约束，表示为：,决策变量：,目标函数：,约束条件：,Max（maximize最大化）Min(minimum)s.t.(subjectto受制于),第二章线性规划的图解法,解：设安排甲、乙产量分别为x1，x2,总收入为f，则该问题的数学模型为：,第二章线性规划的图解法,（1）决策变量：甲、乙产品的产量x1，x2,线性规划模型的三个基本要素：（也是所有规划问题的三个基本要素）：,决策变量：需要决策的量，即等待求解的未知数。,目标函数：想要达到的目标，用决策变量的表达式表示。,约束条件：由于资源有限，为了实现目标有哪些资源限制，用决策变量的等式或不等式表示。,（3）约束条件：,（2）目标函数：总收入最大，Maxf=7x1+12x2,第二章线性规划的图解法,什么是线性规划模型：,决策变量为可控的连续变量。,目标函数和约束条件都是线性的。,第二章线性规划的图解法,例2.某工厂在计划期内要安排、两种产品的生产，已知生产单位产品所需的设备台时及A、B两种原材料的消耗、资源的限制，如下表：,问题：工厂应分别生产多少单位、产品才能使工厂获利最多？,第二章线性规划的图解法,目标函数：Maxz=50 x1+100 x2约束条件：s.t.x1+x23002x1+x2400 x2250 x1,x20,第二章线性规划的图解法,一般形式目标函数：Max（Min）z=c1x1+c2x2+cnxn约束条件：s.t.a11x1+a12x2+a1nxn（=,）b1a21x1+a22x2+a2nxn（=,）b2am1x1+am2x2+amnxn（=,）bmx1，x2，xn0,第二章线性规划的图解法,对于只有两个变量的简单的线性规划问题，一般采用图解法求解。这种方法仅适用于只有两个变量的线性规划问题。它的特点是直观而易于理解，但实用价值不大。,第二章线性规划的图解法,1.基本概念（1）可行解：满足约束条件的决策变量的取值（2）可行域：可行解的全体（3）最优解：使目标函数取得最优值的可行解（4）最优值：最优解代入目标函数所得到的值,第二章线性规划的图解法,例3.用图解法对下列线性规划模型进行求解。,s.t.,第二章线性规划的图解法,18,图解法求解的步骤：分别取决策变量X1,X2为坐标向量建立直角坐标系。在直角坐标系里，图上任意一点的坐标代表了决策变量的一组值。,第二章线性规划的图解法,9876543210,x2,|123456789,x1,x1+2x28,4x116,4x212,x1+2x284x1164x212x1、x20,第二章线性规划的图解法,9876543210,|123456789,x1,可行域,可行解：满足约束条件的解。红色区域中的每一个点（包括边界点）都是可行解。此区域是就是可行域。,9876543210,x2,目标函数Z=2x1+3x2在这个坐标平面上，它可以表示以Z为参数、-2/3为斜率的一族平行线：,位于同一直线上的点，具有相同的目标函数，称为“等值线”。,9876543210,x2,当Z值由小变大时，直线沿其法线方向向右上方移动。当移动到C时，Z值在可行域的边界上实现最大化。最优解（4，2），Z=14。,最优解(4,2),最优生产方案:产品1生产4kg，产品2生产2kg，最大利润14元(最优值）。,结论：线性规划问题如果有最优解,则最优解一定在可行域的边界上取得.,第二章线性规划的图解法,无穷多最优解,9876543210,x2,|123456789,x1,x1+2x28,4x116,4x212,O,可行域,第二章线性规划的图解法,当移动到AB线段时，Z值在线段CD上实现最大化。线段CD上的任意一点都使Z取得相同的最大值，这个线性规划问题有无穷多最优解。,9876543210,x2,|123456789,x1,x1+2x28,4x116,4x212,A,B,C,D,O,可行域,第二章线性规划的图解法,无可行解,可行域为空集，无可行解，当然也无最优解。,9876543210,x2,|123456789,x1,l2,l1,第二章线性规划的图解法,Maxz=x1+2x2s.t.x1+2x284x1164x212x13x23,无界解,线性规划问题可行域无界，目标函数可以增大到无穷大,第二章线性规划的图解法,该问题如果求目标函数的最小值，由下图可以看出在顶点B取得最优解：,B（1，0）,第二章线性规划的图解法,唯一解无穷多解无有限最优解无可行解,有最优解,无最优解,求解一个线性规划问题就是要判断该问题属于那种情况，当问题有最优解时，还需要在可行区域中求出使目标函数达到最优值的点，也就是最优解，以及目标函数的最优值。,第二章线性规划的图解法,练习题：1.考虑下面线性规划问题：Maxz=2x1+3x2s.t.x1+2x265x1+3x215x1,x20（1）画出其可行域（2）当Z=6时，画出等值线2x1+3x2=6（3）用图解法求出其最优解以及最优目标函数值,第二章线性规划的图解法,31,例2：.某公司由于生产需要，共需要A，B两种原料至少350吨（A，B两种材料有一定替代性），其中A原料至少购进125吨。但由于A，B两种原料的规格不同，各自所需的加工时间也是不同的，加工每吨A原料需要2个小时，加工每吨B原料需要1小时，而公司总共有600个加工小时。又知道每吨A原料的价格为2万元，每吨B原料的价格为3万元，试问在满足生产需要的前提下，在公司加工能力的范围内，如何购买A，B两种原料，使得购进成本最低？,第二章线性规划的图解法,32,解：目标函数：Minf=2x1+3x2约束条件：s.t.x1+x2350 x11252x1+x2600 x1,x20采用图解法。如下图：得Q点坐标（250，100）为最优解。,第二章线性规划的图解法,得Q点坐标（250，100）为最优解X1=250,x2=100时minf=800,100,200,300,400,500,600,100,200,300,400,600,500,x1=125,x1+x2=350,2x1+x2=600,x1,x2,Q,第二章线性规划的图解法,例1.某工厂在计划期内要安排、两种产品的生产，已知生产单位产品所需的设备台时及A、B两种原材料的消耗、资源的限制，如下表：问题：工厂应分别生产多少单位、产品才能使工厂获利最多？,第二章线性规划的图解法,数学模型为：求解得：x1=50,x2=250maxz=27500,第二章线性规划的图解法,36,引入松驰变量（含义是资源的剩余量）例1中引入s1，s2，s3模型化为Maxz=50 x1+100 x2+0s1+0s2+0s3s.t.x1+x2+s1=3002x1+x2+s2=400 x2+s3=250 x1,x2,s1,s2,s30对于最优解x1=50 x2=250，s1=0s2=50s3=0说明：生产50单位产品和250单位产品将消耗完所有可能的设备台时数及原料B，但对原料A则还剩余50千克。,第二章线性规划的图解法,松弛变量和剩余变量,松弛变量：在线性规划中，对于“”约束条件中没有使用的资源或能力称之为松弛变量。剩余变量：在线性规划中，对于“”约束条件，可以增加一些代表最低限约束的超过量，称之为剩余变量。,第二章线性规划的图解法,38,线性规划的标准化一般形式目标函数:Max（Min）z=c1x1+c2x2+cnxn约束条件：s.t.a11x1+a12x2+a1nxn（=,）b1a21x1+a22x2+a2nxn（=,）b2am1x1+am2x2+amnxn（=,）bmx1，x2，xn0,第二章线性规划的图解法,标准形式目标函数：Maxz=c1x1+c2x2+cnxn约束条件：s.t.a11x1+a12x2+a1nxn=b1a21x1+a22x2+a2nxn=b2am1x1+am2x2+amnxn=bmx1，x2，xn0，bi0,第二章线性规划的图解法,40,可以看出，线性规划的标准形式有如下四个特点：目标最大化；约束为等式；决策变量均非负；右端项非负。,第二章线性规划的图解法,41,1.极小化目标函数的问题：设目标函数为:Minf=c1x1+c2x2+cnxn(可以)令z-f，则该极小化问题与下面的极大化问题有相同的最优解即Maxz=-c1x1-c2x2-cnxn但必须注意，尽管以上两个问题的最优解相同，但它们最优解的目标函数值却相差一个符号，即Minf-Maxz,第二章线性规划的图解法,42,2、约束条件不是等式的问题：设约束条件为ai1x1+ai2x2+ainxnbi可以引进一个新的变量s，使它等于约束右边与左边之差s=bi(ai1x1+ai2x2+ainxn)显然，s也具有非负约束，即s0，这时新的约束条件成为ai1x1+ai2x2+ainxn+s=bi,第二章线性规划的图解法,43,当约束条件为ai1x1+ai2x2+ainxnbi时，类似地令s=(ai1x1+ai2x2+ainxn)-bi显然，s也具有非负约束，即s0，这时新的约束条件成为ai1x1+ai2x2+ainxn-s=bi,第二章线性规划的图解法,3.右端项有负值的问题：在标准形式中，要求右端项必须每一个分量非负。当某一个右端项系数为负时，如bi0，则把该等式约束两端同时乘以-1，得到：-ai1x1-ai2x2-ainxn=-bi。,第二章线性规划的图解法,4.变量无符号限制的问题*在标准形式中，必须每一个变量均有非负约束。当某一个变量xj没有非负约束时，可以令xj=xj-xj”其中xj0，xj”0即用两个非负变量之差来表示一个无符号限制的变量，当然xj的符号取决于xj和xj”的大小。,第二章线性规划的图解法,46,例1：将以下线性规划问题转化为标准形式Minf=2x1-3x2+4x3s.t.3x1+4x2-5x362x1+x38x1+x2+x3=-9x1,x2,x30,第二章线性规划的图解法,47,通过以上变换，可以得到以下标准形式的线性规划问题：Maxz=-2x1+3x2-4x3+0s1+0s2s.t.3x1+4x2-5x3+S1=62x1+x3-S2=8-x1-x2-x3=9x1,x2,x3,s1,s20,第二章线性规划的图解法,练习题：1.将以下线性规划问题转化为标准形式Minf=-x1-2x2s.t.3x1+5x270-2x1-5x2=50-3x1+2x230 x10,-x2+,第二章线性规划的图解法,2.考虑下面线性规划问题：Maxz=10 x1+5x2s.t.3x1+4x295x1+x28x1,x20(1)用图解法求解。（2）写出此线性规划问题的标准形式。（3）求出此线性规划问题的两个松弛变量的值。,第二章线性规划的图解法,50,图解法的灵敏度分析灵敏度分析：建立数学模型和求得最优解后，研究线性规划的一个或多个参数（系数）ci,aij,bj变化时，对最优解产生的影响。,第二章线性规划的图解法,3.1目标函数中的系数ci的灵敏度分析考虑例1的情况，ci的变化只影响目标函数等值线的斜率目标函数z=50 x1+100 x2在z=x2(x2=z斜率为0)到z=x1+x2(x2=-x1+z斜率为-1)之间时，原最优解x1=50，x2=100仍是最优解。,第二章线性规划的图解法,一般情况：z=c1x1+c2x2写成斜截式x2=-(c1/c2)x1+z/c2目标函数等值线的斜率为-(c1/c2)，当-1-(c1/c2)0（*）时，原最优解仍是最优解。,第二章线性规划的图解法,53,假设产品的利润100元不变，即c2=100，代到式（*）并整理得0c1100假设产品的利润50元不变，即c1=50，代到式（*）并整理得50c2+,第二章线性规划的图解法,假若产品、的利润均改变，则可直接用式（*）来判断假设产品、的利润分别为60元、55元，则-2-(60/55)-1已经不满足条件了。B点已经不是最优解了。,第二章线性规划的图解法,55,3.2约束条件中右边系数bj的灵敏度分析当约束条件中右边系数bj变化时,线性规划的可行域发生变化，可能引起最优解的变化。,第二章线性规划的图解法,考虑例1的情况：假设设备台时增加1个台时，即b1变化为301，这时可行域扩大，最优解为x2=250和x1+x2=301的交点x1=51，x2=250。变化后的总利润-变化前的总利润=增加的利润(5051+100250)-(5050+100250)=50,第二章线性规划的图解法,x2,C,B,A,D,E,目标函数：Maxz=50 x1+100 x2约束条件：s.t.x1+x23102x1+x2400 x2250 x1,x20最优解x1=60 x2=250,第二章线性规划的图解法,约束条件的对偶价格:在约束条件常数项中增加1个单位而使最优目标函数值得到改进的数量称之为这个约束条件的对偶价格.b1=301时的对偶价格为：(5051+100250)-(5050+100250)=50,第二章线性规划的图解法,59,假设原料A增加1千克时，即b2变化为401，这时可行域扩大，但最优解仍为x2=250和x1+x2=300的交点x1=50，x2=250。此变化对总