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

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,管 理 运 筹 学,1,第,2,章,线性规划的图解法,2,线性规划的图解法,1,线性规划问题的数学模型,3,图解法的灵敏度分析,1,线性规划问题的数学模型,1.,规划问题,生产和经营管理中经常提出如何合理安排，使人力、物力等各种资源得到充分利用，获得最大的效益，这就是规划问题。,线性规划通常解决下列两类问题：,（,1,）当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源（如资金、设备、原标材料、人工、时间等）去完成确定的任务或目标,（,2,）在一定的资源条件限制下，如何组织安排生产获得最好的经济效益（如产品量最多、利润最大,.,）,线性规划问题的数学模型,例,1.1,如图所示，如何截取,x,使铁皮所围成的容积最大？,x,a,线性规划问题的数学模型,例,1.2,某企业计划生产甲、乙两种产品。这些产品分别要在,A,、,B,、,C,、,D,、四种不同的设备上加工。按工艺资料规定，单件产品在不同设备上加工所需要的台时如下表所示，企业决策者应如何安排生产计划，使企业总的利润最大？,设 备,产 品,A,B,C,D,利润（元）,甲,2,1,4,0,2,乙,2,2,0,4,3,有 效 台 时,12,8,16,12,线性规划问题的数学模型,解：设,x,1,、,x,2,分别为甲、乙两种产品的产量，则数学模型为：,max Z=2x,1,+3x,2,x,1,0,x,2,0,s.t.,2x,1,+2x,2,12,x,1,+2x,2,8,4x,1,16,4x,2,12,线性规划问题的数学模型,2.,线性规划的数学模型由三个要素构成,决策变量,Decision variables,，记为,x1,x2.x3.Xn,目标函数,Objective function(,都有一个关于决策变量的线性函数为目标函数，要求这个目标函数在满足约束条件下实现最大或最小化,),约束条件,Constraints,（其中前,M,个称为前约束条件，后,N,个称为后约束条件）,其特征是：,（,1,）问题的目标函数是多个决策变量的,线性,函数，通常是求最大值或最小值；,（,2,）问题的约束条件是一组多个决策变量的,线性,不等式或等式。,怎样辨别一个模型是线性规划模型？,线性规划问题的数学模型,目标函数：,约束条件：,3.,线性规划数学模型的一般形式,简写为：,线性规划问题的数学模型,向量形式：,其中：,线性规划问题的数学模型,矩阵形式：,其中：,线性规划问题的数学模型,3.,线性规划问题的标准形式,特点：,(1),目标函数求最大值（有时求最小值）,(2),约束条件都为等式方程，且右端常数项,b,i,都大于或等于零,(3),决策变量,x,j,为非负。,线性规划问题的数学模型,（,2,）如何化标准形式,目标函数的转换,如果是求极小值即 ，则可将目标函数乘以,(-1),，可化为求极大值问题。,也就是：令 ，可得到上式。,即,若存在取值无约束的变量 ，可令,其中：,变量的变换,线性规划问题的数学模型,约束方程的转换：由不等式转换为等式。,称为松弛变量,称为剩余变量,变量 的变换,可令 ，显然,线性规划问题的数学模型,例,1.3,将下列线性规划问题化为标准形式,用 替换 ，且,解,:,（）因为,x,3,无符号要求，即,x,3,取正值也可取负值，标准型中要求变量非负，所以,线性规划问题的数学模型,(2),第一个约束条件是“”号，在“”左端加入松驰变量,x,4,，,x,4,0,化为等式；,(3),第二个约束条件是“”号，在“”左端减去剩余变量,x,5,，,x,5,0,；,(4),第,3,个约束方程右端常数项为,-5,，方程两边同乘以,(-1),将右端常数项化为正数；,(5),目标函数是最小值，为了化为求最大值，令,z=-z,得到,max z=-z,，即当,z,达到最小值时,z,达到最大值，反之亦然,;,线性规划问题的数学模型,标准形式如下：,线性规划问题的数学模型,4.,线性规划问题的解,线性规划问题,求解线性规划问题，就是从满足约束条件,(2),、,(3),的方程组中找出一个解，使目标函数,(1),达到最大值。,线性规划问题的数学模型,可行解,：满足约束条件、的解为可行解。所有可行解的集合为可行域。,最优解,：使目标函数达到最大值的可行解。,基：,设,A,为约束条件的,mn,阶系数矩阵,(mn),，其秩为,m,，,B,是矩阵,A,中,m,阶满秩子矩阵（,B0,），称,B,是规划问题的一个基。设：,称,B,中每个列向量,P,j,(j=1 2,m),为基向量。与基向量,P,j,对应的变量,x,j,为,基变量,。除基变量以外的变量为,非基变量,。,线性规划问题的数学模型,基解：,某一确定的基,B,，令非基变量等于零，由约束条件方程解出基变量，称这组解为基解。在基解中变量取非,0,值的个数不大于方程数,m,，基解的总数不超过,基可行解：,满足变量非负约束条件的基本解，简称基可行解。,可行基：,对应于基可行解的基称为可行基。,非可行解,可,行,解,基解,基可行解,线性规划问题的数学模型,例,1.4,求线性规划问题的所有基矩阵。,解,:,约束方程的系数矩阵为,25,矩阵,r(A)=2,，,2,阶子矩阵有,10,个，其中基矩阵只有,9,个，即,20,2,线性规划的图解法,在管理中一些典型的线性规划应用,合理利用线材问题：如何在保证生产的条件下，下料最少,配料问题：在原料供应量的限制下如何获取最大利润,投资问题：从投资项目中选取方案，使投资回报最大,产品生产计划：合理利用人力、物力、财力等，使获利最大,劳动力安排：用最少的劳动力来满足工作的需要,运输问题：如何制定调运方案，使总运费最小,线性规划的组成：,目标函数,Max F,或,Min F,约束条件,s.t.(subject to),满足于,决策变量 用符号来表示可控制的因素所要决策的问题待,定的量值。,21,2.1,问题的提出,例,1.,某工厂在计划期内要安排,、,两种产品的生产，已知生产单位产品所需的设备台时及,A,、,B,两种原材料的消耗、资源的限制，如下表：,问题：工厂应分别生产多少单位,、,产品才能使工厂获利最多？,线性规划模型：,目标函数：,Max z=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,22,2.1,问题的提出,建模过程以及线性规划的三要素,1.,理解要解决的问题，了解解题的目标和条件；,2.,定义,决策变量,（,x,1,，,x,2,，,，,x,n,），每一组值表示一个方案；,3.,用决策变量的线性函数形式写出,目标函数,，确定最大化或最小化目标；,4.,用一组决策变量的等式或不等式表示解决问题过程中必须遵循的,约束条件,一般形式,目标函数：,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,23,例,1.,目标函数：,Max z=50 x,1,+100 x,2,约束条件：,s.t.,x,1,+x,2,300 (A),2 x,1,+x,2,400 (B),x,2,250 (C),x,1,0 (D),x,2,0 (E),得到最优解：,x,1,=50,，,x,2,=250,最优目标值,z =27500,2.2,图 解 法,对于只有,两个决策变量,的线性规划问题，可以在平面直角坐标系上作图表示线性规划问题的有关概念，并求解。,下面通过例,1,详细讲解其方法：,24,2.2,图 解 法,(1),分别取决策变量,X,1,X,2,为坐标向量建立直角坐标系。在直角坐标系里，图上任意一点的坐标代表了决策变量的一组值，例,1,的每个约束条件都代表一个半平面。,x,2,x,1,X,2,0,X,2,=0,x,2,x,1,X,1,0,X,1,=0,25,2.2,图 解 法,（,2,）对每个不等式,(,约束条件,),，先取其等式在坐标系中作直线，然后确定不等式所决定的半平面。,100,200,300,100,200,300,x,1,+x,2,300,x,1,+x,2,=300,100,100,200,2x,1,+x,2,400,2x,1,+x,2,=400,300,200,300,400,26,2.2,图 解 法,（,3,）把五个图合并成一个图，取各约束条件的公共部分，如图,2-1,所示。,100,100,x,2,250,x,2,=250,200,300,200,300,x,1,x,2,x,2,=0,x,1,=0,x,2,=250,x,1,+x,2,=300,2x,1,+x,2,=400,图,2-1,27,2.2,图 解 法,（,4,）目标函数,z=50 x,1,+100 x,2,，当,z,取某一固定值时得到一条直线，直线上的每一点都具有相同的目标函数值，称之为“,等值线,”。平行移动等值线，当移动到,B,点时，,z,在可行域内实现了最大化。,A,，,B,，,C,，,D,，,E,是可行域的顶点，对有限个约束条件则其可行域的顶点也是有限的。,x,1,x,2,z=20000=50 x,1,+100 x,2,图,2-2,z=27500=50 x,1,+100 x,2,z=0=50 x,1,+100 x,2,z=10000=50 x,1,+100 x,2,C,B,A,D,E,28,2.2,图 解 法,线性规划的标准化内容之一：,引入,松驰变量,（含义是资源的剩余量）,例,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,千克。,29,2.2,图 解 法,重要结论：,如果线性规划有最优解，则一定有一个可行域的顶点对应一个最优解；,无穷多个最优解。若将例,1,中的目标函数变为,max z=50 x,1,+50 x,2,，则线段,BC,上的所有点都代表了最优解；,无界解。即可行域的范围延伸到无穷远，目标函数值可以无穷大或无穷小。一般来说，这说明模型有错，忽略了一些必要的约束条件；,无可行解。若在例,1,的数学模型中再增加一个约束条件,4x,1,+3x,2,1200,，则可行域为空域，不存在满足约束条件的解，当然也就不存在最优解了。,30,进 一 步 讨 论,例,2,某公司由于生产需要，共需要,A,，,B,两种原料至少,350,吨（,A,，,B,两种材料有一定替代性），其中,A,原料至少购进,125,吨。但由于,A,，,B,两种原料的规格不同，各自所需的加工时间,也是不同的，加工每吨,A,原料需要,2,个小时，加工每吨,B,原料需,要,1,小时，而公司总共有,600,个加工小时。又知道每吨,A,原料的,价格为,2,万元，每吨,B,原料的价格为,3,万元，试问在满足生产需,要的前提下，在公司加工能力的范围内，如何购买,A,，,B,两种,原料，使得购进成本最低？,31,进 一 步 讨 论,解：目标函数：,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,）为最优解。,100,200,300,400,500,600,100,200,300,400,600,500,x,1,=125,x,1,+x,2,=350,2x,1,+3x,2,=800,2x,1,+3x,2,=900,2x,1,+x,2,=600,2x,1,+3x,2,=1200,x,1,x,2,Q,32,3,图解法的灵敏度分析,线性规划的标准化,一般形式,目标函数：,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,33,3,图解法的灵敏度分析,可以看出，线性规划的标准形式有如下四个特,点：,目标最大化；,约束为等式；,决策变量均非负；,右端项非负。,对于各种非标准形式的线性规划问题，我们总可,以通过以下变换，将其转化为标准形式,:,34,3,图解法的灵敏度分析,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,35,3,图解法的灵敏度分析,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,36,3,图解法的灵敏度分析,当约束条件为,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,37,3,图解法的灵敏度分析,为了使,约束由不等式成为等式而引进的变量,s,当,不等式为,“,小于等于,”,时称为,“,松弛变量,”,；当不等式为,“,大于等于,”,时称为,“,剩余变量,”,。如果原问题中有若干个非等式,约束，则将其转化为标准形式时，必须对各个约束引进不同的松弛变量。,3.,右端项有负值的问题：,在标准形式中，要求右端项必须每一个分量非负。当某一个右端项系数为负时，如,b,i,0,，则把该等式约束两端同时乘以,-1,，得到：,-,a,i1,x,1,-,a,i2,x,2,-,-,a,in,x,n,=-,b,i,。,38,3,图解法的灵敏度分析,例：将以下线性规划问题转化为标准形式,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,解：首先,将目标函数转换成极大化：,令,z,=-,f,=-2,x,1,+3,x,2,-4,x,3,其次考虑约束，有,2,个不等式约束，引进松弛变量,x,4,，,x,5,0,。,第三个约束条件的右端值为负，在等式两边同时乘,-1,。,39,3,图解法的灵敏度分析,通过以上变换，可以得到以下标准形式的线性规划问题：,Max,z,=-2,x,1,+3,x,2,-4,x,3,s.t.3,x,1,+4,x,2,-5,x,3,+,x,4,=6,2,x,1,+,x,3,-,x,5,=8,-,x,1,-,x,2,-,x,3,=9,x,1,x,2,x,3,x,4,x,5,0,*,变量无符号限制的问题*,：,在标准形式中，必须每一个变量均有非负约束。当某一个变量,x,j,没,有非负约束时，可以令,x,j,=,x,j,-,x,j,”,其中,x,j,0,，,x,j,”,0,即用两个非负变量之差来表示一个无符号限制的变量，当然,x,j,的符号,取决于,x,j,和,x,j,”,的大小。,40,3,图解法的灵敏度分析,灵敏度分析,：,建立数学模型和求得最优解后，研究线性规,划的一个或多个参数（系数）,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,（*）时，原最优解仍是最优解。,41,3,图解法的灵敏度分析,假设产品,的利润,100,元不变，即,c,2,=100,，代到式（*）并整理得,0,c,1,100,假设产品,的利润,50,元不变，即,c,1,=50,，代到式（*）并整理得,50,c,2,+,假若产品,、,的利润均改变，则可直接用式（*）来判断。,假设产品,、,的利润分别为,60,元、,55,元，则,-2,-(60/55),-1,那么，最优解为,z=x,1,+x,2,和,z=2 x,1,+x,2,的交点,x,1,=100,，,x,2,=200,。,42,3,图解法的灵敏度分析,3.2,约束条件中右边系数,b,j,的灵敏度分析,当约束条件中右边系数,b,j,变化时，线性规划的可行域发生,变化，可能引起最优解的变化。,考虑例,1,的情况：,假设设备台时增加,10,个台时，即,b,1,变化为,310,，这时可行,域扩大，,最优解为,x,2,=250,和,x,1,+x,2,=310,的交点,x,1,=,60,，,x,2,=250,。,变化后的总利润,-,变化前的总利润,=,增加的利润,(5060+100250)-(50 50+100 250)=500,，,500/,10=50,元,说明在一定范围内每增加（减少）,1,个台时的设备能力就,可增加（减少）,50,元利润，称为该约束条件的,对偶价格。,43,3,图解法的灵敏度分析,假设原料,A,增加,10,千克时，即,b,2,变化为,410,，这时可行域,扩大，但,最优解仍为,x,2,=250,和,x,1,+x,2,=300,的交点,x,1,=50,，,x,2,=250,。此变化对总利润无影响，该约束条件的对偶,价格为,0,。,解释：,原最优解没有把原料,A,用尽，有,50,千克的剩余，,因此增加,10,千克值增加了库存，而不会增加利润。,在一定范围内，当约束条件右边常数增加,1,个单位时,（,1,）若约束条件的对偶价格大于,0,，则其最优目标函数值得,到改善（变好）；,（,2,）若约束条件的对偶价格小于,0,，则其最优目标函数值受,到影响（变坏）；,（,3,）若约束条件的对偶价格等于,0,，则最优目标函数值不变。,