数学规划基础-1(全集).pdf

主讲人 刘昉主讲人 刘昉 Tianjin University 一 课程的性质 数学规划是运筹学的重要分支 它的研究目标不 是给出问题的最优最优答案 而是寻求一种不坏不坏的答 案的艺术艺术 否则问题的结果会更坏 定性分析是定量分析的基础 定量分析是定性分析的支持 从数学模型中求出的解不是问题的最终最终答案 而 仅仅是为实际问题的系统处理系统处理提供了有用的有用的可以 作为决策基础决策基础的信息 Tianjin University 二 起源及发展 1 古朴的运筹学思想 田忌赛马 齐王 田忌 上上 中中 下下 上上 中中 下下 结果 齐王 田忌 1 2 对策论 Tianjin University 哥尼斯堡七桥难题哥尼斯堡七桥难题 普莱格尔河 图论 Tianjin University 2 运筹学形成一门学科的时间 二次世界大战 军事上的需要 如 英国防空部门对如何布置防空雷达 建立有效的 防空预警系统进行的研究 英 美空军对如何提高轰炸机对德国地面目标轰 炸的命中率进行的研究 美国海军对如何安排反潜巡逻飞机的飞行路线 特别是如何投放深水炸弹以及如何确定深水炸弹 的起爆深度等的研究 Tianjin University 3 运筹学发展的几个阶段 40年代后半期 运筹学专家重返大学和研究部门 致力于运筹学理论基础的研究 寻找各种分析和 解决管理问题的新方法 50年代 运筹学逐渐成为一门理论性和应用性都 很强的学科 理论和方法都比较完善的分支有线 性规划 非线性规划 动态规划 整数规划 排 队论 存贮论 图与网络等 Tianjin University 60 70年代 运筹学在企业管理 工程设计 生产 计划 财政金融 资源配置 物资存贮 公共服 务 医疗保健 交通运输 教育科研 国防军事 航天技术各个领域得到广泛的应用 80年代 今 运筹学的兴旺发达时期 成为解决 人口 能源 粮食 裁军 经济发展等重大问题 的重要工具 展望未来 前景广阔 随着新问题的不断出现 运筹学的应用邻域也将不断扩展 Tianjin University 运筹学的研究内容 运筹学的具体内容包括 规划论 包括线性规划 非线性规划 整数规划和动态规划 图论 决策论 对策论 排队论 存储论 可靠性理论 等 Tianjin University 三 本课程所涉及到 运筹学 的具体内容 第一章 数学规划及其研究方法 第二章 线性规划 第三章 单纯形法 第四章 灵敏度分析和对偶 第五章 整数规划 第六章 确定型动态规划 Tianjin University 四 使用教材及参考书目 关于 运筹学 的教科书和专著有很多 同学们可以根据兴趣选读 本课程选用的 讲义 数学规划基础 目前为电子版形式 同学可到QQ群 115200169 的群共享或公 文网本科教学的课程资料中下载 Tianjin University 第一章 数学规划及其研究方法 z 0 z 3 z 6 z 9 z 12 z 15 3 0 1 2 3 4 5 6 8 7 6 5 4 3 2 1 6 5 4 3 2 1 x1 x2 B Tianjin University 运筹学的研究方法运筹学的研究方法 当使用运筹学解决一个实际问题时 需要遵循以 下七个步骤 步骤1 阐述问题 首先 运筹学分析师需要精确地定义精确地定义将要解决的 实际问题 问题的定义包括明确指定目标目标和研究 决策执行单位所能发挥的作用能发挥的作用 Tianjin University 例 某银行主管聘请一位运筹学分析师帮助银行在保 证适当的服务水平前提下减小柜台服务人员的总开减小柜台服务人员的总开 支支 经过与银行主管的讨论 分析师将如何指定银 行的目标 这里分析师提出了三种可能性 1 在保证顾客平均等待时间不超过3分钟的前提下 银 行希望柜台服务人员的月工资支出最少月工资支出最少 2 在保证只有5 的顾客平均等待时间超过3分钟的前提 下 银行希望柜台服务人员的月工资支出最少月工资支出最少 3 银行最多愿意支付给柜台服务人员的月总工资为月总工资为1 1万万 元元 在给定工资约束条件下 使顾客的平均等待时 间最短 Tianjin University 分析师必须掌握影响实现银行目标的银行运营方式 的因素 1 从平均意义来说 每小时有多少顾客来到银行每小时有多少顾客来到银行 顾 客越多 需要的柜台服务人员越多 2 从平均意义来说 柜台服务人员每小时能为多少顾柜台服务人员每小时能为多少顾 客服务客服务 3 顾客排成一排而不是多排对银行目标的实现有什么 影响 4 如果每个柜台服务人员前都有一排 顾客是否总会 排在最短的一排 如果一排变得很长 顾客是否会转 排较短的 Tianjin University 步骤2 研究系统 接下来 分析师收集数据来判断影响问题的参数值 在上面的银行实例中 分析师将收集数据来评估如 下系统参数 1 从平均意义来说 每个小时有多少顾客到达 顾客 的到达率与一天中的时段有关吗 2 从平均意义来说 每个柜台服务人员1小时能为多少 顾客服务 服务人员的服务速度与等待顾客的数量 有关吗 3 顾客是否总排在最短的队 当排在长队的后面 顾 客是否会经常地转到较短的队 Tianjin University 步骤3 建立问题的数学模型 在这步 分析师建立问题的一个数学模型数学模型 在我 们的银行实例中 可建立数学模型预测如下两个 量 顾客的平均等待时间 一个顾客至少等待3分钟的概率 已知参数为 每小时到达银行的平均客户数 每小时柜台服务人员可以服务的平均客户数 银行柜台服务人员数量 柜台服务人员的配置和顾客排队的方式 Tianjin University 步骤4 验证模型和使用模型预测 现在 分析师需要确定在步骤3中建立的数学模型是 否精确地表达真实情况 为了确定模型与真实情况的 吻合程度 我们需要验证模型在当前条件下的有效性 例如 在上面的银行实例中 假设我们建立了一个 关于 的分析模型并认为它是合理的 那么我们将 当前的参数带入到这个分析模型中 得到 的预测值 再通过比较预测值与实际观测到的值来评价模型的 好坏 如果模型的预测值与真实值相差较大 则需要 建立一个新模型 在这种情况下 我们需要回到步骤 2或步骤3来建立一个能更好描述真实情况的新模型 Tianjin University 步骤5 选择一个恰当的方案 在提出了一系列候选方案后 现在分析师需要选定 一个最能满足问题目标的方案 例如 在我们的银 行实例中 我们需要决定的是在保证客户平均等待 时间不超过3分钟的条件下使总工资支出最小的就业 政策 有时 一系列候选方案要受到一些条件的制约 例 如 假设银行可以雇佣全职和兼职服务员 假设兼 职服务员的费用更低但服务也更慢 我们需要在如 下约束下使客户的平均等待时间最短 1 服务员的月总工资最多为2万元 2 兼职人员的工作时间最多只能占总工作时间的1 4 Tianjin University 步骤6 提交研究的结果和结论 在这步 分析师向决策制定的个人或组织提交由 步骤5得到的模型和推荐方案 在有些情况下 我 们需要提供多个备选方案 让决策者最终确定最 适合他们的方案 在提交完运筹学研究成果后 分析师也许会被告 知决策者不接受推荐的最优方案 这种结果的产 生可能是因为对需要解决的问题定义错误或在项 目开始时没有正确地考虑决策者因素 在这种情 况下 分析师需要返回步骤1 2或3 Tianjin University 步骤7 执行与评价推荐方案 如果决策者接受了研究成果 分析师需要辅助执 行推荐方案 必须对系统进行不断地监测 当环 境改变时要动态升级 以保证推荐方案能够实现 既定的目标 例如 在银行的实例中 假如目标 是保证至多5 的客户等待时间超过3分钟 当分析 师的建议被执行后 80 的客户等待时间超过3分 钟 很显然 银行的目标没有实现 分析师需要 重新回到步骤1 2或3并复查模型 Tianjin University 第二章 线性规划 z 0 z 3 z 6 z 9 z 12 z 15 3 0 1 2 3 4 5 6 8 7 6 5 4 3 2 1 6 5 4 3 2 1 x1 x2 B Tianjin University 线性规划 Linearprogramming LP 是解最优化 问题的一个工具 1947年 乔治 丹泽发明了一种 解线性规划问题的高效方法 单纯形法 自从单纯 形法出现后 线性规划就被广泛应用于工业界各个 领域的最优化问题 如银行业务 教育 林业 石 油和交通运输等 在对财富500强企业的调查中 有85 的企业表示使用过线性规划 由于线性规划 在运筹学中的重要地位 本书的绝大部分内容都是 围绕线性规划进行的 Tianjin University 例1 某木刻公司生产两种木质玩具 士兵和火车 一 个士兵售价27元 使用价值10元的原始材料 制作每 个士兵需要花费公司可变人工成本和经常性费用共14 元 一个火车售价21元 使用价值9元的原始材料 制作每个火车需要花费公司可变人工成本和经常性费 用共10元 制作木头士兵和火车需要两种熟练工种 木匠和精加工 一个士兵需要1个木匠工时和2个精加 工工时 一个火车需要1个木匠工时和1个精加工工时 每周 该公司可获得所需的全部原材料 但只有80 个木匠工时和100个精加工工时 火车的订单不受限 制 但每周至多可卖40个士兵 该公司想使周利润最 大化 收入 成本 试建立一个使该公司周利润最 大化的数学模型 Tianjin University 解解 在建立模型过程中 我们将研究所有线性规划问 题都具有的特征 决策变量决策变量 Decision Variables 我们首先定义相 应的决策变量 在任何线性规划模型中 决策变量应 该能够完全描述将要制定的决策完全描述将要制定的决策 显然 木刻公司 必须确定每周制作多少个士兵和火车 因此 我们定 义 每周生产的士兵数量 每周生产的火车数量 1 2 Tianjin University 目标函数目标函数 Objective Function 在任何线性规划 问题中 决策者都想最大化 通常是收入或利润 或最小化 通常是成本 决策变量的某个函数决策变量的某个函数 需 要最大化或最小化的函数称为目标函数 对于木刻 公司问题 我们注意到固定成本 例如房租和保险 费 不依赖于变量 和 因此 木刻公司可以专 注于最大化 周收入 原材料成本 其他 可变成本 木刻公司的周收入和成本可用决策变量 和 表示 对于木刻公司来说 士兵的制作数量大于可卖出 数量是一个愚蠢的决定 因此我们假设所有玩具都 能卖出 这样 1 2 1 2 Tianjin University 周收入 出售士兵获得的周收入 出售火车获得的周收入 同时 木刻公司希望最大化 每个士兵的价格 每周制作的士兵数 每个火车的价格 每周制作的火车数 27 1 21 2 周原材料成本 10 1 9 2 其他周可变成本 14 1 10 2 27 1 21 2 10 1 9 2 14 1 10 2 3 1 2 2 Tianjin University 这样 木刻公司的目标是选择 和 使得 最大 我们使用变量z 代表任意线性规划的目标函 数 木刻公司的目标函数为 1 在后面 我们将使用maximize的缩写max和minimize 的缩写min 在目标函数中变量的系数称为变量的目目 标函数系数标函数系数 例如 的目标函数系数是3 的目 标函数系数是2 在这个例子中 每个变量的目标函 数系数是变量对公司利润的贡献 1 2 3 1 2 2 Maximize 3 1 2 2 1 2 Tianjin University 约束约束 Constraints 随着 和 的增大 木刻公 司的目标函数也增大 这意味着如果木刻公司可以 任意选择 和 则公司可以获得任意大的利润 然而 和 的值受到如下3个约束条件的限制 约束约束1 1 每周 至多可使用100个精加工工时 约束约束2 2 每周 至多可使用80个木匠工时 约束约束3 3 由于需求的限制 每周至多可制作40个士兵 假设原材料的数量没有限制 因此没有关于它的约束 1 2 1 2 1 2 Tianjin University 建立木刻公司问题数学模型的下一步是用决策变量 和 表达约束1 3 为了用 和 表达约束1 我们 注意到 现在 约束1可表达为 2 注意到式 2 的每项都是每周的精加工工时数 对 于一个合理的约束 约束中的所有项必须有相同的单 位 1 2 1 2 每周总的精加工工时 每个士兵的精加工工时 每周制作的士兵数 每个火车的精加工工时 每周制作的火车数 2 1 1 2 2 1 2 2 1 2 100 Tianjin University 为了用 和 表达约束2 我们注意到 约束2可被写为 3 同样 注意到式 3 的每项都有相同的单位 最后 我们通过限制周制作士兵的数量至多为40个 来满足每周至多销售40个士兵的事实 这得到如下 约束 4 1 2 每周总的木匠工时 每个士兵的木匠工时 每周制作的士兵数 每个火车的木匠工时 每周制作的火车数 1 1 1 2 1 2 1 2 80 1 40 Tianjin University 这样 式 2 4 以决策变量的形式表达了约 束1 3 它们叫做木刻公司线性规划问题的约束 在 约束中决策变量的系数称为工艺系数工艺系数 technological coefficients 这是因为工艺系数 常常反映生产不同产品的工艺 例如 式 3 中 的工艺系数是1 表明1个士兵需要1个木匠工时 每 个约束右边的数量称为约束的右部右部 right hand side rhs 约束的右部常表示可用资源的数量 2 Tianjin University 符号约束符号约束 Sign Restrictions 为了完成线性规划 问题建模 必须回答有关每个决策变量的问题 是 否决策变量只能取非负值 或者决策变量既可以取 正值又可以取负值 如果一个决策变量 只能取非负值 我们加上符号约 束 如果一个变量 既可以取正值又可以取 负值 或零 我们称 是无符号约束的 urs 对 于木刻公司问题 很显然 和 在其他问 题中 一些变量可以无符号约束 例如 如果 代 表一个公司的现金平衡 如果公司出现负债 则 可以取负值 在这种情况下 定义 无符号约束是 恰当的 0 1 0 2 0 Tianjin University 将符号约束 和 和目标函数 1 约束 2 4 相组合得到如下优化模型 受限于 s t 决策变量 和 的值必须满足所 有约束和所有符号约束 1 0 2 0 max 3 1 2 2 目标函数 1 受限于 s t 2 1 2 100 精加工约束 2 1 2 80 木匠约束 3 1 40 士兵数量约束 4 1 0 符号约束 5 2 0 符号约束 6 1 2 Tianjin University 在正式定义线性规划问题之前 我们给出线性函 数和线性不等式的定义 定义定义 1 一个关于一个关于 的函数的函数 是线性函数是线性函数 当且仅当存在一 当且仅当存在一 些常数些常数 使得 使得 例如 1 2 2 1 2是 1和 2的一个线性函数 而 1 2 1 2 2不是 1和 2的 一个线性函数 定义定义 2 对于任意线性函数 对于任意线性函数 和任意数和任意数 不等式 不等式 和和 称为线性不等式 称为线性不等式 这样 2 1 3 2 3和2 1 2 3是线性不等式 而 1 2 2 3不是一个线性不等式 Tianjin University 定义定义 3 一个线性规划问题是一个优化问题 我们需要做如下事情 一个线性规划问题是一个优化问题 我们需要做如下事情 1 我们希望最大化 或最小化 一个关于决策变量的线性函数 需要最大化或最小我们希望最大化 或最小化 一个关于决策变量的线性函数 需要最大化或最小 化的函数称为目标函数化的函数称为目标函数 2 决策变量的值必须满足一系列约束条件 每个约束条件必须是一个线性等式或线决策变量的值必须满足一系列约束条件 每个约束条件必须是一个线性等式或线 性不等式 性不等式 3 每个变量都有一个符号约束 对于任意变量每个变量都有一个符号约束 对于任意变量 符号约束规定 符号约束规定 必须是非负必须是非负 或或 可以是无符号约束 可以是无符号约束 urs 由于木刻公司的目标函数是关于 和 的线性函 数 所有的约束是线性不等式 木刻公司问题是 一个线性规划问题 注意到木刻公司问题是广泛 的线性规划问题中的一个典型问题 它描述了决 策者在有限资源限制下希望取得最大利润的目标 1 2 Tianjin University 比例性与可加性假设比例性与可加性假设 一个线性规划问题的目标函数必须是决策变量的线 性函数的事实有两层含义 1 目标函数从每个决策变量得到的贡献正比于决策 变量的值 例如 制作4个士兵 3 4 12 对目 标函数的贡献确切地等于制作1个士兵 3 对目 标函数贡献的4倍 2 任意变量对目标函数的贡献与其他决策变量的值 无关 例如 不管 取何值 制作 个士兵对目 标函数的贡献总是 2 1 3 1 Tianjin University 类似地 每个线性规划的约束必须是线性不等式或线性 等式也有两层含义 1 每个变量对每个约束左部的贡献正比于变量值 例如 制作3个士兵 2 3 6 需要的精加工工时确切地 等于制作1个士兵 2 需要的精加工工时的3倍 2 一个变量对每个约束左部的贡献与其他变量值无关 例如不管 取何值 制作 个火车需要 个精加工工 时和 个木匠工时 第一层含义称为线性规划的比例性假设 第二层含义称 为线性规划的可加性假设 对于一个正确表达现实情 况的线性规划 决策变量必须同时满足比例性假设和 可加性假设 另外两个必须满足的假设是可分性假设 和确定性假设 1 2 2 2 Tianjin University 可分性假设可分性假设 可分性假设要求每个决策变量允许取分数值 例 如 在木刻公司问题中 可分性假设意味着允许 制作1 5个士兵或1 63个火车 由于木刻公司实际 上不可能制作分数个火车或士兵 因此该问题不 满足可分性假设 一个线性规划问题中 个别或 全部变量必须取非负整数的称为整数规划问题整数规划问题 Tianjin University 在许多情况下可以不考虑可分性 将线性规划得 到的最优解舍入到相邻的整数可以得到合理的结 果 假设一个汽车公司的线性规划最优解得到当 年应该生产150000 4辆小型汽车 这这种情况下 你可以告诉汽车公司生产150000或150001辆小 型汽车 得到的结果毫无疑问将非常接近最优生 产计划 另一方面 由线性规划得到的美国需要 修建的导弹防御系统最优解的数量为0 4 当我们 向下舍入得到0和向上舍入得到1时 结果差别很 大 在这种情况下 我们需要使用整数规划方法 因为导弹防御系统是明确不可分的 Tianjin University 确定性假设确定性假设 确定性假设是每个参数 目标函数系数 右部和 工艺系数 都是确切已知的 如果我们不知道制 作一个火车的确切木匠工时和精加工工时 就违 背了确定性假设 Tianjin University 可行域和最优解可行域和最优解 有关线性规划问题两个最基本的概念是可行域 feasible region 和最优解 optimal solution 为了定义这些概念 我们使用术语 点 来 表示每个决策变量一个具体取值 定义4 线性规划的可行域由满足所有线性规划约束线性规划的可行域由满足所有线性规划约束 条件和符号约束的点的集合组成 条件和符号约