运筹学 单纯形法1ppt课件

25 04 2020 1 第4节单纯形法计算步骤 25 04 2020 2 Step1化为标准型 找出初始可行基 并列出初始单纯形表 上述初始单纯形表中 最后一行称为检验数 j 25 04 2020 3 25 04 2020 4 Step2 检查非基变量所对应的检验数 j 若所有的 j 0 则当前的基可行解就是最优解 当前的目标函数值就是最优值 停止计算 否则 转入下一步 Step3 若存在一个 k 0 k所对应的变量xk的系数列向量Pk 0 即Pk中每一个分量aik 0 则该LP无有限最优解 停止计算 否则 转入下一步 Step4 进行可行基的迭代 重复以上步骤 25 04 2020 5 例7用单纯形法求解例6 maxz 2x1 3x2 s t x1 2x2 x3 84x1 x4 164x2 x5 12xj 0 j 1 2 5 25 04 2020 6 练习 分别用图解法和单纯形法求解下列线性规划问题 并指出单纯形法迭代的每一步相当于图形上哪一个顶点 MaxZ 10 x1 5x23x1 4x2 95x1 2x2 8x1 x2 0 25 04 2020 7 解 j 10 5 0 0 3 8 5 x1入 x4出 j 0 1 0 2 x2入 x3出 3 2 4 j 0 0 5 14 25 14 所以 X x1 x2 T 1 3 2 TZ 35 2 对应0 对应A 对应B 25 04 2020 8 回顾 单纯形法求解步骤 25 04 2020 9 第5节单纯形法的进一步讨论 25 04 2020 10 第5节单纯形法的进一步讨论 一 人工变量法 大M法 约束条件 加一个松弛变量 减一个剩余变量后 再加一个人工变量 加一个人工变量目标函数 人工变量的系数为 M 即罚因子若线性规划问题有最优解则人工变量必为0 25 04 2020 11 MaxZ 3x1 x3x1 x2 x3 4 2x1 x2 x3 13x2 x3 9xi 0 j 1 2 3 增加人工变量后 线性规划问题中就存在一个B为单位矩阵 后面可以根据我们前面所讲的单纯形法来进行求解 MaxZ 3x1 x3 Mx6 Mx7x1 x2 x3 x4 4 2x1 x2 x3 x5 x6 13x2 x3 x7 9xi 0 j 1 7 标准化及变形 25 04 2020 12 练习 列出初始单纯形表 并求解第2小题的最优解P55 2 2 1 2 25 04 2020 13 单纯形表 j 3 2M 4M 1 0 0 3 x2入 x6出 M 0 4 1 j 6M 3 0 4M 1 0 4M x1入 x7出 3M 0 1 1 j 0 0 3 0 M 3 2 9 x3入 x1出 3 2 M 1 2 3 2 j 9 2 0 0 0 M 3 4 3 4 M 1 4 所以 X x1 x2 x3 T 0 5 2 3 2 TZ 3 2 25 04 2020 14 二 两阶段法第一阶段暂不考虑原问题是否存在基可行解 给原问题加入人工变量 并构建一个仅含人工变量的目标函数 求极小化 人工变量的价值系数一般为1 约束条件和原问题的一样 当第一阶段中目标函数的最优值 0 即人工变量 0 则转入第二阶段 若第一阶段中目标函数的最优值不等于0 即人工变量不等于0 则判断原问题为无解 第二阶段 将第一阶段计算所得的单纯形表划去人工变量所在的列 并将目标函数换为原问题的目标函数作为第二阶段的初始单纯形表 进行进一步的求解 25 04 2020 15 求解辅助问题 得到辅助问题的最优解 引进人工变量x6 x7 构造辅助问题 辅助问题的目标函数为所有人工变量之和的极小化 MaxW 0 原问题没有可行解 把辅助问题的最优解作为原问题的初始基础可行解 用单纯形法求解原问题 得到原问题的最优解 否 是 两阶段法的算法流程图 MaxZ 3x1 x3x1 x2 x3 4 2x1 x2 x3 13x2 x3 9xi 0 j 1 2 3 MaxW x6 x7x1 x2 x3 x4 4 2x1 x2 x3 x5 x6 13x2 x3 x7 9xi 0 j 1 7 25 04 2020 16 第一阶段 单纯形表1 j 2 4 0 0 0 3 x2入 x6出 1 0 4 1 j 6 0 4 0 4 x1入 x7出 3 0 1 1 j 0 0 0 0 1 0 1 所以 已得最优解 且人工变量为非基变量 则可去掉人工变量 得原问题的一个即可行基 25 04 2020 17 第二阶段 单纯形表2 j 0 0 3 0 3 2 9 3 2 x3入 x1出 j 9 2 0 0 0 3 4 所以 X x1 x2 x3 T 0 5 2 3 2 TZ 3 2 25 04 2020 18 单纯形法小结 给定LP问题首先化为标准型 选取或构造一个单位矩阵作为基 求出初始基可行解 并列出初始单纯形表 标准化过程按第1 3节内容分7种情况 25 04 2020 19 第5节单纯形法的进一步讨论 人工变量法 大M法 和两阶段法约束条件 加一个松弛变量 减一个剩余变量后 再加一个人工变量 加一个人工变量若线性规划问题有最优解则人工变量必为0 25 04 2020 20 目标函数极小化时解的最优性判别 无可行解的判别 无界的判别 无穷多最优解的判别 唯一最优解的判别 三 单纯形法计算中的几个问题 当所有非基变量的 j 0时为最优解 最优解中人工变量为非0的基变量时 存在某个 k 0 且所有的aik 0时 得最优解时 有检验数为0的非基变量 得最优解时 所有非基变量检验数为负 25 04 2020 21 j 40 45 0 25 100 3 40 3 x2入 x4出 j 0 0 0 5 因为全 j 0 且 1 0 则有无穷多最优解 所以 其中一个最优解为X 0 80 3 20 0 0 T Z 1700 例1 0 10 思考 无穷多最优解的一般形式 25 04 2020 22 j 1 1 0 0 50 x1入 x4出 j 0 2 0 1 因为 2 2 且ai2全 0所以 无界 例2 25 04 2020 23 例3 下表为一极大化问题对应的单纯形表 讨论在a1 a2 a3 a4 a5 a6取何值的情况下 该表中的解为 唯一最优解 无穷多最优解 无界 无可行解 非最优 继续换基 X3换入 x2换出 a40 a2 0 a3 0a4 0 a5 0 x4或x2为人工变量 a6 0 x1为人工变量 a6 0a4 0 a4 a5 a6 a1 2 a1 0a6 0 a1 0 25 04 2020 24 复习题 下表为一求解极大值线性规划问题的初始单纯型表及迭代后的表 为松弛变量 试求表中a L的值及各变量下标m t的值 25 04 2020 25 第6节应用举例 一般而言 一个经济 管理问题凡是满足以下条件时 才能建立线性规划模型 要求解问题的目标函数能用数值指标来反映 且为线性函数 存在着多种方案 要求达到的目标是在一定条件下实现的 这些约束可用线性等式或不等式描述 25 04 2020 26 建模步骤 第一步 设置要求解的决策变量 决策变量选取得当 不仅能顺利地建立模型而且能方便地求解 否则很可能事倍功半 第二步 找出所有的限制 即约束条件 并用决策变量的线性方程或线性不等式来表示 第三步 明确目标要求 并用决策变量的线性函数来表示 确定对函数是取极大还是取极小的要求 决策变量的非负要求可以根据问题的实际意义加以确定 25 04 2020 27 一般的产品计划问题举例例1 某工厂生产A B两种产品 均需经过两道工序 每生产一吨产品A需要经第一道工序加工2小时 第二道工序加工3小时 每生产一吨产品B需要经第一道工序加工3小时 第二道工序加工4小时 可供利用的第一道工序为12小时 第二道工序为24小时 生产产品B的同时产出副产品C 每生产一吨产品B 可同时得到2吨产品C而毋需外加任何费用 副产品C一部分可以盈利 剩下的只能报废 出售产品A每吨能盈利400元 产品B每吨能盈利1000元 每销售一吨副产品C能盈利300元 而剩余要报废的则每吨损失200元 经市场预测 在计划期内产品C最大销量为5吨 试列出线性规划模型 决定A B两种产品的产量 使工厂总的利润最大 25 04 2020 28 数学模型 设 x1 产品A的产量 x2 产品B的产量 x3 产品C的销售量 x4 产品C的报废量 依题意 可得 25 04 2020 29 例2合理下料问题 现要截取2 9米 2 1米和1 5米的圆钢各100根 而现在仅有一批长7 4米的棒料毛坯 问应如何下料 才能使所消耗的原材料最省 解 依题意 在排除明显不合理的方案后 可以列出8种套裁方案 前5种更合理 25 04 2020 30 例3 25 04 2020 31 练习1 练习2 P57 T2 9 25 04 2020 32 25 04 2020 33 例4 连续投资问题 P53 2 13 25 04 2020 34 练习 设某投资者有30000元可供为期四年的投资 现有五个投资机会可供选择 A 可在每年年初投资 每年每元投资可获0 2元 B 第一年年初或第三年年初投资 每两年每元投资可获利润0 5元 两年后获利 C 第一年初投资 三年后每元投资获利0 8元 这项投资最多不超过20000元 D 第二年年初投资 两年后每元投资可获利0 6元 这项投资最多不超过15000元 E 第一年年初投资 四年后每元获利1 7元 这项投资最多不超过20000元 投资者应如何投资 使他在四年后所拥有资金总额最大 25 04 2020 35 第一章总结 基本概念 可行解 基 基解 基可行解 可行基 凸集 顶点基本定理 可行域为凸集 基可行解顶点 最优解一定在顶点上取得 25 04 2020 36 基本问题 什么是线性规划问题的