单纯形法绪论

1、魏洁晕愁学？|运筹学的应用可大可小，可以处理各运筹学的应用可大可小，可以处理各种策略性的问题。种策略性的问题。|先给大家讲一个生活中碰到的最先给大家讲一个生活中碰到的最通俗的例通俗的例子子沏茶水。沏茶水。沏茶，看起来是一件日常生沏茶，看起来是一件日常生活中活中再小不过再小不过的的事情事情，却包含着运筹学的道，却包含着运筹学的道理。让我们来看一看，沏茶的过程可以分为理。让我们来看一看，沏茶的过程可以分为烧开水、洗茶壶、放茶叶多道烧开水、洗茶壶、放茶叶多道“工序工序”。其中，。其中，烧开水所需的时间最长，洗茶壶、放茶叶的烧开水所需的时间最长，洗茶壶、放茶叶的时间则较短。善于运筹的人，应该是先将水时

2、间则较短。善于运筹的人，应该是先将水烧上，在烧水的烧上，在烧水的过程中过程中，从从容容地把茶壶，从从容容地把茶壶洗净，把茶叶放好。而不善运筹的人，可能洗净，把茶叶放好。而不善运筹的人，可能会先把茶壶洗净，把茶叶放好，才想起来水会先把茶壶洗净，把茶叶放好，才想起来水还没有烧；或者先把水烧开了，才急急忙忙还没有烧；或者先把水烧开了，才急急忙忙去洗茶壶、放茶叶，搞得手忙脚乱。去洗茶壶、放茶叶，搞得手忙脚乱。|再讲一个日常生活中稍微复杂一点的问题来讨论一下：|比如有一天你在家里看电视，这时熟睡的的孩子醒孩子醒了在哭，接着厨房烧的水水也开开了，家里的电话电话也在响，不巧这时有有人人登门拜访也正在敲门敲门

3、，更糟糕的是天也要下雨了，而你晾着的衣服衣服也没没有收收这时你该怎么做？ |有人认为比较经典的做法是：先去哄着孩子，再抱着孩子去厨房把燃气灶关了，喊着“来了，来了”的同时可以去接电话再给客人开门，最后可以让客人帮你抱着孩子然后你去收衣服，完了，很顺理成章。|当然这里有几个问题值得推敲，首先，水开了是不是会把燃气灶弄熄了，那么是不是会中毒？那家里的电话是不是有什么急事？其次，来拜访的人是不是你认识或熟悉的，如果是坏人你把孩子交给他会怎么样？ |那我们是不是可以这样改一下：衣服我可以先不要管它，客人也可以让他稍等一下，那孩子在哭我们也可以暂时不管。电话响了你可以先接起来说“有事，稍等一下。”再到厨

4、房把燃气灶关了，然后去给拜访的人开门，如果是你的好朋友当然可以让她帮你照看一下孩子再回电话，如果是你不认识的人那么你自然应该先去抱你的孩子，然后再和拜访的人交谈，弄清楚是怎么回事了那么你再去回电话，最后去收衣服也不迟。这样一来如果下雨了，湿的只是衣服。 |这两个生活中的运筹学实例说明了运筹学应用的思想并不神秘，而现实的生活中，从沏茶安排这样一件小事，到规模宏大的建设项目，都能运用运筹学的原理。 |通常在遇到这些复杂繁琐的事的时候，人们不会考虑太多，仅是凭着第一直觉去处理，结果也因为处理方式的不同而不同。有的人第一直觉好，就能把事情处理的很好，而有的人却只能接受糟糕的结果。生活中，如果我们能理智

5、的去分析问题，找到处理问题的最佳办法，那么我们将会避免很多损失和烦恼，取得更大的成功和收获。而像这样去处理问题，就是运筹学的应用就是运筹学的应用。 |人们无论从事任何工作，不管采取什么行动，都希望所制订的工作或行动方案，是一切可行方案中的最优方案，以期获得满意的结果,诸如此类的问题，通常称为最优化问题。|运筹学就是以数学为主要手段、着重研究最优化问题解法的学科。|求解最优化问题的关键，一是建立粗细适宜的数学模型数学模型，把实际问题化为数学问题；二是选择正确而简便的解法解法，以通过计算确定最优解和最优值。|最优解与最优值相结合，便是最优方案。人们按照最优方案行事，即可达到预期的目标。| 田忌赛马

6、：田忌赛马：田忌与齐王多次赛马，田忌与齐王多次赛马，屡战屡败，田忌的一位谋士比较了六屡战屡败，田忌的一位谋士比较了六种对策后建议种对策后建议 田忌赛马田忌赛马.doc.doc | 最早记载的最早记载的对策论对策论范例。范例。|田忌赛马决策矩阵田忌赛马决策矩阵: :123456上上上中中下下下中中下上下中上上下下中下上上中中齐王田忌 |公元前公元前354年，魏国将军庞涓发兵年，魏国将军庞涓发兵8万，以突袭万，以突袭的办法将赵国的都城邯郸包围。的办法将赵国的都城邯郸包围。|赵国抵挡不住，求救于齐。齐威王拜田忌为大赵国抵挡不住，求救于齐。齐威王拜田忌为大将，孙膑为军师，发兵将，孙膑为军师，发兵8万，

7、前往救赵。万，前往救赵。 田忌田忌打算直奔邯郸速解赵国之围。孙膑提出应趁魏打算直奔邯郸速解赵国之围。孙膑提出应趁魏国国内兵力空虚之机，发兵直取魏都大梁国国内兵力空虚之机，发兵直取魏都大梁 (今河今河南开封南开封)，迫使魏军弃赵回救迫使魏军弃赵回救。|这一战略思想，既避免齐军长途奔袭的疲劳，这一战略思想，既避免齐军长途奔袭的疲劳，又致使魏军于奔波被动之中，立即为田忌采纳，又致使魏军于奔波被动之中，立即为田忌采纳，率领齐军杀往魏国都城大梁。率领齐军杀往魏国都城大梁。 | 庞涓得知大梁告急的消息，忙率大军驰援大庞涓得知大梁告急的消息，忙率大军驰援大梁。齐军事先在魏军必经之路的桂陵梁。齐军事先在魏军必

8、经之路的桂陵(今河南今河南长垣南长垣南)，占据有利地形，以逸待劳，打败了，占据有利地形，以逸待劳，打败了魏军。魏军。 这就是历史上有名的这就是历史上有名的“围魏救赵围魏救赵”之战。之战。| “围魏救赵围魏救赵”之妙，妙在善于调动敌人。调之妙，妙在善于调动敌人。调动敌人的要诀，则在动敌人的要诀，则在“攻其所必救攻其所必救”。这在。这在近代战争中的许多场合也是适用的。近代战争中的许多场合也是适用的。| 公元前公元前342年，庞涓带领年，庞涓带领10万大军进攻韩国。万大军进攻韩国。韩国向齐国求救。齐威王召集群臣商讨对策，韩国向齐国求救。齐威王召集群臣商讨对策，齐国的成侯邹忌主张不救，田忌主张早救。孙

9、齐国的成侯邹忌主张不救，田忌主张早救。孙膑建议先答应韩国的请求，致使韩国必倾力抗膑建议先答应韩国的请求，致使韩国必倾力抗敌。等到韩、魏双方战到疲惫不堪时，再出兵敌。等到韩、魏双方战到疲惫不堪时，再出兵拯救危难之中的韩国，就可以用力少而见功多，拯救危难之中的韩国，就可以用力少而见功多，取胜易而受益大。韩国仗恃有齐国相援，全力取胜易而受益大。韩国仗恃有齐国相援，全力抗魏，五战皆败，只得于公元前抗魏，五战皆败，只得于公元前341年再次向年再次向齐求助。齐威王才决定派兵救韩，仍以田忌为齐求助。齐威王才决定派兵救韩，仍以田忌为主将，孙膑为军师。主将，孙膑为军师。| 战役之初，按照孙膑的计策，齐军长驱直入

10、，战役之初，按照孙膑的计策，齐军长驱直入，把攻击的矛头指向魏国的都城大梁。魏将庞涓把攻击的矛头指向魏国的都城大梁。魏将庞涓听到消息，立即回援，但齐军已经进入魏国境听到消息，立即回援，但齐军已经进入魏国境内。孙膑对田忌说：魏国军队素来彪悍勇武而内。孙膑对田忌说：魏国军队素来彪悍勇武而看不起齐国，善于作战的人只能因势利导。兵看不起齐国，善于作战的人只能因势利导。兵法上说，行军百里与敌争利会损失上将军，行法上说，行军百里与敌争利会损失上将军，行军五十里而与敌争利只有一半人能赶到。为了军五十里而与敌争利只有一半人能赶到。为了让魏军以为齐军后退时大量掉队，应使齐军进让魏军以为齐军后退时大量掉队，应使齐军

11、进入魏国境内后先设十万个灶，过一天设五万个入魏国境内后先设十万个灶，过一天设五万个灶，再过一天设三万个灶。灶，再过一天设三万个灶。| 庞涓行军三天，见到齐军所留灶迹庞涓行军三天，见到齐军所留灶迹,判断齐军判断齐军在后退过程中士兵已经逃跑一大半，所以丢下在后退过程中士兵已经逃跑一大半，所以丢下步兵，只率轻车锐骑用加倍的速度追赶齐军。步兵，只率轻车锐骑用加倍的速度追赶齐军。 孙膑计算魏军行程，日暮时必然赶到马陵孙膑计算魏军行程，日暮时必然赶到马陵(今今河南范县西南河南范县西南)。马陵道路狭窄，两旁地形险。马陵道路狭窄，两旁地形险阻。孙膑预先布置好伏兵，并集中优秀弩手夹阻。孙膑预先布置好伏兵，并集中

12、优秀弩手夹道设伏。庞涓日暮追至马陵道设伏。庞涓日暮追至马陵,进入齐军伏击阵进入齐军伏击阵地。齐军万弩齐发，魏军大乱，庞涓兵败自刎。地。齐军万弩齐发，魏军大乱，庞涓兵败自刎。齐军乘胜全歼十万魏军。马陵之战，孙膑的因齐军乘胜全歼十万魏军。马陵之战，孙膑的因势利导、调动敌人、变劣势为优势、力争发挥势利导、调动敌人、变劣势为优势、力争发挥突然性的作战指导思想，是颇有参考价值的。突然性的作战指导思想，是颇有参考价值的。其退军设伏的战法，也给了后人不少的启示。其退军设伏的战法，也给了后人不少的启示。| “围魏救赵围魏救赵”与与“减灶之法减灶之法”都都充分体现了如何筹划兵力，选择充分体现了如何筹划兵力，选择

13、最佳时间、地点，趋利避害，集最佳时间、地点，趋利避害，集中优势兵力以弱克强的中优势兵力以弱克强的运筹运筹思想。思想。|祥符中祥符中, ,禁火。时禁火。时丁晋公丁晋公主营复宫室主营复宫室, ,患患取土远取土远, ,公乃令凿通衢公乃令凿通衢取土取土, ,不日皆成巨堑。不日皆成巨堑。乃决汴水入堑中乃决汴水入堑中, ,引诸道竹木排筏及船运引诸道竹木排筏及船运杂材杂材, ,尽自堑中入至宫门。事毕尽自堑中入至宫门。事毕, ,却以却以斥弃斥弃瓦砾灰壤实于堑中瓦砾灰壤实于堑中, ,复为街衢。一举而三复为街衢。一举而三役济役济, ,计计省费省费以亿万计。以亿万计。 沈括沈括梦溪笔谈梦溪笔谈. .补笔谈卷二补笔谈

14、卷二. .权权智智 公元前公元前354年，魏国将军庞涓发兵年，魏国将军庞涓发兵8万，万，以突袭的办法将赵国的都城邯郸包围。以突袭的办法将赵国的都城邯郸包围。 赵国抵挡不住，求救于齐。齐威王拜田赵国抵挡不住，求救于齐。齐威王拜田忌为大将，孙膑为军师，发兵忌为大将，孙膑为军师，发兵8万，前往救万，前往救赵。赵。 田忌打算直奔邯郸速解赵国之围。孙田忌打算直奔邯郸速解赵国之围。孙膑提出应趁魏国国内兵力空虚之机，发兵直膑提出应趁魏国国内兵力空虚之机，发兵直取魏都大梁取魏都大梁 (今河南开封今河南开封)，迫使魏军弃赵回迫使魏军弃赵回救救。 这一战略思想，既避免齐军长途奔袭的这一战略思想，既避免齐军长途奔袭

15、的疲劳，又致使魏军于奔波被动之中，立即为疲劳，又致使魏军于奔波被动之中，立即为田忌采纳，率领齐军杀往魏国都城大梁。田忌采纳，率领齐军杀往魏国都城大梁。 庞涓得知大梁告急的消息，忙率大军驰援庞涓得知大梁告急的消息，忙率大军驰援大梁。大梁。齐军事先在魏军必经之路的桂陵齐军事先在魏军必经之路的桂陵(今河今河南长垣南南长垣南)，占据有利地形，以逸待劳，打败占据有利地形，以逸待劳，打败了魏军了魏军。 这就是历史上有名的这就是历史上有名的“围魏救赵围魏救赵”之战。之战。 “围魏救赵围魏救赵”之妙，妙在善于调动敌人。之妙，妙在善于调动敌人。调动敌人的要诀，则在调动敌人的要诀，则在“攻其所必救攻其所必救”。这

16、在。这在近代战争中的许多场合也是适用的。近代战争中的许多场合也是适用的。 公元前公元前342年，庞涓带领年，庞涓带领10万大军进攻韩国。万大军进攻韩国。韩国向齐国求救。齐威王召集群臣商讨对策，韩国向齐国求救。齐威王召集群臣商讨对策，齐国的成侯邹忌主张齐国的成侯邹忌主张不救不救，田忌主张，田忌主张早救早救。孙。孙膑建议膑建议先答应先答应韩国的请求，致使韩国必倾力抗韩国的请求，致使韩国必倾力抗敌。等到韩、魏双方战到疲惫不堪时，敌。等到韩、魏双方战到疲惫不堪时，再出兵再出兵拯救危难之中的韩国，就可以用力少而见功多，拯救危难之中的韩国，就可以用力少而见功多，取胜易而受益大。韩国仗恃有齐国相援，全力取胜

17、易而受益大。韩国仗恃有齐国相援，全力抗魏，五战皆败，只得于公元前抗魏，五战皆败，只得于公元前341年年再次向齐再次向齐求助求助。齐威王才决定派兵救韩，仍以田忌为主。齐威王才决定派兵救韩，仍以田忌为主将，孙膑为军师。将，孙膑为军师。 战役之初，按照孙膑的计策，齐军长战役之初，按照孙膑的计策，齐军长驱直入，把攻击的驱直入，把攻击的矛头指向矛头指向魏国的都城魏国的都城大大梁梁。魏将庞涓听到消息，立即回援，但齐。魏将庞涓听到消息，立即回援，但齐军已经进入魏国境内。孙膑对田忌说：魏军已经进入魏国境内。孙膑对田忌说：魏国军队素来彪悍勇武而看不起齐国，善于国军队素来彪悍勇武而看不起齐国，善于作战的人只能作战

18、的人只能因势利导因势利导。兵法上说，行军。兵法上说，行军百里与敌争利会损失上将军，行军五十里百里与敌争利会损失上将军，行军五十里而与敌争利只有一半人能赶到。而与敌争利只有一半人能赶到。为了让魏为了让魏军以为齐军后退时大量掉队，应使齐军进军以为齐军后退时大量掉队，应使齐军进入魏国境内后先设十万个灶，过一天设五入魏国境内后先设十万个灶，过一天设五万个灶，再过一天设三万个灶。万个灶，再过一天设三万个灶。 庞涓行军三天，见到齐军所留灶迹庞涓行军三天，见到齐军所留灶迹,判判断齐军在后退过程中士兵已经逃跑一大半断齐军在后退过程中士兵已经逃跑一大半，所以丢下步兵，只率轻车锐骑用加倍的速所以丢下步兵，只率轻车

19、锐骑用加倍的速度追赶齐军。度追赶齐军。 孙膑计算魏军行程，日暮时孙膑计算魏军行程，日暮时必然赶到马陵必然赶到马陵(今河南范县西南今河南范县西南)。马陵道。马陵道路狭窄，两旁地形险阻。孙膑预先布置好路狭窄，两旁地形险阻。孙膑预先布置好伏兵，并集中优秀弩手夹道设伏。伏兵，并集中优秀弩手夹道设伏。庞涓日庞涓日暮追至马陵暮追至马陵,进入齐军伏击阵地。齐军万弩进入齐军伏击阵地。齐军万弩齐发，魏军大乱，庞涓兵败自刎。齐发，魏军大乱，庞涓兵败自刎。齐军乘齐军乘胜全歼十万魏军。马陵之战，孙膑的因势胜全歼十万魏军。马陵之战，孙膑的因势利导、调动敌人、变劣势为优势、力争发利导、调动敌人、变劣势为优势、力争发挥突然

20、性的作战指导思想，是颇有参考价挥突然性的作战指导思想，是颇有参考价值的。其值的。其退军设伏退军设伏的战法，也给了后人不的战法，也给了后人不少的启示。少的启示。 “围魏救赵围魏救赵”与与“减灶之减灶之法法”都充分体现了如何筹划都充分体现了如何筹划兵力，选择最佳时间、地点，兵力，选择最佳时间、地点，趋利避害，集中优势兵力以趋利避害，集中优势兵力以弱克强的弱克强的运筹运筹思想。思想。|据据史记史记记载：汉高祖刘邦称赞张记载：汉高祖刘邦称赞张良：夫良：夫运筹运筹策帷帐之中，决胜於千里之策帷帐之中，决胜於千里之外，吾不如子房。外，吾不如子房。 司马迁司马迁史记史记高祖本纪高祖本纪|“筹筹”是古代比算盘还

21、早的计算工具是古代比算盘还早的计算工具之一。之一。“运筹运筹”是计划、安排、比较、是计划、安排、比较、决策优化的一个过程。决策优化的一个过程。运运筹筹学学的的产产生生|当时整个世界的资源都投入到了第二次世界当时整个世界的资源都投入到了第二次世界大战中，如何才能更好地利用资源，分配有大战中，如何才能更好地利用资源，分配有限的资源，这是一个值得研究的问题。限的资源，这是一个值得研究的问题。|在英国军队中率先成立了研究小组在英国军队中率先成立了研究小组运筹运筹小组来研究这些问题，这就是著名的小组来研究这些问题，这就是著名的OR小小组组(Operational Research)很快美军中也成立很快美

22、军中也成立了了OR小组。小组。|战争战争 运筹学诞生的温床。运筹学诞生的温床。 |第二次世界大战中运筹学作为科学名字第二次世界大战中运筹学作为科学名字正式出现。正式出现。|运筹学的活动在二次世界大战初期的军事任务特别凸显，当时迫切需要把各项稀少的资源以有效的方式分配给各种不同的军事经营及在每一经营内的各项活动。|在英国军队中率先成立了研究小组在英国军队中率先成立了研究小组运筹小组来研究这些问题，这就是著名运筹小组来研究这些问题，这就是著名的的OR小组小组(Operational Research)。随。随后，美国的军事管理当局也号召大批科后，美国的军事管理当局也号召大批科学家运用科学手段来处理

23、战略与战术问学家运用科学手段来处理战略与战术问题，实际上这便是要求他们对种种（军题，实际上这便是要求他们对种种（军事）经营进行研究，这些科学家小组正事）经营进行研究，这些科学家小组正是最早的运筹小组。是最早的运筹小组。二战中成功的运筹学案例：二战中成功的运筹学案例：|英国防空部门如何布置防空雷达，建立最有效的英国防空部门如何布置防空雷达，建立最有效的防空警报系统。防空警报系统。|英，美空军如何提高对地面目标轰炸的命中率。英，美空军如何提高对地面目标轰炸的命中率。|如何安排反潜飞机的巡逻飞行线路。如何安排反潜飞机的巡逻飞行线路。|深水炸弹的合理爆炸深度，摧毁德军潜艇数增加深水炸弹的合理爆炸深度，

24、摧毁德军潜艇数增加400%400%。|商船如何编队，遭潜艇攻击时如何减少损失？使商船如何编队，遭潜艇攻击时如何减少损失？使船只受敌机攻击时，中弹数由船只受敌机攻击时，中弹数由47%47%降到降到29%29%。|这些研究大大提高了盟军的作战能力，为反法西这些研究大大提高了盟军的作战能力，为反法西斯战争的最后胜利作出了巨大的贡献！斯战争的最后胜利作出了巨大的贡献！运运筹筹学学的的产产生生 名称的由来名称的由来 Operation Research 运筹帷幄运筹帷幄 “史记史记” 运作研究运作研究 发展历程发展历程 运筹学的由来与发展:二战以前萌萌芽芽二战期间产产生生五六十年代发发展展七八十年代成成

25、熟熟运运 筹筹 学学运运 筹筹 学学运运筹筹学学定定义义|运筹学所研究的，通常是在必须分配稀缺资源的条件下，科学地决定如何最佳地设计和运营的人机系统|对象：人机系统|条件：资源稀缺|方法：模型化，定量化|特点：最优化|目的：决策支持|起源：起源：古代战争、娱乐、建设|学科产生：学科产生：第二次世界大战|问题：问题：合理利用稀缺战争资源保 护自己、消灭敌人|扩展：扩展：战后用于民用事业|成型：成型：各个分支成熟|成熟：成熟：计算机、信息技术结合|发展：发展：学科结合、渗透应用广度 和深度、方法和算法的完善概括地说：概括地说：1在数学学科中的地位在数学学科中的地位运筹数学运筹数学1在系统科学中的地

26、位在系统科学中的地位系统工程系统工程1在管理科学中的地位在管理科学中的地位管理与运筹学管理与运筹学1与经济学的关系与经济学的关系问题与方法问题与方法1与工程科学的关系与工程科学的关系方法与应用方法与应用1 与计算机科学的关系与计算机科学的关系核心算法与工具核心算法与工具运筹学的学科地位基础理论基础理论应用理论应用理论应用技术应用技术运筹学运筹学|特点：特点： 1 简化描述 2 核心描述 3 定量描述|优点：优点： 1 事前分析、减少失误 2 符号语言、便于交流 3 抽象反映实际、突出共性 确定目标，明确约束 抓主要矛盾、舍次要矛盾 选择模型、设定变量 描述约束和目标、确定参数 选择求解方法、求

27、解问题 灵敏度分析、评价 汇总、解释结果、报告 运运筹筹学学方方法法提出问题建立模型优化求解评价分析决策支持1、模型的概念、模型的概念za) 模型的定义模型的定义: 模型是一件实际事物或情况的代表或抽象。实际事物是A，若B能够真实地描述A，则称B为A的模型。zb) 运筹学模型的一般形式运筹学模型的一般形式 z ：不：不可控系统变量或环境变量可控系统变量或环境变量zF（X， ）：系统性能或有效性度量）：系统性能或有效性度量zD ：X 的可行域的可行域zX：可控系统变量或决策变量：可控系统变量或决策变量z可控变量：订货点，库存控制水平，盘可控变量：订货点，库存控制水平，盘 点周期。点周期。z不可控

28、变量：顾客到达间隔或需求。不可控变量：顾客到达间隔或需求。),.,;,.,(,(2121nmDXxxxfXF运筹学的模型方法运筹学的模型方法n一般分类：一般分类：形象模型形象模型抽象模型抽象模型l 模拟模型 数学模型 概念模型 （1） 模型的种类模型的种类n按变量的性质分类：按变量的性质分类： 确定性模型确定性模型 随机性模型随机性模型建建立立模模型型的的常常用用方方法法例:合理下料问题例:厂址选择问题例:回归模型例:排队论模型例:世界能源模型|生产管理|交通网络|存储管理|市场营销|项目评价|等等|二次大战后运筹学的应用迅速转向了民用，下面二次大战后运筹学的应用迅速转向了民用，下面对某些重要领域给于简述对某些重要领域给于简述: :|1 1、市场销售、市场销售-广告预算和媒介选择、竞争性广告预算和媒介选择、竞争性定价、新品开发、销售计划的制订定价、新品开发、销售计划的制订。（。（美）杜邦美）杜邦公司在五十年代起就非常重视将运筹学用于如何公司在五十年代起就非常重视将运筹学用于如何做好广告工作、产品定价、新品引入。做好广告工作、产品定价、新品引入。|2 2、生产计划、生产计划-从总体确定生产、存储和劳动从总体确定生产、存储和劳动力的配合等计