《第00章绪论运筹学.ppt》由会员分享,可在线阅读,更多相关《第00章绪论运筹学.ppt(24页珍藏版)》请在优知文库上搜索。
1、运运 筹筹 学学运筹学运筹学绪论绪论2023-11-13第 2页绪绪 论论1.1 1.1 运筹学概述运筹学概述丁谓修宫丁谓修宫宋代科学家沈括在宋代科学家沈括在梦溪笔谈梦溪笔谈中曾记载过这样一个故事:宋真宗大中祥符年间,京城中曾记载过这样一个故事:宋真宗大中祥符年间,京城汴梁(今河南开封市)曾发生一场大火。一夜之间,整个皇宫的楼台殿阁被烧成一片废墟瓦汴梁(今河南开封市)曾发生一场大火。一夜之间,整个皇宫的楼台殿阁被烧成一片废墟瓦砾。灾后,真宗皇帝赵恒任命晋国公丁渭为修葺使,主持修复皇宫的工程。朝中大臣莫不认砾。灾后,真宗皇帝赵恒任命晋国公丁渭为修葺使,主持修复皇宫的工程。朝中大臣莫不认为这是一项
2、耗资巨大,旷日持久的工程。可是丁渭却欣然承诺。他接受使命后,为这是一项耗资巨大,旷日持久的工程。可是丁渭却欣然承诺。他接受使命后,“患取土远患取土远”而首先下令挖宫前的大街取土,不几天大街就成了一条宽大的水渠。于是,他下令将汴水而首先下令挖宫前的大街取土,不几天大街就成了一条宽大的水渠。于是,他下令将汴水引入这条水渠,用引入这条水渠,用“竹水筏和船竹水筏和船”运输建筑材料运输建筑材料“入至宫门入至宫门”。皇宫修复后,又将瓦砾灰壤。皇宫修复后,又将瓦砾灰壤填入沟中,填入沟中,“复为街衢复为街衢”,结果,不仅,结果,不仅“省费以万亿计省费以万亿计”,而且还大大加快了工程进度。,而且还大大加快了工程
3、进度。运筹学运筹学绪论绪论2023-11-13第 3页运筹学运筹学绪论绪论2023-11-13第 4页l 战国时期齐威王常邀武臣田忌赛马赌金,双方约定每方出上马、中马、下马战国时期齐威王常邀武臣田忌赛马赌金,双方约定每方出上马、中马、下马各一匹各赛一局,每局赌注是黄金一千两。各一匹各赛一局,每局赌注是黄金一千两。l 由于田忌的马比齐王同等级的马都要略逊一筹,而在头一轮的比赛中,双方由于田忌的马比齐王同等级的马都要略逊一筹,而在头一轮的比赛中,双方都是用同等级的马进行对抗,所以齐王很快赢了全部三场,得到了三千两黄都是用同等级的马进行对抗,所以齐王很快赢了全部三场,得到了三千两黄金。金。田忌赛马田
4、忌赛马运筹学运筹学绪论绪论2023-11-13第 5页田忌的军师孙膑得知后,进行了分析:齐王和田忌出马的对策各有六种,假田忌的军师孙膑得知后,进行了分析:齐王和田忌出马的对策各有六种,假设胜者表示设胜者表示 1,负者表示,负者表示-1 分,胜负按照分,胜负按照(田忌田忌,齐王齐王)方式表示,则有方式表示,则有 齐王齐王田忌田忌上上中中下下上上(-1,1)(1,-1)(1,-1)中中(-1,1)(-1,1)(1,-1)下下(-1,1)(-1,1)(-1,1)这样搭配起来就有这样搭配起来就有 36种对赛的格局。其中齐王赢三千金的格局有种对赛的格局。其中齐王赢三千金的格局有 6 种,赢种,赢一千金的
5、格局有一千金的格局有 24 种,只有种,只有 6 种才反输一千金。因此,从总的来看,田忌种才反输一千金。因此,从总的来看,田忌输的概率为六分之五。赢的概率只有六分之一。输的概率为六分之五。赢的概率只有六分之一。运筹学运筹学绪论绪论2023-11-13第 6页田忌在好友、著名的军事谋略家孙膑的指导下,以以下安排:田忌在好友、著名的军事谋略家孙膑的指导下,以以下安排:齐王齐王上上中中下下田忌田忌下下上上中中最终净胜一局,赢得最终净胜一局,赢得10001000金。金。运筹学运筹学绪论绪论2023-11-13第 7页特拉法加尔(特拉法加尔(TrafalgarTrafalgar)海战和纳尔森()海战和纳
6、尔森(NelsonNelson)秘诀)秘诀 1919世纪中叶,法国拿破伦统帅大军要与英国争夺海上霸主地位,而实施这一战略的最世纪中叶,法国拿破伦统帅大军要与英国争夺海上霸主地位,而实施这一战略的最主要的关键是消灭英国的舰队。英国海军统帅、海军中将纳尔森亲自制定了周密的战术主要的关键是消灭英国的舰队。英国海军统帅、海军中将纳尔森亲自制定了周密的战术方案。方案。18051805年年1010月月2121日,这场海上大战爆发了。英国是纳尔森亲自统帅的地中海舰队,由日,这场海上大战爆发了。英国是纳尔森亲自统帅的地中海舰队,由2727艘战舰组成;另外一方是由费伦纽夫(艘战舰组成;另外一方是由费伦纽夫(Vi
7、llenuveVillenuve)率领的法国)率领的法国西班牙联合舰队,西班牙联合舰队,共有共有3333艘战舰。艘战舰。海战结果:法国海战结果:法国西班牙联合舰队以惨败告终:联合舰队司令费伦纽夫连同西班牙联合舰队以惨败告终:联合舰队司令费伦纽夫连同1212艘艘战舰被俘,战舰被俘,8 8艘沉没,仅艘沉没,仅1313艘逃走,人员伤亡艘逃走,人员伤亡70007000人。而英国战舰没有沉没,人员伤亡人。而英国战舰没有沉没,人员伤亡16631663人,但是,作为统帅的纳尔森阵亡。人,但是,作为统帅的纳尔森阵亡。运筹学运筹学绪论绪论2023-11-13第 8页秘密备忘录中的纳尔森(秘密备忘录中的纳尔森(N
8、elsonNelson)秘诀:)秘诀:预期参加战斗的英国舰队:预期参加战斗的英国舰队:4040艘。法国艘。法国西班牙联合舰队:西班牙联合舰队:4646艘。预计联合舰队战斗队形艘。预计联合舰队战斗队形一字横列。一字横列。英国舰队的战斗队形与任务:分成两个主纵列及一个小纵列。英国舰队的战斗队形与任务:分成两个主纵列及一个小纵列。主纵列主纵列1 1:1616艘,由纳尔森亲自指挥,拦腰将法国艘,由纳尔森亲自指挥,拦腰将法国西班牙联合舰队切为两段,并攻击联西班牙联合舰队切为两段,并攻击联合舰队的中间部分。合舰队的中间部分。主纵列主纵列2 2:1616艘,由英国海军中将科林伍德指挥,从联合舰队后半部再切断
9、,分割并攻击后艘,由英国海军中将科林伍德指挥,从联合舰队后半部再切断,分割并攻击后部部1212艘。艘。小纵列:小纵列:8 8艘,在中心部分附近攻击其先头部分的艘,在中心部分附近攻击其先头部分的3-43-4艘。艘。运筹学运筹学绪论绪论2023-11-13第 9页用兰彻斯特用兰彻斯特N N2 2定律可以对定律可以对“纳尔森(纳尔森(NelsonNelson)秘诀)秘诀”进行分析:进行分析:设双方单个战斗单位的战斗力相同,则有:设双方单个战斗单位的战斗力相同,则有:英国舰队:英国舰队:40402 2=1600=1600 联合舰队:联合舰队:46462 2=2116=2116 此时联合舰队占优势,设想
10、联合舰队全歼英国舰队后,联合舰队还有此时联合舰队占优势,设想联合舰队全歼英国舰队后,联合舰队还有5165161/21/2=23=23艘。艘。将联合舰队拦腰切断,将联合舰队拦腰切断,23+23=4623+23=46,是将联合舰队实力减弱的最小分割法。此时,联合,是将联合舰队实力减弱的最小分割法。此时,联合舰队的实力为:舰队的实力为:23232 2+23+232 2=1058=1058而英国舰队的实力为:(而英国舰队的实力为:(16+1616+16)2 2+8+82 2=1088=1088,已略占有优势。,已略占有优势。在英国舰队两个主纵列共在英国舰队两个主纵列共3232艘,攻击联合舰队的后一半艘
11、,攻击联合舰队的后一半2323艘,此时,艘,此时,英国舰队实力:(英国舰队实力:(16+1616+16)2 2=32=322 2=1064=1064联合舰队的实力为:联合舰队的实力为:23232 2 =529 =529英国舰队已占有优势。在全歼联合舰队后部后,英国舰队两个主纵列还可以保留:英国舰队已占有优势。在全歼联合舰队后部后,英国舰队两个主纵列还可以保留:(1064-5291064-529)1/2 1/2 =516=5161/21/2=23=23艘,再与小纵列中舰队联合对联合舰队前部作战还占有优艘,再与小纵列中舰队联合对联合舰队前部作战还占有优势。即在最坏情况下,势。即在最坏情况下,“纳尔
12、森(纳尔森(NelsonNelson)秘诀)秘诀”也可以使英国舰队获得胜利。也可以使英国舰队获得胜利。运筹学运筹学绪论绪论2023-11-13第 10页大西洋反潜战(大西洋反潜战(19421942年)年)19421942年,美国大西洋舰队反潜战官员年,美国大西洋舰队反潜战官员W.D.BAKERW.D.BAKER舰长请求成立反潜战运筹组,麻省舰长请求成立反潜战运筹组,麻省理工学院的物理学家理工学院的物理学家P.W.MORSEP.W.MORSE被请来担任计划与监督。被请来担任计划与监督。MORSE MORSE 出色的工作之一,是协助英国打破了德国对英吉利海峡的封锁。出色的工作之一,是协助英国打破了
13、德国对英吉利海峡的封锁。1941-19421941-1942年,年,德国潜艇严密封锁了英吉利海峡,企图切断英国的德国潜艇严密封锁了英吉利海峡,企图切断英国的“生命线生命线”。海军几次反封锁,均不成。海军几次反封锁,均不成功。功。英国要求,美国派英国要求,美国派MORSEMORSE率领一个小组去协助。率领一个小组去协助。MORSEMORSE经过多方实地考察,最后提出了经过多方实地考察,最后提出了两条重要建议:两条重要建议:1.1.将反潜攻击由反潜潜艇投掷水雷,改为飞机投掷深水炸弹。起爆深度由将反潜攻击由反潜潜艇投掷水雷,改为飞机投掷深水炸弹。起爆深度由100100米左米左右改为右改为2525米左
14、右。即当潜艇刚下潜时攻击效果最佳。米左右。即当潜艇刚下潜时攻击效果最佳。(提高效率提高效率4-74-7倍倍)2.2.运送物资的船队及护航舰队编队,由小规模多批次,改为加大规模、减少批次,运送物资的船队及护航舰队编队,由小规模多批次,改为加大规模、减少批次,这样,损失率将减少。(这样,损失率将减少。(25%25%下降到下降到10%10%)丘吉尔采纳了丘吉尔采纳了MORSEMORSE的建议,最终成功地打破封锁,并重创了德国潜艇。的建议,最终成功地打破封锁,并重创了德国潜艇。MORSEMORSE同时获同时获得英国和美国的最高勋章。得英国和美国的最高勋章。运筹学运筹学绪论绪论2023-11-13第 1
15、1页运筹学发展三阶段运筹学发展三阶段:创建时期(创建时期(4545年至年至5050年代初)年代初)19481948年年 英国成立英国成立“运筹学运筹学”俱乐部俱乐部19481948年年 麻省理工学院麻省理工学院 介绍运筹学介绍运筹学19501950年年 伯明翰大学开设运筹学课程伯明翰大学开设运筹学课程19521952年年 卡斯大学卡斯大学 设立运筹学硕士和博士学位设立运筹学硕士和博士学位19471947年年 丹捷格丹捷格 提出单纯形法提出单纯形法5050年代初年代初 计算机求解线性规划获得成功计算机求解线性规划获得成功成长时期(成长时期(5050年代初至年代初至5050年代末)年代末)多个国家
16、成立运筹学会,多种运筹学刊物问世多个国家成立运筹学会,多种运筹学刊物问世19571957年年 在牛津大学召开第一次国际运筹学会议在牛津大学召开第一次国际运筹学会议19591959年年 成立国际运筹学联合会成立国际运筹学联合会迅速发展时期(迅速发展时期(6060年代以来)年代以来)运筹学进一步分为各个分支,更多运筹学出版物运筹学进一步分为各个分支,更多运筹学出版物运筹学课程纳入教学计划运筹学课程纳入教学计划运筹学运筹学绪论绪论2023-11-13第 12页我国运筹学发展历程:我国运筹学发展历程:19561956年年 运筹学小组运筹学小组19581958年年 运筹学研究室运筹学研究室19601960年年 应用运筹学经验交流会议应用运筹学经验交流会议19621962年年 全国运筹学专业学术会议全国运筹学专业学术会议19781978年年 全国运筹学专业学术会议全国运筹学专业学术会议19801980年年 成立中国运筹学学会成立中国运筹学学会运筹学运筹学绪论绪论2023-11-13第 13页运筹学定义运筹学定义 运筹学是以数学为主要技术手段,综合应用经济学、军事学、心运筹学是以数学为主要技术手段,