管理运筹学课件.ppt

1 管理运筹学课件 2 1 绪论2 线性规划3 对偶问题4 运输问题5 动态规划6 图与网络分析7 决策论 运筹学 目录 说明本教学课件是与教材紧密配合使用的 教材为 管理运筹学 韩大卫编著 大连理工大学出版社 参考书 运筹学 清华大学出版社 管理运筹学 方面本科教材的相关内容 3 绪论 运筹学 OperationalResearch 直译为 运作研究 运筹学是运用科学的方法 如分析 试验 量化等 来决定如何最佳地运营和设计各种系统的一门学科 运筹学对经济管理系统中的人力 物力 财力等资源进行统筹安排 为决策者提供有依据的最优方案 以实现最有效的管理 运筹学有广泛应用运筹学的产生和发展 4 运筹学解决问题的过程 1 提出问题 认清问题2 寻求可行方案 建模 求解3 确定评估目标及方案的标准或方法 途径4 评估各个方案 解的检验 灵敏性分析等5 选择最优方案 决策6 方案实施 回到实践中7 后评估 考察问题是否得到完满解决1 2 3 形成问题 4 5 分析问题 定性分析与定量分析 构成决策 5 运筹学的分支 线性规划非线性规划整数规划动态规划多目标规划随机规划模糊规划等 图与网络理论存储论排队论决策论对策论排序与统筹方法可靠性理论等 6 运筹学在工商管理中的应用 生产计划 生产作业的计划 日程表的编排 合理下料 配料问题 物料管理等库存管理 多种物资库存量的管理 库存方式 库存量等运输问题 确定最小成本的运输线路 物资的调拨 运输工具的调度以及建厂地址的选择等人事管理 对人员的需求和使用的预测 确定人员编制 人员合理分配 建立人才评价体系等市场营销 广告预算 媒介选择 定价 产品开发与销售计划制定等财务和会计 预测 贷款 成本分析 定价 证券管理 现金管理等 设备维修 更新 项目选择 评价 工程优化设计与管理等 7 运筹学方法使用情况 美1983 8 运筹学方法在中国使用情况 随机抽样 9 运筹学的推广应用前景 据美劳工局1992年统计预测 运筹学应用分析人员需求从1990年到2005年的增长百分比预测为73 增长速度排到各项职业的前三位 结论 运筹学在国内或国外的推广前景是非常广阔的工商企业对运筹学应用和需求是很大的在工商企业推广运筹学方面有大量的工作要做 10 学习运筹学要把重点放在分析 理解有关的概念 思路上 在自学过程中 应该多向自己提问 如一个方法的实质是什么 为什么这样做 怎么做等 自学时要掌握三个重要环节1 认真阅读教材和参考资料 以指定教材为主 同时参考其他有关书籍 一般每一本运筹学教材都有自己的特点 但是基本原理 概念都是一致的 注意主从 参考资料会帮助你开阔思路 使学习深入 但是 把时间过多放在参考资料上 会导致思路分散 不利于学好 2 要在理解了基本概念和理论的基础上研究例题 注意例题是为了帮助你理解概念 理论的 作业练习的主要作用也是这样 它同时还有让你自己检查自己学习的作用 因此 做题要有信心 要独立完成 不要怕出错 因为 整个课程是一个整体 各节内容有内在联系 只要学到一定程度 知识融会贯通起来 你做题的正确性自己就有判断 3 要学会做学习小结 每一节或一章学完后 必须学会用精炼的语言来该书所学内容 这样 你才能够从较高的角度来看问题 更深刻的理解有关知识和内容 这就称作 把书读薄 若能够结合自己参考大量文献后的深入理解 把相关知识从更深入 广泛的角度进行论述 则称之为 把书读厚 在建数学模型时要结合实际应用 要学会用计算机软件解决问题 如何学习运筹学课程 返回目录 11 各章节的重点 难点及注意事项 12 1 线性规划 线性规划模型 目标函数 Maxz 50 x1 100 x2约束条件 s t x1 x2 3002x1 x2 400 x2 250 x1 x2 0 看p1例1 1 1 2 例1 某工厂在计划期内要安排甲 乙两种产品的生产 已知生产单位产品所需的设备台时及A B两种原材料的消耗以及资源的限制 如下表 问题 工厂应分别生产多少单位甲 乙产品才能使工厂获利最多 13 1 线性规划 续1 1 1 1线性规划的概念线性规划的组成 目标函数Maxf或Minf约束条件s t subjectto 满足于决策变量用符号来表示可控制的因 一般形式 p10 p11 目标函数 Max Min z c1x1 c2x2 cnxn约束条件 s t a11x1 a12x2 a1nxn b1a21x1 a22x2 a2nxn b2 am1x1 am2x2 amnxn bmx1 x2 xn 0 标准形式 p11 p15 例1 3 目标函数 Maxz c1x1 c2x2 cnxn约束条件 s t a11x1 a12x2 a1nxn b1a21x1 a22x2 a2nxn b2 am1x1 am2x2 amnxn bmx1 x2 xn 0 练习 p28 29习题1 3 14 1 线性规划 续1 2 1 2线性规划问题解的概念及性质熟悉下列一些解的概念 p12 18 可行解 可行解集 可行域 最优解 最优值 基 基变量 非基变量 基本解 基本可行解 可行基 最优基 图解方法及各有关概念的意义 p4 6 看 图解法步骤 p6下一页是一个图解法解题的一个例子 右图中的阴影部分为可行域 单纯形法的理论基础 p31 36 1 2 3段要求看懂 了解如何直接通过对约束矩阵的分析求出基本可行解1 2 4 1 2 5两段应注重结论的了解 如单纯形法思想和关于线性规划解的四个定理 而对证明过程则可根据自己的数学基础来掌握 基础很好 可要求掌握 否则 也可略去不看 习题 p51习题2 1 15 线性规划模型 线性规划模型的结构目标函数 max min约束条件 变量符号 0 自由 0线性规划的标准形式目标函数 max约束条件 变量符号 0 16 线性规划的图解 maxz x1 3x2s t x1 x2 6 x1 2x2 8x1 0 x2 0 可行域 目标函数等值线 最优解 6 4 8 6 0 x1 x2 17 可行域的性质 线性规划的可行域是凸集线性规划的最优解在极点上 凸集 凸集 不是凸集 极点 18 线性规划的基本概念 线性规划的基矩阵 基变量 非基变量 目标函数 约束条件 行列式 0基矩阵 右边常数 19 20 基变量x1 x2 x3 非基变量x4 x5 x6 基础解为 x1 x2 x3 x4 x5 x6 5 3 1 0 0 0 是基础可行解 表示可行域的一个极点 目标函数值为 z 20 21 基变量x1 x2 x4 非基变量x3 x5 x6 基础解为 x1 x2 x3 x4 x5 x6 27 5 12 5 0 2 5 0 0 是基础可行解 表示可行域的一个极点 目标函数值为 z 18 22 基变量x1 x2 x5 非基变量x3 x4 x6 基础解为 x1 x2 x3 x4 x5 x6 6 3 0 0 3 0 是基础解 但不是可行解 不是一个极点 23 基变量x1 x2 x6 非基变量x3 x4 x5 基础解为 x1 x2 x3 x4 x5 x6 3 4 0 0 0 4 是基础可行解 表示可行域的一个极点 目标函数值为 z 18 24 基变量x2 x3 x4 非基变量x1 x5 x6 基础解为 x1 x2 x3 x4 x5 x6 0 21 2 27 2 30 0 0 是基础解 但不是可行解 25 非基变量x1 x4 x6 基变量x2 x3 x5 基础解为 x1 x2 x3 x4 x5 x6 0 3 6 0 15 0 是基础可行解 表示可行域的一个极点 目标函数值为 z 15 26 非基变量x1 x4 x5 基变量x2 x3 x6 基础解为 x1 x2 x3 x4 x5 x6 0 11 2 3 2 0 0 10 是基础解但不是可行解 27 目标函数 约束条件 基矩阵 右边常数 进基变量 离基变量 基变换 基变量 28 进基变量 离基变量 目标函数 约束条件 右边常数 29 目标函数 约束条件 新的基矩阵 右边常数 30 进基变量 离基变量 目标函数 约束条件 基矩阵 31 目标函数 约束条件 新的基矩阵 右边常数 32 基础解 基础可行解 maxz x1 3x2Ds t x1 x2 x3 6B x1 2x2 x4 8x4 0Cx3 0 x1 x2 x3 x4 0 x1 0EOx2 0A 33 几何概念 代数概念 约束直线 满足一个等式约束的解 约束半平面 满足一个不等式约束的解 约束半平面的交集 凸多边形 满足一组不等式约束的解 约束直线的交点 基础解 可行域的极点 基础可行解 目标函数等值线 一组平行线 目标函数值等于一个常数的解 34 单纯形表 35 求解线性规划问题 写成标准化形式 36 写出单纯形表 25 1 36 2 0 3 2 0 2 72 0 1 1 2 0 1 1 2 7 1 2 1 x5 1 2 1 0 1 2 18 1 2 4 7 18 1 1 2 1 2 x2 0 x6离基 x2进基 x5离基 x1进基 37 0 4 2 2 1 86 0 1 1 0 2 1 1 x1 0 1 1 1 4 14 11 0 1 0 x2 3 得到最优解 最优解为 x1 x2 x3 x4 x5 x6 14 11 0 0 0 0 maxz 86 38 1 线性规划 续1 2 例1 目标函数 Maxz 50 x1 100 x2约束条件 s t x1 x2 300 A 2x1 x2 400 B x2 250 C x1 0 D x2 0 E 得到最优解 x1 50 x2 250最优目标值z 27500 39 1 线性规划 续1 3 1 3单纯形法利用单纯形表的方法求解线性规划 重点 p36 51 此项内容是本章的重点 学习中应注意掌握表格单纯形法求解线性规划问题的基本过程 要通过读懂教材内容以及大量练习来掌握 40 1 线性规划 续1 3 表格单纯形法 p40 p45 考虑 bi 0i 1 mMaxz c1x1 c2x2 cnxns t a11x1 a12x2 a1nxn b1a21x1 a22x2 a2nxn b2 am1x1 am2x2 amnxn bmx1 x2 xn 0加入松弛变量 Maxz c1x1 c2x2 cnxns t a11x1 a12x2 a1nxn xn 1 b1a21x1 a22x2 a2nxn xn 2 b2 am1x1 am2x2 amnxn xn m bmx1 x2 xn xn 1 xn m 0 41 显然 xj 0j 1 n xn i bii 1 m是基本可行解对应的基是单位矩阵 以下是初始单纯形表 mm其中 f cn ibi j cn iaij cj为检验数cn i 0i 1 mi 1i 1an i i 1 an i j 0 j i i j 1 m 1 线性规划 42 单纯形法的计算步骤 1 43 单纯形法的计算步骤 2 44 注意 单纯形法中 1 每一步运算只能用矩阵初等行变换 2 表中第3列的数总应保持非负 0 3 当所有检验数均为正 0 时 得到最优单纯形表 单纯形法的计算步骤 3 45 1 线性规划 例1 化标准形式 Maxz 3x1 5x2s t x1 x3 82x2 x4 123x1 4x2 x5 36x1 x2 x3 x4 x5 0由于所有检验系数都大于0 因此已得到最优解X 4 6 4 0 0 T z 42 46 1 线性规划 一般情况的处理及注意事项的强调 p41 51 这段主要是讨论初始基本可行解不明显时 常用的方法 弄清它的原理 并通过例题掌握这些方法 同时进一步熟悉用单纯形法解题 考虑一般问题 bi 0i 1 mMaxz c1x1 c2x2 cnxns t a11x1 a12x2 a1nxn b1a21x1 a22x2 a2nxn b2 am1x1 am2x2 amnxn bmx1 x2 xn 0 47 1 线性规划 大M法 引入人工变量xn i 0i 1 m 充分大正数M 得到 Maxz c1x1 c2x2 cnxn Mxn 1 Mxn m s t a11x1 a12x2 a1nxn xn 1 b1a21x1 a22x2 a2nxn xn 2 b2 am1x1 am2x2 amnxn xn m bmx1 x2 xn xn 1 xn m 0显然 xj 0j 1 n xn i bii 1 m是基本可行解对应的基是单位矩阵 结论 1 若得到的最优解X 而且X的基变矢中不含有人工变量 则X的前n个分量就构成原LP问题的一个最优基本解 否则原问题无可行解 48 2 若迭代的最终结果为原问题解无界 此时若最末单纯形表的 基列 中不含有人工变量 则原问题也是解界 否则原问题无可行解 注意 一旦某个人工变量离基 即可将其删除 因此用单纯形表计算时 离基的人工变量计算工作可以省去 1 线性规划 49 1 线性规划 两阶段法 引入人工变量xn i 0 i 1 m 构造 Maxz xn 1 xn 2 xn ms t a11x1 a12x2 a1nxn xn 1 b1a21x1 a22x2 a2nxn xn 2 b2 am1x1 am2x2 amnxn xn m bmx1 x2 xn xn 1 xn m 0第一阶段求解上述问题显然 xj 0j 1 n xn i bii 1 m是基本可行解对应的基是单位矩阵 结论 p43 44 若得到的最优解满足xn i 0i 1 m则是原问题的基本可行解 否则 原问题无可行解 得到原问题的基本可行解后 第二阶段求解原问题 50 1 线性规划 续1 3 例题 例 LP Maxz 5x1 2x2 3x3 x4s t x1 2x2 3x3 152x1 x2 5x3 20 x1 2x2 4x3 x4 26x1 x2 x3 x4 0大M法问题 LP M Maxz 5x1 2x2 3x3 x4 Mx5 Mx6s t x1 2x2 3x3 x5 152x1 x2 5x3 x6 20 x1 2x2 4x3 x4 26x1 x2 x3 x4 x5 x6 0两阶段法 第一阶段问题 LP 1 Maxz x5 x6s t x1 2x2 3x3 x5 152x1 x2 5x3 x6 20 x1 2x2 4x3 x4 26x1 x2 x3 x4 x5 x6 0 51 1 线性规划 续1 3 大M法例 大M法 LP M 得到最优解 25 3 10 3 0 11 T最优目标值 112 3 52 1 线性规划 续1 3 两阶段法例 第一阶段 LP 1 得到原问题的基本可行解 0 15 7 25 7 52 7 T 53 1 线性规划 续1 3 两阶段法例 第二阶段把基本可行解填入表中 得到原问题的最优解 25 3 10 3 0 11 T最优目标值 112 3 54 1 线性规划 续1 3 1 3 5矩阵描述 此段为选读 有困难者可不看 1 3 6段单纯形迭代过程中的几点注意事项是对有关内容的强调和补充 要认真学习 理解 习题 p70 71习题11 5 1 6 55 1 4线性规划应用 建模 p55 68 本节介绍了些线性规划应用的例子 这些例子从多个方面介绍建模对未来是很有用的 应认真对待 除了教材上的例子之外 还有许多其它应用 合理利用线材问题 如何下料使用材最少 配料问题 在原料供应量的限制下如何获取最大利润 投资问题 从投资项目中选取方案 使投资回报最大 产品生产计划 合理利用人力 物力 财力等 使获利最大 劳动力安排 用最少的劳动力来满足工作的需要 运输问题 如何制定调运方案 使总运费最小 下面是一些建模的例子 有兴趣者 可作为练习 这些例子有一定的难度 做起来会有一些困难 习题 p72 73习题11 7 1 8 1 9 1 10 1 线性规划 续1 4 返回目录 56 例 某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下 设司机和乘务人员分别在各时间段一开始时上班 并连续工作八小时 问该公交线路怎样安排司机和乘务人员 既能满足工作需要 又配备最少司机和乘务人员 例 人力资源分配的问题 57 解 设xi表示第i班次时开始上班的司机和乘务人员数 这样我们建立如下的数学模型 目标函数 Minx1 x2 x3 x4 x5 x6约束条件 s t x1 x6 60 x1 x2 70 x2 x3 60 x3 x4 50 x4 x5 20 x5 x6 30 x1 x2 x3 x4 x5 x6 0 例 人力资源分配的问题 续 58 例 明兴公司生产甲 乙 丙三种产品 都需要经过铸造 机加工和装配三个车间 甲 乙两种产品的铸件可以外包协作 亦可以自行生产 但产品丙必须本厂铸造才能保证质量 数据如下表 问 公司为了获得最大利润 甲 乙 丙三种产品各生产多少件 甲 乙两种产品的铸造中 由本公司铸造和由外包协作各应多少件 例 生产计划的问题 59 解 设x1 x2 x3分别为三道工序都由本公司加工的甲 乙 丙三种产品的件数 x4 x5分别为由外协铸造再由本公司机加工和装配的甲 乙两种产品的件数 求xi的利润 利润 售价 各成本之和可得到xi i 1 2 3 4 5 的利润分别为15 10 7 13 9元 这样我们建立如下的数学模型 目标函数 Max15x1 10 x2 7x3 13x4 9x5约束条件 s t 5x1 10 x2 7x3 80006x1 4x2 8x3 6x4 4x5 120003x1 2x2 2x3 3x4 2x5 10000 x1 x2 x3 x4 x5 0 例 生产计划的问题 续 60 例 永久机械厂生产 三种产品 均要经过A B两道工序加工 假设有两种规格的设备A1 A2能完成A工序 有三种规格的设备B1 B2 B3能完成B工序 可在A B的任何规格的设备上加工 可在任意规格的A设备上加工 但对B工序 只能在B1设备上加工 只能在A2与B2设备上加工 数据如下表 问 为使该厂获得最大利润 应如何制定产品加工方案 例 生产计划的问题 续 61 解 设xijk表示第i种产品 在第j种工序上的第k种设备上加工的数量 利润 销售单价 原料单价 产品件数 之和 每台时的设备费用 设备实际使用的总台时数 之和 这样我们建立如下的数学模型 Max0 75x111 0 7753x112 1 15x211 1 3611x212 1 9148x312 0 375x121 0 5x221 0 4475x122 1 2304x322 0 35x123s t 5x111 10 x211 6000 设备A1 7x112 9x212 12x312 10000 设备A2 6x121 8x221 4000 设备B1 4x122 11x322 7000 设备B2 7x123 4000 设备B3 x111 x112 x121 x122 x123 0 产品在A B工序加工的数量相等 x211 x212 x221 0 产品在A B工序加工的数量相等 x312 x322 0 产品在A B工序加工的数量相等 xijk 0 i 1 2 3 j 1 2 k 1 2 3 例 生产计划的问题 续 62 例 某工厂要做100套钢架 每套用长为2 9m 2 1m 1 5m的圆钢各一根 已知原料每根长7 4m 问 应如何下料 可使所用原料最省 解 设计下列5种下料方案 假设x1 x2 x3 x4 x5分别为上面前5种方案下料的原材料根数 这样我们建立如下的数学模型 目标函数 Minx1 x2 x3 x4 x5约束条件 s t x1 2x2 x4 1002x3 2x4 x5 1003x1 x2 2x3 3x5 100 x1 x2 x3 x4 x5 0 例 套裁下料问题 63 例6 某工厂要用三种原料1 2 3混合调配出三种不同规格的产品甲 乙 丙 数据如下表 问 该厂应如何安排生产 使利润收入为最大 例 配料问题 64 例 配料问题 续 解 设xij表示第i种 甲 乙 丙 产品中原料j的含量 这样我们建立数学模型时 要考虑 对于甲 x11 x12 x13 对于乙 x21 x22 x23 对于丙 x31 x32 x33 对于原料1 x11 x21 x31 对于原料2 x12 x22 x32 对于原料3 x13 x23 x33 目标函数 利润最大 利润 收入 原料支出约束条件 规格要求4个 供应量限制3个 65 Maxz 15x11 25x12 15x13 30 x21 10 x22 40 x31 10 x33s t 0 5x11 0 5x12 0 5x13 0 原材料1不少于50 0 25x11 0 75x12 0 25x13 0 原材料2不超过25 0 75x21 0 25x22 0 25x23 0 原材料1不少于25 0 5x21 0 5x22 0 5x23 0 原材料2不超过50 x11 x21 x31 100 供应量限制 x12 x22 x32 100 供应量限制 x13 x23 x33 60 供应量限制 xij 0 i 1 2 3 j 1 2 3 例 配料问题 续 66 例8 某部门现有资金200万元 今后五年内考虑给以下的项目投资 已知 项目A 从第一年到第五年每年年初都可投资 当年末能收回本利110 项目B 从第一年到第四年每年年初都可投资 次年末能收回本利125 但规定每年最大投资额不能超过30万元 项目C 需在第三年年初投资 第五年末能收回本利140 但规定最大投资额不能超过80万元 项目D 需在第二年年初投资 第五年末能收回本利155 但规定最大投资额不能超过100万元 据测定每万元每次投资的风险指数如右表 问 a 应如何确定这些项目的每年投资额 使得第五年年末拥有资金的本利金额为最大 b 应如何确定这些项目的每年投资额 使得第五年年末拥有资金的本利在330万元的基础上使得其投资总的风险系数为最小 解 1 确定决策变量 连续投资问题设xij i 1 5 j 1 2 3 4 表示第i年初投资于A j 1 B j 2 C j 3 D j 4 项目的金额 这样我们建立如下的决策变量 Ax11x21x31x41x51Bx12x22x32x42Cx33Dx24 例 投资问题 67 2 约束条件 第一年 A当年末可收回投资 故第一年年初应把全部资金投出去 于是x11 x12 200 第二年 B次当年末才可收回投资故第二年年初的资金为x11 于是x21 x22 x24 1 1x11 第三年 年初的资金为x21 x12 于是x31 x32 x33 1 1x21 1 25x12 第四年 年初的资金为x31 x22 于是x41 x42 1 1x31 1 25x22 第五年 年初的资金为x41 x32 于是x51 1 1x41 1 25x32 B C D的投资限制 xi2 30 I 1 2 3 4 x33 80 x24 1003 目标函数及模型 a Maxz 1 1x51 1 25x42 1 4x33 1 55x24s t x11 x12 200 x21 x22 x24 1 1x11 x31 x32 x33 1 1x21 1 25x12 x41 x42 1 1x31 1 25x22 x51 1 1x41 1 25x32 xi2 30 I 1 2 3 4 x33 80 x24 100 xij 0 i 1 2 3 4 5 j 1 2 3 4 b Minf x11 x21 x31 x41 x51 3 x12 x22 x32 x42 4x33 5 5x24s t x11 x12 200 x21 x22 x24 1 1x11 x31 x32 x33 1 1x21 1 25x12 x41 x42 1 1x31 1 25x22 x51 1 1x41 1 25x32 xi2 30 I 1 2 3 4 x33 80 x24 1001 1x51 1 25x42 1 4x33 1 55x24 330 xij 0 i 1 2 3 4 5 j 1 2 3 4 例 投资问题 续 68 2 线性规划问题的进一步研究 2 1 2 1对偶原理1 对偶问题 考虑前文例1若设备和原料都用于外协加工 工厂收取加工费 试问 设备工时和原料A B各如何收费才最有竞争力 设y1 y2 y3分别为每设备工时 原料A B每单位的收取费用Maxz 50 x1 100 x2Minf 300y1 400y2 250y3s t x1 x2 300s t y1 2y2 502x1 x2 400 不少于甲产品的利润 x2 250y1 y2 y3 100 x1 x2 0y1 y2 y3 0 69 2 对偶定义对称形式 互为对偶 LP Maxz cTx DP Minf bTys t Ax bs t ATy cx 0y 0 Max Min 一般形式 若一个问题的某约束为等式 那么对应的对偶问题的相应变量无非负限制 反之 若一个问题的某变量无非负限制 那么对应的对偶问题的相应约束为等式 2 线性规划问题的进一步研究 2 1 70 3 对偶定理 原问题与对偶问题解的关系 考虑 LP 和 DP 定理2 1 弱对偶定理 若x y分别为 LP 和 DP 的可行解 那么cTx bTy 推论若 LP 可行 那么 LP 无有限最优解的充分必要条件是 LD 无可行解 定理2 2 最优性准则定理 若x y分别为 LP 和 DP 的可行解 且cTx bTy 那么x y分别为 LP 和 DP 的最优解 定理2 3 主对偶定理 若 LP 和 DP 均可行 那么 LP 和 DP 均有最优解 且最优值相等 以上定理 推论对任意形式的相应线性规划的对偶均有效 习题 p99习题22 1 2 线性规划问题的进一步研究 2 1 71 4 影子价格 是一个向量 它的分量表示最优目标值随相应资源数量变化的变化率 若x y 分别为 LP 和 DP 的最优解 那么 cTx bTy 根据f bTy b1y1 b2y2 bmym 可知 f bi yi yi 表示bi变化1个单位对目标f产生的影响 称yi 为bi的影子价格 注意 若B是最优基 y BT 1cB为影子价格向量 2 线性规划问题的进一步研究 2 1 72 5 由最优单纯形表求对偶问题最优解第1章例1 化标准形式 Maxz 50 x1 100 x2s t x1 x2 x3 300 2x1 x2 x4 400 x2 x5 250 x1 x2 x3 x4 x5 0IOB p1 p4 p2 BT 1cBB 1最优解x1 50 x2 250 x4 50 松弛标量 表示原料A有50个单位的剩余 影子价格y1 50y2 0y3 50 B 1对应的检验数 BT 1cB 2 线性规划问题的进一步研究 2 1 73 2 2对偶单纯形法对偶单纯形法在什么情况下使用 应用前提 有一个基 其对应的基本解满足 单纯形表的检验数行全部非正 对偶可行 变量取值可有负数 非可行解 注 通过矩阵行变换运算 使所有相应变量取值均为非负数即得到最优单纯性表 2 线性规划问题的进一步研究 2 2 74 2 线性规划问题的进一步研究 2 2 对偶单纯形法求解线性规划问题过程 1 建立初始对偶单纯形表 对应一个基本解 所有检验数均非正 转2 2 若b 0 则得到最优解 停止 否则 若有bk 0则选k行的基变量为出基变量 转3 3 若所有akj 0 j 1 2 n 则原问题无可行解 停止 否则 若有akj 0则选 min j akj akj 0 r akr 那么r为进基变量 转4 4 以akr 为转轴元 作矩阵行变换使其变为1 该列其他元变为0 转2 75 例 求解线性规划问题 Minf 2x1 3x2 4x3S t x1 2x2 x3 32x1 x2 x3 4x1 x2 x3 0标准化 MaxZ 2x1 3x2 4x3S t x1 2x2 x3 x4 3 2x1 x2 3x3 x5 4x1 x2 x3 x4 x5 0 2 线性规划问题的进一步研究 2 2 76 表格对偶单纯形法 习题 p100习题22 2 2 3 2 线性规划问题的进一步研究 2 2 对偶线性规划 对偶的定义对偶问题的性质原始对偶关系目标函数值之间的关系最优解之间的关系 互补松弛关系对偶可行基对偶单纯形法对偶的经济解释 DUAL 一 对偶的定义 原始问题minz CTXs t AX bX 0 对偶问题maxy bTWs t ATW CW 0 min b A CT C AT bT max m n m n 二 对偶问题的性质 1 对偶的对偶就是原始问题 2 其他形式问题的对偶 三 原始对偶关系 1 可行解的目标函数值之间的关系设XF WF分别是原始问题和对偶问题的可行解z CTXF WTAXF WTb y2 最优解的目标函数值之间的关系设Xo Wo分别是原始问题和对偶问题的最优解z CTXo WoTAXo WoTb y 3 原始问题和对偶问题最优解之间的互补松弛关系 minz CTXs t AX XS bX XS 0 maxy bTWs t ATW WS CW WS 0 minz CTXs t AX bX 0 maxy bTWs t ATW CW 0 互补松弛关系 minz CTXs t AX XS bX XS 0 maxy bTWs t ATW WS CW WS 0 XTWS 0WTXS 0 m n W WS AT I C n A XS I b n m m X 原始问题和对偶问题变量 松弛变量的维数 w1wiwmwm 1wm jwn m x1xjxnxn 1xn ixn m 对偶问题的变量对偶问题的松弛变量 原始问题的变量原始问题的松弛变量 xjwm j 0wixn i 0 i 1 2 m j 1 2 n 在一对变量中 其中一个大于0 另一个一定等于0 Kuhn Tucher条件 3 原始问题和对偶问题最优解的充分必要条件 1 原始可行条件 PFC AX XS bX XS 0 2 对偶可行条件 DFC ATW WS CW WS 0 3 互补松弛条件 CSC XTWS 0WTXS 0 四 对偶单纯形法 1 用单纯形表求解原始问题的四种形式 minz CTXs t AX bX 0 minz CTXs t AX bX 0 maxz CTXs t AX bX 0 maxz CTXs t AX bX 0 2 3 4 1 单纯形表和对偶 1 minz CTXs t AX XS bX XS 0 maxy bTWs t ATW WS CW WS 0 minz CTXs t AX bX 0 maxy bTWs t ATW CW 0 对偶问题 原始问题 引进松弛变量 引进松弛变量 minz CTXs t AX XS bX XS 0 maxy bTWs t ATW WS CW WS 0 WT CBTB 1WST CT WTA minz CTXs t AX XS bX XS 0 maxy bTWs t ATW WS CW 0 WS 0 minz CTXs t AX bX 0 maxy bTWs t ATW CW 0 单纯形表和对偶 2 对偶问题 原始问题 引进松弛变量 引进松弛变量 minz CTXs t AX XS bX XS 0 maxy bTWs t ATW WS CW 0 WS 0 WT CBTB 1WST CT WTA maxz CTXs t AX XS bX XS 0 maxy bTWs t ATW WS CW 0 WS 0 maxz CTXs t AX bX 0 miny bTWs t ATW CW 0 单纯形表和对偶 3 对偶问题 原始问题 引进松弛变量 引进松弛变量 maxz CTXs t AX XS bX XS 0 miny bTWs t ATW WS CW 0 WS 0 WT CBTB 1WST WTA CT maxz CTXs t AX XS bX XS 0 maxy bTWs t ATW WS CW WS 0 maxz CTXs t AX bX 0 miny bTWs t ATW CW 0 单纯形表和对偶 4 对偶问题 原始问题 引进松弛变量 引进松弛变量 maxz CTXs t AX XS bX XS 0 miny bTWs t ATW WS CW WS 0 WT CBTB 1WST WTA CT 2 对偶单纯形法 初始解原始不可行的问题 已获得最优解 x1 x2 x3 x4 x5 x6 5 7 6 0 0 0 minz 35对偶问题的最优解为 w1 w2 w3 w4 w5 w6 1 5 7 0 0 0 maxy 35 3 初始解原始 对偶都不可行的问题 解法1 先解决原始可行性 在得到原始可行解时同时得到对偶可行解 已获得最优解 x1 x2 x3 x4 x5 x6 5 7 6 0 0 0 minz 17对偶问题的最优解为 w1 w2 w3 w4 w5 w6 7 5 10 0 0 0 maxy 17 解法2 先解决对偶可行性 已得到对偶可行解 再用对偶单纯形法求解 得到原始可行解 已获得最优解 x1 x2 x3 x4 x5 x6 5 7 6 0 0 0 minz 17对偶问题的最优解为 w1 w2 w3 w4 w5 w6 7 5 10 0 0 0 maxy 17 106 2 3灵敏度分析进一步理解最优单纯形表中各元素的含义考虑问题Maxz c1x1 c2x2 cnxns t a11x1 a12x2 a1nxn b1a21x1 a22x2 a2nxn b2 am1x1 am2x2 amnxn bmx1 x2 xn 0引入m个松弛变量后 通过计算得到最优单纯形表 应 1 1能够找到最优基B的逆矩阵B 以及BN 检验数等 2 线性规划问题的进一步研究 2 3 107 2 线性规划问题的进一步研究 2 3 最优单纯形表 B 1 BT 1cB I O 108 价值系数C发生变化 m考虑检验数 j cj criarijj 1 2 ni 11 若ck是非基变量的系数 设ck变化为ck ck k ck ck criarik k ck只要 k 0 即 ck k 则最优解不变 否则 将最优单纯形表中的检验数 k用 k 取代 继续单纯形法的表格计算 例 MaxZ 2x1 3x2 4x3S t x1 2x2 x3 x4 3 2x1 x2 3x3 x5 4x1 x2 x3 x4 x5 0 2 线性规划问题的进一步研究 2 3 109 例 最优单纯形表从表中看到 3 C3 C3 C2 a13 C1 a23 可得到 C3 9 5时 原最优解不变 2 线性规划问题的进一步研究 2 3 110 2 若cs是基变量的系数 设cs变化为cs cs 那么 j cj criarij cs cs asj j csasj 对所有非基变量i s只要对所有非基变量 j 0 即 j csasj 则最优解不变 否则 将最优单纯形表中的检验数 j用 j 取代 继续单纯形法的表格计算 Max j asj asj 0 cs Min j asj asj 0 例 MaxZ 2x1 3x2 0 x3 0 x4 0 x5S t x1 2x2 x3 84x1 x4 164x2 x5 12x1 x2 x3 x4 x5 0 2 线性规划问题的进一步研究 2 3 111 例 下表为最优单纯形表 考虑基变量系数c2发生变化从表中看到 j Cj C1 a1j C5 a5j C2 C2 a2j j 3 4可得到 3 C2 1时 原最优解不变 2 线性规划问题的进一步研究 2 3 112 右端项b发生变化设分量br变化为br br 根据第1章的讨论 最优解的基变量xB B 1b 那么只要保持B 1 b b 0 则最优基不变 即基变量保持 只有值的变化 否则 需要利用对偶单纯形法继续计算 对于问题 LP Maxz cTxs t Ax bx 0最优单纯形表中含有B 1 aij i 1 m j n 1 n m那么 新的xi B 1b i brairi 1 m 由此可得 最优基不变的条件是Max bi air air 0 br Min bi air air 0 2 线性规划问题的进一步研究 2 3 113 例 上例最优单纯形表如下 00 250 这里B 1 20 51 各列分别对应b1 b2 b3的单一 0 5 0 1250 变化 因此 设b1增加4 则x1 x5 x2分别变为 4 0 4 4 4 2 4 4 0 2 0 5 4 4用对偶单纯形法进一步求解 可得 x 4 3 2 0 0 Tf 17 2 线性规划问题的进一步研究 2 3 114 增加一个变量增加变量xn 1则有相应的pn 1 cn 1 那么 计算出B 1pn 1 n 1 cn 1 criarin 1填入最优单纯形表 若 n 1 0则最优解不变 否则 进一步用单纯形法求解 例 前例增加x6 p6 2 6 3 T c6 5 计算得到 2 线性规划问题的进一步研究 2 3 用单纯形法进一步求解 可得 x 1 1 5 0 0 0 2 Tf 16 5 115 增加一个约束增加约束一个之后 应把最优解带入新的约束 若满足则最优解不变 否则填入最优单纯形表作为新的一行 引入1个新的非负变量 原约束若是小于等于形式可引入非负松弛变量 否则引入非负人工变量 并通过矩阵行变换把对应基变量的元素变为0 进一步用单纯形法或对偶单纯形法求解 例 前例增加3x1 2x2 15 原最优解不满足这个约束 于是 2 线性规划问题的进一步研究 2 3 116 A中元素发生变化 只讨论N中某一列变化情况 与增加变量xn 1的情况类似 假设pj变化 那么 重新计算出B 1pj j cj criarij填入最优单纯形表 若 j 0则最优解不变 否则 进一步用单纯形法求解 2 线性规划问题的进一步研究 2 3 可得最优解 x 3 2 0 8 0 0 2 4 Tf 15 2 117 2 线性规划问题的进一步研究 2 3 2 3灵敏度分析 内容 为重点 2 3 1Ci发生变化2 3 2Bj发生变化2 3 3增加一个变量2 3 4增加一个约束2 3 5A中元素发生变化 习题 p100习题22 4 返回目录 118 3 1运输问题模型与性质运输模型例 某公司从两个产地A1 A2将物品运往三个销地B1 B2 B3 各产地的产量 各销地的销量和各产地运往个销地每件物品的运费如下表所示 问 应如何调运可使总运输费用最小 3 运输问题 3 1 119 解 产销平衡问题 总产量 总销量设xij为从产地Ai运往销地Bj的运输量 得到下列运输量表 Minf 6x11 4x12 6x13 6x21 5x22 5x23s t x11 x12 x13 200 x21 x22 x23 300 x11 x21 150 x12 x22 150 x13 x23 200 xij 0 i 1 2 j 1 2 3 3 运输问题 3 1 120 系数矩阵 111000 000111 100100 010010 001001 特点 1 共有m n行 分别表示产地和销地 mn列分别表示各变量 2 每列只有两个1 其余为0 分别表示只有一个产地和一个销地被使用 3 运输问题 3 1 121 设xij为从产地Ai运往销地Bj的运输量 得到下列一般运输量问题的模型 mnMinf cijxiji 1j ins t xij sii 1 2 mj 1m xij djj 1 2 ni 1xij 0 i 1 2 m j 1 2 n 一般运输模型 产销平衡A1 A2 Am表示某物资的m个产地 B1 B2 Bn表示某物质的n个销地 si表示产地Ai的产量 dj表示销地Bj的销量 cij表示把物资为从产地Ai运往销地Bj的单位运价 3 运输问题 3 1续 122 3 运输问题 3 1续 变化 1 有时目标函数求最大 如求利润最大或营业额最大等 2 当某些运输线路上的能力有限制时 模型中可直接加入 等式或不等式 约束 3 产销不平衡时 可加入虚设的产地 产大于销时 或销地 销大于产时 123 3 运输问题 3 1续 求解思路是基本可行解最优否结束否换基运输问题基变量的特点 运输问题的基变量共有m n 1个 A的秩为m n 1 运输问题的m n 1个变量构成基变量的充分必要条件是不含闭回路 要弄清下列概念 闭回路 闭回路的顶点 124 3 2运输问题的表上作业法 本章重点1 初始基本可行解的确定 1 西北角法 从西北角 左上角 格开始 在格内的右下角标上允许取得的最大数 然后按行 列 标下一格的数 若某行 列 的产量 销量 已满足 则把该行 列 的其他格划去 如此进行下去 直至得到一个基本可行解 2 最小元素法 从运价最小的格开始 在格内的右下角标上允许取得的最大数 然后按运价从小到大顺序填数 若某行 列 的产量 销量 已满足 则把该行 列 的其他格划去 如此进行下去 直至得到一个基本可行解 注 应用西北角法和最小元素法 每次填完数 都只划去一行或一列 只有最后一个元例外 同时划去一行和一列 当填上一个数后行 列同时饱和时 也应任意划去一行 列 在保留的列 行 任意没被划去的格内标一个0 3 运输问题 3 2 125 3 运输问题 3 2 126 3 运输问题 3 2 127 2 最优性检验 因为求最小 当所有检验数均大于等于0时为最优解 1 位势法求检验数 位势 设对应基变量xij的m n 1个ij 存在ui vj满足ui vj cij i 1 m j 1 n 称这些ui vj为该基本可行解对应的位势 由于有m n个变量 ui vj m n 1个方程 基变量个数 故有一个自由变量 位势不唯一 利用位势求检验数 ij cij ui vji 1 m j 1 n 3 运输问题 3 2 128 前例 位势法求检验数 step1从任意基变量对应的cij开始 任取ui或vj 然后利用公式cij ui vj依次找出m n个ui vj 从c14 10开始step2计算非基变量的检验数 ij cij ui vj 填入圆圈内 3 运输问题 3 2 129 3 主元变换 1 选负检验数中最小者 rk 那么xrk为主元 作为进基变量 上页图中x24 2 以为xrk起点找一条闭回路 除xrk外其余顶点必须为基变量格 上页图中蓝色回路 3 为闭回路的每一个顶点标号 xrk为偶点 沿一个方向依次给各顶点标号 4 求 min xij xij对应闭回路上的奇数标号格 xpq那么确定xpq为出基变量 为调整量 5 对闭回路的各偶点标号顶点xij 对各奇点标号顶点xij 特别xpq 0 变为非基变量 3 运输问题 3 2 重复2 3步 直到所有检验数均非负 得到最优解 130 主元变换 由前面得到 1 于是 3 运输问题 3 2 ij 0 得到最优解x13 5 x14 2 x21 3 x24 1 x32 6 x34 3 其余xij 0 最优费用 f 3 5 10 2 1 3 8 1 4 6 5 3 85 习题 p123习题33 1 3 2 131 3 3产销不平衡的运输问题1 产量大于销量例 某公司从两个产地A1 A2将物品运往三个销地B1 B2 B3 各产地的产量 各销地的销量和各产地运往个销地每件物品的运费如下表所示 问 应如何调运可使总运输费用最小 解 增加一个虚设的销地运输费用为0 3 运输问题 3 3 132 2 销量大于产量例 某公司从两个产地A1 A2将物品运往三个销地B1 B2 B3 各产地的产量 各销地的销量和各产地运往个销地每件物品的运费如下表所示 问 应如何调运可使总运输费用最小 解 增加一个虚设的产地运输费用为0 3 运