单纯形法绪论.ppt

杭州电子科技大学管理学院魏洁 运筹学 魏洁 weijieding@163.com 运筹学的应用可大可小，可以处理各种策略性的问题。 先给大家讲一个生活中碰到的最通俗的例子——沏茶水。沏茶，看起来是一件日常生活中再小不过的事情，却包含着运筹学的道理。让我们来看一看，沏茶的过程可以分为烧开水、洗茶壶、放茶叶多道“工序”。其中，烧开水所需的时间最长，洗茶壶、放茶叶的时间则较短。善于运筹的人，应该是先将水烧上，在烧水的过程中，从从容容地把茶壶洗净，把茶叶放好。而不善运筹的人，可能会先把茶壶洗净，把茶叶放好，才想起来水还没有烧；或者先把水烧开了，才急急忙忙去洗茶壶、放茶叶，搞得手忙脚乱。 再讲一个日常生活中稍微复杂一点的问题来讨论一下： 比如有一天你在家里看电视，这时熟睡的的孩子醒了在哭，接着厨房烧的水也开了，家里的电话也在响，不巧这时有人登门拜访也正在敲门，更糟糕的是天也要下雨了，而你晾着的衣服也没有收……这时你该怎么做？ 有人认为比较经典的做法是：先去哄着孩子，再抱着孩子去厨房把燃气灶关了，喊着“来了，来了”的同时可以去接电话再给客人开门，最后可以让客人帮你抱着孩子然后你去收衣服，完了，很顺理成章。 当然这里有几个问题值得推敲，首先，水开了是不是会把燃气灶弄熄了，那么是不是会中毒？那家里的电话是不是有什么急事？其次，来拜访的人是不是你认识或熟悉的，如果是坏人你把孩子交给他会怎么样？ 那我们是不是可以这样改一下：衣服我可以先不要管它，客人也可以让他稍等一下，那孩子在哭我们也可以暂时不管。电话响了你可以先接起来说“有事，稍等一下。”再到厨房把燃气灶关了，然后去给拜访的人开门，如果是你的好朋友当然可以让她帮你照看一下孩子再回电话，如果是你不认识的人那么你自然应该先去抱你的孩子，然后再和拜访的人交谈，弄清楚是怎么回事了那么你再去回电话，最后去收衣服也不迟。这样一来如果下雨了，湿的只是衣服。 这两个生活中的运筹学实例说明了运筹学应用的思想并不神秘，而现实的生活中，从沏茶安排这样一件小事，到规模宏大的建设项目，都能运用运筹学的原理。 通常在遇到这些复杂繁琐的事的时候，人们不会考虑太多，仅是凭着第一直觉去处理，结果也因为处理方式的不同而不同。有的人第一直觉好，就能把事情处理的很好，而有的人却只能接受糟糕的结果。生活中，如果我们能理智的去分析问题，找到处理问题的最佳办法，那么我们将会避免很多损失和烦恼，取得更大的成功和收获。而像这样去处理问题，就是运筹学的应用。 人们无论从事任何工作，不管采取什么行动，都希望所制订的工作或行动方案，是一切可行方案中的最优方案，以期获得满意的结果,诸如此类的问题，通常称为最优化问题。 运筹学就是以数学为主要手段、着重研究最优化问题解法的学科。 求解最优化问题的关键，一是建立粗细适宜的数学模型，把实际问题化为数学问题；二是选择正确而简便的解法，以通过计算确定最优解和最优值。 最优解与最优值相结合，便是最优方案。人们按照最优方案行事，即可达到预期的目标。 古籍中的运筹问题 田忌赛马：田忌与齐王多次赛马，屡战屡败，田忌的一位谋士比较了六种对策后建议…… 田忌赛马.doc 最早记载的《对策论》范例。 田 忌 赛 马 田忌赛马决策矩阵: 围魏救赵 公元前354年，魏国将军庞涓发兵8万，以突袭的办法将赵国的都城邯郸包围。 赵国抵挡不住，求救于齐。齐威王拜田忌为大将，孙膑为军师，发兵8万，前往救赵。 田忌打算直奔邯郸速解赵国之围。孙膑提出应趁魏国国内兵力空虚之机，发兵直取魏都大梁 (今河南开封)，迫使魏军弃赵回救。 这一战略思想，既避免齐军长途奔袭的疲劳，又致使魏军于奔波被动之中，立即为田忌采纳，率领齐军杀往魏国都城大梁。 庞涓得知大梁告急的消息，忙率大军驰援大梁。齐军事先在魏军必经之路的桂陵(今河南长垣南)，占据有利地形，以逸待劳，打败了魏军。 这就是历史上有名的“围魏救赵”之战。 “围魏救赵”之妙，妙在善于调动敌人。调动敌人的要诀，则在“攻其所必救”。这在近代战争中的许多场合也是适用的。 减灶之法 公元前342年，庞涓带领10万大军进攻韩国。韩国向齐国求救。齐威王召集群臣商讨对策，齐国的成侯邹忌主张不救，田忌主张早救。孙膑建议先答应韩国的请求，致使韩国必倾力抗敌。等到韩、魏双方战到疲惫不堪时，再出兵拯救危难之中的韩国，就可以用力少而见功多，取胜易而受益大。韩国仗恃有齐国相援，全力抗魏，五战皆败，只得于公元前341年再次向齐求助。齐威王才决定派兵救韩，仍以田忌为主将，孙膑为军师。 战役之初，按照孙膑的计策，齐军长驱直入，把攻击的矛头指向魏国的都城大梁。魏将庞涓听到消息，立即回援，但齐军已经进入魏国境内。孙膑