南京应用运筹学线性规划

《南京应用运筹学线性规划》由会员分享，可在线阅读，更多相关《南京应用运筹学线性规划（193页珍藏版）》请在金锄头文库上搜索。

1、南京大学 周 晶 教授 jzhou,运筹 学,问 题？,什么是运筹学？ 为什么要学习运筹学？ 要学习哪些内容？,什么是运筹学？,运筹帷幄，决策千里 作为一门学科诞生于20世纪30年代末期。运筹学一词在英国称为operational research，在美国称为operations research，缩写为O.R.。 在大英百科全书中，“运筹学是一门应用于管理有组织系统的科学”，“运筹学为掌握这类系统的人提供决策目标和数量分析的工具”。,朴素的运筹思想 都江堰水利工程 战国时期（大约公元前250年）川西太守李冰父子主持修建。其目标是：利用岷江上游的水资源灌溉川西平原。追求的效益还有防洪与航运。其

2、总体构思是系统思想的杰出运用。,丁谓的皇宫修复工程 北宋年间，丁谓负责修复火毁的开封皇宫。他的施工方案是：先将工程皇宫前的一条大街挖成一条大沟，将大沟与汴水相通。使用挖出的土就地制砖，令与汴水相连形成的河道承担繁重的运输任务；修复工程完成后，实施大沟排水，并将原废墟物回填，修复成原来的大街。丁谓将取材、生产、运输及废墟物的处理用“一沟三用”巧妙地解决了。,田忌赛马 齐王要与大臣田忌赛马，双方各出上、中、下马各一匹，对局三次，每次胜负1000金。田忌在好友、著名的军事谋略家孙膑的指导下，以以下安排： 齐王 上 中 下 田忌 下 上 中 最终净胜一局，赢得1000金。,运筹学的三大来源,军事 运筹

3、帷幄、决策千里 第二次世界大战 经济 莱昂惕夫的投入产出模型 管理 著名经济学家西蒙有一句名言：“管理就是决策”,鲍德西（Bawdsey）雷达站的研究（1935年） 1935年，英国科学家R.Watson-Wart发明了雷达。丘吉尔命令在英国东海岸的Bawdsey建立了一个秘密雷达站。当时，德国已拥有一支强大的空军，起飞17分钟即到达英国本土。在如此短的时间内，如何预警和拦截成为一大难题。,1939年由曼彻斯特大学物理学家、英国战斗机司令部顾问、战后获得诺贝尔奖金的P.M.S.Blackett为首，组织了一个小组，代号“Blackett马戏团”。这个小组包括三名心理学家、两名数学家、两名应用数

4、学家、一名天文物理学家、一名普通物理学家、一名海军军官、一名陆军军官、一名测量员。,研究的问题是：设计将雷达信息传送到指挥系统和武器系统的最佳方式；雷达与武器的最佳配置；对探测、信息传递、作战指挥、战斗机与武器的协调，作了系统的研究，并获得成功。“Blackett马戏团”在秘密报告中使用了“Operational Research”，即“运筹学”。,大西洋反潜战（1942年） 1942年，美国大西洋舰队反潜战官员W.D.Baker舰长请求成立反潜战运筹组，麻省理工学院的物理学家P.W.Morse被请来担任计划与监督。 Morse 出色的工作之一，是协助英国打破了德国对英吉利海峡的封锁。,194

5、1-1942年，德国潜艇严密封锁了英吉利海峡，企图切断英国的“生命线”。海军几次反封锁，均不成功。应英国要求，美国派Morse率领一个小组去协助。Morse经过多方实地考察，最后提出了两条重要建议：,将反潜攻击由反潜潜艇投掷水雷，改为飞机投掷深水炸弹。起爆深度由100米左右改为25米左右。即当潜艇刚下潜时攻击效果最佳。(提高效率4-7倍) 运送物资的船队及护航舰队编队，由小规模多批次，改为加大规模、减少批次，这样，损失率将减少。（25%下降到10%）,管理与运筹学,泰勒的科学管理方法 对工人提出科学的操作方法（时间动作研究） 对工人进行科学的选择、培训和提高（能力与工作相适应） 制定科学的工艺

6、流程，并以文件的形式加以固定和推广（工作定额与标准化） 使管理和劳动相分离（计划与执行分离） 在工资制度上实行差别计件制（差别计件付酬制）,各种管理科学学派,科学管理原理 社会技术系统学派 行为科学学派 人际关系行为学派 管理过程学派 社会合作系统学派 决策理论学派 沟通信息学派 管理科学学派 经验案例学派 数理学派 系统管理学派 经理角色学派 群体行为学派 战略管理 创新管理 知识管理 ,决策制定主体（管理者）,管理者的多重角色,- 认可并奖励业绩 - 不断完善个人管理技能 - 给予指导建议 - 不断提出反馈 - 员工发展,- 构建有效团队 - 倾听 - 调解冲突,- 设定富于挑战但可以 达

7、到的业绩标准 - 提供及时精确的信息 - 控制质量,- 倡导变化,- 影响高层领导的决策 - 争取资源实现团队目标,- 实现经营目标 - 满足客户的需要,- 明确阐述目标 - 全盘考虑,- 计划资源的 合理利用,灵活性,控制,公司外部的重点,公司内部的重点,$,教练员 创新者,促导者 经纪人,监理者 生产者,协调员 指挥者,激励 适应,政策 目标,决策制定决策环境,不确定性程度：确定、风险、不确定 可重复性程度：程序、非程序 人员参与程度：个体、群体 主体价值判断：最优、满意、合理,决策制定决策过程,识别问题,方案执行,观察,方案选择,方案评价,备择方案,理解问题,设定目标,解决问题周期,反馈

8、,典型的定量决策问题,装箱问题,已知： 两种货物装葙 每种货物装葙利润 体积限制 重量限制 问题:两种货物各多少箱? 可使获得利润最大？(箱数不能为分数),OR航空公司的问题,该公司要在郊区商业中心内设一个订票服务处。旅客订票时可以用电话与服务处联系。OR公司想知道，为了满足订票业务的需要，应该安装多少条电话线路为宜。显然，电话机和雇员的费用随电话线路的增设而变化。该公司希望对若干条不同线路方案的服务水平加以对比。尤其是公司要设法确定所有线路被占用的时间百分比，以及占先的平均时间长度。,经济的定货量问题,萨拇.塔龙是某闹市区的一家工装裤零售店的主人，他对于尺码短缺的裤子应该进多少货常常感到为难

9、。他决定采用科学的方法来补充库存，以避免因存货短缺而脱销。先假定他出售某种特殊尺码裤子的销售量每周为M件，为简便起见，还假定这个销售是固定的。那么如果库存量为kM件，则库存恰好在k周内售完。又假设M在整个时期内是不变的，因而是补充定货可以定期进行。要决策的问题是确定最经济的定货量。,A 2,B 7,C 20,D 12,1,2,3,4,0,2,2,9,2,22,9,21,0,2,3,10,10,22,2,22,网络计划,白色表示作业长度tij，红色表示最早TES和TEF，绿色表示最迟TLS和TLF,秘书问题,瓦特.威洛比是一家从事经济分析和预测的咨询公司.这家公司的总经理凯.塞拉女士想雇佣一位新

10、的事务秘书,正大算请职业介绍所推荐适当的人选同他会面。根据过去的经验，她自信能凭面谈即可断定求职者在受雇后的表现是极好的、好的、还是一般的。她给三种人以相应的分数：极好的为3分，好的为2分，一般为1分。一往的经验还使她相信，会见极好的候选人的概率为0.2，会见好的候选人的概率为0.5，而会见一般的候选人的概率为0.3。,定量分析的过程,定性分析 定量分析的前奏应当是一个彻底的定性分析 表达问题 列出表达问题的基本要素：决策变量、不可控量、限制条件等； 建立模型 列出表达这些要素之间关系的数学方程式 求解模型与分析 运用算法求解所构建的模型得到最佳方案或满意方案 对输入数据和模型结构作灵敏度分析

11、 执行决定或修改模型 在实际应用过程中不断完善模型,定量分析的工具模型,模型：把需要解决的决策问题，通过分析其外部影响因素和内部的条件变量，用一个逻辑的或数学的表达式，从整体上说明它们之间的结构关系。 代表一种现实情况 经过简化只保留相关的部分 用模型的特性代表现实情况中的 特性 P=N(S-C) 利润销售量（价格单位成本）,建立模型的重要性,建立模型是运筹学方法的精髓 建立模型有助于我们把决策问题所遇到的复杂性和可能的不确定性，转变为适于综合分析的逻辑结构； 模型是一种媒介，借以对现实世界作出正确的认识。 模型是现实的近似表达，要能抓住决策问题的关键，在真实性和可用性之间取得适当的平衡。,典

12、型的定量分析模型,定量分析的特点,定量分析：管理问题的理性描述和最优解 分析方法：数学的、概率的和统计的方法 定量优势：可靠数据为依据保证结果客观 定量局限：实际问题无法完全地理性描述 方法改进：数据分析与经验判断有机结合,运筹学的定义,定义1：为决策机构在对其控制下业务活动进行决策时，提供以定量化为基础的科学方法。 定义2：运筹学是一门应用科学，它广泛应用现有的科学技术知识和数学方法，解决实际中提出的专门问题，为决策者选择最优决策提供定量依据。 定义3: 运筹学是应用系统的、科学的、数学分析的方法，通过 建模、检验和求解数学模型而获得最优决策的科学。,运筹学的研究对象,机器、设备、网络、乃至

13、系统的运用问题，即如何提高运作效率； 拥挤现象：交通路口的车辆排队、服务热线、飞机着陆、船舶进港、网络； 竞争现象：人与自然的对抗、人与人的对抗；,运筹学的重要分支,运用分析理论 数学规划（又包含线性规划、非线性规划、整数规划、目标规划、动态规划等） 图与网络流 随机服务系统理论 排队论 库存论 竞争决策理论 决策论：人与自然的较量 对策论（博弈论）：人与人的较量,运筹学的主要研究分支,线性规划：模型简单，是运筹学中应用最为广泛的一个分支。 非线性规划：在各类工程的优化设计中应用广泛。 动态规划：研究多阶段决策过程最优化的运筹学分支。 图与网络流：利用图来表示研究对象及其联系，并用图论方法来研

14、究网络结构和流量的优化分析。 决策论：研究决策过程中关于方案目标选取和度量、效用值计算、选取最优方案和策略等的有关科学理论。 对策论（博弈论）：用于研究具有对抗局势的模型。 存贮论：研究最优存贮策略的理论和方法。 排队论：对排队系统的研究理论和方法。,运筹学主要分支简介,数学规划 Mathematical Programming,一般数学描述 目标函数或约束函数都是线性的,则是线性规划(Linear Programming); 若其中至少有一个是非线性的,为非线性规划(Nonlinear Programming); 若其中至少有一个变量要求为整数,则为整数规划(Integer Programm

15、ing).,数学规划,动态规划(Dynamic Programming) 解决多阶段决策过程最优化问题的一种方法 可用于解决最优路径问题、生产计划与库存、投资决策等实际问题。,图与网络流 Graph theory,决策论（decision),著名经济学家西蒙有一句名言：“管理就是决策”。 “决策”一词本身是一个广义的概念，后续课程将介绍在不确定或随机环境下的决策分析方法。 应用背景：产品开发决策问题、风险投资决策问题、开设连锁店问题等等,博弈论（Game Theory),排队论（Queuing Theory,银行、医院、机场跑道、港口码头、理发店、通信设备、交通路口等等的排队现象； 排队论又叫

16、做随机服务系统理论。它的研究目的是要回答如何改进服务机构、或组织被服务的对象，使得某种指标达到最优的问题。比如一个港口应该有多少个码头，一个工厂应该有多少维修人员等 。,库存论 (Inventory Theory),存储物品的现象是为了解决供应（生产）与需求（消费）之间的不协调的一种措施； 由此带来一些需要决策的问题：库存量、进货量（如报童问题）、补货的时间等等决策量。 现在也是供应链管理研究中的热点问题。,真实系统,系统分析 问题描述,模型建立与修改,模型求解与检验,结果分析与实施,数据准备,运筹学分析的步骤,本课程的主要内容,线性规划 整数规划(线性) 图论 决策论 博弈论,第一章 线性规划 Linear Programming,运筹学中应用最广泛的方法之一 运筹学的最基本的方法之一，网络规划，整数规划，目