运筹学图解法.pptVIP

在人们的生产实践中，经常会遇到如何利用现有资源来安排生产，以取得最大经济效益的问题。此类问题构成了运筹学的一个重要分支—数学规划，而线性规划(Linear Programming 简记LP)则是数学规划的一个重要分支。 自从1947年G. B. Dantzig 提出求解线性规划的单纯形方法以来，线性规划在理论上趋向成熟，在实用中日益广泛与深入。特别是在计算机能处理成千上万个约束条件和决策变量的线性规划问题之后，线性规划的适用领域更为广泛了，已成为现代管理中经常采用的基本方法之一。 原料 : 3. 都有一个要达到的目标，它可以用决 策变量的线性函数来表示。按问题的 不同要求，目标函数实现最大化或最 小化。 例2 某公司由于生产需要，共需要A，B两种原料至少350吨（A，B两种材料有一定替代性），其中A原料至少购进125吨。但由于A，B两种原料的规格不同，各自所需的加工时间也是不同的，加工每吨A原料需要2个小时，加工每吨B原料需要1小时，而公司总共有600个加工小时。又知道每吨A原料的价格为2万元，每吨B原料的价格为3万元，试问在满足生产需要的前提下，在公司加工能力的范围内，如何购买A，B两种原料，使得购进成本最低？ 设购进原料A的数量为设购进原料B的数量为 灵敏度分析：建立数学模型和求得最优解后，研究线性规划的一个或多个参数（系数） 变化时，对最优解产生的影响。 假设产品Ⅱ的利润100元不变，即 代入到式（*）并整理得： 假设产品Ⅰ的利润50 元不变，即 代到式（*）并整理得： 假设原料A增加10千克时，即b2变化为410，这时可行域扩大，但最优解仍为直线x2 = 250和 x1 + x2 = 300 的交点 x1 = 50，x2 = 250 。此变化对总利润无影响，该约束条件的对偶价格为 0 。 解释：原最优解没有把原料 A 用尽，有50千克的剩余，因此增加10千克值增加了库存，而不会增加利润。 B A 一般情况： 写成斜截式即： 目标函数等值线的斜率为 当 （*） 时，原最优解仍是最优解。 假若产品Ⅰ、Ⅱ的利润均改变，则可直接用式（*）来判断。假设产品Ⅰ、Ⅱ的利润分别为60元、55元，则有： 那么，最优解为直线 的交点 ： 二、约束条件中右边系数 的灵敏度分析 当约束条件中右边系数 变化时， 线性规划的可行域发生变化，可能引起最优解的变化。 B A （60，250） 变化后的总利润 - 变化前的总利润 = 增加的利润: 增加的总利润： (50×60+ 100×250) - (50 × 50+100 × 250) = 500 ， 说明：在一定范围内每增加（减少）1个台时的设备能力就可增加（减少）50元利润，称为该约束条件的对偶价格。 单位资源增加的利润： 500 / 10 = 50 元 B A （60，250） 1.3、线性规划问题的标准形式 线性规划有各种不同的形式，现将各种形式都统一变为如下的标准形式： 目标函数为最大 约束为等式 决策变量大于等于0 右端常数项大于0 或者 （向量和矩阵符号表述） 其中： 向量 对应的决策变量是 用矩阵表述： 其中 -----称为系数矩阵 -----称为资源向量 -----称为价值向量 -----称为决策变量向量 目标转换 令自由变量 其中 求最小可以等价的转换为求最大 变量转换(若出现自由变量 ) 将一般形式转换为标准形式 约束转换（实例） 不等式变等式 松弛变量 剩余变量 或者： 不等式变不等式 等式变不等式 例1:将下列数学模型变为标准型： 解： (1)、原式的标准型为： (2)、令 则可得原 规划的标准型为： 注意： 在将求最小问题化为标准型时，一 定注意所求的最优值互为相反数。 在不引起混淆的情况下，松弛变量、 剩余变量与决策变量的符号不加区 分,均用 表示。 松弛变量和剩余变量的解释 例1. 某工厂在计划期内要安排Ⅰ、Ⅱ两种产品的生产，已知生