第00章绪论运筹学

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,2002ZLZK-PM-KICKOFF,项目终期报告,运筹学,第,*,页,绪论,运 筹 学,2024/11/19,第,2,页,绪 论,1.1,运筹学概述,丁谓修宫,宋代科学家沈括在,梦溪笔谈,中曾记载过这样一个故事：宋真宗大中祥符年间，京城汴梁（今河南开封市）曾发生一场大火。一夜之间，整个皇宫的楼台殿阁被烧成一片废墟瓦砾。灾后，真宗皇帝赵恒任命晋国公丁渭为修葺使，主持修复皇宫的工程。朝中大臣莫不认为这是一项耗资巨大，旷日持久的工程。可是丁渭却欣然承诺。他接受使命后，,“,患取土远,”,而首先下令挖宫前的大街取土，不几天大街就成了一条宽大的水渠。于是，他下令将汴水引入这条水渠，用,“,竹水筏和船,”,运输建筑材料,“,入至宫门,”,。皇宫修复后，又将瓦砾灰壤填入沟中，,“,复为街衢,”,，结果，不仅,“,省费以万亿计,”,，而且还大大加快了工程进度。,2024/11/19,第,3,页,2024/11/19,第,4,页,战国时期齐威王常邀武臣田忌赛马赌金，双方约定每方出上马、中马、下马各一匹各赛一局，每局赌注是黄金一千两。,由于田忌的马比齐王同等级的马都要略逊一筹，而在头一轮的比赛中，双方都是用同等级的马进行对抗，所以齐王很快赢了全部三场，得到了三千两黄金。,田忌赛马,2024/11/19,第,5,页,田忌的军师孙膑得知后，进行了分析：齐王和田忌出马的对策各有六种，假设胜者表示,1,，负者表示,-1,分，胜负按照,(,田忌,齐王,),方式表示，则有,齐王,田忌,上,中,下,上,(-1,1),(1,-1),(1,-1),中,(-1,1),(-1,1),(1,-1),下,(-1,1),(-1,1),(-1,1),这样搭配起来就有,36,种对赛的格局。其中齐王赢三千金的格局有,6,种，赢一千金的格局有,24,种，只有,6,种才反输一千金。因此，从总的来看，田忌输的概率为六分之五。赢的概率只有六分之一。,2024/11/19,第,6,页,田忌在好友、著名的军事谋略家孙膑的指导下，以以下安排：,齐王上中下,田忌下上中,最终净胜一局，赢得,1000,金。,2024/11/19,第,7,页,特拉法加尔（,Trafalgar,）海战和纳尔森（,Nelson,）秘诀,19,世纪中叶，法国拿破伦统帅大军要与英国争夺海上霸主地位，而实施这一战略的最主要的关键是消灭英国的舰队。英国海军统帅、海军中将纳尔森亲自制定了周密的战术方案。,1805,年,10,月,21,日，这场海上大战爆发了。英国是纳尔森亲自统帅的地中海舰队，由,27,艘战舰组成；另外一方是由费伦纽夫（,Villenuve,）率领的法国,西班牙联合舰队，共有,33,艘战舰。,海战结果：法国,西班牙联合舰队以惨败告终：联合舰队司令费伦纽夫连同,12,艘战舰被俘，,8,艘沉没，仅,13,艘逃走，人员伤亡,7000,人。而英国战舰没有沉没，人员伤亡,1663,人，但是，作为统帅的纳尔森阵亡。,2024/11/19,第,8,页,秘密备忘录中的纳尔森（,Nelson,）秘诀：,预期参加战斗的英国舰队：,40,艘。法国,西班牙联合舰队：,46,艘。预计联合舰队战斗队形一字横列。,英国舰队的战斗队形与任务：分成两个主纵列及一个小纵列。,主纵列,1,：,16,艘，由纳尔森亲自指挥，拦腰将法国,西班牙联合舰队切为两段，并攻击联合舰队的中间部分。,主纵列,2,：,16,艘，由英国海军中将科林伍德指挥，从联合舰队后半部再切断，分割并攻击后部,12,艘。,小纵列：,8,艘，在中心部分附近攻击其先头部分的,3-4,艘。,2024/11/19,第,9,页,用兰彻斯特,N,2,定律可以对,“,纳尔森（,Nelson,）秘诀,”,进行分析：,设双方单个战斗单位的战斗力相同，则有：,英国舰队：,40,2,=1600,联合舰队：,46,2,=2116,此时联合舰队占优势，设想联合舰队全歼英国舰队后，联合舰队还有,516,1/2,=23,艘。,将联合舰队拦腰切断，,23+23=46,，是将联合舰队实力减弱的最小分割法。此时，联合舰队的实力为：,23,2,+23,2,=1058,而英国舰队的实力为：（,16+16,）,2,+8,2,=1088,，已略占有优势。,在英国舰队两个主纵列共,32,艘，攻击联合舰队的后一半,23,艘，此时，,英国舰队实力：（,16+16,）,2,=32,2,=1064,联合舰队的实力为：,23,2,=529,英国舰队已占有优势。在全歼联合舰队后部后，英国舰队两个主纵列还可以保留：,（,1064-529,）,1/2,=516,1/2,=23,艘，再与小纵列中舰队联合对联合舰队前部作战还占有优势。即在最坏情况下，,“,纳尔森（,Nelson,）秘诀,”,也可以使英国舰队获得胜利。,2024/11/19,第,10,页,大西洋反潜战（,1942,年）,1942,年，美国大西洋舰队反潜战官员,W.D.BAKER,舰长请求成立反潜战运筹组，麻省理工学院的物理学家,P.W.MORSE,被请来担任计划与监督。,MORSE,出色的工作之一，是协助英国打破了德国对英吉利海峡的封锁。,1941-1942,年，德国潜艇严密封锁了英吉利海峡，企图切断英国的,“,生命线,”,。海军几次反封锁，均不成功。,英国要求，美国派,MORSE,率领一个小组去协助。,MORSE,经过多方实地考察，最后提出了两条重要建议：,1.,将反潜攻击由反潜潜艇投掷水雷，改为飞机投掷深水炸弹。起爆深度由,100,米左右改为,25,米左右。即当潜艇刚下潜时攻击效果最佳。,(,提高效率,4-7,倍,),2.,运送物资的船队及护航舰队编队，由小规模多批次，改为加大规模、减少批次，这样，损失率将减少。（,25%,下降到,10%,）,丘吉尔采纳了,MORSE,的建议，最终成功地打破封锁，并重创了德国潜艇。,MORSE,同时获得英国和美国的最高勋章。,2024/11/19,第,11,页,运筹学发展三阶段,：,创建时期（,45,年至,50,年代初）,1948,年 英国成立,“,运筹学,”,俱乐部,1948,年 麻省理工学院 介绍运筹学,1950,年 伯明翰大学开设运筹学课程,1952,年 卡斯大学 设立运筹学硕士和博士学位,1947,年 丹捷格 提出单纯形法,50,年代初 计算机求解线性规划获得成功,成长时期（,50,年代初至,50,年代末）,多个国家成立运筹学会，多种运筹学刊物问世,1957,年 在牛津大学召开第一次国际运筹学会议,1959,年 成立国际运筹学联合会,迅速发展时期（,60,年代以来）,运筹学进一步分为各个分支，更多运筹学出版物,运筹学课程纳入教学计划,2024/11/19,第,12,页,我国运筹学发展历程：,1956,年 运筹学小组,1958,年 运筹学研究室,1960,年 应用运筹学经验交流会议,1962,年 全国运筹学专业学术会议,1978,年 全国运筹学专业学术会议,1980,年 成立中国运筹学学会,2024/11/19,第,13,页,运筹学定义,运筹学是以数学为主要技术手段，综合应用经济学、军事学、心理学、社会学、物理学、化学及工农业生产的一些理论和方法，对实际问题找出最优的或满意的决策方案的一门边缘性的、综合性的应用科学。,运筹学（,Operational Research,）,怎样把事情做到最好,“,夫,运筹,帷幄之中，决胜于千里之外,”,史记,张良传,2024/11/19,第,14,页,运筹学在管理中的应用,:,生产计划：,生产作业的计划、日程表的编排、合理下料、配料问题、物料管理等，追求利润最大化和成本最小化。,库存管理：,多种物资库存量的管理，库存方式、库存量等,运输问题：,确定最小成本的运输线路、物资的调拨、运输工具的调度以及建厂地址的选择等。,人事管理：,对人员的需求和使用的预测，确定人员编制、人员合理分配，建立人才评价体系等。,市场营销：,广告预算、媒介选择、定价、产品开发与销售计划制定等,财务会计：,预测、贷款、成本分析、定价、证券管理、现金管理等。,2024/11/19,第,15,页,2024/11/19,第,16,页,1.2,运筹学的模型,三种基本形式：形象模型、模拟模型、符号或数学模型,构模的方法和思路,直接分析法、类比法、数据分析法、实验分析法、构想法,模型的一般数学表现形式,评价准则,U=f(x,i,y,i,k,),约束条件,g(x,i,y,i,k,)0,其中,x,i,为可控变量，,y,i,为已知参数，,k,为随机因素,2024/11/19,第,17,页,1.2,运筹学的模型,某工厂生产经理正面临如何安排生产,A,、,B,两种产品的问题。已知产品,A,、,B,都是热销产品。生产单位产品的利润与所需的劳动力、设备台时及原材料的消耗，如下表所示。如果你是该工厂的生产经理，你将如何安排以使得该厂获利最大？,产品,A,产品,B,资源限额,劳动力,1,小时单位产量,1,工时单位产量,45,工时,设备,2,工时单位产量,2,工时单位产量,80,工时,原材料,公斤单位产量,公斤单位产量,90,公斤,单位产品利润（元单位产量）,4,5,.,如何用数学的方法描述此类生产规划问题？,.,总利润如何描述？,.,影响决策的因素有哪些？,2024/11/19,第,18,页,1.2,运筹学的模型,目标是使产品销售的总利润最大：,z=4x,1,+5x,2,影响决策的因素有哪些：,x,1,+x,2,45,2x,1,+x,2,80,x,1,+3x,2,90,x,1,0,x,2,0,2024/11/19,第,19,页,1.2,运筹学的模型,Max z=4x,1,+5x,2,x,1,+x,2,45,2x,1,+x,2,80,x,1,+3x,2,90,x,1,0,x,2,0,St.,2024/11/19,第,20,页,1.3,运筹学的工作步骤,提出问题,建立模型,设计算法,整理数据,求解模型,评价结果,提出问题,建立模型,设计算法,整理数据,求解模型,评价结果,简化？,满意？,Yes,No,No,2024/11/19,第,21,页,例：一个最大化问题,某家具厂生产桌子和椅子两种家具，有关资料如下表：,桌子 椅子 可供量,木工,4,小时,/,张,3,小时,/,把,120,小时,/,月,油漆工,2,小时,/,张,1,小时,/,把,50,小时,/,月,售价,50,元,/,张,30,元,/,把,问该厂如何安排生产才能使每月销售收入最大,?,解：,1.,确定决策变量：,设,x,1,为桌子生产量,x,2,为椅子生产量,2.,确定目标函数：,max.z=50 x,1,+30 x,2,3.,确定约束方程：,木工约束：,4x,1,+3x,2,120,油漆工约束：,2x,1,+x,2,50,2024/11/19,第,22,页,例：人员安排问题,医院护士,24,小时值班，每次值班,8,小时。不同时段需要的护士人数不等。据统计：,序号,时段,最少人数,1,06,10,60,2,10,14,70,3,14,18,60,4,18,22,50,5,22,02,20,6,02,06,30,目标函数：,min Z=x,1,+x,2,+x,3,+x,4,+x,5,+x,6,约束条件：,x,1,+x,2,70,x,2,+x,3,60,x,3,+x,4,50,x,4,+x,5,20,x,5,+x,6,30,非负性约束：,x,j,0,j=1,2,6,2024/11/19,第,23,页,1.,运筹学分支,线性规划,整数线性规划,图与网络分析,存贮模型,排队论,对策论,排序与统筹方法,决策论,动态规划,预测,2024/11/19,第,24,页,学习运筹学,:,注重于学以致用的原则,结合实际问题建立运筹学模型,解决问题的方案或模型的解,