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

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,管理运筹学,第二章：线性规划的图解法,第一节：线性规划问题的提出,第二节：线性规划的图解法,第三节：图解法的灵敏度分析,本章的重点和难点,：,2,：图解法的灵敏度分析,1,：线性规划的图解法,线性规划的定义,求线性目标函数在,线性约束条件,下的最大值或最小值的问题，统称为线性规划问题。,满足线性约束条件的解叫做,可行解,，由所有可行解组成的集合叫做,可行域,。,决策变量、约束条件、目标函数,是线性规划的三要素,.,第二章 线性规划的图解法,4,在管理中一些典型的线性规划应用,合理利用线材问题：如何在保证生产的条件下，下料最少,配料问题：在原料供应量的限制下如何获取最大利润,投资问题：从投资项目中选取方案，使投资回报最大,第二章 线性规划的图解法,产品生产计划：合理利用人力、物力、财力等，使获利最大,劳动力安排：用最少的劳动力来满足工作的需要,运输问题：如何制定调运方案，使总运费最小,第二章 线性规划的图解法,问题,1:,某工厂计划生产甲、乙两种产品，,生产,1kg,的甲需耗煤,9t,、电力,4kw.h,、油,3t,；,生产,1kg,的乙需耗煤,4t,、电力,5kw.h,、油,10t,；,该厂现有煤,360t,、电力,200kw.h,、油,300t,。,已知甲产品每千克的售价为,7,万元、乙产品每千克的售价为,12,万元。,在上述条件下决定生产方案，使得总收入最大,。,第二章 线性规划的图解法,问题,1,具体数据如表所示：,资源 产品,单耗,资源,甲 乙,资源限量,煤,(t),电,(,kw.h,),油,(t),9 4,4 5,3 10,360,200,300,单位产品价格,7 12,提出和形成问题,建立模型,求解,结果的分析和应用,第二章 线性规划的图解法,总收入记为,f,则,f,=7,x,1,+12,x,2,，为体现对其求极大化，在,f,的前面冠以极大号,Max,，,也就是：,甲、乙产品的计划产量，记为,x,1,，,x,2,；,在本例中,资源煤、电、油的数量是有限的，对产品甲和乙的生产量构成了约束，表示为：,决策变量：,目标函数：,约束条件：,Max,（,maximize,最大化）,Min,(minimum),s.t,.,(subject to,受制于,),第二章 线性规划的图解法,解：设安排甲、乙产量分别为,x,1,，,x,2,总收入为,f,，则该问题的数学模型为：,第二章 线性规划的图解法,（,1,）决策变量：甲、乙产品的,产量,x,1,，,x,2,线性规划模型的,三个基本要素：（也是所有规划问题的三个基本要素）,：,决策变量：需要决策的量，即等待求解的未知数。,目标函数：想要达到的目标，用决策变量的表达式表示。,约束条件：由于资源有限，为了实现目标有哪些资源限制，用决策变量的等式或不等式表示。,（,3,）约束条件：,（,2,）目标函数：总收入最大,，,Max f,=7,x,1,+12,x,2,第二章 线性规划的图解法,什么是线性规划模型：,决策变量为可控的连续变量。,目标函数和约束条件都是线性的。,x,1,0,，,x,2,0,x,1,=0,1,2,3n,第二章 线性规划的图解法,例,2.,某工厂在计划期内要安排,、,两种产品的生产，已知生产单位产品所需的设备台时及,A,、,B,两种原材料的消耗、资源的限制，如下表：,问题：工厂应分别生产多少单位,、,产品才能使工厂获利最多？,第二章 线性规划的图解法,目标函数：,Maxz,=50 x,1,+100 x,2,约束条件：,s.t,.x,1,+x,2,300,2 x,1,+x,2,400,x,2,250,x,1,x,2,0,第二章 线性规划的图解法,一般形式,目标函数：,Max,（,Min,）,z=c,1,x,1,+c,2,x,2,+,c,n,x,n,约束条件：,s.t,.,a,11,x,1,+,a,12,x,2,+,a,1n,x,n,（,=,）,b,1,a,21,x,1,+,a,22,x,2,+,a,2n,x,n,（,=,）,b,2,a,m1,x,1,+,a,m2,x,2,+,a,mn,x,n,（,=,）,b,m,x,1,，,x,2,，,，,x,n,0,第二章 线性规划的图解法,对于只有两个变量的简单的线性规划问题，一般采用图解法求解。这种方法仅适用于只有两个变量的线性规划问题。它的特点是直观而易于理解，但实用价值不大。,第二章 线性规划的图解法,1.,基本概念,（,1,）可行解：,满足约束条件的决策变量的取值,（,2,）可行域：可行解的全体,（,3,）最优解：使目标函数取得最优值的可行解,（,4,）最优值：最优解代入目标函数所得到的值,第二章 线性规划的图解法,例,3.,用图解法对下列线性规划模型进行求解,。,Max Z=2,x,1,+3,x,2,x,1,+2,x,2,8,4x,1,16,x,2,12,x,1,x,2,0,s.t,.,第二章 线性规划的图解法,18,图解法求解的步骤：,分别取决策变量,X,1,X,2,为坐标向量建立直角坐标系。在直角坐标系里，图上任意一点的坐标代表了决策变量的一组值。,第二章 线性规划的图解法,9,8,7,6,5,4,3,2,1,0,x,2,|,123456789,x,1,x,1,+2,x,2,8,4,x,1,16,4,x,2,12,x,1,+2,x,2,8,4,x,1,16,4,x,2,12,x,1,、,x,2,0,第二章 线性规划的图解法,9,8,7,6,5,4,3,2,1,0,|,123456789,x,1,x,1,+2,x,2,8,4,x,1,16,4,x,2,12,可行域,A,B,C,D,O,可行解：满足约束条件的解。红色区域中的每一个点（包括边界点）都是可行解。此区域是就是可行域。,9,8,7,6,5,4,3,2,1,0,x,2,|,123456789,x,1,x,1,+2,x,2,8,4,x,1,16,4,x,2,12,A,B,C,D,O,目标函数,Z=2x,1,+3x,2,在这个坐标平面上，它可以表示以,Z,为参数、,-2/3,为斜率的一族平行线,：,位于同一直线上的点，具有相同的目标函数，称为,“,等值线,”,。,9,8,7,6,5,4,3,2,1,0,x,2,当,Z,值由小变大时，直线,沿其法线方向向右上方移动。当移动到,C,时，,Z,值在可行域的边界上实现最大化。最优解（,4,，,2,），,Z=14,。,|,123456789,x,1,x,1,+2,x,2,8,4,x,1,16,4,x,2,12,A,B,C,D,O,最优解,(4,2),最优生产方案,:,产品,1,生产,4kg,，产品,2,生产,2kg,，最大利润,14,元,(,最优值）。,结论：,线性规划问题如果有最优解,则最优解一定在可行域的边界上取得,.,第二章 线性规划的图解法,无穷多最优解,9,8,7,6,5,4,3,2,1,0,x,2,|,123456789,x,1,x,1,+2,x,2,8,4,x,1,16,4,x,2,12,O,可行域,第二章 线性规划的图解法,当移动到,AB,线段时，,Z,值在线段,CD,上实现最大化。,线段,CD,上的任意一点都使,Z,取得相同的最大值，这个线性规划问题有无穷多最优解。,9,8,7,6,5,4,3,2,1,0,x,2,|,123456789,x,1,x,1,+2,x,2,8,4,x,1,16,4,x,2,12,A,B,C,D,O,可行域,第二章 线性规划的图解法,无可行解,可行域为空集，无可行解，当然也无最优解。,9,8,7,6,5,4,3,2,1,0,x,2,|,123456789,x,1,O,l,2,l,1,第二章 线性规划的图解法,Maxz,=x,1,+2 x,2,s.t,.x,1,+2 x,2,8,4x,1,16,4x,2,12,x,1,3,x,2,3,无界解,x,1,x,2,0,1 2 3 4 5 6 7 8 9,654321,线性规划问题可行域无界，目标函数可以增大到无穷大,第二章 线性规划的图解法,该问题如果求目标函数的最小值，由下图可以看出在顶点,B,取得最优解：,x,1,x,2,0,1 2 3 4 5 6 7 8 9,654321,B,（,1,，,0,）,第二章 线性规划的图解法,唯一解,无穷多解,无有限最优解,无可行解,有最优解,无最优解,求解一个线性规划问题就是要判断该问题属于那种情况，当问题有最优解时，还需要在可行区域中求出使目标函数达到最优值的点，也就是最优解，以及目标函数的最优值。,第二章 线性规划的图解法,练习题：,1.,考虑下面线性规划问题,：,Maxz,=2 x,1,+3 x,2,s.t,.x,1,+2 x,2,6,5x,1,+3 x,2,15,x,1,x,2,0,（,1,）画出其可行域,（,2,）当,Z=6,时，画出等值线,2 x,1,+3 x,2,=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,解：目标函数：,Min f=2x,1,+3 x,2,约束条件：,s.t,.x,1,+x,2,350,x,1,125,2 x,1,+x,2,600,x,1,x,2,0,采用图解法。如下图：得,Q,点坐标（,250,，,100,）为最优解。,第二章 线性规划的图解法,得,Q,点坐标（,250,，,100,）为最优解,X,1,=250,x,2,=100,时,minf,=800,100,200,300,400,500,600,100,200,300,400,600,500,x,1,=125,x,1,+x,2,=350,2x,1,+x,2,=600,x,1,x,2,Q,第二章 线性规划的图解法,例,1.,某工厂在计划期内要安排,、,两种产品的生产，已知生产单位产品所需的设备台时及,A,、,B,两种原材料的消耗、资源的限制，如下表：,问题：工厂应分别生产多少单位,、,产品才能使工厂获利最多？,第二章 线性规划的图解法,数学模型为,：,求解得：,x,1,=50,x,2,=250,maxz,=27500,第二章 线性规划的图解法,36,引入松驰变量（含义是资源的剩余量）,例,1,中引入,s,1,，,s,2,，,s,3,模型化为,Max z=50 x,1,+100 x,2,+0 s,1,+0 s,2,+0 s,3,s.t,.x,1,+x,2,+s,1,=300,2 x,1,+x,2,+s,2,=400,x,2,+s,3,=,250,x,1,x,2,s,1,s,2,s,3,0,对于最优解,x,1,=50 x,2,=250,，,s,1,=0 s,2,=50 s,3,=0,说明：生产,50,单位,产品和,250,单位,产品将消耗完所有可能的设备台时数及原料,B,，但对原料,A,则还剩余,50,千克。,第二章 线性规划的图解法,松弛变量和剩余变量,松弛变量,：在线性规划中，对于“”约束条件中没有使用的资源或能力称之为松弛变量。,剩余变量,：在线性规划中，对于“”约束条件，可以增加一些代表最低限约束的超过量，称之为剩余变量。,第二章 线性规划的图解法,38,线性规划的标准化,一般形式,目标函数,:,Max,（,Min,）,z=c,1,x,1,+c,2,x,2,+,c,n,x,n,约束条件：,s.t,.,a,11,x,1,+,a,12,x,2,+,a,1n,x,n,（,=,）,b,1,a,21,x,1,+,a,22,x,2,+,a,2n,x,n,（,=,）,b,2,a,m1,x,1,+,a,m2,x,2,+,a,mn,x,n,（,=,）,b,m,x,1,，,x,2,，,，,x,n,0,第二章 线性规划的图解法,标准形式,目标函数：,Max z =c,1,x,1,+c,2,x,2,+,c,n,x,n,约束条件：,s.t,.,a,11,x,1,+,a,12,x,2,+,a,1n,x,n,=b,1,a,21,x,1,+,a,22,x,2,+,a,2n,x,n,=b,2,a,m1,x,1,+,a,m2,x,2,+,a,mn,x,n,=,b,m,x,1,，,x,2,，,，,x,n,0,，,b,i,0,第二章 线性规划的图解法,40,可以看出，线性规划的标准形式有如下四个特点：,目标最大化；,约束为等式；,决策变量均非负；,右端项非负。,第二章 线性规划的图解法,41,1.,极小化目标函数的问题：,设目标函数为,:,Min f=c,1,x,1,+c,2,x,2,+,c,n,x,n,(,可以,),令,z,-f,，,则该极小化问题与下面的极大化问题有相同的最优解,即,Max z=-c,1,x,1,-c,2,x,2,-,c,n,x,n,但必须注意，尽管以上两个问题的最优解相同，但它们最优解的目标函数值却相差一个符号，即,Min f,-Max z,第二章 线性规划的图解法,42,2,、约束条件不是等式的问题,：,设约束条件为,a,i1,x,1,+a,i2,x,2,+,a,in,x,n,b,i,可以引进一个新的变量,s,，使它等于约束右边与左边之差,s=b,i,(a,i1,x,1,+a,i2,x,2,+,a,in,x,n,),显然，,s,也具有非负约束，即,s,0,，,这时新的约束条件成为,a,i1,x,1,+a,i2,x,2,+,a,in,x,n,+s,=b,i,第二章 线性规划的图解法,43,当约束条件为,a,i1,x,1,+a,i2,x,2,+,a,in,x,n,b,i,时，,类似地令,s=(a,i1,x,1,+a,i2,x,2,+,a,in,x,n,)-b,i,显然，,s,也具有非负约束，即,s,0,，这时新的约束条件成为,a,i1,x,1,+a,i2,x,2,+,a,in,x,n,-s,=b,i,第二章 线性规划的图解法,3.,右端项有负值的问题：,在标准形式中，要求右端项必须每一个分量非负。当某一个右端项系数为负时，如,b,i,0,，则把该等式约束两端同时乘以,-1,，得到：,-a,i1,x,1,-a,i2,x,2,-,a,in,x,n,=-b,i,。,第二章 线性规划的图解法,4.,变量无符号限制的问题*,在标准形式中，必须每一个变量均有非负约束。当某一个变量,x,j,没有非负约束时，可以令,x,j,=,x,j,-,x,j,”,其中,x,j,0,，,x,j,”,0,即用两个非负变量之差来表示一个无符号限制的变量，当然,x,j,的符号取决于,x,j,和,x,j,”,的大小。,第二章 线性规划的图解法,46,例,1,：将以下线性规划问题转化为标准形式,Min,f,=2,x,1,-3,x,2,+4,x,3,s.t,.3,x,1,+4,x,2,-5,x,3,6,2,x,1,+,x,3,8,x,1,+,x,2,+,x,3,=-9,x,1,x,2,x,3,0,第二章 线性规划的图解法,47,通过以上变换，可以得到以下标准形式的线性规划问题：,Max,z,=-2,x,1,+3,x,2,-4,x,3,+0s,1,+0s,2,s.t,.3,x,1,+4,x,2,-5,x,3,+S,1,=6,2,x,1,+,x,3,-S,2,=8,-,x,1,-,x,2,-,x,3,=9,x,1,x,2,x,3,s,1,s,2,0,第二章 线性规划的图解法,练习题：,1.,将以下线性规划问题转化为标准形式,Min,f,=-,x,1,-2,x,2,s.t,.3,x,1,+5,x,2,70,-2,x,1,-5,x,2,=50,-3,x,1,+2,x,2,30,x,1,0,-,x,2,+,第二章 线性规划的图解法,2.,考虑下面线性规划问题,：,Maxz,=10,x,1,+5,x,2,s.t,.3,x,1,+4,x,2,9,5,x,1,+,x,2,8,x,1,x,2,0,(1),用图解法求解。,（,2,）写出此线性规划问题的标准形式。,（,3,）求出此线性规划问题的两个松弛变量的值。,第二章 线性规划的图解法,50,图解法的灵敏度分析,灵敏度分析,：建立数学模型和求得最优解后，研究线性规划的一个或多个参数（系数）,c,i,a,ij,b,j,变化时，对最优解产生的影响。,第二章 线性规划的图解法,3.1,目标函数中的系数,c,i,的灵敏度分析,考虑例,1,的情况，,c,i,的变化只影响目标函数等值线的斜率,目标函数,z=50 x,1,+100 x,2,在,z=x,2,(x,2,=z,斜率为,0,),到,z=x,1,+x,2,(x,2,=-x,1,+z,斜率为,-1,),之间时，原最优解,x,1,=50,，,x,2,=100,仍是最优解。,第二章 线性规划的图解法,一般情况：,z=c,1,x,1,+c,2,x,2,写成斜截式,x,2,=-(c,1,/c,2,)x,1,+z/c,2,目标函数等值线的斜率为,-(c,1,/c,2,),，,当,-1,-(c,1,/c,2,),0,（*）时，,原最优解仍是最优解。,第二章 线性规划的图解法,53,假设产品,的利润,100,元不变，即,c,2,=100,，代到式（*）并整理得,0,c,1,100,假设产品,的利润,50,元不变，即,c,1,=50,，代到式（*）并整理得,50,c,2,+,第二章 线性规划的图解法,假若产品,、,的利润均改变，则可直接用式（*）来判断,假设产品,、,的利润分别为,60,元、,55,元，则,-2,-(60/55),-1,已经不满足条件了。,B,点已经不是最优解了。,第二章 线性规划的图解法,55,3.2,约束条件中右边系数,b,j,的灵敏度分析,当约束条件中右边系数,b,j,变化时,线性规划的可行域发生变化，可能引起最优解的变化。,第二章 线性规划的图解法,考虑例,1,的情况：,假设设备台时增加,1,个台时，即,b,1,变化为,301,，这时可行域扩大，,最优解为,x,2,=250,和,x,1,+x,2,=301,的交点,x,1,=51,，,x,2,=250,。,变化后的总利润,-,变化前的总利润,=,增加的利润,(5051+100250)-(50 50+100 250)=50,第二章 线性规划的图解法,x,2,C,B,A,D,E,目标函数：,Maxz,=50 x1+100 x2,约束条件：,s.t,.x1+x2 310,2 x1+x2 400,x2 250,x1,x2 0,最优解,x1=60,x2 =250,第二章 线性规划的图解法,约束条件的对偶价格,:,在约束条件常数项中增加,1,个单位而使最优目标函数值得到改进的数量称之为这个,约束条件的对偶价格,.,b,1,=301,时的对偶价格为：,(5051+100250)-(50 50+100 250)=50,第二章 线性规划的图解法,59,假设原料,A,增加,1,千克时，即,b,2,变化为,401,，这时可行域扩大，但,最优解仍为,x,2,=250,和,x,1,+x,2,=300,的交点,x,1,=50,，,x,2,=250,。此变化对总利润无影响，该约束条件的对偶价格为,0,。,解释：,原最优解没有把原料,A,用尽，有,50,千克的剩余，因此增加,1,千克值增加了库存，而不会增加利润。,第二章 线性规划的图解法,在一定范围内，当约束条件右边常数增加,1,个单位时,:,（,1,）若约束条件的对偶价格大于,0,，则其最优目标函数值得到改善（变好）；,（,2,）若约束条件的对偶价格小于,0,，则其最优目标函数值受到影响（变坏）；,（,3,）若约束条件的对偶价格等于,0,，则最优目标函数值不变。,第二章 线性规划的图解法,例题：考虑下面的线性规划问题,Maxz,=2,x,1,+3,x,2,s.t,.,x,1,+,x,2,10,2,x,1,+,x,2,4,x,1,+3,x,2,24,2,x,1,+,x,2,16,x,1,x,2,0,第二章 线性规划的图解法,(1),用图解法求解,.,(2),假定,c2,值不变,求出使其最优解不变的,c1,值的变化范围,.,(3),假定,c1,值不变,求出使其最优解不变的,c2,值的变化范围,.,(4),当,c1,值从,2,变为,4,c2,值不变时,求出新的最优解,.,(5),当,c1,不变,c2,值从,3,变为,1,时,求出新的最优解,.,第二章 线性规划的图解法,第二章 线性规划的图解法,2,4,6,8,10,2,4,6,8,10,x,1,+3x,2,=24,2x,1,+x,2,=4,x,1,+x,2,=10,24,x,2,16,2x,1,+x,2,=16,A,2.,某农户计划用,12,公顷耕地生产玉米，大豆和地瓜，可投入,48,个劳动日，资金,360,元。生产玉米,1,公顷，需,6,个劳动日，资金,36,元，可获净收入,200,元；生产,1,公顷大豆，需,6,个劳动日，资金,24,元，可获净收入,150,元；生产,1,公顷地瓜需,2,个劳动日，资金,18,元，可获净收入,1200,元，问怎样安排才能使总的净收入最高。,第二章 线性规划的图解法,