2009.11.151《運(yùn)籌學(xué)基礎(chǔ)》李榮鈞博士，教授，博士生導(dǎo)師2009.11.152運(yùn)籌學(xué)既是一門科學(xué)又是一門藝術(shù)2009.11.153教學(xué)內(nèi)容第一章：緒言第二章：線性規(guī)劃第三章：運(yùn)輸模型與分配問題第四章：整數(shù)規(guī)劃第五章：圖論基礎(chǔ)與網(wǎng)絡(luò)分析第六章：網(wǎng)絡(luò)計劃技術(shù)第七章：庫存論第九章：決策論2009.11.154第一章：緒言2009.11.1551.1緒言：運(yùn)籌學(xué)的產(chǎn)生與發(fā)展

運(yùn)籌學(xué)在商業(yè)活動與行政事務(wù)中的早期應(yīng)用可追溯到幾個世紀(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é)家，因而被人們戲稱為Blackett馬戲團(tuán)?？梢钥闯?，運(yùn)籌學(xué)是一門應(yīng)用性極強(qiáng)的交叉科學(xué)。2009.11.156

由于運(yùn)籌學(xué)技術(shù)在二次大戰(zhàn)中的成功運(yùn)用，它與許許多多受戰(zhàn)爭推動而產(chǎn)生的其它科學(xué)技術(shù)一樣，在戰(zhàn)爭結(jié)束后立即引起了民間組織和商業(yè)機(jī)構(gòu)的濃厚興趣。因為隨著社會工業(yè)化程度的逐步提高，各種生產(chǎn)組織和商業(yè)機(jī)構(gòu)變得越來越大，與之相關(guān)的管理決策問題也變得越來越復(fù)雜。過去那種憑直觀、憑感覺、憑經(jīng)驗決策的方式已幾乎不再可能。企業(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é)這一帶有軍事色彩的專業(yè)術(shù)語被代之以管理科學(xué)這一頗具現(xiàn)代氣息的新名詞2009.11.1571.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)解的檢驗：正確性、有效性和穩(wěn)定性。(5)解的控制：靈敏度分析。(6)解的實施：解釋、培訓(xùn)和監(jiān)測。2009.11.158

作為藝術(shù)，運(yùn)籌學(xué)涉及到?jīng)Q策者的社會環(huán)境、心理作用、主觀意愿和工作經(jīng)驗等多方面的因素，而這些因素又大都具有模糊特征與動態(tài)性質(zhì)。為了有效地應(yīng)用運(yùn)籌學(xué)，前英國運(yùn)籌學(xué)學(xué)會會長托姆林森提出以下原則：(1)合伙原則：運(yùn)籌學(xué)工作者與管理工作者相結(jié)合。(2)催化原則：多學(xué)科協(xié)作，打破常規(guī)。(3)滲透原則：跨部門、跨行業(yè)聯(lián)合。(4)獨(dú)立原則：不受某人或某部門的特殊政策所左右。(5)寬容原則：廣開思路，兼容并蓄。(6)平衡原則：平衡矛盾，平衡關(guān)系。2009.11.1591.3運(yùn)籌學(xué)的方法論

模型是運(yùn)籌學(xué)研究客觀現(xiàn)實的工具和手段。常見的模型有以下3種基本形式：(1)思維模型：它是研究者對于某種事物的想象或者概念性的描述，譬如公司主管頭腦中對于公司未來市場的規(guī)劃。這雖然不是一種精確、具體、可見的形式，但通常是其它模型的原源。(2)物理模型：它可以是一個與實物同等尺寸、或者被放大、或者被縮小、或者被簡化的幾何模型，用以形象地表現(xiàn)和演示被研究的對象；它也可以是一些圖表，用以說明事物的流程。(3)數(shù)學(xué)模型：它是采用數(shù)學(xué)符號來精確描述實際事物中的變動因素和因素間的相互關(guān)系。2009.11.1510

構(gòu)造模型是一種創(chuàng)造性勞動，成功的模型往往是科學(xué)和藝術(shù)的結(jié)晶。建模的方法和思路有以下4種：(1)直接分析法：根據(jù)研究者對問題內(nèi)在機(jī)理的認(rèn)識直接構(gòu)造模型，并利用已知的算法對問題求解與分析。如線性規(guī)劃模型，動態(tài)規(guī)劃模型，排隊模型，存儲模型，決策與對策模型等等。(2)類比法：模仿類似問題的結(jié)構(gòu)性質(zhì)建立模型并進(jìn)行類比分析。如物理系統(tǒng)、化學(xué)系統(tǒng)、信息系統(tǒng)、和經(jīng)濟(jì)系統(tǒng)之間都有某些相通的地方，因而可互相借鑒。(3)統(tǒng)計分析法：盡管機(jī)理未明，但可根據(jù)歷史資料或?qū)嶒灲Y(jié)果運(yùn)用統(tǒng)計分析方法建模。(4)邏輯推理法：利用知識和經(jīng)驗對事物的變化過程進(jìn)行邏輯推理來構(gòu)造模型。2009.11.1511

數(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)模型中沒有不確定性因素時，稱之為確定性模型。如果不確定性因素是隨機(jī)因素，則為隨機(jī)模型；如果是模糊因素，則為模糊模型；如果既有隨機(jī)因素又有模糊因素，則為模糊隨機(jī)模型。1.4數(shù)學(xué)模型與定量分析2009.11.1512

在建立了問題的數(shù)學(xué)模型之后，如何求解模型是運(yùn)籌學(xué)的另一個關(guān)鍵所在。運(yùn)籌學(xué)的進(jìn)步有賴于定量分析技術(shù)的應(yīng)用與發(fā)展，尤其是近年來計算機(jī)技術(shù)的迅速提高，各種管理決策方面的應(yīng)用性軟件相繼推出，使決策者得以借助于計算機(jī)對復(fù)雜的實際問題進(jìn)行定量分析，大大改進(jìn)了定量技術(shù)的有效性。

必須指出的是，我們在應(yīng)用數(shù)學(xué)模型和定量分析技術(shù)的時候應(yīng)該十分小心。因為實際問題通常是復(fù)雜的，它包含著許許多多數(shù)字的和非數(shù)字的有用信息。在數(shù)學(xué)模型的量化與抽象過程中，很容易由于理想化而偏離實際情況從而失去代表性。132009.11.15第二章：線性規(guī)劃142009.11.152.1線性規(guī)劃的數(shù)學(xué)模型

原材料消耗

(噸)產(chǎn)品利潤(千元/噸)產(chǎn)品需求量(噸)ABC產(chǎn)品I10685不大于1500II520157不小于100原材料最大供應(yīng)量(噸)600500800

線性規(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)計劃問題)

某化工廠在計劃期內(nèi)擬安排生產(chǎn)I、II兩種產(chǎn)品，已知其市場需求量和單位利潤及原材料的消耗量如表2.1所示。問應(yīng)如何安排生產(chǎn)計劃以使該工廠的獲利最多？表2.1生產(chǎn)計劃綜合信息2009.11.1515

解

該問題可用以下的數(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)品的計劃產(chǎn)量限制在1500噸以內(nèi)，但對第二種產(chǎn)品的產(chǎn)量并未構(gòu)成實質(zhì)性約束，即2009.11.1516

以上4個約束條件被稱為顯式約束條件。此外，考慮到變量x1、x2分別表示產(chǎn)品I、II的產(chǎn)量，取值范圍應(yīng)滿足

大于等于零的要求，否則沒有意義。這一類公理性的約束條件被稱為隱式約束條件。

綜上所述，該問題的數(shù)學(xué)模型可寫為：

例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——|①|(zhì)——5——|——5——|———7———|—3—|

②|——5——|——5——|————9————|1|

③|——5——|———7———|———7———|1|④|———7———|————9————|—

4—|⑤|————9————|————9———|2

|⑥

圖2.1基本切割方式2009.11.15172009.11.1518其線性規(guī)劃的數(shù)學(xué)模型可以表示為：

上述數(shù)學(xué)模型的目標(biāo)函數(shù)也可以改寫為：作為一個練習(xí)，請讀者仔細(xì)思考上述兩個模型的差別。2009.11.1519

例2.3(連續(xù)投資問題)某公司考慮兩種可能的連續(xù)投資計劃A和B。其中，計劃A每元投資每年可贏利0.1元；計劃B每元投資每2年可贏利0.3元。設(shè)公司在第一年年初擬用于投資的金額為100萬元，問應(yīng)如何安排投資計劃可使該公司在第3年年末所收回的資金最多？

解

令xij

表示公司在第i年年初投資于計劃j中的金額，則今后3年可能的投資情況如表2.2所示：表2.2投資分析表年份年初可用金額(萬元)投資計劃年末收回金額(萬元)AB1100x1Ax1B1.1x1A21.1x1Ax2Ax2B1.1x2A+1.3x1B31.1x2A+1.3x1Bx3A

1.1x3A+1.3x2B2009.11.1520故該投資問題的線性規(guī)劃模型為：

從以上的例題分析可以看出，建立線性規(guī)劃的數(shù)學(xué)模型要求決策者回答三個問題：(1)變量是什么？(2)目標(biāo)函數(shù)是什么？(3)約束條件是什么？其中，變量是線性規(guī)劃建模的關(guān)鍵與基礎(chǔ)。如果變量設(shè)計合理，便容易回答后面的兩個問題；否則不易找到目標(biāo)函數(shù)與約束條件的表示形式，即使勉強(qiáng)完成了建模，也難以理解模型的物理意義。2009.11.15212.2線性規(guī)劃的圖解方法例2.4考慮下面的線性規(guī)劃問題：2009.11.1522步驟1在約束條件的基礎(chǔ)上確定線性規(guī)劃的可行域步驟2在目標(biāo)函數(shù)的基礎(chǔ)上確定可行域中的最優(yōu)點步驟3求解最優(yōu)點對應(yīng)的變量值和目標(biāo)函數(shù)值2009.11.15232.3線性規(guī)劃的標(biāo)準(zhǔn)形式線性規(guī)劃的標(biāo)準(zhǔn)形式：2009.11.1524

1．非負(fù)變量：

。

若變量

xi無約束，可將其改寫為兩個非負(fù)變量之差的表示形式，即

，其中

2．極大型目標(biāo)函數(shù)：max。

對于極小型目標(biāo)函數(shù)min，可采用等價變換轉(zhuǎn)化為極大型目標(biāo)函數(shù)max，即

3．等式約束條件：＝。

對于≤型或≥型的不等式約束條件，可通過添加外在變量的方法將不等式約束條件轉(zhuǎn)換為等式約束條件。如：2009.11.1525例2.5將以下線性規(guī)劃改寫為數(shù)學(xué)模型的標(biāo)準(zhǔn)形式解

2009.11.15262.4常規(guī)單純形方法由線性代數(shù)的原理可知，一個包含n個變量和m個方程的線性方程組，當(dāng)n>m時是一個不定型方程組，其中包含有無窮多個解。此時，n個變量被分為兩組，一組是基本變量，數(shù)目等于m；另一組為非基本變量，數(shù)目等于n–m。令非基本變量的取值為零，然后對基本變量求解方程組，可以得到一組唯一的解，稱為基本解。如果基本解中全部變量的取值是非負(fù)的，則稱為可行基本解；否則為不可行基本解。關(guān)于基本變量的選擇，原則上是任意的，只要所選出的變量相互獨(dú)立即可。例如，考慮下面的線性方程組：式中n=4,m=2,n-m=2，故4個變量中的2個是基本變量，另外2個是非基本變量。顯然，除了x1和x3因為線性相關(guān)而不能同時選為基本變量外，變量間其他的兩兩組合都可以產(chǎn)生一個基本解。2009.11.1527若令x3=x4=0，則有

若令x1=x2=0，則有

線性規(guī)劃的可行基本解與不可行基本解在線性規(guī)劃的單純形算法中起著同等重要的作用，并因此形成單純形方法的兩個分支：常規(guī)單純形與對偶單純形。2009.11.1528,

重新考慮例2.4中的線性規(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)原點A，其目標(biāo)函數(shù)值Z=02009.11.1529由圖2.3可見，從A點出發(fā)，沿著可行域的邊界有兩條路線可以到達(dá)最優(yōu)點C。一條是：，另一條是：。顯然，兩條路線的長度不一樣。換言之，不同搜索方式有著不同的效率。作為對方法的要求，這里有兩個問題需要解決：一是行走的方向，二是行走的距離。前者涉及解的好壞，即優(yōu)化性；后者涉及解的對錯，即可行性。圖2.32009.11.1530

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

根據(jù)優(yōu)化原則，例2.4中下一步的進(jìn)入變量應(yīng)為非基本變量x1。相應(yīng)的退出變量則由各種資源允許產(chǎn)品I生產(chǎn)的數(shù)量來決定，其計算結(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)是其中的最小正比值，它表示資源允許產(chǎn)品I生產(chǎn)的最大數(shù)量。本例中的最小正比值為4，由約束直線2取得，故與之對應(yīng)的基本變量s2應(yīng)該退出，因為x1=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點，其目標(biāo)函數(shù)值Z=12。重復(fù)上述過程，可逐步達(dá)到問題的最優(yōu)解：x1=10/3，x2=4/3，Z=38/3對應(yīng)圖2.2中的C點。2009.11.1532常規(guī)單純形方法的兩個重要原則是：

(1)優(yōu)化原則：極大問題中的進(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.15332.4.2常規(guī)單純形表上作業(yè)單純形方法的運(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.1534依據(jù)優(yōu)化和可行原則，x1和s2分別為進(jìn)入變量和退出變量，故表中與之對應(yīng)的列和行被分別稱為進(jìn)入列和退出行。同時，將位于進(jìn)入列和退出行相交單元上的元素定義為基準(zhǔn)元素，它在單純形的表上作業(yè)法中占有特殊的地位并發(fā)揮重要作用。線性規(guī)劃單純形表上作業(yè)的有關(guān)說明見表2.7。352009.11.15原基準(zhǔn)行2101008原基準(zhǔn)元素2新基準(zhǔn)行11/201/2004

單純形表上作的計算步驟可以概括為：

(1)先計算基準(zhǔn)行：新基準(zhǔn)行元素=原基準(zhǔn)行元素/原基準(zhǔn)元素(2)后計算其它行：新行元素=原行元素－原進(jìn)入列對應(yīng)元素×新基準(zhǔn)行元素本例中新基準(zhǔn)行、新目標(biāo)行和新的S3-行的計算結(jié)果為：(1)新基準(zhǔn)行2009.11.1536原目標(biāo)行-3-200000-(-3)×新基準(zhǔn)行33/203/20012新目標(biāo)行0-1/203/20012原S3行-1100101-(-1)×新基準(zhǔn)行11/201/2004新S3行03/201/2105(2)新目標(biāo)行(3)新S3行2009.11.1537例2.4:完整的表上作業(yè)

目標(biāo)與基X1X2S1S2S3S4解A點Z-3-200000S11210006S22101008S3-1100101S40100012B點Z0-1/203/20012S103/21-1/2002X111/201/2004S303/201/2105S40100012C點Z001/34/30038/3X2012/3-1/3004/3X110-1/32/30010/3S300-11103S400-2/31/3012/32009.11.15382.4.4單純形應(yīng)用中的特殊情形

單純形應(yīng)用中可能出現(xiàn)的幾種特殊情形為：退化解，多優(yōu)解，無界解，無可行解

(1)退化解：在使用單純形表確定退出變量時，如果有兩個以上的基本變量具有相同的最小比值，那么在下一個單純形表中會出現(xiàn)一個或幾個基本變量取值為零、而目標(biāo)值不變的情形，這樣得到的新解被稱為退化解。起因是模型的構(gòu)造不合理，其中包含了一個或多個冗余約束條件。2009.11.1539例2.6

考慮以下線性規(guī)劃問題：

目標(biāo)與基X1X2X3X4解比值迭代1Z-3-9000X3141082X4120142迭代2Z-3/409/4018

X21/411/402

X41/20-1/210

迭代3Z003/23/218

X2011/2-1/22

X110-120

2009.11.1540(2)多優(yōu)解：當(dāng)目標(biāo)直線平行于包含最優(yōu)解的約束直線時，該約束直線在可行域中的任意一點都是問題的最優(yōu)解。

例2.7考慮以下線性規(guī)劃問題2009.11.1541(3)無界解：當(dāng)極大問題的可行域上方無界或極小問題的可行域下方無界時，目標(biāo)函數(shù)值可增至無窮大或減至無窮小，這樣的解被稱為無界解。

例2.8考慮以下線性規(guī)劃問題2009.11.1542(4)無可行解：約束條件互相矛盾，導(dǎo)致問題的可行域不存在。

例2.9考慮以下線性規(guī)劃問題2009.11.15432.5對偶單純形方法

常規(guī)單純形方法是從一個欠優(yōu)的可行基本解開始，在求解過程中始終保持解的可行性而逐步改進(jìn)解的優(yōu)化性；反之，對偶單純形方法則從一個超優(yōu)的不可行基本解開始，在求解過程中始終保持解的優(yōu)化性而逐步改進(jìn)解的可行性。

例2.10給定線性規(guī)劃的數(shù)學(xué)模型→2009.11.1544(1)圖解法：問題的初始解為X=(0,0,-3,-6,3)T，Z=0相應(yīng)于圖中的A點，即坐標(biāo)原點。最優(yōu)解為：2009.11.1545(2)對偶單純形方法

回顧常規(guī)單純形方法的求解過程，現(xiàn)行解可行而未優(yōu)化，故先選擇最可能改進(jìn)優(yōu)化性的非基本變量作為進(jìn)入變量，然后考慮退出變量的問題，其交換順序是先進(jìn)后出；而在對偶單純形方法中，現(xiàn)行解超優(yōu)但不可行，故先選擇最不可行的基本變量讓其離開，然后考慮進(jìn)入變量的問題，其交換順序是先出后進(jìn)。相應(yīng)原則為：

可行性原則：離開變量是取負(fù)值且絕對值最大的基本變量。

優(yōu)化性原則：極小問題的進(jìn)入變量是具有最小比值的非基本變量；極大問題的進(jìn)入變量是具有最小絕對比值的非基本變量。比值的確定方式是用目標(biāo)行系數(shù)除以退出行中相應(yīng)的負(fù)系數(shù)。如果退出行中所有的系數(shù)均大于或等于零，則該問題不存在可行基本解。2009.11.1546例2.10的對偶表上作業(yè)過程介紹如下

目標(biāo)與基X1X2X3X4X5解迭代1Z-3-20000X3-3-1100-3X4-4-3010-6X5110013比值3/42/3

迭代2Z-1/300-2/304X3-5/301-1/30-1X24/310-1/302X5-1/3001/311比值1/5

2

迭代3Z00-1/5-3/5021/5X110-3/51/503/5X2014/5-3/506/5X500-1/52/516/52009.11.15472.6常規(guī)-對偶算法(廣義單純形)常規(guī)－對偶算法是常規(guī)單純形和對偶單純形的自然擴(kuò)展，它允許使用者從一個既不可行、也未優(yōu)化的任意基本解開始，靈活運(yùn)用常規(guī)單純形方法或?qū)ε紗渭冃畏椒?，以最簡捷的方式趨近最?yōu)解。

例2.11考慮以下線性規(guī)劃問題2009.11.1548初始解：x1=0,x2=0,s1=-6,s2=-3,s3=5,Z=0。此解既未優(yōu)化，也不可行，變換過程見下表，優(yōu)化路徑：A→F→G。

目標(biāo)與基X1X2S1S2S3解迭代1Z-120000S1-3-2100-6S2-1-2010-3S3110015迭代2Z-40100-6X23/21-1/2003S220-1103S3-1/201/2012迭代3Z-3000-2-10X2110015S2100127S1-1010242009.11.1549

一般來說，廣義單純形方法在確定進(jìn)入和退出變量時不需要計算比值。對于標(biāo)準(zhǔn)化線性規(guī)劃(max)而言，其進(jìn)、出原則可自然實現(xiàn)如下：

1．因為現(xiàn)行解未優(yōu)化，則檢驗數(shù)中必然有負(fù)數(shù)，故根據(jù)優(yōu)化原則，應(yīng)選擇絕對值最大的負(fù)檢驗數(shù)對應(yīng)的非基本變量作為進(jìn)入變量；2．因為現(xiàn)行解不可行，則基本變量的取值中必然有負(fù)數(shù)，故故根據(jù)可行性原則，應(yīng)選擇絕對值最大的負(fù)數(shù)所對應(yīng)的基本變量作為退出變量。

由本例的求解路線可以看出，廣義單純形方法的搜索軌跡并不總是“一步一個腳印”，而有可能采取走“捷徑(cutpath)”的方式，跨越線性規(guī)劃的某些基本解，如本例圖2.9中的E點。2009.11.15502.7改進(jìn)單純形線性規(guī)劃的矩陣模型其中：2009.11.1551

約束條件Ax

=

b是一個含m個方程和n個變量的線性方程組，其中n

≥

m。依據(jù)線性代數(shù)理論，從系數(shù)矩陣A中任選m個線性獨(dú)立的列向量

均可產(chǎn)生問題的一個基本解。這m個列向量所構(gòu)成的方陣B被稱為線性規(guī)劃的基：顯然，這樣的方陣必須是非奇異的，即：|B|≠0。2009.11.1552例2.12設(shè)某線性規(guī)劃的系數(shù)矩陣為：這里m=3,n=7,n－m=4。容易驗證，p1,p2,p3可以構(gòu)成一個基B，因為但是p4和p5就不能同時被包含在任何基本矩陣中，因為它們線性相關(guān)：p4

=

－p52009.11.1553

線性規(guī)劃單純形方法中的初始基是一個單位矩陣，即B

=

I。然后每次交換基內(nèi)、外的一個列向量，逐步將現(xiàn)行解推向優(yōu)化(常規(guī)單純形)或推向可行(對偶單純形)。這一過程的數(shù)學(xué)描述為：設(shè)xI,xII分別代表初始基中的非基本變量和基本變量，前者由決策變量和剩余變量組成，后者由松弛變量和人工變量組成。則線性規(guī)劃的矩陣模型可以改寫為：?2009.11.1554

對于任何一個中間過程，用xB,cB表示與現(xiàn)行基B對應(yīng)的基本變量及其目標(biāo)系數(shù)，考慮到非基本變量等于零的事實，則線性規(guī)劃的數(shù)學(xué)模型可以寫為：?將上式的兩邊左乘矩陣的逆矩陣,即可導(dǎo)出目標(biāo)值和基本變量取值的理論計算公式：2009.11.1555

上式對應(yīng)單純形表中的最后一列，即問題的結(jié)果部分。為了判斷和改進(jìn)現(xiàn)行解的優(yōu)化性，有必要進(jìn)一步導(dǎo)出單純形表的其余部分，包括檢驗數(shù)與進(jìn)入列或退出行的計算公式。↓2009.11.1556上式可以改寫成單純形表的初始形式目標(biāo)與基xIxII解ZCBB-1A－CICBB-1－CIICBB-1bxBB-1A’B-1B-1b上表所示的單純形算法結(jié)構(gòu)中，由于xI,xII始終對應(yīng)著初始解中的基本變量和非基本變量，隨著解的變換演進(jìn)，使用不很方便。故更常見的單純形算法結(jié)構(gòu)為：目標(biāo)與基xj解ZCBB-1pj

–CjCBB-1bxBB-1pjB-1b2009.11.1557改進(jìn)單純形方法的計算步驟：步驟1

在線性規(guī)劃標(biāo)準(zhǔn)模型的系數(shù)矩陣A中任選m個相互獨(dú)立的列向量構(gòu)成問題的初始基B。步驟2

求出現(xiàn)行解：xB=B–1b，計算非基變量的檢驗數(shù)：步驟3如果對應(yīng)的非基本變量

xk為進(jìn)入變量；并選擇比值對應(yīng)的基本變量xt為退出變量。步驟3

如果且，則終止算法，并輸出xB與Z。步驟4

如果且，同時，則選擇檢驗數(shù)2009.11.1558步驟5

如果

，且，則選擇基本變量為退出變量；并選擇比值對應(yīng)的非基本變量

xk為進(jìn)入變量。步驟6

如果

，且，，則選擇基本變量為退出變量；并選擇檢驗數(shù)

對應(yīng)的非基本變量xk為進(jìn)入變量。步驟7

令B

=

B-pi+pk，返回步驟2。2009.11.1559例2.13考慮以下線性規(guī)劃該線性規(guī)劃的基B中含有多少個行列向量和向量？答案：

均為2個(2)列向量p2和p3能否構(gòu)成一個可行基？答案：否，因為二

者線性相關(guān)：p3=2p2。(3)寫出B=(p1,p2)和B–1。答案：2009.11.1560(4)寫出(3)中的xB,cB。答案：(5)上述xB是可行解嗎？答案：是，因為(6)上述xB是最優(yōu)解嗎？答案：否，因為(7)哪個變量應(yīng)該進(jìn)入？哪個變量應(yīng)該退出？答案：因為對應(yīng)比值為：

，故

x3進(jìn)入，x2退出。2009.11.1561(8)確定新的xB和基B。答案：例2.14給定線性規(guī)劃已知試確定該基本解是否為最優(yōu)解？如果是，給出相應(yīng)結(jié)果；否則，確定進(jìn)出變量。2009.11.1562解：優(yōu)化性檢驗→此解非優(yōu)，變量x5進(jìn)入可行性檢驗→此解可行。退出變量？2009.11.1563計算比值

結(jié)論：原基本解可行，但非優(yōu)；相應(yīng)的進(jìn)入變量為

x5，退出變量為x4。2009.11.1564課堂練習(xí)給定線性規(guī)劃：已知：確定該基本解是否為最優(yōu)解？如果是，給出目標(biāo)值；否則，確定進(jìn)、出變量。2009.11.15652.8線性規(guī)劃的對偶理論

為了說明線性規(guī)劃多偶問題的數(shù)學(xué)模型，我們考慮以下生產(chǎn)計劃問題。

例2.15在生產(chǎn)管理和經(jīng)營活動中經(jīng)常需要從不同的角度來考察同一個問題。例如某工廠計劃生產(chǎn)I、II兩種產(chǎn)品，已知單位產(chǎn)品的利潤和生產(chǎn)所需的設(shè)備臺時及原材料A、B的消耗如下表所示。問應(yīng)如何安排生產(chǎn)計劃以使該工廠的獲利最多？

原材料消耗(公斤)所需設(shè)備臺時產(chǎn)品利潤（元/件）AB產(chǎn)品III40041223最大供應(yīng)量16128

2009.11.1566該生產(chǎn)計劃問題可以用以下數(shù)學(xué)模型來描述：式中x1、x2分別表示產(chǎn)品I、II的產(chǎn)量。

現(xiàn)在從另一角度來討論這個問題。假設(shè)該工廠決定不生產(chǎn)產(chǎn)品I、II，而將其所有資源出租或外售。這時工廠就要考慮每種資源的定價問題。2009.11.1567

設(shè)用y1，y2，y3分別表示出租單位設(shè)備臺時的租金和出讓單位原材料A、B的附加額。一個自然的比較方式是：1個單位設(shè)備臺時和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è)備和資源的出租與出讓計劃可以寫成下面的線性規(guī)劃模型：2009.11.1568此線性規(guī)劃問題被稱為上一線性規(guī)劃問題的對偶問題。

一般而言，原問題與對偶問題之間存在著下述關(guān)系：(1)每一個原問題的約束條件對應(yīng)著一個對偶問題的變量；(2)每一個原問題的變量對應(yīng)著一個對偶問題的約束條件；(3)原問題的模型系數(shù)與對偶問題的模型系數(shù)之間的對應(yīng)關(guān)系如下表所示。2009.11.1569x1x2…xn原關(guān)系對偶目標(biāo)minW對偶變量y1a11a12…a1n=b1無約束y2a21a22…a2n=b2無約束﹕﹕﹕

﹕﹕﹕﹕ymam1am2…amn=bm無約束對偶關(guān)系≥≥…≥Z*=maxZ=minW=W*原目標(biāo)maxZc1c2…cn原變量≥0≥0…≥0綜上所述，原問題與對偶問題之間的模型轉(zhuǎn)換可以寫為：2009.11.1570原問題與對偶問題之間的關(guān)系可用下圖說明：上圖表明，一般情形下

Z=cx<yb=W

，即企業(yè)獲得的最大利潤小于其掌握資源的應(yīng)有價值，只有當(dāng)資源的配置達(dá)到最優(yōu)狀態(tài)時，企業(yè)的利潤才等于其資源的價值，即：Z*=W*。

因為原問題的最優(yōu)解等于對偶問題的最優(yōu)解，即：故資源的影子價格，即對偶變量的計算公式為：2009.11.1571例2.16重新考察例2.15中的線性規(guī)劃→原問題的最優(yōu)單純形表為：目標(biāo)與基x

Ix

II解x1x2s1s2s3Z003/21/8014x11001/404s300-21/214x2011/2-1/802對偶問題的最優(yōu)解為：Y*=(3/2,1/8,0)，W*=Z*=142009.11.1572對偶問題的經(jīng)濟(jì)解釋

在線性規(guī)劃的數(shù)學(xué)模型中，所有≤形式的約束條件都在某種意義上反映了資源的有限性。該資源的實際狀態(tài)是多余還是短缺，由對應(yīng)松弛變量的數(shù)值來反映。S>0意味著該種資源尚未用完，是處于多余狀態(tài)；S=0說明資源已經(jīng)耗盡，屬于短缺狀態(tài)。對于短缺的資源，決策者不禁要問：如進(jìn)一步增加資源，是否有可能改進(jìn)收益？

前已述及，Z=cx<yb=W

。這里c為單位產(chǎn)品的價格或利潤，x為產(chǎn)品的產(chǎn)量，故不等式的左邊表示總收益，即一共多少錢。而右邊的b表示資源的數(shù)量，從簡單的量綱分析可知，對偶變量y必然表示單位資源具有的價值，故y也被稱為資源的影子價格。從而上述關(guān)系的物理含義被理解為：在一般情形下，總收益≤總資源價值，只有在最優(yōu)狀態(tài)下等式才會成立。因為只有短缺資源才具有增進(jìn)收益的潛力，故短缺資源的影子價格大于零，而富余資源的影子價格等于零。2009.11.1573

在上面討論的生產(chǎn)問題中，計算表明原料A的影子價格y2=0.125元，故只要原料A繼續(xù)處于緊缺狀態(tài)(s2=0)，每增加或減少1公斤的原料A，將增加或減少0.125元的總收益。如果市場上每公斤原料A的價格低于0.125元，則可考慮購進(jìn)原料A以擴(kuò)大生產(chǎn)規(guī)模；反之，如果每公斤原料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.15742.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ù)變化的靈敏度分析原則為：如果所有檢驗數(shù)的計算結(jié)果均大于零，則原最優(yōu)解繼續(xù)有效；否則，需在靈敏度分析的基礎(chǔ)上進(jìn)行相應(yīng)的改進(jìn)。2009.11.1575例2.18重新考慮例2.4中的問題：目標(biāo)與基X1X2S1S2S3S4解Z001/34/30038/3X2012/3-1/3004/3X110-1/32/30010/3S300-11103S400-2/31/3012/3如果價值系數(shù)從原來的c=(3,2)改變?yōu)閏=(5,4)，那么上表中非基變量的檢驗數(shù)變?yōu)椋涸顑?yōu)解繼續(xù)有效，但目標(biāo)值從38/3增加到22。2009.11.15762.非基本變量資源消耗系數(shù)票pj的變化分析

因為基本變量對應(yīng)資源消耗系數(shù)改變會導(dǎo)致基本矩陣B的改變，從而超出了靈敏度分析的范疇，故這里僅考慮非基本變量對應(yīng)資源消耗系數(shù)改變的情形。此時，pj的變化只影響單純形表的第j列，而其他列的數(shù)字不會發(fā)生變化。

例2.19給定線性規(guī)劃目標(biāo)與基X1X2S1S2S3S4解Z01020016S103/21-1/2002X111/201/2004S303/201/2105S40100012→若將p2=(2,1,1,1)T

改變成p2=(4,3,1,1)T，則Y=cBB-1=(0,2,0,0)，檢驗數(shù)λ2=yp2-c2=5>0，故原解繼續(xù)有效。2009.11.15773.增加新產(chǎn)品分析

如果在生產(chǎn)計劃問題中增加一個新的產(chǎn)品，線性規(guī)劃的數(shù)學(xué)模型必然增加一個新的變量。假定原線性規(guī)劃具有n個變量，則新增加的變量記為xn+1。由于線性規(guī)劃的約束條件沒有改變，故基本變量的個數(shù)維持不變，新增加的變量只能是非基本變量。由單純形表的特性可知，此時的單純型表將增加新的一列，其余不受影響。

例2.19在例2.4的生產(chǎn)計劃問題中增加一個新產(chǎn)品III，產(chǎn)量記為x3。c3=3/2,p3=(3/4,3/4,-1,0)T。其數(shù)學(xué)模型為：2009.11.15782009.11.1579

目標(biāo)與基X1X2X3S1S2S3S4解比值迭代1Z00-1/41/34/30038/3—X2011/42/3-1/3004/316/3X1101/4-1/32/30010/340/3S300-1-11103—S400-1/4-2/31/3012/3—迭代2Z010110014

X30418/3-4/30016/3

X11-10-11002

S30405/3-1/31025/3

S401000012

新的最優(yōu)解為：x1=2,x3=16/3,Z=142009.11.1580在線性規(guī)劃的單純形求解過程中，可行性主要來自以下兩方面的影響：資源供應(yīng)量b的改變或增加新的約束條件，現(xiàn)分別討論如下。

1.資源供應(yīng)量b的變化分析由改進(jìn)單純形的計算公式可知，資源供應(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.1581目標(biāo)與基X1X2S1S2S3S4解Z001/34/30023/3X2012/3-1/30010/3X110-1/32/3001/3S300-1110－2S400-2/31/301－4/3目標(biāo)與基X1X2S1S2S3S4解Z0005/31/307X20101/32/302X11001/3-1/301S1001-1-102S4000-1/3-2/310采用對偶單純形方法改進(jìn)，其結(jié)果為2009.11.1582

2.增加新的約束條件如果原最優(yōu)解滿足新的約束條件，則原解繼續(xù)有效；否則必須改進(jìn)。此時，由于多了一個約束條件，必然增添一個外加變量，而且是基本變量，故原單純形表需增加一行和一列。

例2.21在例2.17的線性規(guī)劃中增加約束條件：x1≤3目標(biāo)與基X1X2S1S2S3S4解Z001/34/30038/3X2012/3-1/3004/3X110-1/32/30010/3S300-11103S400-2/31/3012/3原最優(yōu)單純形表→x1=10/3+(1/3)s1－(2/3)s2∵x1+s5=3∴(1/3)s1–(2/3)s2+s5=－1/32009.11.1583目標(biāo)與基X1X2S1S2S3S4S5解Z001/34/300038/3X2012/3-1/30004/3X110-1/32/300010/3S300-111003S400-2/31/30102/3S5001/32/3001－1/3目標(biāo)與基X1X2S1S2S3S4S5解Z001000212X2011/2000-1/23/2X110000013S300-1/20103/25/2S400-1/20011/21/2S200-1/2100-3/21/2采用對偶單純形方法改進(jìn)2009.11.15842.9.3優(yōu)化性-可行性綜合分析(c+b)

理論上，兩類要素的任意組合都會導(dǎo)致一種新的靈敏度分析情形，但分析的原理和方法是相同的。

例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.1585

可見原解的優(yōu)化性和可行性均被破壞，其改進(jìn)過程如下表所示。2009.11.1586

基本變量X1X2S1S2S3S4解迭代1Z007/3-2/30041/3X2012/3-1/30010/3X110-1/32/3001/3S300-1110-2S400-2/31/301-4/3迭代2Z10200014X21/211/20007/2S23/20-1/21001/2S3-3/20-1/2010-5/2S4-1/20-1/2001-3/2迭代3Z005/302/3037/3X2011/301/308/3S200-1110-2X1101/30-2/305/3S400-1/30-1/31-2/3迭代4Z0005/37/309X20101/32/302S1001-1-102X11001/3-1/301S4000-1/3-2/3102009.11.1587第三章：運(yùn)輸模型與分配問題2009.11.1588第三章：運(yùn)輸模型與分配問題

運(yùn)輸模型解決單一貨物從多個產(chǎn)地向多個目的地輸送的計劃安排問題。典型的運(yùn)輸模型如以下圖表所示：

銷地產(chǎn)地12…n供應(yīng)量1c11c12…c1na12c21c22…c2na2:::…::mcm1cm2…cmnam需求量b1b2…bn

2009.11.1589

設(shè)貨物的運(yùn)輸成本與運(yùn)輸數(shù)量成正比。若用xij表示從產(chǎn)地i到銷地j的運(yùn)量，則在產(chǎn)銷平衡的前提下，要確定總運(yùn)費(fèi)最小的調(diào)運(yùn)方案，可求解以下線性規(guī)劃問題：2009.11.1590

例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)輸成本最??？

銷地

產(chǎn)地B1B2供應(yīng)量(輛)A1802151000A21001081500A3102681200需求量(輛)2300140037002009.11.1591為制訂最優(yōu)運(yùn)輸方案，可求解以下線性規(guī)劃模型：2009.11.1592不平衡運(yùn)輸問題標(biāo)準(zhǔn)化1.供應(yīng)量小于需求量：虛構(gòu)一產(chǎn)地(啞元)

銷地產(chǎn)地B1B2供應(yīng)量(輛)A1802151000A21001081300A3102681200需求量(輛)23001400

35003700

銷地產(chǎn)地B1B2供應(yīng)量(輛)A1802151000A21001081300A3102681200A400200需求量(輛)23001400

350037002009.11.15932.供應(yīng)量大于需求量：虛構(gòu)一銷地(啞元)

銷地產(chǎn)地B1B2供應(yīng)量(輛)A1802151000A21001081500A3102681200需求量(輛)19001400

37003300

銷地產(chǎn)地B1B2B3(啞元)供應(yīng)量(輛)210010801500A31026801200需求量(輛)19001400400

370037002009.11.1594運(yùn)輸問題表上作業(yè)法一.確定初始解：最小成本法(LeastCost)例3.2考慮下面的運(yùn)輸問題：

銷地產(chǎn)地B1B2B3B4供應(yīng)量(輛)A1100201115A212792025A301416185需求量(輛)5151510452009.11.15952009.11.1596二.判定解的優(yōu)化性：閉合路線法

2009.11.15972009.11.1598三.改進(jìn)運(yùn)輸方案：閉合路線法

2009.11.1599分配問題：匈牙利算法

設(shè)有m個不同工件需進(jìn)行某種加工，現(xiàn)有n臺不同機(jī)器可以承擔(dān)此加工任務(wù)，但由于每臺機(jī)器的性能不同，加工不同工件所需的費(fèi)用和效率都不一樣。于是產(chǎn)生了應(yīng)該將哪一個工件分配給哪一臺機(jī)器加工所需的總費(fèi)用最小的問題。這類問題被稱為分配問題或指派問題，它可以用下面的分配表加以描述：

機(jī)器工件12…n數(shù)量1c11c12…c1n12c21c22…c2n1………

……mcm1cm2…cmn1數(shù)量11…1

2009.11.15100

匈牙利算法具體步驟：步驟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)記的行中所有含0元素的列作一標(biāo)記，然后對有標(biāo)記的列中含0元素的行作一標(biāo)記，如此反復(fù)進(jìn)行，直至找不到可標(biāo)記的行或列為止。最后劃去沒有標(biāo)記的行和有標(biāo)記的列，即為覆蓋所有0元素的最少直線數(shù)。步驟5

增加零.將沒有被直線覆蓋的元素減去其中的最小元素，并將各直線交點上的元素加上該最小元素。然后返回步驟2。2009.11.15101例3.4求解下表所示的分配問題1463971094511787850352203201733230032220020143320003222002014332000211300200324200√21130√20√32420√2009.11.15102第四章：整數(shù)線性規(guī)劃2009.11.151034.2分枝定界法例4.2求解以下整數(shù)線性規(guī)劃問題2009.11.151042009.11.151054.3割平面法

分枝定界法本質(zhì)上是一種對線性規(guī)劃可行域?qū)嵤┓指钋蠼獾姆椒?，但分割方式比較被動和單一，故其效率不高。割平面方法的總體思路與分枝定界法相似，也是通過切割作業(yè)從線性規(guī)劃中尋求整數(shù)解。但割平面方法的切割方式主動靈活，切割目標(biāo)明確具體，旨在將整數(shù)規(guī)劃的最優(yōu)點造就為一個普通線性規(guī)劃的頂點，從而有的放矢地求解整數(shù)規(guī)劃問題，故其效率較高。2009.11.15106例4.3求解以下整數(shù)線性規(guī)劃問題2009.11.15107純整數(shù)規(guī)劃分量切割

分量切割方程的推導(dǎo)要求整數(shù)規(guī)劃的數(shù)學(xué)模型中所有變量的系數(shù)和常數(shù)都必須是整數(shù)。為方便起見，將問題的最優(yōu)單純形表改寫為以下形式：2009.11.15108設(shè)

xi取非整數(shù)值，那么第

i個約束等式被稱為源行，寫為：

(分量切割方程)2009.11.15109運(yùn)用上述分量切割方程重解例4.3中的整數(shù)規(guī)劃問題基變量x1x2x3x4解Z0028/1115/1163x2017/221/227/2x110-1/223/229/2

2009.11.15110基變量x1x2x3x4s1解Z0028/1115/11063x2017/221/2207/2x110-1/223/2209/2s100-7/22-1/221-1/2基變量x1x2x3x4s1解Z0001859x2010013x11001/7-1/732/7x30011/7-22/711/72009.11.15111基變量x1x2x3x4s1s2解Z00018059x20100103x11001/7-1/7032/7x30011/7-22/7011/7s2000-1/7-6/71-4/7基變量x1x2x3x4s1s2解Z00002755x20100103x11000-114x30010-411x400016-74x1=4,x2=3，Z=552009.11.15112約束條件還原2009.11.15113混合整數(shù)規(guī)劃分量切割設(shè)

xk

是問題中要求取整值的變量，以其在相應(yīng)單純形最優(yōu)表中的表示式為源行，即：如果

xk≤[βk],則如果

xk≥[βk]+1,則令J+表示

的

j的集合,則

令J

-

表示

的

j集合,則(混合切割方程)

2009.11.15114

例4.4重新考慮例4.3中的整數(shù)規(guī)劃問題，假設(shè)只有x1必須取整數(shù)值，則源行表示式為：這里

J

-={3},J+={4},f

1=1/2。其混合切割方程式為：基變量X1X2X3X4S1解Z0028/1115/11063X2017/221/2207/2X110-1/223/2209/2S100-1/22-3/221-1/2Z0023/1101058X20110/330-1/310/3X110-1/11014X4001/31-22/311/3

2009.11.15115第五章：圖論與網(wǎng)絡(luò)分析2009.11.151165.1圖論基礎(chǔ)

現(xiàn)實生活中的許多事物都可以用某種圖形來描述，這種圖形是由一些點和點間的連線組成的。例如，可用圖形表示某地區(qū)各單位之間的業(yè)務(wù)往來關(guān)系，在這張關(guān)系圖里以點代表單位，以兩點之間的連線表示這兩個單位之間有業(yè)務(wù)往來。顯然，對于這種圖形，我們的興趣在于圖中有多少個點和哪些點之間有線相連接，至于點的具體位置和連線的長短曲直都無關(guān)緊要?？梢妶D論中的圖與常見的幾何圖、建筑圖是不同的。2009.11.15117

定義5.1圖G是由n個點元素的非空有限集合V和V中給定的m個偶對構(gòu)成的邊集合E以及從邊集E到點集V上的函數(shù)F組成的三元組，記為G(V,E,F)，或簡記為G(V,E)。

例5.1設(shè)有圖G(V,E,F)：V={v1,v2,v3},E={e1,e2,e3,e4,e5},f(e1)=(v1,v3),f(e2)=(v1,v2),f(e3)=(v1,v2),f(e4)=(v2,v3),f(e5)=(v3,v3)。則圖G可用圖5.1表示。

若邊e所對應(yīng)的點偶對是有序的，則稱e為有向邊。若邊e所對應(yīng)的點偶對是無序的，則稱e為無向邊。完全由有向邊構(gòu)成的圖稱為有向圖，完全由無向邊構(gòu)成的圖稱為無向圖，由有向邊和無向邊混合構(gòu)成的圖稱為混合圖。2009.11.15118(1)令p

=|V|表示頂點數(shù),q=|E|表示邊數(shù)。圖中p=3,q=5。(2)如果邊e=(u,v)∈E,則稱u,v為邊e的端點,e為u,v的關(guān)聯(lián)邊。(3)具有關(guān)聯(lián)邊的頂點稱為鄰點,與同一頂點關(guān)聯(lián)的邊為鄰邊。(4)如果邊

e的兩個端點相同,稱

e

為環(huán);如果連接兩點的邊不

只一條,這些邊稱為多重邊。(5)一個無環(huán)、無多重邊的圖被稱為簡單圖。(6)沒有任何邊的圖稱為空圖。(7)圖中頂點v的次定義為與v相關(guān)聯(lián)的邊的數(shù)目,記為d(v)。(8)次等于1的頂點稱為懸掛點，其關(guān)聯(lián)邊稱為懸掛邊，次等

于0的頂點稱為孤立點。(9)如果圖G中,使得G的每條邊的一個端點屬于集合X，而另一端點屬于集合Y，則稱G為二分圖。2009.11.15119

簡單圖二分圖完全圖原圖子圖生成子圖2009.11.15120(13)圖中點邊交替的有限非零序列,

如果滿足ei=(vi-1,vi),則稱W是從v0到vk的鏈。如v0=vk,

則W為閉鏈;否則W為開鏈。在簡單圖中,鏈也可以用

頂點序列來表示,即。(14)如果鏈中所有的邊都不同,則W為簡單鏈;如果鏈中所

有的頂點都不同,則W為初等鏈。開的初等鏈稱為路；

閉的初等鏈稱為圈(或回路)。W1=(v0,v1,v2,v1,v3)是鏈,但不是簡單鏈W2=(v0,v1,v2,v4,v1,v3)是簡單鏈,但不是初等鏈W3=(v0,v1,v2,v4,v3)是初等鏈,也是通路W4=(v1,v2,v4,v3,v1)是初等鏈,也是回路

2009.11.15121(15)如果圖G中任意兩點之間都存在一條路,則稱G為連通

圖;否則為不連通圖。。(16)圖G中的任意最大連通子圖被稱為G的連通分圖。不連通圖及其連通分圖(17)給定圖G1和G2,如果存在點函數(shù)f,使得,且如果,則有,那么G1和G2被

稱為同構(gòu)圖。