第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 3002 x1 + x2 400x2 250x1 , x2 03管 理 运 筹 学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 （ =, ） b1a21 x1 + a22 x2 + + a2n xn （ =, ） b2 am1 x1 + am2 x2 + + amn xn （ =, ） bmx1 ， x2 ， ， xn 0 4管 理 运 筹 学例 1.目标函数：Max z = 50 x1 + 100 x2 约束条件：s.t. x1 + x2 300 (A)2 x1 + x2 400 (B)x2 250 (C)x1 0 (D)x2 0 (E)得到最优解：x1 = 50， x2 = 250 最优目标值 z = 275002 图 解 法对于只有两个决策变量的线性规划问题，可以在平面直角坐标系上作图表示线性规划问题的有关概念，并求解。下面通过例 1详细讲解其方法：5管 理 运 筹 学2 图 解 法(1)分别取决策变量 X1 , X2 为坐标向量建立直角坐标系。在直角坐标系里，图上任意一点的坐标代表了决策变量的一组值，例 1的每个约束条件都代表一个半平面。x2x1X20X2=0x2x1X10X1=06管 理 运 筹 学2 图 解 法（ 2）对每个不等式 (约束条件 )，先取其等式在坐标系中作直线，然后确定不等式所决定的半平面。100200300100 200 300x1+x2300x1+x2=300100100 2002x1+x24002x1+x2=4003002003004007管 理 运 筹 学2 图 解 法（ 3）把五个图合并成一个图，取各约束条件的公共部分，如图 2-1所示。100100x2250x2=250200 300200300x1x2x2=0 x1=0x2=250x1+x2=3002x1+x2=400图 2-18管 理 运 筹 学2 图 解 法（ 4）目标函数 z=50x1+100x2，当 z取某一固定值时得到一条直线，直线上的每一点都具有相同的目标函数值，称之为 “等值线 ”。平行移动等值线，当移动到 B点时， z在可行域内实现了最大化。 A， B， C， D， E是可行域的顶点，对有限个约束条件则其可行域的顶点也是有限的。x1x2z=20000=50x1+100x2图 2-2z=27500=50x1+100x2z=0=50x1+100x2z=10000=50x1+100x2 CBADE9管 理 运 筹 学2 图 解 法 线性规划的标准化内容之一： 引入松驰变量（含义是资源的剩余量）例 1 中引入 s1， s2， s3 模型化为目标函数 ： Max z = 50 x1 + 100 x2 + 0 s1 + 0 s2 + 0 s3约束条件 ： s.t. x1 + x2 + s1 = 3002 x1 + x2 + s2 = 400x2 + s3 = 250x1 , 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=50x1+50x2，则线段 BC上的所有点都代表了最优解； 无界解。即可行域的范围延伸到无穷远，目标函数值可以无穷大或无穷小。一般来说，这说明模型有错，忽略了一些必要的约束条件； 无可行解。若在例 1的数学模型中再增加一个约束条件 4x1+3x21200， 则 可行域 为 空域，不存在满 足 约 束条件的解，当然也就不存在最 优 解了。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 = 2x1 + 3 x2约束条件：s.t. x1 + x2 350x1 1252 x1 + x2 600x1 , x2 0采用图解法。如下图： 得 Q点坐标（ 250， 100）为最优解。100 200 300 400 500 600100200300400600500x1 =125x1+x2 =3502x1+3x2 =8002x1+3x2 =9002x1+x2 =6002x1+3x2 =1200x1 x2 Q13管 理 运 筹 学3 图解法的灵敏度分析线性规划的标准化 一般形式目标函数： Max （ Min） z = c1 x1 + c2 x2 + + cn xn 约束条件： s.t. a11 x1 + a12 x2 + + a1n xn （ =, ） b1a21 x1 + a22 x2 + + a2n xn （ =, ） b2 am1 x1 + am2 x2 + + amn xn （ =, ） bmx1 ， x2 ， ， xn 0 标准形式目标函数： Max z = c1 x1 + c2 x2 + + cn xn 约束条件： s.t. a11 x1 + a12 x2 + + a1n xn = b1a21 x1 + a22 x2 + + a2n xn = b2 am1 x1 + am2 x2 + + amn xn = bmx1 ， x2 ， ， xn 0， bi 014管 理 运 筹 学3 图解法的灵敏度分析可以看出，线性规划的标准形式有如下四个特点： 目标最大化； 约束为等式； 决策变量均非负； 右端项非负。对于各种非标准形式的线性规划问题，我们总可以通过以下变换，将其转化为标准形式 :15管 理 运 筹 学3 图解法的灵敏度分析1.极小化目标函数的问题：设目标函数为Min f = c1x1 + c2x2 + + cnxn (可以 )令 z -f ，则该极小化问题与下面的极大化问题有相同的最优解，即 Max z = - c1x1 - c2x2 - - cnxn 但 必须注意，尽管以上两个问题的最优解相同，但它们最优解的目标函数值却相差一个符号，即Min f - Max z16管 理 运 筹 学3 图解法的灵敏度分析2、约束条件不是等式的问题 ：设约束条件为ai1 x1+ai2 x2+ + ain xn bi可以引进一个新的变量 s ， 使它等于约束右边与左边之差s=bi( ai1 x1 + ai2 x2 + + ain xn )显然， s 也具有非负约束，即 s0 ，这时新的约束条件成为ai1 x1+ai2 x2+ + ain xn+s = bi17管 理 运 筹 学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 = bi18管 理 运 筹 学3 图解法的灵敏度分析为了使 约束由不等式成为等式而引进的变量 s,当不等式为 “ 小于等于 ” 时 称为 “ 松弛变量 ” ； 当不等式为 “ 大 于等于 ” 时 称为 “ 剩余变量 ” 。如果原问题中有若干个非等式 约束，则将其转化为标准形式时，必须对各个约束引进不同的松弛变量。3.右端项有负值的问题：在标准形式中，要求右端项必须每一个分量非负。当某一个右端项系数为负时，如 bi0， 则把该等式约束两端同时乘以 -1，得到： -ai1 x1-ai2 x2- - ain xn = -bi。19管 理 运 筹 学3 图解法的灵敏度分析例：将以下线性规划问题转化为标准形式 Min f = 2 x1 -3x2 + 4 x3s.t. 3 x1 + 4x2 - 5 x3 62 x1 + x3 8x1 + x2 + x3 = -9x1 , x2 , x3 0 解：首先 ,将目标函数转换成极大化：令 z= -f = -2x1+3x2-4x3 其次考虑约束，有 2个不等式约束，引进松弛变量x4， x5 0 。第三个约束条件的右端值为负，在等式两边同时乘 -1。20管 理 运 筹 学3 图解法的灵敏度分析通过以上变换，可以得到以下标准形式的线性规划问题： Max z = - 2x1 + 3 x2 - 4x3s.t. 3x1+4x2-5x3 +x4 = 62x1 +x3 -x5= 8-x1 -x2 -x3 = 9x1 ,x2 ,x3 ,x4 ,x5 0* 变量无符号限制的问题 *：在标准形式中，必须每一个变量均有非负约束。当某一个变量 xj没有非负约束时，可以令xj = xj - xj”其中xj 0 ， xj” 0即用两个非负变量之差来表示一个无符号限制的变量，当然 xj的符号取决于 xj 和 xj” 的大小。21管 理 运 筹 学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 仍是最优解。 一般情况：z = c1 x1 + c2 x2 写成斜截式 x2 = - (c1 / c2 ) x1 + z / c2 目标函数等值线的斜率为 - (c1 / c2 ) ，当 -1 - (c1 / c2 ) 0 （ *） 时，原最优解仍是最优解。22管 理 运 筹 学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 。23管 理 运 筹 学3 图解法的灵敏度分析3.2 约束条件中右边系数 bj 的灵敏度分析当约束条件中右边系数 bj 变化时，线性规划的可行域发生变化，可能引起最优解的变化。考虑例 1的情况： 假设设备台时增加 10个台时，即 b1变化为 310，这时可行域扩大， 最优解为 x2 = 250 和 x1 + x2 = 310 的交点 x1 = 60， x2 = 250 。变化后的总利润 - 变化前的总利润 = 增加的利润(5060+ 100250) - (50 50+100 250) = 500 ， 500 /10 = 50 元说明在一定范围内每增加（减少） 1个台时的设备能力就可增加（减少） 50元利润，称为该约束条件的对偶价格。24管 理 运 筹 学3 图解法的灵敏度分析假设原料 A 增加 1