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

1、管管 理理 运运 筹筹 学学第二章第二章 线性规划的图解法线性规划的图解法 1 1 问题的提出问题的提出 2 2 图解法图解法 3 3 图解法的灵敏度分析图解法的灵敏度分析管管 理理 运运 筹筹 学学第二章第二章 线性规划的图解法线性规划的图解法在管理中一些典型的线性规划运用在管理中一些典型的线性规划运用合理利用线材问题：如何在保证消费的条件下，下料最少合理利用线材问题：如何在保证消费的条件下，下料最少配料问题：在原料供应量的限制下如何获取最大利润配料问题：在原料供应量的限制下如何获取最大利润投资问题：从投资工程中选取方案，使投资报答最大投资问题：从投资工程中选取方案，使投资报答最大产品消费方

2、案：合理利用人力、物力、财力等，使获利最大产品消费方案：合理利用人力、物力、财力等，使获利最大劳动力安排：用最少的劳动力来满足任务的需求劳动力安排：用最少的劳动力来满足任务的需求运输问题：如何制定调运方案，使总运费最小运输问题：如何制定调运方案，使总运费最小线性规划的组成：线性规划的组成：目的函数目的函数 Max F Max F 或或 Min F Min F约束条件约束条件 s.t. (subject to) s.t. (subject to) 满足于满足于决策变量决策变量 用符号来表示可控制的要素用符号来表示可控制的要素管管 理理 运运 筹筹 学学1 1 问题的提出问题的提出例例1. 某工厂

3、在方案期内要安排某工厂在方案期内要安排、两种产品的消费，知消费单位产品两种产品的消费，知消费单位产品所需的设备台时及所需的设备台时及A、B两种原资料的耗费、资源的限制，如下表：两种原资料的耗费、资源的限制，如下表：问题：工厂应分别消费多少单位问题：工厂应分别消费多少单位、产品才干使工厂获利最多？产品才干使工厂获利最多？线性规划模型：线性规划模型： 目的函数：目的函数：Max z = 50 x1 + 100 x2 利润利润 约束条件：约束条件：s.t. x1 + x2 300设备数量约束设备数量约束 2 x1 + x2 400 原料原料A数量约束数量约束 x2 250 原料原料B数量约束数量约束

4、 x1 , x2 0管管 理理 运运 筹筹 学学1 1 问题的提出问题的提出 建模过程建模过程 1.了解要处理的问题，了解解题的目的和条件；了解要处理的问题，了解解题的目的和条件； 2.定义决策变量定义决策变量 x1 ，x2 ， ，xn ，每一组值表示一，每一组值表示一个方案；个方案； 3.用决策变量的线性函数方式写出目的函数，确定最大化用决策变量的线性函数方式写出目的函数，确定最大化或最小化目的；或最小化目的； 4.用一组决策变量的等式或不等式表示处理问题过程中必用一组决策变量的等式或不等式表示处理问题过程中必需遵照的约束条件需遵照的约束条件 普通方式普通方式 目的函数：目的函数： Max

5、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 管管 理理 运运 筹筹 学学例例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)得到最优解：得到

6、最优解： x1 = 50， x2 = 250 最优目的值最优目的值 z = 275002 图图 解解 法法 对于只需两个决策变量的线性规划问题，可以在平面直角坐标系上作图表示线性规划问题的有关概念，并求解。 下面经过例1详细讲解其方法：管管 理理 运运 筹筹 学学2 图图 解解 法法 (1)分别取决策变量X1 , X2 为坐标向量建立直角坐标系。在直角坐标系里，图上恣意一点的坐标代表了决策变量的一组值，例1的每个约束条件都代表一个半平面。x2x1X20X2=0 x2x1X10X1=0管管 理理 运运 筹筹 学学2 图图 解解 法法2对每个不等式(约束条件)，先取其等式在坐标系中作直线，然后确定

7、不等式所决议的半平面。100200300100200300 x1+x2300 x1+x2=3001001002002x1+x24002x1+x2=400300200300400 x1x1x2x2管管 理理 运运 筹筹 学学2 图图 解解 法法3把五个图合并成一个图，取各约束条件的公共部分，如图2-1所示。100100 x2250 x2=250200300200300 x1x2x2=0 x1=0 x2=250 x1+x2=3002x1+x2=400图2-1x2x1CBADE管管 理理 运运 筹筹 学学2 图图 解解 法法4目的函数z=50 x1+100 x2，当z取某一固定值时得到一条直线，直线

8、上的每一点都具有一样的目的函数值，称之为“等值线。平行挪动等值线，当挪动到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 x2CBADE管管 理理 运运 筹筹 学学2 图图 解解 法法 线性规划的规范化内容之一：线性规划的规范化内容之一：引入松驰变量含义是引入松驰变量含义是资源的剩余量资源的剩余量 例例1 1 中引入中引入 s1 s1， s2 s2， s3 s3 模型

9、化为模型化为 目的函数：目的函数：Max z = 50 x1 + 100 x2 + 0 s1 Max z = 50 x1 + 100 x2 + 0 s1 + 0 s2 + 0 s3+ 0 s2 + 0 s3 约束条件：约束条件：s.t. x1 + x2 + s1 s.t. x1 + x2 + s1 = 300= 300 2 x1 + 2 x1 + x2 + s2 = 400 x2 + s2 = 400 x2 + s3 = 250 x2 + s3 = 250 x1 , x2 , s1 , x1 , x2 , s1 , s2 , s3 0s2 , s3 0 对于最优解对于最优解 x1 =50 x2

10、 = 250 x1 =50 x2 = 250 ， s1 = 0 s2 s1 = 0 s2 =50 s3 = 0=50 s3 = 0 阐明：消费阐明：消费5050单位单位产品和产品和250250单位单位产品将耗费完产品将耗费完一切一切 能够的设备台时数及原料能够的设备台时数及原料B B，但原料，但原料A A那么还剩余那么还剩余5050千克。千克。管管 理理 运运 筹筹 学学2 图图 解解 法法 重要结论： 假设线性规划有独一最优解，那么一定有一个可行域的顶点对应最优解； 无穷多个最优解。假设将例1中的目的函数变为max z=50 x1+50 x2，那么线段BC上的一切点都代表了最优解；管管 理理

11、 运运 筹筹 学学x1x2图2-2z=0=50 x1+50 x2CBADE管管 理理 运运 筹筹 学学2 图图 解解 法法 重要结论： 无界解。即可行域的范围延伸到无穷远，目的函数值可以无穷大或无穷小。普通来说，这阐明模型有错，忽略了一些必要的约束条件； 无可行解。假设在例1的数学模型中再添加一个约束条件4x1+3x21200，那么可行域为空域，不存在满足约束条件的解，当然也就不存在最优解了。管管 理理 运运 筹筹 学学x1x2z=20000=50 x1+100 x2图2-2z=27500=50 x1+100 x2z=0=50 x1+100 x2z=10000=50 x1+100 x2CBAD

12、E管管 理理 运运 筹筹 学学进进 一一 步步 讨讨 论论 例例2 2 某公司由于消费需求，共需求某公司由于消费需求，共需求A A，B B两种原料至少两种原料至少350350吨吨A A，B B两种资料有一定替代性，其中两种资料有一定替代性，其中A A原料至少购进原料至少购进125125吨。但由于吨。但由于A A，B B两种原料的规格不同，各自所需的加工时间两种原料的规格不同，各自所需的加工时间也是不同的，加工每吨也是不同的，加工每吨A A原料需求原料需求2 2个小时，加工每吨个小时，加工每吨B B原料需原料需要要1 1小时，而公司总共有小时，而公司总共有600600个加工小时。又知道每吨个加工

13、小时。又知道每吨A A原料的原料的价钱为价钱为2 2万元，每吨万元，每吨B B原料的价钱为原料的价钱为3 3万元，试问在满足消费需万元，试问在满足消费需要的前提下，在公司加工才干的范围内，如何购买要的前提下，在公司加工才干的范围内，如何购买A A，B B两种两种原料，使得购进本钱最低？原料，使得购进本钱最低？管管 理理 运运 筹筹 学学进进 一一 步步 讨讨 论论解：目的函数： Min f = 2x1 + 3 x2 购买本钱约束条件：s.t. x1 + x2 350 总量约束 x1 125 A量的约束 2 x1 + x2 600 加工工时的约束 x1 , x2 0 管管 理理 运运 筹筹 学学

14、进进 一一 步步 讨讨 论论采用图解法。如以下图：得Q点坐标250，100为最优解。100200300400500600100200300400600500 x1 =125x1+x2 =3502x1+3x2 =8002x1+3x2 =9002x1+x2 =6002x1+3x2 =1200 x1 x2 Q管管 理理 运运 筹筹 学学3 图解法的灵敏度分析图解法的灵敏度分析线性规划的规范化线性规划的规范化普通方式普通方式目的函数：目的函数： Max Min z = c1 x1 + c2 x2 + + cn xn 约束条件：约束条件： s.t. a11 x1 + a12 x2 + + a1n xn

15、=, 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 0管管 理理 运运 筹筹 学学3 图解法的灵敏度分析图解法的灵敏

16、度分析 可以看出，线性规划的规范方式有如下四个特点：目的最大化；约束为等式；决策变量均非负；右端项非负。 对于各种非规范方式的线性规划问题，我们总可以经过以下变换，将其转化为规范方式:管管 理理 运运 筹筹 学学3 图解法的灵敏度分析图解法的灵敏度分析1.极小化目的函数的问题： 设目的函数为 Min f = c1x1 + c2x2 + + cnxn (可以)令 z -f ， 那么该极小化问题与下面的极大化问题有一样的最优解，即 Max z = - c1x1 - c2x2 - - cnxn 但必需留意，虽然以上两个问题的最优解一样，但它们最优解的目的函数值却相差一个符号，即 Min f - Ma

17、x z管管 理理 运运 筹筹 学学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 = bi管管 理理 运运 筹筹 学学3 图解法的灵敏度分析图解法的灵敏度分析 当约束条件为 ai1 x1+ai2 x2+ +ain xn bi 时， 类似地令 s=(ai1 x1+ai2 x2+ +ai

18、n xn)- bi 显然，s 也具有非负约束，即s0，这时新的约束条件成为 ai1 x1+ai2 x2+ +ain xn-s = bi管管 理理 运运 筹筹 学学3 图解法的灵敏度分析图解法的灵敏度分析 为了使约束由不等式成为等式而引进的变量s,当不等式为“小于等于时称为“松弛变量；当不等式为“大于等于时称为“剩余变量。假设原问题中有假设干个非等式约束，那么将其转化为规范方式时，必需对各个约束引进不同的松弛变量。 3.右端项有负值的问题： 在规范方式中，要求右端项必需每一个分量非负。当某一个右端项系数为负时，如 bi0，那么把该等式约束两端同时乘以-1，得到：-ai1 x1-ai2 x2- -

19、ain xn = -bi。管管 理理 运运 筹筹 学学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。管管 理理 运运 筹筹 学学3 图解法的灵敏度分析图解法的灵敏度分析经过以上变换，可

20、以得到以下规范方式的线性规划问题： 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 0管管 理理 运运 筹筹 学学3 图解法的灵敏度分析图解法的灵敏度分析4. * 变量无符号限制的问题*： 在规范方式中，必需每一个变量均有非负约束。当某一个变量xj没有非负约束时，可以令 xj = xj- xj 其中 xj0，xj0 即用两个非负变量之差来表示一个无符号限制的变量，当然xj的符号取决于xj和xj的大小。管管 理理 运运 筹筹 学学3 图解法的

21、灵敏度分析图解法的灵敏度分析例：将以下线性规划问题转化为规范方式 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 管管 理理 运运 筹筹 学学3 图解法的灵敏度分析图解法的灵敏度分析经过以上变换，可以得到以下规

22、范方式的线性规划问题： 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 0管管 理理 运运 筹筹 学学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-4x

23、3 其次思索约束，有2个不等式约束，引进松弛变量 x4，x5 0。 第三个约束条件的右端值为负，在等式两边同时乘-1。 变量x3没有非负约束，可以令 x3= x3- x3 其中 x30，x30管管 理理 运运 筹筹 学学3 图解法的灵敏度分析图解法的灵敏度分析经过以上变换，可以得到以下规范方式的线性规划问题： Max z = - 2x1 + 3 x2 - 4x3- x3 s.t. 3x1+4x2-5x3- x3 +x4 = 6 2x1 +x3- x3 -x5= 8 -x1 -x2 -x3- x3 = 9 x1 ,x2 , x3, x3 ,x4 ,x5 0管管 理理 运运 筹筹 学学3 图解法的

24、灵敏度分析图解法的灵敏度分析 灵敏度分析：建立数学模型和求得最优解后，研讨线性规灵敏度分析：建立数学模型和求得最优解后，研讨线性规划的一个或多个参数系数划的一个或多个参数系数ci , aij , bj 变化时，对最优解产变化时，对最优解产生的影响。生的影响。3.1 目的函数中的系数目的函数中的系数 ci 的灵敏度分析的灵敏度分析 思索例思索例1的情况，的情况， ci 的变化只影响目的函数等值线的斜率，的变化只影响目的函数等值线的斜率，目的函数目的函数 z = 50 x1 + 100 x2 在在 z = x2 (x2 = z 斜率为斜率为0 ) 到到 z = x1 + x2 (x2 = -x1

25、+ z 斜斜率为率为 -1 )之间时，原最优解之间时，原最优解 x1 = 50，x2 = 100 仍是最优解。仍是最优解。普通情况：普通情况： z = c1 x1 + c2 x2 写成斜截式写成斜截式 x2 = - (c1 / c2 ) x1 + z / c2 目的函数等值线的斜率为目的函数等值线的斜率为 - (c1 / c2 ) ， 当当 -1 - (c1 / c2 ) 0 * 时，原最优解仍是最优解。时，原最优解仍是最优解。管管 理理 运运 筹筹 学学x1x2z=20000=50 x1+100 x2图2-2z=27500=50 x1+100 x2z=0=50 x1+100 x2z=10000=50 x1+100 x2CBADE管管 理理 运运 筹筹 学学3 图解法的灵敏度分析图解法的灵敏度分析 假设产品的利润100元不变，即 c2 = 100，代到式*并整理得 0 c1 100 假设产品的利润 50 元不变，即 c1 =