《运筹学图解法.ppt》由会员分享，可在线阅读，更多相关《运筹学图解法.ppt（73页珍藏版）》请在三一文库上搜索。
1、,Linear Programming,线 性 规 划 Chapter 2 Linear Programming,在人们的生产实践中，经常会遇到如何利用现有资源来安排生产，以取得最大经济效益的问题。此类问题构成了运筹学的一个重要分支数学规划，而线性规划(Linear Programming 简记LP)则是数学规划的一个重要分支。,自从1947年G. B. Dantzig 提出求解线性规划的单纯形方法以来，线性规划在理论上趋向成熟，在实用中日益广泛与深入。特别是在计算机能处理成千上万个约束条件和决策变量的线性规划问题之后，线性规划的适用领域更为广泛了，已成为现代管理中经常采用的基本方法之一。,2
2、.1 问题的提出,2.3 图解法的灵敏度分析,2.2 线性规划的图解法,1.1、问题的提出,例1: 某工厂用三种原料生产三种产品，已知的条件如下表所示，试制订总利润最大的生产计划,可控因素：每天生产三种产品的数量，分别设为：,受制条件：每天原料的需求量不超过可用量,目标：每天的利润最大 利润函数：,原料 :,原料 :,蕴含约束：产量非负,原料 :,问题用一组决策变量 表示某一方案；决策变量的值就代表一个具体的方案，一般这些变量是非负的。,从以上例可以看出，其特征是：,3. 都有一个要达到的目标，它可以用决 策变量的线性函数来表示。按问题的 不同要求，目标函数实现最大化或最 小化。,存在一定的约
3、束条件，这些约束都可以用一组线性等式或线性不等式表示。,满足以上三个条件的数学模型称为线性规划的数学模型，其一般形式为:,目标函数,约束条件,上述规划中的决策变量也可以是无约束的。,满足所有约束条件的一组决策变量称为可行解,最优解所对应的目标函数值称为最优值,所有可行解组成的集合称为可行域,使目标函数达到最大的一组决策变量称为最优解,图解法,缺点： 只能求解两个决策变量的线性规划,优点：简单、直观、帮助我 们了解求解线性规划的原理,2.2、图解法,要点：,约束条件用坐标系中的半空间或直线的 交表示,变量用直角坐标系中的点表示,目标函数用一组等值线表示，沿着增加 或减少的方向移动,例1:,B,A
4、,结论：,可行域一定是凸集,若最优解存在，则最优解一定在凸集的顶点达到,上例中求得 问题的解是唯一的，但对一般线性规划问题，求解结果还可能出现以下几种情况：,1、无穷多最优解（多重解） 若将上例中的目标函数 改为则表示目标函数中以参数的等值线与约束条件的边界平行，当值由小变大时，将与此边界重合，线段AB上的所有点都是最优解。,2、无界解 对下述问题用图解法求解结果见下图：,由图可知，该问题的可行域无界，目标函数可以增大到无穷大，称这种情况为无界解或无最优解。,3、无可行解 在上述问题中增加一个约束条件， 该问题可行域为空集，即无可行解，从而不存在最优解。,总之，可能出现的情况： 可行域是空集
5、可行域无界无最优解 最优解存在且唯一，则一定在顶点上达到 最优解存在且不唯一，一定存在顶点是 最优解,注：图解法简便、直观，有助于了解 线性规划问题求解的基本原理，但是当 变量的个数多于三个时，它就无能为力 了，因此我们将介绍单纯形法。为了便 于讨论，我们先规定线性规划问题的数 学模型的标准形式。,线性规划的一般形式,1.3、线性规划问题的标准形式,线性规划有各种不同的形式，现将各种形式都统一变为如下的标准形式：,目标函数为最大,约束为等式,决策变量大于等于0,右端常数项大于0,或者,（向量和矩阵符号表述）,用矩阵表述：,其中,目标转换,令自由变量 其中,求最小可以等价的转换为求最大,变量转换
6、(若出现自由变量 ),将一般形式转换为标准形式,约束转换（实例）,不等式变等式,松弛变量,剩余变量,或者：,不等式变不等式,等式变不等式,例1:将下列数学模型变为标准型：,解：,(1)、原式的标准型为：,(2)、令 则可得原 规划的标准型为：,注意：,在将求最小问题化为标准型时，一 定注意所求的最优值互为相反数。,在不引起混淆的情况下，松弛变量、 剩余变量与决策变量的符号不加区 分,均用 表示。,例1. 某工厂在计划期内要安排、两种产品的生产，已知生产单位产品所需的设备台时及A、B两种原材料的消耗、资源的限制，如下表： 问题：工厂应分别生产多少单位、产品才能使工厂获利最多？,解：设工厂应分别生
7、产两种产品 个单位，则该问题的线性模型为：,B,用图解法可以求得其最优解为：,松弛变量：没有使用的资源或能力,对原线性规 划标准化：,例2 某公司由于生产需要，共需要A，B两种原料至少350吨（A，B两种材料有一定替代性），其中A原料至少购进125吨。但由于A，B两种原料的规格不同，各自所需的加工时间也是不同的，加工每吨A原料需要2个小时，加工每吨B原料需要1小时，而公司总共有600个加工小时。又知道每吨A原料的价格为2万元，每吨B原料的价格为3万元，试问在满足生产需要的前提下，在公司加工能力的范围内，如何购买A，B两种原料，使得购进成本最低？,设购进原料A的数量为 设购进原料B的数量为,采用
8、图解法求解得：,剩余变量：超过资源下线的超过量,灵敏度分析：建立数学模型和求得最优解后，研究线性规划的一个或多个参数（系数） 变化时，对最优解产生的影响。,例1. 某工厂在计划期内要安排、两种产品的生产，已知生产单位产品所需的设备台时及A、B两种原材料的消耗、资源的限制，如下表：,问题：工厂应分别生产多少单位、产品才能使工厂获利最多？,解：设工厂应分别生产两种产品 个单位，则该问题的线性模型为：,B,对本例而言， 的变化只影响目标函数等值线的斜率，目标函数 在直线 (斜率为0 )到 (斜率为 -1 )之间时，原最优解 x1 = 50，x2 = 100 仍是最优解。,一、 目标函数中的系数 的灵
9、敏度分析,一般情况： 写成斜截式即： 目标函数等值线的斜率为 当 （*） 时，原最优解仍是最优解。,假设产品的利润100元不变，即 代入到式（*）并整理得： 假设产品的利润50 元不变，即 代到式（*）并整理得：,假若产品、的利润均改变，则可直接用式（*）来判断。假设产品、的利润分别为60元、55元，则有： 那么，最优解为直线 的交点 ：,二、约束条件中右边系数 的灵敏度分析,当约束条件中右边系数 变化时， 线性规划的可行域发生变化，可能引起最优解的变化。,B,A,（60，250）,变化后的总利润 - 变化前的总利润 = 增加的利润:,增加的总利润： (5060+ 100250) - (50
10、50+100 250) = 500 ，,说明：在一定范围内每增加（减少）1个台时的设备能力就可增加（减少）50元利润，称为该约束条件的对偶价格。,单位资源增加的利润： 500 / 10 = 50 元,B,A,（60，250）,假设原料A增加10千克时，即b2变化为410，这时可行域扩大，但最优解仍为直线x2 = 250和 x1 + x2 = 300 的交点 x1 = 50，x2 = 250 。此变化对总利润无影响，该约束条件的对偶价格为 0 。 解释：原最优解没有把原料 A 用尽，有50千克的剩余，因此增加10千克值增加了库存，而不会增加利润。,B,A,（60，250）,对偶价格具有一定的适用范围。,在一定范围内，当约束条件右边常数增加1个单位时：,（1）若约束条件的对偶价格大于0，则其最优目标函数值得到改善（变好）；,（2）若约束条件的对偶价格小于0，则其最优目标函数值受到影响（变坏）；,（3）若约束条件的对偶价格等于0，则最优目标函数值不变。,