运筹学完整版ppt课件.ppt

运筹学 OperationsResearch 经济管理学核心课程 Introduction 第一章 绪论 1 运筹学简述 2 运筹学的主要内容 3 本课程的教材及参考书 4 本课程的特点和要求 5 本课程授课方式与考核 6 运筹学在经济管理中的应用 本章主要内容 绪论 什么是运筹学 OperationalResearch运用研究 运作研究 绪论 什么是运筹学是一门应用学科 它广泛应用现有的科学技术知识和数学方法解决实际中提出的专门问题 为决策者选择最优决策提供量化依据 运筹学简述 运筹学 OperationsResearch 简写OR 系统工程的最重要的理论基础之一 在美国有人把运筹学称之为管理科学 ManagementScience 运筹学所研究的问题 可简单地归结为一句话 依照给定条件和目标 从众多方案中选择最佳方案 故有人称之为最优化技术 绪论 运筹学的历史与发展 运筹学思想的出现可以追溯到很早 田忌赛马 齐王要与大臣田忌赛马 双方各出上 中 下马各一匹 对局三次 每次胜负1000金 田忌在好友 著名的军事谋略家孙膑的指导下 以以下安排 齐王上中下田忌下上中 绪论 丁谓的皇宫修复工程北宋年间 丁谓负责修复火毁的开封皇宫 他的施工方案是 先将皇宫前的一条大街挖成一条大沟 将大沟与汴水相通 使用挖出的土就地制砖 令与汴水相连形成的河道承担繁重的运输任务 修复工程完成后 实施大沟排水 并将原废墟物回填 修复成原来的大街 丁谓将取材 运输及清废用 一沟三用 巧妙地解决了 体现了系统规划的思想 绪论 国际上运筹学的思想可追溯到1914年 当时的兰彻斯特提出了军事运筹学的作战模型 1917年 丹麦工程师埃尔朗在研究自动电话系统中通话线路与用户呼叫的数量关系问题时 提出了埃尔朗公式 研究了随机服务系统中的系统排队与系统拥挤问题 存储论的最优批量公式是在20世纪20年代初提出的 运筹学简述 运作研究 OperationalResearch 小组 解决复杂的战略和战术问题 例如 如何合理运用雷达有效地对付德军德空袭对商船如何进行编队护航 使船队遭受德国潜艇攻击时损失最少 在各种情况下如何调整反潜深水炸弹的爆炸深度 才能增加对德国潜艇的杀伤力等 绪论 在生产管理方面的应用 最早是1939年前苏联的康特洛为奇提出了生产组织与计划中的线性规划问题 并给出解乘数法的求解方法 出版了第一部关于线性规划的著作 生产组织与计划中的数学方法 但当时并没有引起重视 直到1960年康特洛为奇再次出版了 最佳资源利用的经济计算 才受到国内外的一致重视 为此康特洛为奇获得了诺贝尔经济学奖 线性规划提出后很快受到经济学家的重视 如 二次世界大战中从事运输模型研究的美国经济学家库普曼斯 T C Koopmans 他很快看到了线性规划在经济中应用的意义 并呼吁年轻的经济学家要关注线性规划 其中阿罗 萨谬尔逊 西蒙 多夫曼和胡尔威茨等都获得了诺贝尔奖 绪论 20世纪50年代中期 钱学森 许国志等教授在国内全面介绍和推广运筹学知识 1956年 中国科学院成立第一个运筹学研究室 1957年运筹学运用到建筑和纺织业中 1958年提出了图上作业法 山东大学的管梅谷教授提出了 中国邮递员问题 1970年 在华罗庚教授的直接指导下 在全国范围内推广统筹方法和优选法 1978年11月 在成都召开了全国数学年会 对运筹学的理论与应用研究进行了一次检阅 1980年4月在山东济南正式成立了 中国数学会运筹学会 1984年在上海召开了 中国数学会运筹学会第二届代表大会暨学术交流会 并将学会改名为 中国运筹学会 绪论 成熟的学科分支向纵深发展新的研究领域产生与新的技术结合与其他学科的结合加强传统优化观念不断变化 运筹学的发展趋势 运筹学的主要内容 数学规划 线性规划 整数规划 目标规划 动态规划等 图论存储论排队论对策论排序与统筹方法决策分析 运筹学的主要内容 1 线性规划 LinearProgram 是一个成熟的分支 它有效的算法 单纯形法 主要解决生产计划问题 合理下料问题 最优投资问题 2 整数规划 IntegrateProgram 在线性规划的基础上 变量加上整数约束 3 非线性规划 NonlinearProgram 目标函数和约束条件是非线性函数 如证券投资组合优化 如何合理投资使风险最小 4 动态规划 DynamicProgram 多阶段决策问题 是美国贝尔曼于1951年提出的 运筹学的主要内容 5 图与网络 GraphTheoryandNetwork 中国邮递员问题 哥尼斯堡城问题 最短路 最大流问题 6 存储论 InventoryTheory 主要解决生产中的库存问题 订货周期和订货量等问题 7 排队论 QueueTheory 主要研究排队系统中的系统排队和系统拥挤现象 从而评估系统的服务质量 8 对策论 GameTheory 主要研究具有斗争性质的优化问题 9 决策分析 DecisionAnalysis 主要研究定量化决策 本课程的教材及参考书 选用教材 运筹学教程 胡运权主编 第3版 清华出版社参考教材 运筹学基础及应用 胡运权主编哈工大出版社 管理运筹学 韩伯棠主编 第2版 高等教育出版社 运筹学 修订版 钱颂迪主编清华出版社 本课程的特点和要求 先修课 高等数学 基础概率 线性代数特点 系统整体优化 多学科的配合 模型方法的应用运筹学的研究的主要步骤 本课程授课方式与考核 讲授为主 结合习题作业 运筹学在经济管理中的应用 运筹学在经济管理中的应用涉及的方面 生产计划运输问题人事管理库存管理市场营销财务和会计物流配送另外 还应用于设备维修 更新和可靠性分析 项目的选择与评价 工程优化设计等 管理运筹学 软件介绍 管理运筹学 2 0版包括 线性规划 运输问题 整数规划 0 1整数规划 纯整数规划和混合整数规划 目标规划 对策论 最短路径 最小生成树 最大流量 最小费用最大流 关键路径 存储论 排队论 决策分析 预测问题和层次分析法 共15个子模块 线性规划及单纯形法 LinearProgramming 第一章 Chapter1线性规划 LinearProgramming LP的数学模型图解法单纯形法单纯形法的进一步讨论 人工变量法LP模型的应用 本章主要内容 线性规划问题的数学模型 1 规划问题 生产和经营管理中经常提出如何合理安排 使人力 物力等各种资源得到充分利用 获得最大的效益 这就是规划问题 线性规划通常解决下列两类问题 1 当任务或目标确定后 如何统筹兼顾 合理安排 用最少的资源 如资金 设备 原标材料 人工 时间等 去完成确定的任务或目标 2 在一定的资源条件限制下 如何组织安排生产获得最好的经济效益 如产品量最多 利润最大 线性规划问题的数学模型 例1 1如图所示 如何截取x使铁皮所围成的容积最大 线性规划问题的数学模型 例1 2某厂生产两种产品 下表给出了单位产品所需资源及单位产品利润 问 应如何安排生产计划 才能使总利润最大 解 1 决策变量 设产品I II的产量分别为x1 x2 2 目标函数 设总利润为z 则有 maxz 2x1 x2 3 约束条件 线性规划问题的数学模型 例1 3已知资料如下表所示 问如何安排生产才能使利润最大 或如何考虑利润大 产品好销 解 1 决策变量 设产品I II的产量分别为x1 x2 2 目标函数 设总利润为z 则有 maxz 2x1 x2 3 约束条件 线性规划问题的数学模型 例1 4某厂生产三种药物 这些药物可以从四种不同的原料中提取 下表给出了单位原料可提取的药物量 解 要求 生产A种药物至少160单位 B种药物恰好200单位 C种药物不超过180单位 且使原料总成本最小 1 决策变量 设四种原料的使用量分别为 x1 x2 x3 x4 2 目标函数 设总成本为zminz 5x1 6x2 7x3 8x4 3 约束条件 例1 5某航运局现有船只种类 数量以及计划期内各条航线的货运量 货运成本如下表所示 问 应如何编队 才能既完成合同任务 又使总货运成本为最小 线性规划问题的数学模型 解 设 xj为第j号类型船队的队数 j 1 2 3 4 z为总货运成本 则 minz 36x1 36x2 72x3 27x4 线性规划问题的数学模型 线性规划问题的数学模型 2 线性规划的数学模型由三个要素构成 决策变量Decisionvariables目标函数Objectivefunction约束条件Constraints 其特征是 1 问题的目标函数是多个决策变量的线性函数 通常是求最大值或最小值 2 问题的约束条件是一组多个决策变量的线性不等式或等式 怎样辨别一个模型是线性规划模型 线性规划问题的数学模型 3 建模条件 1 优化条件 问题所要达到的目标能用线型函数描述 且能够用极值 max或min 来表示 2 限定条件 达到目标受到一定的限制 且这些限制能够用决策变量的线性等式或线性不等式表示 3 选择条件 有多种可选择的方案供决策者选择 以便找出最优方案 线性规划问题的数学模型 4 建模步骤 1 确定决策变量 即需要我们作出决策或选择的量 一般情况下 题目问什么就设什么为决策变量 2 找出所有限定条件 即决策变量受到的所有的约束 3 写出目标函数 即问题所要达到的目标 并明确是max还是min 线性规划问题的数学模型 目标函数 约束条件 5 线性规划数学模型的一般形式 简写为 线性规划问题的数学模型 向量形式 其中 线性规划问题的数学模型 矩阵形式 其中 线性规划问题的数学模型 6 线性规划问题的标准形式 特点 1 目标函数求最大值 有时求最小值 2 约束条件都为等式方程 且右端常数项bi都大于或等于零 3 决策变量xj为非负 线性规划问题的数学模型 2 如何化标准形式 目标函数的转换 如果是求极小值即 则可将目标函数乘以 1 可化为求极大值问题 也就是 令 可得到上式 即 若存在取值无约束的变量 可令其中 变量的变换 线性规划问题的数学模型 约束方程的转换 由不等式转换为等式 称为松弛变量 称为剩余变量 常量bi 0的变换 约束方程两边乘以 1 线性规划问题的数学模型 例1 6将下列线性规划问题化为标准形式 用替换 且 解 因为x3无符号要求 即x3取正值也可取负值 标准型中要求变量非负 所以 线性规划问题的数学模型 2 第一个约束条件是 号 在 左端加入松驰变量x4 x4 0 化为等式 3 第二个约束条件是 号 在 左端减去剩余变量x5 x5 0 4 第3个约束方程右端常数项为 5 方程两边同乘以 1 将右端常数项化为正数 5 目标函数是最小值 为了化为求最大值 令z z 得到maxz z 即当z达到最小值时z 达到最大值 反之亦然 线性规划问题的数学模型 标准形式如下 例1 7将下列线性规划问题化为标准形式 为无约束 无非负限制 线性规划问题的数学模型 解 用替换 且 将第3个约束方程两边乘以 1 将极小值问题反号 变为求极大值 标准形式如下 引入变量 线性规划问题的数学模型 例1 8将线性规划问题化为标准型 解 线性规划问题的数学模型 例1 9将线性规划问题化为标准型 解 Minf 3x1 5x2 8x3 7x4s t 2x1 3x2 5x3 6x4 284x1 2x2 3x3 9x4 396x2 2x3 3x4 58x1 x3 x4 0 x2无约束 Maxz 3x1 5x2 5x2 8x3 7x4s t 2x1 3x2 3x2 5x3 6x4 x5 284x1 2x2 2x2 3x3 9x4 x6 39 6x2 6x2 2x3 3x4 x7 58x1 x2 x2 x3 x4 x5 x6 x7 0 线性规划问题的数学模型 线性规划问题的数学模型 7 线性规划问题的解 线性规划问题 求解线性规划问题 就是从满足约束条件 2 3 的方程组中找出一个解 使目标函数 1 达到最大值 线性规划问题的数学模型 可行解 满足约束条件 的解为可行解 所有可行解的集合为可行域 最优解 使目标函数达到最大值的可行解 基 设A为约束条件 的m n阶系数矩阵 m n 其秩为m B是矩阵A中m阶满秩子矩阵 B 0 称B是规划问题的一个基 设 称B中每个列向量Pj j 12 m 为基向量 与基向量Pj对应的变量xj为基变量 除基变量以外的变量为非基变量 线性规划问题的数学模型 基解 某一确定的基B 令非基变量等于零 由约束条件方程 解出基变量 称这组解为基解 在基解中变量取非0值的个数不大于方程数m 基解的总数不超过基可行解 满足变量非负约束条件的基本解 简称基可行解 可行基 对应于基可行解的基称为可行基 线性规划问题的数学模型 例1 10求线性规划问题的所有基矩阵 解 约束方程的系数矩阵为2 5矩阵 r A 2 2阶子矩阵有10个 其中基矩阵只有9个 即 图解法 线性规划问题的求解方法 一般有两种方法 图解法单纯形法 两个变量 直角坐标三个变量 立体坐标 适用于任意变量 但必需将一般形式变成标准形式 下面我们分析一下简单的情况 只有两个决策变量的线性规划问题 这时可以通过图解的方法来求解 图解法具有简单 直观 便于初学者窥探线性规划基本原理和几何意义等优点 解题步骤 4将最优解代入目标函数 求出最优值 1在直角平面坐标系中画出所有的约束等式 并找出所有约束条件的公共部分 称为可行域 可行域中的点称为可行解 2标出目标函数值增加或者减小的方向 3若求最大 小 值 则令目标函数等值线沿 逆 目标函数值增加的方向平行移动 找与可行域最后相交的点 该点就是最优解 图解法 图解法 maxZ 2X1 X2X1 1 9X2 3 8X1 1 9X2 3 8s t X1 1 9X2 10 2X1 1 9X2 3 8X1 X2 0 例1 11用图解法求解线性规划问题 图解法 x1 x2 o X1 1 9X2 3 8 X1 1 9X2 3 8 X1 1 9X2 3 8 X1 1 9X2 10 2 4 2X1 X2 20 2X1 X2 17 2 2X1 X2 11 2X1 X2 Lo 0 2X1 X2 7 6 2 D maxZ minZ 此点是唯一最优解 且最优目标函数值maxZ 17 2 可行域 maxZ 2X1 X2 图解法 maxZ 3X1 5 7X2 x1 x2 o X1 1 9X2 3 8 X1 1 9X2 3 8 X1 1 9X2 3 8 X1 1 9X2 10 2 7 6 2 D L0 0 3X1 5 7X2 maxZ 3 8 4 34 2 3X1 5 7X2 蓝色线段上的所有点都是最优解这种情形为有无穷多最优解 但是最优目标函数值maxZ 34 2是唯一的 可行域 图解法 minZ 5X1 4X2 x1 x2 o X1 1 9X2 3 8 X1 1 9X2 3 8 X1 1 9X2 10 2 D L0 0 5X1 4X2 maxZ minZ 8 5X1 4X2 43 5X1 4X2 0 2 可行域 此点是唯一最优解 图解法 2 4 6 x1 x2 2 4 6 无界解 无最优解 maxZ x1 2x2 例1 6 x1 x2 4 x1 3x2 6 3x1 x2 6 maxZ minZ x1 x2 O 10 20 30 40 10 20 30 40 50 50 无可行解 即无最优解 maxZ 3x1 4x2 例1 7 由图解法得到的几种情况 根据以上例题 进一步分析讨论可知线性规划的可行域和最优解有以下几种可能的情况 1 可行域为封闭的有界区域 a 有唯一的最优解 b 有无穷多个最优解 2 可行域为封闭的无界区域 c 有唯一的最优解 d 有无穷多个最优解 e 目标函数无界 即虽有可行解 但在可行域中 目标函数可以无限增大或无限减少 因而没有有限最优解 3 可行域为空集 f 没有可行解 原问题无最优解 图解法 由图解法得到的启示 1 线性规划问题解的情况 唯一最优解 无穷多最优解 无界解 无可行解 3 最优解一定是在凸集的某个顶点 2 线性规划问题的可行域是凸集 凸多边形 4 解题思路是 先找出凸集的任一顶点 计算其目标函数值 再与周围顶点的目标函数值比较 如不是最大 继续比较 直到找出最大为止 图解法 图解法 学习要点 1 通过图解法了解线性规划有几种解的形式 唯一最优解 无穷多最优解 无界解 无可行解 2 作图的关键有三点 1 可行解区域要画正确 2 目标函数增加的方向不能画错 3 目标函数的直线怎样平行移动 连接几何形体中任意两点的线段仍完全在该几何形体之中 有限个凸集的交集仍然是凸集 单纯形法基本原理 单纯形法基本原理 凸集 如果集合C中任意两个点X1 X2 其连线上的所有点也都是集合C中的点 称C为凸集 顶点 如果凸集C中不存在任何两个不同的点X1 X2 使X成为这两个点连线上的一个点 单纯形法基本原理 定理1 若线性规划问题存在可行解 则该问题的可行域是凸集 定理2 线性规划问题的基可行解X对应可行域 凸集 的顶点 定理3 若问题存在最优解 一定存在一个基可行解是最优解 或在某个顶点取得 单纯形法的计算步骤 单纯形法的思路 找出一个初始可行解 是否最优 转移到另一个基本可行解 找出更大的目标函数值 最优解 是 否 循环 核心是 变量迭代 结束 单纯形法的计算步骤 单纯形表 单纯形法的计算步骤 例1 12用单纯形法求下列线性规划的最优解 解 1 将问题化为标准型 加入松驰变量x3 x4则标准型为 单纯形法的计算步骤 2 求出线性规划的初始基可行解 列出初始单纯形表 检验数 单纯形法的计算步骤 3 进行最优性检验 如果表中所有检验数 则表中的基可行解就是问题的最优解 计算停止 否则继续下一步 4 从一个基可行解转换到另一个目标值更大的基可行解 列出新的单纯形表 确定换入基的变量 选择 对应的变量xj作为换入变量 当有一个以上检验数大于0时 一般选择最大的一个检验数 即 其对应的xk作为换入变量 确定换出变量 根据下式计算并选择 选最小的 对应基变量作为换出变量 单纯形法的计算步骤 用换入变量xk替换基变量中的换出变量 得到一个新的基 对应新的基可以找出一个新的基可行解 并相应地可以画出一个新的单纯形表 5 重复3 4 步直到计算结束为止 单纯形法的计算步骤 换入列 bi ai2 ai2 0 40 10 换出行 将3化为1 5 3 1 18 0 1 3 0 1 3 10 1 1 3 30 30 0 5 3 0 4 3 乘以1 3后得到 1 0 3 5 1 5 18 0 1 1 5 2 5 4 0 0 1 1 单纯形法的计算步骤 例1 13用单纯形法求解 解 将数学模型化为标准形式 不难看出x4 x5可作为初始基变量 列单纯形表计算 单纯形法的计算步骤 20 x2 2 1 3 1 5 0 1 20 75 3 0 17 1 3 1 3 0 9 0 2 25 60 x1 1 1 0 17 3 1 3 1 25 0 1 28 9 1 9 2 3 35 3 0 0 98 9 1 9 7 3 变成标准型 单纯形法的计算步骤 例1 14用单纯形法求解 约束方程的系数矩阵 为基变量 为非基变量 I为单位矩阵且线性独立 单纯形法的计算步骤 单纯形法的计算步骤 单纯形法的计算步骤 学习要点 1 线性规划解的概念以及3个基本定理2 熟练掌握线性规划问题的标准化3 熟练掌握单纯形法的解题思路及求解步骤 单纯形法的进一步讨论 人工变量法 人工变量法 前面讨论了在标准型中系数矩阵有单位矩阵 很容易确定一组基可行解 在实际问题中有些模型并不含有单位矩阵 为了得到一组基向量和初基可行解 在约束条件的等式左端加一组虚拟变量 得到一组基变量 这种人为加的变量称为人工变量 构成的可行基称为人工基 用大M法或两阶段法求解 这种用人工变量作桥梁的求解方法称为人工变量法 单纯形法的进一步讨论 人工变量法 例1 10用大M法解下列线性规划 解 首先将数学模型化为标准形式 系数矩阵中不存在单位矩阵 无法建立初始单纯形表 单纯形法的进一步讨论 人工变量法 故人为添加两个单位向量 得到人工变量单纯形法数学模型 其中 M是一个很大的抽象的数 不需要给出具体的数值 可以理解为它能大于给定的任何一个确定数值 再用前面介绍的单纯形法求解该模型 计算结果见下表 单纯形法的进一步讨论 人工变量法 单纯形法的进一步讨论 人工变量法 例1 11用大M法解下列线性规划 解 首先将数学模型化为标准形式 系数矩阵中不存在单位矩阵 无法建立初始单纯形表 单纯形法的进一步讨论 人工变量法 故人为添加两个单位向量 得到人工变量单纯形法数学模型 其中 M是一个很大的抽象的数 不需要给出具体的数值 可以理解为它能大于给定的任何一个确定数值 再用前面介绍的单纯形法求解该模型 计算结果见下表 单纯形法的进一步讨论 人工变量法 单纯形法的进一步讨论 人工变量法 单纯形法的进一步讨论 两阶段法 用计算机处理数据时 只能用很大的数代替M 可能造成计算机上的错误 故多采用两阶段法 第一阶段 在原线性规划问题中加入人工变量 构造如下模型 对上述模型求解 单纯形法 若 0 说明问题存在基可行解 可以进行第二个阶段 否则 原问题无可行解 停止运算 单纯形法的进一步讨论 两阶段法 第一阶段的线性规划问题可写为 第一阶段单纯形法迭代的过程见下表 注意 没有化为极大化问题 单纯形法的进一步讨论 两阶段法 单纯形法的进一步讨论 两阶段法 第二阶段 在第一阶段的最终表中 去掉人工变量 将目标函数的系数换成原问题的目标函数系数 作为第二阶段计算的初始表 用单纯形法计算 例 单纯形法的进一步讨论 两阶段法 第二阶段 最优解为 41900 目标函数Z 2 单纯形法的进一步讨论 通过大 法或两阶段法求初始的基本可行解 但是如果在大 法的最优单纯形表的基变量中仍含有人工变量 或者两阶段法的辅助线性规划的目标函数的极小值大于零 那么该线性规划就不存在可行解 无可行解 C 3 2 1000 M M CB XB b x1x2x3x4x5x6x7x8 0 M M x4x7x8 643 1111000010 10 101001 100 101 6 1 3 1 Z 7M 6 4M 15 M 3 M 2 M 1 2M0 M M00 0 M 2 x4x7x2 343 1021010 110 10 101001 100 101 3 14 1 Z Z 3 M0 3 M0 M 202 M 3 M 2 x1x7x2 313 1021010 100 3 1 1 11101 100 101 003 3M3 M M1 M0 1 例 单纯形法的进一步讨论 运算到检验数全负为止 仍含有人工变量 无可行解 单纯形法的进一步讨论 无最优解与无可行解时两个不同的概念 无可行解是指原规划不存在可行解 从几何的角度解释是指线性规划问题的可行域为空集 无最优解则是指线性规划问题存在可行解 但是可行解的目标函数达不到最优值 即目标函数在可行域内可以趋于无穷大 或者无穷小 无最优解也称为有限最优解 或无界解 判别方法 无最优解判别定理在求解极大化的线性规划问题过程中 若某单纯形表的检验行存在某个大于零的检验数 但是该检验数所对应的非基变量的系数列向量的全部系数都为负数或零 则该线性规划问题无最优解 无最优解 因但所以原问题无最优解 单纯形法的进一步讨论 退化 即计算出的 用于确定换出变量 存在有两个以上相同的最小比值 会造成下一次迭代中由一个或几个基变量等于零 这就是退化 会产生退化解 为避免出现计算的循环 勃兰特 Bland 提出一个简便有效的规则 摄动法原理 当存在多个时 选下标最小的非基变量为换入变量 2 当 值出现两个以上相同的最小值时 选下标最小的基变量为换出变量 单纯形法的进一步讨论 0 0 0 24 2 80 3 0 Z 5 6 0 42 0 8 0 5 Z 1 0 0 0 1 0 0 1 x3 2 1 2 0 6 0 24 1 1 x1 3 3 2 1 30 0 8 0 3 x5 0 0 3 0 42 5 8 0 0 Z 1 1 0 0 1 0 0 1 x7 0 0 1 0 6 1 24 1 0 x1 3 0 1 1 30 3 8 0 0 x5 0 1 1 0 0 1 0 0 1 x7 0 0 0 1 0 6 1 24 1 0 x6 0 0 0 0 1 36 4 32 1 0 x5 0 x7 x6 x5 x4 x3 x2 x1 b XB CB 0 0 0 24 2 80 3 C 第一次迭代中使用了摄动法原理 选择下标为6的基变量x6离基 可得最优解maxZ 单纯形法的进一步讨论 无穷多最优解 若线性规划问题某个基本可行解所有的非基变量检验数都小于等于零 但其中存在一个检验数等于零 那么该线性规划问题有无穷多最优解 例 最优表 非基变量检验数 所以有无穷多最优解 单纯形法的进一步讨论 单纯形法的进一步讨论 解的判别 1 唯一最优解判别 最优表中所有非基变量的检验数非零 则线性规划具有唯一最优解 2 多重最优解判别 最优表中存在非基变量的检验数为零 则线性规划具有多重最优解 或无穷多最优解 3 无界解判别 某个 k 0且aik i 1 2 m 则线性规划具有无界解 4 无可行解的判断 当用大M单纯形法计算得到最优解并且存在Ri 0时 则表明原线性规划无可行解 5 退化解的判别 存在某个基变量为零的基本可行解 单纯形法的进一步讨论 单纯性法小结 A 线性规划模型的应用 一般而言 一个经济 管理问题凡是满足以下条件时 才能建立线性规划模型 要求解问题的目标函数能用数值指标来反映 且为线性函数存在着多种方案要求达到的目标是在一定条件下实现的 这些约束可用线性等式或不等式描述 线性规划模型的应用 常见问题 合理利用线材问题 如何下料使用材最少 配料问题 在原料供应量的限制下如何获取最大利润 投资问题 从投资项目中选取方案 使投资回报最大 产品生产计划 合理利用人力 物力 财力等 使获利最大 劳动力安排 用最少的劳动力来满足工作的需要 运输问题 如何制定调运方案 使总运费最小 线性规划模型的应用 1 设立决策变量 2 明确约束条件并用决策变量的线性等式或不等式表示 3 用决策变量的线性函数表示目标 并确定是求极大 Max 还是极小 Min 4 根据决策变量的物理性质研究变量是否有非负性 建立线性规划模型的过程可以分为四个步骤 线性规划在经济管理中的应用 1 资源的合理利用 某厂计划在下一生产周期内生产B1 B2 Bn种产品 要消耗A1 A2 Am种资源 已知每件产品所消耗的资源数 每种资源的数量限制以及每件产品可获得的利润如表所示 问如何安排生产计划 才能充分利用现有的资源 使获得的总利润最大 线性规划在经济管理中的应用 2 生产组织与计划问题 某工厂用机床A1 A2 Am加工B1 B2 Bn种零件 在一个周期内 各机床可能工作的机时 台时 工厂必须完成各种零件的数量 各机床加工每个零件的时间 机时 个 和加工每个零件的成本 元 个 如表所示 问如何安排各机床的生产任务 才能完成加工任务 又使总成本最低 线性规划在经济管理中的应用 某厂生产 三种产品 都分别经A B两道工序加工 设A工序可分别在设备A1和A2上完成 有B1 B2 B3三种设备可用于完成B工序 已知产品 可在A B任何一种设备上加工 产品 可在任何规格的A设备上加工 但完成B工序时 只能在B1设备上加工 产品 只能在A2与B2设备上加工 加工单位产品所需工序时间及其他各项数据如下表 试安排最优生产计划 使该厂获利最大 线性规划在经济管理中的应用 线性规划在经济管理中的应用 解 设xijk表示产品i在工序j的设备k上加工的数量 约束条件有 线性规划在经济管理中的应用 线性规划在管理中的应用 目标是利润最大化 即利润的计算公式如下 带入数据整理得到 线性规划在管理中的应用 因此该规划问题的模型为 线性规划在经济管理中的应用 例 现有一批某种型号的圆钢长8米 需要截取2 5米长的毛坯100根 长1 3米的毛坯200根 问如何才能既满足需要 又能使总的用料最少 解 为了找到一个省料的套裁方案 必须先设计出较好的几个下料方案 其次要求这些方案的总体能裁下所有各种规格的圆钢 以满足对各种不同规格圆钢的需要并达到省料的目的 为此可以设计出4种下料方案以供套裁用 3 合理下料问题 线性规划在管理中的应用 设按方案 下料的原材料根数分别为xj j 1 2 3 4 可列出下面的数学模型 线性规划在经济管理中的应用 4 合理配料问题 某饲养场用n种饲料B1 B2 Bn配置成含有m种营养成分A1 A2 Am的混合饲料 其余资料如表所示 问应如何配料 才能既满足需要 又使混合饲料的总成本最低 解 线性规划在管理中的应用 例 某人每天食用甲 乙两种食物 如猪肉 鸡蛋 其资料如下 问两种食物各食用多少 才能既满足需要 又使总费用最省 线性规划在管理中的应用 解 设Xj表示Bj种食物用量 线性规划在管理中的应用 5 人力资源分配问题 例1 11某昼夜服务的公交线路每天各时间段内所需司机和乘务人员人数如下表所示 设司机和乘务人员分别在各时间段开始时上班 并连续工作8小时 问该公交线路应怎样安排司机和乘务人员 即能满足工作需要 又使配备司机和乘务人员的人数减少 线性规划在管理中的应用 解 设xi表示第i班次时开始上班的司机和乘务人员人数 此问题最优解 x1 50 x2 20 x3 50 x4 0 x5 20 x6 10 一共需要司机和乘务员150人 Chapter2对偶理论 DualityTheory 线性规划的对偶模型对偶性质对偶问题的经济解释 影子价格对偶单纯形法灵敏度分析 本章主要内容 线性规划的对偶模型 设某工厂生产两种产品甲和乙 生产中需4种设备按A B C D顺序加工 每件产品加工所需的机时数 每件产品的利润值及每种设备的可利用机时数列于下表 产品数据表 问 充分利用设备机时 工厂应生产甲和乙型产品各多少件才能获得最大利润 1 对偶问题的提出 线性规划的对偶模型 解 设甲 乙型产品各生产x1及x2件 则数学模型为 反过来问 若厂长决定不生产甲和乙型产品 决定出租机器用于接受外加工 只收加工费 那么 种机器的机时如何定价才是最佳决策 线性规划的对偶模型 在市场竞争的时代 厂长的最佳决策显然应符合两条 1 不吃亏原则 即机时定价所赚利润不能低于加工甲 乙型产品所获利润 由此原则 便构成了新规划的不等式约束条件 2 竞争性原则 即在上述不吃亏原则下 尽量降低机时总收费 以便争取更多用户 设A B C D设备的机时价分别为y1 y2 y3 y4 则新的线性规划数学模型为 线性规划的对偶模型 把同种问题的两种提法所获得的数学模型用表2表示 将会发现一个有趣的现象 原问题与对偶问题对比表 对偶性是线性规划问题的最重要的内容之一 每一个线性规划 LP 必然有与之相伴而生的另一个线性规划问题 即任何一个求maxZ的LP都有一个求minZ的LP 其中的一个问题叫 原问题 记为 P 另一个称为 对偶问题 记为 D 线性规划的对偶模型 2 原问题与对偶问题的对应关系 原问题 P 对偶问题 D 线性规划的对偶模型 线性规划的对偶模型 1 对称形式 特点 目标函数求极大值时 所有约束条件为 号 变量非负 目标函数求极小值时 所有约束条件为 号 变量非负 线性规划的对偶模型 例2 1写出线性规划问题的对偶问题 解 首先将原问题变形为对称形式 注意 以后不强调等式右段项b 0 原因在对偶单纯型表中只保证而不保证 故b可以是负数 线性规划的对偶模型 线性规划的对偶模型 2 非对称型对偶问题 若给出的线性规划不是对称形式 可以先化成对称形式再写对偶问题 也可直接按教材表2 2中的对应关系写出非对称形式的对偶问题 线性规划的对偶模型 线性规划的对偶模型 例2 2写出下列线性规划问题的对偶问题 解 原问题的对偶问题为 无约束 线性规划的对偶模型 例2 3写出下列线性规划问题的对偶问题 解 原问题的对偶问题为 线性规划的对偶模型 例2 4 线性规划的对偶模型 对偶性质 性质1对称性定理 对偶问题的对偶是原问题 minZ CXs t AX bX 0 maxW Ybs t YA CY 0 对偶性质 性质2弱对偶原理 弱对偶性 设和分别是问题 P 和 D 的可行解 则必有 推论1 原问题任一可行解的目标函数值是其对偶问题目标函数值的下界 反之 对偶问题任意可行解的目标函数值是其原问题目标函数值的上界 推论2 在一对对偶问题 P 和 D 中 若其中一个问题可行但目标函数无界 则另一个问题无可行解 反之不成立 这也是对偶问题的无界性 对偶性质 例2 5 对偶性质 推论3 在一对对偶问题 P 和 D 中 若一个可行 如P 而另一个不可行 如D 则该可行的问题目标函数值无界 试估计它们目标函数的界 并验证弱对偶性原理 P 例2 6 对偶性质 解 D 对偶性质 性质3最优性定理 如果是原问题的可行解 是其对偶问题的可行解 并且 则是原问题的最优解 是其对偶问题的最优解 例如 在一对对偶问题 P 和 D 中 可找到X 0 0 4 4 Y 1 2 0 2 且Z W28 则X Y 分别是P和D的最优解 对偶性质 性质4强对偶性 若原问题及其对偶问题均具有可行解 则两者均具有最优解 且它们最优解的目标函数值相等 还可推出另一结论 若 LP 与 DP 都有可行解 则两者都有最优解 若一个问题无最优解 则另一问题也无最优解 性质5互补松弛性 设X0和Y0分别是P问题和D问题的可行解 则它们分别是最优解的充要条件是 其中 Xs Ys为松弛变量 对偶性质 性质5的应用 该性质给出了已知一个问题最优解求另一个问题最优解的方法 即已知Y 求X 或已知X 求Y 互补松弛条件 由于松弛变量都非负 要使求和式等于零 则必定每一分量为零 因而有下列关系 若Y 0 则Xs必为0 若X 0 则Ys必为0利用上述关系 建立对偶问题 或原问题 的约束线性方程组 方程组的解即为最优解 对偶性质 例2 7已知线性规划 的最优解是X 6 2 0 T 求其对偶问题的最优解Y 解 写出原问题的对偶问题 即 标准化 对偶性质 设对偶问题最优解为Y y1 y2 由互补松弛性定理可知 X 和Y 满足 即 因为X1 6 0 X2 2 0 所以对偶问题的第一 二个约束的松弛变量等于零 即y3 0 y4 0 带入方程中 解此线性方程组得y1 1 y2 1 从而对偶问题的最优解为 Y 1 1 最优值w 26 对偶性质 例2 8已知线性规划 的对偶问题的最优解为Y 0 2 求原问题的最优解 解 对偶问题是 标准化 无约束 对偶性质 设对偶问题最优解为X x1 x2 x3 T 由互补松弛性定理可知 X 和Y 满足 将Y 0 2 带入由方程可知 y3 y5 0 y4 1 y2 2 0 x5 0又 y4 1 0 x2 0 将x2 x5分别带入原问题约束方程中 得 解方程组得 x1 5 x3 1 所以原问题的最优解为 X 5 0 1 最优值z 12 对偶性质 原问题与对偶问题解的对应关系小结 对偶问题的经济解释 影子价格 1 影子价格的数学分析 定义 在一对P和D中 若P的某个约束条件的右端项常数bi 第i种资源的拥有量 增加一个单位时 所引起目标函数最优值z 的改变量称为第i种资源的影子价格 其值等于D问题中对偶变量yi 由对偶问题得基本性质可得 对偶问题的经济解释 影子价格 2 影子价格的经济意义1 影子价格是一种边际价格在其它条件不变的情况下 单位资源数量的变化所引起的目标函数最优值的变化 即对偶变量yi就是第i种资源的影子价格 即 对偶问题的经济解释 影子价格 2 影子价格是一种机会成本影子价格是在资源最优利用条件下对单位资源的估价 这种估价不是资源实际的市场价格 因此 从另一个角度说 它是一种机会成本 若第i种资源的单位市场价格为mi 则有当yi mi时 企业愿意购进这种资源 单位纯利为yi mi 则有利可图 如果yi mi 则企业有偿转让这种资源 可获单位纯利mi yi 否则 企业无利可图 甚至亏损 结论 若yi mi则购进资源i 可获单位纯利yi mi若yi mi则转让资源i 可获单位纯利mi yi 对偶问题的经济解释 影子价格 3 影子价格在资源利用中的应用根据对偶理论的互补松弛性定理 Y Xs 0 YsX 0表明生产过程中如果某种资源bi未得到充分利用时 该种资源的影子价格为0 若当资源资源的影子价格不为0时 表明该种资源在生产中已耗费完 对偶问题的经济解释 影子价格 4 影子价格对单纯形表计算的解释 单纯形表中的检验数 其中cj表示第j种产品的价格 表示生产该种产品所消耗的各项资源的影子价格的总和 即产品的隐含成本 当产值大于隐含成本时 即 表明生产该项产品有利 可在计划中安排 否则 用这些资源生产别的产品更有利 不在生产中安排该产品 对偶单纯形法 对偶单纯形法是求解线性规划的另一个基本方法 它是根据对偶原理和单纯形法原理而设计出来的 因此称为对偶单纯形法 不要简单理解为是求解对偶问题的单纯形法 对偶单纯形法原理 对偶单纯形法基本思路 找出一个对偶问题的可行基 保持对偶问题为可行解的条件下 判断XB是否可行 XB b为非负 有最优解 否则 通过变换基解 直到找到原问题基可行解 即XB为非负 这时原问题与对偶问题同时达到可行解 由定理4可得 对偶单纯形法 找出一个DP的可行基 LP是否可行 XB 0 保持DP为可行解情况下转移到LP的另一个基本解 最优解 是 否 循环 结束 对偶单纯形法 例2 9用对偶单纯形法求解 解 1 将模型转化为求最大化问题 约束方程化为等式求出一组基本解 因为对偶问题可行 求max问题 对偶单纯形法 对偶单纯形法 对偶单纯形法 原问题的最优解为 X 2 2 2 0 0 0 Z 72由定理4 其对偶问题的最优解为 Y 1 3 3 7 3 W 72 对偶单纯形法 对偶单纯形法应注意的问题 用对偶单纯形法求解线性规划是一种求解方法 而不是去求对偶问题的最优解 初始表中一定要满足对偶问题可行 也就是说检验数满足最优判别准则 最小比值中的绝对值是使得比值非负 在极小化问题 j 0 分母aij 0这时必须取绝对值 在极大化问题中 j 0 分母aij 0 总满足非负 这时绝对值符号不起作用 可以去掉 如在本例中将目标函数写成 这里 j 0在求 k时就可以不带绝对值符号 对偶单纯形法 对偶单纯形法与普通单纯形法的换基顺序不一样 普通单纯形法是先确定进基变量后确定出基变量 对偶单纯形法是先确定出基变量后确定进基变量 普通单纯形法的最小比值是其目的是保证下一个原问题的基本解可行 对偶单纯形法的最小比值是 其目的是保证下一个对偶问题的基本解可行 对偶单纯形法在确定出基变量时 若不遵循规则 任选一个小于零的bi对应的基变量出基 不影响计算结果 只是迭代次数可能不一样 灵敏度分析 线性规划问题的标准形式 令 灵敏度分析 一 价值系数cj的变化分析 例1 某企业利用三种资源生产两种产品的最优计划问题归结为下列线性规划 问题 1 确定x2的系数c2的变化范围 使原最优解保持最优 2 若c2 6 求新的最优计划 灵敏度分析 最优表如下 灵敏度分析 4 c2 5 0 5 5 2c2 05 2 c2 5 最优解X 35 10 25 0 0 保持不变 1 灵敏度分析 2 用对偶单纯形法是求解得 x1 45 2 x2 45 2 x4 25 2 x3 x5 0 z 495 2 灵敏度分析 二 右端常数bi的变化分析 XB B 1b 例2 对于上例中的线性规划作下列分析 1 b3在什么范围内变化 原最优基不变 2 若b3 55 求出新的最优解 灵敏度分析 灵敏度分析 1 XB B 1b 解得40 b3 50 即当b3 40 50 时 最优基B不变 灵敏度分析 2 当b3 55时 最优解 X 30 20 0 0 5 灵敏度分析 三 增加一个变量的分析 例3 续例1 设企业研制了一种新产品 对三种资源的消耗系数列向量以P6表示P6 问它的价值系数c6符合什么条件才必须安排它的生产 设c6 3 新的最优生产计划是什么 6 c6 CBB 1P6 c6 0 5 4 c6 5 2 灵敏度分析 灵敏度分析 四 增加新的约束条件的分析 例4 假设在例1中 还要考虑一个新的资源约束 4x1 2x2 150 标准化 灵敏度分析 灵敏度分析 1 cj和bi同时变化的情况 五 其它变化情况的分析 例5 在例1中 假定c2由4上升为6 b3增加到55 试问最优解将会发生什么变化 B 1 B 代替最优表的b列 并把c2改为6 灵敏度分析 原问题与对偶问题均非可行解 表中第一方程是 x3 2x4 5x5 25 两边乘以 1 得 x3 2x4 5x5 25 再引入人工变量x6 x3 2x4 5x5 x6 25以x6为基变量 增添第6列 应用大M法继续求解 新的最优计划产量为x1 30 x2 20 z 270 x3 2x4 5x5 x6 25 灵敏度分析 2 技术系数aij的变化 例6 在例1中 第一种产品的消耗系数改变为 价值系数不变 求新的最优解 B 1 灵敏度分析 思考题 判断下列结论是否正确 如果不正确 应该怎样改正 1 任何线性规划都存在一个对应的对偶线性规划 2 原问题第i个约束是 约束 则对偶变量yi 0 3 互为对偶问题 或者同时都有最优解 或者同时都无最优解 4 对偶问题有可行解 则原问题也有可行解 5 原问题有多重解 对偶问题也有多重解 6 对偶问题有可行解 原问题无可行解 则对偶问题具有无界解 7 原问题无最优解 则对偶问题无可行解 8 对偶问题不可行 原问题可能无界解 9 原问题与对偶问题都可行 则都有最优解 10 原问题具有无界解 则对偶问题不可行 11 对偶问题具有无界解 则原问题无最优解 12 若X Y 是原问题与对偶问题的最优解 则X Y 本章小结 学习要点 1 线性规划解的概念以及3个基本定理2 熟练掌握单纯形法的解题思路及求解步骤3 熟练掌握对偶问题的转换4 掌握对偶问题的5个性质5 熟练掌握对偶单纯形法的解题思路及求解步骤 Chapter3运输规划 TransportationProblem 运输规划问题的数学模型表上作业法运输问题的应用 本章主要内容 运输规划问题的数学模型 例3 1某公司从两个产地A1 A2将物品运往三个销地B1 B2 B3 各产地的产量 各销地的销量和各产地运往各销地每件物品的运费如下表所示 问 应如何调运可使总运输费用最小 运输规划问题的数学模型 解 产销平衡问题 总产量 总销量 500设xij为从产地Ai运往销地Bj的运输量 得到下列运输量表 MinC 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 运输规划问题的数学模型 运输问题的一般形式 产销平衡 A1 A2 Am表示某物资的m个产地 B1 B2 Bn表示某物质的n个销地 ai表示产地Ai的产量 bj表示销地Bj的销量 cij表示把物资从产地Ai运往销地Bj的单位运价 设xij为从产地Ai运往销地Bj的运输量 得到下列一般运输量问题的模型 运输规划问题的数学模型 已知资料如下 产销平衡 销量 运价 运输规划问题的