川大《运筹学》课件-序论0

1、运 筹 帷 幄 之 中决 胜 千 里 之 外运 筹 学 课 件绪 论Introduction运筹学的概况最优化模型教学计划与方法 绪 论运筹学的由来与发展运筹学的性质与特点 运筹学的主要内容运筹学的发展趋势运筹学的学科地位运 筹 学 概 况名称的由来 Operation Research 运筹帷幄 “史记” 运作研究发展历程 运筹学的由来与发展二战以前萌芽二战期间产生五六十年代发展七八十年代成熟一、运筹学的起源（国内、国外）：国外：1938年，英国为解决空袭的早期预警，做好反侵略战争准备，大量使用雷达，随着雷达的使用，出现了来自不同雷达站的信息及雷达站同整个防空作战系统的协调问题。1938年7

2、月，Bawdsey雷达站的负责人A.P.Rowe（罗伊）提出立即进行整个防空作战系统运行的研究，1939年，以英国的物理学家，时任英国战斗机司令部科学顾问的Blackett为首，联合心理学家、数学家、应用数学家、天文物理学家、海军陆军军官组成了一个代号“Blackett马戏团”的研究小组，专门就改进防空系统进行研究。在他们的报告中使用了“Operational Research”一词，这便是我们所说的运筹学。国内：国内最早的运筹学思想源于齐王与田忌赛马。 系统的整体优化、 多学科的配合、 模型方法的应用系统的整体优化：所谓系统即是由相互关联、相互制约、相互作用的一些部分组成的具有某种功能的有机

3、整体。而运筹学不是对每一个决策行为孤立的进行评价，而是把它同系统内所有其他重要的相互作用结合起来作出评价，把相互影响的各方面作为一个统一体，从总体利益出发，寻找一个优化方案。运筹学的性质与特点多学科的配合：一个企业的有效管理涉及到很多方面，运筹学的研究要吸收不同领域、不同学科的知识和技术。模型方法的应用：1。分析与表述问题：2。建立模型：3。对问题求解：4。对模型和由模型导出的解进行实验5。建立起对解的有效控制6。方案的实施线性规划数学规划非线性规划整数规划动态规划学科内容多目标规划组合优化最优计数问题网络优化排序问题统筹图随机优化对策论排队论库存论决策分析可靠性分析运筹学的主要内容成熟的学科

4、分支向纵深发展新的研究领域产生与新的技术结合与其他学科的结合加强传统优化观念不断变化运筹学的发展趋势模型要素 变量可控因素 目标优化的动力和依据 约束内部条件和外部约束研究内容 建模概念最优性条件算法灵敏度分析最优化模型 实例某工厂用三种原料生产三种产品，已知的条件如表所示，试制订总利润最大的生产计划单位产品所需原料数量（公斤）产品Q1产品Q2产品Q3原料可用量（公斤/日）原料P12301500原料P2024800原料P33252000单位产品的利润（千元）3541. 生 产 计 划 问 题问 题 分 析模 型软 件 计 算 结 果某食品公司经销的主要产品之一是糖果。它下面设有三个加工厂，每天

5、的生产量分别为:A17吨， A24吨，A39吨。拟把这些糖果运往四个门市销售，各门市的每日销量为B13吨， B26吨，B35吨，B46吨。运价表如下，问：如何运送使总运费最小？2. 运 输 问 题B1B2B3B4 A1311310 A21928 A374105表1：单位运价表门市加工厂方案B1B2B3B4产量A1527A2314A3639销 量3656最优方案3. 整数规划 问 题证券投资：把一定的资金投入到合适的有价证券上以规避风险并获得最大的利润。项目投资：财团或银行把资金投入到若干项目中以获得中长期的收益最大。4. 组合投资 问 题某财团有 万元的资金，经出其考察选中 个投资项目，每个项

6、目只能投资一次。其中第 个项目需投资金额为 万元，预计5年后获利 （ ）万元，问应如何选择项目使得5年后总收益最大？模 型5. 目标规划 问 题例 某电视机厂装配黑白和彩色两种电视机，每装配一台电视机需占用装配线1小时，装配线每周计划开动40小时。预计市场每周彩色电视机的销量是24台，每台可获利80元；黑白电视机的销量是30台，每台可获利40元。该厂确定的目标为：第一优先级：充分利用装配线每周计划开动40小时；第二优先级：允许装配线加班；但加班时间每周尽量不超过10小时；第三优先级：装配电视机的数量尽量满足市场需要。因彩色电视机的利润高，取其权系数为2。试建立这问题的目标规划模型，并求解黑白和

7、彩色电视机的产量。 (d)0102030405060102030405060(a)(b)(c)(24, 26)满足P1, P2的可行域满足P1, P2, P3(c)的可行域目标规划的最优解d1+d2+d4+例1：18世纪，在东普鲁士哥尼斯堡有座桥，如下图，一个散步者能否走遍七座桥，每座桥只走过一次，最后回到出发点？ 6. 图论 问 题定义：（Euler开（闭）迹、Euler迹、可一笔画）解：1。模拟图：以顶点表陆地，以边表桥，得4个顶点的模拟图。2。问题等价于：能否有一条闭迹包含模拟图的所有边，即：模拟图含有Euler闭迹吗？3。求解：假设图G含Euler闭迹。因为闭迹是连通的，所以图G也连通。又因为每个顶点既能到达也能离开，所以图G的每个顶点度都是偶数。即：图G含Euler闭迹的必要条件：连通且没有奇度顶点。所以，“七桥问题”是不可能的。若有一条开（闭）迹含图G的所有顶点和边，则称其为Euler开（闭）迹， Euler开（闭）迹统称Euler迹。可一笔画：从起点到终点一笔画完。华罗庚的例子：有客来访，要请他饮茶，于是要做几件事：洗茶杯、洗杯盖、烧开水、泡茶到端茶。7. 关键路线法 问 题客来沏茶本问题的几道“工序”有次序, 洗杯盖 端茶 烧水 泡茶 洗杯 虚 251020.5教学计划 数学规划部分：线性规划，对偶问题，整数规划，目标规划，动