項(xiàng)目一　運(yùn)籌學(xué)概述

1.1　運(yùn)籌學(xué)的產(chǎn)生與發(fā)展

任何一門學(xué)科或理論都是為解決一些客觀實(shí)際問題而出現(xiàn)并得以發(fā)展的，為了更好地理解和掌握今天的運(yùn)籌學(xué)，有必要先了解一下運(yùn)籌學(xué)發(fā)展的歷史。雖然一定的運(yùn)籌學(xué)思想和方法在很久以前已留下了被應(yīng)用的痕跡，歷代先驅(qū)所做的一些工作今天看來也具有一定的運(yùn)籌學(xué)性質(zhì)，但這些零散的活動(dòng)還不足以標(biāo)志作為系統(tǒng)知識(shí)體系的一門新學(xué)科的誕生。運(yùn)籌學(xué)的產(chǎn)生很難有一個(gè)明確的時(shí)間界定，目前國際上公認(rèn)的觀點(diǎn)是運(yùn)籌學(xué)產(chǎn)生于第二次世界大戰(zhàn)前后。1937年，英國部分科學(xué)家被邀請(qǐng)去幫助皇家空軍研究雷達(dá)的部署和運(yùn)作問題，目的在于最大限度地發(fā)揮有限雷達(dá)的效用，以應(yīng)對(duì)德軍的空襲。1938年，波德塞（Bawdsey）雷達(dá)站的負(fù)責(zé)人羅伊（A．B．Rowe）提出了優(yōu)化防空作戰(zhàn)系統(tǒng)運(yùn)行的問題，并用“operational research”一詞作為對(duì)這一方面研究的描述，這就是直至今日我們?nèi)匀粚⑦\(yùn)籌學(xué)稱為“O．R．”的歷史由來。1939年，從事此方面問題研究的科學(xué)家被召集到英國皇家空軍指揮總部，成立了一個(gè)由布萊開特（P．M．S．Blacket）領(lǐng)導(dǎo)的軍事科技攻關(guān)小組；由于其成員學(xué)科性質(zhì)的多樣性，這一最早成立的軍事科技攻關(guān)小組被戲稱為“布萊開特馬戲團(tuán)”。由于“布萊開特馬戲團(tuán)”的活動(dòng)是第一次有組織的、系統(tǒng)的運(yùn)籌學(xué)活動(dòng)，所以后人將該小組的成立作為運(yùn)籌學(xué)產(chǎn)生的標(biāo)志。此后，O．R．小組的活動(dòng)范圍不斷擴(kuò)大，從最初僅限于空軍，逐步擴(kuò)展到海軍和陸軍；研究內(nèi)容也從對(duì)軍事戰(zhàn)術(shù)性問題的研究，逐步擴(kuò)展到對(duì)軍事戰(zhàn)略性問題的研究。由于科學(xué)家的天賦、戰(zhàn)爭的需要以及不同學(xué)科的交互作用，這一軍事科技攻關(guān)小組在提高軍事運(yùn)籌水平方面取得了驚人的成就，這使得運(yùn)籌學(xué)在整個(gè)軍事領(lǐng)域迅速傳播，到1941年，英國皇家陸、海、空三軍都成立了這樣的科學(xué)小組。比較典型的論題包括雷達(dá)布置策略、反空襲系統(tǒng)控制、海軍艦隊(duì)的編制和對(duì)敵潛艇的探測(cè)等，O．R．小組的巨大成就所顯示出的神奇力量，促使其他盟軍也紛紛效仿，建立了自己的研究小組。以美國為代表的一些英語國家稱這類研究小組的工作為“operations research”。

二戰(zhàn)后，許多從事運(yùn)籌小組活動(dòng)的科學(xué)家將其精力轉(zhuǎn)向?qū)υ缙趥}促建立起來的運(yùn)籌優(yōu)化技術(shù)進(jìn)行加工整理，探索應(yīng)用運(yùn)籌學(xué)思想和方法解決社會(huì)經(jīng)濟(jì)問題的可能性。首先接納運(yùn)籌學(xué)的非軍事組織是一些效益較好的大公司，如石油公司和汽車公司。“大商業(yè)”引領(lǐng)運(yùn)籌學(xué)應(yīng)用的新潮流是很自然的事，因?yàn)殡m然當(dāng)時(shí)運(yùn)籌學(xué)可以為任何一個(gè)經(jīng)濟(jì)組織提供獲得競(jìng)爭優(yōu)勢(shì)的方案，但由于運(yùn)籌學(xué)還處于起步的基礎(chǔ)研究時(shí)期，只有大公司才能承擔(dān)起運(yùn)籌學(xué)研究的巨大費(fèi)用。后來，隨著運(yùn)籌學(xué)思想和方法的積累與程序化，不用太大的投入就能受益，運(yùn)籌學(xué)才得到了廣泛的應(yīng)用。計(jì)算機(jī)的普及與發(fā)展是推動(dòng)運(yùn)籌學(xué)迅速發(fā)展的巨大動(dòng)力，沒有現(xiàn)代計(jì)算機(jī)技術(shù)，求解復(fù)雜的運(yùn)籌學(xué)模型是不可設(shè)想的，也是不實(shí)際的；運(yùn)籌學(xué)實(shí)踐反過來又促進(jìn)了計(jì)算機(jī)技術(shù)的發(fā)展，它不斷地對(duì)計(jì)算機(jī)提出更大內(nèi)存、更快運(yùn)行速度的要求。可以說，運(yùn)籌學(xué)在過去的半個(gè)多世紀(jì)里，既得益于計(jì)算機(jī)技術(shù)的應(yīng)用與發(fā)展，同時(shí)也極大地促進(jìn)了計(jì)算機(jī)技術(shù)的發(fā)展。

20世紀(jì)50年代，運(yùn)籌學(xué)理論、方法及其活動(dòng)發(fā)展到了一個(gè)新的水平，運(yùn)籌學(xué)開始成為一門獨(dú)立的學(xué)科，其標(biāo)志是大量運(yùn)籌學(xué)學(xué)會(huì)的創(chuàng)建和相應(yīng)期刊的問世。繼1948年英國創(chuàng)立運(yùn)籌學(xué)學(xué)會(huì)之后，美國運(yùn)籌學(xué)學(xué)會(huì)于1952年成立，它的宗旨是滿足運(yùn)籌學(xué)研究領(lǐng)域的科學(xué)家相互交流的需要，以促進(jìn)O．R．理論與實(shí)踐的發(fā)展。1953年，美國又成立了管理科學(xué)研究所。美國運(yùn)籌學(xué)學(xué)會(huì)和管理科學(xué)研究所兩個(gè)組織所創(chuàng)辦的刊物《運(yùn)籌學(xué)》和《管理科學(xué)》將許多零散的研究成果系統(tǒng)化，為構(gòu)建運(yùn)籌學(xué)新學(xué)科的知識(shí)體系作出了突出的貢獻(xiàn)。在1956年至1959年短短的幾年里，先后就有法國、印度、日本等十幾個(gè)國家成立了運(yùn)籌學(xué)學(xué)會(huì)，并有6種運(yùn)籌學(xué)期刊問世。1957年，在英國牛津大學(xué)召開了第一屆運(yùn)籌學(xué)國際會(huì)議，1959年，成立了國際運(yùn)籌學(xué)學(xué)會(huì)（International Federation of Operations Research Societies，IFORS）。截至1986年，國際上已有38個(gè)國家和地區(qū)成立了運(yùn)籌學(xué)學(xué)會(huì)或類似的組織。

20世紀(jì)60年代以來，運(yùn)籌學(xué)得到了迅速的普及和發(fā)展。運(yùn)籌學(xué)細(xì)分為許多分支，許多高等院校把運(yùn)籌學(xué)的規(guī)劃理論引入教學(xué)課程，把規(guī)劃理論以外的內(nèi)容引入碩士、博士研究生的教學(xué)課程。運(yùn)籌學(xué)的學(xué)科劃分沒有統(tǒng)一的標(biāo)準(zhǔn)，在工科學(xué)院、商學(xué)院、經(jīng)濟(jì)學(xué)院和數(shù)理學(xué)院的教學(xué)中都可以發(fā)現(xiàn)它的存在。

1.2　我國古代運(yùn)籌學(xué)應(yīng)用案例

運(yùn)籌學(xué)作為科學(xué)概念是在20世紀(jì)中期提出來的，而運(yùn)籌學(xué)思想可以追溯到很久以前。我國蜀漢時(shí)期即有所謂“夫運(yùn)籌帷幄之中，決勝千里之外”的說法，充分體現(xiàn)了我國古代人民對(duì)于運(yùn)籌學(xué)的分支“預(yù)測(cè)和規(guī)劃論”的重視。秦始皇派蒙恬大軍抗擊匈奴時(shí)，從山東每調(diào)運(yùn)192石糧草只有1石能到達(dá)在沙漠中與匈奴作戰(zhàn)的將士手中；而清朝乾隆平息噶爾丹叛亂時(shí)，從江南每調(diào)運(yùn)12石糧草就有1石糧草能到達(dá)在大漠中與噶爾丹叛軍作戰(zhàn)的將士手中，這與運(yùn)籌實(shí)踐水平的提高是分不開的。

我國古代的能人志士有許多采用運(yùn)籌學(xué)思想指導(dǎo)實(shí)踐的案例，至今對(duì)我們?nèi)杂泻芎玫慕梃b作用。

1.2.1　丁謂修宮，一舉而三役濟(jì)

宋真宗大中祥符年間，宮內(nèi)失火，燒毀了大片宮殿、樓閣、涼亭和臺(tái)榭。宋真宗任命晉國公丁謂負(fù)責(zé)修復(fù)這些建筑。該建筑工程需要解決三個(gè)難題：一是取土困難，因?yàn)橐浇紖^(qū)去取土，路途太遠(yuǎn)；二是與此相關(guān)的運(yùn)輸問題難以解決，包括運(yùn)土和運(yùn)輸大量其他建筑材料；三是大量建筑垃圾的處理。丁謂運(yùn)籌規(guī)劃，終于制定了絕妙的施工方案。首先下令“鑿?fù)ㄡ槿⊥痢保靡越鉀Q施工用土問題；然后引汴水入新挖的大溝，“引諸道竹木筏排及船運(yùn)雜材，盡自塹中入至宮門”，從而解決了大批木材、石料的運(yùn)輸問題；最后待建筑運(yùn)輸任務(wù)完成之后，再排除塹水，把工地所有垃圾倒入溝內(nèi)，重新填為平地。該方案的三個(gè)過程為：挖溝并取土—引水入溝并運(yùn)輸—填溝并處理垃圾。此方案“一舉而三役濟(jì)”“省費(fèi)以億萬計(jì)”，大大縮短了工期。丁謂所設(shè)計(jì)的方案，其思想與如今運(yùn)籌學(xué)中的統(tǒng)籌方法一致。

1.2.2　田忌賽馬

戰(zhàn)國初期，齊國的君主要求田忌和他賽馬，規(guī)定各人從自己的上馬（即頭等馬）、中馬、下馬中各選一匹馬來比賽，并且說好每輸一匹馬就得支付一千兩銀子給獲勝者。當(dāng)時(shí)齊王的馬比田忌的馬強(qiáng)，結(jié)果每年田忌都要輸?shù)羧摄y子。孫臏給田忌出主意：上馬雖不及齊王的上馬，但卻強(qiáng)于齊王的中馬，因此用上馬與齊王的中馬比賽，同理用中馬與齊王的下馬比賽，而用下馬與齊王的上馬比賽。結(jié)果田忌反而贏得了一千兩銀子。田忌所用的策略就是如今運(yùn)籌學(xué)中對(duì)策論的策略。

上述案例說明，從古代開始，我國就已經(jīng)擁有了樸素的運(yùn)籌學(xué)思想。

1.3　我國現(xiàn)代對(duì)運(yùn)籌學(xué)的認(rèn)識(shí)和應(yīng)用

運(yùn)籌學(xué)概念起源于歐美，在學(xué)科研究方面，歐美的水平也明顯領(lǐng)先于我國。但我國的科學(xué)工作者們并不氣餒，他們用自己的聰明才智和努力工作使運(yùn)籌學(xué)的思想得以在全國普及，并指導(dǎo)人們的實(shí)踐。1955年，運(yùn)籌學(xué)的思想開始為我國科學(xué)工作者所認(rèn)識(shí)，1956年中國科學(xué)院力學(xué)研究所建立了我國第一個(gè)運(yùn)籌學(xué)研究組。20世紀(jì)60年代，華羅庚教授親自指導(dǎo)青年科技工作者在全國推廣運(yùn)籌學(xué)方法。華羅庚的“優(yōu)選法”和“統(tǒng)籌方法”被各部門采用，取得了很好的效果。楊紀(jì)珂教授親自帶領(lǐng)學(xué)生深入廠礦企業(yè)，推廣應(yīng)用“質(zhì)量控制”技術(shù)，也取得了很好的效果，受到各界的好評(píng)。更重要的是，他們還為管理人員編寫了通俗易懂的普及性讀物，讓更多的人學(xué)習(xí)和運(yùn)用運(yùn)籌學(xué)方法，使得運(yùn)籌學(xué)的思想得以普及。

改革開放以來，運(yùn)籌學(xué)的應(yīng)用更為普遍，特別是在流通領(lǐng)域中。例如，運(yùn)用線性規(guī)劃進(jìn)行全國范圍的糧食、鋼材，廣東水泥的合理調(diào)運(yùn)等：許多企業(yè)在作業(yè)調(diào)配、工序安排、場(chǎng)地選擇時(shí)，創(chuàng)造性地使用了簡單易行的“圖上作業(yè)法”和“表上作業(yè)法”等運(yùn)籌學(xué)方法，取得了顯著的效果。

1.4　運(yùn)籌學(xué)的主要研究方向

運(yùn)籌學(xué)（operation research）也稱為作業(yè)研究，是運(yùn)用系統(tǒng)化的方法，通過建立數(shù)學(xué)模型及其測(cè)試，協(xié)助達(dá)成最佳決策的一門學(xué)科。它主要研究經(jīng)濟(jì)活動(dòng)和軍事活動(dòng)中能用數(shù)量來表達(dá)的有關(guān)運(yùn)用、籌劃與管理等方面的問題。它根據(jù)問題的要求，通過數(shù)學(xué)的分析與運(yùn)算，做出綜合性的合理安排，以達(dá)到更加經(jīng)濟(jì)、有效地配置人力、物力、財(cái)力等資源的目的。

運(yùn)籌學(xué)的主要分支有規(guī)劃論、圖論、網(wǎng)絡(luò)分析、存儲(chǔ)論、對(duì)策論和預(yù)測(cè)技術(shù)等，它們?cè)诠芾韺W(xué)科中得到了廣泛的應(yīng)用。

1.4.1　規(guī)劃論（programming theory）

在生產(chǎn)和經(jīng)營管理工作中，經(jīng)常要研究計(jì)劃管理工作中有關(guān)安排和估計(jì)的問題，特別是如何有效地利用有限的人力、財(cái)力和物力來取得最優(yōu)的經(jīng)濟(jì)效果。這類問題一般可以歸納為在滿足既定的要求下，按某一衡量指標(biāo)來尋求最優(yōu)方案的問題。這類問題其實(shí)就是規(guī)劃問題。

如果問題的目標(biāo)函數(shù)和約束條件的數(shù)學(xué)表達(dá)式都是線性的，則稱為“線性規(guī)劃”（linear programming）問題。“線性規(guī)劃”問題只有一個(gè)目標(biāo)函數(shù)，其建模相對(duì)簡單，有通用的算法和計(jì)算機(jī)軟件。用線性規(guī)劃可以解決的典型問題有生產(chǎn)計(jì)劃問題、混合配料問題、下料問題和運(yùn)輸問題等。

如果問題的目標(biāo)函數(shù)和約束條件的數(shù)學(xué)表達(dá)式不都是線性的，則稱為“非線性規(guī)劃”（nonlinear programming）問題。非線性規(guī)劃在很多工程問題的優(yōu)化設(shè)計(jì)中具有重要作用，是優(yōu)化設(shè)計(jì)的有力工具。

如果所考慮的規(guī)劃問題可劃分為幾個(gè)階段求解，則稱為“動(dòng)態(tài)規(guī)劃”（dynamic programming）問題。動(dòng)態(tài)規(guī)劃問題也有目標(biāo)函數(shù)和約束條件。該方法根據(jù)多階段決策問題的特點(diǎn)，提出了多階段決策問題的最優(yōu)性原理，可以解決生產(chǎn)管理和工程技術(shù)等領(lǐng)域中的許多實(shí)際問題，如最優(yōu)路徑問題、資源分配問題、生產(chǎn)計(jì)劃問題和庫存問題等。

1.4.2　圖論和網(wǎng)絡(luò)分析（graph theory and network analysis）

圖論是運(yùn)籌學(xué)一個(gè)古老但又十分活躍的分支，它是網(wǎng)絡(luò)技術(shù)的基礎(chǔ)。圖論的創(chuàng)始人是數(shù)學(xué)家歐拉。1736年他發(fā)表了圖論方面的第一篇論文，解決了著名的哥尼斯堡七橋難題。1847年基爾霍夫第一次應(yīng)用圖論的原理分析電網(wǎng)，從而把圖論引入工程技術(shù)領(lǐng)域。20世紀(jì)50年代以來，圖論的理論得到了進(jìn)一步發(fā)展，用圖描述復(fù)雜、龐大的工程系統(tǒng)和管理問題，可以解決很多工程設(shè)計(jì)和管理決策的最優(yōu)化問題。例如，完成工程任務(wù)的時(shí)間最少、距離最短、費(fèi)用最省等等。因此，圖論受到數(shù)學(xué)、工程技術(shù)和經(jīng)營管理等方面越來越廣泛的重視。

生產(chǎn)管理中經(jīng)常會(huì)遇到線路的合理銜接搭配、管道線路的通過能力、倉儲(chǔ)設(shè)施的布局等問題。在運(yùn)籌學(xué)中，可將這些問題抽象為節(jié)點(diǎn)、邊（弧）所組成的圖形問題。網(wǎng)絡(luò)分析就是根據(jù)所研究的網(wǎng)絡(luò)對(duì)象，賦予圖中各邊某個(gè)具體參數(shù)，如時(shí)間、流量、費(fèi)用、距離等，規(guī)定圖中節(jié)點(diǎn)為流動(dòng)的始點(diǎn)、中轉(zhuǎn)點(diǎn)和終點(diǎn)，然后進(jìn)行網(wǎng)絡(luò)流量的分析和優(yōu)化。

1.4.3　存儲(chǔ)論（inventory theory）

存儲(chǔ)論是一種研究最優(yōu)存儲(chǔ)策略的理論和方法。在實(shí)際生產(chǎn)實(shí)踐過程中，企業(yè)希望盡可能減少原材料和產(chǎn)成品的存儲(chǔ)以減少流動(dòng)資金和倉儲(chǔ)費(fèi)用。但是，過少的原材料倉儲(chǔ)可能導(dǎo)致企業(yè)原材料供應(yīng)不上，從而導(dǎo)致生產(chǎn)不能正常進(jìn)行；過少的產(chǎn)成品存儲(chǔ)則可能導(dǎo)致客戶不能得到足夠的商品，從而導(dǎo)致客戶忠誠度的下降。存儲(chǔ)論就是研究在不同需求、供貨及到達(dá)方式等情況下，在什么時(shí)間點(diǎn)及一次提出多大批量的訂貨，使用于訂購、存儲(chǔ)和可能發(fā)生短缺的費(fèi)用的總和最少。

1.4.4　排隊(duì)論（queueing theory）

排隊(duì)論又稱為隨機(jī)服務(wù)系統(tǒng)理論。1909年丹麥的電話工程師愛爾朗（A．K．Erlang）提出了排隊(duì)問題；1930年以后，開始了更為一般的研究，取得了一些重要成果；1949年前后，開始了對(duì)機(jī)器管理、陸空交通等方面的研究；1951年以后，理論研究工作有了新的進(jìn)展，逐漸奠定了現(xiàn)代隨機(jī)服務(wù)系統(tǒng)的理論基礎(chǔ)。排隊(duì)論主要研究各種系統(tǒng)的排隊(duì)隊(duì)長、排隊(duì)的等待時(shí)間及所提供的服務(wù)等各種參數(shù)，以便獲得更好的服務(wù)。排隊(duì)論是研究系統(tǒng)隨機(jī)聚散現(xiàn)象的理論。

1.4.5　對(duì)策論（game theory）

對(duì)策論研究有關(guān)決策的問題。所謂決策，就是根據(jù)客觀可能性，借助一定的理論、方法和工具，科學(xué)地選擇最優(yōu)方案的過程，決策問題由決策者和決策域構(gòu)成，而決策域又由決策空間、狀態(tài)空間和結(jié)果函數(shù)構(gòu)成。研究決策理論與方法的科學(xué)就是決策科學(xué)。決策所要解決的問題是多種多樣的，從不同角度有不同的分類方法。按決策者所面臨的自然狀態(tài)的確定與否可分為：確定型決策、風(fēng)險(xiǎn)型決策和不確定型決策；按決策所依據(jù)的目標(biāo)個(gè)數(shù)可分為：單目標(biāo)決策與多目標(biāo)決策；按決策問題的性質(zhì)可分為：戰(zhàn)略決策和策略決策；以及按不同準(zhǔn)則劃分成的其他決策問題類型。

1.4.6　預(yù)測(cè)論（forecast theory）

預(yù)測(cè)是在科學(xué)理論的指導(dǎo)下做出有一定科學(xué)依據(jù)的假定。常見的預(yù)測(cè)方法有時(shí)間序列預(yù)測(cè)法和回歸模型預(yù)測(cè)法兩種。

1.5　運(yùn)籌學(xué)的工作步驟

運(yùn)籌學(xué)作為解決有限資源合理利用問題的系統(tǒng)的科學(xué)方法，具有其固有的工作步驟，現(xiàn)將這一步驟概括如下。

（1）提出和形成問題：即要弄清問題的目標(biāo)、可能的約束、可控變量、有關(guān)的參數(shù)以及搜集有關(guān)信息資料。

（2）建立模型：即把問題中的決策變量、參數(shù)和目標(biāo)、約束之間的關(guān)系用一定的模型表示出來。

（3）求解模型：根據(jù)模型的性質(zhì)，選擇相應(yīng)的求解方法，求得最優(yōu)或滿意解，解的精度要求可由決策者提出。

（4）解的檢驗(yàn)與轉(zhuǎn)譯：首先檢查求解過程是否有誤，然后再檢查解是否反映客觀實(shí)際。如果所得之解不能較好地反映實(shí)際問題，必須返回（1）修改模型，重新求解；如果所得之解能較好地反映實(shí)際問題，也必須仔細(xì)將模型結(jié)論轉(zhuǎn)譯成現(xiàn)實(shí)結(jié)論。

（5）解的實(shí)施：實(shí)施過程必須考慮解的應(yīng)用范圍及對(duì)各主要因素的敏感程度，向決策者講清解的用法以及在實(shí)施中可能產(chǎn)生的問題和修改的方法。