同济大学：《运筹学》课程教学资源（课件讲稿）引言 Operations Research（负责人：陈雄达）

第一章引言 §1 学科简述 §2 线性和非线性规划问题 §3* 一些数学概念 §4凸集和凸函数

1 第一章 引言 • §1 学科简述 • §2 线性和非线性规划问题 • §3* 一些数学概念 • §4 凸集和凸函数

§1 学科简述 ·最优化理论与算法 optimization and algorithms ◆研究在众多的方案中什么样的方案最优以及如何 找出最优方案。 ◆17世纪的Newton极值问题 ◆Lagrange乘数法 ◆1847年，Cauchy最速下降法... 2

2 • 最优化理论与算法（ optimization and algorithms ) ‹研究在众多的方案中什么样的方案最优以及如何 找出最优方案。 ‹17世纪的Newton极值问题 ‹Lagrange 乘数法 ‹1847年，Cauchy 最速下降法…… §1 学科简述

◆20世纪40年代，成为一个学科。 ◆主要分支： ·线性规划 ·非线性规划 ·动态规划 ·整数规划 ·随机规划 ·网络流 3

3 ‹20世纪40年代，成为一个学科。 年代，成为一个学科。 ‹主要分支： • 线性规划 • 非线性规划 • 动态规划 • 整数规划 • 随机规划 • 网络流 ……

>战国时代齐王与田忌赛马的故事 >孙子兵法 >1736年欧拉(Euler)解决著名的哥尼斯堡七桥问题 >1915年哈里斯(Harris): 推导出最优经济订货批量 公式 >1917年爱尔朗(Erlang)进行了关于自动拨号设备 对电话需求影响的实验

4 ¾ 战国时代齐王与田忌赛马的故事 ¾ 孙子兵法 ¾ 1736年欧拉（Euler）解决著名的哥尼斯堡七桥问题 ¾ 1915年哈里斯（Harris）推导出最优经济订货批量 公式 ¾ 1917年爱尔朗（Erlang）进行了关于自动拨号设备 对电话需求影响的实验

>大西洋反潜战 1941-1942年，德国潜艇严密封锁了英吉利海峡，企图办 断英国的生命线，英国海军数次反封锁均不成功。应英国 要求，美国派Morse率一个小组协助研究。 两条重要建议 1、将反潜攻击由反潜舰艇投掷水雷，改为飞机投掷深水炸弹， 起爆深度由100米左右，改为25米左右，即当德方潜艇刚下潜时 攻击效果最佳；（提高效率4-7倍） 2、运送物资的船队及护航舰艇编队，由小规模多批次，改为如 大规模减少批次，损失率将降低。(25%降低到10%)

5 ¾ 大西洋反潜战 1941-1942年，德国潜艇严密封锁了英吉利海峡，企图切 断英国的‘生命线’，英国海军数次反封锁均不成功。应英国的 要求，美国派 Morse 率一个小组协助研究。 两条重要建议 1、将反潜攻击由反潜舰艇投掷水雷，改为飞机投掷深水炸弹， 起爆深度由100米左右，改为25米左右，即当德方潜艇刚下潜时 攻击效果最佳；（提高效率4-7倍） 2、运送物资的船队及护航舰艇编队，由小规模多批次，改为加 大规模，减少批次，损失率将降低。（25%降低到10%）

船只在受到敌机攻击时的逃避策略 对付威胁美国太平洋舰队的日本神风攻击机（自杀飞机） 的问题是军舰应该急速改变航向以扰乱俯冲的自杀飞机的瞄 准，还是应保持航行不变以改善己方防空火力的瞄准？ 运筹小组分析了477次战例，自杀飞机命中战舰172次， 击沉舰只27次。 研究结果： 大舰受到俯冲的神风机攻击时，应该急速地改变航线； 而小舰则应该慢慢变。还发现当攻击机从高空俯冲时，舰只 应以船舷迎向攻击机；而从低空俯冲时，应以首尾相向

6 ¾ 船只在受到敌机攻击时的逃避策略 对付威胁美国太平洋舰队的日本神风攻击机（自杀飞机） 的问题是军舰应该急速改变航向以扰乱俯冲的自杀飞机的瞄 准，还是应保持航行不变以改善己方防空火力的瞄准？ 运筹小组分析了477次战例，自杀飞机命中战舰172次， 击沉舰只27次。 研究结果： 大舰受到俯冲的神风机攻击时，应该急速地改变航线； 而小舰则应该慢慢变。还发现当攻击机从高空俯冲时，舰只 应以船舷迎向攻击机；而从低空俯冲时，应以首尾相向

·生产计划：生产作业的计划、日程表的编排、合理下 料、配料问题、物料管理等，追求利润最大化和成本 最小化 ·运输问题：确定最小成本的运输线路、物资的调拨、 运输工具的调度以及建厂地址的选择等 ·军事指挥：最佳作战方案的确定等 农田规划：确定农作物的合理布局，保持高产稳产 ·财务和会计：预测、贷款、成本分析、定价、证券管 理、现金管理等

7 • 生产计划：生产作业的计划、日程表的编排、合理下 料、配料问题、物料管理等，追求利润最大化和成本 最小化 • 运输问题：确定最小成本的运输线路、物资的调拨、 运输工具的调度以及建厂地址的选择等 • 军事指挥：最佳作战方案的确定等 • 农田规划：确定农作物的合理布局，保持高产稳产 • 财务和会计：预测、贷款、成本分析、定价、证券管 理、现金管理等

教材及参考书目： 1、《最优化理论与算法》 陈宝林编 清华大学出版社 2005.10 2、《运筹学（第三版)》 《运筹学》教材编写组 清华大学出版社 2005.06 3、《数学规划与组合优化》】 姚恩瑜 何勇 陈仕平 浙江大学出版社 2005.05 4、《Nonlinear programming:theory and algorithms》 Bazaraa MS,Shetty CM.1979 8 Go back

8 教材及参考书目： 1、《最优化理论与算法》 陈宝林编 清华大学出版社 2005.10 2、《运筹学（第三版）》 《运筹学》教材编写组 清华大学出版社 2005.06 3、《数学规划与组合优化》 姚恩瑜 何勇 陈仕平 浙江大学出版社 2005.05 4、《Nonlinear programming：theory and algorithms》 Bazaraa MS， Shetty CM. 1979 Go back

§2线性与非线性规划问题 1.2.1引例 ·例1农业生产计划问题 某村计划在1O0公顷土地上种植A、B、C 三种农作物，可提供的劳力、粪肥和化 肥等资源的数量，种植每公顷农作物所 需这三种资源的数量以及获得的利润如 表（1-1)所示：

9 §2 线性与非线性规划问题 1.2.1 引例 • 例1 农业生产计划问题 某村计划在100公顷土地上种植 A 、 B 、C 三种农作物，可提供的劳力、粪肥和化 肥等资源的数量，种植每公顷农作物所 需这三种资源的数量以及获得的利润如 表（1-1）所示：

用工 粪肥 化肥（千 利润 (吨) 克) (元) A 450 35 350 1500 B 600 25 400 1200 C 900 30 300 1800 资 6300 33000 源 0 3300 其中一个劳动力干一天为1个工。试确定三种农作物 的种植面积，使利润最大。 10

10 33000 3300 6300 0 资 源 C 900 30 300 1800 B 600 25 400 1200 A 450 35 350 1500 利润 （元） 化肥（千 克） 粪肥 （吨） 用工 其中一个劳动力干一天为1个工。试确定三种农作物 的种植面积，使利润最大