《运筹学图解法》PPT课件.ppt

《《运筹学图解法》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《运筹学图解法》PPT课件.ppt（73页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Linear ProgrammingLinear Programming线线 性性 规规 划划Chapter 2Chapter 2Linear ProgrammingLinear Programming 在在人人们们的的生生产产实实践践中中，经经常常会会遇遇到到如如何何利利用用现现有有资资源源来来安安排排生生产产，以以取取得得最最大大经经济济效效益益的的问问题题。此此类类问问题题构构成成了了运运筹筹学学的的一一个个重重要要分分支支数数学学规规划划，而而线线性性规规划划(Linear(Linear Programming Programming 简简记记LP)LP)则是数学规划的一个重要分支。则

2、是数学规划的一个重要分支。自自从从19471947年年G.G.B.B.Dantzig Dantzig 提提出出求求解解线线性性规规划划的的单单纯纯形形方方法法以以来来，线线性性规规划划在在理理论论上上趋趋向向成成熟熟，在在实实用用中中日日益益广广泛泛与与深深入入。特特别别是是在在计计算算机机能能处处理理成成千千上上万万个个约约束束条条件件和和决决策策变变量量的的线线性性规规划划问问题题之之后后，线线性性规规划划的的适适用用领领域域更更为为广广泛泛了了，已已成成为为现现代代管管理理中中经经常采用的基本方法之一。常采用的基本方法之一。2.1 2.1 问题的提出问题的提出2.3 2.3 图解法的灵敏

3、度分析图解法的灵敏度分析2.2 2.2 线性规划的图解法线性规划的图解法 第一节第一节第一节第一节 问题的提出问题的提出1.1、问题的提出、问题的提出例例1:1:某工厂用三种原料生产三种产品，已知某工厂用三种原料生产三种产品，已知的条件如下表所示，试制订总利润最大的生的条件如下表所示，试制订总利润最大的生产计划产计划453单位产品的利润单位产品的利润（千元）（千元）2000523原料原料P3800420原料原料P21500032原料原料P1原料可用量原料可用量（公斤（公斤/日）日）产品产品Q3产品产品Q2产品产品Q1单位产品所需原单位产品所需原料数量（公斤）料数量（公斤）可控因素：可控因素：每

4、天生产三种产品的数量，每天生产三种产品的数量，分别设为：分别设为：受制条件：受制条件：每天原料的需求量不超过可用量每天原料的需求量不超过可用量 目标：目标：每天的利润最大每天的利润最大 利润函数：利润函数：原料原料 :原料原料 :蕴含约束：蕴含约束：产量非负产量非负 453单单位位产产品的利品的利润润（千元）（千元）2000523原料原料P3800420原料原料P21500032原料原料P1原料可用量原料可用量（公斤（公斤/日）日）产产品品Q3产产品品Q2产产品品Q1单单位位产产品所需原料品所需原料数量（公斤）数量（公斤）原料原料 :综上，本问题可用如下模型描述：综上，本问题可用如下模型描述：

5、目标函数：目标函数：约束条件：约束条件：1)问题用一组决策变量问题用一组决策变量 表示某一方案；决策变量的值就代表表示某一方案；决策变量的值就代表一个具体的方案，一般这些变量是非一个具体的方案，一般这些变量是非负的。负的。从以上例可以看出，其特征是：从以上例可以看出，其特征是：3.都有一个要达到的目标，它可以用决都有一个要达到的目标，它可以用决 策变量的线性函数来表示。按问题的策变量的线性函数来表示。按问题的 不同要求，目标函数实现最大化或最不同要求，目标函数实现最大化或最 小化。小化。2.存在一定的约束条件，这些约束都可存在一定的约束条件，这些约束都可以用一组线性等式或线性不等式表示。以用一

6、组线性等式或线性不等式表示。满足以上三个条件的数满足以上三个条件的数学模型称为学模型称为线性规划的数线性规划的数学模型，学模型，其一般形式为其一般形式为:目标函数目标函数约束条件约束条件注解：注解：o 称为决策变量。称为决策变量。o上述规划中的决策变量也可以是无约束的。上述规划中的决策变量也可以是无约束的。o满足所有约束条件的一组决策变量称为满足所有约束条件的一组决策变量称为可行解可行解o最优解所对应的目标函数值称为最优解所对应的目标函数值称为最优值最优值o所有可行解组成的集合称为所有可行解组成的集合称为可行域可行域o使目标函数达到最大的一组决策变量称为使目标函数达到最大的一组决策变量称为最优

7、解最优解 第二节第二节第二节第二节 线性规划的图解法线性规划的图解法图解法图解法缺点缺点：只能求解两个决策变只能求解两个决策变量的线性规划量的线性规划优点优点：简单、直观、帮助我：简单、直观、帮助我 们了解求解线性规划的原理们了解求解线性规划的原理2.2、图解法、图解法要点：要点：约束条件用坐标系中的半空间或直线的约束条件用坐标系中的半空间或直线的 交表示交表示 变量用直角坐标系中的点表示变量用直角坐标系中的点表示 目标函数用一组等值线表示，沿着增加目标函数用一组等值线表示，沿着增加 或减少的方向移动或减少的方向移动等值线等值线例例1:1:最优解（最优解（4 4，2 2）可行域可行域BA结论：

8、结论：可行域一定是凸集可行域一定是凸集若最优解存在，则最优解一定若最优解存在，则最优解一定在凸集的顶点达到在凸集的顶点达到 上例中求得上例中求得 问题的解是唯一的，问题的解是唯一的，但对一般线性规划问题，求解结果还但对一般线性规划问题，求解结果还可能出现以下几种情况：可能出现以下几种情况：1、无穷多最优解（多重解）、无穷多最优解（多重解）若将上例中的目标函数若将上例中的目标函数 改为则表示目标函数中以参数的等值线改为则表示目标函数中以参数的等值线与约束条件的边界平行，当值由小变大与约束条件的边界平行，当值由小变大时，将与此边界重合，线段时，将与此边界重合，线段AB上的所有上的所有点都是最优解。

9、点都是最优解。2、无界解、无界解 对下述问题用图解法求解结果见下图：对下述问题用图解法求解结果见下图：由图可知，该问题的可行域无界，目由图可知，该问题的可行域无界，目标函数可以增大到无穷大，称这种情况标函数可以增大到无穷大，称这种情况为无界解或无最优解。为无界解或无最优解。3 3、无可行解、无可行解 在上述问题中增加一个约束条件，在上述问题中增加一个约束条件，该问题可行域为空集，即无可行解，从而不存在最优解。该问题可行域为空集，即无可行解，从而不存在最优解。总之，可能出现的情况：可行域是空集可行域是空集可行域无界无最优解可行域无界无最优解最优解存在且唯一，则一定在顶点上达到最优解存在且唯一，则

10、一定在顶点上达到最优解存在且不唯一，一定存在顶点是最优解存在且不唯一，一定存在顶点是 最优解最优解注：注：图解法简便、直观，有助于了解图解法简便、直观，有助于了解线性规划问题求解的基本原理，但是当线性规划问题求解的基本原理，但是当变量的个数多于三个时，它就无能为力变量的个数多于三个时，它就无能为力了，因此我们将介绍单纯形法。为了便了，因此我们将介绍单纯形法。为了便于讨论，我们先规定线性规划问题的数于讨论，我们先规定线性规划问题的数学模型的标准形式。学模型的标准形式。线性规划问题的标准形式线性规划问题的标准形式线性规划的一般形式线性规划的一般形式1.3、线性规划问题的标准形式线性规划问题的标准形

11、式 线性规划有各种不同的形式，线性规划有各种不同的形式，现将各种形式都统一变为如下的现将各种形式都统一变为如下的标准形式：标准形式：目标函数为最大目标函数为最大约束为约束为等式等式决策变量大于等于决策变量大于等于0右端常数项大于右端常数项大于0或者或者（向量和矩阵符号表述）（向量和矩阵符号表述）其中：其中：向量向量 对应的决策变量是对应的决策变量是用矩阵表述：用矩阵表述：其中其中-称为系数矩阵称为系数矩阵 -称为资源向量称为资源向量-称为价值向量称为价值向量-称为决策变量向量称为决策变量向量II.目标转换目标转换 令自由变量令自由变量 其中其中 求最小可以等价的转换为求最大求最小可以等价的转换

12、为求最大I.变量转换变量转换(若出现自由变量若出现自由变量 )将一般形式转换为标准形式将一般形式转换为标准形式III.约束转换（实例）约束转换（实例）1)不等式变等式不等式变等式松弛变量松弛变量剩余变量剩余变量或者：或者：2)不等式变不等式不等式变不等式3)等式变不等式等式变不等式例例1:1:将下列数学模型变为标准型：将下列数学模型变为标准型：解：解：(1)(1)、原式的标准型为：、原式的标准型为：(2)(2)、令令 则可得原则可得原 规划的标准型为：规划的标准型为：注意：注意：在将在将求最小问题化为标准型时，一求最小问题化为标准型时，一 定注意所求的最优值互为相反定注意所求的最优值互为相反数

13、。数。在不在不引起混淆的情况下，松弛变量、引起混淆的情况下，松弛变量、剩余变量与决策变量的符号不加区剩余变量与决策变量的符号不加区 分分,均用均用 表示表示。松弛变量和剩余变量的解释例例1.某工厂在计划期内要安排、两种产品的生产，已知生产单位产品所需的设备台时及A、B两种原材料的消耗、资源的限制，如下表：问题：工厂应分别生产多少单位、产品才能使工厂获利最多？解：设工厂应分别生产两种产品解：设工厂应分别生产两种产品 个单个单位，则该问题的线性模型为：位，则该问题的线性模型为：可行域可行域BA最优解（最优解（5050，250250）用图解法可以求得其最优解为：用图解法可以求得其最优解为：松弛变量：

14、没有使用的资源或能力松弛变量：没有使用的资源或能力对原线性规对原线性规划标准化：划标准化：例例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小时，小时，而公司总共有而公司总共有6

15、00600个加工小时。又知道每吨个加工小时。又知道每吨A A原料的价格为原料的价格为2 2万元，每吨万元，每吨B B原料的价格为原料的价格为3 3万元，试问在满足生产需要的前提下，在万元，试问在满足生产需要的前提下，在公司加工能力的范围内，如何购买公司加工能力的范围内，如何购买A A，B B两两种原料，使得购进成本最低？种原料，使得购进成本最低？设购进原料A的数量为设购进原料B的数量为1x采用图解法求解得：采用图解法求解得：剩余变量：超过资源下线的超过量剩余变量：超过资源下线的超过量图解法的灵敏度分析 灵敏度分析：建立数学模型和求得最优解后，研究线性规划的一个或多个参数（系数）变化时，对最优解

16、产生的影响。例例1.某工厂在计划期内要安排某工厂在计划期内要安排、两种产两种产品的生产，已知生产单位产品所需的设备台品的生产，已知生产单位产品所需的设备台时及时及A、B两种原材料的消耗、资源的限制，两种原材料的消耗、资源的限制，如下表：如下表：问题：工厂应分别生产多少单位问题：工厂应分别生产多少单位、产品才能产品才能使工厂获利最多？使工厂获利最多？解：设工厂应分别生产两种产品解：设工厂应分别生产两种产品 个单个单位，则该问题的线性模型为：位，则该问题的线性模型为：可行域可行域BA最优解（最优解（5050，250250）用图解法可以求得其最优解为：用图解法可以求得其最优解为：现在我们对其系数加以

17、分析：现在我们对其系数加以分析：对本例而言，对本例而言，的变化只影响目标函数等值线的的变化只影响目标函数等值线的斜率，目标函数斜率，目标函数 在直线在直线 (斜率为斜率为0)0)到到 (斜率为斜率为-1)-1)之之间时，原最优解间时，原最优解 x x1 1=50=50，x x2 2=100 =100 仍是最优解。仍是最优解。一、一、目标函数中的系数目标函数中的系数 的灵敏度分析的灵敏度分析BA一般情况：一般情况：写成斜截式即：写成斜截式即：目标函数等值线的斜率为目标函数等值线的斜率为 当当 （*）时，原最优解仍是最优解。时，原最优解仍是最优解。假设产品的利润100元不变，即 代入到式（*）并整

18、理得：假设产品的利润50 元不变，即 代到式（*）并整理得：假若产品、的利润均改变，则可直接用式（*）来判断。假设产品、的利润分别为60元、55元，则有：那么，最优解为直线 的交点：二、约束条件中右边系数 的灵敏度分析当约束条件中右边系数 变化时，线性规划的可行域发生变化，可能引起最优解的变化。BA（60，250）变化后的总利润-变化前的总利润 =增加的利润:增加的总利润：增加的总利润：(5060+100250)-(50 50+100 250)=500，说明：在一定范围内每增加（减少）1个台时的设备能力就可增加（减少）50元利润，称为该约束条件的对偶价格。单位资源增加的利润：500/10=50

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