线性规划第一章

1、1.1 运筹学产生与发展运筹学产生与发展1.2 运筹学的主要内容运筹学的主要内容1.3 运筹学在工商管理中的应用运筹学在工商管理中的应用1.4 学习运筹学的基本原则学习运筹学的基本原则-学以致用学以致用1.5 本课程的教材及参考书本课程的教材及参考书1.6 本课程的特点和要求本课程的特点和要求1.7 本课程授课方式与考核本课程授课方式与考核 本章主要内容：本章主要内容：Page 3“想泡壶茶喝。当时的情况是：开水没有，开水壶要洗，想泡壶茶喝。当时的情况是：开水没有，开水壶要洗，茶壶茶杯要洗，火已生了，茶叶也有了，怎么办茶壶茶杯要洗，火已生了，茶叶也有了，怎么办?”?”Page 4一、问题描述一

2、、问题描述1.1.目标：目标：喝到一碗清新的热茶。喝到一碗清新的热茶。2.2.条件：条件：已有一个茶壶、一包好茶叶、一个燃着的火炉已有一个茶壶、一包好茶叶、一个燃着的火炉和可用的凉水水源。和可用的凉水水源。3.3.其它要求：其它要求：以最节约资源的方式实现目标。以最节约资源的方式实现目标。4.4.运筹学研究任务：运筹学研究任务：为解决喝茶问题设计一个行动计划为解决喝茶问题设计一个行动计划 ( (设计一个解决泡茶问题的行动计划设计一个解决泡茶问题的行动计划) )。 Page 51.1.资源需求资源需求 根据我们的日常经验，现代人类的活动通常需要人、财、根据我们的日常经验，现代人类的活动通常需要人

3、、财、物等类资源。在这个泡茶问题上，不涉及资金，所需的资物等类资源。在这个泡茶问题上，不涉及资金，所需的资源包括：凉水、茶壶、茶叶、茶碗、火炉。这些资源目前源包括：凉水、茶壶、茶叶、茶碗、火炉。这些资源目前都已齐备，且假设除人外没有限制。都已齐备，且假设除人外没有限制。2 .2 .目标要求目标要求 以以最节约资源最节约资源的方式泡一壶好茶。的方式泡一壶好茶。 这个问题中，前面提到的各项资源除了人力资源外，都这个问题中，前面提到的各项资源除了人力资源外，都是没有限制的。但实际上，茶壶的大小是确定的，因而所是没有限制的。但实际上，茶壶的大小是确定的，因而所用水是确定的。再假定炉火的发热量及热效率是

4、确定的，用水是确定的。再假定炉火的发热量及热效率是确定的，那么，一旦装满水的茶壶放到火上，其消耗的能源也是确那么，一旦装满水的茶壶放到火上，其消耗的能源也是确定的。茶叶使用量是有定额的。定的。茶叶使用量是有定额的。 所以，在泡茶问题上，前述各项资源除随机干扰外，不所以，在泡茶问题上，前述各项资源除随机干扰外，不存在节约问题。这个问题，唯一涉及的节约问题是关于一存在节约问题。这个问题，唯一涉及的节约问题是关于一种既无限又有限的资源种既无限又有限的资源时间的节约时间的节约。二、问题分析二、问题分析Page 63.3.运筹学研究运筹学研究任务任务界定界定 设计一个解决泡茶问题的行动计划，要求合理安排

5、各道设计一个解决泡茶问题的行动计划，要求合理安排各道工序，最大限度节约时间。工序，最大限度节约时间。二、问题分析二、问题分析Page 7三、定性策划几个备选方案三、定性策划几个备选方案根据日常经验，对以上泡茶问题可以有以下三种解法：根据日常经验，对以上泡茶问题可以有以下三种解法：甲：甲：洗净水壶；洗净水壶；灌上凉水；灌上凉水；壶放在火上；壶放在火上；等水开；等水开；水开后，以最快的速度洗茶杯，找茶叶；水开后，以最快的速度洗茶杯，找茶叶；泡茶，待茶泡好；泡茶，待茶泡好；喝茶。喝茶。乙：乙：洗净水壶；洗净水壶；洗茶杯；洗茶杯；找好茶叶；找好茶叶；灌凉水；灌凉水；壶放壶放火上；火上；等水开；等水开；

6、水开后，用准备好的茶杯、茶叶泡茶；水开后，用准备好的茶杯、茶叶泡茶；等待茶泡好；等待茶泡好；喝茶。喝茶。丙：丙：洗净水壶；洗净水壶；灌凉水；灌凉水；壶放火上；壶放火上；洗茶杯；洗茶杯；拿茶拿茶叶；叶；水开之前，可干一些其它事；水开之前，可干一些其它事；水开，泡茶；水开，泡茶；喝茶。喝茶。Page 81.1.列出泡茶所需的全部工序列出泡茶所需的全部工序 2.2.确定每道工序所需的时间确定每道工序所需的时间3.3.确定各道工序之间的时间连接关系确定各道工序之间的时间连接关系4.4.分析计算每种方案所需的总时间分析计算每种方案所需的总时间5.5.做出比较结论做出比较结论Page 9工序列表工序列表序

7、号序号名称名称紧前工序紧前工序工序时间工序时间( (分分) )1 1洗壶洗壶无无1 12 2灌水灌水1 10.50.53 3放壶放壶2 20.30.34 4等水开等水开3 315155 5洗杯洗杯无无1 16 6找茶叶找茶叶无无1 17 7泡茶泡茶3 3，5 5，6 62.22.28 8喝茶喝茶7 7洗壶洗壶灌水灌水放壶放壶洗杯洗杯泡茶泡茶拿茶叶拿茶叶等水开等水开115 1 10.30.5喝茶喝茶2.20.3丙：丙：洗壶洗壶洗杯洗杯找茶叶找茶叶灌水灌水等水开等水开放壶放壶泡茶泡茶1150.30.5 11喝茶喝茶2.2乙：乙：洗壶洗壶灌水灌水放壶放壶等水开等水开泡茶泡茶洗杯，找茶叶洗杯，找茶叶喝

8、茶喝茶12.22150.30.5甲：甲：Page 11甲方案总时间甲方案总时间=1+0.5+0.3+15+2+2.2=21=1+0.5+0.3+15+2+2.2=21乙方案总时间乙方案总时间=1+1+1+0.5+0.3+15+2.2=21=1+1+1+0.5+0.3+15+2.2=21丙方案总时间丙方案总时间=1+0.5+(0.3+15)+2.2=19=1+0.5+(0.3+15)+2.2=19分析结果：丙方案最节约时间。分析结果：丙方案最节约时间。方案建议：丙方案建议：丙Page 12泡茶工程经验总结泡茶工程经验总结几大步骤：几大步骤：确定问题确定问题目标分析目标分析需求分析需求分析方案策划

9、方案策划系统分析（统计、计算、比较）系统分析（统计、计算、比较）决策建议决策建议方案实施方案实施原理：原理： 最优化、并行统筹、工序图法最优化、并行统筹、工序图法Page 13 自人类社会诞生以来，人们都一直在经历着运用和筹划的决策过程。自人类社会诞生以来，人们都一直在经历着运用和筹划的决策过程。而运筹学的一些朴素思想可以追溯到很早以前。历史上曾记载着很多巧而运筹学的一些朴素思想可以追溯到很早以前。历史上曾记载着很多巧妙的运筹事例。妙的运筹事例。一、早期朴素的运筹思想一、早期朴素的运筹思想1.1.都江堰水利工程都江堰水利工程 1)“1)“鱼嘴鱼嘴”岷江分水工程：将岷江水有控制地引入内江。岷江分

10、水工程：将岷江水有控制地引入内江。 2)“2)“飞沙堰飞沙堰”分洪排沙工程：将泥沙排入外江。分洪排沙工程：将泥沙排入外江。 3)“3)“宝瓶口宝瓶口”引水工程：除沙后的江水引入水网干道。引水工程：除沙后的江水引入水网干道。 2.2.丁谓的皇宫修复工程丁谓的皇宫修复工程 当时任务：当时任务：1 1）取土）取土 2 2）外地材料的储运）外地材料的储运 3 3）处理瓦砾）处理瓦砾“一沟三用一沟三用”解决了这解决了这三个问题。三个问题。Page 14Page 15Page 16Page 173.3.田忌赛马田忌赛马齐王齐王上上中中下下田忌田忌下下上上中中最终净胜一局，赢得最终净胜一局，赢得100010

11、00金。金。 二、运筹学的产生与发展二、运筹学的产生与发展 但是运筹学作为一个科学名词出现，并形成一门独立的、具有特色但是运筹学作为一个科学名词出现，并形成一门独立的、具有特色的学科，则是的学科，则是2020世纪世纪3030年代末以后，由于二次世界大战期间军事上的需年代末以后，由于二次世界大战期间军事上的需要及战后经济的发展，它才逐渐产生和发展起来的。代表性的事件：要及战后经济的发展，它才逐渐产生和发展起来的。代表性的事件：1.1.鲍德西（鲍德西（BawdseyBawdsey）雷达站的研究（）雷达站的研究（19351935年）：年）：如何合理运用雷达有如何合理运用雷达有效地对付德军德空袭。效地

12、对付德军德空袭。 2.2.大西洋反潜战（大西洋反潜战（19441944年）年） ：在各种情况下如何调整反潜深水炸弹的在各种情况下如何调整反潜深水炸弹的爆炸深度，才能增加对德国潜艇的杀伤力等。爆炸深度，才能增加对德国潜艇的杀伤力等。3.3.军用物质运输（军用物质运输（4040年代）：年代）：对商船如何进行编队护航，使船队遭受德对商船如何进行编队护航，使船队遭受德国潜艇攻击时损失最少。国潜艇攻击时损失最少。Page 18背景： 19351935年，英国科学家年，英国科学家R.Watson-WartR.Watson-Wart发明了雷达。丘吉尔发明了雷达。丘吉尔命令在英国东海岸的命令在英国东海岸的Ba

13、wdseyBawdsey建立了一个秘密雷达站，用来发建立了一个秘密雷达站，用来发现敌机。但在一次空防演习中发现，由这些雷达送来的现敌机。但在一次空防演习中发现，由这些雷达送来的( (常常常常是互相矛盾的是互相矛盾的) )信息，需要加以协调和关联，才能改进作战效信息，需要加以协调和关联，才能改进作战效能。能。 当时，德国已拥有一支强大的空军，起飞当时，德国已拥有一支强大的空军，起飞1717分钟即到达英分钟即到达英国本土。在如此短的时间内，如何预警和拦截成为一大难题。国本土。在如此短的时间内，如何预警和拦截成为一大难题。 19391939年由曼彻斯特大学物理学家、英国战斗机司令部顾问、年由曼彻斯特

14、大学物理学家、英国战斗机司令部顾问、战后获得诺贝尔奖金的战后获得诺贝尔奖金的P.M.S.BlackettP.M.S.Blackett为首，组织了一个小组，为首，组织了一个小组，代号代号“BlackettBlackett马戏团马戏团”。这个小组包括三名心理学家、两名。这个小组包括三名心理学家、两名数学家、两名应用数学家、一名天文物理学家、一名普通物理数学家、两名应用数学家、一名天文物理学家、一名普通物理学家、一名海军军官、一名陆军军官、一名测量员。学家、一名海军军官、一名陆军军官、一名测量员。Page 19研究的问题研究的问题：设计将雷达信息传送到指挥系统和武器系统的最佳：设计将雷达信息传送到指

15、挥系统和武器系统的最佳方式；雷达与武器的最佳配置；对探测、信息传递、作战指挥、方式；雷达与武器的最佳配置；对探测、信息传递、作战指挥、战斗机与武器的协调，作了系统的研究战斗机与武器的协调，作了系统的研究. .研究目的研究目的: :如何有效地使用雷达控制的防空系统。如何有效地使用雷达控制的防空系统。研究结果研究结果: :勃兰凯特小组通过多次现场实验，使雷达和高炮配合勃兰凯特小组通过多次现场实验，使雷达和高炮配合达到最佳状态。由于该小组卓有成效的工作，雷达的优越性充分达到最佳状态。由于该小组卓有成效的工作，雷达的优越性充分体现出来，并获得成功。体现出来，并获得成功。“BlackettBlacket

16、t马戏团马戏团”在秘密报告中使用在秘密报告中使用了了“Operational Research”Operational Research”，即，即“运筹学运筹学”。 当时德国雷达在技术性能指标上虽然优于英国，但德国人当时德国雷达在技术性能指标上虽然优于英国，但德国人忽略了对包括雷达在内的防空系统的有关操作的研究，其防空系忽略了对包括雷达在内的防空系统的有关操作的研究，其防空系统效果因而始终不如英国。统效果因而始终不如英国。Page 20背景：背景： 1941-19421941-1942年，德国潜艇严密封锁了英吉利海峡，企图年，德国潜艇严密封锁了英吉利海峡，企图切断英国的切断英国的“生命线生命线

17、”。海军几次反封锁，均不成功。海军几次反封锁，均不成功。 19431943年年3 3月，为对德国在大西洋的潜艇实现更加有效的月，为对德国在大西洋的潜艇实现更加有效的攻击，应英国要求，美国海军成立了由物理学家莫尔斯领攻击，应英国要求，美国海军成立了由物理学家莫尔斯领导的跨学科小组。小组通过对潜艇的搜索研究发现，飞机导的跨学科小组。小组通过对潜艇的搜索研究发现，飞机一般在潜艇上浮的时候对其实施攻击，这时潜艇深度约为一般在潜艇上浮的时候对其实施攻击，这时潜艇深度约为3030英尺，而美军的深水炸弹的爆炸深度至少为英尺，而美军的深水炸弹的爆炸深度至少为7575英尺，杀英尺，杀伤范围伤范围2020英尺左右

18、，这样攻击就对德国潜艇威胁有限。根英尺左右，这样攻击就对德国潜艇威胁有限。根据这一情况，莫尔斯小组提议对深水炸即作技术改进，使据这一情况，莫尔斯小组提议对深水炸即作技术改进，使其在水深其在水深3030英尺上下爆炸。英尺上下爆炸。Page 21研究方案及效果：经过多方实地考察，最后提出了两条重要建议：经过多方实地考察，最后提出了两条重要建议： 将反潜攻击由将反潜攻击由反潜潜艇投掷投掷水雷，改为，改为飞机投掷投掷深水炸弹。起爆深度由起爆深度由100100米左右改为米左右改为2525米左右。即当潜艇刚下潜时攻击效米左右。即当潜艇刚下潜时攻击效果最佳。根据这一情况，莫尔斯小组建议对深水炸即作技术改进，

19、果最佳。根据这一情况，莫尔斯小组建议对深水炸即作技术改进，使其在水深使其在水深3030英尺上下爆炸。仅此一项措施，使对潜艇的击沉率英尺上下爆炸。仅此一项措施，使对潜艇的击沉率增加了增加了6 6倍。倍。( (提高效率提高效率4-74-7倍倍) ) 运送物资的船队及护航舰队编队，由小规模多批次，改为加运送物资的船队及护航舰队编队，由小规模多批次，改为加大规模、减少批次，这样，损失率将减少。（大规模、减少批次，这样，损失率将减少。（25%25%下降到下降到10%10%） 丘吉尔采纳了丘吉尔采纳了MORSEMORSE的建议，最终成功地打破封锁，并重创的建议，最终成功地打破封锁，并重创了德国潜艇。了德国

20、潜艇。MORSEMORSE同时获得英国和美国的最高勋章。同时获得英国和美国的最高勋章。 Page 22二战早期的欧洲军用物质都是从美国用商船通过大西洋运二战早期的欧洲军用物质都是从美国用商船通过大西洋运往欧洲，但发现在公海里受到德军飞机的轰炸，英美商船往欧洲，但发现在公海里受到德军飞机的轰炸，英美商船为了对付德国飞机的袭击，在船上装设了高炮，但这些高为了对付德国飞机的袭击，在船上装设了高炮，但这些高炮击落的敌机很少（占来袭敌机的炮击落的敌机很少（占来袭敌机的4 4），而且高炮的安装），而且高炮的安装维修费高，这时有人提出将高炮拆除。维修费高，这时有人提出将高炮拆除。但是运筹分析人员指出，安装高

21、炮的不是击落敌机，而是但是运筹分析人员指出，安装高炮的不是击落敌机，而是保护商船安全如期到达目的地。保护商船安全如期到达目的地。实战统计显示，不安装高炮的商船损失率大于实战统计显示，不安装高炮的商船损失率大于2525，安装，安装高炮后，致使敌机不敢低飞，商船的损失率降到了高炮后，致使敌机不敢低飞，商船的损失率降到了1010以以下，可见安装高炮是必需的。下，可见安装高炮是必需的。( (保护了我们自己的商船，目保护了我们自己的商船，目标达到了。标达到了。) ) Page 23 这些运筹小组大量出色的工作，不仅为盟国在军事上重挫纳粹德国这些运筹小组大量出色的工作，不仅为盟国在军事上重挫纳粹德国做出了

22、重大贡献，也为运筹学的发展积累了丰富的材料。不过，当时研做出了重大贡献，也为运筹学的发展积累了丰富的材料。不过，当时研究和解决的问题都是短期的和战术性的。究和解决的问题都是短期的和战术性的。 二次世界大战后，一些运筹专家把研究的重点转向了民用问题，转二次世界大战后，一些运筹专家把研究的重点转向了民用问题，转向了国民经济的恢复和发展，即开始着手研究战略性问题（包括军事战向了国民经济的恢复和发展，即开始着手研究战略性问题（包括军事战略问题），其中以美国的兰德公司（略问题），其中以美国的兰德公司（RANDRAND）最为著名。）最为著名。 总之，从以上运筹学的发展简史可见，运筹学的发展过程可分为三总之

23、，从以上运筹学的发展简史可见，运筹学的发展过程可分为三个阶段：个阶段： 1 1）19461946年以前，运筹学主要用于军事；年以前，运筹学主要用于军事； 2 2）1947-601947-60年代上半期，运筹学主要用于工厂企业管理，并在理论年代上半期，运筹学主要用于工厂企业管理，并在理论上趋于成熟；上趋于成熟； 3 3）6060年代下半期以来，其主要特征是，研究的系统有小到大，并逐年代下半期以来，其主要特征是，研究的系统有小到大，并逐渐和系统分析想结合，和未来学相结合，和社会科学相结合。渐和系统分析想结合，和未来学相结合，和社会科学相结合。 Page 24总结：总结： 运筹学（运筹学（Opera

24、tions Research），系统工程的最重要的），系统工程的最重要的理论基础之一，在美国有人把运筹学称之为管理科学理论基础之一，在美国有人把运筹学称之为管理科学(Management Science)，运筹学所研究的问题，可简单地归，运筹学所研究的问题，可简单地归结为一句话：结为一句话：“依照给定条件和目标，从众多方案中选择最佳方案依照给定条件和目标，从众多方案中选择最佳方案”故有人称之为最优化技术。故有人称之为最优化技术。Page 25数学规划（数学规划（线性规划、整数规划、目标规划线性规划、整数规划、目标规划、动态、动态规划等）规划等）图论图论存储论存储论排队论排队论对策论对策论排序与

25、统筹方法排序与统筹方法决策分析决策分析Page 26运筹学在工商管理中的应用涉及几个方面：运筹学在工商管理中的应用涉及几个方面： 生产计划生产计划 运输问题运输问题 人事管理人事管理 库存管理库存管理 市场营销市场营销 财务和会计财务和会计1.另外，还应用于设备维修、更新和可靠性分析，项目的选另外，还应用于设备维修、更新和可靠性分析，项目的选择与评价，工程优化设计等。择与评价，工程优化设计等。Page 27Interface上发表的部分获奖项目上发表的部分获奖项目组织组织应用应用效果效果联合航空公司联合航空公司在满足乘客需求的前提下，以最低成本进在满足乘客需求的前提下，以最低成本进行订票及机场

26、工作班次安排行订票及机场工作班次安排每年节约成本每年节约成本600600万美元万美元CitgoCitgo石油公司石油公司优化炼油程序及产品供应、配送和营销优化炼油程序及产品供应、配送和营销每年节约成本每年节约成本70007000万万AT&TAT&T优化商业用户的电话销售中心选址优化商业用户的电话销售中心选址每年节约成本每年节约成本4.064.06亿美元，销亿美元，销售额大幅增加售额大幅增加标准品牌公司标准品牌公司控制成本库存（制定最优再定购点和定购控制成本库存（制定最优再定购点和定购量确保安全库存）量确保安全库存）每年节约成本每年节约成本380380万美元万美元法国国家铁路公司法国国家铁路公司

27、制定最优铁路时刻表并调整铁路日运营量制定最优铁路时刻表并调整铁路日运营量每年节约成本每年节约成本15001500万美元，万美元，年收入大幅增加。年收入大幅增加。Taco BellTaco Bell优化员工安排，以最低成本服务客户优化员工安排，以最低成本服务客户每年节约成本每年节约成本13001300万美元万美元DeltaDelta航空公司航空公司优化配置上千个国内航线航班来实现利润优化配置上千个国内航线航班来实现利润最大化最大化每年节约成本每年节约成本1 1亿美元亿美元Page 28一、运筹学在传统教学中存在的问题：不能学以致用。一、运筹学在传统教学中存在的问题：不能学以致用。 原因：原因：1

28、 1）观念上的原因：死学，没有理解、掌握。）观念上的原因：死学，没有理解、掌握。 2 2）对运筹学的理解是陈旧的。）对运筹学的理解是陈旧的。二、学习运筹学的原则二、学习运筹学的原则学以致用学以致用 1.1.学习运筹学要结合实际的应用，不要被一些概念、理论的困难学习运筹学要结合实际的应用，不要被一些概念、理论的困难吓倒。吓倒。 2.2.学习运筹学要把注意力放在学习运筹学要把注意力放在“结合实际问题建立运筹学模型结合实际问题建立运筹学模型”和和“解决问题的方案或模型的解解决问题的方案或模型的解”两头，中间的计算过程尽可能让计两头，中间的计算过程尽可能让计算机软件去完成。算机软件去完成。 3.3.学

29、习运筹学是为了用于实践，解决实际问题。以前重视人工计学习运筹学是为了用于实践，解决实际问题。以前重视人工计算是因为没有计算机，现在有了就应该好好利用。算是因为没有计算机，现在有了就应该好好利用。Page 29 例如，有人要从北京去乌鲁木齐。在一百多年以前，我们应例如，有人要从北京去乌鲁木齐。在一百多年以前，我们应该告诉他如何配备粮草、银两、衣物，如何选购马匹、马车，挑该告诉他如何配备粮草、银两、衣物，如何选购马匹、马车，挑选马夫和保镖，如何根据天气、地理条件和社会诸因素来确定行选马夫和保镖，如何根据天气、地理条件和社会诸因素来确定行车路线和行程，更重要的是如何在几个月的行程中处理吃穿住行，车路线和行程，更重要的是如何在几个月的行程