运筹学-02-线性规划的图解法

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,管 理 运 筹 学,第二章,线性规划的图解法,1,问题的提出,2,图解法,3,图解法的灵敏度分析,1,第二章,线性规划的图解法,在管理中一些典型的线性规划应用,合理利用线材问题：如何在保证生产的条件下，下料最少,配料问题：在原料供应量的限制下如何获取最大利润,投资问题：从投资项目中选取方案，使投资回报最大,产品生产计划：合理利用人力、物力、财力等，使获利最大,劳动力安排：用最少的劳动力来满足工作的需要,运输问题：如何制定调运方案，使总运费最小,线性规划的组成：,目标函数,Max F,或,Min F,约束条件,s.t.(subject to),满足于,决策变量 用符号来表示可控制的因素,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,3,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,4,例,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,图 解 法,对于只有两个决策变量的线性规划问题，可以在平面直角坐标系上作图表示线性规划问题的有关概念，并求解。,下面通过例,1,详细讲解其方法：,5,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,6,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,7,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,8,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,9,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,千克。,10,2,图 解 法,重要结论：,如果线性规划有最优解，则一定有一个可行域的顶点对应一个最优解；,无穷多个最优解。若将例,1,中的目标函数变为,max z=50 x,1,+50 x,2,，则线段,BC,上的所有点都代表了最优解；,无界解。即可行域的范围延伸到无穷远，目标函数值可以无穷大或无穷小。一般来说，这说明模型有错，忽略了一些必要的约束条件；,无可行解。若在例,1,的数学模型中再增加一个约束条件,4x,1,+3x,2,1200,，则可行域为空域，不存在满足约束条件的解，当然也就不存在最优解了。,11,进 一 步 讨 论,例,2,某公司由于生产需要，共需要,A,，,B,两种原料至少,350,吨（,A,，,B,两种材料有一定替代性），其中,A,原料至少购进,125,吨。但由于,A,，,B,两种原料的规格不同，各自所需的加工时间,也是不同的，加工每吨,A,原料需要,2,个小时，加工每吨,B,原料需,要,1,小时，而公司总共有,600,个加工小时。又知道每吨,A,原料的,价格为,2,万元，每吨,B,原料的价格为,3,万元，试问在满足生产需,要的前提下，在公司加工能力的范围内，如何购买,A,，,B,两种,原料，使得购进成本最低？,12,进 一 步 讨 论,解：目标函数：,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,13,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,14,3,图解法的灵敏度分析,可以看出，线性规划的标准形式有如下四个特,点：,目标最大化；,约束为等式；,决策变量均非负；,右端项非负。,对于各种非标准形式的线性规划问题，我们总可,以通过以下变换，将其转化为标准形式,:,15,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,16,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,17,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,18,3,图解法的灵敏度分析,为了使,约束由不等式成为等式而引进的变量,s,当,不等式为“小于等于”时,称为“松弛变量”；,当不等式,为“,大,于等于”时,称为“剩余变量”。如果原问题中有,若干个非等式,约束，则将其转化为标准形式时，必须,对各个约束引进不同的松弛变量。,3.,右端项有负值的问题：,在标准形式中，要求右端项必须每一个分量非负。当某一个右端项系数为负时，如,b,i,0,，,则把该等式约束两端同时乘以,-1,，得到：,-,a,i1,x,1,-,a,i2,x,2,-,a,in,x,n,=-,b,i,。,19,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,。,20,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,”,的大小。,21,3,图解法的灵敏度分析,灵敏度分析,：,建