第2章线性规划的图解法

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,管 理 运 筹 学,第二章,线性规划的图解法,1 问题的提出,2 图解法,3 图解法的灵敏度分析,1,第二章,线性规划的图解法,在管理中一些典型的线性规划应用,合理利用线材问题：如何在保证生产的条件下，下料最少,配料问题：在原料供给量的限制下如何获取最大利润,投资问题：从投资工程中选取方案，使投资回报最大,产品生产方案：合理利用人力、物力、财力等，使获利最大,劳动力安排：用最少的劳动力来满足工作的需要,运输问题：如何制定调运方案，使总运费最小,线性规划的组成：,目标函数,Max F,或,Min F,约束条件,s.t.(subject to),满足于,决策变量 用符号来表示可控制的因素,2,1 问题的提出,例1.某工厂在方案期内要安排、两种产品的生产，生产单位产品所需的设备台时及A、B两种原材料的消耗、资源的限制，如下表：,问题：工厂应分别生产多少单位、产品才能使工厂获利最多？,线性规划模型：,目标函数：Max z=50 x1+100 x2 利润,约束条件：s.t.x1+x2 300设备数量约束,2 x1+x2 400 原料A数量约束,x2 250 原料B数量约束,x1,x2 0,3,1 问题的提出,建模过程,1.理解要解决的问题，了解解题的目标和条件；,2.定义决策变量 x1，x2，xn，每一组值表示一个方案；,3.用决策变量的线性函数形式写出目标函数，确定最大化或最小化目标；,4.用一组决策变量的等式或不等式表示解决问题过程中必须遵循的约束条件,一般形式,目标函数：Max Min z=c1 x1+c2 x2+cn xn,约束条件：s.t.a11 x1+a12 x2+a1n xn =,b1,a21 x1+a22 x2+a2n xn =,b2,am1 x1+am2 x2+amn xn =,bm,x1，x2，xn 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,x1,x1,x2,x2,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,x2,x1,C,B,A,D,E,8,2 图 解 法,4目标函数z=50 x1+100 x2，当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 中引入 s1，s2，s3 模型化为,目标函数：Max z=50 x1+100 x2+0 s1 +0 s2 +0 s3,约束条件：s.t.x1+x2 +s1 =300,2 x1+x2+s2 =400,x2 +s3 =250,x1 ,x2 ,s1,s2 ,s3 0,对于最优解 x1 =50 x2 =250，s1=0 s2 =50 s3=0,说明：生产50单位产品和250单位产品将消耗完所有,可能的设备台时数及原料B，但原料A那么还剩余50千克。,10,2 图 解 法,重要结论：,如果线性规划有唯一最优解，那么一定有一个可行域的顶点对应最优解；,无穷多个最优解。假设将例1中的目标函数变为max z=50 x1+50 x2，那么线段BC上的所有点都代表了最优解；,11,x,1,x,2,图2-2,z=0=50 x,1,+50 x,2,C,B,A,D,E,12,2 图 解 法,重要结论：,无界解。即可行域的范围延伸到无穷远，目标函数值可以无穷大或无穷小。一般来说，这说明模型有错，忽略了一些必要的约束条件；,无可行解。假设在例1的数学模型中再增加一个约束条件4x1+3x21200，那么可行域为空域，不存在满足约束条件的解，当然也就不存在最优解了。,13,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,14,进 一 步 讨 论,例2 某公司由于生产需要，共需要A，B两种原料至少350,吨A，B两种材料有一定替代性，其中A原料至少购进125,吨。但由于A，B两种原料的规格不同，各自所需的加工时间,也是不同的，加工每吨A原料需要2个小时，加工每吨B原料需,要1小时，而公司总共有600个加工小时。又知道每吨A原料的,价格为2万元，每吨B原料的价格为3万元，试问在满足生产需,要的前提下，在公司加工能力的范围内，如何购置A，B两种,原料，使得购进本钱最低？,15,进 一 步 讨 论,解：,目标函数：Min f=2x1+3 x2 购置本钱,约束条件：,s.t.x1+x2 350 总量约束,x1 125 A量的约束,2 x1+x2 600 加工工时的约束,x1 ,x2 0,16,进 一 步 讨 论,采用图解法。如以下图：得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,17,3 图解法的灵敏度分析,线性规划的标准化,一般形式,目标函数：Max Min z=c1 x1+c2 x2+cn xn,约束条件：s.t.a11 x1+a12 x2+a1n xn =,b1,a21 x1+a22 x2+a2n xn =,b2,am1 x1+am2 x2+amn xn =,bm,x1，x2，xn 0,标准形式,目标函数：Max z =c1 x1+c2 x2+cn xn,约束条件：s.t.a11 x1+a12 x2+a1n xn =b1,a21 x1+a22 x2+a2n xn =b2,am1 x1+am2 x2+amn xn =bm,x1，x2，xn 0，bi 0,18,3 图解法的灵敏度分析,可以看出，线性规划的标准形式有如下四个特,点：,目标最大化；,约束为等式；,决策变量均非负；,右端项非负。,对于各种非标准形式的线性规划问题，我们总可,以通过以下变换，将其转化为标准形式:,19,3 图解法的灵敏度分析,1.极小化目标函数的问题：,设目标函数为,Min f=c1x1+c2x2+cnxn,(可以)令 z -f，,那么该极小化问题与下面的极大化问题有相同的最优解，,即 Max z=-c1x1-c2x2-cnxn,但必须注意，尽管以上两个问题的最优解相同，但它们,最优解的目标函数值却相差一个符号，即,Min f -Max z,20,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,21,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,22,3 图解法的灵敏度分析,为了使约束由不等式成为等式而引进的变量s,当,不等式为“小于等于时称为“松弛变量；当不等式,为“大于等于时称为“剩余变量。如果原问题中有,假设干个非等式约束，那么将其转化为标准形式时，必须,对各个约束引进不同的松弛变量。,3.右端项有负值的问题：,在标准形式中，要求右端项必须每一个分量非负。当某一个右端项系数为负时，如 bi0，那么把该等式约束两端同时乘以-1，得到：-ai1 x1-ai2 x2-ain xn=-bi。,23,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。,24,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,25,3 图解法的灵敏度分析,4.*变量无符号限制的问题*：就是取值无约束,在标准形式中，必须每一个变量均有非负约束。当某一个变量xj没有非负约束时，可以令,xj=xj-xj,其中,xj0，xj0,即用两个非负变量之差来表示一个无符号限制的变量，当然xj的符号取决于xj和xj的大小。,26,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,0,x,3,0,解：首先,将目标函数转换成极大化：,令,z,=-,f,=-2,x,1,+3,x,2,-4,x,3,其次考虑约束，有2个不等式约束，引进松弛变量,x,4,，,x,5,0。,第三个约束条件的右端值为负，在等式两边同时乘-1。,第三个,变量,x,3,为负