管理运筹学第2章线性规划的图解法.ppt

管管 理理 运运 筹筹 学学第二章第二章 线性规划的图解法线性规划的图解法•§§1 1 问题的提出问题的提出•§§2 2 图解法图解法•§§3 3 图解法的灵敏度分析图解法的灵敏度分析1管管 理理 运运 筹筹 学学第二章第二章 线性规划的图解法线性规划的图解法在管理中一些典型的线性规划应用在管理中一些典型的线性规划应用•合理利用线材问题：如何在保证生产的条件下，下料最少•配料问题：在原料供应量的限制下如何获取最大利润•投资问题：从投资项目中选取方案，使投资回报最大•产品生产计划：合理利用人力、物力、财力等，使获利最大•劳动力安排：用最少的劳动力来满足工作的需要•运输问题：如何制定调运方案，使总运费最小线性规划的组成：线性规划的组成：•目标函数 Max F 或 Min F•约束条件 s.t. (subject to) 满足于•决策变量 用符号来表示可控制的因素2管管 理理 运运 筹筹 学学§1 §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      ≥  03管管 理理 运运 筹筹 学学§1 §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 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  =  27500§2 图图 解解 法法 对于只有两个决策变量的线性规划问题，可以在平面直角坐标系上作图表示线性规划问题的有关概念，并求解。

下面通过例1详细讲解其方法：5管管 理理 运运 筹筹 学学§2 图图 解解 法法 (1)分别取决策变量X1 , X2 为坐标向量建立直角坐标系在直角坐标系里，图上任意一点的坐标代表了决策变量的一组值，例1的每个约束条件都代表一个半平面x2x1X2≥0X2=0x2x1X1≥0X1=06管管 理理 运运 筹筹 学学§2 图图 解解 法法（2）对每个不等式(约束条件)，先取其等式在坐标系中作直线，然后确定不等式所决定的半平面100200300100200300x1+x2≤300x1+x2=3001001002002x1+x2≤4002x1+x2=400300200300400x1x1x2x27管管 理理 运运 筹筹 学学§2 图图 解解 法法（3）把五个图合并成一个图，取各约束条件的公共部分，如图2-1所示100100x2≤250x2=250200300200300x1x2x2=0x1=0x2=250x1+x2=3002x1+x2=400图2-1x2x1CBADE8管管 理理 运运 筹筹 学学§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+100x2CBADE9管管 理理 运运 筹筹 学学§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=50x1+50x2，则线段BC上的所有点都代表了最优解；11管管 理理 运运 筹筹 学学x1x2图2-2z=0=50x1+50x2CBADE12管管 理理 运运 筹筹 学学§2 图图 解解 法法•重要结论：–无界解即可行域的范围延伸到无穷远，目标函数值可以无穷大或无穷小一般来说，这说明模型有错，忽略了一些必要的约束条件；–无可行解若在例1的数学模型中再增加一个约束条件4x1+3x2≥1200，则可行域为空域，不存在满足约束条件的解，当然也就不存在最优解了13管管 理理 运运 筹筹 学学x1x2z=20000=50x1+100x2图2-2z=27500=50x1+100x2z=0=50x1+100x2z=10000=50x1+100x2CBADE14管管 理理 运运 筹筹 学学进进 一一 步步 讨讨 论论 例例2 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）为最优解100200300400500600100200300400600500x1 =125x1+x2 =3502x1+3x2 =8002x1+3x2 =9002x1+x2 =6002x1+3x2 =1200x1 x2 Q17管管 理理 运运 筹筹 学学§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 ≥018管管 理理 运运 筹筹 学学§3 图解法的灵敏度分析图解法的灵敏度分析 可以看出，线性规划的标准形式有如下四个特点：–目标最大化；–约束为等式；–决策变量均非负；–右端项非负。

对于各种非标准形式的线性规划问题，我们总可以通过以下变换，将其转化为标准形式:19管管 理理 运运 筹筹 学学§3 图解法的灵敏度分析图解法的灵敏度分析1.极小化目标函数的问题： 设目标函数为 Min f = c1x1 + c2x2 + … + cnxn (可以)令 z ＝ -f ， 则该极小化问题与下面的极大化问题有相同的最优解，即 Max z = - c1x1 - c2x2 - … - cnxn 但必须注意，尽管以上两个问题的最优解相同，但它们最优解的目标函数值却相差一个符号，即 Min f ＝ - Max z20管管 理理 运运 筹筹 学学§3 图解法的灵敏度分析图解法的灵敏度分析2、约束条件不是等式的问题： 设约束条件为 ai1 x1+ai2 x2+ … +ain xn ≤ bi 可以引进一个新的变量s ，使它等于约束右边与左边之差 s=bi–(ai1 x1 + ai2 x2 + … + ain xn )显然，s 也具有非负约束，即s≥0， 这时新的约束条件成为 ai1 x1+ai2 x2+ … +ain xn+s = bi21管管 理理 运运 筹筹 学学§3 图解法的灵敏度分析图解法的灵敏度分析 当约束条件为 ai1 x1+ai2 x2+ … +ain xn ≥ bi 时， 类似地令 s=(ai1 x1+ai2 x2+ … +ain xn)- bi 显然，s 也具有非负约束，即s≥0，这时新的约束条件成为 ai1 x1+ai2 x2+ … +ain xn-s = bi22管管 理理 运运 筹筹 学学§3 图解法的灵敏度分析图解法的灵敏度分析 为了使约束由不等式成为等式而引进的变量s,当不等式为“小于等于”时称为“松弛变量”；当不等式为“大于等于”时称为“剩余变量”。

如果原问题中有若干个非等式约束，则将其转化为标准形式时，必须对各个约束引进不同的松弛变量 3.右端项有负值的问题： 在标准形式中，要求右端项必须每一个分量非负当某一个右端项系数为负时，如 bi<0，则把该等式约束两端同时乘以-1，得到：-ai1 x1-ai2 x2- … -ain xn = -bi23管管 理理 运运 筹筹 学学§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 解：首先,将目标函数转换成极大化： 令 z= -f = -2x1+3x2-4x3 其次考虑约束，有2个不等式约束，引进松弛变量x4，x5 ≥0     第三个约束条件的右端值为负，在等式两边同时乘-1。

24管管 理理 运运 筹筹 学学§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 ≥ 025管管 理理 运运 筹筹 学学§3 图解法的灵敏度分析图解法的灵敏度分析4. *** 变量无符号限制的问题***： 在标准形式中，必须每一个变量均有非负约束当某一个变量xj没有非负约束时，可以令 xj = xj’- xj” 其中 xj’≥0，xj”≥0 即用两个非负变量之差来表示一个无符号限制的变量，当然xj的符号取决于xj’和xj”的大小26管管 理理 运运 筹筹 学学§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。

     第三个约束条件的右端值为负，在等式两边同时乘-1    第三个变量x3为负约束时，可以令x3 = -x3’ 27管管 理理 运运 筹筹 学学§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 ≥ 028管管 理理 运运 筹筹 学学§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 解：首先,将目标函数转换成极大化： 令 z= -f = -2x1+3x2-4x3 其次考虑约束，有2个不等式约束，引进松弛变量 x4，x5 ≥0。

     第三个约束条件的右端值为负，在等式两边同时乘-1 变量x3没有非负约束，可以令 x3= x3’- x3” 其中 x3’≥0，x3”≥029管管 理理 运运 筹筹 学学§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”） = 9 x1 ,x2 , x3’, x3” ,x4 ,x5 ≥ 030管管 理理 运运 筹筹 学学§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  （*） 时，原最优解仍是最优解31管管 理理 运运 筹筹 学学x1x2z=20000=50x1+100x2图2-2z=27500=50x1+100x2z=0=50x1+100x2z=10000=50x1+100x2CBADE32管管 理理 运运 筹筹 学学§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 33管管 理理 运运 筹筹 学学§3 图解法的灵敏度分析图解法的灵敏度分析 3.2  约束条件中右边系数 bj 的灵敏度分析      当约束条件中右边系数 bj 变化时，线性规划的可行域发生变化，可能引起最优解的变化      考虑例1的情况：        假设设备台时增加10个台时，即 b1变化为310，这时可行域扩大，最优解为    x2 = 250  和    x1 +  x2 = 310  的交点，                         最优解为 x1 = 60，x2 = 250      变化后的总利润 -  变化前的总利润 = 增加的利润      (50×60+ 100×250) - (50 × 50+100 × 250) = 500               每个台时的价值为   500 / 10 = 50 元       说明在一定范围内每增加（减少）1个台时的设备能力就可增加（减少）50元利润，称为该约束条件的对偶价格。

34管管 理理 运运 筹筹 学学§3 图解法的灵敏度分析图解法的灵敏度分析       假设原料 A 增加10 千克时，即 b2变化为410，这时可行域扩大，      但最优解仍为    x2 = 250    和    x1 +  x2 = 300  的交点 x1 = 50，x2 = 250           此变化对总利润无影响，该约束条件的对偶价格为 0        解释：原最优解没有把原料 A 用尽，有50千克的剩余，因此增加10千克值增加了库存，而不会增加利润      35管管 理理 运运 筹筹 学学§3 图解法的灵敏度分析图解法的灵敏度分析在一定范围内，当约束条件右边常数增加1个单位时  （1）若约束条件的对偶价格大于0，则其最优目标函数值得到改善（变好）；  （2）若约束条件的对偶价格小于0，则其最优目标函数值受到影响（变坏）；  （3）若约束条件的对偶价格等于0，则最优目标函数值不变。