运筹学概论(精选)

12/3 4
z
1 2
x4
x5 42
x3
2 3
x4
1 3
x5
4
新典式
主元化 为1，主 元所在
x2
1 2
x4
6
列的其 余元素
x1
2 3
x4
1 3
x5
4
化为0
观察最后一个典式，所有检验数均为非负， 故其对应的基本可行解为最优解，即
X * 4,6,6,0,0T z* 42
去掉引入变量，得原问题的最优解为：
运筹学课件
目录
运筹学概论 第一章 线性规划基础 第二章 单纯形法 第三章 LP对偶理论 第四章 灵敏度分析 第五章 运输问题 第六章 整数规划 第七章 动态规划 第八章 网络分析
第二章 单纯形法
(SM-Simplex Method)
1947年，美国运筹学家Dantzig提出，原理是 代数迭代。
单纯形法中的单纯形的这个术语，与该方法毫 无关系，它源于求解方法的早期阶段所研究的一 个特殊问题，并延用下来。
CB B1b B1b
z
CB B1N CN X N X B B1NX N
CB B1b B1b
上述方程组的矩阵形式为
10
0 I
CB
B1N B1N
CN
z XB XN
CB B1b B1b
上式的系数增广阵称为对应于基B的单纯形表：
T(B)
CB B1b B1b
0 I
CB
B1N B1N
CN
形式的LP问题，必须解决三个问题： ⑴初始基本可行解的确定； ⑵解的最优性检验； ⑶基本可行解的转移规则。 这里先放一下⑴，研究⑵和⑶，为此，

运筹学是一门寻求在给定资源条 件下，如何设计和运行一个系统的 科学决策的方法
运筹学与其他学科的关系
运 筹 学 与 管 理 科 学 （Management Science MS）关 系：管理科学涵盖的领域比运筹 学更宽一些。可以说，运筹学是 管理科学最重要的组成部分。
运筹学与其他学科的关系
运筹学与系统科学、系统分析、 工业工程的关系：系统科学、系统 分析、工业工程等学科研究的内容 比运筹学窄一些。
运筹学研究的特点
科学性 （1）它是在科学方法论的指导下通 过一系列规范化步骤进行的；
（2）它是广泛利用多种学科的科学 技术知识进行的研究。运筹学研究不 仅仅涉及数学，还要涉及经济科学、 系统科学、工程物理科学等其他学科。
运筹学研究的特点
实践性
运筹学以实际问题为分析对象， 通过鉴别问题的性质、系统的目标 以及系统内主要变量之间的关系， 利用数学方法达到对系统进行最优 化的目的。更为重要的是分析获得 的结果要能被实践检验，并被用来 指导实际系统的运行。
运筹学研究的特点
系统性
运筹学用系统的观点来分析 一个组织（或系统），它着眼于整 个系统而不是一个局部，通过协调 各组成部分之间的关系和利害冲突， 使整个系统达到最优状态。
运筹学研究的特点
综合性
运筹学研究是一种综合性的 研究，它涉及问题的方方面面，应 用多学科的知识，因此，要由一个 各方面的专家组成的小组来完成。
1939年由曼彻斯特大学物理学 家、英国战斗机司令部顾问、战后 获得诺贝尔奖金的P.M.S.Blackett为 首，组织了一个小组，代号 “Blackett马戏团”。这个小组包括 三名心理学家、两名数学家、两名 应用数学家、一名天文物理学家、 一名普通物理学家、一名海军军官、 一名陆军军官、一名测量员。

第一讲 运筹学概述一、运筹学是什么？----------------------晕愁学其实，这绝对一种误解，事实上运筹学方法及应用早在中小学就比较系统地学过，并且在我们每时每刻的生活过程中都在利用。

北师大版小学语文第六册教材中就有一篇课文《田忌赛马》，在座的各位应该都不陌生。

这是战国时期运筹学思想成功应用的典型实例。

孙膑同志合理地利用当时的现有资源、条件和比赛规则，只建议田忌调换了赛马的出场顺序，就使得原来屡战屡败的战局得到了彻底的扭转，以获胜而告终。

形成了本文主题中“初战失败”、“孙膑献计”、“再赛获胜”的三部分内容。

运筹学思想体现的是，将现有资源的作用得到充分发挥，以获得最优的结果。

运筹让生活得更有条理的艺术。

谈起运筹学，是否会想到很通俗的例子——沏茶水。

沏茶，看起来是一件日常生活中再小不过的事情，却包含着运筹学的道理。

让我们来看一看，沏茶的过程可以分为烧开水、洗茶壶、放茶叶多道“工序”。

其中，烧开水所需的时间最长，洗茶壶、放茶叶的时间则较短。

善于运筹的人，应该是先将水烧上，在烧水的过程中，从从容容地把茶壶洗净，把茶叶放好。

而不善运筹的人，可能会先把茶壶洗净，把茶叶放好，才想起来水还没有烧；或者先把水烧开了，才急急忙忙去洗茶壶、放茶叶，搞得手忙脚乱。

另外还有一个例子我们外地生到上海的路线选择，虽然条条大路都能通到上海，但我们都有一个明确的目标，有些人的目标是准备用最短的时间到达，有些人的目标是用最少费用到达，这样基于不同的目标，就会选择不同的最佳路线。

这两个生活中的运筹学实例说明了运筹学应用的思想并不神秘，而现实的生活中，从沏茶、选择路线这样一件小事，到规模宏大的建设项目，都能运用运筹学的原理。

在人生大事的安排上，也同样需要下功夫好好运筹一番。

从技术是，也就是运筹学解决决策问题的工具方面，在初中的数学教材中有一个重要的内容是《线性规划》，其中比较详细地讲述了线性规划的数学表述形式和求解方法。

田忌赛马
齐王要与大臣田忌赛马，双方各出上、 齐王要与大臣田忌赛马，双方各出上、中、下马 各一匹，对局三次，每次胜负1000 1000金 各一匹，对局三次，每次胜负1000金。田忌在 好友、著名的军事谋略家孙膑的指导下， 好友、著名的军事谋略家孙膑的指导下，做以下 安排： 安排： 齐王 上 中 下 田忌 下 上 中 最终净胜一局，赢得千金。 最终净胜一局，赢得千金。
运筹学形成于20 世纪 年代 运筹学形成于 20世纪 30年代（ 第二次 世纪30 年代（
世界大战期间 ） 战斗机搜索潜艇（40年代） 年代） 战斗机搜索潜艇（40年代 军用物质运输（40年代 年代） 军用物质运输（40年代） 苏联著名数学家康托洛维奇：“生产组织与计划中的 苏联著名数学家康托洛维奇： 数学方” 数学方法”中提出合理调配和使用资源以便充分发挥 其效用的研究中所提出的新的数学方法和理论。 其效用的研究中所提出的新的数学方法和理论。
系统工程应用领域： 系统工程应用领域： 宏观经济： 宏观经济： 能源： 能源总体规划、 运输、 能源 ： 能源总体规划 、 运输 、 产 供销： 石油如何分配、 水电、 供销 ： 石油如何分配 、 水电 、 核 电发展规划。 电发展规划。 军事： 武器论证、 反坦克系统、 军事 ： 武器论证 、 反坦克系统 、 高炮系统、 坦克系统、 作战模拟、 高炮系统 、 坦克系统 、 作战模拟 、 陆海空军作战。 陆海空军作战。 农业：农业规划、农业施肥。 农业：农业规划、农业施肥。
交通：全国交通网、城市交通网、 交通：全国交通网、城市交通网、 出租车、公交路线规划、港口选址、 出租车、公交路线规划、港口选址、 驳运、 河运（ 航道堵塞） 驳运 、 河运 （ 航道堵塞 ） 、 空运 空中交通管制ATC） （空中交通管制ATC）、物流 工业企业：企业发展规划、 工业企业：企业发展规划、生产计 库存问题、新设备可行性、 划、库存问题、新设备可行性、下 料问题、全面质量管理、投入产出、 料问题、全面质量管理、投入产出、 生产调度问题、投资问题。 生产调度问题、投资问题。

排队论：

是一种研究公共服务系统的运行与优化 的数学理论与方法.它通过对随机服务 现象的统计研究，找出反映这些随机现 象的平均特性，从而研究提高服务系统 水平和工作效率的方法.
决策论

是为了科学地解 决带有不确定性和风 险性决策问题所发展的一套系统分析方 法，其目的是为了提高科学决策的水平， 减少决策失误的风险.它广泛地应用在 经营管理工作的高中层决策中.
存储论

又称库存论，是研究经营生产中各种物 资应当在什么时间，以多少数量来补充 库存，才能使库存和采购的总费用最小 的一门学科.它在提高系统工作效率、 降低产品成本上有重要的作用.
运筹学的研究方法
(1) 从现实生活常和抽出本质的要素来 构造数学模型.因而可寻求一个跟决策 着的目标有关的解； (2) 探索求解的结构并到处系统的求 解过程； (3) 从可行方案中寻求系统的最优解 法.
丹麦电气工程师埃尔朗( Erlang, A.K)关 于用概率论理论来研究电话服务的论文 (运筹学中排队论的早期论文)发表于 1909年 原苏联数学家康托洛维奇的《生产组织 与计划中的数学方法》一书出版于1939 年.

二战结束时, 在英国,首先出现了一个 “运筹学俱乐部”, 1950年出版了第一份运筹学杂志,并于 1953年成立了英国运筹学学会. 在美国,则于1952年即成立了美国运筹 学学会. 1959年成立了国际运筹学联盟 ( International Federation of Operational Research Societies ,简称IFORS).该联盟 现有会员国45个.
运筹学的主要分支

运筹学的具体内容包括：规划论（包括 线性规划、非线性规划、整数规划和动 态规划）、图论、决策论、排队论、对 策论、存储论、可靠性理论等.

1.1运筹学的简史
值得一提的是丹捷格认为线性规划模型的提出是受 到了列昂节夫的投入产出模型(1932年)的影响；后 来列昂节夫的投入产出模型也得到了诺贝尔奖。
关于线性规划的理论是受到了冯·诺依曼(Von Neumann)的帮助。冯·诺依曼和摩根斯特恩 (O.Morgenstern)合著的《博弈论与经济行为》 (1944年)是对策论的奠基作，同时该书已隐约地指 出了对策论与线性规划对偶理论的紧密联系。
美国——operations research.
中国——1956年曾用过“运用学”，到1957年正式定 名为“运筹学”。
1.1运筹学的简史
二战期间，在英、美的军队中成立了一些专门小组， 开展了护航舰队保护商船队的编队问题和当船队遭受 德国潜艇攻击时，如何使船队损失最少的问题的研究。
研究了反潜深水炸弹的合理爆炸深度后，使德国潜艇 被摧毁数增加到400%；
从以上简史可见，为运筹学的建立和发展作出贡 献的有物理学家、经济学家、数学家、其他专业 的学者、军官和各行业的实际工作者。
1.1运筹学的简史
最早建立运筹学会的国家是英国(1948年)，接着是 美国(1952年)、法国(1956年)、日本和印度(1957年) 等。到2005年为止，国际上已有48个国家和地区 建立了运筹学会或类似的组织。
每生产一件产品Ⅰ可获利2元，每生产一件产品Ⅱ可获利 3元，问应如何安排计划使该工厂获利最多?
20
举例：问题的提出
例 2 靠近某河流有两个化工厂 (见图1-1)，流经第一化工厂的河 流流量为每天500万立方米，在
两个工厂之间有一条流量为每天
200万立方米的支流。
图1-1
化工厂1每天排放含有某种有害物质的工业污水2万立方米，化工厂2每天 排放的工业污水为1.4万立方米。从化工厂1排出的污水流到化工厂2前， 有20%可自然净化。根据环保要求，河流中工业污水的含量应不大于 0.2%。因此两个工厂都需处理一部分工业污水。化工厂1处理污水的成本 是1000元/万立方米,化工厂2处理污水的成本是800元/万立方米。问:

(线性规划模型）
2.图论模型----哥尼斯堡七桥问题
哥尼斯堡是前苏联加里宁格勒 的一个小城， 流贯全城的普 雷格尔河西岸和河中两个小岛 有七座桥彼此相通. 如左图所 示. 该城镇居民热衷于: 从陆地任 一地方开始, 能否通过每座桥 一次且仅仅一次就能回到原地.
哥尼斯堡七桥问题
1763 年伟大的数 学家欧拉将此难题 转化为图论模型 （如左图）。

四、运筹学应用举例
1.最优生产安排：
一工厂生产甲、乙、丙三种产品 , 已知有关 数据如左表 所示。（a） 求使该厂获利最大 的生产计划; (b)若产品乙、丙的单件利润不 变, 则产品甲的利润在什么范围内变化时, 上 述最优解不变? (c)若有一种新产品丁, 其原 料消耗定额: A为3单位, B为2单位, 单件利 润为2.5单位. 问该种产品是否值得安排生产, 并求新的最优计划 ; (d) 若原料 A市场紧缺 , 除拥有量外一时无法购进 , 而原料 B如数量 不足可去市场购买, 单价为0.5, 问该厂应否 购买, 以购进多少为宜? (e)由于某种原因该 厂决定暂停甲产品的生产, 试重新确定该厂 的最优生产计划.
4.3 乐观系数法


பைடு நூலகம்
乐观系数法是介于乐观法 与悲观法之间, 取一系数 α ∈[0, 1], 求 α (最好可能)+(1-α )(最 坏可能 ) 对应的方案为最 优方案. α =0 时, 即为悲观法; α =1 时,• 即为乐观法. α =0.5, 最优方案为 A1 或 A2 或 A4.
4.4 等可能准则
确定性理论
随机性理论
线性规划
随机过程
非线性规划
图论 整数规划 多目标规划
决策理论
对策理论 排队理论 搜索理论

运筹学编写组.运筹学.清华大学出版社 胡运权.运筹学教程.清华大学出版社 杜纲.管理科学基础.天津大学出版社 邓梁成.运筹学的原理和方法.华中科技大学 中国工程项目管理知识体系.建工社 其他：线性代数、管理学及部分杂志
➢ 设备维修和更新 ➢ 项目评价和选择 ➢ 工程优化设计
➢ 计算机和信息系 统
➢ 城市管理 ➢ 发展战略
五、教学及考试说明
➢ 以课本为主教学 ➢ 必要的习题（30～40题） ➢ 考试：采用闭卷 ➢ 平时成绩30％；考试成绩占70％
六、教材和参考书
➢ 教材： ➢ 胡云权.运筹学教程（第三版）.清华大学出版社 ➢ 宋学峰.运筹学.东南大学出版社 ➢ 参考书：
➢ 60年代，相继在工业、农业、经济和社会问题各 领域都得到应用。
➢ 理论飞快发展，形成许多分支：数学规划、图与 网络、排队论、存储论、对策论、决策论等。
➢ 1959年成立国际运筹学联合会。我国1980年成 立运筹学会，1982年加入国际运筹学联合会。
四、运筹学解决问题的思路
➢ 提出问题——用自然语言描述问题。 ➢ 建立数学模型——用变量、函数、方程描述问
题。
➢ 求解——主要用数学方法求出模型的最优解、 次优解、满意解，复杂模型求解要用计算机。
➢ 解的检验——检查模型和求解步骤有无错误， 检查解是否反映现实问题。
➢ 决策实施——决策者根据自己的经验和偏好， 对方案进行选择和修改，作出实施的决定。
五、运筹学的运用
➢ 生产计划 ➢ 市场销售 ➢ 资本运营 ➢ 库存管理 ➢ 运输问题 ➢ 财政和会计 ➢ 人事管理
——近代一些运筹学工作者
一、什么是运筹学
➢ 3、运筹学的三大来源 1）军事
两次世界大战期间的军事运筹研究 2）管理

第一章绪论（2学时）1.1运筹学起源1.2运筹学的发展1.3运筹学的应用1.4运筹学的性质和特点1.5运筹学的学习与研究方法第二章线性规划及单纯型法2.1线性规划问题及其模型（2学时）2.2.1线性规划图解法2.2.2 线性规划解的性质（2学时）2.3单纯形法原理习题课1 （2学时）2.4单纯形法计算步骤（2学时）习题课2 （2学时）2.5.1单纯形法的进一步讨论（2学时）习题课3 （2学时）2.5.2单纯形法的矩阵描述及改进单纯形法（2学时）2.6线性规划应用举例2.7习题课4 （2学时）第三章线性规划的对偶问题（2学时）3.1对偶问题的提出3.2原问题与对偶问题的数学模型3.3原问题与对偶问题的对应关系第四章运输问题（2学时）4.1 运输问题4.2 运输问题的表上作业法（2学时）习题课5 （2学时）第五章整数规划（2学时）5.1 整数规划的数学模型及解的特点5.2 分支定界法习题课6 （2学时）第六章图与网络6.1 图的基本概念（2学时）6.2 最优树问题6.3 最短（通）路问题（2学时）习题课7 （2学时）第七章决策分析7．1 决策系统（2学时）7．2 确定型决策7．3 不确定型决策7．4 风险型决策7.5 效用函数（2学时）7.6 贝叶斯（Bayes）决策习题课8 （2学时）第八章储存论8.1 存贮问题及其基本概念（2学时）8.2 确定型存贮模型8.3 单周期的随机型存贮模型（2学时）习题课9 （1学时）总复习（2学时）。

否则，目标函数等值线与可行域 将交于无穷远处，此时称无有限最 优解。
36
例2-2 考虑例2-1
某工厂拥有A、B、C 三种类型的设备，
生产甲、乙两种产品。每件产品在生产中 需要占用的设备机时数，每件产品可以获 得的利润以及三种设备可利用的时数如下 表所示。问题：工厂应如何安排生产可获 得最大的总利润？
一、线性规划问题的提出
在实践中，根据实际问题的要求，常常 可以建立线性规划问题数学模型。
例2-1 我们首先分析开篇案例提到的问题。 解：设变量 xi 为第 i 种（甲、乙）产品的 生产件数（i＝1，2）。根据题意，我们知道 两种产品的生产受到设备能力（机时数）的 限制。对设备A：两种产品生产所占用的机时 数不能超过65，于是我们可以得到不等式：
运筹学是运用科学的方法（如 分析、试验、量化等）来决定如何 最佳地运营和设计各种系统的一门 学科。
4
运筹学概述
运筹学能够对经济管理系统中 的人力、物力、财力等资源进行统 筹安排，为决策者提供有依据的最 优方案，以实现最有效的管理。
通常以最优、最佳等作为决策 目标，避开最劣的方案。
5
运筹学的产生和发展
8பைடு நூலகம்
运筹学在管理中的应用
生产计划：生产作业的计划、日程表的
编排、合理下料、配料问题、物料管 理等。
库存管理：多种物资库存量的管理，库
存方式、库存量等。
运输问题：确定最小成本的运输线路、
物资的调拨、运输工具的调度以及建
厂地址的选择等。
9
运筹学在管理中的应用
• 人事管理：对人员的需求和使用的 预测，确定人员编制、人员合理分 配，建立人才评价体系等。
x1 ，x2 ，… ，xn ≥ 0

四、图与网络分析(graph theory and network analysis)
五、存贮论(inventory theory)
六、排队论(queueing theory, or waiting line)
七、对策论(game theory)
八、决策论(decision theory)
三、运筹学
最优进货量。
预备知识
向量 矩阵及其运算 函数的导数与极值 多元函数的导数与极值
环境
输入 各种 资源
过程 计资划源 行 动决策
决策者
输出 产品和
服务
三、运筹学
运筹学研究的基本特征
多学科的综合 －－运筹学研究中吸收来自不同领 域、具有不同经验和技能的专家。 模型方法的应用－－运筹学研究的系统不能搬到 实验室来，而是建立这个问题的数学和模拟的模 型。制定决策是运筹学应用的核心，而建立模型 则是运筹学方法的精髓。
工点的位置
混凝土 需要量
（x1，y1） Q1
（x2，y2） Q2
（x3，y3） Q3
（x4，y4） Q4
运筹学主要分支简介
三、动态规划
(dynamic programming)
动态规划研究多阶段决策过程最优化。有些经营
管理活动由一系列相互关联的阶段组成，在每个阶段
一次进行决策，而且上一阶段的输出状态就是下一阶
运输问题、物资调运、车辆调度等。
图与图络分析
求解如图所示的中国邮路问题，A点是邮局。
运筹学主要分支简介
五、存贮论 (inventory theory) 存贮策略研究在不同需求、供货及到达方式 等情况下，确定在什么时间点订货，以及一 次提出多大的批量，使用于订购、储存和可 能发生短缺的费用的总和为最少。

运筹学分析的主要步骤
运筹学分析的主要步骤包括：发现和定义待研究 的问题；构造数学模型；寻找经过模型优化的结果， 并通过应用这些结果来改善系统的运行效率。
真 实 系 统
数据准备
系统分析 问题描述
模型建立 与修改
模型求解 与检验
结果分析 与实施
运筹学分析的步骤
运筹学包含的分支
数学规划（线性规划、整数规划、目标规划、非线 性规划、动态规划、网络规划） 图论与网络流 决策分析 排队论 可靠性数学理论 库存论 对策论 搜索论
英国舰队： 主 纵 列2 （16 艘） （12 艘） （23 艘） （46 艘） 主 小 纵 纵 列1 列 （16 艘） （8 艘） （3-4 艘）
。
运筹学研究的特点
实践性
运筹学以实际问题为分析对象，通过鉴别问题的性质、 系统的目标以及系统内主要变量之间的关系，利用数学方法 达到对系统进行最优化的目的。更为重要的是分析获得的结
果要能被实践检验，并被用来指导实际系统的运行。
系统性
运筹学用系统的观点来分析一个组织（或系统），它着 眼于整个系统而不是一个局部，通过协调各组成部分之间
静态模型：模型只反映某一个固定时间点的系统状态，变 量、参数与时间无关。
动态模型：模型反映一段时间内系统变化的状态，变量、 参数与时间有关。如动态规划模型等。 目前用得最多的是符号与数学模型 数学模型：对某一特定问题，用数学语言（字母、符号、图 表、图形等）描述而得到的一个结构。
运筹学模型的一个显著特点是它们大部分为最优 化模型。一般来说，运筹学模型都有一个目标函数和 一系列的约束条件，模型的目标是在满足约束条件的 前提下使目标函数最大化或最小化。
田忌赛马 齐王要与大臣田忌赛马，双方各出上、 中、下马各一匹，对局三次，每次胜 负1000金。田忌在好友、著名的军事谋 略家孙膑的指导下，以以下安排：

xi (i 1,, n)
x
j
0
变量
x
j
0
x
j
无约束
约束条件的右端项向量
m
min w bi yi i 1
有n个( j 1,, n)
m
aij y j c j
i 1
m
aij y j c j
约束条件
i 1
m
aij y j c j
i 1
2020/12/13
有m个(i 1,, m)
例2 假设某个公司想把美佳公司的资源购买过来，他至少应付多大的代 价，才能使美佳公司愿意放弃生产活动，出让自己的资源。
( LP 1) max z 2 x1 x 2
5 x 2 15
6 x
x
1
1
x
2
2
x2
5
24
x1 , x 2 0
(LP2) min f 15y1 24y2 5y3
6y2 y3 2 5y1 2y2 y3 1 y1, y2, y3 0
线性规划的对偶问题 对偶问题的基本性质 影子价格
2020/12/13
第二节 对偶问题的基本性质
为了便于讨论，下面不妨总是假设：
原问题:
maxZ CX
s.t.
AX b
X
0
对偶问:题minW Y'b
2020/12/13
A'Y C' s.t.
Y 0
一、单纯形法的矩阵描述
原线性规划问题的矩阵表达式加上松弛变量后为：
2020/12/13
原问题
对偶问题
二、对称形式下对偶问题的一般形式
Max z c1 x1 c 2 x 2 c n x n

负指数分布、几何分布、爱尔朗分布等。
服务时间分布
负指数分布、确定型分布、一般分布等。
顾客到达和服务时间的独立性
假设顾客到达和服务时间是相互独立的。
单服务台排队系统
M/M/1排队系统
顾客到达服从泊松分布，服务时间服从负指 数分布，单服务台。
M/D/1排队系统
顾客到达服从泊松分布，服务时间服从确定 型分布，单服务台。
投资组合优化
确定投资组合中各种资产的最 优配置比例，以最大化收益或
最小化风险。
03
整数规划
整数规划问题的数学模型
01
整数规划问题的定 义
整数规划是数学规划的一个分支 ，研究决策变量取整数值的规划 问题。
02
整数规划问题的数 学模型
包括目标函数、约束条件和决策 变量，其中决策变量要求取整数 值。
03
Edmonds-Karp算法
介绍Edmonds-Karp算法的原理、步骤和实现方法，以及其与FordFulkerson算法的比较。
网络最大流问题的应用
列举网络最大流问题在资源分配、任务调度等领域的应用案例。
最小费用流问题
最小费用流问题的基本概 念
介绍最小费用流问题的定义、 分类和应用背景。
Bellman-Ford算法
优点是可以求解较大规模的整数规划问题，缺点是计算量较大，需 要较高的计算精度。
割平面法
割平面法的基本思想
通过添加新的约束条件（割平面）来缩小可行域的范围，从而逼 近最优解。
割平面法的步骤
包括构造割平面、求解子问题和更新割平面三个步骤，通过不断 迭代找到最优解。
割平面法的优缺点
优点是可以处理较复杂的整数规划问题，缺点是构造割平面的难 度较大，需要较高的数学技巧。

三、运筹学的模型化方法
运筹学解决实际问题的方法具体如下： 运筹学解决实际问题的方法具体如下：
（1）提出问题并分析和认清问题 ） （2）建立模型 ） （3）求解模型 ） （4）模型的检验与评价 ） （5）模型结果的实施 ） （6）再检验 ）
三、运筹学的模型化方法
某工厂要做100套钢架 ， 每套用长为 套钢架， 举例 某工厂要做 套钢架 每套用长为2.9m、 、 2.1m和1.5m的圆钢各一根。 已知原料每根长 的圆钢各一根。 和 的圆钢各一根 已知原料每根长7.4m， ， 问应如何下料，可使所用原料最省。 问应如何下料，可使所用原料最省。 （1）分析问题 ） 最简单的做法是： 最简单的做法是：
2.9 7.4 2.1 1.5ቤተ መጻሕፍቲ ባይዱ0.9
有没有其他方案？目标是什么？约束有哪些？ 有没有其他方案？目标是什么？约束有哪些？
三、运筹学的模型化方法
为此我们设计出以下5种下料方案以供套裁用 为此我们设计出以下 种下料方案以供套裁用 方案 长度 2.9 2.1 1.5 合计 料头 截法Ⅰ 截法Ⅱ 截法Ⅲ 截法Ⅳ 截法Ⅴ 截法Ⅰ 截法Ⅱ 截法Ⅲ 截法Ⅳ 截法Ⅴ x1 x2 x3 x4 x5 1 0 3 7.4 0 2 0 1 7.3 0.1 0 2 2 7.2 0.2 1 2 0 7.1 0.3 0 1 3 6.6 0.8
齐王赛马的故事——可用矩阵对策模型来描述。 可用矩阵对策模型来描述。 齐王赛马的故事 可用矩阵对策模型来描述
二、运筹学的发展简史
（二）运筹学起源 运筹学作为一个科学名词出现 作为一个科学名词出现， 运筹学作为一个科学名词出现，是在第二次世界大战 期间。 期间。 当时，英美等国为了对付德国的侵略， 当时，英美等国为了对付德国的侵略，发明制造了包 括雷达在内的一些新式武器， 括雷达在内的一些新式武器，这些武器虽然在技术上 是可行的，但如何有效地运用它们（ 是可行的，但如何有效地运用它们（how to operate them），成了当时的一个重要课题。 ） 成了当时的一个重要课题。 这个课题当时被称为： 这个课题当时被称为：Operational Research —— 运 用研究（操作研究、作业研究、作战研究） 用研究（操作研究、作业研究、作战研究）。 在美国该课题称为： 在美国该课题称为：Operations Research——OR。 。

管理科学与工程学院
何谓“运筹学”？它的英文名称是 课 程 简 介 Operations Research,直译为“作业研 究”，就是研究在经营管理活动中如 何行动，如何以尽可能小的代价，获 取尽可能好的结果，即所谓“最优化” 问题。汉语是世界上最丰富的语言， 中国学者把这门学科意译为“运筹 学”，就是取自古语“运筹于帷幄之 中，决胜于千里之外”，其意为运算 筹划，出谋献策，以最佳策略取胜。 这就极为恰当地概括了这门学科的精 髓。
（3）经济：经济理论特别是数理经济 ）经济： 学派对运筹学影响巨大。 年来， 学派对运筹学影响巨大。近30年来， 年来 经济数学和运筹学互相影响， 经济数学和运筹学互相影响，相互 促进，共同发展。 促进，共同发展。
运筹学在中国： 50年代中期钱学森，许国志引入 华罗庚推广 优选法、统筹法 中国邮递员问题、运输问题
真 实 系 统
数据准备
系统分析 问题描述
模型建立 与修改
模型求解 与检验
结果分析 与实施
运筹学分析的步骤
管理科学与工程学院
4、运筹学的应用 、
早期应用在军事领域，二次大战后转向民用。 早期应用在军事领域，二次大战后转向民用。 1 生产计划 使用运筹学方法从总体上确定适应要求的 生产。 贮存和劳动力安排等计划。 生产 。 贮存和劳动力安排等计划 。 以谋求最 大的利润或最小的成本， 主要用线性规划。 大的利润或最小的成本 ， 主要用线性规划 。 整数规划以及模拟方法来解决此类问题， 整数规划以及模拟方法来解决此类问题 ， 此 外还在生产作业计划日程表的编排， 外还在生产作业计划日程表的编排 ， 合理下 料，配料问题，物料管理等方面的应用。 配料问题，物料管理等方面的应用。 2 市场营销 可把运筹学方法用于广告预算和媒介的选 竞争性的定价、 新产品的开发、 择 ， 竞争性的定价 、 新产品的开发 、 销售计 划的制定等方面。 如美国杜邦公司从50年代 划的制定等方面 。 如美国杜邦公司从 年代 起就非常重视运筹学在市场营销上的应用。 起就非常重视运筹学在市场营销上的应用。