线性规划的图解法.ppt

1、1,第二章 线性规划的图解法,1 问题的提出 2 图解法 3 图解法的灵敏度分析,2,第二章 线性规划的图解法,在管理中一些典型的线性规划应用 合理利用线材问题：如何在保证生产的条件下，下料最少 配料问题：在原料供应量的限制下如何获取最大利润 投资问题：从投资项目中选取方案，使投资回报最大 产品生产计划：合理利用人力、物力、财力等，使获利最大 劳动力安排：用最少的劳动力来满足工作的需要 运输问题：如何制定调运方案，使总运费最小,线性规划的组成： 目标函数 Max F 或 Min F 约束条件 s.t. (subject to) 满足于 决策变量 用符号来表示可控制的因素,3,1 问题的提出,例

2、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,4,1 问题的提出,建模过程 1.理解要解决的问题，了解解题的目标和条件； 2.定义决策变量（ x1 ，x2 ， ，xn ），每一组值表示一个方案； 3.用决策变量的线性函数形

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,5,例1.目标函数： Max z = 50 x1 + 100 x2 约束条件： s.t. x1 + x2 300 (A)

4、2 x1 + x2 400 (B) x2 250 (C) x1 0 (D) x2 0 (E) 得到最优解： x1 = 50， x2 = 250 最优目标值 z = 27500,2 图 解 法,对于只有两个决策变量的线性规划问题，可以在平面直角坐标系上作图表示线性规划问题的有关概念，并求解。 下面通过例1详细讲解其方法：,6,2 图 解 法,(1)分别取决策变量X1 , X2 为坐标向量建立直角坐标系。在直角坐标系里，图上任意一点的坐标代表了决策变量的一组值，例1的每个约束条件都代表一个半平面。,7,2 图 解 法,（2）对每个不等式(约束条件)，先取其等式在坐标系中作直线，然后确定不等式所决定

5、的半平面。,x1,x1,x2,x2,8,2 图 解 法,（3）把五个图合并成一个图，取各约束条件的公共部分，如图2-1所示。,x2,x1,C,B,A,D,E,9,2 图 解 法,（4）目标函数z=50 x1+100 x2，当z取某一固定值时得到一条直线，直线上的每一点都具有相同的目标函数值，称之为“等值线”。平行移动等值线，当移动到B点时，z在可行域内实现了最大化。A，B，C，D，E是可行域的顶点，对有限个约束条件则其可行域的顶点也是有限的。,x1,x2,z=20000=50 x1+100 x2,图2-2,z=27500=50 x1+100 x2,z=0=50 x1+100 x2,z=1000

6、0=50 x1+100 x2,C,B,A,D,E,10,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单位产品将消耗完所有 可

7、能的设备台时数及原料B，但原料A则还剩余50千克。,11,2 图 解 法,重要结论： 如果线性规划有唯一最优解，则一定有一个可行域的顶点对应最优解； 无穷多个最优解。若将例1中的目标函数变为max z=50 x1+50 x2，则线段BC上的所有点都代表了最优解；,12,x1,x2,图2-2,z=0=50 x1+50 x2,C,B,A,D,E,13,2 图 解 法,重要结论： 无界解。即可行域的范围延伸到无穷远，目标函数值可以无穷大或无穷小。一般来说，这说明模型有错，忽略了一些必要的约束条件； 无可行解。若在例1的数学模型中再增加一个约束条件4x1+3x21200，则可行域为空域，不存在满足约束

8、条件的解，当然也就不存在最优解了。,14,15,进 一 步 讨 论,例2 某公司由于生产需要，共需要A，B两种原料至少350 吨（A，B两种材料有一定替代性），其中A原料至少购进125 吨。但由于A，B两种原料的规格不同，各自所需的加工时间 也是不同的，加工每吨A原料需要2个小时，加工每吨B原料需 要1小时，而公司总共有600个加工小时。又知道每吨A原料的 价格为2万元，每吨B原料的价格为3万元，试问在满足生产需 要的前提下，在公司加工能力的范围内，如何购买A，B两种 原料，使得购进成本最低？,16,进 一 步 讨 论,解： 目标函数： Min f = 2x1 + 3 x2 （购买成本） 约束

9、条件： s.t. x1 + x2 350 （总量约束） x1 125 （A量的约束） 2 x1 + x2 600 （加工工时的约束） x1 , x2 0,17,进 一 步 讨 论,采用图解法。如下图：得Q点坐标（250，100）为最优解。,18,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

10、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,19,3 图解法的灵敏度分析,可以看出，线性规划的标准形式有如下四个特 点： 目标最大化； 约束为等式； 决策变量均非负； 右端项非负。 对于各种非标准形式的线性规划问题，我们总可 以通过以下变换，将其转化

11、为标准形式:,20,3 图解法的灵敏度分析,1.极小化目标函数的问题： 设目标函数为 Min f = c1x1 + c2x2 + + cnxn (可以)令 z -f ， 则该极小化问题与下面的极大化问题有相同的最优解， 即 Max z = - c1x1 - c2x2 - - cnxn 但必须注意，尽管以上两个问题的最优解相同，但它们 最优解的目标函数值却相差一个符号，即 Min f - Max z,21,3 图解法的灵敏度分析,2、约束条件不是等式的问题： 设约束条件为 ai1 x1+ai2 x2+ +ain xn bi 可以引进一个新的变量s ，使它等于约束右边与左 边之差 s=bi(ai1

12、 x1 + ai2 x2 + + ain xn ) 显然，s 也具有非负约束，即s0， 这时新的约束条件成为 ai1 x1+ai2 x2+ +ain xn+s = bi,22,3 图解法的灵敏度分析,当约束条件为 ai1 x1+ai2 x2+ +ain xn bi 时， 类似地令 s=(ai1 x1+ai2 x2+ +ain xn)- bi 显然，s 也具有非负约束，即s0，这时新的约 束条件成为 ai1 x1+ai2 x2+ +ain xn-s = bi,23,3 图解法的灵敏度分析,为了使约束由不等式成为等式而引进的变量s,当 不等式为“小于等于”时称为“松弛变量”；当不等式 为“大于等于

13、”时称为“剩余变量”。如果原问题中有 若干个非等式约束，则将其转化为标准形式时，必须 对各个约束引进不同的松弛变量。,3.右端项有负值的问题： 在标准形式中，要求右端项必须每一个分量非负。当某一个右端项系数为负时，如 bi0，则把该等式约束两端同时乘以-1，得到：-ai1 x1-ai2 x2- -ain xn = -bi。,24,3 图解法的灵敏度分析,例：将以下线性规划问题转化为标准形式 Min f = 2 x1 -3x2 + 4 x3 s.t. 3 x1 + 4x2 - 5 x3 6 2 x1 + x3 8 x1 + x2 + x3 = -9 x1 , x2 , x3 0 解：首先,将目标

14、函数转换成极大化： 令 z= -f = -2x1+3x2-4x3 其次考虑约束，有2个不等式约束，引进松弛变量 x4，x5 0。 第三个约束条件的右端值为负，在等式两边同时乘-1。,25,3 图解法的灵敏度分析,通过以上变换，可以得到以下标准形式的线性规划问题： Max z = - 2x1 + 3 x2 - 4x3 s.t. 3x1+4x2-5x3 +x4 = 6 2x1 +x3 -x5= 8 -x1 -x2 -x3 = 9 x1 ,x2 ,x3 ,x4 ,x5 0,26,3 图解法的灵敏度分析,4. * 变量无符号限制的问题*：就是取值无约束 在标准形式中，必须每一个变量均有非负约束。当某一

15、个变量xj没有非负约束时，可以令 xj = xj- xj” 其中 xj0，xj”0 即用两个非负变量之差来表示一个无符号限制的变量，当然xj的符号取决于xj和xj”的大小。,27,3 图解法的灵敏度分析,例：将以下线性规划问题转化为标准形式 Min f = 2 x1 -3x2 + 4 x3 s.t. 3 x1 + 4x2 - 5 x3 6 2 x1 + x3 8 x1 + x2 + x3 = -9 x1 , x2 0,x3 0 解：首先,将目标函数转换成极大化： 令 z= -f = -2x1+3x2-4x3 其次考虑约束，有2个不等式约束，引进松弛变量 x4，x5 0。 第三个约束条件的右端值

16、为负，在等式两边同时乘-1。 第三个变量x3为负约束时，可以令x3 = -x3,28,3 图解法的灵敏度分析,通过以上变换，可以得到以下标准形式的线性规划问题： Max z = - 2x1 + 3 x2 +4 x3 s.t. 3x1+4x2 +5 x3 +x4 = 6 2x1 -x3 -x5= 8 -x1 -x2 +x3 = 9 x1 ,x2 , x3 ,x4 ,x5 0,29,3 图解法的灵敏度分析,例：将以下线性规划问题转化为标准形式 Min f = 2 x1 -3x2 + 4 x3 s.t. 3 x1 + 4x2 - 5 x3 6 2 x1 + x3 8 x1 + x2 + x3 = -

17、9 x1 , x2 0 解：首先,将目标函数转换成极大化： 令 z= -f = -2x1+3x2-4x3 其次考虑约束，有2个不等式约束，引进松弛变量 x4，x5 0。 第三个约束条件的右端值为负，在等式两边同时乘-1。 变量x3没有非负约束，可以令 x3= x3- x3” 其中 x30，x3”0,30,3 图解法的灵敏度分析,通过以上变换，可以得到以下标准形式的线性规划问题： Max z = - 2x1 + 3 x2 - 4（x3- x3”） s.t. 3x1+4x2-5（x3- x3”） +x4 = 6 2x1 +（x3- x3”） -x5= 8 -x1 -x2 -（x3- x3”） =

18、9 x1 ,x2 , x3, x3” ,x4 ,x5 0,31,3 图解法的灵敏度分析,灵敏度分析：建立数学模型和求得最优解后，研究线性规 划的一个或多个参数（系数）ci , aij , bj 变化时，对最优解产 生的影响。 3.1 目标函数中的系数 ci 的灵敏度分析就是目标利润斜率变化 考虑例1的情况， ci 的变化只影响目标函数等值线的斜率， 目标函数 z = 50 x1 + 100 x2 在 z = x2 (x2 = z 斜率为0 ) 到 z = x1 + x2 (x2 = -x1 + z 斜 率为 -1 )之间时，原最优解 x1 = 50，x2 = 100 仍是最优解。 一般情况：先

19、做成斜截式再去判断。只是在利润上变化。 z = c1 x1 + c2 x2 写成斜截式 x2 = - (c1 / c2 ) x1 + z / c2 目标函数等值线的斜率为 - (c1 / c2 ) ， 当 -1 - (c1 / c2 ) 0 （*） 时，原最优解仍是最优解。,32,33,3 图解法的灵敏度分析,假设产品的利润100元不变，即 c2 = 100，代到式（*）并整理得 0 c1 100 假设产品的利润 50 元不变，即 c1 = 50 ，代到式（*）并整理得 50 c2 + 假若产品、的利润均改变，则可直接用式（*）来判断。 假设产品、的利润分别为60元、55元，则 - 2 - (60 / 55) - 1 那么，最优解为 z = x1 + x2 和 z = 2 x1 + x2 的交点 x1 = 100，x2 = 200 。,34,3 图解法的灵敏度分析,3.2 约束条件中右边系数 bj 的灵敏度分析。应用增减设备员工是 不是赚。看变化前后的利润情况。 当约束