运筹学第2章线性规划的图解法

1、第二章第二章线性规划的图解法线性规划的图解法 1 1问题的提出问题的提出 2 2图解法图解法 3 3线性规划的标准化线性规划的标准化 4 4图解法的灵敏度分析图解法的灵敏度分析第二章第二章线性规划的图解法线性规划的图解法在管理中一些典型的线性规划应用在管理中一些典型的线性规划应用 合理利用线材问题：如何在保证生产的条件下，下料最少 配料问题：在原料供应量的限制下如何获取最大利润 投资问题：从投资项目中选取方案，使投资回报最大 产品生产计划：合理利用人力、物力、财力等，使获利最大 劳动力安排：用最少的劳动力来满足工作的需要 运输问题：如何制定调运方案，使总运费最小线性规划的组成：线性规划的组成：

2、目标函数 Max F 或 Min F约束条件 s.t. (subject to) 满足于决策变量 用符号来表示可控制的因素1 1问题的提出问题的提出例例1. 某工厂在计划期内要安排、两种产品的生产，已知生产单位产品所需的设备台时及A、B两种原材料的消耗、资源的限制，如下表：问题：工厂应分别生产多少单位、产品才能使工厂获利最多？线性规划模型：线性规划模型： 目标函数：Max z = 50 x1 + 100 x2 约束条件：s.t. x1 + x2 300 2 x1 + x2 400 x2 250 x1 , x2 0 一家工厂制造三种产品，需要三种资源：技术服务、劳动力、行政管理。下表列出了三种单

3、位产品对每种资源的需要量。今有100h的技术服务，600h的劳动力和300h的行政管理时间可供使用。试确定能使总利润最大的产品生产量的线性规划模型。产品资源/h单位利润/元技术服务 劳动力行政管理11102102142631564 解：设三种产品的生产量分别为x1、x2、x3。 线性规划模型为： Max z=10 x1+6x2+4x3 S.t. x1+x2+x3100 10 x1+4x2+5x3 600 2x1+2x2+6x3 300 x1,x2,x30例例2 M&D公司生产两种产品A和B，基于对现有的存储水平和下一个月的市场潜力的分析，M&D公司管理层决定A和B的总产量至少要

4、达到350千克，此外，公司的一个客户订了125千克的A产品必须首先满足。每千克A、B产品的制造时间分别为2小时和1小时，总工作时间为600小时。每千克A、B产品的原材料成本分别为2$和3$。确定在满足客户要求的前提下，原材料成本最小的生产计划。解：设产品 A、B 的产量分别为y, x。则，数学模型为： 0600235012532y, xyxyxxyxZmin 1 1问题的提出问题的提出 建模过程建模过程1.理解要解决的问题，了解解题的目标和条件；2.定义决策变量（ x1 ，x2 ， ，xn ），每一组值表示一个方案；3.用决策变量的线性函数形式写出目标函数，确定最大化或最小化目标；4.用一组决

5、策变量的等式或不等式表示解决问题过程中必须遵循的约束条件 一般形式一般形式目标函数： 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（min） z = c1x1 + c2x2 + + cnxn x1，x2 ， ，xn 0stst. .a11x1 + a12x2 + + a1nxn (或或=,)

6、b1a21x1 + a22x2 + + a2nxn (或或=,) b2an1x1 + a2nx2 + + annxn (或或=,) bn 目标函数目标函数约束约束条件条件决策决策变量变量xj称为该问题的决策变量。称为该问题的决策变量。资源拥资源拥有量有量价值价值系数系数在目标函数中在目标函数中xj的系数的系数cj称为称为该决策变量的价值系数。该决策变量的价值系数。技术系技术系数或工数或工艺系数艺系数aij 称为该问题的技术称为该问题的技术系数或工艺系数。由所有系数或工艺系数。由所有aij组成的矩阵称为约束组成的矩阵称为约束方程的方程的系数矩阵系数矩阵。在问题中，在问题中，xj的取值受的取值受m

7、项资项资源的约束，源的约束，bi称为第称为第i项资源项资源的拥有量。的拥有量。其它表示方式其它表示方式x xj j 0 (j=1,2, 0 (j=1,2, ,n) ,n)stst . . max max（minmin） z =z =nj 1c cj jx xj jnj 1a aijijx xj j ( (或或=,) b=,) bi i (i=1,2, (i=1,2, ,m) ,m) max max（minmin） z =z =X X 0 0stst . .CX C=CX C=（c c1 1 , , c c2 2 , , , c, cn n ）P Pj jx xj j ( (或或=,) b=,)

8、 b用用向向量量表表达达nj 1P Pj j= =（a a1j 1j , , a a2j 2j , , , a , anjnj）T Tb=b=（b b1 1 , , b b2 2 , , , b , bm m）T T简简化化表表示示X=X=（x x1 1 , , x x2 2 , , , x , xn n）T T其中其中X X 0 0stst . .AX AX ( (或或=,) b=,) b用用矩矩阵阵表表达达A= A= a a11 11 a a12 12 a a1n 1n a a21 21 a a22 22 a a2n 2n a am1 m1 a am2 m2 a amnmn 矩阵矩阵A A

9、称为约束方程组（约束条件）的系数矩阵。称为约束方程组（约束条件）的系数矩阵。 max max（minmin） z =z =C CX X C= C=（c c1 1 , , c c2 2 , , , c , cn n ）例例2-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图图 解解 法法 对于只有两个决策变量的线性规划问题，可以在平面直角坐标系上作图表示线

10、性规划问题的有关概念，并求解。 下面通过例1详细讲解其方法：图解线性规划问题步骤 第一步，画直角坐标系 第二步，根据约束条件画可行域 第三步，画过坐标原点的目标函数线，斜率为-c1/c2 第四步，确定目标函数值的增大（减小）方向 第五步，让目标函数沿着增大（减小）方向平行移动，与可行域相交且有最大（最小）目标函数值的顶点，即为线性规划问题的最优解和值。x1x2z=20000=50 x1+100 x2图z=27500=50 x1+100 x2z=0=50 x1+100 x2z=10000=50 x1+100 x2CBADE二元一次不等式（组）表示的平面区域的确定 怎样判断二元一次不等式 表示的是

11、直线 哪一侧的平面区域？ 0CByAx0CByAx可以用“选点法”确定具体区域：任选一个不在直线上的点，检验它的坐标是否满足所给的不等式若适合，则该点所在的一侧即为不等式所表示的平面区域；否则，直线的另一侧为所求的平面区域 画出下列不等式所表示的平面区域： （1）y-2x+1 （2）x-y+20 (1) x0 (2) 6x+5y22 (3)yx 2图图 解解 法法 (1)分别取决策变量X1 , X2 为坐标向量建立直角坐标系。在直角坐标系里，图上任意一点的坐标代表了决策变量的一组值，例1的每个约束条件都代表一个半平面。x2x1X20X2=0 x2x1X10X1=02图图 解解 法法（2）对每个

12、不等式(约束条件)，先取其等式在坐标系中作直线，然后确定不等式所决定的半平面。100200300100200300 x1+x2300 x1+x2=3001001002002x1+x24002x1+x2=4003002003004002图图 解解 法法（3）把五个图合并成一个图，取各约束条件的公共部分，如图2-1所示。100100 x2250 x2=250200300200300 x1x2x2=0 x1=0 x2=250 x1+x2=3002x1+x2=400图2-12图图 解解 法法（4）目标函数z=50 x1+100 x2，当z取某一固定值时得到一条直线，直线上的每一点都具有相同的目标函数值

13、，称之为“等值线”。平行移动等值线，当移动到B点时，z在可行域内实现了最大化。A，B，C，D，E是可行域的顶点，对有限个约束条件则其可行域的顶点也是有限的。x1x2z=20000=50 x1+100 x2图2-2z=27500=50 x1+100 x2z=0=50 x1+100 x2z=10000=50 x1+100 x2CBADE21112100 xxZ 斜截式价值系数的符号与目标函数直线族的平行移动 写成斜截式比较容易弄清楚移动方向 Z=50 x1+100 x2 （+，+）求最大右上方移动，求最小左下方移动 Z=-50 x1-100 x2 （-， -）求最大左下方移动，求最小右上方移动 Z

14、=-50 x1+100 x2 （-， +）求最大左上方移动，求最小右下方移动 Z=50 x1-100 x2 （+， -）求最大右下方移动，求最小左上方移动21112100 xxZ21112100 xxZ 21112100 xxZ 21112100 xxZx1x2O1020304010203040(300,400)(15,10)最优解最优解X=(15,10)最优值最优值Z=850040221xx305 . 121xx0, 0305 . 1402212121xxxxxx例例2-212max300400Zxx246x1x2246最优解最优解X=(3,1)最优值最优值Z=5(3,1)006346321

15、212121xxxxxxxx、min Z=x1+2x2例例2-3(1,2)246x1x2246X（2）（3,1）X（1）（1,3）(5,5)006346321212121xxxxxxxx、min Z=5x1+5x2例例2-4有无穷多个最优解有无穷多个最优解即具有多重解即具有多重解,通解为通解为 01 ,)1 ()2() 1 (XXX 当当=0.5时时=(x1,x2)=0.5(1,3)+0.5(3,1)=(2,2) 246x1x2246(1,2)006346321212121xxxxxxxx、无界解无界解(无最优解无最优解)max Z=x1+2x2例例2-5x1x2O10203040102030

16、4050500,050305 .140221212121xxxxxxxx无可行解无可行解即无最优解即无最优解max Z=10 x1+4x2例例2-6由以上例题可知，线性规划的解有由以上例题可知，线性规划的解有4种形式种形式：1.有唯一最优解有唯一最优解(例例2-2例例2-3)2.有多重解有多重解(例例2-4)3.有无界解有无界解(例例2-5)4.无可行解无可行解(例例2-6)1、2情形为有最优解情形为有最优解3、4情形为无最优解情形为无最优解2图图 解解 法法 重要结论： 如果线性规划有最优解，则一定可以在可行域的某个顶点上找到最优解； 无穷多个最优解，在边界上取得。若将例2-1中的目标函数变

17、为max z=50 x1+50 x2，则线段BC上的所有点都代表了最优解； 无界解。即可行域的范围延伸到无穷远，目标函数值可以无穷大或无穷小。一般来说，这说明模型有错，忽略了一些必要的约束条件； 无可行解。若在例2-1的数学模型中再增加一个约束条件4x1+3x21200，则可行域为空域，不存在满足约束条件的解，当然也就不存在最优解了。进进 一一 步步 讨讨 论论 例例2 2 某公司由于生产需要，共需要A，B两种原料至少350吨（A，B两种材料有一定替代性），其中A原料至少购进125吨。但由于A，B两种原料的规格不同，各自所需的加工时间也是不同的，加工每吨A原料需要2个小时，加工每吨B原料需要1

18、小时，而公司总共有600个加工小时。又知道每吨A原料的价格为2万元，每吨B原料的价格为3万元，试问在满足生产需要的前提下，在公司加工能力的范围内，如何购买A，B两种原料，使得购进成本最低？进进 一一 步步 讨讨 论论解：目标函数： Min f = 2x1 + 3 x2 约束条件：s.t. x1 + x2 350 x1 125 2 x1 + x2 600 x1 , x2 0 采用图解法。如下图：得Q点坐标（250，100）为最优解。100200300 400 500 600100200300400600500 x1 =125x1+x2 =3502x1+3x2 =8002x1+3x2 =9002x

19、1+x2 =6002x1+3x2 =1200 x1 x2 Q3线性规划的标准化线性规划的标准化标准化便于代数求解，为后面单纯形法求解作准备。标准化便于代数求解，为后面单纯形法求解作准备。 一般形式一般形式目标函数： 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

20、= 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 03线性规划的标准化线性规划的标准化 可以看出，线性规划的标准形式有如下四个特点：目标最大化；约束为等式；决策变量均非负；右端项非负。 对于各种非标准形式的线性规划问题，我们总可以通过以下变换，将其转化为标准形式:3线性规划的标准化线性规划的标准化1、决策变量不是非负 在标准形式中，必须每一个变量

21、均有非负约束。1）当决策变量xk0，则用-xk代替xk，且xk 02）当某一个变量xj无符号要求时，可以令 xj = xj- xj” 其中 xj0，xj”0 即用两个非负变量之差来表示一个无符号限制的变量，当然xj的符号取决于xj和xj”的大小。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+

22、s = bi3线性规划的标准化线性规划的标准化 当约束条件为 ai1 x1+ai2 x2+ +ain xn bi 时， 类似地令 s=(ai1 x1+ai2 x2+ +ain xn)- bi 显然，s 也具有非负约束，即s0，这时新的约束条件成为 ai1 x1+ai2 x2+ +ain xn-s = bi3线性规划的标准化线性规划的标准化 为了使约束由不等式成为等式而引进的变量s,当不等式为“小于等于”时称为“松弛变量”；当不等式为“大于等于”时称为“剩余变量”。如果原问题中有若干个非等式约束，则将其转化为标准形式时，必须对各个约束引进不同的松弛变量。 松弛变量表示未被充分利用的资源，剩余变量

23、表示超过最低限约束的资源多用量。两者在目标函数中的价值系数均为零。只有决策变量影响到目标函数值。 3线性规划的标准化线性规划的标准化3.极小化目标函数的问题： 设目标函数为 Min f = c1x1 + c2x2 + + cnxn (可以)令 z -f ， 则该极小化问题与下面的极大化问题有相同的最优解，即 Max z = - c1x1 - c2x2 - - cnxn 但必须注意，尽管以上两个问题的最优解相同，但它们最优解的目标函数值（最优值）却相差一个符号，即 Min f - Max z 4.右端项有负值的问题： 在标准形式中，要求右端项必须每一个分量非负。当某一个右端项系数为负时，如 bi

24、0，则把该等式约束两端同时乘以-1。如：x1-4x2-5线性规划标准化的步骤【例】将下列线性规划化为标准型【例】将下列线性规划化为标准型 3213minxxxZ无符号要求、32132132132100)3(523)2(3) 1 (82xxxxxxxxxxxx【解】（）因为【解】（）因为x3无符号要求无符号要求 ，即，即x3取正值也取正值也可取负值，标准型中要求变量非负，所以令可取负值，标准型中要求变量非负，所以令 0,33333 xxxxx其中 (3)第二个约束条件是第二个约束条件是号，在号，在号号 左左端减去剩余变量端减去剩余变量(Surplus variable)x5，x50。也称松驰变。

25、也称松驰变量量3213minxxxZ无符号要求、32132132132100) 3(523)2(3) 1 (82xxxxxxxxxxxx(2) 第一个约束条件是第一个约束条件是号，在号，在左端左端加入松驰变量加入松驰变量 (slack variable) x4，x40,化为等式；化为等式；(4)第三个约束条件是第三个约束条件是号且常数项为负数，因此在号且常数项为负数，因此在左边加入松左边加入松驰变量驰变量x6，x60，同时两边乘以，同时两边乘以1。 （5）目标函数是最小值，为了化为求最大值，令）目标函数是最小值，为了化为求最大值，令Z=Z,得到得到max Z=Z，即当，即当Z达到最小值时达到最

26、小值时Z达到最大值，反之亦然。达到最大值，反之亦然。 综合起来得到下列标准型综合起来得到下列标准型 332133maxxxxxZ 05)(233826543321633215332143321xxxxxxxxxxxxxxxxxxxxxx、当某个约束是绝对值不等式时，将绝对值不等式化为两个不等当某个约束是绝对值不等式时，将绝对值不等式化为两个不等式，再化为等式，例如约束式，再化为等式，例如约束 974321xxx将其化为两个不等式将其化为两个不等式 974974321321xxxxxx再加入松驰变量化为等式。再加入松驰变量化为等式。 对于对于axb(a、b均大于零均大于零)的有界变量化为标准形式

27、有两种方的有界变量化为标准形式有两种方法。法。 一种方法是增加两个约束一种方法是增加两个约束xa及及xb 另一种方法是令另一种方法是令x=xa，则，则axb等价于等价于0 xba，增加，增加一个约束一个约束xba并且将原问题所有并且将原问题所有x用用x= x+a替换。替换。化标准型的步骤总结1、决策变量非负2、约束条件为等式3、目标函数极大化4、右端常数非负4图解法的灵敏度分析图解法的灵敏度分析 灵敏度分析灵敏度分析：建立数学模型和求得最优解后，研究线性规划的一个或多个参数（系数）ci , aij , bj 变化时，对最优解产生的影响。4.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 （*） 时