1、1,運(yùn)籌學(xué)基礎(chǔ) 黃海燕,2,運(yùn)籌學(xué)既是一門科學(xué) 又是一門藝術(shù),第一章,緒論,運(yùn)籌學(xué)（Operational Research） 運(yùn)籌學(xué)直譯為“運(yùn)作研究”，是應(yīng)用分析、試驗(yàn)、量化的方法，對經(jīng)濟(jì)管理系統(tǒng)中的人力、物力、財力等資源進(jìn)行統(tǒng)籌安排，為決策者提供有依據(jù)的最優(yōu)方案，以實(shí)現(xiàn)最有效的管理。,運(yùn)籌學(xué) 管理運(yùn)籌學(xué) 管理科學(xué),第一章,緒論,運(yùn)籌學(xué)的產(chǎn)生和發(fā)展,我國古代有很多關(guān)于運(yùn)籌學(xué)思想方法的典故。 齊王賽馬 丁渭修皇宮 沈括運(yùn)軍糧,一般軍隊(duì)出行，從敵方獲取軍糧是最要緊的急務(wù)。運(yùn)糧不僅費(fèi)用多，而且難以載糧遠(yuǎn)行。我曾經(jīng)計(jì)算過，每人背米六斗，士兵自己攜帶五日干糧，每人供一個士兵，一行可達(dá)十八天；六斗米，每

2、人一天吃兩升，兩個人吃，正好十八天吃完；如果以往返計(jì)算，只可吃九天的行程。兩個人供一個士兵食糧，一行可以達(dá)二十六天；（一石二斗米，三人每天吃六升，八天的話一個背夫所負(fù)的糧食已經(jīng)吃完，給他六天的糧食遣回，后十八天，二個人每天吃四升或干糧）。如果以往返計(jì)，只可有十三天的路程。（前八天每天吃六升，后五天加回程，每天吃四升加干糧）三個人供一個士兵，一行可供三十一天，一石八斗米，前六天半四個人每天吃八升，派返一個背夫，給他四天口糧；十七天三人每天吃六升，又送加一個民夫，給他九天口糧；后十八天，二個人每天吃四升加干糧。計(jì)算往返的話只可前行十六天的里程，（前六天半，每天吃八升，中間七天每天吃六升，后十一天加

3、回程每天吃四升加干糧）。三個人供一個士卒吃用，已為最大極限。如果興兵十萬人，管護(hù)輜重的有三分之一，能夠戰(zhàn)斗的士兵只有七萬人，而運(yùn)糧的民夫要用三十萬人，此外很難再增人了。（放回運(yùn)夫要有兵卒護(hù)援，由于路途中死亡疾病，人數(shù)會不斷減少，而那些省下來的糧食，以備護(hù)援兵卒吃用。運(yùn)糧的制度，每人平均以六斗計(jì)算，這是個總計(jì)方法。其中隊(duì)長不背東西，打柴汲水的人背負(fù)減半，多出斤重部分平攤給眾民夫，更有死亡疾病不能背米的，他們應(yīng)負(fù)的重量，又平均分?jǐn)偅敲疵總€人所負(fù)的重量，常常不止六斗的重量。因此軍中不容許多余的飯口，一個多余的人吃飯，就要兩三個人供應(yīng)他，還有可能供不夠。如果以牲畜運(yùn)糧，駱駝可以負(fù)三石，馬、騾一石五斗

4、，驢一石，相比于以人運(yùn)糧，雖然負(fù)多費(fèi)少，但如果不按時喂草，牲畜多會死亡，一個牲口死掉，它馱負(fù)的糧食也得扔掉，相比用人背扛，有利有弊，利害均半。,運(yùn)籌學(xué)在工商管理中的應(yīng)用,自 1972 年至 2014 年，F(xiàn)ranz Edelman 獎項(xiàng)入圍項(xiàng)目獲利累計(jì)超過 2130 億美元。,運(yùn)籌學(xué)在工商管理中的應(yīng)用,8,教學(xué)內(nèi)容,第一章： 緒言 第二章： 線性規(guī)劃 第三章： 運(yùn)輸模型與分配問題 第四章： 整數(shù)規(guī)劃 第五章： 圖論基礎(chǔ)與網(wǎng)絡(luò)分析 第六章： 網(wǎng)絡(luò)計(jì)劃技術(shù) 第七章： 庫存論 第九章： 決策論,9,第一章：緒言,10,1.1 緒言：運(yùn)籌學(xué)的產(chǎn)生與發(fā)展,運(yùn)籌學(xué)在商業(yè)活動與行政事務(wù)中的早期應(yīng)用可追溯到幾

5、個世紀(jì)以前，但是系統(tǒng)的運(yùn)籌學(xué)理論起源于二次大戰(zhàn)期間。最初是英國軍方為了最大限度地利用已經(jīng)十分短缺的戰(zhàn)爭資源，召集了一批科學(xué)家與工程技術(shù)人員共同籌劃作戰(zhàn)物資的分配問題。英國軍方的這一舉動很快引起了美國軍方的重視，類似的研究小組在美國三軍機(jī)構(gòu)中相繼成立，并開發(fā)出一套相對完整的新技術(shù)，用以指導(dǎo)協(xié)約國方面在戰(zhàn)略上和戰(zhàn)術(shù)上的各種軍事行動。許多諾貝爾獎金獲得者都為運(yùn)籌學(xué)的建立與發(fā)展作出過重要的貢獻(xiàn)。其中，最早投入運(yùn)籌學(xué)研究的諾貝爾獎金獲得者是美國物理學(xué)家Blackett。他領(lǐng)導(dǎo)了第一個以運(yùn)籌學(xué)命名的研究小組。由于該小組的成員來自各個方面，既有物理學(xué)家，也有經(jīng)濟(jì)學(xué)家、數(shù)學(xué)家、社會學(xué)家和心理學(xué)家，因而被人們戲

6、稱為Blackett馬戲團(tuán)?？梢钥闯?，運(yùn)籌學(xué)是一門應(yīng)用性極強(qiáng)的交叉科學(xué)。,11,由于運(yùn)籌學(xué)技術(shù)在二次大戰(zhàn)中的成功運(yùn)用，它與許許多多受戰(zhàn)爭推動而產(chǎn)生的其它科學(xué)技術(shù)一樣，在戰(zhàn)爭結(jié)束后立即引起了民間組織和商業(yè)機(jī)構(gòu)的濃厚興趣。因?yàn)殡S著社會工業(yè)化程度的逐步提高，各種生產(chǎn)組織和商業(yè)機(jī)構(gòu)變得越來越大，與之相關(guān)的管理決策問題也變得越來越復(fù)雜。過去那種憑直觀、憑感覺、憑經(jīng)驗(yàn)決策的方式已幾乎不再可能。企業(yè)家們迫切需要一種定量分析的技術(shù)來幫助他們正確處理日益復(fù)雜的經(jīng)濟(jì)決策問題。于是運(yùn)籌學(xué)技術(shù)很快被運(yùn)用到了民間組織和商業(yè)機(jī)構(gòu)的管理決策當(dāng)中，且由于其影響之大、應(yīng)用之廣，以至于在民間應(yīng)用的特定環(huán)境中，運(yùn)籌學(xué)這一帶有軍事色

7、彩的專業(yè)術(shù)語被代之以管理科學(xué)這一頗具現(xiàn)代氣息的新名詞,12,1.2 運(yùn)籌學(xué)的科學(xué)性和藝術(shù)性,作為科學(xué)，運(yùn)籌學(xué)必須在科學(xué)方法論的指導(dǎo)下進(jìn)行科學(xué)探索。其工作步驟包括： (1) 確定問題：目標(biāo)、約束、變量和參數(shù)。 (2) 建立模型：目標(biāo)、約束、變量和參數(shù)之間的關(guān)系。 (3) 求解模型：最優(yōu)解、有效解和滿意解。 (4) 解的檢驗(yàn)：正確性、有效性和穩(wěn)定性。 (5) 解的控制：靈敏度分析。 (6) 解的實(shí)施：解釋、培訓(xùn)和監(jiān)測。,13,作為藝術(shù)，運(yùn)籌學(xué)涉及到?jīng)Q策者的社會環(huán)境、心理作用、主觀意愿和工作經(jīng)驗(yàn)等多方面的因素，而這些因素又大都具有模糊特征與動態(tài)性質(zhì)。為了有效地應(yīng)用運(yùn)籌學(xué)，前英國運(yùn)籌學(xué)學(xué)會會長托姆林森

8、提出以下原則： (1) 合伙原則：運(yùn)籌學(xué)工作者與管理工作者相結(jié)合。 (2) 催化原則：多學(xué)科協(xié)作，打破常規(guī)。 (3) 滲透原則：跨部門、跨行業(yè)聯(lián)合。 (4) 獨(dú)立原則：不受某人或某部門的特殊政策所左右。 (5) 寬容原則：廣開思路，兼容并蓄。 (6) 平衡原則：平衡矛盾，平衡關(guān)系。,14,1.3 運(yùn)籌學(xué)的方法論,模型是運(yùn)籌學(xué)研究客觀現(xiàn)實(shí)的工具和手段。常見的模型有以下3種基本形式： (1) 思維模型：它是研究者對于某種事物的想象或者概念性的描述，譬如公司主管頭腦中對于公司未來市場的規(guī)劃。這雖然不是一種精確、具體、可見的形式，但通常是其它模型的原源。 (2) 物理模型：它可以是一個與實(shí)物同等尺寸、

9、或者被放大、或者被縮小、或者被簡化的幾何模型，用以形象地表現(xiàn)和演示被研究的對象；它也可以是一些圖表，用以說明事物的流程。 (3) 數(shù)學(xué)模型：它是采用數(shù)學(xué)符號來精確描述實(shí)際事物中的變動因素和因素間的相互關(guān)系。,15,構(gòu)造模型是一種創(chuàng)造性勞動，成功的模型往往是科學(xué)和藝術(shù)的結(jié)晶。建模的方法和思路有以下4種： (1) 直接分析法：根據(jù)研究者對問題內(nèi)在機(jī)理的認(rèn)識直接構(gòu)造模型，并利用已知的算法對問題求解與分析。如線性規(guī)劃模型，動態(tài)規(guī)劃模型，排隊(duì)模型，存儲模型，決策與對策模型等等。 (2) 類比法：模仿類似問題的結(jié)構(gòu)性質(zhì)建立模型并進(jìn)行類比分析。如物理系統(tǒng)、化學(xué)系統(tǒng)、信息系統(tǒng)、和經(jīng)濟(jì)系統(tǒng)之間都有某些相通的地方

10、，因而可互相借鑒。 (3) 統(tǒng)計(jì)分析法：盡管機(jī)理未明，但可根據(jù)歷史資料或?qū)嶒?yàn)結(jié)果運(yùn)用統(tǒng)計(jì)分析方法建模。 (4) 邏輯推理法：利用知識和經(jīng)驗(yàn)對事物的變化過程進(jìn)行邏輯推理來構(gòu)造模型。,16,數(shù)學(xué)模型是三種常見模型中最抽象、最復(fù)雜的模型，它反映的是事物的本質(zhì)。數(shù)學(xué)模型的一般形式可以寫為： 目標(biāo)的評價準(zhǔn)則 U = f(xi, yj, k) 約束條件 g(xi, yj, k) 0 式中： xi為可控變量； yj為已知參數(shù)； k為不確定性因素。 目標(biāo)的評價準(zhǔn)則一般要求達(dá)到最佳(最大或最小)、適中、滿意等。準(zhǔn)則可以是單一的，也可以是多個的。約束條件可以有許多，也可以一個沒有。如果g為等式，即為平衡條件。當(dāng)模

11、型中沒有不確定性因素時，稱之為確定性模型。如果不確定性因素是隨機(jī)因素，則為隨機(jī)模型；如果是模糊因素，則為模糊模型；如果既有隨機(jī)因素又有模糊因素，則為模糊隨機(jī)模型。,1.4 數(shù)學(xué)模型與定量分析,2009.11.15,17,在建立了問題的數(shù)學(xué)模型之后，如何求解模型是運(yùn)籌學(xué)的另一個關(guān)鍵所在。運(yùn)籌學(xué)的進(jìn)步有賴于定量分析技術(shù)的應(yīng)用與發(fā)展，尤其是近年來計(jì)算機(jī)技術(shù)的迅速提高，各種管理決策方面的應(yīng)用性軟件相繼推出，使決策者得以借助于計(jì)算機(jī)對復(fù)雜的實(shí)際問題進(jìn)行定量分析，大大改進(jìn)了定量技術(shù)的有效性。 必須指出的是，我們在應(yīng)用數(shù)學(xué)模型和定量分析技術(shù)的時候應(yīng)該十分小心。因?yàn)閷?shí)際問題通常是復(fù)雜的，它包含著許許多多數(shù)字的

12、和非數(shù)字的有用信息。在數(shù)學(xué)模型的量化與抽象過程中，很容易由于理想化而偏離實(shí)際情況從而失去代表性。,18,2009.11.15,第二章：線性規(guī)劃,19,2.1 線性規(guī)劃的數(shù)學(xué)模型,線性規(guī)劃是運(yùn)籌學(xué)的一個重要分支。自1947年美國數(shù)學(xué)家Dantzig提出了求解線性規(guī)劃的單純形方法之后，已被廣泛應(yīng)用于現(xiàn)代工業(yè)、農(nóng)業(yè)、交通運(yùn)輸、軍事、經(jīng)濟(jì)等各種決策領(lǐng)域，成為科學(xué)管理的重要手段之一。 例2.1(生產(chǎn)計(jì)劃問題) 某化工廠在計(jì)劃期內(nèi)擬安排生產(chǎn)I 、II兩種產(chǎn)品，已知其市場需求量和單位利潤及原材料的消耗量如表2.1所示。問應(yīng)如何安排生產(chǎn)計(jì)劃以使該工廠的獲利最多？,表2.1 生產(chǎn)計(jì)劃綜合信息,20,解 該問題可

13、用以下的數(shù)學(xué)模型描述：設(shè)x1、x2分別表示產(chǎn)品I、II的產(chǎn)量，則工廠追求的目標(biāo)可寫成利潤函數(shù),式中：符號max表示對利潤函數(shù)Z求極大值。目標(biāo)追求所受到的限制來自原材料供應(yīng)和產(chǎn)品需求兩個方面，其中原材料供應(yīng)施加的約束條件可以寫為,表2.1提供的信息將第一種產(chǎn)品的計(jì)劃產(chǎn)量限制在1500噸以內(nèi)，但對第二種產(chǎn)品的產(chǎn)量并未構(gòu)成實(shí)質(zhì)性約束，即,21,以上4個約束條件被稱為顯式約束條件。此外，考慮到變量x1、x2分別表示產(chǎn)品I、II的產(chǎn)量，取值范圍應(yīng)滿足 大于等于零的要求，否則沒有意義。這一類公理性的約束條件被稱為隱式約束條件。 綜上所述，該問題的數(shù)學(xué)模型可寫為：, 1,線性規(guī)劃問題的提出,例1.某工廠在計(jì)

14、劃期內(nèi)要安排、兩種產(chǎn)品的生產(chǎn)，生產(chǎn)單位產(chǎn)品所需的設(shè)備臺時及 A、B 兩種原材料的消耗以及資源的限制，如下表所示。,問：工廠應(yīng)分別生產(chǎn)多少單位、產(chǎn)品才能使工廠獲利最多？, 1,線性規(guī)劃問題的提出,問：工廠應(yīng)分別生產(chǎn)多少單位、產(chǎn)品才能使工廠獲利最多？,約束條件：,例2.2(邊角余料問題) 某紙廠生產(chǎn)紙卷的標(biāo)準(zhǔn)寬度為20英尺?，F(xiàn)有三宗訂單，所要求紙卷的寬度分別為5、7、9英尺，需求量分別為150卷、200卷、300卷。廠家需從標(biāo)準(zhǔn)寬度的紙卷上進(jìn)行切割以滿足顧客的訂貨要求。問應(yīng)如何切割以滿足顧客的訂購需求且使廢棄的邊角余料最少？ 解 該問題中紙卷的可能切割方式共有6種(見圖2.1)。 |5|5|5|5

15、| |5|5|7|3| |5|5|9|1| |5|7|7|1| |7|9| 4 | | 9 | 9 | 2 | 圖2.1 基本切割方式,2009.11.15,24,2009.11.15,25,其線性規(guī)劃的數(shù)學(xué)模型可以表示為：,上述數(shù)學(xué)模型的目標(biāo)函數(shù)也可以改寫為：,作為一個練習(xí)，請讀者仔細(xì)思考上述兩個模型的差別。,26,例2.3(連續(xù)投資問題) 某公司考慮兩種可能的連續(xù)投資計(jì)劃A和B。其中，計(jì)劃A每元投資每年可贏利0.1元；計(jì)劃B每元投資每2年可贏利0.3元。設(shè)公司在第一年年初擬用于投資的金額為100萬元，問應(yīng)如何安排投資計(jì)劃可使該公司在第3年年末所收回的資金最多？ 解 令xij 表示公司在第i

16、年年初投資于計(jì)劃j中的金額，則今后3年可能的投資情況如表2.2所示： 表2.2 投資分析表,27,故該投資問題的線性規(guī)劃模型為：,從以上的例題分析可以看出，建立線性規(guī)劃的數(shù)學(xué)模型要求決策者回答三個問題：(1) 變量是什么？(2) 目標(biāo)函數(shù)是什么？(3) 約束條件是什么？其中，變量是線性規(guī)劃建模的關(guān)鍵與基礎(chǔ)。如果變量設(shè)計(jì)合理，便容易回答后面的兩個問題；否則不易找到目標(biāo)函數(shù)與約束條件的表示形式，即使勉強(qiáng)完成了建模，也難以理解模型的物理意義。, 2,圖解法,兩個決策變量的線性問題，可以用圖解法求解。, 2,圖解法,每個約束條件都代表一個半平面。, 2,圖解法,每個約束條件都代表一個半平面。, 2,圖

17、解法,把五個限制條件對應(yīng)的五個半平面合并成一個圖，各約束條件的公共部分即為可行域。, 2,圖解法,得到最優(yōu)解：B:=50,=250 最優(yōu)目標(biāo)值 z=27500, 2,圖解法,重要結(jié)論, 2,圖解法,重要結(jié)論無界解（無最優(yōu)解的情況）,目標(biāo)函數(shù)：max z = x1 + x2 ； 約束條件：x1 - x2 1 -3 x1 +2 x2 6 x1 0， x2 0,該問題可行域無界，目標(biāo)函數(shù)值無窮大，無界解，即無最優(yōu)解。, 2,圖解法,例2 某公司由于生產(chǎn)需要，共需A,B兩種原料至少350噸（A，B有一定替代性）限制條件具體如下：,求目標(biāo)函數(shù)最小化的線性規(guī)劃問題,試問在滿足生產(chǎn)需要的前提下，在公司加工能

18、力的范圍內(nèi)，如何購買 A，B 兩種原料，使得購進(jìn)成本最低？, 2,圖解法,得 B 點(diǎn)坐標(biāo)（250，100）為最優(yōu)解,建立模型：,37,2.2 線性規(guī)劃的圖解方法,例2.4 考慮下面的線性規(guī)劃問題：,38,步驟1 在約束條件的基礎(chǔ)上確定線性規(guī)劃的可行域,步驟2 在目標(biāo)函數(shù)的基礎(chǔ)上確定可行域中的最優(yōu)點(diǎn),步驟3 求解最優(yōu)點(diǎn)對應(yīng)的變量值和目標(biāo)函數(shù)值,2009.11.15,39,2.3 線性規(guī)劃的標(biāo)準(zhǔn)形式,線性規(guī)劃的標(biāo)準(zhǔn)形式：,2009.11.15,40,1非負(fù)變量： 。 若變量 xi 無約束，可將其改寫為兩個非負(fù)變量之差的表示形式，即 ，其中 2極大型目標(biāo)函數(shù)：max。 對于極小型目標(biāo)函數(shù)min，可采

19、用等價變換轉(zhuǎn)化為極大型目標(biāo)函數(shù)max，即 3等式約束條件：。 對于型或型的不等式約束條件，可通過添加外在變量的方法將不等式約束條件轉(zhuǎn)換為等式約束條件。如：,41,例2.5 將以下線性規(guī)劃改寫為數(shù)學(xué)模型的標(biāo)準(zhǔn)形式,解,2009.11.15,42,2.4 常規(guī)單純形方法,由線性代數(shù)的原理可知，一個包含n個變量和m個方程的線性方程組，當(dāng)nm時是一個不定型方程組，其中包含有無窮多個解。此時，n個變量被分為兩組，一組是基本變量，數(shù)目等于m；另一組為非基本變量，數(shù)目等于nm。令非基本變量的取值為零，然后對基本變量求解方程組，可以得到一組唯一的解，稱為基本解。如果基本解中全部變量的取值是非負(fù)的，則稱為可行基

20、本解；否則為不可行基本解。關(guān)于基本變量的選擇，原則上是任意的，只要所選出的變量相互獨(dú)立即可。例如，考慮下面的線性方程組：,式中n=4, m=2, n-m=2，故4個變量中的2個是基本變量，另外2個是非基本變量。顯然，除了x1和x3因?yàn)榫€性相關(guān)而不能同時選為基本變量外，變量間其他的兩兩組合都可以產(chǎn)生一個基本解。,2009.11.15,43,若令 x3 = x4 = 0，則有,若令 x1 = x2 = 0，則有,線性規(guī)劃的可行基本解與不可行基本解在線性規(guī)劃的單純形算法中起著同等重要的作用，并因此形成單純形方法的兩個分支：常規(guī)單純形與對偶單純形。,2009.11.15,44,重新考慮例2.4中的線性

21、規(guī)劃問題，旨在觀察圖解方法的代數(shù)演繹過程。首先將線性規(guī)劃的數(shù)學(xué)模型標(biāo)準(zhǔn)化，即 這里 n=6, m=4, n-m=2。若將x1和x2確定為非基本變量，其對應(yīng)的初始解是一個可行基本解： x1 = 0, x2 = 0, s1= 6, s2 = 8, s3 = 1, s4= 2 它相應(yīng)于圖2.2中的坐標(biāo)原點(diǎn)A，其目標(biāo)函數(shù)值Z = 0,2009.11.15,45,由圖2.3可見，從A點(diǎn)出發(fā)，沿著可行域的邊界有兩條路線可以到達(dá)最優(yōu)點(diǎn)C。一條是： ，另一條是： 。顯然，兩條路線的長度不一樣。換言之，不同搜索方式有著不同的效率。作為對方法的要求，這里有兩個問題需要解決：一是行走的方向，二是行走的距離。前者涉及

22、解的好壞，即優(yōu)化性；后者涉及解的對錯，即可行性。,圖2.3,2009.11.15,46,根據(jù)高斯約旦的消元法則，每次交換解中的一個非基本變量與基本變量。其中，被交換的非基本變量稱為進(jìn)入變量，而對應(yīng)的基本變量稱為退出變量。 為了解釋進(jìn)入變量和退出變量的選擇原則，需要先回顧線性規(guī)劃數(shù)學(xué)模型的物理含義。一般而言，極大型目標(biāo)函數(shù)中變量的系數(shù)可視為相應(yīng)產(chǎn)品的單位利潤或單位收益（例如生產(chǎn)計(jì)劃問題）。本例中坐標(biāo)原點(diǎn)所對應(yīng)的生產(chǎn)系統(tǒng)尚處于計(jì)劃實(shí)施前的空閑狀態(tài)，即系統(tǒng)有能力生產(chǎn)兩個不同的產(chǎn)品，但目前一個產(chǎn)品都還沒有生產(chǎn)。現(xiàn)在面臨的問題是：如果暫時只能生產(chǎn)一個產(chǎn)品，應(yīng)該選擇哪一個產(chǎn)品作為生產(chǎn)對象？在不考慮其他方面

23、影響因素的前提下，一個直觀的想法應(yīng)該是選擇單位利潤或單位收益最大的產(chǎn)品作為生產(chǎn)產(chǎn)品。換言之，進(jìn)入變量應(yīng)為目標(biāo)函數(shù)中最大正系數(shù)所對應(yīng)的變量，這一原則被稱為線性規(guī)劃單純形方法的優(yōu)化原則。,2009.11.15,47,根據(jù)優(yōu)化原則，例2.4中下一步的進(jìn)入變量應(yīng)為非基本變量x1。相應(yīng)的退出變量則由各種資源允許產(chǎn)品I生產(chǎn)的數(shù)量來決定，其計(jì)算結(jié)果為： 資源1允許產(chǎn)品I生產(chǎn)的數(shù)量：6/1 = 6 資源2允許產(chǎn)品I生產(chǎn)的數(shù)量：8/2 = 4 資源3允許產(chǎn)品I生產(chǎn)的數(shù)量：1/-1 = -1 資源4允許產(chǎn)品I生產(chǎn)的數(shù)量：2/0 = 其中負(fù)比值沒有意義，無窮大意味著沒有限制，故真正反映生產(chǎn)資源最薄弱環(huán)節(jié)的比值應(yīng)是其

24、中的最小正比值，它表示資源允許產(chǎn)品I生產(chǎn)的最大數(shù)量。本例中的最小正比值為4，由約束直線2取得，故與之對應(yīng)的基本變量s2應(yīng)該退出，因?yàn)閤1=4時，s2=0。上述退出變量的選擇原則被稱為常規(guī)單純形方法的可行性原則。x1和s2的交換導(dǎo)致新的基本可行解： x2 = 0, s2 = 0, x1= 4, s1= 2, s3= 5, s4= 2 它相應(yīng)于圖2-2中的B點(diǎn)，其目標(biāo)函數(shù)值Z = 12。 重復(fù)上述過程，可逐步達(dá)到問題的最優(yōu)解： x1 = 10/3，x2 = 4/3，Z = 38/3 對應(yīng)圖2.2中的C點(diǎn)。,2009.11.15,48,常規(guī)單純形方法的兩個重要原則是： (1) 優(yōu)化原則：極大問題中的

25、進(jìn)入變量是目標(biāo)函數(shù)中最大正系數(shù)所對應(yīng)的非基本變量；如果目標(biāo)方程中所有非基本變量的系數(shù)均為負(fù)數(shù)，則該可行解即為最優(yōu)解。 (2) 可行原則：極大問題中的退出變量都是在進(jìn)入變量軸上具有最小正比值的基本變量。如果存在兩個或兩個以上的最小正比值，可任選其中之一。 常規(guī)單純形方法的迭代步驟概括為： 步驟1 在線性規(guī)劃標(biāo)準(zhǔn)模型的基礎(chǔ)上確定一個可行基本解作為初始解 步驟2 依據(jù)優(yōu)化原則從目前的非基本變量中選擇一個進(jìn)入變量 步驟3 依據(jù)可行原則從目前的基本變量中選擇一個退出變量 步驟4 交換進(jìn)入變量和退出變量以產(chǎn)生新的可行基本解，然后返回步驟2。,2009.11.15,49,2.4.2 常規(guī)單純形表上作業(yè),單純

26、形方法的運(yùn)算過程可基于Gauss-Jordan的消元法則在單純形表上完成。單純形表的制作形式與線性規(guī)劃的數(shù)學(xué)模型一一對應(yīng)。但在制作單純形表之前，應(yīng)先將目標(biāo)函數(shù)改寫為方程式。例如： Z = 3x1+2x2 Z -3x1-2x2 = 0 為此，常規(guī)單純形的優(yōu)化原則需做如下修改： (1) 優(yōu)化原則：極大問題的進(jìn)入變量是目標(biāo)函數(shù)中絕對值最大的負(fù)系數(shù)所對應(yīng)的非基本變量；如果目標(biāo)方程中所有非基本變量的系數(shù)均大于等于零，則該可行解即為最優(yōu)解。 (2) 可行原則：極大問題的退出變量都是在進(jìn)入變量軸上具有最小正比值的基本變量。如果存在兩個或兩個以上的最小正比值，可任選其中之一。,2009.11.15,50,依據(jù)

27、優(yōu)化和可行原則，x1和s2分別為進(jìn)入變量和退出變量，故表中與之對應(yīng)的列和行被分別稱為進(jìn)入列和退出行。同時，將位于進(jìn)入列和退出行相交單元上的元素定義為基準(zhǔn)元素，它在單純形的表上作業(yè)法中占有特殊的地位并發(fā)揮重要作用。線性規(guī)劃單純形表上作業(yè)的有關(guān)說明見表2.7。,51,2009.11.15,單純形表上作的計(jì)算步驟可以概括為： (1) 先計(jì)算基準(zhǔn)行：新基準(zhǔn)行元素 = 原基準(zhǔn)行元素 / 原基準(zhǔn)元素 (2) 后計(jì)算其它行：新行元素 = 原行元素 原進(jìn)入列對應(yīng)元素新基準(zhǔn)行元素 本例中新基準(zhǔn)行、新目標(biāo)行和新的S3-行的計(jì)算結(jié)果為： (1) 新基準(zhǔn)行,2009.11.15,52,(2) 新目標(biāo)行,(3) 新 S

28、3 行,2009.11.15,53,例2.4: 完整的表上作業(yè),2009.11.15,54,2.4.4 單純形應(yīng)用中的特殊情形,單純形應(yīng)用中可能出現(xiàn)的幾種特殊情形為：退化解，多優(yōu)解，無界解，無可行解 (1) 退化解：在使用單純形表確定退出變量時，如果有兩個以上的基本變量具有相同的最小比值，那么在下一個單純形表中會出現(xiàn)一個或幾個基本變量取值為零、而目標(biāo)值不變的情形，這樣得到的新解被稱為退化解。起因是模型的構(gòu)造不合理，其中包含了一個或多個冗余約束條件。,2009.11.15,55,例2.6 考慮以下線性規(guī)劃問題：,2009.11.15,56,(2) 多優(yōu)解：當(dāng)目標(biāo)直線平行于包含最優(yōu)解的約束直線時，

29、該約束直線在可行域中的任意一點(diǎn)都是問題的最優(yōu)解。 例2.7 考慮以下線性規(guī)劃問題,2009.11.15,57,(3) 無界解：當(dāng)極大問題的可行域上方無界或極小問題的可行域下方無界時，目標(biāo)函數(shù)值可增至無窮大或減至無窮小，這樣的解被稱為無界解。 例2.8 考慮以下線性規(guī)劃問題,2009.11.15,58,(4) 無可行解：約束條件互相矛盾，導(dǎo)致問題的可行域不存在。 例2.9 考慮以下線性規(guī)劃問題,2009.11.15,59,2.5 對偶單純形方法,常規(guī)單純形方法是從一個欠優(yōu)的可行基本解開始，在求解過程中始終保持解的可行性而逐步改進(jìn)解的優(yōu)化性；反之，對偶單純形方法則從一個超優(yōu)的不可行基本解開始，在求

30、解過程中始終保持解的優(yōu)化性而逐步改進(jìn)解的可行性。 例2.10 給定線性規(guī)劃的數(shù)學(xué)模型,2009.11.15,60,(1) 圖解法：問題的初始解為 X = (0, 0, -3, -6, 3)T，Z=0 相應(yīng)于圖中的A點(diǎn)，即坐標(biāo)原點(diǎn)。最優(yōu)解為：,2009.11.15,61,(2) 對偶單純形方法 回顧常規(guī)單純形方法的求解過程，現(xiàn)行解可行而未優(yōu)化，故先選擇最可能改進(jìn)優(yōu)化性的非基本變量作為進(jìn)入變量，然后考慮退出變量的問題，其交換順序是先進(jìn)后出；而在對偶單純形方法中，現(xiàn)行解超優(yōu)但不可行，故先選擇最不可行的基本變量讓其離開，然后考慮進(jìn)入變量的問題，其交換順序是先出后進(jìn)。相應(yīng)原則為： 可行性原則：離開變量是

31、取負(fù)值且絕對值最大的基本變量。 優(yōu)化性原則：極小問題的進(jìn)入變量是具有最小比值的非基本變量；極大問題的進(jìn)入變量是具有最小絕對比值的非基本變量。 比值的確定方式是用目標(biāo)行系數(shù)除以退出行中相應(yīng)的負(fù)系數(shù)。如果退出行中所有的系數(shù)均大于或等于零，則該問題不存在可行基本解。,2009.11.15,62,例2.10 的對偶表上作業(yè)過程介紹如下,2009.11.15,63,2.6 常規(guī)-對偶算法(廣義單純形),常規(guī)對偶算法是常規(guī)單純形和對偶單純形的自然擴(kuò)展，它允許使用者從一個既不可行、也未優(yōu)化的任意基本解開始，靈活運(yùn)用常規(guī)單純形方法或?qū)ε紗渭冃畏椒?，以最簡捷的方式趨近最?yōu)解。 例2.11 考慮以下線性規(guī)劃問題,

32、2009.11.15,64,初始解：x1=0, x2=0, s1=-6, s2=-3, s3=5, Z=0 。此解既未優(yōu)化，也不可行，變換過程見下表，優(yōu)化路徑：AFG。,2009.11.15,65,一般來說，廣義單純形方法在確定進(jìn)入和退出變量時不需要計(jì)算比值。對于標(biāo)準(zhǔn)化線性規(guī)劃(max)而言，其進(jìn)、出原則可自然實(shí)現(xiàn)如下： 1因?yàn)楝F(xiàn)行解未優(yōu)化，則檢驗(yàn)數(shù)中必然有負(fù)數(shù)，故根據(jù)優(yōu)化原則，應(yīng)選擇絕對值最大的負(fù)檢驗(yàn)數(shù)對應(yīng)的非基本變量作為進(jìn)入變量； 2因?yàn)楝F(xiàn)行解不可行，則基本變量的取值中必然有負(fù)數(shù)，故故根據(jù)可行性原則，應(yīng)選擇絕對值最大的負(fù)數(shù)所對應(yīng)的基本變量作為退出變量。 由本例的求解路線可以看出，廣義單純形

33、方法的搜索軌跡并不總是“一步一個腳印”，而有可能采取走“捷徑(cut path)”的方式，跨越線性規(guī)劃的某些基本解，如本例圖2.9中的E點(diǎn)。,2009.11.15,66,2.7 改進(jìn)單純形,線性規(guī)劃的矩陣模型,其中：,2009.11.15,67,約束條件Ax = b是一個含m個方程和n個變量的線性方程組，其中n m。依據(jù)線性代數(shù)理論，從系數(shù)矩陣A中任選m個線性獨(dú)立的列向量 均可產(chǎn)生問題的一個基本解。這m個列向量所構(gòu)成的方陣B被稱為線性規(guī)劃的基：,顯然，這樣的方陣必須是非奇異的，即：|B| 0。,2009.11.15,68,例2.12 設(shè)某線性規(guī)劃的系數(shù)矩陣為：,這里m = 3, n = 7,

34、nm = 4。容易驗(yàn)證，p1, p2, p3可以構(gòu)成一個基B，因?yàn)?但是p4和p5就不能同時被包含在任何基本矩陣中，因?yàn)樗鼈兙€性相關(guān)：p4 = p5,2009.11.15,69,線性規(guī)劃單純形方法中的初始基是一個單位矩陣，即B = I。然后每次交換基內(nèi)、外的一個列向量，逐步將現(xiàn)行解推向優(yōu)化(常規(guī)單純形)或推向可行(對偶單純形)。這一過程的數(shù)學(xué)描述為：設(shè)xI, xII 分別代表初始基中的非基本變量和基本變量，前者由決策變量和剩余變量組成，后者由松弛變量和人工變量組成。則線性規(guī)劃的矩陣模型可以改寫為：,2009.11.15,70,對于任何一個中間過程，用xB, cB表示與現(xiàn)行基B對應(yīng)的基本變量及其

35、目標(biāo)系數(shù)，考慮到非基本變量等于零的事實(shí)，則線性規(guī)劃的數(shù)學(xué)模型可以寫為：,將上式的兩邊左乘矩陣,的逆矩陣,即,可導(dǎo)出目標(biāo)值和基本變量取值的理論計(jì)算公式：,2009.11.15,71,上式對應(yīng)單純形表中的最后一列，即問題的結(jié)果部分。為了判斷和改進(jìn)現(xiàn)行解的優(yōu)化性，有必要進(jìn)一步導(dǎo)出單純形表的其余部分，包括檢驗(yàn)數(shù)與進(jìn)入列或退出行的計(jì)算公式。,2009.11.15,72,上式可以改寫成單純形表的初始形式,上表所示的單純形算法結(jié)構(gòu)中，由于xI, xII 始終對應(yīng)著初始解中的基本變量和非基本變量，隨著解的變換演進(jìn)，使用不很方便。故更常見的單純形算法結(jié)構(gòu)為：,2009.11.15,73,改進(jìn)單純形方法的計(jì)算步驟

36、： 步驟1 在線性規(guī)劃標(biāo)準(zhǔn)模型的系數(shù)矩陣A中任選m個相互獨(dú)立的列向量構(gòu)成問題的初始基B。 步驟2 求出現(xiàn)行解：xB = B1b，計(jì)算非基變量的檢驗(yàn)數(shù)：,步驟3 如果,對應(yīng)的非基本變量 xk為進(jìn)入變量；并選擇比值,對應(yīng)的基本變量xt為退出變量。,步驟3 如果 且 ，則終止算法，并輸出xB與Z。 步驟4 如果 且 ，同時 ，則選擇檢驗(yàn)數(shù),2009.11.15,74,步驟5 如果 ， 且 ，則選擇基本變量,為退出變量；并選擇比值,對應(yīng)的非基本變量 xk 為進(jìn)入變量。,步驟6 如果 ， 且 ， ，則選擇基本變量,為退出變量；并選擇檢驗(yàn)數(shù) 對應(yīng)的非基本變量xk為進(jìn)入變量。 步驟7 令B = B-pi+p

37、k，返回步驟2。,2009.11.15,75,例2.13 考慮以下線性規(guī)劃,該線性規(guī)劃的基B中含有多少個行列向量和向量？答案： 均為2個 (2) 列向量p2和p3能否構(gòu)成一個可行基？答案：否，因?yàn)槎?者線性相關(guān)： p3 = 2p2。 (3) 寫出B = (p1, p2) 和B 1。答案：,2009.11.15,76,(4) 寫出(3)中的xB, cB。答案：,(5) 上述xB是可行解嗎？答案：是，因?yàn)?(6) 上述xB是最優(yōu)解嗎？答案：否，因?yàn)?(7) 哪個變量應(yīng)該進(jìn)入？哪個變量應(yīng)該退出？答案：因?yàn)?對應(yīng)比值為： ，故 x3 進(jìn)入，x2 退出。,2009.11.15,77,(8) 確定新的xB

38、和基B。答案： 例2.14 給定線性規(guī)劃 已知 試確定該基本解是否為 最優(yōu)解？如果是，給出相應(yīng)結(jié)果；否則，確定進(jìn)出變量。,2009.11.15,78,解：優(yōu)化性檢驗(yàn), 此解非優(yōu)，變量x5進(jìn)入,可行性檢驗(yàn), 此解可行。退出變量？,2009.11.15,79,計(jì)算比值,結(jié)論：原基本解可行，但非優(yōu)；相應(yīng)的進(jìn)入變量為 x5，退出變量為x4。,2009.11.15,80,課堂練習(xí),給定線性規(guī)劃：,已知： 確定該基本解是否為最優(yōu)解？如果是，給出目標(biāo)值；否則， 確定進(jìn)、出變量。,2009.11.15,81,2.8 線性規(guī)劃的對偶理論,為了說明線性規(guī)劃多偶問題的數(shù)學(xué)模型，我們考慮以下生產(chǎn)計(jì)劃問題。 例2.15

39、 在生產(chǎn)管理和經(jīng)營活動中經(jīng)常需要從不同的角度來考察同一個問題。例如某工廠計(jì)劃生產(chǎn)I、II兩種產(chǎn)品，已知單位產(chǎn)品的利潤和生產(chǎn)所需的設(shè)備臺時及原材料A、B的消耗如下表所示。問應(yīng)如何安排生產(chǎn)計(jì)劃以使該工廠的獲利最多？,2009.11.15,82,該生產(chǎn)計(jì)劃問題可以用以下數(shù)學(xué)模型來描述：,式中x1、x2分別表示產(chǎn)品I、II的產(chǎn)量。 現(xiàn)在從另一角度來討論這個問題。假設(shè)該工廠決定不生產(chǎn)產(chǎn)品I、II，而將其所有資源出租或外售。這時工廠就要考慮每種資源的定價問題。,2009.11.15,83,設(shè)用y1，y2，y3分別表示出租單位設(shè)備臺時的租金和出讓單位原材料A、B的附加額。一個自然的比較方式是：1個單位設(shè)備臺

40、時和4個單位原材料A可以生產(chǎn)一件產(chǎn)品I，所得利潤為2元，那么生產(chǎn)每件產(chǎn)品I的設(shè)備臺時和原材料出租和出讓的總收入應(yīng)不低于生產(chǎn)一件產(chǎn)品I的利潤，即：,同理，將生產(chǎn)每件產(chǎn)品II的設(shè)備臺時和原材料出租和出讓的總收入應(yīng)不低于生產(chǎn)一件產(chǎn)品II的利潤，即：,而將全部設(shè)備和資源出租和出讓的總收入為：,從工廠的角度來看當(dāng)然是w越大越好，但從市場的角度來看則是w越小越好。那么，設(shè)備和資源的出租與出讓計(jì)劃可以寫成下面的線性規(guī)劃模型：,2009.11.15,84,此線性規(guī)劃問題被稱為上一線性規(guī)劃問題的對偶問題。 一般而言，原問題與對偶問題之間存在著下述關(guān)系： (1) 每一個原問題的約束條件對應(yīng)著一個對偶問題的變量；

41、(2) 每一個原問題的變量對應(yīng)著一個對偶問題的約束條件； (3) 原問題的模型系數(shù)與對偶問題的模型系數(shù)之間的對應(yīng)關(guān)系如下表所示。,2009.11.15,85,綜上所述，原問題與對偶問題之間的模型轉(zhuǎn)換可以寫為：,2009.11.15,86,原問題與對偶問題之間的關(guān)系可用下圖說明：,上圖表明，一般情形下 Z = cx yb = W ，即企業(yè)獲得的最大利潤小于其掌握資源的應(yīng)有價值，只有當(dāng)資源的配置達(dá)到最優(yōu)狀態(tài)時，企業(yè)的利潤才等于其資源的價值，即：Z* = W*。 因?yàn)樵瓎栴}的最優(yōu)解等于對偶問題的最優(yōu)解，即：,故資源的影子價格，即對偶變量的計(jì)算公式為：,2009.11.15,87,例2.16 重新考察

42、例2.15中的線性規(guī)劃,原問題的最優(yōu)單純形表為：,對偶問題的最優(yōu)解為：Y* = (3/2, 1/8, 0)，W* = Z* =14,2009.11.15,88,對偶問題的經(jīng)濟(jì)解釋,在線性規(guī)劃的數(shù)學(xué)模型中，所有形式的約束條件都在某種意義上反映了資源的有限性。該資源的實(shí)際狀態(tài)是多余還是短缺，由對應(yīng)松弛變量的數(shù)值來反映。S0意味著該種資源尚未用完，是處于多余狀態(tài)；S=0說明資源已經(jīng)耗盡，屬于短缺狀態(tài)。對于短缺的資源，決策者不禁要問：如進(jìn)一步增加資源，是否有可能改進(jìn)收益？ 前已述及，Z = cx yb = W 。這里c為單位產(chǎn)品的價格或利潤，x為產(chǎn)品的產(chǎn)量，故不等式的左邊表示總收益，即一共多少錢。而右

43、邊的b表示資源的數(shù)量，從簡單的量綱分析可知，對偶變量y必然表示單位資源具有的價值，故y也被稱為資源的影子價格。從而上述關(guān)系的物理含義被理解為：在一般情形下，總收益 總資源價值，只有在最優(yōu)狀態(tài)下等式才會成立。因?yàn)橹挥卸倘辟Y源才具有增進(jìn)收益的潛力，故短缺資源的影子價格大于零，而富余資源的影子價格等于零。,2009.11.15,89,在上面討論的生產(chǎn)問題中，計(jì)算表明原料A的影子價格 y2 = 0.125元，故只要原料A繼續(xù)處于緊缺狀態(tài)(s2 = 0)，每增加或減少1公斤的原料A，將增加或減少0.125元的總收益。如果市場上每公斤原料A的價格低于0.125元，則可考慮購進(jìn)原料A以擴(kuò)大生產(chǎn)規(guī)模；反之，如

44、果每公斤原料A的價格高于0.125元，則應(yīng)考慮出售原料A以減小生產(chǎn)規(guī)模。顯然，隨著生產(chǎn)規(guī)模的擴(kuò)大或縮小，原料A的影子價格將相應(yīng)減小或增大，當(dāng)原材料的影子價格等于其市場價格時，產(chǎn)品的生產(chǎn)規(guī)模被稱為經(jīng)濟(jì)規(guī)模。,2009.11.15,90,2.9 靈敏度分析,2.9.1 優(yōu)化性分析 線性規(guī)劃的優(yōu)化性要素主要來自三個方面：價值系數(shù)c，非基本變量的原材料消耗系數(shù)p，和新產(chǎn)品的引進(jìn) x。 1. 價值系數(shù)c的變化分析 對于極大型的線性規(guī)劃而言，關(guān)于價值系數(shù)變化的靈敏度分析原則為：如果所有檢驗(yàn)數(shù)的計(jì)算結(jié)果均大于零，則原最優(yōu)解繼續(xù)有效；否則，需在靈敏度分析的基礎(chǔ)上進(jìn)行相應(yīng)的改進(jìn)。,2009.11.15,91,例

45、2.18 重新考慮例2.4中的問題：,如果價值系數(shù)從原來的c = (3, 2) 改變?yōu)閏 = (5, 4)，那么上表中非基變量的檢驗(yàn)數(shù)變?yōu)椋?原最優(yōu)解繼續(xù)有效，但目標(biāo)值從38/3增加到22。,2009.11.15,92,2. 非基本變量資源消耗系數(shù)票pj的變化分析 因?yàn)榛咀兞繉?yīng)資源消耗系數(shù)改變會導(dǎo)致基本矩陣B的改變，從而超出了靈敏度分析的范疇，故這里僅考慮非基本變量對應(yīng)資源消耗系數(shù)改變的情形。此時，pj的變化只影響單純形表的第j列，而其他列的數(shù)字不會發(fā)生變化。 例2.19 給定線性規(guī)劃,若將p2=(2,1,1,1)T 改變成p2=(4,3,1,1)T，則Y=cBB-1=(0,2,0,0)，

46、檢驗(yàn)數(shù)2=yp2-c2=50，故原解繼續(xù)有效。,2009.11.15,93,3. 增加新產(chǎn)品分析 如果在生產(chǎn)計(jì)劃問題中增加一個新的產(chǎn)品，線性規(guī)劃的數(shù)學(xué)模型必然增加一個新的變量。假定原線性規(guī)劃具有n個變量，則新增加的變量記為xn+1。由于線性規(guī)劃的約束條件沒有改變，故基本變量的個數(shù)維持不變，新增加的變量只能是非基本變量。由單純形表的特性可知，此時的單純型表將增加新的一列，其余不受影響。,例2.19 在例2.4的生產(chǎn)計(jì)劃問題中增加一個新產(chǎn)品III，產(chǎn)量記為x3。c3 = 3/2, p3 = (3/4,3/4,-1,0)T。其數(shù)學(xué)模型為：,2009.11.15,94,2009.11.15,95,新的

47、最優(yōu)解為：x1=2, x3=16/3, Z=14,2009.11.15,96,在線性規(guī)劃的單純形求解過程中，可行性主要來自以下兩方面的影響：資源供應(yīng)量b的改變或增加新的約束條件，現(xiàn)分別討論如下。 1. 資源供應(yīng)量b的變化分析 由改進(jìn)單純形的計(jì)算公式可知，資源供應(yīng)量b的改變只會影響到表中最右邊的常數(shù)列。 例2.20 重新考慮例2.17中的線性規(guī)劃問題。假定原資源供應(yīng)量b=(6,8,1,2)T 被改變?yōu)閎=(7,4,1,2)T ，即,2.9.2 可行性分析,原解不滿足可行性要求， 對應(yīng)單純形表如下：,2009.11.15,97,采用對偶單純形方法改進(jìn)，其結(jié)果為,2009.11.15,98,2. 增

48、加新的約束條件 如果原最優(yōu)解滿足新的約束條件，則原解繼續(xù)有效；否則必須改進(jìn)。此時，由于多了一個約束條件，必然增添一個外加變量，而且是基本變量，故原單純形表需增加一行和一列。 例2.21 在例2.17的線性規(guī)劃中增加約束條件：x13,原最優(yōu)單純形表, x1 = 10/3 + (1/3)s1 (2/3)s2 x1 + s5 = 3 (1/3)s1 (2/3)s2 +s5 = 1/3,2009.11.15,99,采用對偶單純形方法改進(jìn),2009.11.15,100,2.9.3 優(yōu)化性-可行性綜合分析(c + b),理論上，兩類要素的任意組合都會導(dǎo)致一種新的靈敏度分析情形，但分析的原理和方法是相同的。

49、 例2.22 在例2.4中，若將參數(shù)C = (3, 2) 改換成C = (4, 1)，同時將參數(shù)b = (6, 8, 1, 2)改換成b = (7, 4, 1, 2)，則有：,原最優(yōu)解為：,2009.11.15,101,可見原解的優(yōu)化性和可行性均被破壞，其改進(jìn)過程如下表 所示。,2009.11.15,102,2009.11.15,103,第三章：運(yùn)輸模型與分配問題,2009.11.15,104,第三章：運(yùn)輸模型與分配問題,運(yùn)輸模型解決單一貨物從多個產(chǎn)地向多個目的地輸送的計(jì)劃安排問題。典型的運(yùn)輸模型如以下圖表所示：,2009.11.15,105,設(shè)貨物的運(yùn)輸成本與運(yùn)輸數(shù)量成正比。若用xij表示從

50、產(chǎn)地i到銷地j的運(yùn)量，則在產(chǎn)銷平衡的前提下，要確定總運(yùn)費(fèi)最小的調(diào)運(yùn)方案，可求解以下線性規(guī)劃問題：,2009.11.15,106,例3.1 某汽車制造公司下設(shè)3個生產(chǎn)廠：A1, A2, A3，2個產(chǎn)品集散中心：B1, B2。已知生產(chǎn)廠的日產(chǎn)量分別為：1000輛, 1500輛, 1200輛；集散中心的日需求量分別為：2300輛, 1400輛。從各生產(chǎn)廠到各集散中心的產(chǎn)品運(yùn)價見下表。問該公司應(yīng)如何制訂調(diào)運(yùn)方案，在滿足各集散中心需求量的前提下，可使總運(yùn)輸成本最??？,2009.11.15,107,為制訂最優(yōu)運(yùn)輸方案，可求解以下線性規(guī)劃模型：,2009.11.15,108,運(yùn)輸問題表上作業(yè)法,一. 確定初

51、始解：最小成本法(Least Cost),例3.2 考慮下面的運(yùn)輸問題：,2009.11.15,109,110,與線性規(guī)劃基本解優(yōu)化性的判斷一樣，運(yùn)輸方案優(yōu)化性的判斷也由非基本變量的檢驗(yàn)數(shù)決定。如果所有非基本變量對應(yīng)的檢驗(yàn)數(shù)均小于或等于零，則該運(yùn)輸方案為優(yōu)化方案；否則，需對運(yùn)輸方案進(jìn)一步作出改進(jìn)。 設(shè)ui和vi分別為運(yùn)輸表的行因子和列因子。對于基本變量xij，存在關(guān)系 若令UI=0，則可循環(huán)計(jì)算其他因子的數(shù)值。而對于非基本變量xpj，存在關(guān)系,二. 判定解的優(yōu)化性：位勢法,(2),Vogel法（作業(yè)過程一）,10,2,14,5,15,15,10,5,15,25,5,0,0,(2),Vogel法

52、（作業(yè)過程二）,11,2,5,15,15,10,5,15,25,5,0,0,15,10,0,(2),Vogel法（作業(yè)過程三）,11,13,0,15,0,10,5,15,10,0,15,0,10,0,(2),Vogel法（作業(yè)過程四）,11,0,5,0,10,5,15,0,0,15,10,0,10,5,(2),Vogel法（作業(yè)過程五）,0,0,0,10,5,10,0,0,15,10,0,5,10,0,(2),Vogel法（作業(yè)過程六）,0,0,0,0,5,0,0,0,15,10,5,10,0,(2),Vogel法,10,2,14,0,15,15,10,15,25,5,2009.11.15,1

53、18,二. 判定解的優(yōu)化性：閉合路線法,2009.11.15,119,2009.11.15,120,三. 改進(jìn)運(yùn)輸方案：閉合路線法,2009.11.15,121,不平衡運(yùn)輸問題標(biāo)準(zhǔn)化,1. 供應(yīng)量小于需求量：虛構(gòu)一產(chǎn)地(啞元),2009.11.15,122,2. 供應(yīng)量大于需求量：虛構(gòu)一銷地(啞元), 3,附加條件的不平衡運(yùn)輸問題,需求大于總供應(yīng)量問題，構(gòu)造產(chǎn)銷平衡與運(yùn)價表。,140, 3,附加條件的不平衡運(yùn)輸問題,平衡后單位運(yùn)價表。,M,140,變換過程一,5,1,7,6,4,2,3,7,5,6,3,M,0,30,35,0,20,變換過程二,5,1,7,6,4,2,3,7,5,6,3,M,0

54、,30,35,0,20,25,0,10,變換過程三,5,1,7,6,4,2,3,7,5,6,3,M,0,30,35,0,20,25,0,10,10,20,變換過程四,5,1,7,6,4,2,3,7,5,6,3,M,0,30,20,0,0,25,0,0,10,20,35,20,變換過程五,5,1,7,6,4,2,3,7,5,6,3,M,0,30,20,0,0,25,0,0,10,0,35,0,20,2009.11.15,130,分配問題：匈牙利算法,設(shè)有m個不同工件需進(jìn)行某種加工，現(xiàn)有n臺不同機(jī)器可以承擔(dān)此加工任務(wù)，但由于每臺機(jī)器的性能不同，加工不同工件所需的費(fèi)用和效率都不一樣。于是產(chǎn)生了應(yīng)該將

55、哪一個工件分配給哪一臺機(jī)器加工所需的總費(fèi)用最小的問題。這類問題被稱為分配問題或指派問題，它可以用下面的分配表加以描述：,2009.11.15,131,匈牙利算法具體步驟： 步驟1 行作業(yè). 將每行的元素減去行中的最小元素； 步驟2 列作業(yè). 將每列的元素減去列中的最小元素； 步驟3 試分配. 從0元素最少的行或列開始，選擇一個0，然后劃去同行和同列的其它0。如此反復(fù)進(jìn)行，直到所有0元素都被選擇或劃去為止。若所選0元素的數(shù)目等于矩陣的階，則分配問題的最優(yōu)解已經(jīng)得到，終止算法；否則，轉(zhuǎn)入下一步。 步驟4 刪除零. 用最少的直線刪除所有0元素，其操作過程為：先對沒有被選元素的行作一標(biāo)記，再對已標(biāo)記的

56、行中所有含0元素的列作一標(biāo)記，然后對有標(biāo)記的列中含0元素的行作一標(biāo)記，如此反復(fù)進(jìn)行，直至找不到可標(biāo)記的行或列為止。最后劃去沒有標(biāo)記的行和有標(biāo)記的列，即為覆蓋所有0元素的最少直線數(shù)。 步驟5 增加零. 將沒有被直線覆蓋的元素減去其中的最小元素，并將各直線交點(diǎn)上的元素加上該最小元素。然后返回步驟2。,2009.11.15,132,例3.4 求解下表所示的分配問題,2009.11.15,133,第四章：整數(shù)線性規(guī)劃,2009.11.15,134,4.2 分枝定界法,例4.2 求解以下整數(shù)線性規(guī)劃問題,2009.11.15,135,2009.11.15,136,4.3 割平面法,分枝定界法本質(zhì)上是一種

57、對線性規(guī)劃可行域?qū)嵤┓指钋蠼獾姆椒?，但分割方式比較被動和單一，故其效率不高。割平面方法的總體思路與分枝定界法相似，也是通過切割作業(yè)從線性規(guī)劃中尋求整數(shù)解。但割平面方法的切割方式主動靈活，切割目標(biāo)明確具體，旨在將整數(shù)規(guī)劃的最優(yōu)點(diǎn)造就為一個普通線性規(guī)劃的頂點(diǎn)，從而有的放矢地求解整數(shù)規(guī)劃問題，故其效率較高。,2009.11.15,137,例4.3 求解以下整數(shù)線性規(guī)劃問題,2009.11.15,138,純整數(shù)規(guī)劃分量切割,分量切割方程的推導(dǎo)要求整數(shù)規(guī)劃的數(shù)學(xué)模型中所有變量的系數(shù)和常數(shù)都必須是整數(shù)。為方便起見，將問題的最優(yōu)單純形表改寫為以下形式：,2009.11.15,139,設(shè) xi 取非整數(shù)值，那么第 i 個約束等式被稱為源行，寫為：,(分