運(yùn)籌學(xué)運(yùn)輸問題解析 2

1、運(yùn)籌學(xué)運(yùn)輸問題解析在中國戰(zhàn)國時(shí)期，曾經(jīng)有過一次流傳后世的賽馬比賽，相信大家都知道，這就是田忌賽 馬。田忌賽馬的故事說明在已有的條件下，經(jīng)過籌劃、安排，選擇一個(gè)最好的方案，就會(huì)取 得最好的效果。可見，籌劃安排是十分重要的?，F(xiàn)在普遍認(rèn)為，運(yùn)籌學(xué)是近代應(yīng)用數(shù)學(xué)的一個(gè)分支，主要是將生產(chǎn)、管理等事件中出現(xiàn) 的一些帶有普遍性的運(yùn)籌問題加以提煉，然后利用數(shù)學(xué)方法進(jìn)行解決。前者提供模型，后者 提供理論和方法。運(yùn)籌學(xué)的思想在古代就已經(jīng)產(chǎn)生了。敵我雙方交戰(zhàn)，要克敵制勝就要在了解雙方情況的 基礎(chǔ)上，做出最優(yōu)的對(duì)付敵人的方法，這就是“運(yùn)籌帷幄之中，決勝千里之外”的說法。但是作為一門數(shù)學(xué)學(xué)科，用純數(shù)學(xué)的方法來解決最優(yōu)方

2、法的選擇安排，卻是晚多了。也 可以說，運(yùn)籌學(xué)是在二十世紀(jì)四十年代才開始興起的一門分支。運(yùn)籌學(xué)主要研究經(jīng)濟(jì)活動(dòng)和軍事活動(dòng)中能用數(shù)量來表達(dá)的有關(guān)策劃、管理方面的問題。 當(dāng)然，隨著客觀實(shí)際的發(fā)展，運(yùn)籌學(xué)的許多內(nèi)容不但研究經(jīng)濟(jì)和軍事活動(dòng)，有些已經(jīng)深入到 日常生活當(dāng)中去了。運(yùn)籌學(xué)可以根據(jù)問題的要求，通過數(shù)學(xué)上的分析、運(yùn)算，得出各種各樣 的結(jié)果，最后提出綜合性的合理安排，已達(dá)到最好的效果。運(yùn)籌學(xué)作為一門用來解決實(shí)際問題的學(xué)科，在處理千差萬別的各種問題時(shí)，一般有以下 幾個(gè)步驟：確定目標(biāo)、制定方案、建立模型、制定解法。雖然不大可能存在能處理及其廣泛對(duì)象的運(yùn)籌學(xué)，但是在運(yùn)籌學(xué)的發(fā)展過程中還是形成 了某些抽象模型

3、，并能應(yīng)用解決較廣泛的實(shí)際問題。隨著科學(xué)技術(shù)和生產(chǎn)的發(fā)展，運(yùn)籌學(xué)已滲入很多領(lǐng)域里，發(fā)揮了越來越重要的作用。運(yùn) 籌學(xué)本身也在不斷發(fā)展，現(xiàn)在已經(jīng)是一個(gè)包括好幾個(gè)分支的數(shù)學(xué)部門了。比如：數(shù)學(xué)規(guī)劃（又 包含線性規(guī)劃；非線性規(guī)劃；整數(shù)規(guī)劃；組合規(guī)劃等、圖論、網(wǎng)絡(luò)流、決策分析、排隊(duì)論、 可靠性數(shù)學(xué)理論、庫存論、對(duì)策論、搜索論、模擬等等。運(yùn)籌學(xué)有廣闊的應(yīng)用領(lǐng)域，它已滲透到諸如服務(wù)、庫存、搜索、人口、對(duì)抗、控制、時(shí) 間表、資源分配、廠址定位、能源、設(shè)計(jì)、生產(chǎn)、可靠性、等各個(gè)方面。運(yùn)籌學(xué)是軟科學(xué)中“硬度”較大的一門學(xué)科，兼有邏輯的數(shù)學(xué)和數(shù)學(xué)的邏輯的性質(zhì)，是系 統(tǒng)工程學(xué)和現(xiàn)代管理科學(xué)中的一種基礎(chǔ)理論和不可缺少的方

4、法、手段和工具。運(yùn)籌學(xué)已被應(yīng) 用到各種管理工程中，在現(xiàn)代化建設(shè)中發(fā)揮著重要作用。編輯本段運(yùn)籌學(xué)的歷史運(yùn)籌學(xué)作為一門現(xiàn)代科學(xué)，是在第二次世界大戰(zhàn)期間首先在英美兩國發(fā)展起來的，有的 學(xué)者把運(yùn)籌學(xué)描述為就組織系統(tǒng)的各種經(jīng)營作出決策的科學(xué)手段。P.M.Morse與 GEKimball在他們的奠基作中給運(yùn)籌學(xué)下的定義是：“運(yùn)籌學(xué)是在實(shí)行管理的領(lǐng)域，運(yùn)用數(shù) 學(xué)方法，對(duì)需要進(jìn)行管理的問題統(tǒng)籌規(guī)劃，作出決策的一門應(yīng)用科學(xué)?！边\(yùn)籌學(xué)的另一位創(chuàng) 始人定義運(yùn)籌學(xué)是：“管理系統(tǒng)的人為了獲得關(guān)于系統(tǒng)運(yùn)行的最優(yōu)解而必須使用的一種科學(xué) 方法?！彼褂迷S多數(shù)學(xué)工具（包括概率統(tǒng)計(jì)、數(shù)理分析、線性代數(shù)等）和邏輯判斷方法， 來研究

5、系統(tǒng)中人、財(cái)、物的組織管理、籌劃調(diào)度等問題，以期發(fā)揮最大效益?，F(xiàn)代運(yùn)籌學(xué)的起源可以追溯到幾十年前，在某些組織的管理中最先試用科學(xué)手段的時(shí) 候?？墒?，現(xiàn)在普遍認(rèn)為，運(yùn)籌學(xué)的活動(dòng)是從二次世界大戰(zhàn)初期的軍事任務(wù)開始的。當(dāng)時(shí)迫 切需要把各項(xiàng)稀少的資源以有效的方式分配給各種不同的軍事經(jīng)營及在每一經(jīng)營內(nèi)的各項(xiàng) 活動(dòng)，所以美國及隨后美國的軍事管理當(dāng)局都號(hào)召大批科學(xué)家運(yùn)用科學(xué)手段來處理戰(zhàn)略與戰(zhàn) 術(shù)問題，實(shí)際上這便是要求他們對(duì)種種（軍事）經(jīng)營進(jìn)行研究，這些科學(xué)家小組正是最早的 運(yùn)籌小組。第二次世界大戰(zhàn)期間，“OR”成功地解決了許多重要作戰(zhàn)問題，顯示了科學(xué)的巨大物質(zhì) 威力，為“OR”后來的發(fā)展鋪平了道路。當(dāng)戰(zhàn)后的

6、工業(yè)恢復(fù)繁榮時(shí)，由于組織內(nèi)與日俱增的復(fù)雜性和專門化所產(chǎn)生的問題，使人 們認(rèn)識(shí)到這些問題基本上與戰(zhàn)爭(zhēng)中所曾面臨的問題類似，只是具有不同的現(xiàn)實(shí)環(huán)境而已，運(yùn) 籌學(xué)就這樣潛入工商企業(yè)和其它部門，在50年代以后得到了廣泛的應(yīng)用。對(duì)于系統(tǒng)配置、 聚散、競(jìng)爭(zhēng)的運(yùn)用機(jī)理深入的研究和應(yīng)用，形成了比較完備的一套理論，如規(guī)劃論、排隊(duì)論、 存貯論、決策論等等，由于其理論上的成熟，電子計(jì)算機(jī)的問世，又大大促進(jìn)了運(yùn)籌學(xué)的發(fā) 展，世界上不少國家已成立了致力于該領(lǐng)域及相關(guān)活動(dòng)的專門學(xué)會(huì)，美國于1952年成立了 運(yùn)籌學(xué)會(huì)，并出版期刊運(yùn)籌學(xué)，世界其它國家也先后創(chuàng)辦了運(yùn)籌學(xué)會(huì)與期刊，1957年成 立了國際運(yùn)籌學(xué)協(xié)會(huì)。編輯本段運(yùn)籌學(xué)

7、的特點(diǎn)運(yùn)籌學(xué)的特點(diǎn)是：1.運(yùn)籌學(xué)已被廣泛應(yīng)用于工商企業(yè)、軍事部門、民政事業(yè)等研究組織 內(nèi)的統(tǒng)籌協(xié)調(diào)問題，故其應(yīng)用不受行業(yè)、部門之限制；2.運(yùn)籌學(xué)既對(duì)各種經(jīng)營進(jìn)行創(chuàng)造性的 科學(xué)研究，又涉及到組織的實(shí)際管理問題，它具有很強(qiáng)的實(shí)踐性，最終應(yīng)能向決策者提供建 設(shè)性意見，并應(yīng)收到實(shí)效；3.它以整體最優(yōu)為目標(biāo)，從系統(tǒng)的觀點(diǎn)出發(fā)，力圖以整個(gè)系統(tǒng)最 佳的方式來解決該系統(tǒng)各部門之間的利害沖突。對(duì)所研究的問題求出最優(yōu)解，尋求最佳的行 動(dòng)方案，所以它也可看成是一門優(yōu)化技術(shù)，提供的是解決各類問題的優(yōu)化方法。編輯本段運(yùn)籌學(xué)的研究方法運(yùn)籌學(xué)的研究方法有：1.從現(xiàn)實(shí)生活場(chǎng)合抽出本質(zhì)的要素來構(gòu)造數(shù)學(xué)模型，因而可尋求 一個(gè)跟決

8、策者的目標(biāo)有關(guān)的解；2.探索求解的結(jié)構(gòu)并導(dǎo)出系統(tǒng)的求解過程；3.從可行方案中 尋求系統(tǒng)的最優(yōu)解法。編輯本段運(yùn)籌學(xué)的具體內(nèi)容運(yùn)籌學(xué)的具體內(nèi)容包括：規(guī)劃論(包括線性規(guī)劃、非線性規(guī)劃、整數(shù)規(guī)劃和動(dòng)態(tài)規(guī)劃、 圖論、決策論、對(duì)策論、排隊(duì)論、存儲(chǔ)論、可靠性理論等。規(guī)劃論數(shù)學(xué)規(guī)劃即上面所說的規(guī)劃論，是運(yùn)籌學(xué)的一個(gè)重要分支，早在1939年蘇聯(lián)的康托洛 維奇(H.B.Kahtopob)和美國的希奇柯克(F.L.Hitchcock)等人就在生產(chǎn)組織管理和制定交 通運(yùn)輸方案方面首先研究和應(yīng)用一線性規(guī)劃方法。1947年旦茨格等人提出了求解線性規(guī)劃 問題的單純形方法，為線性規(guī)劃的理論與計(jì)算奠定了基礎(chǔ)，特別是電子計(jì)算機(jī)的

9、出現(xiàn)和日益 完善，更使規(guī)劃論得到迅速的發(fā)展，可用電子計(jì)算機(jī)來處理成千上萬個(gè)約束條件和變量的大 規(guī)模線性規(guī)劃問題，從解決技術(shù)問題的最優(yōu)化，到工業(yè)、農(nóng)業(yè)、商業(yè)、交通運(yùn)輸業(yè)以及決策 分析部門都可以發(fā)揮作用。從范圍來看，小到一個(gè)班組的計(jì)劃安排，大至整個(gè)部門，以至國 民經(jīng)濟(jì)計(jì)劃的最優(yōu)化方案分析，它都有用武之地，具有適應(yīng)性強(qiáng)，應(yīng)用面廣，計(jì)算技術(shù)比較 簡(jiǎn)便的特點(diǎn)。非線性規(guī)劃的基礎(chǔ)性工作則是在1951年由庫恩(H.W.Kuhn)和達(dá)克(A.W.Tucker)等人完成的，到了 70年代，數(shù)學(xué)規(guī)劃無論是在理論上和方法上，還是在應(yīng) 用的深度和廣度上都得到了進(jìn)一步的發(fā)展。數(shù)學(xué)規(guī)劃的研究對(duì)象是計(jì)劃管理工作中有關(guān)安排和估

10、值的問題，解決的主要問題是在給 定條件下，按某一衡量指標(biāo)來尋找安排的最優(yōu)方案。它可以表示成求函數(shù)在滿足約束條件下 的極大極小值問題。數(shù)學(xué)規(guī)劃和古典的求極值的問題有本質(zhì)上的不同，古典方法只能處理具有簡(jiǎn)單表達(dá)式， 和簡(jiǎn)單約束條件的情況。而現(xiàn)代的數(shù)學(xué)規(guī)劃中的問題目標(biāo)函數(shù)和約束條件都很復(fù)雜，而且要 求給出某種精確度的數(shù)字解答，因此算法的研究特別受到重視。這里最簡(jiǎn)單的一種問題就是線性規(guī)劃。如果約束條件和目標(biāo)函數(shù)都是呈線性關(guān)系的就叫 線性規(guī)劃。要解決線性規(guī)劃問題，從理論上講都要解線性方程組，因此解線性方程組的方法， 以及關(guān)于行列式、矩陣的知識(shí)，就是線性規(guī)劃中非常必要的工具。線性規(guī)劃及其解法一單純形法的出現(xiàn)

11、，對(duì)運(yùn)籌學(xué)的發(fā)展起了重大的推動(dòng)作用。許多實(shí)際 問題都可以化成線性規(guī)劃來解決，而單純形法有是一個(gè)行之有效的算法，加上計(jì)算機(jī)的出現(xiàn)， 使一些大型復(fù)雜的實(shí)際問題的解決成為現(xiàn)實(shí)。非線性規(guī)劃是線性規(guī)劃的進(jìn)一步發(fā)展和繼續(xù)。許多實(shí)際問題如設(shè)計(jì)問題、經(jīng)濟(jì)平衡問題 都屬于非線性規(guī)劃的范疇。非線性規(guī)劃擴(kuò)大了數(shù)學(xué)規(guī)劃的應(yīng)用范圍，同時(shí)也給數(shù)學(xué)工作者提 出了許多基本理論問題，使數(shù)學(xué)中的如凸分析、數(shù)值分析等也得到了發(fā)展。還有一種規(guī)劃問 題和時(shí)間有關(guān)，叫做“動(dòng)態(tài)規(guī)劃”。近年來在工程控制、技術(shù)物理和通訊中的最佳控制問題中， 已經(jīng)成為經(jīng)常使用的重要工具。圖論圖論是一個(gè)古老的但又十分活躍的分支，它是網(wǎng)絡(luò)技術(shù)的基礎(chǔ)。圖論的創(chuàng)始人是

12、數(shù)學(xué)家 歐拉。1736年他發(fā)表了圖論方面的第一篇論文，解決了著名的哥尼斯堡七橋難題，相隔一 百年后，在1847年基爾霍夫第一次應(yīng)用圖論的原理分析電網(wǎng)，從而把圖論引進(jìn)到工程技術(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)營管理等各方面越來越廣 泛的重視。排隊(duì)論排隊(duì)論又叫隨機(jī)服務(wù)系統(tǒng)理論。最初是在二十世紀(jì)初由丹麥工程師艾爾郎關(guān)于電話交換 機(jī)的效率研究開始的，在第二次世界大戰(zhàn)中為了對(duì)飛機(jī)場(chǎng)跑道的容納量進(jìn)行估算，它得到了

13、進(jìn)一步的發(fā)展，其相應(yīng)的學(xué)科更新論、可靠性理論等也都發(fā)展起來。1909年丹麥的電話工程師愛爾朗（A.K.Erlang）排隊(duì)問題，1930年以后，開始了更為 一般情況的研究，取得了一些重要成果。1949年前后，開始了對(duì)機(jī)器管理、陸空交通等方 面的研究，1951年以后，理論工作有了新的進(jìn)展，逐漸奠定了現(xiàn)代隨機(jī)服務(wù)系統(tǒng)的理論基 礎(chǔ)。排隊(duì)論主要研究各種系統(tǒng)的排隊(duì)隊(duì)長(zhǎng)，排隊(duì)的等待時(shí)間及所提供的服務(wù)等各種參數(shù)，以 便求得更好的服務(wù)。它是研究系統(tǒng)隨機(jī)聚散現(xiàn)象的理論。排隊(duì)論又叫做隨機(jī)服務(wù)系統(tǒng)理論。它的研究目的是要回答如何改進(jìn)服務(wù)機(jī)構(gòu)或組織被服 務(wù)的對(duì)象，使得某種指標(biāo)達(dá)到最優(yōu)的問題。比如一個(gè)港口應(yīng)該有多少個(gè)碼頭，

14、一個(gè)工廠應(yīng)該 有多少維修人員等。因?yàn)榕抨?duì)現(xiàn)象是一個(gè)隨機(jī)現(xiàn)象，因此在研究排隊(duì)現(xiàn)象的時(shí)候，主要采用的是研究隨機(jī)現(xiàn) 象的概率論作為主要工具。此外，還有微分和微分方程。排隊(duì)論把它所要研究的對(duì)象形象的 描述為顧客來到服務(wù)臺(tái)前要求接待。如果服務(wù)臺(tái)以被其它顧客占用，那么就要排隊(duì)。另一方 面，服務(wù)臺(tái)也時(shí)而空閑、時(shí)而忙碌。就需要通過數(shù)學(xué)方法求得顧客的等待時(shí)間、排隊(duì)長(zhǎng)度等 的概率分布。排隊(duì)論在日常生活中的應(yīng)用是相當(dāng)廣泛的，比如水庫水量的調(diào)節(jié)、生產(chǎn)流水線的安排， 鐵路分成場(chǎng)的調(diào)度、電網(wǎng)的設(shè)計(jì)等等?？煽啃岳碚摽煽啃岳碚撌茄芯肯到y(tǒng)故障、以提高系統(tǒng)可靠性問題的理論?？煽啃岳碚撗芯康南到y(tǒng)一 般分為兩類：（1）不可修系統(tǒng)：如

15、導(dǎo)彈等，這種系統(tǒng)的參數(shù)是壽命、可靠度等，（2）可修復(fù) 系統(tǒng)：如一般的機(jī)電設(shè)備等，這種系統(tǒng)的重要參數(shù)是有效度，其值為系統(tǒng)的正常工作時(shí)間與 正常工作時(shí)間加上事故修理時(shí)間之比。對(duì)策論對(duì)策論也叫博弈論，前面講的田忌賽馬就是典型的博弈論問題。作為運(yùn)籌學(xué)的一個(gè)分支， 博弈論的發(fā)展也只有幾十年的歷史。系統(tǒng)地創(chuàng)建這門學(xué)科的數(shù)學(xué)家，現(xiàn)在一般公認(rèn)為是美籍 匈牙利數(shù)學(xué)家、計(jì)算機(jī)之父一一馮諾依曼。最初用數(shù)學(xué)方法研究博弈論是在國際象棋中開始的，旨在用來如何確定取勝的算法。由 于是研究雙方?jīng)_突、制勝對(duì)策的問題，所以這門學(xué)科在軍事方面有著十分重要的應(yīng)用。近年 來，數(shù)學(xué)家還對(duì)水雷和艦艇、殲擊機(jī)和轟炸機(jī)之間的作戰(zhàn)、追蹤等問題進(jìn)

16、行了研究，提出了 追逃雙方都能自主決策的數(shù)學(xué)理論。近年來，隨著人工智能研究的進(jìn)一步發(fā)展，對(duì)博弈論提 出了更多新的要求。決策論研究決策問題。所謂決策就是根據(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)則劃分成 的種種決策問題類型。不同類型的決策問題應(yīng)采用不同的決策方法。決策的基本步驟為：（1） 確定問題，提出決策的目標(biāo)；（2）發(fā)現(xiàn)、探索和擬定各種可行方案；（3）從多種可行方案中， 選出最滿意的方案；（4）決策的執(zhí)行與反饋，以尋求決策的動(dòng)態(tài)最優(yōu)。如果決策者的對(duì)方也是人（一個(gè)人或一群人）雙方都希望取勝，這類具有競(jìng)爭(zhēng)性的決策 稱為對(duì)策或博弈型決策。構(gòu)成對(duì)策問題的三個(gè)根本要素是：局中人、策略與一局對(duì)策的得失。 目前對(duì)