1、运筹学 Operations Research 期末复习期末复习 如果学问不能教会我们如何思想 和行动，那真是莫大的遗憾。 - 米歇尔.德.蒙田随笔集 期末考试 ?闭卷考试 ?考试时间120分钟 ?题型： ?判断题 ?单选题 ?计算题 ?考试内容：第一章第一章, ,第二章第二章, ,第三章第三章, ,第四章、第四章、 第六章、第八章第六章、第八章, ,第九章第九章, ,第十章第十章, , 第十一章第十一章 ?带上铅笔、钢笔、尺子、橡皮擦、草稿纸 复习资料 ? ?教材教材教材教材：第一章、第二章、第三章、第四 章、第六章、第八章、第九章、 第十章、第十一章 ? ?课件课件课件课件：所有本课程的课
2、件 ? ?作业作业作业作业 第一章复习要点 ?科学的研究方法：遵循一系列科学研究的程 序。 ?全局观点：着眼于组织整体的利益。 ?最优解：寻求问题的最优解，不只是对当前 问题的改进。 ?团体努力：运筹学研究需要具备多个领域背 景（例如数学、统计、经济学、商业管理、 计算机科学）的成员共同合作。 ?运筹学的特性： 什么是运筹学(Operations Research)？ ?研究如何管理和调整组织内部的运作，运 用数学、统计、信息技术等为决策者提供 科学依据的学科。 ?Operations: 组织运作包括对稀缺资源的有效分 配，协调组织中目标和各部门目标间的冲突，优 化大型企业中复杂的物流、配送等
3、问题。 ?Research: 运用科学的方法对组织内的运作问题 进行研究，遵循科学研究的程序。 现代运筹学的起源 ?第二次世界大战初期：英军和美军运用科 学手段把稀缺资源有效地分配到军事作业 中。这些研究对英军空军取得胜利，以及 北大西洋反潜战都发挥了重要作用。 ?二战后的工业繁荣时期：组织的规模和复 杂性日益增加，面临与战争中相似的问 题，即对稀少资源的优化分配。 第二章复习要点 ? 运筹学建模方法综述 1. 定义问题和收集数据 2. 构建表示问题的数学模型 3. 模型求解 4. 检验模型：调试程序；用历史数据检验 5. 准备应用模型：检验过的模型装入DSS 6. 实施：按管理层的指示实施系
4、统 第三章复习要点 ?如何根据问题描述建立线性规划模型。 ? 注意建立线性规划模型时，使用规范化的形式 ?如何使用图解法求解2个变量的小型线性规 划问题。 ?线性规划的四个假设 第四章复习要点 ?单纯形法的实质 ? 了解关键的概念：角点解、CPF解、最优性检 验等 ? 关键的解原理：6个解原理 ?构建单纯形法 ? 了解关键的概念：扩展形式、扩展解、松弛变 量、基本解、BF解、基变量、非基变量 ? 如何构建模型的扩展形式 ?单纯形法的代数形式 ? 运用单纯形法的代数方式求解线性规划问题 第四章复习要点 ?单纯形法的表格形式 ? 运用单纯形法的表格方式求解线性规划问题 ? 单纯形法总结 ?计算中相
5、持的突破 ? 入基变量的相持 ? 出基变量的相持 ? 无出基变量 ? 多个最优解 第四章复习要点 ?改造适用于其他模型形式 ? 等式约束：大M法 ? 负的右端项 ? 形式的约束条件：大M法；两阶段法 ? 最小化目标函数 ? 大M法 VS. 两阶段法 ? 无可行解 ? 允许为负的变量 第四章复习要点 ?优化后分析 ? 再优化 ? 影子价格 ? 灵敏度分析 ? 参数线形规划 第六章复习要点 ? 对偶理论的实质 ? 原问题和对偶问题的形式 ? 如何根据一个问题建立另一个问题 ? 原问题和对偶问题的关系：弱对偶性、强对偶 性、互补解特性、最优互补解特性、对称性等 ? 对偶的经济解释 ? 原问题和对偶问
6、题的关系 ? 互补基本解 ? 互补的基本解间的关系 ? 改造适用于其他问题形式 对偶问题在灵敏度分析中的作用对偶问题在灵敏度分析中的作用对偶问题在灵敏度分析中的作用对偶问题在灵敏度分析中的作用 ?原问题中系数值的变化也会改变对偶问题中 对应的值。 ?在调查每个变化时可以选择原问题或对偶问 题。 ?在有些情况下分析对偶问题更为方便： ?非基变量参数的改变 ?引入新变量 第六章复习要点 灵敏度分析的实质灵敏度分析的实质灵敏度分析的实质灵敏度分析的实质 ?灵敏度分析的一个重要目的是找出敏感参数。 ?对于某些非敏感参数，找出其不会影响最优解 的变化范围。这个变化范围对应于约束方程的 影子价格的变化范围
7、。 ?灵敏度分析提供的信息是很重要的： ?识别出重要的参数，分析阶段时对他们进行严密的 评估。 ?识别出哪些参数在研究过程中应该被更密切地监视。 如果发现某个参数的真实值超出了允许的变化范 围，就应该改变方案。 第六章复习要点 第六章复习要点 应用灵敏度分析应用灵敏度分析应用灵敏度分析应用灵敏度分析 ? 情形1：改变bi ? 情形2a：改变非基变量系数 ? 情形2b：引入新变量 ? 情形3：改变基变量系数 ? 情形4：引入新的约束 ? 参数规划 第八章复习要点 ?运输问题 ?用于运输问题的单纯形法 ?指派问题 ?求解指派问题的特殊算法 运输问题 ?运输问题：线型规划问题的一种 ?这类问题的很多
8、应用是为了解决运输的最优 化。不过也有一些应用与运输没有关系，如 生产计划问题。 ?运输问题的应用一般涉及很多约束条件和变 量，用单纯形法计算要耗费大量的时间。 ?由于这类问题的结构特点(约束条件中的大多 数aij参数为0)，用改进的算法来求解可以节 省计算工作量。 一般运输问题的网络表示 运输问题：参数表 运输问题的假设 ?需求假设： ?每个产地的供给是固定的，且所有的供给(si) 必须全部分发到目的地。类似的，每个目的 地的需求(di)是固定的，且所有的需求必须全 部被满足。 ?可行解特性： ?运输问题有可行解的充分必要条件: 11 mn ii ij sd = = 运输问题的假设 ?成本假
9、设： ?任何产地到任何目的地的运输费用与分发的 产品数成正比。因此，运输总成本等于每单 位产品的运输成本乘以分发的总产品数。 ?现实问题中，产地的供给和目的地的需求都 不是固定的，而是最大化地实现供给和需 求，因而违反了运输问题的假设。 ?这种情况可以通过引入虚拟产地或目的地， 从而满足需求假设。 用于运输问题的单纯形法 ?初始化：创建一个初始的基本可行解，对 之进行最优解检验。 初始化：创建一个初始的基本可行解，对 之进行最优解检验。 ?最优性检验：如果对每个非基变量xij都有 cij ui vj0，此时的BF解是最优解，停 止计算，否则进行下面的迭代。 ?迭代： ?确定入基的变量 ?确定出
10、基的变量 ?确定新的BF解 运输单纯形法：初始解 ?初始化：创建一个初始的基本可行解。 ?单纯形法通过引入松弛变量、人工变量等获 得初始的基本可行解。 ?运输问题中的约束条件是等式，因此需要引 入人工变量作为初始的BF解。 ?要从初始的BF解得到原问题的BF解，必须要 经过几轮迭代让人工变量从BF解消失。 ?运输问题有多个约束，因此需要多次迭代。 ?运输单纯形法设法直接构建一个BF解。 运输单纯形法：初始化 ?基变量的个数： ?线性规划问题中，通常基变量的个数=约束方程 的个数 ?运输问题的约束方程个数： ? 运输问题的约束方程个数=产地个数m+目的地个数n ? 运输问题中基变量的个数： ?
11、基变量的个数=约束方程的个数 - 1 ? 因为m+n个约束方程中有一个是多余的(将其去除 也不影响可行域)。 运输单纯形法：初始化 ?构建初始BF解的一般过程： 1. 从运输单纯形表中所有的行和列中根据一定的标 准，选择基变量(配额)。 2. 配额的量恰好能够满足用完该行中剩余的供给或 列中未满足的需要(小的那个)。 3. 把具有较小的剩余供给或需求的行或列从单纯形 表中删除。如果行或列具有相同的剩余量，删除 行，而列会被用作退化基变量。 4. 如果表中只剩下一行或一列，选择剩下的与该行 或列相关的变量作为基变量，构建过程结束。否 则回到第一步。 运输问题的单纯形法：最优性检验 ?计算现有BF
12、解的ui和vj，计算方法如下： ?如果xij是基变量：cij ui vj=0? cij= ui+ vj ? 由于运输问题有m+n-1个基变量，意味着有 一个变量可以被赋予任意值而不违背等式。 ? 一个捷径是选择在行中具有最多配额个数 (基变量个数)的ui，赋其值为0 ? 计算出所有ui和vj，然后对所有非基变量检 验：如果cij ui vj不全为非负，则进一步迭 代，否则当前解为最优。 运输问题的单纯形法：迭代 1. 确认入基变量： ? 具有最大负值cij ui vj的非基变量 2. 确认出基变量： ? 从增加入基变量开始，找出基变量中发生的 连锁反应，确认接收单元和赠与单元。 ? 选择赠与单
13、元中具有最小值的变量作为出基 变量。 3. 确认新的BF解： ? 每个接收单元加上出基变量的配额，赠与单 元减去出基变量的配额。 指派问题 ? 指派问题是一类特殊的线型规划问题，旨在给不同 的指派对象指派任务。指派对象可以是被分配任务 的员工、车辆、机器、时段等。 ? 指派问题的应用一般应符合以下假设条件： ?指派对象的数目和任务的数目是一致的(n) ?每个指派对象只被指派一项任务 ?每项任务只被一个指派对象完成 ?指派对象i(i=1,2,n)执行任务j(j=1,2,n)所需的成本为cij ?指派问题的目标是确定如何分配n项任务，使得完成任务的 总成本最小 ? 符合这些假设的指派问题可以用特殊算法快速求解。 指派问题 ?偏离指派问题假设条件的情况： ?指派对象被分配多个任务： ?把指派对象分为多个指派对象，每个指派对象分 配一件任务 ?一个任务由多个指派对象完成：
