运筹学课件整理版本.ppt

适用专业 信息管理授课教师 张凤玲 运筹学 课程回顾 线性规划问题灵敏度分析 1 CCN 影响对应的某个非基变量检验数CB 影响所有非基变量检验数2 b 影响基变量取值 最优基 最优解 本次授课内容 增加一个变量增加一个约束技术系数A发生变化 课程回顾 1 单纯形法小结2 线性规划应用 本次授课内容 线性规划问题灵敏度分析 价值系数 资源常数 课程回顾 一 什么样的问题可以建立线性规划模型 一般讲 一个经济 管理问题凡满足以下条件时 才能建立线性规划模型 1 要求解问题的目标函数能用数值指标来反映 且为线性函数 2 存在着多种方案 3 要求达到的目标是在一定的约束条件下实现的 这些约束条件可用线性等式或不等式来描述 二 建立模型的步骤 1 设变量 2 定目标 3 列约束 课程回顾 添加松弛变量 构造单位矩阵 添加人工变量1 大M法人工变量 不能够影响目标函数 必须取0用M放大人工变量的影响2 两阶段法对人工变量构造新的目标函数 使人工变量的系数为 1 迭代运算1 用非基变量替换基变量2 对主元素行 第l行 令bi aik bl alj alk ajl3 对主元素列 第k列 令1 alk 0 其它元素4 表中其它行列元素令aij ali alk aik aijbi bl alk aik bi 添加松弛变量 人工变量列出初始单纯形表 计算非基变量各列的检验数 J 所有 J 0 基变量中有非零的人工变量 某非基变量检验数为零 唯一最优解 对任一 J 0有aik 0 令 K max J 对所有aik 0计算 i bi aik令 l min i xl为换出变量aik为主元素 无界解 无可行解 无穷多最优解 是 否 否 是 否 是 是 否 第三章灵敏度分析 3 1灵敏度分析的含义1 意义A 代表企业的技术状况B 代表企业的资源状况C 代表企业产品市场状况决策者 预先了解各因素变化时的反应 在实际生产过程中 不断变化 2 灵敏度分析的类型 目标函数中价值系数C的变化 基变量价值系数变化 非基变量价值系数变化 右端资源常数b变化增加一个变量增加一个约束技术系数A发生变化 第三章灵敏度分析 3 2价值系数C发生改变 1 当CN中某个Cj发生变化时 只影响xj的检验数 若cj的变化满足 j cj zj 0 则目前解还是最优 否则就不是最优 继续单纯形迭代就可以求得新的最优解 若不影响原最优解 分析Cj变化范围 例 对于下例问题 讨论c3范围 1 价值系数C发生改变 2 当CB中某个Ci发生变化时 则会影响所有非基变量的检验数 若ci的变化满足 N 0 则目前解还是最优 否则就不是最优 继续单纯形迭代就可以求得新的最优解 最优解不变的情况下 CB的变化范围 例 对于下题中 讨论C1在什么范围内变化 问题的最优解不变 2 3 3 0 0 x1 x2 x3 x4 x5 1 0 1 4 3 1 3 0 1 2 1 3 1 3 1 2 x1 x2 2 3 0 0 c1 3 CB XB b j cj zj c1 c1 1 5 3 1 3 3 c1 3 4 5 0 0 0 c1 3 C1 3 4 c1 3 当3 4 c1 3时 最优解不变 习题 已知右侧的线性规划问题用单纯形法求解得最终单纯形表如下表所示 试分析 1 目标函数中变量x3的系数变为6 最优解是什么 2 目标函数中变量x1和x2的系数在什么范围内变动时最优解不变 3 3右端资源常数b发生改变 当b中某个分量bi发生改变时 将影响所在基变量的取值XB B 1b 若bi的变化仍满足B 1b 0 则目前基还是最优基 最优解为X B 1b 0 否则 若bi的变化使B 1b中某些分量小于0 则目前基成了不可行基 可以用对偶单纯形法迭代求得新的最优解 例 在例1中 讨论b1改变的情况 b1在什么范围内变化时 当前最优基不变 解 设b变为 b1 9 T 若B 1b 0则 解得9 4 b1 9 习题 已知右侧的线性规划问题用单纯形法求解得最终单纯形表如下表所示 0 2 1 3 0 01 x5 11 x4 11 x3 13 x2 10 610 x1x5 x1 cj zj 试说明分别发生下列变化时 最优解改变么 a 目标函数变为maxZ 2x1 3x2 x3 b 约束条件右端项由 6 4 T变为 3 4 T 课程小结 线性规划问题合理配料问题灵敏度分析1 CCN 影响对应的某个非基变量检验数CB 影响所有非基变量检验数2 b 影响基变量取值 最优基 最优解 3 3增加一个变量 若企业在计划期内 有新的产品可以生产 是否会影响原定生产计划 若企业在计划期内 有新的产品可以生产 则在知道新产品的单位利润Cn 1 消耗量Pn 1 a1n 1 a2n 1 amn 1 T时 可以在最优表中补充一列 可以由B 1Pn 1得到 而检验数行可以由 n 1 Cn 1 CBB 1Pn 1计算得到 若 n 1 0 则原最优解仍为最优 原生产计划不变 不生产这种新产品 否则当 n 1 0时 则应以xn 1进基 作单纯形迭代 从而找出新的最优解 例 在例1中 讨论增加产品D时的情况 假设产品D的单位利润为5 千元 工时消耗和材料消耗为 2 3 T 解 6 c6 CBB 1P6 5 2 3 2 3 0 5 x6 5 3 1 3 2 3 2 3 3 0 0 x1 x2 x3 x4 x5 1 0 1 4 3 1 3 0 1 2 1 3 1 3 1 2 x1 x2 2 3 0 0 1 5 3 1 3 CB XB b j cj zj 0 x5 5 3 1 3 2 3 3 5 0 3 5 4 5 1 5 1 5 1 11 5 3 5 2 5 3 5 9 5 x6 x2 5 3 1 0 2 5 0 3 5 11 5 1 5 0 习题 7 已知右侧的线性规划问题用单纯形法求解得最终单纯形表如下表所示 试说明分别发生下列变化时 新的最优解是什么 3 约束条件右端项由 1 3 T变为 2 3 T 4 增加一个新的变量x6 P6 1 1 T C6 7 3 4增加约束条件 外部环境变化生产原材料变化 条件变化出现新的约束条件 增加一个约束 把目前的最优解代入新增加的约束 能满足约束条件 则说明该增加的约束条件对最优解不构成影响 即不影响最优生产计划的实施 若当前最优解不满足新增加的约束 则应把新的约束添加到原问题的最优表内新的一行中去 用对偶单纯形方法来进行迭代 求出新的最优解 例 在例1的问题中增加约束2x1 2x2 x3 5 讨论最优解的情况 2 3 3 0 0 x1 x2 x3 x4 x5 1 0 1 4 3 1 3 0 1 2 1 3 1 3 1 2 x1 x2 2 3 0 0 1 5 3 1 3 CB XB b j cj zj 解 将当前最优解X 1 2 0 T代入约束条件中 得2 1 2 2 0 6 5 在新增加的约束条件中引入松弛变量得2x1 2x2 x3 x6 5加入最优表得 2 2 1 0 0 1 0 x6 0 0 5 x6 0 2 3 3 0 0 x1 x2 x3 x4 x5 1 0 1 4 3 1 3 0 1 2 1 3 1 3 1 2 x1 x2 2 3 CB XB b j cj zj 0 x6 0 0 2 2 1 0 0 1 5 x6 0 0 2 3 8 3 2 3 1 3 0 0 1 2 0 1 1 0 0 1 5 3 1 3 0 2 3 0 x1 x2 x4 1 3 13 6 1 2 1 0 5 3 0 1 3 0 1 13 6 0 1 3 2 3 1 6 0 0 1 0 1 2 1 2 0 0 1 6 0 1 3 5 6 1 5 6 企业某种工艺改进 原材料消耗发生变化 生产计划如何调整 3 5A中的元素发生变化 N中Pj改变的情形 与增加一个变量时完全相同 只需要认为新增加一个产品 其利润与xj的利润相同为cj 而其消耗系数Pn 1等于变化后的Pj 则可以直接用处理增加一个变量的方法进行处理 例 对例1中的线性规划 若a23由7改变为5 试讨论其最优解的情况 1 2 4 3 1 3 1 0 0 1 1 3 1 3 1 5 3 0 0 1 3 1 2 x1 x2 2 3 Cj zj XB CB b x4 x5 0 0 3 0 2 3 0 3 9 4 Cj zj 初始单纯形表 最终单纯形表 解 虚拟一种产品D 其单位利润为c6 3 资源消耗为P6 1 5 T 则 6 C6 CBB 1P6 1 3 0 由此可知 最优解不变 试讨论a23在什么范围变化时最优解不变 CB XB b 初始单纯形表 最终单纯形表 问题一 若原计划生产产品I的工艺结构有了改进 这时有关它的技术系数向量变为P1 2 5 2 T 每件利润为4元 试分析对原计划有什么影响 问题二 若原计划生产产品I的工艺结构有了改进 这时有关它的技术系数向量变为P1 4 5 2 T 每件利润为4元 试问该厂应如何安排最优生产方案 解 把改进工艺的产品I看作产品I 设x1 为其产量 计算在最终表中x1 对应的列向量B 1P1 和检验数 1 100 5 41 23 8 0 x1 x1 3 8 5 4 7 211 8 21 8 2 已知线性规划问题用单纯形法计算时得到的初始单纯形表及最终单纯形表如下所示 请将表中空白处数字填上 习题 CB XB b cj zj cj zj 习题 6 已知右侧的线性规划问题用单纯形法求解得最终单纯形表如下表所示 0 2 1 3 0 01 x5 11 x4 11 x3 13 x2 10 610 x1x5 x1 cj zj 试说明分别发生下列变化时 新的最优解是什么 a 目标函数变为maxZ 2x1 3x2 x3 b 约束条件右端项由 6 4 T变为 3 4 T c 增添一个新的约束 x1 2x3 2 习题 7 已知右侧的线性规划问题用单纯形法求解得最终单纯形表如下表所示 试说明分别发生下列变化时 新的最优解是什么 1 目标函数中变量x3的系数变为6 2 目标函数中变量x1和x2的系数在什么范围内变动时最优解不变 3 约束条件右端项由 1 3 T变为 2 3 T 4 增加一个新的变量x6 P6 1 1 T C6 7 5 增添一个新的约束x1 2x2 x3 4 例1 某工厂在计划期内要安排生产 三种产品 已知生产单位产品所需的A B两种原材料的消耗 如表1 1所示 该工厂每生产一件产品 可获利2元 每生产一件产品 可获利3元 问应如何安排计划使该工厂获利最多 表1 1 XB CB b x4 x5 0 0 3 0 2 3 0 3 4 7 4 1 0 3 4 1 4 0 1 1 4 1 4 9 4 0 5 4 0 3 4 3 4 9 4 x4 x2 0 3 1 2 4 3 1 3 1 0 0 1 1 3 1 3 1 5 3 0 0 1 3 1 2 x1 x2 2 3 3 9 4 1 9 Cj zj Cj zj Cj zj 用单纯形法求解下列问题 X 1 2 0 0 0 TZ 8 解 标准化得 例1 某工厂在计划期内要