1.2线性规求划解方法法.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 线性规划的标准化：——引入松驰变量（含义是资源的剩余量） 例 中引入 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元，则