南京-应用运筹学-线性规划-1

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

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

2、守李冰父子主持修建。其目标是：利 用岷江上游的水资源灌溉川西平原。追用岷江上游的水资源灌溉川西平原。追 求的效益还有防洪与航运。其总体构思求的效益还有防洪与航运。其总体构思 是系统思想的杰出运用是系统思想的杰出运用。vv丁谓的皇宫修复工程丁谓的皇宫修复工程 北宋年间，丁谓负责修复火毁的开封北宋年间，丁谓负责修复火毁的开封 皇宫。他的施工方案是：先将工程皇宫前皇宫。他的施工方案是：先将工程皇宫前 的一条大街挖成一条大沟，将大沟与汴水的一条大街挖成一条大沟，将大沟与汴水 相通。使用挖出的土就地制砖，令与汴水相通。使用挖出的土就地制砖，令与汴水 相连形成的河道承担繁重的运输任务；修相连形成的河道承担

3、繁重的运输任务；修 复工程完成后，实施大沟排水，并将原废复工程完成后，实施大沟排水，并将原废 墟物回填，修复成原来的大街。丁谓将取墟物回填，修复成原来的大街。丁谓将取 材、生产、运输及废墟物的处理用材、生产、运输及废墟物的处理用“一沟一沟 三用三用”巧妙地解决了。巧妙地解决了。vv田忌赛马田忌赛马齐王要与大臣田忌赛马，双方各出上、齐王要与大臣田忌赛马，双方各出上、 中、下马各一匹，对局三次，每次胜负中、下马各一匹，对局三次，每次胜负10001000 金。田忌在好友、著名的军事谋略家孙膑的金。田忌在好友、著名的军事谋略家孙膑的 指导下，以以下安排：指导下，以以下安排： 齐王齐王 上上 中中 下下

4、 田忌田忌 下下 上上 中中最终净胜一局，赢得最终净胜一局，赢得10001000金。金。运筹学的三大来源F军事 运筹帷幄、决策千里 第二次世界大战F经济 莱昂惕夫的投入产出模 型F管理 著名经济学家西蒙有一 句名言：“管理就是决策”vv鲍德西（鲍德西（BawdseyBawdsey）雷达站的研究（雷达站的研究（ 19351935年）年）19351935年，英国科学家年，英国科学家R.Watson-WartR.Watson-Wart 发明了雷达。丘吉尔命令在英国东海岸发明了雷达。丘吉尔命令在英国东海岸 的的BawdseyBawdsey建立了一个秘密雷达站。当建立了一个秘密雷达站。当 时，德国已拥有

5、一支强大的空军，起飞时，德国已拥有一支强大的空军，起飞 1717分钟即到达英国本土。在如此短的时分钟即到达英国本土。在如此短的时 间内，如何预警和拦截成为一大难题。间内，如何预警和拦截成为一大难题。19391939年由曼彻斯特大学物理学家年由曼彻斯特大学物理学家 、英国战斗机司令部顾问、战后获得诺、英国战斗机司令部顾问、战后获得诺 贝尔奖金的贝尔奖金的P.M.S.BlackettP.M.S.Blackett为首，组织为首，组织 了一个小组，代号了一个小组，代号“ “BlackettBlackett马戏团马戏团” ”。 这个小组包括三名心理学家、两名数学这个小组包括三名心理学家、两名数学 家、两

6、名应用数学家、一名天文物理学家、两名应用数学家、一名天文物理学 家、一名普通物理学家、一名海军军官家、一名普通物理学家、一名海军军官 、一名陆军军官、一名测量员。、一名陆军军官、一名测量员。研究的问题是：设计将雷达信息研究的问题是：设计将雷达信息 传送到指挥系统和武器系统的最佳方式传送到指挥系统和武器系统的最佳方式 ；雷达与武器的最佳配置；对探测、信；雷达与武器的最佳配置；对探测、信 息传递、作战指挥、战斗机与武器的协息传递、作战指挥、战斗机与武器的协 调，作了系统的研究，并获得成功。调，作了系统的研究，并获得成功。 “ “BlackettBlackett马戏团马戏团” ”在秘密报告中使用了在

7、秘密报告中使用了 “ “Operational Operational Research”Research”，即即“ “运筹学运筹学 ” ”。vv大西洋反潜战（大西洋反潜战（19421942年）年）19421942年，美国大西洋舰队反潜战官年，美国大西洋舰队反潜战官 员员W.D.BakerW.D.Baker舰长请求成立反潜战运舰长请求成立反潜战运 筹组，麻省理工学院的物理学家筹组，麻省理工学院的物理学家 P.W.MorseP.W.Morse被请来担任计划与监督。被请来担任计划与监督。 Morse Morse 出色的工作之一，是协助英国出色的工作之一，是协助英国 打破了德国对英吉利海峡的封锁。打

8、破了德国对英吉利海峡的封锁。1941-19421941-1942年，德国潜艇严密封锁年，德国潜艇严密封锁 了英吉利海峡，企图切断英国的了英吉利海峡，企图切断英国的“ “ 生命线生命线” ”。海军几次反封锁，均不。海军几次反封锁，均不 成功。应英国要求，美国派成功。应英国要求，美国派MorseMorse 率领一个小组去协助。率领一个小组去协助。MorseMorse经过经过 多方实地考察，最后提出了两条重多方实地考察，最后提出了两条重 要建议：要建议： 将反潜攻击由反潜潜艇投掷水雷，改将反潜攻击由反潜潜艇投掷水雷，改 为飞机投掷深水炸弹。起爆深度由为飞机投掷深水炸弹。起爆深度由100100 米左右

9、改为米左右改为2525米左右。即当潜艇刚下潜米左右。即当潜艇刚下潜 时攻击效果最佳。时攻击效果最佳。( (提高效率提高效率4-74-7倍倍) ) 运送物资的船队及护航舰队编队，由运送物资的船队及护航舰队编队，由 小规模多批次，改为加大规模、减少批小规模多批次，改为加大规模、减少批 次，这样，损失率将减少。（次，这样，损失率将减少。（25%25%下降下降 到到10%10%）管理与运筹学泰勒的科学管理方法对工人提出科学的操作方法（时间动作研究） 对工人进行科学的选择、培训和提高（能力与工作相适应） 制定科学的工艺流程，并以文件的形式加以固定和推广（工作定额与标准化） 使管理和劳动相分离（计划与执行

10、分离） 在工资制度上实行差别计件制（差别计件付酬制）各种管理科学学派各种管理科学学派科学管理原理 社会技术系统 学派 行为科学学派 人际关系行为 学派 管理过程学派 社会合作系 统学派 决策理论学派 沟通信息学派 管理科学学派 经验案例学派 数理学派 系统管理学派 经理角色学派 群体行为学派战略管理 创新管理 知识管 理 决策制定决策制定主体（管理者）主体（管理者）管理者的多重角色 - 认可并奖励业绩 - 不断完善个人管理技能 - 给予指导建议 - 不断提出反馈 - 员工发展- 构建有效团队 - 倾听 - 调解冲突- 设定富于挑战但可以达到的业绩标准 - 提供及时精确的信息 - 控制质量- -

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

12、址项目规划排队问题对产品的需求有多大，类别如何，利润影响？ 需要多少资金，从何处得到，成本有多大？ 需要多少人员，应有何技能，留用多长时间？ 什么工作最重要，工作顺序如何安排？ 需要什么资源，是否短缺，如何优先获得？ 设备运转如何，可靠性如何，何时更新？ 合理库存量为多少，订货的最佳批量和周期？ 运作的最佳场所在何处，需要什么设施？ 项目合理的作业时间为多少，资源如何利用？ 队列多长，提供多少个服务台，服务水平？装箱问题已知： 两种货物装葙每种货物装葙利润体积限制重量限制问题:两种货物各多少箱? 可使获得 利润最大？(箱数不能为分数)OR航空公司的问题F该公司要在郊区商业中心内设一个订 票服务

13、处。旅客订票时可以用电话与服 务处联系。OR公司想知道，为了满足订 票业务的需要，应该安装多少条电话线 路为宜。显然，电话机和雇员的费用随 电话线路的增设而变化。该公司希望对 若干条不同线路方案的服务水平加以对 比。尤其是公司要设法确定所有线路被 占用的时间百分比，以及占先的平均时 间长度。经济的定货量问题F萨拇.塔龙是某闹市区的一家工装裤零 售店的主人，他对于尺码短缺的裤子应 该进多少货常常感到为难。他决定采用 科学的方法来补充库存，以避免因存货 短缺而脱销。先假定他出售某种特殊尺 码裤子的销售量每周为M件，为简便起见 ，还假定这个销售是固定的。那么如果 库存量为kM件，则库存恰好在k周内售

14、完 。又假设M在整个时期内是不变的，因而 是补充定货可以定期进行。要决策的问 题是确定最经济的定货量。A 2B 7C 20 D 121234结结点编编号作业业作业业 长长度最早开 工时时刻最迟迟开 工时时刻最早完 工时时刻最迟迟完 工时时刻时时差关键键 作业业 i jtijTESTLSTEFTLFS12A200220A23B723910124C202222220C34D12910212210229222921023 101022222网络计划白色表示作业长度tij，红色表 示最早TES和TEF，绿色表示 最迟TLS和TLF秘书问题F瓦特.威洛比是一家从事经济分析和预 测的咨询公司.这家公司的总

15、经理凯.塞 拉女士想雇佣一位新的事务秘书,正大算 请职业介绍所推荐适当的人选同他会面 。根据过去的经验，她自信能凭面谈即 可断定求职者在受雇后的表现是极好的 、好的、还是一般的。她给三种人以相 应的分数：极好的为3分，好的为2分， 一般为1分。一往的经验还使她相信，会 见极好的候选人的概率为0.2，会见好的 候选人的概率为0.5，而会见一般的候选 人的概率为0.3。T0.2F0.3G0.5继续继续停止T0.2F0.3G0.5继续T0.2F0.3停止G0.5停止继续停止停止1233322停止停止T极好F一般G好的定量分析的过程F定性分析 定量分析的前奏应当是一个彻 底的定性分析F表达问题 列出表达问题的基本要素：决 策变量、不可控量、限制条件等；F建立模型 列出表达这些要素之间关系的 数学方程式F求解模型与分析 运用算法求解所构建的模型得 到最佳方案或满意方案 对输入数据和模型结构作灵敏 度分析F执行决定或修改模型 在实际应用过程中不断完善模 型定量分析的工具模型模型：把需要解决的决策问题，通过 分析其外部影响因素和内部的条件变量 ，用一个逻辑的或数学的表达式，从整 体上说明它们之间的结构关系。 代表一种现实情况 经过简化只保留相关的部分 用模型的特性代表现实情况中的 特性P=N