线性规划求解方法法.ppt

线 性 规 划 授课教师： 王淑华 运筹学课件 可 行 区 域 与 基 本 可 行 解 | 图解法 |可行域的几何结构 | 基本可行解与基本定理 返回 运筹学课件线性规划 图 解 法 运筹学课件线性规划 例 运筹学课件线性规划 运筹学课件线性规划 注 释 线性规划解的的情况： | 可行域是空集（问题无解） |无界 | 最优解存在且唯一，则一定在 可行域顶点上达到 |存在无穷多最优解，一定存在可 行域的顶点是最优解 注：如果线性规划有最优解且最优 解不唯一，则一定有无穷多个最 优解 返回 运筹学课件线性规划 可 行 域 的 几 何 结 构 |基本假设 |凸集 |可行域的凸性 返回 运筹学课件线性规划 基 本 假 设 返回 运筹学课件线性规划 凸 集 返回 运筹学课件线性规划 问 题 返回 运筹学课件线性规划 基本 可行 解与 基本 定理 |定义 |基本定理 |问题 返回 运筹学课件线性规划 返回 运筹学课件线性规划 基 本 可 行 解 定 义 基 本 可 行 解 定 义 运筹学课件线性规划 返回 运筹学课件线性规划 基 本 定 理 返回 运筹学课件线性规划 说 明 返回 运筹学课件线性规划 图 解法 的灵 敏度 分析 灵敏度分析：建立数学模型和求得最优解 后，研究线性规 划的一个或多个参数（系数）ci , aij , bj 变化时 ，对最优解产生的影响。 例: 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 = 27500 x1 x2 z=20000=50x1+100x2 z=27500=50x1+100x2 z=0=50x1+100x2 z=10000=50x1+100x2 C B A D E |线性规划的标准化：引入松驰变量（含义 是资源的剩余量） 例 中引入 s1， s2， s3 模型化为 目标函数：Max z = 50 x1 + 100 x2 + 0 s1 + 0 s2 + 0 s3 约束条件：s.t. x1 + x2 + s1 = 300 2 x1 + x2 + s2 = 400 x2 + s3 = 250 x1 , x2 , s1 , s2 , s3 0 对于最优解 x1 =50 x2 = 250 ， s1 = 0 s2 =50 s3 = 0 说明：生产50单位产品和250单位产品将消 耗完所有可能的设备台时数及原料B，但对原料 A则还剩余50千克。 灵敏 度分 析 |目标函数中的系数 ci 的灵敏度分析： ci 的变化只影响目标函数等值线的斜 率，目标函数 z = 50 x1 + 100 x2 在 250= x2 (x2 = z 斜率为0 ) 300 = 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 （*） 时，原 最优解仍是最优解。 |假设产品的利润100元不变，即 c2 = 100，代到式（*）并整理得 0 c1 100 |假设产品的利润 50 元不变，即 c1 = 50 ，代到式（*）并整理得 50 c2 + |假若产品、的利润均改变，则可 直接用式（*）来判断。 |假设产品、的利润分别为60元、 55元，则 - 2 - (60 / 55) - 1 那么，最优解为 300= x1 + x2 和 400 = 2 x1 + x2 的交点 x1 = 100，x2 = 200 。 3 图 解法 的灵 敏度 分析 |假设产品的利润100元不变，即 c2 = 100，代到式（*）并整理得 0 c1 100 |假设产品的利润 50 元不变，即 c1 = 50 ，代到式（*）并整理得 50 c2 + |假若产品、的利润均改变，则可 直接用式（*）来判断。 |假设产品、的利润分别为60元、 55元，则 - 2 - (60 / 55) - 1 那么，最优解为 300= x1 + x2 和 400 = 2 x1 + x2 的交点 x1 = 100，x2 = 200 。 3 图 解法 的灵 敏度 分析 2 约束条件中右边系数 bj 的灵敏度分析 当约束条件中右边系数 bj 变化时，线性规划的 可行域发生变化，可能引起最优解的变化。 考虑上例的情况： 假设设备台时增加10个台时，即 b1变化为310， 这时可行域扩大， 最优解为 x2 = 250 和 x1 + x2 = 310 的交点 x1 = 60，x2 = 250 。 变化后的总利润 - 变化前的总利润 = 增加的利润 (5060+ 100250) - (50 50+100 250) = 500 ， 500 / 10 = 50 元 说明在一定范围内每增加（减少）1个台时 的设备能力就可增加（减少）50元利润，称为该 约束条件的对偶价格。 假设原料 A 增加10 千克时，即 b2变化为 410，这时可行域扩大， 但最优解仍为 x2 = 250 和 x1 + x2 = 300 的交点 x1 = 50，x2 = 250 。此变化对总利润 无影响，该约束条件的对偶价格为 0 。 解释：原最优解没有把原料 A 用尽，有 50千克的剩余，因此增加10千克值增加了 库存，而不会增加利润。 在一定范围内，当约束条件右边常数增加 1个单位时 （1）若约束条件的对偶价格大于0，则其最 优目标函数值得到改善（变好）； （2）若约束条件的对偶价格小于0，则其最 优目标函数值受到影响（变坏）； （3）若约束条件的对偶价格等于0，则最优 目标函数值不变。 注释 1.对偶价格表示其对应的资源每增 加一个单位，将改进多少个单位 的最优值。 2.当约束条件中的常数项增加一个 单位时，最优目标函数值增加的数量 称之为影子价格。在求目标函数最大 时，当约束条件中的常数项增加一个 单位时，目标函数值增加的数量就为 改进的数量，所以影子价格等于对偶 价格；在求目标函数值最小时，改进 的数量就是减少的数量，所以影子价 格即为负的对偶价格。 单 纯 形 法 单纯形法的基本思路：从可行域中某 一个顶点(即基本可行解)开始，判断 此顶点是否是最优解，如不是,则再找 另一个使得其目标函数值更优的顶点 ，称之为迭代，再判断此点是否是最 优解。直到找到一个顶点(基本可行解 )为其最优解，就是使得其目标函数值 最优的解，或者能判断出