第一讲：导论ZY

大连海事大学交通运输管理学院张燕2012.3绪论§1什么是运筹学§2运筹学简史§2运筹学方法§1什么是运筹学特点相关学科内容典故名称定义典故田忌赛马丁谓挖沟沈括运粮田忌齐威王田忌赢得1上上－1千金2中中－1千金3下下－1千金合计-3千金田忌赛马孙膑1千金1千金1千金丁谓挖沟皇宫火毁大街丁谓挖沟宫址长沟取土运材除圾与汴水沟通丁谓挖沟宫址皇宫大街沈括运粮•《梦溪笔谈》鸿篇巨著•研究士兵数、行军天数、粮食需求数、民夫数这四个变量之间的关系，得出结论：十万大军行军一个月，至少需要三十万民夫运粮。结论：夺取敌军粮草至关重要。•与《孙子兵法》一脉相承：“食敌一盅，当吾三十盅。”“因粮于敌”OperationalResearchOperation’sResearchOR名称中译名称来源《汉书·高帝记》：“上曰：夫运筹帷幄之中，决胜于千里之外，吾不如子房。”子房即张良，高帝刘邦视为肱股其他译名港台：作业研究日本：运用学我国《管理百科全书》“运筹学是应用分析、实验、量化的方法，对经济管理系统中人力、物力、财力等资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。”1.边缘学科2.研究与实践紧密联系3.科学与艺术结合4.利用模型5.数量方法特点6.实验方法7.有赖电子计算机8.全局优化9.科学决策的依据10.适用面广特点内容确定型：线性规划，整数规划，目标规划，非线性规划，几何规划，不可微规划，参数规划，多目标规划，大型规划，网络规划，图论等等。随机型：随机规划，价值论，决策分析，对策论，多属性决策，随机过程，排队论,搜索论，可靠性理论，质量控制等等。内容混合型：动态规划，组合规划，存贮论，汰置论，模拟论，最优控制理论等等。模糊型：1965年，美国人查德(L.A.Zadeh)创立模糊数学;运筹学与之结合,形成模糊型。相关学科数学科学系统科学管理科学计算机科学经济系统最优运营问题经济系统投入产出管理投入既定，如何实现最大产出？产出既定，如何实现最小投入？多快好省多好快省田忌赛马丁谓挖沟OR经济系统最优运营问题资源效益教材：◦管理运筹学，靳志宏主编，大连海事大学出版社管理运筹学，韩大卫，大连理工大学出版社，2010年（第6版）运筹学导论，胡运权等译，弗雷德里克，杰拉尔德著，清华大学出版社，2007（第8版）IntroductiontoOperationsResearch,Frederick,Gerald著，清华大学出版社，2010（9thEdition）（英文版）考试方式及成绩组成：◦闭卷考试◦平时成绩（30%）+期末成绩（70%）第2章单纯形法21课程要求：◦课堂出勤、平时作业、软件操作、实践运用课程主讲：◦张燕，毕业于西安交通大学管理学院◦现任大连海事大学交通运输管理学院物流系讲师◦办公室：管理楼314◦个人邮箱：[e-mail]课程交流:◦邮箱：[e-mail]◦pw:spring2012§2运筹学简史混沌时期朦胧时期初创时期确立时期扩展时期混沌时期(古代)军事运筹《孙子兵法》、《孙膑兵法》公元前353年，围魏救赵，桂陵战役公元前342年，逐日减灶，马陵战役公元前212年，古希腊，阿基米德，策划粉碎罗马海军舰队对叙拉库斯城的围攻。混沌时期(古代)工程运筹金字塔古埃及都江堰秦朝李冰父子第一次工业革命，泰勒(F.W.Taylor)倡导“科学管理”以来，在生产经营中开始尝试运用数量方法；1905年，丹麦电话工程师爱尔朗(A.K.Erlang)开始研究电话自动拨号设备服务频数波动现象，至1917年创立排队论；1915年，美国学者哈里斯(F.W.Harris)提出经典经济批量公式，开创存贮论先河；朦胧时期(近代及现代初叶)一战中，美国发明家爱迪生(T.A.Edison)研究商船队避敌攻击最适当航行策略；1921年，法国数学家波雷尔(EmileBorel)研究国际象棋，首提博弈策略的概念；1922年，劳滕施特劳赫(W.Rautenstrauch)首创损益平衡图，用以表述量本利分析法；朦胧时期(近代及现代初叶)1924年，休哈特(WalterShewhart)，1931年，列昂节夫(W.W.Leontief)，国民经济计划投入产出平衡模型。朦胧时期(近代及现代初叶)x-σ控制图，质量控制；初创时期(二战中)英国1935年，雷达预警；1938年，作战研究；1939年，威廉斯(E.C.Williams)；1940年，“布莱克特马戏团”；初创时期(二战中)1942年，OR小组普及全军。典例•雷达部署•深水炸弹定深规范•空军巡航比率•空军基地机种配置与远航轰炸最佳编队•海运舰船最佳编队初创时期深水炸弹定深规范命中率仅2%左右威廉斯:数理学家40%情况属于:还能看到潜艇刚下潜15秒20~30呎原定深规范:100~200呎5倍以上定深规范改为初创时期空军巡航最高比率总量劣势：英德空军飞机数量1︰7为求局部极大化解总量劣势：最初规定全部飞机升空巡航比率70%但很快就难以为继巡航最高比率=?最终由OR小组成员生物学家康顿解决问题核心：飞机平均寿命35%可以持续初创时期海运舰船最佳编队lkc2500≈英国护航军舰数击沉德国潜艇数击沉英国舰船数交换系数编队45艘以上:1.7%以下:2.6%损失率•大规模编队,大量增加护航军舰北大西洋海上运输线——英国的生命线初创时期初创时期(二战中)美国•1940年，美国国防研究委员会主席康南特(J.B.Conant)访英归来，建议美军进行类似研究，促成美英两军OR合作•1942年，美军成立两个OR小组海军OR小组：摩尔斯(P.W.Morse)教授陆军OR小组：利茨(W.B.Leach)律师初创时期典例•日本—新加坡间海上布雷方案•对付日本空军神风队的作战策略•B-25轰炸机夜袭日本本土的作战策略•海陆军联合作战策略•诺曼底半岛登陆战•直布罗陀水域巡航策略初创时期(二战中)初创时期对付日本空军神风队调查477舰次遭袭记录损失率47%29%对策敌机态势主辅俯冲平冲大舰小舰发挥对空火力做z字型摆动做z字型摆动发挥对空火力横向迎击纵向迎击初创时期诺曼底半岛登陆战诺曼底半岛英吉利海峡英国法国布隆涅-加莱-敦刻尔克•摩尔斯:1943•D日计划•心理战•气象战•情报战初创时期直布罗陀水域巡航策略•1944:哈金斯少校海军VP–63巡逻机中队•约翰·佩芝姆博士:屏障巡逻战术1哩4哩•2月24日~3月16日三周:击沉3艘115哩/时3分钟初创时期其他国家•加拿大：1942年，空军OR小组•澳大利亚、法国(戴高乐)•苏联：1939年，列宁格勒大学，康托洛维奇(Л.В.Канторовиц)“生产组织与计划中的数学方法”初创时期(二战中)英国•1948年4月，英国运筹学俱乐部•1950年，《运筹学季刊》•1953年，更名英国运筹学会确立时期(1945~1955)确立时期确立时期美国1949年，美国运筹学委员会1952年5月，美国运筹学会(ORSA)《美国运筹学会会刊》1956年更名为《运筹学》1953年，美国管理科学研究会(TIMS)确立时期(1945~1955)确立时期著作、教育、研究、应用1955年，美英筹备国际运筹学会1955年，摩尔斯总结、展望确立时期(1945~1955)扩展时期我国现代运筹学概况1970年，华罗庚教授推广“优选法”1972年，钱令希教授开发“计算力学”钱令希——大连理工大学名誉校长、教授，中国科学院资深院士，我国最高层次的学术刊物≪运筹学杂志≫5名特约顾问编委中唯一的中国人掌握“三基”基本概念基本模型基本方法树立优化观念当前系统是否已经优化？否则，如何实现优化运行？未来的真实系统如何实现优化设计？为经济管理决策运筹学提供定量分析方法以及科学依据和优化方案运筹学研究的一般过程：定义问题和收集数据构建问题的数学模型借助计算机求解模型检验审核和调整模型准备模型的后续应用实施应用模型和系统设有n个客户，第j个客户的地理位置坐标为，该客户对某种货物的需求量为。现规划设立m个配送网点，第i个网点的容量为，试确定网点的地理位置，合理规划物流网络的结构与布局，使物流成本最低。jjba,njqj,...,1,mici,...,1,现代管理实践中遇到的众多决策问题最终都可以归结为优化问题，在物流工程与管理以及交通运输规划与管理等领域一、设施选址问题设第i个网点的地理位置坐标为，第i个网点为第j个客户配送货物量为。则该问题用数学模型表示为：miyxii,...,1,,njmizij,...,1,,...,1,minjjijiijbyaxz1122micznjiij,...,1,1njqzmijij,...,1,1njmizij,...,1;,...,1,0Min.s.t.某物流网络系统由多个批发商向多个零售商提供多种货物所组成。各批发商的供货能力及其地理位置、各零售商的需求量及其地理位置已知，试确定各批发商每种货物的供货范围和相应的供货量，使整个物流网络运输成本最低。二、运输规划问题设第i个供货商，其第k种货物的供应能力为，第j个零售商，其对第k种货物的需求量为第i个供货商到第j个零售商的单位运输成本为决策变量为第i个供货商向第j个零售商供应第k种货物数量为则该决策问题可以用数学模型表示为：Min.s.t.lkmiAik,...,1,,...,1,lknjBjk,...,1,,...,1,ijCijkxminjlkijkijxC111lkmiAxnjikijk,...,1;,...,1,1lknjBxmijkijk,...,1;,...,1,1lknjmixijk,...,1;,...,1;,...,1,0三、背包问题Max.s.t.niiixc1bxaniii1nixi,...,1,1,0四、旅行商问题Min.s.t.jiijijxdnixnjij,...,1,11njxniij,...,1,11nsnssxsjiij,...,1,22,1,jinjixij,,...,1,,1,0决策变量一、决策问题的构成要素目标函数约束条件Tnxxxx,...,,21xf0xg一般表示为xfzmjxgj,...,1,0xxxxxTn,,...,,21s.t.Opt.(min.ormax)启发式规则定性分析定量分析二、决策问题的解决途径决策问题决策环境启发式规则：直觉、经验定量分析:模型、算法定性分析：认识论、方法论二、管理运筹学的定位基础数学应用基础应用方法数学应用数学应用应用数学管理运筹学基础数学曲线应用数学曲线三、管理运筹学的工作程序问题分析数据处理数学建模约束处理算法设计程序设计结果分析辅助实施建模准备建模假设建模分析建模检验精确解算法近似解算法•导论第二章线性规划第四章目标规划第三章整数规划第五章非线性规划第六章动态规划第七章网络规划第八章不确定规划第九章服务系统规划第十章管理模拟第十一章管理博弈第十二章管理决策线性→非线性点→面静态→动态确定性→不确定性制造系统→服务系统数学模型→仿真模型定量→定量+定性技术→技术+艺术第四节：管理运筹学的内容体系及其内在联系市场销售生产计划资本运营库存管理运输问题财政和会计人事管理设备维修和更新项目评价和选择工程优化设计计算机信息系统城市管理发展战略先修课：高等数学，基础概率、线性代数教学计划数学规划以线性规划、整数规划、目标规划、运输问题为讲授重点；图与网络部分主要讲网络优化；随机优化讲授服务系统规划和管理决策。教学方法以授课为主，讲课中主要培养用最优化方法解决实际问题的能力。学习运筹学要把重点放在分析、理解有关的概念、思路上。在自学过程中，应该多向自己提问，如一个方法的实质是什么，为什么这样做，怎么做等。自学时要掌握三个重