第二章线性规划的图解法

第二章线性规划的图解法一、线性规划的概念二、线性规划问题的提出三、线性规划的数学模型四、线性规划的图解法五、线性规划解的情况六、LP图解法的灵敏度分析一、线性规划的概念线性规划LinearProgramming简称LP，是一种解决在线性约束条件下追求最大或最小的线性目标函数的方法。线性规划的目标和约束条件都可以表示成线性的式子。例1.1、胜利家具厂生产桌子和椅子两种家具，桌子售价50元/张，椅子售价30元/张。生产一张桌子需要木工4h，油漆工2h，生产一张椅子需要木工3h，油漆工1h。该厂每月可用木工工时120h，油漆工工时50h。问该厂每月生产多少张桌子和椅子才能使每月的销售收入最大？解：1、确定决策变量

x1、x2——每月生产桌子、椅子的数量；

2、确定目标函数——销售收入最大

Maxs=50x1+30x23、确定约束条件s.t.

4x1+3x2≤1202x1+x2≤504、变量非负限制x1,x2≥0二、线性规划问题的提出

线性规划模型：

Maxs=50x1+30x2

s.t.

4x1+3x2≤1202x1+x2≤50x1,x2≥0例1.2某工厂用三种原料生产三种产品，已知的条件如下表所示，试制订总利润最大的生产计划单位产品所需原料数量（公斤）产品Q1产品Q2产品Q3原料可用量（公斤/日）原料P12301500原料P2024800原料P33252000单位产品的利润（千元）354决策变量：每天生产三种产品的数量，分别设为x1，x2，x3；目标：每天的生产利润最大目标函数为Maxs＝3x1＋5x2＋4x3约束条件：每天原料的需求量不超过可用量原料P1

：2x1＋3x2＋0x3≤1500原料P2

：0x1＋2x2＋4x3≤800原料P3

：3x1＋2x2＋5x3≤2000隐含约束：产量为非负数x1

，x2，x3≥0数学模型：Maxs=3x1＋5x2＋4x3

s.t.

2x1＋3x2＋0x3≤15000x1＋2x2＋4x3≤8003x1＋2x2＋5x3≤2000x1

，x2，x3≥0从前面两个例子中可以看出一般线性规划问题的建模过程：A、理解要解决的问题，明确在什么条件下，要追求什么目标；B、定义决策变量；C、用决策变量的线性函数形式写出所要追求的目标，即目标函数；D、用一组决策变量的等式或不等式来表示在解决问题过程中所必须遵循的约束条件。1、LP模型的一般形式目标函数：Max(Min)z=c1x1+c2x2+…+cnxn约束条件：a11x1+a12x2+…+a1nxn≤(=,≥)b1a21x1+a22x2+…+a2nxn≤(=,≥)b2

...am1x1+am2x2+…+amnxn≤(=,≥)bmx1，x2，…，xn≥(≤)0或无约束三、线性规划的数学模型xj为待定的决策变量；cj为目标函数系数，或价值系数、费用系数；aij为技术系数；bj为资源常数，简称右端项；其中i＝1，2，…m；j＝1，2，…n可以看出，一般LP模型的特点：A、决策变量x1，x2，x3，……xn表示要寻求的方案，每一组值就是一个方案；B、约束条件是用等式或不等式表述的限制条件；C、一定有一个追求目标，或希望最大或希望最小；D、所有函数都是线性的。2、线性规划模型的标准型：x1≥0，x2≥0，…，xn≥0s.t.标准形式的特点：A、目标函数为Max形式B、约束全为＝式C、所有决策变量xj≥0，j＝1，2，3，…nD、所有bi≥0，i＝1，2，3，……m3、如何将一般LP问题化为标准形式A、极小化目标函数问题转化为极大化目标函数问题：若目标函数为：

Minf=c1x1+c2x2+…+cnxn

则可令z＝-f，原目标等同于：

Maxz=-c1x1-c2x2-…-cnxn

但须注意,f*＝–z*B、约束条件不是等式的问题：若约束条件为

ai1x1+ai2x2+…+ain

xn≤bi

可以引进一个新的变量si

，使它等于约束右边与左边之差

si=bi–(ai1x1+ai2x2+…+ain

xn)

显然，si

也具有非负约束，即si≥0，这时新的约束条件成为

ai1x1+ai2x2+…+ain

xn+si=bi当约束条件为

ai1x1+ai2x2+…+ain

xn

≥bi时，类似地令

si=(ai1x1+ai2x2+…+ain

xn)–bi显然，si也满足非负约束，即si≥0，这时新的约束条件成为

ai1x1+ai2x2+…+ain

xn-s=bi注意：不同的约束不等式引入的变量也不同；一般称≤不等式中引入的变量为松弛变量，称≥不等式中引入的变量为剩余变量。C、变量符号限制的问题：当某一个变量xj

≤0时，可以令

xj=-xj’

则xj’≥0当某一个变量xj没有非负约束时，可以令

xj=xj’-xj”其中xj’≥0，xj”≥0D、右端项有负值的问题：如bi<0，则把该等式约束两端同时乘以-1，得到：-ai1x1-ai2x2-…-ain

xn=-bi

。例1.3：将以下线性规划问题转化为标准形式

Minf=3.6x1-5.2x2+1.8x3s.t.2.3x1+5.2x2-6.1x3≤15.74.1x1+3.3x3≥8.9x1+x2+x3=38x1,x2,x3≥0解：首先，将目标函数转换成极大化：令z=-f=-3.6x1+5.2x2-1.8x3

其次考虑约束，有2个不等式约束，引进松弛变量x4

，x5≥0。于是，我们可以得到以下标准形式的线性规划问题：Maxz=-3.6x1+5.2x2-1.8x3s.t.2.3x1+5.2x2-6.1x3+x4=15.74.1x1+3.3x3–x5=8.9x1+x2+x3=38x1,x2,x3,x4,x5≥0例1.4将以下线性规划问题转化为标准形式minf=x1+2x2+3x3s.t.x1-x2+x3≤4x1+2x3≥8x1+x2+x3≥2x1≥0,x2≤0答案：标准型为maxz=-x1+2x2’-3x3’+3x3’’s.t.x1+x2’+x3’－

x3’’+s1=4x1+2x3’－2x3’’–s2＝8x1-x2

’+x3’－

x3’’–s3

＝2x1

，x2’

，x3’，

x3’’，

s1，s2，s3≥0（注：其中z＝-f，x2’

=-x2

，

x3’－x3’’

＝x3

）对于只有两个决策变量的线性规划问题，可以在二维直角坐标平面上作图表示线性规划问题的有关概念，并求解。四、线性规划的图解法例1.5某工厂在计划期内要安排Ⅰ，Ⅱ两种产品的生产，生产单位产品所需的设备台时及A、B两种原材料的消耗以及资源的限制如表所示：产品ⅠⅡ资源限制设备11300台时原料A21400kg原料B01250kg工厂每生产一单位产品Ⅰ可以获利50元，每生产一单位产品Ⅱ可获利100元，问工厂应分别生产多少单位产品Ⅰ和产品Ⅱ才能使获利最多？问题的线性规划模型：目标函数：maxz=50x1+100x2

约束条件：x1+x2≤300

2x1+x2≤400

x2≤250

x1≥0，x2≥0第一步：确定可行域X1X2Ox1+x2＝300300200100100200300400x2＝2502x1+x2＝400可行域第二步：作目标函数等值线，确定使目标函数最优的点X1X2OZ＝10000300200100100200300400等值线法线z＝0(50,250)Z＝27500等值线最优解最优值故原问题最优解为：x1＝50，x2＝250最优值为27500。图解法求解线性规划问题的步骤：

1、建立直角坐标系。

2、画出可行域。

3、作目标函数的等值线

4、找出最优解。X1X2Ox1+x2＝300300200100100200300400x2＝2502x1+x2＝400最优解：x1＝50x2＝250非可行解：x1＝200x2＝300可行解：x1＝100x2＝100可行域线性规划中解的概念线性规划中几个的概念1、解：决策变量的任意一组取值；2、可行解：满足约束条件（包括非负条件）的一组决策变量值，称可行解；3、可行域：所有可行解的集合；4、最优解：使目标函数值最优（即使最大化目标函数值最大，使最小化目标函数最小）的可行解；5、最优值：最优解对应的目标函数值。松弛变量的值和意义例1.5的线性规划模型化为标准型：目标函数：maxz=50x1+100x2

约束条件：x1+x2+s1＝300

2x1+x2+s2＝400

x2+s3＝250

x1,x2,s1,s2,s3≥0引入的松弛变量常常表示未被充分利用的资源条件。松弛变量的值和意义对最优解x1＝50，x2＝250来说，各松弛变量的值如下表所示：约束条件松弛变量的值设备台时数S1=0原料AS2=50原料BS3=0松弛变量的值也可以从图解法中获得一些信息：X1X2Ox1+x2＝300300200100100200300400x2＝2502x1+x2＝400最优解：x1＝50x2＝250S1=0S2>0S3=0剩余变量的值和意义请大家下去后阅读教材15－17页例2课堂练习：图解法求解以下LP问题目标函数

Maxz=2500x1+1500x2

约束条件

s.t.3x1+2x2≤652x1+x2≤403x2≤75x1,x2≥0X1X2O3x1+2x2＝65302010102030403x2＝752x1+x2＝40（15，10）4050答案：最优解为：x1＝15，x2＝10最优值为：z*＝2500×15+1500×10

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

约束条件：x1+x2≤300

2x1+x2≤400

x2≤250

x1≥0，x2≥0

若目标函数变为：Maxz=50x1+50x2

2、无穷多最优解的情况A(0,250)B(50,250)C(100,200)D(200,0)X1X2O300200100100200300400最优情况下目标函数的等值线与直线BC重合。这时，最优解有无穷多个，是从点B到点C线段上的所有点，最优值为15000。2、无穷多最优解的情况3、无界解的情况若将例1.5的线性规划模型中约束条件1、2的不等式符号改变，则线性规划模型变为：目标函数：Maxz=50x1+100x2

约束条件：x1+x2≥

300

2x1+x2≥

400

x2≤250

x1≥0，x2≥0X1X2可行域成为一个无上界的区域。这时，没有有限最优解。3、无界解的情况4、无可行解的情况在例1.5的线性规划模型中，如果增加约束条件x1≥400，则模型变为：目标函数：Maxz=50x1+100x2

约束条件：x1+x2≤300

2x1+x2≤400

x2≤250

x1≥400x1≥0，x2≥04、无可行解的情况可行域成为空的区域。这时，没有可行解，显然线性规划问题无解。X1X2Ox1+x2＝300300200100100200300400x2＝2502x1+x2＝400x1＝400根据以上例题，进一步分析可知线性规划的可行域和最优解有以下几种可能的情况，简图如下：可行域有界—唯一最优解可行域有界—多个最优解可行域无界—唯一最优解可行域无界—无穷多最优解可行域无界—目标函数无界可行域为空集—无可行解课堂练习：用图解法求解目标函数

Maxz=3x1+9x2

约束条件

s.t.x1+3x2≤22-x1+x2≤4x2≤62x1-5x2≤0x1,x2≥0答案：无穷多最优解，最优解在第一条直线确定的可行域边界上，最优值为66。六、LP问题图解法的灵敏度分析主要研究线性规划模型中的一些系数cj，bi，aij变化时，对最优解产生的影响。1、目标函数系数ci的灵敏度分析系数ci的变动直接影响目标函数等值线的斜率k。kBC≤k≤kAB时，最优解不变。X1X2Ox1+x2＝300300200100100200300400x2＝2502x1+x2＝400BACC1＝150C1＝75C1＝-100对于例1.5，将目标函数系数c1，c2作为参数来讨论，目标函数为：maxz＝c1x1+c2x2要使最优解在点B(50,250)不变，必须保持目标函数等值线的斜率在直线x1+x2＝300和x2＝250之间。即-1≤-c1/c2≤0当c1＝50不变时，-1≤-50/c2≤0即c2的取值范围为c2≥50；当c2＝100不变时，-1≤-c1/100≤0即c2的取值范围为100≥c1≥0课堂练习分析以下模型中c1的取值范围和最优解之间的关系：

Maxz=c1x1+9x2

s.t.x1+x2≤6x1+2x2≤10x1,x2≥02、约束条件中右端常数bi的灵敏度分析例1.5中，当设备台时数增加10个单位时，第一个约束条件变为：x1+x2≤310，可行域发生变化。X1X2Ox1+x2＝300300200100100200300400x2＝2502x1+x2＝400x1+x2＝310此时最优解为：x1＝60，x2＝250最优值为z*＝28000比原最优值增加了28000-27500＝500（元）ABCDX1X2O300200100100200300400B’C’可见每增加一个台时的设备就可以多获得500/10＝50元的利润。资源常数每增加一个单位而使最优目标函数值得到改进的数量，称为该资源的对偶价格。设备的对偶价格为50元/台时。问题：一般情况下设备租价为20元/台时，最近设备紧张，要增加设备，出价高达40元/台时。问是否应该增加租用设备？当原料A的限制变为

2x1+x2≤410时，可行域会扩大。但不会影响最优解和最优值。故原料A的对偶价格为0。ABCDX1X2O300200100100200300