《孙子兵法与运筹学中的数学思想(田忌赛马).ppt》由会员分享，可在线阅读，更多相关《孙子兵法与运筹学中的数学思想(田忌赛马).ppt（110页珍藏版）》请在三一办公上搜索。
1、1,数学文化第十讲 孙子兵法与运筹学中的数学思想,数 学 聊 吧,滚滚长江东逝水 浪花淘尽英雄 是非成败转头空 青山依旧在 几度夕阳红 白发渔樵江楮上 惯看秋月春风 数学聊吧喜相逢 古今数学多少事 都付笑谈中,2,期末考核,3,六、“数学文化”课的考核,1纪律要求（二四法则）不迟到、不说话、不影响别人；抽查点名，有事请假，旷课从严。2考核及成绩评定方式(五五分成）（一）考核方式：1.平时举办学生读书报告、课堂演讲会。2.期末学生实话实说写学习本课程的心得体会小论文。（A卷：品数学之文化 B卷：烹数学之美食）（二）成绩评定：平时成绩占50%，期末成绩占50%。及格标准：实话实说 不及格标准：1.
2、网上下载自己不懂的东西 2.答卷雷同 3.待定(受同学们的启发),4,本期数学文化课平时安排及期末考核,平时安排的实践内容 1.读书报告、演讲会 2.关于数学素养的调查报告 3.征集数学聊吧广告语期末考核 1.填写“高职数学文化”课评课意见 2.实话实说写学习本课程的心得体会小论文,5,“高职数学文化”课程结业论文（含评课意见）封面及要求,1.封面：高职数学文化课程结业论文（含评课意见）201_学年_学期 题 目 _ 选 修 班 _ 系 别 _ 专 业 _ 学 号 _ 姓 名 _2.要求：1）选题：要与数学文化相关，要有新意（视角独特）、范围适当（切入口小），一事一议。2）课程结业论文包括两部
3、分：第一部分课程论文：2000-3000字左右 第二部分评课意见：500字以内。3)论文应按照学术论文规范要求：由题目、摘要、关键词、正文（引用应标出处）、参 考文献组成。4）一律用A4纸打印。5）实话实说。严禁抄袭，一旦发现，作不及格处理。,6,数学聊吧-第十讲 孙子兵法与运筹学中的数学思想,聊 田忌与齐王赛马一、古代中国的运筹典故二、近代世界的运筹学的起源三、运筹学的性质和特点四、运筹学在管理领域的应用范围五、运筹学的分支六、现代运筹学实例七、数学文化美食（之）：指鹿为马幼儿版 纠错码,7,一、古代中国的运筹典故,1.田忌与齐王赛马 孙膑(约公元前380-432),孙武的后世子孙,战国中期
4、著名军事家,担任齐国将领田忌的军师.孙膑的“斗马术”是我国古代运筹思想中争取总体最优的脍炙人口的著名范例.齐将田忌与齐王赛马,孙膑献策:以下马对齐王上马,以上马对齐王中马,以中马对齐王下马.结果田忌以一负两胜而获胜.,8,孙膑兵法,9,这个故事后来被传为千古佳话,成为军事上一条重要的用兵规律,即要善于用局部的牺牲去换取全局的胜利,从而达到以弱胜强的目的.他的基本思想是不强求一局的得失,而争取全盘的胜利.这是一个典型的博弈问题.,10,2.围魏救赵,公元前354年,魏国将军庞涓发兵8万,以突袭的办法将赵国的都城邯郸包围.赵国抵挡不住,求救于齐.齐威王拜田忌为大将,孙膑为军师,发兵8万,前往救赵.
5、田忌打算直奔邯郸,速解赵国之围.孙膑提出应趁魏国国内兵力空虚之机,发兵直取魏都大梁(今河南开封),迫使魏军弃赵回救.这一战略思想,既避免齐军长途奔袭的疲劳,又致使魏军于 奔波被动之中,立即为田忌采纳,率领齐军杀往魏国都城大梁.,11,围魏救赵,12,庞涓得知大梁告急的消息,忙率大军驰援大梁.齐军事先在魏军必经之路的桂陵(今河南长垣南),占据有利地形,以逸待劳,打败了魏军.这就是历史上有名的围魏救赵之战.围魏救赵之妙,妙在善于调动敌人.调动敌人的要诀,则在攻其所必救.这在近代战争中的许多场合也是适用的.,13,3.减灶之法,公元前342年,庞涓带领10万大军进攻韩国.韩国向齐国求救.齐威王召集群
6、臣商讨对策,齐国的成侯邹忌主张不救,田忌主张早救.孙膑建议先答应韩国的请求,致使韩国必倾力抗敌.等到韩、魏双方战到疲惫不堪时,再出兵拯救危难之中的韩国,就可以用力少而见功多,取胜易而受益大.韩国仗恃有齐国相援,倾全力抗魏,五战皆败,只得于公元前341 年再次向齐求助.齐威王才决定派兵救韩,仍以田忌为主将,孙膑为军师.,14,战役之初,按照孙膑的计策,齐军长驱直入，把攻击的矛头指向魏国的都城大梁.魏将庞涓听到消息,立即回援,但齐军已经进入魏国境内.孙膑对田忌说:魏国军队素来彪悍勇武而看不起齐国,善于作战的人只能因势利导.兵法上说,行军百里与敌争利会损失上将军,行军五十里而与敌争 利只有一半人能赶
7、到.为了让魏军以为齐军后退时大量掉队,应使齐军进入魏国境内后先设十万个灶,过一天设五万个灶,再过一天设三万个灶.,15,庞涓行军三天,见到齐军所留灶迹,判断齐军在后退过程中士兵已经逃跑一大半,所以丢下步兵,只率轻车锐骑用加倍的速度追赶齐军.孙膑计算魏军行程,日暮时必然赶到马陵(今河南范县西南).马陵道路狭窄,两旁地形险阻.孙膑预先布置好伏兵,并集中优秀弩手夹道设伏.庞涓日暮追至马陵,进入齐军伏击阵地.齐军万弩齐发,魏军大乱,庞涓兵败自刎.齐军乘胜全歼十万魏军.马陵之战,孙膑的因势利导、调动敌人、变劣势为优势、力争发挥突然性的作战指导思想,是颇有参考价值的.其退军设伏的战法,也给了后人不少的启示
8、.,16,围魏救赵与减灶之法都充分体现了如何筹划兵力,选择最佳时间、地点,趋利避害,集中优势兵力以弱克强的运筹思想.,17,4.丁谓修皇宫,丁 谓：苏州长洲（今江苏省苏州）人，北宋真宗时任右谏议大夫（右议院院长)、权三司使，后升至宰相，被封为晋国公。其修复京城的故事被尊为古代“运筹学”运用的典范。宋真宗大中祥符年间(公元1008一1017年),都城开封里的皇宫失火,需要重建.右谏议大夫、权三司使丁渭受命负责限期重新营造皇宫.建造皇宫需要很多土,丁渭考虑到从营建工地到城外取土的地方距离太远,费工费力.丁渭便下令将城中街道挖开取土,节省了不 少工时.,18,挖了不久,街道便成了大沟.丁渭又命人挖开
9、官堤,引汴河水进入大沟之中,然后调来各地的竹筏木船经这条大沟运送建造皇宫所用的各种物材,十分便利(见图.等到皇宫营建完毕,丁渭命人将大沟中的水排尽,再将拆掉废旧皇宫以及营建新皇宫所丢弃的 砖头瓦砾添入大沟中,大沟又变成了平地,重新成为街道.这样,丁渭一举三得,挖土、运 送物材、处理废弃瓦砾等三件工程一蹴而成,节省的工费数以亿万计.这是我国古代大规模工程施工组织方面运筹思想的典型例子.,19,20,5.沈括运粮,沈括(1031-1095年),北宋时期大科学家、军事家.在率兵抗击西夏侵扰的征途中,曾经从行军中各类人员可以背负粮食的基本数据出发,分析计算了后勤人员与作战士兵在不同行军天数中的不同比例
10、关系,同时也分析计算了用各种牲畜运粮与人力运粮之间的利弊,最后做出了从敌国就地征粮,保障前方供应的重要决策.从而减少了后勤人员的比例,增强了 前方作战的兵力.,21,梦溪笔谈,梦溪笔谈是我国北宋大科学家沈括的传世著作。沈括在晚年用笔记文学体裁写成梦溪笔谈二十六卷，再加上补笔谈三卷和续笔谈，共列有条文六百零九条，遍及天文、数学、物理、化学、地学、生物以及冶金、机械、营造、造纸技术等各个方面，内容十分广泛、丰富，是中国科学史的重要著作。梦溪笔谈中所记述的许多科学成就均达到了当时世界的最高水平。英国著名科学史专家李约瑟称梦溪笔谈是“中国科学史上的坐标”。,22,当时沈括的分析计算过程（梦溪笔谈译文）
11、,凡是行军作战,如何从敌方取得粮食,是最急迫的 事情.自己运粮不仅耗费大,而且势必难以远行.假设一个民夫可以背六斗米,士兵自带五天的干粮.如果一个民夫供应一个士兵,单程只能进军十八天六斗米,每人每天吃二升,二人吃十八天*).如果要计回程的话,只能进军九天.如果两个民夫供应一个士兵,单程可进军二十六天.(两个民夫背一石二斗米,三个人 每天要吃六升.八天以后,其中一个民夫背的米已经吃光,给他六天的口粮让他先返回,以后的十八天,二人每天吃四升米,)如果要计回程的话,只能前进十三天的路程(前八天每天吃六升,后五天及回程每天吃四升米,能够进军十八天).若考虑回程,只能进军十三天.如果三个民夫供应一个士兵
12、,单程可进军三十一天(三人背米一石八斗,前六天半四个人,每天吃八升米,遣返一个民夫,给他四天口粮.中间的七天三个人同吃,每天吃六升,再遣返一个民夫,给他九天口粮,最后的十八天两个人吃,每天四升.如果要计回程的话,只可以前进十六天的路程(开始六天半每天吃八升,中间七天,每天吃六升,最后两天半以及十六天回程每天吃四升）.而三个民夫供应一个士兵,已经到极限了.*士兵干粮相当于十升米,连同民夫背的米共有七十升,每天吃四升,实际上只能维持十七天半.十八天是以整数来说的.以下计算类同.,23,如果要出动十万军队,辎重占去三分之一兵源,能够上阵打仗的士兵不足七万人.这就要用三十万民夫运粮.再要扩大规模很困难
13、了.每人背六斗米的数量也是根据民夫的总数平均来说的.因为其中的队长不背,伙夫减半,他们所减少的要摊在众人头上.更何况还会有患病和死亡的人,他们所背的米又要由众人分担.这样每个民夫所背的米常常不止六斗.所以军队中不容许饮食无度,如果有一个人暴食,二、三个人供应他还不够.如果用牲畜运输,骆驼可以驮三石,马或骡可以驮一石五斗,驴子可以驮一石.与人工 相比,虽然能驮的多,花费也少,但如果不能及时放牧或喂食,牲口就会瘦弱而死.一头牲口死了,只能连它驮的粮食也一同丢弃.所以与人工相比,实际上是利害相当.利弊分析后的结论是：从敌国就地征粮。这种军事后勤问题的分析计算是具有现代意义的运筹思想的范例.,24,史
14、记：“运筹帷幄中,决胜千里外”,在公元前3世纪楚汉相争中,汉高祖刘邦的著名谋士张良为推翻秦朝,打败项羽,统一全国,立下大功,刘邦赞誉他运筹帷幄中,决胜千里外.史记在高祖本纪、留侯世家多处提及运筹帷幄中,决胜千里外.这里的运筹,指张良在帷幄中制定作战谋略的过程.在西汉时代,运筹已被当作制定谋略与决策职能分工的代名词.我国学术界1955年开始研究运筹学时,正是从史记中摘取“运筹”一词作为OR(Operations Research)的意译,就是运用筹划、以智取胜的含义.从史记对运筹的记述表明,我国运筹思想源远流长,至今对运筹学的发展仍有 重要影响.诸葛亮也是得心应手地运用运筹学思想的古代军事家。,
15、25,司马迁-史记,司马迁,26,刘邦赞誉张良运筹帷幄中,决胜千里外.,27,张良,28,二、近代运筹学的起源,运筹学是由英文Operation Research翻译过来的.Operation Research原意是运作研究或作战研究,我国将它译作运筹学,是借用了史记中运筹帷幢中,决胜千里之外一语中“运筹”二字,既显示其军事的起源,也表明它在我国已早有萌芽,因此,以运筹学为译名,是非常恰当的.20世纪初,丹麦工程师爱尔朗(A.K.Erlang)研究电话服务的等候问题,标志着排队论的诞生(1909).1928年,冯.诺伊曼(John Von Neumann 1903-1957）以研究二人零和对策
16、的一系列论文为对策论奠基.1939年,苏联的康托洛维奇(L.V.kantorovich,1912-1986)发表生产组织和计划中的数学方法一书是规划论的开始.这些工作,仍是现在运筹学研究的领域.但作为一门学科,运筹学诞生于20世纪第二次世界大战期间,运筹学起源于军事、管理、经济.,29,爱尔朗,冯.诺伊曼,康托洛维奇,30,1.运筹学的军事起源,古代中国 孙子兵法一书中,体现了丰富的运筹思想。孙武首先将度、量、数 等概念引人军事领域,通过必要的计算,来预测战争的胜负,并指导战争中的有关行为.围魏救赵、增兵减灶、沈括运军粮.古代欧洲 阿基米德、达芬奇、伽利略都研究过作战中的运筹问题.,31,第一
17、次世界大战与第二次世界大战期间 这期间最早进行的运筹学工作是以英国生理学家希尔为首的英国国防部防空试验小组在第一次世界大战期间进行的高射炮系统利用研究.美国人爱迪生用博弈论和统计分析方法研究出了商船避免德国潜艇袭击的航行策略,也对以后运筹学的发展有所影响.1935年,英国科学家沃森一瓦特(R.Watson-Wart发明了雷达.但在一次空防演习中发现,由这些雷达送来的常常是互相矛盾的信息,需要加以协调和关联,才能改进作战效能,于是提出了运筹的课题.1939年,组建了一个代号为Blackett马戏团的研究小组,专门就改进防空系统进行研究.,32,他们对雷达探测、信息传递、作战指挥、战斗机与防空火力
18、的协调,做了系统的研究并获得 了成功,大大提高了英国本土的防空能力,在后来对抗德国纳粹的空袭战斗中发挥了极大作用.“Blackett马戏团”是世界上第一个运筹学小组.在他们就此项研究所写的研究报告中使用了“Operational Research”一词,意指“作战研究”或“运作研究”.从学术思想上,他们的研究已经蕴含着整体性的概念和系统分析的思想，这是运筹学的精髓.,33,改进深水炸弹的起爆深度，打破德国的海上封锁,第二次世界大战时,德国的潜水艇严重威胁盟军的运输船,于是有必要研究如何用飞机投掷深水炸弹,有效摧毁敌军潜艇.1942年,麻省理工学院的物理学家莫尔斯(P.W.Morse)领导的小组
19、经过调查研究,提出两条重要建议:(l)将反潜攻击由反潜舰艇投掷水雷改为由飞机投掷深水炸弹；且仅当潜艇浮出水面或刚下潜时,才投掷深水炸弹:炸弹的起爆深度由原来的水下100米左右改为水下25米左右.(2)改进运送物资的船队及护航舰艇编队的方式,由小规模多批次,改进为加大规模、减少批次,可使损失减少.军方采用了上述建议,最终成功地打破了德国的海上封锁,并重创德国潜艇舰队.第二次世界大战结束时,英美及加拿大军队中工作的运筹学工作者已超过了700人,正是由于战争的需要,运筹学有了长足的发展,并且形成为一门科学.,34,2.运筹学的管理起源,第一次世界大战前就已经发展成熟的古典管理学派,对运筹学的产生和发
20、展影响很大.以泰勒(Taylor、甘特(Gantt、吉尔布雷思(Gilbreth)等为代表的古典管理学派,对企业管理的中心思想是寻求一些方法,让人们自愿地联合和协作,保持个人的首创精神和创造能力,达到增加效率的目的.他们提出了管理的基本原则,研究 了机构设置、权限、工厂布局、计划等一系列问题,也提出了刺激性工资制度.甘特提出的黑道图,现在已经发展为统筹方法.管理实践和管理科学的许多问题,至今仍然是运筹学家关注的课题.,35,3.运筹学的经济学起源,经济学理论对运筹学的影响是和数理经济学学派紧密联系的.数理经济学对运筹学,特别是对线性规划的影响可以从魁奈(Qusnay)1758年发表的经济表算起
21、,当时最著名的经济学家沃尔拉斯(Walras)研究了经济平衡问题,后来的经济学家对其数学形式继续研究并得到深入发展.1928年,冯.诺伊曼(von Neumann John,1903-1957)以研究二人零和对策的一系列论文为“对策论”奠基,1932年,又提出了广义经济平衡模型.1939年,苏联的康托洛维奇发表生产组织和计划中的数学方 法.这些工作都可以看作是运筹学的前奏.,36,三、运筹学的性质和特点,1.运筹学的性质 1）运筹学是一种普遍的科学 运筹学从实践中产生以后，不再是对个别事物的分散研究，而是对统筹协调类问题的普遍研究,可广泛应用于工商企业、军事部门、民政事 业等许多部门。,37,
22、2）运筹学强调以量化为基础 运筹学需要建立数学模型,为决策者提供定量的依据。,38,3）运筹学依靠多学科的交叉 例如，综合运用经济学、心理学、物理学、系统学等学科中的方法。,39,4）运筹学强调整体最优 它不是仅仅考虑局部的优化，而是以整体最优为目标。它从系统的观点出发,力图以整个系统最佳的方式来解决该系统各部门之间的利害冲突，对所研究的问题求出最优解。,40,2.运筹学的特点,1）目的性 做一件事，首先应该明确，你追求的是哪方面的效益.例如，我方与敌方作战,目的是为了抢占战略要地,还是最大限度地杀伤敌人有生力量,还是突围，等等.目的明确之后，应贯彻始终,直至最终实现目的.如果起初目的就不明确
23、或目的有误,那么后面的工作很可能就是徒劳.,41,例：第二次世界大战期间,英美商船为了对付德国飞机的袭击,在船上装设了高炮,但这些高炮击落的敌机很少(仅占来袭敌机的4%),而且高炮的安装维修费用高；这时有人提出应将商船上的高炮拆除.但是运筹分析人员指出,安装高炮的目的不是击落敌机,而是保护商船安全按期到达目的地.统计显示,不安装高炮的商船损失率大于25%,安装高炮后,致使敌机不敢低飞,商船的损失率降到了10%以下,可见安装高炮是有效的.目前最先进的高炮，对现代喷气式战斗机的击毁率不到千分之一,但各国的防空系统中还少不了高炮，这同样是因为考虑到使用高炮的目的性.,42,2）系统性 一个系统的优化
24、指标常常有多个,例如对于彩电来说,优化目标有清晰度、稳定性、抗干扰性、灵敏度等。几个指标同时达到最优的情况，一般并不存在.因此,要达到整体的优化,必须进行统一规划,在诸多的可能方案中找出一个相对优秀的方案.系统性在军事指挥中尤为重要.古今不乏这样的战例,某方以少量兵力,阻止敌方主要力量前进,以实现整个战局目的.这就是牺牲局部利益来求取全局最优.,43,3）.有效性 例如，在军事上,兵贵神速,但军事效果不仅是指速度,更重要的是以较少的代价换取较大的成功.于是，如何减小伤亡就是一个军事上的有效性问题.在运输系统中,怎样以较小的油耗,在限定时间内,使运输车队到达，也是一个有效性问题.这类问题的解决并
25、非轻而易举,其中要求的几个方面效果，实现起来可能互相矛盾。而运筹学能为解决这类问题提供可行的途径.,44,4）科学性 运用运筹学,能大大增强决策的科学性。因为这种决策方式有定量分析作基础,而且手段先进,有较准确的数学模型、适合的算法以及计算机设备作保证,只要信息来源可靠,运用运筹学做出的决策方案肯定比凭感觉,拍脑袋 想出来的要有更高的可行性价值.这就是运筹学的科学性所在.例：马知恩小组关于“非典型肺炎”的预测（03-5-19）高峰期已经过去；当年6月下旬可以解除旅游禁令；患病总人数小于6000.,45,5）参谋性“运筹学再高级也只起参谋作用，他不能充当指挥员，不是决策人。运筹的结果只是用来辅助
26、指挥员去作决策。”其原因在于,并非所有的问题都能进行量化处理，建立数学模型。例如，系统中各种“人的因素”就难以量化描述。因此,运筹得出的结果在最终决策时,只能作为参谋和咨询之用。领导者实践经验的积累，当然有利于提高决策能力；而学习和掌握运筹学,也将对提高综合决策能力有很大的帮助。,46,四、运筹学在管理领域的应用范围,1.生产计划 如一家重 型制造厂用线性规划安排生产计划,节省了10%的生产费用.另外,诸如生产作业计划、日程表的安排、合理下料、配料问题、物料管理等也可用运筹学来帮助解决.,47,2.市场营销,在广告预算和广告媒介的选择、竞争性定价、新产品开发、销售计划、市场竞争策略的制定等方面
27、,运筹学 也大展身手.美国杜邦公司在五十年代起就非常重视将运筹学用于研究如何做好广告工作、产品定价,通用公司也运用运筹学方法进行市场模拟研究.,48,3.库存管理,运筹学中的存贮论可以应用于物资库存量的管理,以确定仓库的合理容量，以及确定适当的库存方式和库存量.,49,4.运输问题,用运筹学,可以确定最小成本的运输线路、物资的调拨、运输工具的调度，以及为方便运 输选择建厂的地址等等.,50,5.人事管理,对人员的需求和招聘情况的预测；人力资源的开发，如对人才的教育和培训,人员的合理编制,人才的合理分配和利用,人才评价体系、薪酬体系的确定等，都可运用运筹学方法。,51,6.财务与会计,这里涉及预
28、算、贷款、成本分析、定价、投资、证券管理和现金管理等。,52,其他,此外,运筹学还成功地应用于设备维修、更新和可靠性研究，项目选择与评价，工程的优化设计，信息系统的设计和管理以及各种城市紧急服务系统的设计和管理上。,53,五、运筹学的分支,1.线性规划 这是运筹学最成熟的一个分支。开始是在生产组织管理和制定交通运输方案方面,后来波及更广的范围，小到一个班组的计划安排,大至整个部门,以至国民经济计划的最优化方案分析,它都有用武之地。线性规划具有适应性强,应用面广,计算技术比较简便的特点.电子计算机的出现和日益完善,更使规划论得以迅速发展。,54,2.非线性规划,规划论的另一部分，是非线性规划。它
29、的基础性工作是在1951年才由库恩(H.W.kuhn)和图克(A.W.Tucker)等人完成的,后来逐步发展。,55,3.图论,图论是一个古老的但又十分活跃的分支,它是网络技术的基础.在1847年基尔霍夫应用图论的原理分析电网,从而把图论引进到工程技术领域.20世纪50年代以来,图论的理论得到了进一步发展。将复杂庞大的工程系统和管理问题用图描述,可以解决很多工程设计和管理决策的最优化问题。,56,4.决策论,决策就是根据客观可能性,借助一定的理论、方法和工具,选择最优策略、方案的过程。决策问题是由决策者和决策域构成的,而决策域又由决策空间、状态空间和结果函数构成。决策的类型,按决策者所面临的状
30、态是否确定可分为:确定型决策、风险型决策与不确定型决策；按决策所依据的目标多少可分为:单目标决策与多目标决策；按决策问题的性质可分为:战略决策与策略决策，等等。,57,5.博弈论(对策论),有利害冲突的诸方,为了各自的需要在竞争场合下做出决策,且各自的决策能互相影响,这种决策称为对策.竞争性质的活动是人类生活中常见的，如体育比赛、军事斗争,各企业之间的经济谈判及市场争夺等。在竞争过程中,各方为了达到自己的目标和利益,必须考虑对手各种可能的行动方案,并力图选取对自己最为有利或最为合理的方案。博弈论就是研究对策行为中竞争各方是否存在着最合理的行动方案,以及如何找到这个合理的行动方案的数学理论和方法
31、.,58,6.排队论(随机服务系统理论),1909年丹麦的电话工程师爱尔朗(A.K.Erlang)提出排队问题；1949年前后,开始了对机器管理、陆空交通等方面的研究；逐渐奠定了现代随机服务系统的理论基础。排队论主要研究各种排队的队长,排队的等待时间及所提供的服务等各种参数,以便求得更好的服务。它是研究系统随机聚散现象的理论.,59,7.可靠性理论,可靠性理论是研究系统故障、以提高系统可靠性的理论.它研究的系统有两类:(1)不可修复系统:如导弹 这种系统的参数是寿命、可靠度等；(2)可修复系统:如一般的机电设备 这种系统的重要参数是有效度,即 正常工作时间/(正常工作时间+事故修理时间).,6
32、0,8.搜索论,搜索，即寻找某种目标。搜索论研究的是:在资源和探测手段受到限制的情况下,如何设计搜索的方案,并加以实施的理论.例如二十世纪60年代，美国寻找在大西洋失踪的核潜艇打谷者号和蝎子号,以及在地中海寻找丢失的氢弹,都是依据搜索论获得成功的.,61,六、线性规划方法简介,在所有的管理与经营中，都要涉及到资金、时间、人力、物力等资源的消耗。如何优化资源配置，使有限的资源产生最大的效益，这就是规划论。规划论分线性规划与非线性规划。线性规划是运筹学中研究最为深入、应用范围最广、使用效果也最为明显的一个分支。,62,1.通过实际问题认识线性规划,1）利润最大化问题 某企业生产三种产品，这些产品分
33、别需要甲、乙两种原料，生产每种产品一吨所需原料（吨）和每天原料总限量（吨）及每吨不同产品可获利润(千元/吨)情况如表21所示。试问，该企业怎样安排生产，才会使每天的利润最大?,63,解：设该企业生产产品，分别为 吨，则总利润的表达式为 我们希望在现有资源条件下总利润最大。现有资源的限制为 此外，由于未知数（我们称为决策变量）是计划产量，应有 列为非负的限制，即。,64,由此得到问题的数学模型为其中 为英文subject to的缩写，表示决策变量 受它后面的条件的约束。求出这个问题的最优解为，代入总利润的表达式 对应的目标函数最大值为250。由此得到该企业在现有资源条件下，日生产的最优安排是：产
34、品 不生产，生产25吨，生产25吨，可实现最大利润250（千元）/日。,65,2）成本最小化问题,某钢铁厂熔炼一种新型不锈钢,需要 4种合金为原料，经测定这 4种原料关于元素铬（Cr）、锰（Mn）和镍（Ni）的质量分数（%）、单价以及这种新型不锈钢所需铬（Cr）、锰（Mn）和镍（Ni）的最低质量分数（%）如表23所示 假设熔炼时重量没有损耗，问：要熔炼100吨这样的不锈钢，应选用原料 各多少吨，能够使成本最小?,66,解：设选用原料 分别为 吨。由于追求的目标是成本最小，故有最小成本表达式：关于约束条件，由于假设熔炼时重量没有损耗，熔炼该种不锈钢100吨，它由原料 熔炼而成，故有等式约束又因该
35、不锈钢所需铬（Cr）、锰（Mn）和镍（Ni）的最低质量分数是由4种合金 对相应元素的质量分数构成，注意到要熔炼该种不锈钢100吨，于是得到铬（Cr）、锰（Mn）和镍（Ni）的质量分数满足的不等式约束依次为,67,此外，各种合金的加入量以整吨为单位，即有限制 且为整数。综合上述讨论，我们得到该问题的线性规划模型为其解为。即选用原料 依次为27吨、32吨、41吨、0吨，最低成本9571万元。,68,3）运输问题,一个企业有若干个生产基地与销售站点，根据各生产基地的产量及销售站点的销量，如何制定调运方案，使某种一定量的产品从若干个产地运到若干个销售地的总的运费最小?如某建材公司有三个水泥厂，四个经销
36、商 其产量、销量、运费（元/吨）见表25。如何制定调运方案，使总的运费最小?,69,解：设由生产基地 运到销售地 的货运量为，则得到问题的线性规划模型为,70,其解为元。最佳运输方案见：表26,71,4）合理下料问题,现有一批长度一定的原材料钢管，由于生产的需要，要求截出不同规格的钢管若干。试问应如何下料，既能满足生产的需要，又使得使用的原材料钢管数量最少（即废材最少）?具体问题：料长74m，要求截成29m，2lm，15m的钢管分别为1000根，2000根，1000根。如何截取，才使得总用料最省?,72,解：把所有可能的下料方式、按照各种下料方式从料长74m的原料上得到的不同规格钢管的根数、残
37、料长度,以及需要量列于表28中。例如，按照下料方式，可以得到2.9m钢管2根，15m钢管1根。问题转化为确定每种下料方式各用多少根74m的原料。,73,设 分别为按照 方式下料的原料根数。则得到问题的线性规划模型为其解为（根）。最佳下料方案为：方式 根，方式 根，方式 根。,74,2.线性规划的图解法,对一个线性规划问题建立数学模型之后，就面临着如何求解的问题。我们仅介绍线性规划问题的图解法，并且仅介绍含有两个决策变量的情况。它简单直观，由此便可以了解线性规划问题求解的基本原理。图解法的步骤可概括为：（1）在平面上建立直角坐标系；（2）图示约束条件，找出可行区域；（3）图示目标函数，即画出目标
38、函数等值线；（4）对 问题朝着增大（减少）纵截距的方向移动 目标函数等值线至可行区域的某个边界点；（5）寻找该边界点的坐标得到最优解。以下结合实例来具体说明.,75,【例】用图解法求解线性规划,解：先画出线性规划的可行区域如图阴影部分。再画出目标函数等值线，朝着增大纵截距的方向移动等值线至阴影部分的边缘点。,76,最后求解线性方程组解得最优解，代入 f 的表达式，求得最大值。解完。,77,【例】用图解法求解线性规划,解:先画出线性规划的可行区域如图阴影部分。再画出目标函数等值线，朝着增大纵截距的方向移动等值线至点。最后求解线性方程组 得到最优解，,代入 f 的表达式，最大值。解完。,78,求解
39、结果还可能出现其它情况,上面两个例子中，求解得到的问题的最优解，是惟一的；但对一般线性规划问题，求解结果还可能出现其它情况。有时，可能出现多个最优解（但都对应着相同的最优值）；有时，可能出现无穷多个最优解（但都对应着相同的最优值）；有时，可能没有最优解（例如当可行区域是无界区域，或可行区域为空集时）。当根据实际问题建立的线性规划模型的求解结果出现无解的情况时，一般说明建模有错误。或者缺乏必要的约束条件，或者是出现了互相矛盾的约 束条件，建模时应注意。,79,七、现代运筹学实例,博弈论(The Game Theory)也是运筹学的重要分支。以下实例主要选自博弈论。博弈论思想的主要特征是各参与人所
40、实施的策略相互依存，各方在冲突或合作后所实现的得失结果，不仅取决于自己所采用的策略，同时也依赖于其他参与人所采用的策略，它是各参与人策略组合的函数。从数学的角度看，博弈论就是研究竞争行为中的竞争各方是否存在最合理的策略，以及如何找到这个合理策略的理论。博弈论认为：人是理性的，即人人都会在约束条件下最大化自身的利益；人们在交往合作中有冲突，行为互相影响，而且信息不对称。博弈论的经典案例是“囚徒困境”。,80,1.囚徒困境问题,两个小偷甲和乙联手作案，因私入民宅被警方抓住但未获证据。警方将两人分别置于两间房间分开审讯，政策是若一人招供但另一人未招，则招者立即被释放，未招者判入狱10年；若二人都招，
41、则两人各判刑8年；若两人都不招，则未获证据但因私入民宅各拘留1年。将这些数据列表如下：,81,尽管甲不知道乙是否招供，但他认为自己选“招”最好，因而甲会选择“招”，乙也同样会选择“招”，结果各判8年；但若两人都不招，结果是每人只被判1年，但在“人是理性的，即人人都会在约束条件下最大化自身的利益”的基本假设下，这种结果是不会出现的。甲和乙是参与博弈的人，称为“局中人”。上表中每一个小方格内的数字被称为局中 人的支付，其中左边的数字代表甲的支付，右边的是乙的支付。表上中的双变量矩阵称为博弈支付矩阵。局中人所选择的策略构成的组合（招，招）被称为博弈均衡。这个组合中前后两个策略分别表示甲和乙所选择的策
42、略。,82,类似的问题：商家价格战,当一些出售同类产品的商家共谋将价格抬高，消费者实际上不用着急，因为商家联合维持高价的垄断行为一般不会持久。例如，2000年我国几家生产彩电的大厂商合谋将彩电价格维持高位，他们搞了一个“彩电厂家价格自律联盟”，并在深圳举行了由厂商首脑参加的“彩电厂商自律联盟高峰会议”。当时，国家有关部门还未出台相关的反垄断法律，对于这种所谓“自律联盟”，国家在法律上暂时还无能为力。但是实际情况并不像策划人预想的那样。这是因为，“彩电厂商自律联盟”只不过是一种“囚徒困境”。在高峰会议之后不到两周，彩电价格不是上涨而是一路下跌。这是因为厂商们都有这样一种心态：无论其他厂商是否降价
43、，我自己降价是有利于自己的市场份额扩大的。,83,纳什均衡,对于一个博弈问题，如果在每一个局势中，全体局中人的得失相加都是零，则称此博弈为零和博弈，否则称为非零和博弈。在二人零和博弈中，双方局中人寻求的最优解是一种纳什均衡；达到这种均衡时，只要其他局中人不改变自己的策略，则任何一方单独改变策略，只能带来收益或效用的减少。,84,2.俾斯麦海的海空对抗,（l）相关背景资料 1943年2月，第二次世界大战中的日本，在太平洋战区己处于明显的劣势。为扭转战局，日军统帅山本五十六统率下的一支舰队策划了一次军事行动：由集结地南太平洋新不列颠群岛的拉包尔出发，穿过俾斯麦海，开往新几内亚的莱城,支援困守在那里
44、的日军（见下图）。,85,86,山本五十六心中明白，在日本舰队穿过俾斯麦海的3天航程中，不可能躲开美军的 空袭；他要谋划的是尽可能地减少损失。当美军获此情报后，太平洋战区盟军统帅麦克阿瑟命令空军司令肯尼将军组织空中打击。.日美双方的指挥官及参谋人员都进行了冷静与全面的谋划。自然条件对于双方来说是已知的。基本情况是:从拉包尔到莱城 的海上航线有南线和北线两条，通过时间均为3天。气象预报表明，未来3天中，北线阴雨，能见度差；而南线则天气晴好，能见度佳。,87,（2）局势估计,局势1：美军侦察机重点搜索北线，日本舰队恰好走北线。由于气候恶劣，能见度低以及美军空军基地靠近南线，因而美军只能实施两天有效
45、的轰炸。局势2：美军侦察机重点搜索北线，而日本舰队走南线。由于发现晚，尽管美军空军基地靠近南线，但有效轰炸也只有两天。局势3：美军侦察机重点搜索南线，而日本舰队走北线。由于发现晚，美军空军基地靠近南线，以及北线天气恶劣，故有效轰炸只能实施1天。局势4：美军侦察机重点搜索南线，日 本舰队恰好走南线。此时，日军舰队 被迅速发现，美军轰炸机群所需航程 很短，加之天气晴好，这将使美军空 军在3天中皆可实施有效轰炸。,88,（3）数学模型,局中人：美日双方决策者策 略：美日双方各有两个策略：南线、北线支 付：美方的支付（赢得轰炸天数）矩阵为,89,（4）求解分析,局中人1（美军）希望获得的支付（赢得轰炸
46、天数）尽可能多，但同时，他们也深知：局中人2（日军）必然想方设法使自己的付出（被轰炸天数）尽 可能少。因此，美军参谋部在作选择时，首先要考虑：选择每个策略时至少能赢得多少，然后从中选取最有利的策略。具体来说：先对支付矩阵的各列求极小（至少赢得）,然后，在对矩阵各列极小组成的集合中取极大（争取最佳）。于是有：对于日军参谋部，因居于被动地位，故首先考虑在对方每个策略中最多损 失多少。在此前提下争取损失最小。具体来说：对同一支付矩阵的各行求极大（最多损失），然后，对矩阵各行极大组成的集合中取极小（争取最佳)。于是有：上述求解思想可概括为：“从最坏处着想，去争取最好的结果”。这是理性思考的表现。,90
47、,实际结果,这里恰有：这正是历史实际对局的结果，即：局势1 成为事实。肯尼将军命令美军侦察机重点搜索北线；而山本五十六命令日本舰队 取道北线航行。美军飞机在1天后发现日本 舰队，基地在南线的美军轰炸 机群远程飞行，在恶劣天气中，实施了2天有效地轰炸，重创了 日本舰队，但未能全歼。,91,3.中美贸易战,（1）相关背景资料 1996年5月15日，美国政府借口中国对知识产权保护不力，单方面宣布：对中国出口到美国的纺织品、服装及电子产品实施惩罚性关税，涉及产品金额达30亿美元，惩罚性税率达100%，将于一个月后生效。当晚，中国外经贸部发表公告，做出了强烈的反应。公告中表示：如果美国政府一意孤行，中国
48、将实施反报复，并与美国贸易报复措施生效的同时生效。在公告中还列举了反报复清单，报复惩罚额与美国相当。,92,（2）数学模型,局中人：中国、美国。下面用一些模拟的数据来写出该博弈问题的赢得矩阵：将双方报复的损失均假设为50亿元，双方不报复的收益均假设为20亿元，单方报复而另一 方不报复，不报复方的损失假设为150亿元（考虑牵连效应）。,93,（3）实际结果,这是一个二人非零和博弈问题。按纳什均衡理论可以得出:策略对（报复，报复）为惟一的纳什均衡。事实发展是：双方都有允若，也有威胁。由于中方反报复力度相当，又在强化知识产权保护上作了承诺，因而，诱使美方考虑合作与不合作的得与失。双方经过5天的磋商，
49、在知识产权问题上达成一致的同时，彼此宣布取消拟采取的贸易报复措施，避免了两败俱伤的结局，得到了好的结果。,94,4.层次分析法应用实例,某市中心有一家商场，由于街道狭窄，经常造成交通堵塞，市政府决定解决这个问题。经过有关专家会商研究，制定出3个可行方案：Al：在商场附近修建一座环形天桥；A2：在商场附近修建地下人行通道；A3：搬迁商场。需要提出改善市中心交通环境的决策建议。根据当地实际情况，专家组拟定5个评价准则：通车能力；方便群众；基建费用不要太高；交通安全；市容美观。,95,根据实例中给出的专家咨询意见，建立层次结构模型，如图,96,利用层次分析法（过程略去）得到结论 3个可行方案的排序结
50、果是：修建天桥为上策；修建地下人行通道为中策；搬迁商场为下策。市政府实际决策：修建天桥,97,八、结语,学习运筹学，最重要的是掌握其思想方法，将运筹学的思维模式变成自己思考问题的模式之一。遇到问题，首先想到解决该问题需要哪些资源，从哪里可以获得这些资源；其次考虑在获得资源后，如何使这些资源得到最合理的利用，使其产生最大效益。,98,六、数学文化美食（之）-聪明的博比,从一本杂志上读到一则笑话：某人向客人夸耀自己的儿子博比特别聪明：“他只有两岁，就认识所有的动物了。”并让儿子在客人面前表演。客人翻开一本动物画册，指着一张长颈鹿的画片问：“这是什么？”博比答：“马马。”又指了一张老虎的画片，又答：
