第二章 线性规划的图解法

1、第二章 线性规划的图解法一、线性规划的概念一、线性规划的概念二、线性规划问题的提出二、线性规划问题的提出三、线性规划的数学模型三、线性规划的数学模型四、线性规划的图解法四、线性规划的图解法五、线性规划解的情况五、线性规划解的情况六、六、LP图解法的灵敏度分析图解法的灵敏度分析一、线性规划的概念线性规划线性规划Linear Programming 简称简称LP，是一，是一种解决在种解决在线性约束条件线性约束条件下追求最大或最小的下追求最大或最小的线性目标函数线性目标函数的方法。的方法。线性规划的目标和约束条件都可以表示成线线性规划的目标和约束条件都可以表示成线性的式子。性的式子。 例例1.1、胜

2、利家具厂生产桌子和椅子两种家具，桌子售价、胜利家具厂生产桌子和椅子两种家具，桌子售价50元元/张，椅子售价张，椅子售价30元元/张。生产一张桌子需要木工张。生产一张桌子需要木工4h，油漆，油漆工工2h，生产一张椅子需要木工，生产一张椅子需要木工3h，油漆工，油漆工1h。该厂每月可用。该厂每月可用木工工时木工工时120h，油漆工工时，油漆工工时50h。问该厂每月生产多少张桌。问该厂每月生产多少张桌子和椅子才能使每月的销售收入最大？子和椅子才能使每月的销售收入最大？ 解：解： 1、确定决策变量、确定决策变量 x1、x2每月生产桌子、椅子的数量；每月生产桌子、椅子的数量； 2、确定目标函数、确定目标

3、函数销售收入最大销售收入最大 Max s =50 x1+30 x2 3、确定约束条件、确定约束条件 s.t. 4x1+3x2 120 2x1+x2 50 4、变量非负限制、变量非负限制 x1 ,x2 0二、线性规划问题的提出 线性规划模型：线性规划模型： Max s =50 x1+30 x2 s.t. 4x1+3x2 120 2x1+x2 50 x1 ,x2 0产品甲 产品乙 生产能力设备A设备B2111108单位利润32承导入案例承导入案例设两种产品产量为设两种产品产量为x1,x2,则有则有:12121212max32210. .8,0zxxxxstxxx x总利润表达式总利润表达式最大化最

4、大化设备设备A台时占用台时占用设备设备B台时占用台时占用生产能力生产能力,不不允许超过允许超过产量非负产量非负决策变量决策变量（decision variable） 目标函数目标函数（objective function） 约束条件约束条件（subject to）三要素三要素当目标函数与约束条件均为决策变当目标函数与约束条件均为决策变量的线性函数，且变量取连续值时，量的线性函数，且变量取连续值时，称为线性规划称为线性规划LP；变量取整称为整；变量取整称为整数线性规划数线性规划ILP；变量取二进制为；变量取二进制为0-1规划规划BLP。例例1.2 某工厂用三种原料生产三种产品，已知的条件某工厂用

5、三种原料生产三种产品，已知的条件如下表所示，试制订总利润最大的生产计划如下表所示，试制订总利润最大的生产计划单位产品所需原料数量单位产品所需原料数量（公斤）（公斤）产品产品Q1产品产品Q2产品产品Q3原料可用量原料可用量（公斤（公斤/日）日）原料原料P12301500原料原料P2024800原料原料P33252000单位产品的利润（千元）单位产品的利润（千元）354决策变量：每天生产三种产品的数量，分别决策变量：每天生产三种产品的数量，分别设为设为x1，x2，x3；目标：每天的生产利润最大目标：每天的生产利润最大目标函数为目标函数为Max s 3x15x24x3约束条件：每天原料的需求量不超过

6、可用量约束条件：每天原料的需求量不超过可用量原料原料P1 ： 2x13x20 x3 1500原料原料P2 ： 0 x12x24x3800原料原料P3 ： 3x12x25x32000隐含约束：产量为非负数隐含约束：产量为非负数x1 ，x2 ，x3 0 数学模型：数学模型：Max s = 3x15x24x3 s.t. 2x13x20 x3 1500 0 x12x24x3800 3x12x25x32000 x1 ，x2 ，x3 0从前面两个例子中可以看出一般线性规划问题从前面两个例子中可以看出一般线性规划问题的建模过程：的建模过程：A、理解要解决的问题，明确在什么条件下，、理解要解决的问题，明确在什

7、么条件下，要追求什么目标；要追求什么目标；B、定义决策变量；、定义决策变量；C、用决策变量的线性函数形式写出所要追求、用决策变量的线性函数形式写出所要追求的目标，即目标函数的目标，即目标函数,按问题的不同，要求目按问题的不同，要求目标函数实现最大化和最小化；标函数实现最大化和最小化；D、用一组决策变量的等式或不等式来表示在、用一组决策变量的等式或不等式来表示在解决问题过程中所必须遵循的约束条件。解决问题过程中所必须遵循的约束条件。1、LP模型的一般形式模型的一般形式目标函数：目标函数：Max(Min)z = c1x1 + c2x2 + + cnxn约束条件：约束条件： a11x1+a12x2+

8、a1nxn( =, )b1a21x1+a22x2+a2nxn( =, )b2 . . . am1x1+am2x2 +amnxn( =, )bmx1 ，x2 ， ，xn ( ) 0 或无约束或无约束三、线性规划的数学模型xj为待定的决策变量；为待定的决策变量；cj为目标函数系数，或价值系数、费用系数；为目标函数系数，或价值系数、费用系数；aij为技术系数；为技术系数；bj为资源常数，简称右端项；为资源常数，简称右端项；其中其中i1，2，m； j1，2，n可以看出，一般可以看出，一般LP模型的特点：模型的特点：A、决策变量、决策变量x1，x2，x3，xn表示要寻求表示要寻求的方案，每一组值就是一个

9、方案；的方案，每一组值就是一个方案；B、约束条件是用等式或不等式表述的限制、约束条件是用等式或不等式表述的限制条件；条件；C、一定有一个追求目标，或希望最大或希、一定有一个追求目标，或希望最大或希望最小；望最小；D、所有函数都是线性的。、所有函数都是线性的。1 122maxnnzc xc xc x=+11 112211(0)nna xa xa xb+=()1 1220mmmnnma xaxaxb+=2、线性规划模型的标准型：、线性规划模型的标准型：x1 0， x2 0， xn 0s.t.标准形式的特点：标准形式的特点：A、目标函数为、目标函数为Max形式形式B、约束全为式、约束全为式C、所有决

10、策变量、所有决策变量xj 0，j 1，2，3， nD、所有、所有bi0，i1，2，3， m3、如何将一般、如何将一般LP问题化为标准形问题化为标准形式式A、极小化目标函数问题转化为极大化目标、极小化目标函数问题转化为极大化目标函数问题：函数问题： 若目标函数为：若目标函数为： Min f = c1x1 + c2x2 + + cnxn 则可令则可令z -f ，原目标等同于：，原目标等同于： Max z = -c1x1 - c2x2 - - cnxn 但须注意但须注意, f* z*B、约束条件不是等式的问题：约束条件不是等式的问题： 若约束条件为若约束条件为 ai1 x1+ai2 x2+ +ain

11、 xn bi 可以引进一个新的变量可以引进一个新的变量si ，使它等于约束右，使它等于约束右边与左边之差边与左边之差 si=bi(ai1 x1 + ai2 x2 + + ain xn ) 显然，显然，si 也具有非负约束，即也具有非负约束，即si0， 这时新的约束条件成为这时新的约束条件成为 ai1 x1+ai2 x2+ +ain xn+si = bi当约束条件为当约束条件为 ai1 x1+ai2 x2+ +ain xn bi时，类似地令时，类似地令 si= (ai1 x1 + ai2 x2 + + ain xn ) bi显然，显然，si也满足非负约束，即也满足非负约束，即si0，这时新，这时

12、新的约束条件成为的约束条件成为 ai1 x1+ai2 x2+ +ain xn-s = bi注意：注意：不同的约束不等式引入的变量也不同；不同的约束不等式引入的变量也不同；一般称一般称不等式中引入的变量为松弛变量，称不等式中引入的变量为松弛变量，称不等式中引入的变量为剩余变量。不等式中引入的变量为剩余变量。C、变量符号限制的问题：、变量符号限制的问题：当某一个变量当某一个变量xj 0时，可以令时，可以令 xj = -xj 则则xj0当某一个变量当某一个变量xj没有非负约束时，可以令没有非负约束时，可以令 xj = xj- xj”其中其中 xj0，xj”0D、右端项有负值的问题：、右端项有负值的问

13、题：如如 bi0S3=0剩余变量的值和意义请大家下去后阅读教材请大家下去后阅读教材1517页例页例2课堂练习：图解法求解以下LP问题 目标函数目标函数 Max z = 2500 x1 + 1500 x2 约束条件约束条件 s.t. 3x1+2x2 65 2x1+x2 40 3x2 75 x1 ,x2 0X1X2O3x1+2x265302010102030403x2752x1+x240（15，10）4050答案：答案：最优解为：最优解为： x1 15 ，x210最优值为：最优值为：z*250015+150010 52500五、线性规划问题解的情况例例1.5的最优解只有一个，这是线性规划问题的最优

14、解只有一个，这是线性规划问题最一般的解的情况，但线性规划问题解的情最一般的解的情况，但线性规划问题解的情况还存在其它特殊的可能：无穷多最优解、况还存在其它特殊的可能：无穷多最优解、无界解或无可行解。无界解或无可行解。1、有唯一最优解的情况例例1.5中即是，在此不再赘述。中即是，在此不再赘述。如果一个线性规划问题有最优解，则一定有如果一个线性规划问题有最优解，则一定有一个可行域的顶点对应最优解，唯一最优解一个可行域的顶点对应最优解，唯一最优解一定在可行域的顶点上取得。一定在可行域的顶点上取得。在例在例1. 5的线性规划模型中的线性规划模型中 目标函数：目标函数：Max z= 50 x1+100

15、x2 约束条件：约束条件：x1+x2300 2x1+x2400 x2250 x1 0， x2 0 若目标函数变为：若目标函数变为： Max z= 50 x1+50 x2 2、无穷多最优解的情况A(0,250)B(50,250)C(100,200)D(200,0)X1X2O300200100100200300400最优情况下目标函数最优情况下目标函数的等值线与直线的等值线与直线BC重重合。这时，最优解有合。这时，最优解有无穷多个，是从点无穷多个，是从点 B到点到点 C 线段上的所有线段上的所有点，最优值为点，最优值为15000。2、无穷多最优解的情况、无穷多最优解的情况3、无界解的情况若将例若将

16、例1.5的线性规划模型中约束条件的线性规划模型中约束条件1、2的的不等式符号改变，则线性规划模型变为：不等式符号改变，则线性规划模型变为： 目标函数：目标函数：Max z= 50 x1+100 x2 约束条件：约束条件：x1+x2 300 2x1+x2 400 x2250 x1 0， x2 0X1X2可行域成为一个可行域成为一个无上界无上界的区域。这时，没有有的区域。这时，没有有限最优解。限最优解。3、无界解的情况4、无可行解的情况在例在例1.5的线性规划模型中，如果增加约束条的线性规划模型中，如果增加约束条件件x1 400，则模型变为：，则模型变为：目标函数：目标函数：Max z= 50 x

17、1+100 x2 约束条件：约束条件：x1+x2300 2x1+x2400 x2250 x1 400 x1 0， x2 04、无可行解的情况可行域成为空的区域。这时，没有可行域成为空的区域。这时，没有可行解，显然线性规划问题无解。可行解，显然线性规划问题无解。X1X2Ox1+x2300300200100100200300400 x22502x1+x2400 x1400根据以上例题，进一步分析可知线性规划的可行域根据以上例题，进一步分析可知线性规划的可行域和最优解有以下几种可能的情况，简图如下：和最优解有以下几种可能的情况，简图如下：可行域有界可行域有界唯一最优解唯一最优解可行域有界可行域有界多

18、个最优解多个最优解可行域无界可行域无界唯一最优解唯一最优解可行域无界可行域无界无穷多最无穷多最优解优解可行域无界可行域无界目标函数无界目标函数无界可行域为空集可行域为空集无可行解无可行解课堂练习：用图解法求解目标函数目标函数 Max z = 3x1 + 9x2 约束条件约束条件 s.t. x1+3x2 22 -x1+x2 4 x26 2x1-5x2 0 x1 ,x2 0v答案：答案：v无穷多最优解，最优解在第一条直无穷多最优解，最优解在第一条直线确定的可行域边界上，最优值为线确定的可行域边界上，最优值为66。六、LP问题图解法的灵敏度分析主要研究线性规划模型中的一些系数主要研究线性规划模型中的

19、一些系数cj，bi，aij变化时，对最优解产生的影响。变化时，对最优解产生的影响。1、目标函数系数、目标函数系数ci的灵敏度分析的灵敏度分析系数系数ci的变动直接的变动直接影响目标函数等值影响目标函数等值线的斜率线的斜率k。kBCkkAB时，最时，最优解不变。优解不变。X1X2Ox1+x2300300200100100200300400 x22502x1+x2400BACC1150C175C1-100对于例对于例1.5，将目标函数系数，将目标函数系数c1，c2作为参数作为参数来讨论，目标函数为：来讨论，目标函数为：maxz c1 x1+ c2 x2要使最优解在点要使最优解在点B(50,250)

20、不变，必须保持目不变，必须保持目标函数等值线的斜率在直线标函数等值线的斜率在直线x1+x2300和和x2250之间。之间。即即-1- c1 / c2 0当当c150不变时，不变时， -1- 50 / c2 0即即c2的取值范围为的取值范围为c250；当当c2 100不变时，不变时， -1- c1 / 100 0即即c2的取值范围为的取值范围为100 c10课堂练习v分析以下模型中分析以下模型中c1的取值范围和最优解之间的取值范围和最优解之间的关系：的关系： Max z = c1 x1 + 9x2 s.t. x1+x2 6 x1+2x2 10 x1 ,x2 02、约束条件中右端常数、约束条件中右

21、端常数bi的灵敏度分析的灵敏度分析例例1.5中，当设备台时数中，当设备台时数增加增加10个单位时，第一个单位时，第一个约束条件变为：个约束条件变为： x1+x2310，可行域发生，可行域发生变化。变化。X1X2Ox1+x2300300200100100200300400 x22502x1+x2400 x1+x2310此时最优解为：此时最优解为：x160 ， x2250最优值为最优值为z*28000比原最优值增加了比原最优值增加了28000-27500500（元）（元）ABCDX1X2O300200100100200300400BC可见每增加一个台时的设备就可以多获得可见每增加一个台时的设备就可

22、以多获得500/1050元的利润。元的利润。资源常数每增加一个单位而使最优目标函数资源常数每增加一个单位而使最优目标函数值得到值得到改进改进的数量，称为该资源的的数量，称为该资源的对偶价格对偶价格。设备的对偶价格为设备的对偶价格为50元元/台时。台时。问题：一般情况下设备租价为问题：一般情况下设备租价为20元元/台时，最台时，最近设备紧张，要增加设备，出价高达近设备紧张，要增加设备，出价高达40元元/台台时。问是否应该增加租用设备？时。问是否应该增加租用设备？当原料当原料A的限制变为的限制变为 2x1+x2410时，可行域时，可行域会扩大。会扩大。但不会影响最优解和最但不会影响最优解和最优值。

23、优值。故原料故原料A的对偶价格为的对偶价格为0。ABCDX1X2O300200100100200300400例例1.5中，当原材料中，当原材料B增加增加10个单位时，第三个约束条件个单位时，第三个约束条件变为：变为：x2260，可行域发生，可行域发生变化。变化。最优解变为最优解变为K(40,260)，最优，最优值变为值变为28000。可见原材料。可见原材料B的对偶价格为的对偶价格为50。X1X2Ox1+x2300300200100100200300400 x22502x1+x2400 x2260K思考题：对于目标函数思考题：对于目标函数最小化最小化的的LP模型，模型，A、如果、如果i 约束条件中约束条件中bi的对偶价格为的对偶价格为30， bi增加增加2，则其最优目标函数值将，则其最优目标函数值将 ；B、如果、如果bi的对偶价格为的对偶价格为20， bi增加增加2，则，则其目标函数值将会其目标函数