第00章 绪论-运筹学

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