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

運(yùn)籌學(xué)運(yùn)輸問(wèn)題解析在中國(guó)戰(zhàn)國(guó)時(shí)期,曾經(jīng)有過(guò)一次流傳后世的賽馬比賽,相信大家都知道,這就是田忌賽馬。田忌賽馬的故事說(shuō)明在已有的條件下,經(jīng)過(guò)籌劃、安排,選擇一個(gè)最好的方案,就會(huì)取得最好的效果。可見(jiàn),籌劃安排是十分重要的?，F(xiàn)在普遍認(rèn)為,運(yùn)籌學(xué)是近代應(yīng)用數(shù)學(xué)的一個(gè)分支,主要是將生產(chǎn)、管理等事件中出現(xiàn)的一些帶有普遍性的運(yùn)籌問(wèn)題加以提煉,然后利用數(shù)學(xué)方法進(jìn)行解決。前者提供模型,后者提供理論和方法。運(yùn)籌學(xué)的思想在古代就已經(jīng)產(chǎn)生了。敵我雙方交戰(zhàn),要克敵制勝就要在了解雙方情況的基礎(chǔ)上,做出最優(yōu)的對(duì)付敵人的方法,這就是“運(yùn)籌帷幄之中,決勝千里之外”的說(shuō)法。但是作為一門(mén)數(shù)學(xué)學(xué)科,用純數(shù)學(xué)的方法來(lái)解決最優(yōu)方法的選擇安排,卻是晚多了。也可以說(shuō),運(yùn)籌學(xué)是在二十世紀(jì)四十年代才開(kāi)始興起的一門(mén)分支。運(yùn)籌學(xué)主要研究經(jīng)濟(jì)活動(dòng)和軍事活動(dòng)中能用數(shù)量來(lái)表達(dá)的有關(guān)策劃、管理方面的問(wèn)題。當(dāng)然,隨著客觀實(shí)際的發(fā)展,運(yùn)籌學(xué)的許多內(nèi)容不但研究經(jīng)濟(jì)和軍事活動(dòng),有些已經(jīng)深入到日常生活當(dāng)中去了。運(yùn)籌學(xué)可以根據(jù)問(wèn)題的要求,通過(guò)數(shù)學(xué)上的分析、運(yùn)算,得出各種各樣的結(jié)果,最后提出綜合性的合理安排,已達(dá)到最好的效果。運(yùn)籌學(xué)作為一門(mén)用來(lái)解決實(shí)際問(wèn)題的學(xué)科,在處理千差萬(wàn)別的各種問(wèn)題時(shí),一般有以下幾個(gè)步驟:確定目標(biāo)、制定方案、建立模型、制定解法。雖然不大可能存在能處理及其廣泛對(duì)象的運(yùn)籌學(xué),但是在運(yùn)籌學(xué)的發(fā)展過(guò)程中還是形成了某些抽象模型,并能應(yīng)用解決較廣泛的實(shí)際問(wèn)題。隨著科學(xué)技術(shù)和生產(chǎn)的發(fā)展,運(yùn)籌學(xué)已滲入很多領(lǐng)域里,發(fā)揮了越來(lái)越重要的作用。運(yùn)籌學(xué)本身也在不斷發(fā)展,現(xiàn)在已經(jīng)是一個(gè)包括好幾個(gè)分支的數(shù)學(xué)部門(mén)了。比如:數(shù)學(xué)規(guī)劃(又包含線性規(guī)劃;非線性規(guī)劃;整數(shù)規(guī)劃;組合規(guī)劃等、圖論、網(wǎng)絡(luò)流、決策分析、排隊(duì)論、可靠性數(shù)學(xué)理論、庫(kù)存論、對(duì)策論、搜索論、模擬等等。運(yùn)籌學(xué)有廣闊的應(yīng)用領(lǐng)域,它已滲透到諸如服務(wù)、庫(kù)存、搜索、人口、對(duì)抗、控制、時(shí)間表、資源分配、廠址定位、能源、設(shè)計(jì)、生產(chǎn)、可靠性、等各個(gè)方面。運(yùn)籌學(xué)是軟科學(xué)中“硬度”較大的一門(mén)學(xué)科,兼有邏輯的數(shù)學(xué)和數(shù)學(xué)的邏輯的性質(zhì),是系統(tǒng)工程學(xué)和現(xiàn)代管理科學(xué)中的一種基礎(chǔ)理論和不可缺少的方法、手段和工具。運(yùn)籌學(xué)已被應(yīng)用到各種管理工程中,在現(xiàn)代化建設(shè)中發(fā)揮著重要作用。[編輯本段]運(yùn)籌學(xué)的歷史運(yùn)籌學(xué)作為一門(mén)現(xiàn)代科學(xué),是在第二次世界大戰(zhàn)期間首先在英美兩國(guó)發(fā)展起來(lái)的,有的學(xué)者把運(yùn)籌學(xué)描述為就組織系統(tǒng)的各種經(jīng)營(yíng)作出決策的科學(xué)手段。P.M.Morse與G.E.Kimball在他們的奠基作中給運(yùn)籌學(xué)下的定義是:“運(yùn)籌學(xué)是在實(shí)行管理的領(lǐng)域,運(yùn)用數(shù)學(xué)方法,對(duì)需要進(jìn)行管理的問(wèn)題統(tǒng)籌規(guī)劃,作出決策的一門(mén)應(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ù)等和邏輯判斷方法,來(lái)研究系統(tǒng)中人、財(cái)、物的組織管理、籌劃調(diào)度等問(wèn)題,以期發(fā)揮最大效益?，F(xiàn)代運(yùn)籌學(xué)的起源可以追溯到幾十年前,在某些組織的管理中最先試用科學(xué)手段的時(shí)候?？墒?現(xiàn)在普遍認(rèn)為,運(yùn)籌學(xué)的活動(dòng)是從二次世界大戰(zhàn)初期的軍事任務(wù)開(kāi)始的。當(dāng)時(shí)迫切需要把各項(xiàng)稀少的資源以有效的方式分配給各種不同的軍事經(jīng)營(yíng)及在每一經(jīng)營(yíng)內(nèi)的各項(xiàng)活動(dòng),所以美國(guó)及隨后美國(guó)的軍事管理當(dāng)局都號(hào)召大批科學(xué)家運(yùn)用科學(xué)手段來(lái)處理戰(zhàn)略與戰(zhàn)術(shù)問(wèn)題,實(shí)際上這便是要求他們對(duì)種種(軍事經(jīng)營(yíng)進(jìn)行研究,這些科學(xué)家小組正是最早的運(yùn)籌小組。第二次世界大戰(zhàn)期間,“OR”成功地解決了許多重要作戰(zhàn)問(wèn)題,顯示了科學(xué)的巨大物質(zhì)威力,為“OR”后來(lái)的發(fā)展鋪平了道路。當(dāng)戰(zhàn)后的工業(yè)恢復(fù)繁榮時(shí),由于組織內(nèi)與日俱增的復(fù)雜性和專(zhuān)門(mén)化所產(chǎn)生的問(wèn)題,使人們認(rèn)識(shí)到這些問(wèn)題基本上與戰(zhàn)爭(zhēng)中所曾面臨的問(wèn)題類(lèi)似,只是具有不同的現(xiàn)實(shí)環(huán)境而已,運(yùn)籌學(xué)就這樣潛入工商企業(yè)和其它部門(mén),在50年代以后得到了廣泛的應(yīng)用。對(duì)于系統(tǒng)配置、聚散、競(jìng)爭(zhēng)的運(yùn)用機(jī)理深入的研究和應(yīng)用,形成了比較完備的一套理論,如規(guī)劃論、排隊(duì)論、存貯論、決策論等等,由于其理論上的成熟,電子計(jì)算機(jī)的問(wèn)世,又大大促進(jìn)了運(yùn)籌學(xué)的發(fā)展,世界上不少?lài)?guó)家已成立了致力于該領(lǐng)域及相關(guān)活動(dòng)的專(zhuān)門(mén)學(xué)會(huì),美國(guó)于1952年成立了運(yùn)籌學(xué)會(huì),并出版期刊《運(yùn)籌學(xué)》,世界其它國(guó)家也先后創(chuàng)辦了運(yùn)籌學(xué)會(huì)與期刊,1957年成立了國(guó)際運(yùn)籌學(xué)協(xié)會(huì)。[編輯本段]運(yùn)籌學(xué)的特點(diǎn)運(yùn)籌學(xué)的特點(diǎn)是:1.運(yùn)籌學(xué)已被廣泛應(yīng)用于工商企業(yè)、軍事部門(mén)、民政事業(yè)等研究組織內(nèi)的統(tǒng)籌協(xié)調(diào)問(wèn)題,故其應(yīng)用不受行業(yè)、部門(mén)之限制;2.運(yùn)籌學(xué)既對(duì)各種經(jīng)營(yíng)進(jìn)行創(chuàng)造性的科學(xué)研究,又涉及到組織的實(shí)際管理問(wèn)題,它具有很強(qiáng)的實(shí)踐性,最終應(yīng)能向決策者提供建設(shè)性意見(jiàn),并應(yīng)收到實(shí)效;3.它以整體最優(yōu)為目標(biāo),從系統(tǒng)的觀點(diǎn)出發(fā),力圖以整個(gè)系統(tǒng)最佳的方式來(lái)解決該系統(tǒng)各部門(mén)之間的利害沖突。對(duì)所研究的問(wèn)題求出最優(yōu)解,尋求最佳的行動(dòng)方案,所以它也可看成是一門(mén)優(yōu)化技術(shù),提供的是解決各類(lèi)問(wèn)題的優(yōu)化方法。[編輯本段]運(yùn)籌學(xué)的研究方法運(yùn)籌學(xué)的研究方法有:1.從現(xiàn)實(shí)生活場(chǎng)合抽出本質(zhì)的要素來(lái)構(gòu)造數(shù)學(xué)模型,因而可尋求一個(gè)跟決策者的目標(biāo)有關(guān)的解;2.探索求解的結(jié)構(gòu)并導(dǎo)出系統(tǒng)的求解過(guò)程;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ī)劃即上面所說(shuō)的規(guī)劃論,是運(yùn)籌學(xué)的一個(gè)重要分支,早在1939年蘇聯(lián)的康托洛維奇(H.B.Kahtopob和美國(guó)的希奇柯克(F.L.Hitchcock等人就在生產(chǎn)組織管理和制定交通運(yùn)輸方案方面首先研究和應(yīng)用一線性規(guī)劃方法。1947年旦茨格等人提出了求解線性規(guī)劃問(wèn)題的單純形方法,為線性規(guī)劃的理論與計(jì)算奠定了基礎(chǔ),特別是電子計(jì)算機(jī)的出現(xiàn)和日益完善,更使規(guī)劃論得到迅速的發(fā)展,可用電子計(jì)算機(jī)來(lái)處理成千上萬(wàn)個(gè)約束條件和變量的大規(guī)模線性規(guī)劃問(wèn)題,從解決技術(shù)問(wèn)題的最優(yōu)化,到工業(yè)、農(nóng)業(yè)、商業(yè)、交通運(yùn)輸業(yè)以及決策分析部門(mén)都可以發(fā)揮作用。從范圍來(lái)看,小到一個(gè)班組的計(jì)劃安排,大至整個(gè)部門(mén),以至國(guó)民經(jīng)濟(jì)計(jì)劃的最優(yōu)化方案分析,它都有用武之地,具有適應(yīng)性強(qiáng),應(yīng)用面廣,計(jì)算技術(shù)比較簡(jiǎn)便的特點(diǎn)。非線性規(guī)劃的基礎(chǔ)性工作則是在1951年由庫(kù)恩(H.W.Kuhn和達(dá)克(A.W.Tucker等人完成的,到了70年代,數(shù)學(xué)規(guī)劃無(wú)論是在理論上和方法上,還是在應(yīng)用的深度和廣度上都得到了進(jìn)一步的發(fā)展。數(shù)學(xué)規(guī)劃的研究對(duì)象是計(jì)劃管理工作中有關(guān)安排和估值的問(wèn)題,解決的主要問(wèn)題是在給定條件下,按某一衡量指標(biāo)來(lái)尋找安排的最優(yōu)方案。它可以表示成求函數(shù)在滿(mǎn)足約束條件下的極大極小值問(wèn)題。數(shù)學(xué)規(guī)劃和古典的求極值的問(wèn)題有本質(zhì)上的不同,古典方法只能處理具有簡(jiǎn)單表達(dá)式,和簡(jiǎn)單約束條件的情況。而現(xiàn)代的數(shù)學(xué)規(guī)劃中的問(wèn)題目標(biāo)函數(shù)和約束條件都很復(fù)雜,而且要求給出某種精確度的數(shù)字解答,因此算法的研究特別受到重視。這里最簡(jiǎn)單的一種問(wèn)題就是線性規(guī)劃。如果約束條件和目標(biāo)函數(shù)都是呈線性關(guān)系的就叫線性規(guī)劃。要解決線性規(guī)劃問(wèn)題,從理論上講都要解線性方程組,因此解線性方程組的方法,以及關(guān)于行列式、矩陣的知識(shí),就是線性規(guī)劃中非常必要的工具。線性規(guī)劃及其解法—單純形法的出現(xiàn),對(duì)運(yùn)籌學(xué)的發(fā)展起了重大的推動(dòng)作用。許多實(shí)際問(wèn)題都可以化成線性規(guī)劃來(lái)解決,而單純形法有是一個(gè)行之有效的算法,加上計(jì)算機(jī)的出現(xiàn),使一些大型復(fù)雜的實(shí)際問(wèn)題的解決成為現(xiàn)實(shí)。非線性規(guī)劃是線性規(guī)劃的進(jìn)一步發(fā)展和繼續(xù)。許多實(shí)際問(wèn)題如設(shè)計(jì)問(wèn)題、經(jīng)濟(jì)平衡問(wèn)題都屬于非線性規(guī)劃的范疇。非線性規(guī)劃擴(kuò)大了數(shù)學(xué)規(guī)劃的應(yīng)用范圍,同時(shí)也給數(shù)學(xué)工作者提出了許多基本理論問(wèn)題,使數(shù)學(xué)中的如凸分析、數(shù)值分析等也得到了發(fā)展。還有一種規(guī)劃問(wèn)題和時(shí)間有關(guān),叫做“動(dòng)態(tài)規(guī)劃”。近年來(lái)在工程控制、技術(shù)物理和通訊中的最佳控制問(wèn)題中,已經(jīng)成為經(jīng)常使用的重要工具。圖論圖論是一個(gè)古老的但又十分活躍的分支,它是網(wǎng)絡(luò)技術(shù)的基礎(chǔ)。圖論的創(chuàng)始人是數(shù)學(xué)家歐拉。1736年他發(fā)表了圖論方面的第一篇論文,解決了著名的哥尼斯堡七橋難題,相隔一百年后,在1847年基爾霍夫第一次應(yīng)用圖論的原理分析電網(wǎng),從而把圖論引進(jìn)到工程技術(shù)領(lǐng)域。20世紀(jì)50年代以來(lái),圖論的理論得到了進(jìn)一步發(fā)展,將復(fù)雜龐大的工程系統(tǒng)和管理問(wèn)題用圖描述,可以解決很多工程設(shè)計(jì)和管理決策的最優(yōu)化問(wèn)題,例如,完成工程任務(wù)的時(shí)間最少,距離最短,費(fèi)用最省等等。圖論受到數(shù)學(xué)、工程技術(shù)及經(jīng)營(yíng)管理等各方面越來(lái)越廣泛的重視。排隊(duì)論排隊(duì)論又叫隨機(jī)服務(wù)系統(tǒng)理論。最初是在二十世紀(jì)初由丹麥工程師艾爾郎關(guān)于電話交換機(jī)的效率研究開(kāi)始的,在第二次世界大戰(zhàn)中為了對(duì)飛機(jī)場(chǎng)跑道的容納量進(jìn)行估算,它得到了進(jìn)一步的發(fā)展,其相應(yīng)的學(xué)科更新論、可靠性理論等也都發(fā)展起來(lái)。1909年丹麥的電話工程師愛(ài)爾朗(A.K.Erlang排隊(duì)問(wèn)題,1930年以后,開(kāi)始了更為一般情況的研究,取得了一些重要成果。1949年前后,開(kāi)始了對(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)的問(wèn)題。比如一個(gè)港口應(yīng)該有多少個(gè)碼頭,一個(gè)工廠應(yīng)該有多少維修人員等。因?yàn)榕抨?duì)現(xiàn)象是一個(gè)隨機(jī)現(xiàn)象,因此在研究排隊(duì)現(xiàn)象的時(shí)候,主要采用的是研究隨機(jī)現(xiàn)象的概率論作為主要工具。此外,還有微分和微分方程。排隊(duì)論把它所要研究的對(duì)象形象的描述為顧客來(lái)到服務(wù)臺(tái)前要求接待。如果服務(wù)臺(tái)以被其它顧客占用,那么就要排隊(duì)。另一方面,服務(wù)臺(tái)也時(shí)而空閑、時(shí)而忙碌。就需要通過(guò)數(shù)學(xué)方法求得顧客的等待時(shí)間、排隊(duì)長(zhǎng)度等的概率分布。排隊(duì)論在日常生活中的應(yīng)用是相當(dāng)廣泛的,比如水庫(kù)水量的調(diào)節(jié)、生產(chǎn)流水線的安排,鐵路分成場(chǎng)的調(diào)度、電網(wǎng)的設(shè)計(jì)等等?？煽啃岳碚摽煽啃岳碚撌茄芯肯到y(tǒng)故障、以提高系統(tǒng)可靠性問(wèn)題的理論?？煽啃岳碚撗芯康南到y(tǒng)一般分為兩類(lèi):(1不可修系統(tǒng):如導(dǎo)彈等,這種系統(tǒng)的參數(shù)是壽命、可靠度等,(2可修復(fù)系統(tǒng):如一般的機(jī)電設(shè)備等,這種系統(tǒng)的重要參數(shù)是有效度,其值為系統(tǒng)的正常工作時(shí)間與正常工作時(shí)間加上事故修理時(shí)間之比。對(duì)策論對(duì)策論也叫博弈論,前面講的田忌賽馬就是典型的博弈論問(wèn)題。作為運(yùn)籌學(xué)的一個(gè)分支,博弈論的發(fā)展也只有幾十年的歷史。系統(tǒng)地創(chuàng)建這門(mén)學(xué)科的數(shù)學(xué)家,現(xiàn)在一般公認(rèn)為是美籍匈牙利數(shù)學(xué)家、計(jì)算機(jī)之父——馮·諾依曼。最初用數(shù)學(xué)方法研究博弈論是在國(guó)際象棋中開(kāi)始的,旨在用來(lái)如何確定取勝的算法。由于是研究雙方?jīng)_突、制勝對(duì)策的問(wèn)題,所以這門(mén)學(xué)科在軍事方面有著十分重要的應(yīng)用。近年來(lái),數(shù)學(xué)家還對(duì)水雷和艦艇、殲擊機(jī)和轟炸機(jī)之間的作戰(zhàn)、追蹤等問(wèn)題進(jìn)行了研究,提出了追逃雙方都能自主決策的數(shù)學(xué)理論。近年來(lái),隨著人工智能研究的進(jìn)一步發(fā)展,對(duì)博弈論提出了更多新的要求。決策論研究決策問(wèn)題。所謂決策就是根據(jù)客觀可能性,借助一定的理論、方法和工具,科學(xué)地選擇最優(yōu)方案的過(guò)程。決策問(wèn)題是由決策者和決策域構(gòu)成的,而決策域又由決策空間、狀態(tài)空間和結(jié)果函數(shù)構(gòu)成。研究決策理論與方法的科學(xué)就是決策科學(xué)。決策所要解決的問(wèn)題是多種多樣的,從不同角度有不同的分類(lèi)方法,按決策者所面臨的自然狀態(tài)的確定與否可分為:確定型決策、風(fēng)險(xiǎn)型決策和不確定型決策;按決策所依據(jù)的目標(biāo)個(gè)數(shù)可分為:單目標(biāo)決策與多目標(biāo)決策;按決策問(wèn)題的性質(zhì)可分為:戰(zhàn)略決策與策略決策,以及按不同準(zhǔn)則劃分成的種種決策問(wèn)題類(lèi)型。不同類(lèi)型的決策問(wèn)題應(yīng)采用不同的決策方法。決策的基本步驟為:(1確定問(wèn)題,提出決策的目標(biāo);(2發(fā)現(xiàn)、探索和擬定各種可行方案;(3從多種可行方案中,選出最滿(mǎn)意的方案;(4決策的執(zhí)行與反饋,以尋求決策的動(dòng)態(tài)最優(yōu)。如果決策者的對(duì)方也是人(一個(gè)人或一群人雙方都希望取勝,這類(lèi)具有競(jìng)爭(zhēng)性的決策稱(chēng)為對(duì)策或博弈型決策。構(gòu)成對(duì)策問(wèn)題的三個(gè)根本要素是:局中人、策略與一局對(duì)策的得失。目前對(duì)策