管理运筹学-第2章-线性规划的图解法只是课件.ppt

,单击此处编辑母版标题样式,*,1,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,管理运筹学-第2章-线性规划的图解法,解：,设安排甲、乙产量分别为,总收入为 ，则模型为：,目标函数：总收入，记为,z,则 ，为体现,对其追求极大化，在,z,的前面冠以极大号,Max,；,决策变量：甲、乙产品的计划产量，记为,；,约束条件：分别来自资源煤、电、油限量的约束，和产,量非负的约束，表示为,线性,规划模型的三要素,3.,约束条件：,为实现优化目标需受到的限制，用,决策变量的等式或不等式表示。,1.,决策变量：,需决策的量，即待求的未知数；,2.,目标函数：,需优化的量，即欲达的目标，用决,策变量的表达式表示；,线性规划模型的一般形式：,（以,MAX,型、约束为例）,决策变量：,目标函数：,约束条件：,则模型可表示为,模型一般式的矩阵形式,记,回顾例,1.1,的模型,其中,表示决策变量的向量；,表示产品的价格向量；,表示资源限制向量；,表示产品对资源的单耗系数矩阵。,一般地,其中,称为决策变量向量，称为价格系数向量,称为技术系数矩阵,称为资源限制向量。,问题：,为什么,A,称为技术系数矩阵？,二、线性规划模型的图解法,图解法是用画图的方式求解线性规划的一种方法。它虽然只能用于解二维（两个变量）的问题，但其主要作用并不在于求解，而是在于能够直观地说明线性规划解的一些重要性质。,例,1,用图解法求解线性规划问题,max Z=50X,1,+100X,2,X,1,+X,2,300,2 X,1,+X,2,400,s.t.X,2,250,X,1,，,X,2,0,7/9/2025,（,1,）分别取决策变量,X,1,，,X,2,为坐标向量建立直角坐标系。在直角坐标系里，图上任意一点的坐标代表了决策变量的一组值，例,1,的每个约束条件都代表一个半平面。,x,2,x,1,X,2,0,X,2,=0,x,2,x,1,X10,X,1,=0,7/9/2025,12,（,2,）对每个不等式（约束条件），先取其等式在坐标系中作直线，然后确定不等式所决定的半平面。,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,100,200,300,x,1,x,1,100,200,300,x,2,x,2,7/9/2025,12,13,（,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,x,1,x,2,7/9/2025,（,4,）目标函数,Z=50X,1,+100X,2,，当,Z,取某一固定值时得到一条直线，直线上的每一点都具有相同的目标函数值，称之为“,等值线,”。平行移动等值线，,当移动到,B,点时,，,z,在可行域内实现了最大化。,A,，,B,，,C,，,D,，,E,是可行域的顶点，对有限个约束条件则其可行域的顶点也是有限的。,x,1,x,2,z=20000=50 x,1,+100 x,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,由图可知：,顶点,B,为最优解。,X,1,=50,X,2,=250,Z=50 x50+250 x100=27500,7/9/2025,14,（,1,）做约束的图形,先做非负约束的图形；,再做资源约束的图形。,以例,1.1,为例，其约束为,各约束的公共部分即,模型的约束，称可行域。,1.,图解法的步骤,(2),做目标的图形,做出相应的二直线，便可看出增大的方向。,对于目标函数,便可做出相应的二组任给,Z,不同的值，形成二直线，用虚线表示。以例,1.1,为例，其目标为,分别令,（,3,）求出最优解,将目标直线向使目,标 优化的方向移，直,至可行域的边界为止，,这时其与可行域的,“,切,”,点 即最优解。,如在例,1.1,中，,是可行域的一个角点，,经求解交出 的,二约束直线联立的方程,可解得,由图解法的结果得到例,1.1,的最优解,还可将其代入目标函数求得相应的最优目标值,。说明当甲产量安排,20,个单位，乙产量安排,24,个单位时，可获得最大的收入,428,。,2.,由图解法得到线性规划解的一些特性,（,1,）,线性规划的约束集（即可行域）是一个凸多面体。,凸多面体,:,把多面体的任何一个面伸展成平面，如果所有其他各面都在这个平面的同侧，这样的多面体就叫做凸多面体。,凸多面体的任何截面都是,凸多边形。,（,2,）,线性规划的最优解（若存在的话）必能在可行域的角点（顶点）获得。,因为，由图解法可知，只有当目标直线平移到边界时，才能使目标,z,达到最大限度的优化。,问题：,本性质有何重要意义？,本性质重要意义：,这样，问题就转化为,从有限多个角点中寻找最优点,，使原来从所有可行解中去,寻找最优解的工作大大简化,。线性规划的,单纯形解法,的依据,就是这两个性质。,（,3,）线性规划解的几种情形,唯一最优解,多重最优解,无解,无有限最优解,（无界解）,重要结论：,如果线性规划有最优解，则一定有一个可行域的顶点对应一个最优解；,无穷多个最优解。,无界解。即可行域的范围延伸到无穷远，目标函数值可以无穷大或无穷小。一般来说，这说明模型有错，忽略了一些必要的约束条件；,无可行解。则可行域为空域，不存在满足约束条件的解，当然也就不存在最优解了。,小结,线性规划,L,P(linear programming),的定义：,LP,是在,有限资源,的条件下，,合理分配,和利用资源，以期取得,最佳,的经济效益的优化方法。,LP,有一组,决策变量，,一个,目标函数，,一组,约束条件，,目标函数和约束方程都是线性的。,重要性：,要想在工农业生产、交通运输、商业贸易等各方面提高效益，有两种途径：一是革新技术，二是改进生产组织与计划，即合理安排有限的人力和物力资源，最合理地组织生产过程。,数学规划能够为更好地配置资源、组织生产提供理论与方法,，,包括线性规划、非线性规划、整数规划、多目标规划等很多分支。,其中线性规划是在现代管理中运用最广、理论比较完善的一个部分。随着电子计算机的发展，数学规划在现代管理中的重要性日益明显。,线性规划的标准化内容之一：,引入,松驰变量（含义是资源的剩余量）,例,1.1,中引入,s,1,，,s,2,，,s,3,模型化为,目标函数：,Max z=7x,1,+12x,2,+0 s,1,+0 s,2,+0 s,3,约束条件：,9 x,1,+4 x,2,+s,1,=360,4x,1,+5x,2,+s,2,=200,s.t.3x,1,+10 x,2,+s,3,=,300,x,1,x,2,s,1,s,2,s,3,0,对于最优解,x,1,=20 x,2,=24,，,s,1,=84 s,2,=0 s,3,=0,说明：生产,20,单位甲产品和,24,单位乙产品将消耗完所有可能的电和油，但对煤则还剩余,84,个单位。,线性规划的标准化,一般形式,目标函数：,Max,（,Min,）,z=c,1,x,1,+c,2,x,2,+c,n,x,n,约束条件：,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,s.t.,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,约束条件：,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,s.t.,a,m1,x,1,+,a,m2,x,2,+,a,mn,x,n,=b,m,x,1,，,x,2,，,，,x,n,0,，,b,i,0,可以看出，线性规划的标准形式有如下四个特点：,目标最大化；,约束为等式；,决策变量均非负；,右端项非负。,对于各种非标准形式的线性规划问题，我们总可以通过以下变换，将其转化为标准形式,:,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,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,当约束条件为,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,为了使,约束由不等式成为等式而引进的变量,s,，当,不等式为“小于等于,”时称为,“,松弛变量,”,；当,不等式为“大于等于”,时称为,“,剩余变量,”,。如果原问题中有若干个非等式,约束，则将其转化为标准形式时，必须对各个约束引进不同的松弛变量。,3.,右端项有负值的问题：,在标准形式中，要求右端项必须每一个分量非负。当某一个右端项系数为负时，如,b,i,0,，则把该等式约束两端同时乘以,-1,，得到：,例：将以下线性规划问题转化为标准形式,Min,f,=2,x,1,-3,x,2,+4,x,3,3,x,1,+4,x,2,-5,x,3,6,2,x,1,+,x,3,8,s.t.,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,。,通过以上变换，可以得到以下标准形式的线性规划问题：,Max,z,=-2,x,1,+3,x,2,-4,x,3,3,x,1,+4,x,2,-5,x,3,+,x,4,=6,s.t.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,*,4.,变量无符号限制的问题,*,：,在标准形式中，必须每一个变量均有非负约束。当某一个变量,x,j,没有非负约束时，可以令,x,j,=,x,j,-,x,j,”,其中,x,j,0,，,x,j,”,0,即用两个非负变量之差来表示一个无符号限制的变量，当然,x,j,的符号取决于,x,j,和,x,j,”,的大小。,三、图解法的灵敏度分析,灵敏度分析,：,建立数学模型和求得最优解后，研究线性规,划的一个或多个参数（系数）,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,（*）时，原最优解仍是最优解。,35,假设产品,的利润,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,。,36,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,元利润，称为该约束条件的对偶价格。,37,假设原料,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,，则最优目标函数值不变。,38,作业：,教材,P23,：,1,；,2;3,；,4,；,5,此课件下载可自行编辑修改，仅供参考！感谢您的支持，我们努力做得更好！谢谢,