運(yùn)籌學(xué)線性規(guī)劃理論及應(yīng)用講解

1、第一章線性規(guī)劃理論及應(yīng)用線性規(guī)劃 Linear Programming（LP）1引 言解決有限資源在有競(jìng)爭(zhēng)的使用方向中如何進(jìn)行最佳分配。線性規(guī)劃是運(yùn)籌學(xué)的一個(gè)重要分支，也是運(yùn)籌學(xué)中應(yīng)用最廣泛的方法之一。自1947年旦茨基（G. B. Dantzig）提出了一般線性規(guī)劃問題求解的方法單純形法（simplex method）之后，線性規(guī)劃已被廣泛應(yīng)用于解決經(jīng)濟(jì)管理和工業(yè)生產(chǎn)中遇到的實(shí)際問題。調(diào)查表明，在世界500家最大的企業(yè)中，有85%的企業(yè)都曾使用過線性規(guī)劃解決經(jīng)營(yíng)管理中遇到的復(fù)雜問題。線性規(guī)劃的使用為應(yīng)用者節(jié)約了數(shù)以億萬計(jì)的資金。線性規(guī)劃 Linear Programming（LP）2本章中我

2、們將討論什么是線性規(guī)劃問題，線性規(guī)劃問題的數(shù)學(xué)表示，基本理論、概念和求解方法。線性規(guī)劃問題是什么樣的一類問題呢？ 線性規(guī)劃 Linear Programming（LP）3線性規(guī)劃 Linear Programming（LP）1.線性規(guī)劃模型 Linear Programming Model或 Linear Optimization Model 用線性規(guī)劃方法解決實(shí)際問題的第一步是建立能夠完整描述和反映實(shí)際問題的線性規(guī)劃模型。4線性規(guī)劃 Linear Programming（LP） 通常建立LP模型有以下幾個(gè)步驟：1. 確定決策變量： 決策變量是模型要確定的未知變量，也是模型最重要的參數(shù)，是決策

3、者解決實(shí)際問題的控制變量。2. 確定目標(biāo)函數(shù)： 目標(biāo)函數(shù)決定線性規(guī)劃問題的優(yōu)化方向，是模型的重要組成部分。實(shí)際問題的目標(biāo)可表示為決策變量的一個(gè)線性函數(shù)，并根據(jù)實(shí)際問題的優(yōu)化方向求其最大化（max）或最小化（min）。3. 確定約束方程：一個(gè)正確的線性規(guī)劃模型應(yīng)能通過約束方程來描述和反映一系列客觀條件或環(huán)境的限制，這些限制通過一系列線性等式或不等式方程組來描述。4. 變量取值限制：一般情況下，決策變量取正值（非負(fù)值）。因此，模型中應(yīng)有變量的非負(fù)約束即Xj0，但也存在例外。5線性規(guī)劃 Linear Programming（LP）例1 某工廠可生產(chǎn)甲、乙兩種產(chǎn)品，需消耗煤、電、油三種資源。現(xiàn)將有關(guān)數(shù)

4、據(jù)列表如下，試擬訂使總收入最大的生產(chǎn)計(jì)劃方案。資源單耗 產(chǎn)品資源 甲 乙 資源限量 煤 電 油 9 4 4 5 3 10 360 200 300單位產(chǎn)品價(jià)格 7 126線性規(guī)劃模型三要素：1.決策變量：需決策的量，即待求的未知數(shù)；2.目標(biāo)函數(shù)：需優(yōu)化的量，即欲達(dá)的目標(biāo)，用決策變量的表達(dá)式表示；3.約束條件：為實(shí)現(xiàn)優(yōu)化目標(biāo)需受到的限制，用決策變量的等式或不等式表示。7在本例中決策變量：甲、乙產(chǎn)品的計(jì)劃產(chǎn)量，記為x1,x2；目標(biāo)函數(shù)：總收入，記為z, 則z=7x1+12x2，為體現(xiàn)對(duì)其追求極大化，在z的前面冠以極大號(hào)Max；約束條件：分別來自資源煤、電、油限量的約束，和產(chǎn)量非負(fù)的約束，表示為8s.

5、t. 9x1 + 4x2 360 4x1 +5x2 200 3x1 +10 x2 300 x1 ，x2 09線性規(guī)劃模型的一個(gè)基本特點(diǎn)： 目標(biāo)和約束均為變量的線性表達(dá)式如果模型中出現(xiàn)如x12+2lnx2-1/x3的非線性表達(dá)式，則不屬于線性規(guī)劃。10例2 某市今年要興建大量住宅,已知有三種住宅體系可以大量興建，各體系資源用量及今年供應(yīng)量見下表： 資源 住宅體系 造價(jià)（元/M) 鋼材（公斤/M) 水泥（公斤/M) 磚（塊/M) 人工（工日/M)磚混住宅105121102104.5壁板住宅13530190-3.0大模住宅12025180-3.5資源限量11000（千元）20000（噸）150000

6、（噸）147000（千塊）4000 (千工日）要求在充分利用各種資源條件下使建造住宅的總面積為最大，求建造方案。11 解: 設(shè)今年計(jì)劃修建磚混、壁板、大模住宅各為 x1,x2, x3, 為總面積,則本問題的數(shù)學(xué)模型為:s.t. 0.105x1 + 0.135x2 + 0.120 x3 110000 0.012x1 + 0.030 x2 + 0.025x3 20000 0.110 x1 + 0.190 x2 + 0.180 x3 150000 0.210 x1 147000 0.0045x1 + 0. 003x2 + 0.0035x3 4000 x1 ,x2 ,x3 0Max z = x1 +

7、x2 + x3前蘇聯(lián)的尼古拉也夫斯克城住宅興建計(jì)劃采用了上述模型，共用了12個(gè)變量，10個(gè)約束條件。12練習(xí)：某畜牧廠每日要為牲畜購買飼料以使其獲取A、B、C、D四種養(yǎng)分。市場(chǎng)上可選擇的飼料有M、N兩種。有關(guān)數(shù)據(jù)如下：試決定買M與N二種飼料各多少公斤而使支出的總費(fèi)用為最少？ 售價(jià) （元/公斤） 每公斤含營(yíng)養(yǎng)成分 A B C DM10 0.1 0 0.1 0.2N4 0 0.1 0.2 0.1牲畜每日每頭需要量 0.4 0.6 2.0 1.713解：設(shè)購買M、N飼料各為x1,x2 ，則Min z = 10 x1 + 4x2s.t. 0.1x1 + 0 x2 0.4 0 x1 + 0.1x2 0.

8、6 0.1x1 + 0.2x2 2 0.2x1 + 0.1x2 1.7 x1 ,x2 , 0142. 線性規(guī)劃的數(shù)學(xué)模型線性規(guī)劃模型的一般形式：以MAX型、約束為例決策變量: x1 , , xn目標(biāo)函數(shù)：Max z= c1x1 + + cn xn約束條件：s.t. a11x1 + + a1n xn b1 am1x1 + + amn xn bm x1 , , xn 015模型一般式的矩陣形式X=(x1 , , xn)T, C=(c1 , , cn), A=(aij) mxn , b=(b1 , , bn)T則模型可表示為 Max z=CX s.t. AX b X 0以例1為例，寫出其矩陣形式。1

9、6 一般地 Max z=CX s.t. AX b X 0中 X 稱為決策變量向量，C 稱為價(jià)格系數(shù)向量， A 稱為技術(shù)系數(shù)矩陣，b 稱為資源限制向量。17線性規(guī)劃 Linear Programming（LP）2.線性規(guī)劃問題的求解：（圖解法） 如何求解一般的線性規(guī)劃呢？ 下面我們分析一下簡(jiǎn)單的情況 只有兩個(gè)決策變量的線性規(guī)劃問題，這時(shí)可以通過圖解的方法來求解。圖解法具有簡(jiǎn)單、直觀、便于初學(xué)者窺探線性規(guī)劃基本原理和幾何意義等優(yōu)點(diǎn)。18圖解法是用畫圖的方式求解線性規(guī)劃的一種方法。它雖然只能用于解二維（兩個(gè)變量）的問題，但其主要作用并不在于求解，而是在于能夠直觀地說明線性規(guī)劃解的一些重要性質(zhì)。19線

10、性規(guī)劃 Linear Programming（LP）例1max z = 2x1 + x2 5x2 15s.t. 6x1 + 2x2 24 x1 + x2 5 x1 ，x2 0201.做約束的圖形 先做非負(fù)約束的圖形；再做資源約束的圖形；最后找出公共部分。2.做目標(biāo)的圖形對(duì)于目標(biāo)函數(shù)：Max z= c1x1 + + cn xn任給z二不同的值，便可做出相應(yīng)的二直線，用虛線表示。3.求出最優(yōu)解21 將目標(biāo)直線向使目標(biāo)z優(yōu)化的方向移，直至可行域的邊界為止，這時(shí)其與可行域的“切”點(diǎn)X*即最優(yōu)解。 如在例1中， X*是可行域的一個(gè)角點(diǎn)，經(jīng)求解交出的二約束直線聯(lián)立的方程可解得X*=(3.5,1.5) 由圖

11、解法的結(jié)果得到例1的最優(yōu)解，還可將其代入目標(biāo)函數(shù)求得相應(yīng)的最優(yōu)目標(biāo)值z(mì)=8.522線性規(guī)劃 Linear Programming（LP）max z = 2x1 + x2 5x2 15s.t. 6x1 + 2x2 24 x1 + x2 5 x1 ，x2 023線性規(guī)劃 Linear Programming（LP）例2 max z= 2X1 + X2 X1 + 1.9X2 3.8 X1 - 1.9X2 3.8 s.t. X1 + 1.9X2 10.2 X1 - 1.9X2 -3.8 X1 ，X2 024線性規(guī)劃 Linear Programming（LP）max z = 2X1 + X2x1x2o

12、X1 - 1.9X2 = 3.8()X1 + 1.9X2 = 3.8()X1 - 1.9X2 = -3.8 ()X1 + 1.9X2 = 10.2()4 = 2X1 + X2 20 = 2X1 + X2 17.2 = 2X1 + X2 11 = 2X1 + X2 Lo： 0 = 2X1 + X2 （7.6，2）Dmax Zmin Z此點(diǎn)是唯一最優(yōu)解，且最優(yōu)目標(biāo)函數(shù)值 max Z=17.2可行域25線性規(guī)劃 Linear Programming（LP）max z = 3X1+5.7X2x1x2oX1 - 1.9X2 = 3.8 ()X1 + 1.9X2 = 3.8()X1 - 1.9X2 = -

13、3.8()X1 + 1.9X2 = 10.2 ()（7.6，2）DL0： 0=3X1+5.7X2 max Z min Z（3.8，4）34.2 = 3X1+5.7X2 綠色線段上的所有點(diǎn)都是最優(yōu)解這種情形為有無窮多最優(yōu)解，但是最優(yōu)目標(biāo)函數(shù)值max Z=34.2是唯一的?？尚杏?6線性規(guī)劃 Linear Programming（LP）min z = 5X1+4X2x1x2oX1 - 1.9X2 = 3.8 ()X1 + 1.9X2 = 3.8()X1 - 1.9X2 = -3.8()X1 + 1.9X2 = 10.2 ()DL0： 0=5X1+4X2 max Z min Z 8=5X1+4X2

14、43=5X1+4X2 （0，2）可行域此點(diǎn)是唯一最優(yōu)解27練習(xí)：用圖解法求解下面的線性規(guī)劃。min z = 6x1 +4 x2 s.t. 2x1 + x2 1 3x1 + 4x2 1.5 x1 ，x2 028二維線性規(guī)劃的可行域是一個(gè)什么形狀？多邊形，而且是“凸”形的多邊形。最優(yōu)解在什么位置獲得？在邊界，而且是在某個(gè)頂點(diǎn)獲得。29線性規(guī)劃 Linear Programming（LP）圖解法的啟示線性規(guī)劃問題解的可能情況 a.唯一最優(yōu)解 b.無窮多最優(yōu)解 c.無解（沒有有界最優(yōu)解，無可行解）若線性規(guī)劃問題的可行域非空，則可行域是一個(gè)凸集；若線性規(guī)劃問題的最優(yōu)解存在，則一定可以在可行域的凸集的某個(gè)

15、頂點(diǎn)上達(dá)到。（為什么？）30線性規(guī)劃 Linear Programming（LP）凸集凹集凸多面體是凸集的一種。所謂凸集是指：集中任兩點(diǎn)的連線仍屬此集。凸集中的“極點(diǎn)”，又稱頂點(diǎn)或角點(diǎn)，是指它屬于凸集，但不能表示成集中某二點(diǎn)連線的內(nèi)點(diǎn)。如多邊形的頂點(diǎn)。31線性規(guī)劃 Linear Programming（LP）3.單純形法單純形方法是G.B.Danzig于1947年首先發(fā)明的。近50年來，一直是求解線性規(guī)劃的最有效的方法之一，被廣泛應(yīng)用于各種線性規(guī)劃問題的求解。盡管在其后的幾十年中，又有一些算法問世，但單純形法以其簡(jiǎn)單實(shí)用的特色始終保持著絕對(duì)的“市場(chǎng)”占有率。本節(jié)討論單純形法的基本概念、原理及算

16、法。32線性規(guī)劃 Linear Programming（LP）線性規(guī)劃問題的標(biāo)準(zhǔn)形式（預(yù)備知識(shí)一）1、目標(biāo)函數(shù)極大化 “ max ”2、等式約束條件 “ = ” 3、變量非負(fù) “ xj 0 ” max z = c1x1 + c2x2 + + cnxn a11x1 + a12x2 + a1nxn = b1 a21x1 + a22x2 + a2nxn = b2 s.t. am1x1 + am2x2 + amnxn = bm xj 0 （j=1，2 ， n）33線性規(guī)劃 Linear Programming（LP）化標(biāo)準(zhǔn)形式的一般步驟1、目標(biāo)函數(shù)極小化“極大化”2、約束條件的右端項(xiàng) bi0 “bi0

17、” 3、約束條件為不等式 或 “=”4、取值無約束（自由）變量“非負(fù)變量”5、取值非正變量“非負(fù)變量”34線性規(guī)劃 Linear Programming（LP）給定線性規(guī)劃問題（標(biāo)準(zhǔn)形式）max z = c1x1 + c2x2 + + cnxn a11x1 + a12x2 + a1nxn = b1 a21x1 + a22x2 + a2nxn = b2s.t. am1x1 + am2x2 + amnxn = bm xj 0 （j=1，2 n）標(biāo)準(zhǔn)型的特征：max型；等式約束；非負(fù)約束35練習(xí)：將例1的約束化為標(biāo)準(zhǔn)型s.t. 9x1 + 4x2 360 4x1 +5x2 200 3x1 +10 x

18、2 300 x1 ，x2 036一般地，記松弛變量的向量為Xs，則s.t. AX b X 0s.t. AX+IXs= b X, Xs 0s.t. AX b X 0s.t. AX-IXs = b X, Xs 037線性規(guī)劃 Linear Programming（LP）線性規(guī)劃問題的解的概念 （預(yù)備知識(shí)二） 可行解 最優(yōu)解 基矩陣、基變量 基解（基本解） 基可行解 38（1）可行解與最優(yōu)解可行解：滿足全體約束的解，記為X；最優(yōu)解：可行解中最優(yōu)的，記為X*，則對(duì)任可行解X，有CXCX*. 直觀上，可行解是可行域中的點(diǎn)，是一個(gè)可行的方案；最優(yōu)解是可行域中的頂點(diǎn)，是一個(gè)最優(yōu)的方案。39（2）基矩陣和基變

19、量基矩陣(簡(jiǎn)稱基)：系數(shù)陣A中的m階可逆子陣，記為B；其余部分稱為非基矩陣，記為N?；蛄浚夯鵅中的列；其余稱非基向量。基變量：與基向量Pj對(duì)應(yīng)的決策變量xj，記其組成的向量為XB；與非基向量對(duì)應(yīng)的變量稱非基變量，記其組成的向量為XN。40例3 下面為某線性規(guī)劃的約束s.t. x1 + 2x2 + x3 =1 2x1-x2 + x4=3 x1 ，x2 ， x3 ，x4 0請(qǐng)例舉出其基矩陣和相應(yīng)的基向量、基變量。41解：本例中，A=2 1 02 -1 0 1A中的2階可逆子陣有B1=00 1其相應(yīng)的基向量為P3,P4基變量為x3, x4，XB1=x3x442其相應(yīng)的基向量為P1,P2基變量為x1

20、, x2，XB2=x1x2B2=22 -1問題：本例的A中一共有幾個(gè)基？ 一般地，mn 階矩陣A中基的個(gè)數(shù)最多有多少個(gè)？43（3）基本解與基本可行解當(dāng)A中的基B取定后，不妨設(shè)B表示A中的前m列,則可記A=(B N),相應(yīng)地X =(xB xN )T ,約束中的AX= b可表示為（B N) =b ，即 XB = B-1b - B-1NXN ,當(dāng)取XN = 0時(shí)，有XB = B-1b ， X =B-1b 0 xBxN稱AX= b的解X = 為線性規(guī)劃的一個(gè)基本解；B-1b 044 可見：一個(gè)基本解是由一個(gè)基決定的。注意：基本解僅是資源約束的解，并未要求其非負(fù)，因此其未必可行。 稱非負(fù)的基本解為基本可

21、行解（簡(jiǎn)稱基可行解）。45在上例中求相應(yīng)于基B1和B2的可行解，它們是否基本可行解？解：B1=00 1B2-1=1/5 2/52/5 -1/5B1-1b=13 相應(yīng)于基B1的基本解為X=（0，0，1，3）T，是基本可行解。B2=22 -1B1-1=00 1B2 -1b=7/5-1/5 相應(yīng)于基B2的基本解為X=（7/5，-1/5，0，0）T，不是基本可行解。46上二組概念間的聯(lián)系：系數(shù)陣A中可找出若干個(gè)基B每個(gè)基B都對(duì)應(yīng)于一個(gè)基本解非負(fù)的基本解就是基本可行解問題1：幾種解之間的關(guān)系是什么？問題2：基本可行解是可行域中的哪些點(diǎn)？47線性規(guī)劃 Linear Programming（LP）線性規(guī)劃基

22、本定理基本定理 1 線性規(guī)劃所有可行解組成的集合S= X | AX = b，X 0 是凸集。基本定理 2 X是線性規(guī)劃問題的基本可行解的充要條件為是 X 是凸集S= X | AX = b，X 0 的極點(diǎn)。基本定理 3 給定線性規(guī)劃問題， A是秩為 m 的 mn 矩陣， （i） 若線性規(guī)劃問題存在可行解，則必存在基本可行性解 （ii）若線性規(guī)劃問題存在有界最優(yōu)解，則必存在有界最優(yōu)基本可行解。48（1）線性規(guī)劃的可行域是一個(gè)凸多面體。（2）線性規(guī)劃可行域的頂點(diǎn)與基本可行解一一對(duì)應(yīng)。（3）線性規(guī)劃的最優(yōu)解（若存在的話）必能在可行域的頂點(diǎn)獲得。49單純形法的步驟確定初始基可行解檢驗(yàn)其是否最優(yōu)是stop

23、尋找更好的基本可行解否單純形法是一種迭代的算法，它的思想是在可行域的頂點(diǎn)基本可行解中尋優(yōu)。由于頂點(diǎn)是有限個(gè),因此，算法經(jīng)有限步可終止。方法前提：模型化為標(biāo)準(zhǔn)型50線性規(guī)劃 Linear Programming（LP）1 確定初始基可行解由于基可行解是由一個(gè)可行基決定的，因此，確定初始基可行解X0相當(dāng)于確定一個(gè)初始可行基B0。方法：若A中含I，則B0=I；若A中不含I，則可用人工變量法構(gòu)造一個(gè)I。問題：若B0=I，則X0=？51線性規(guī)劃 Linear Programming（LP）2 最優(yōu)性檢驗(yàn)把目標(biāo)函數(shù)用非基變量表示：AX=b XB=B-1b-B-1NXNZ=CX=CBB-1b+(CN-CBB

24、-1N)XN矩陣分塊檢驗(yàn)數(shù)向量，記為。當(dāng)0時(shí)，當(dāng)前解為最優(yōu)解。52線性規(guī)劃 Linear Programming（LP）方法：（1）計(jì)算每個(gè)xj的檢驗(yàn)數(shù)=cj-CBB-1pj（2）若所有j0 ，則當(dāng)前解為最優(yōu)；否則，至少有k0 ，轉(zhuǎn)3。53線性規(guī)劃 Linear Programming（LP）3 尋找更好的基可行解由于基可行解與基對(duì)應(yīng)，即尋找一個(gè)新的基可行解，相當(dāng)于從上一個(gè)基B0變換為下一個(gè)新的基B1，因此，本步驟也稱為基變換?；儞Q的原則改善:z1 z0 可行:B -1b0變換的方法：（P1, Pl , Pk , Pn）54線性規(guī)劃 Linear Programming（LP）進(jìn)基：保證“改

25、善”，令0對(duì)應(yīng)的Pk進(jìn)基出基：保證“可行”，令XB=B-1b-B-1NXN0可決定出基方法：令k=max j0 對(duì)應(yīng)的Pk進(jìn)基；令l =min i =（B -1b）i/(B -1Pk) i |(B-1Pk)i 0 對(duì)應(yīng)的Pl出基；i稱作檢驗(yàn)比。55 以例1為例，可按上述單純形法的步驟求出其最優(yōu)解，其大致的過程如下。（1）先將模型化為標(biāo)準(zhǔn)型s.t. 9x1 + 4x2 + x3 = 360 4x1 +5x2 + x4 = 200 3x1 +10 x2 + x5 =300 x1 ，x2 ，x3 ，x4 ，x5 0max z= 7X1 + 12X256(2) 確定初始基可行解、檢驗(yàn) 1 1B0=,B

26、0 -1b =(360,200,300) T ,X0 =(0,0,360,200,300) T 計(jì)算檢驗(yàn)數(shù)確定進(jìn)基向量為P2 ,再計(jì)算檢驗(yàn)比確定出基向量為P5 ；57（3）換基、計(jì)算下一個(gè)基可行解、再檢驗(yàn)，直至最優(yōu) 4 1 5 10B1=,B1 -1b =(240,50,30) T ,X1 =(0,30,240,50, 0) T ; 計(jì)算檢驗(yàn)數(shù)確定進(jìn)基向量為P1 ,再計(jì)算檢驗(yàn)比確定出基向量為P4 ；589 4 0 4 50 3 10B2=,B2 -1b =(84,20,24) T ,X2 =(20,24,84,0, 0) T ;計(jì)算檢驗(yàn)數(shù)均非正，當(dāng)前解為最優(yōu)。問題：當(dāng)模型規(guī)模較大時(shí)，計(jì)算量很大

27、。 事實(shí)上，單純形法的實(shí)現(xiàn)是在單純形表上完成的。59三、單純形表單純形表是基于單純形法的步驟設(shè)計(jì)的計(jì)算格式，是單純形法的具體實(shí)現(xiàn)?；仡檰渭冃畏ú襟EB0 X0=B0 -1b 0j = cj CB0 B0 -1 Pj i = min (B0 -1b)i(B01Pk)iB1需計(jì)算B -1b需計(jì)算B 1A因此，單純形表的主體內(nèi)容是B 1(b A)60 而相鄰兩個(gè)B只有一列不同，故相鄰兩個(gè)B 1也可通過初等行變換求得。由此設(shè)計(jì)了基于初等行變換迭代計(jì)算的單純形表。即 B0 1(b A)B1 1(b A)B2 1(b A).61單純形表的主要結(jié)構(gòu)： C XB-1bB-1A問題：第一張表的B-1=？單位陣I。

28、檢驗(yàn)數(shù)的公式是什么？j = cj CB B -1 Pj B -1 Pj在哪里？ B-1A中的第j列62例1max z= 7X1 + 12X2s.t. 9x1 + 4x2 360 4x1 +5x2 200 3x1 +10 x2 300 x1 ，x2 0s.t. 9x1 + 4x2 + x3 = 360 4x1 +5x2 + x4 = 200 3x1 +10 x2 + x5 =300 x1 ，x2 ，x3 ，x4 ，x5 0化為標(biāo)準(zhǔn)型max z= 7X1 + 12X263XB CB B-1b 7 12 0 0 0 X1 X2 X3 X4 X5 X3 0 360X4 0 200 X5 0 300 9

29、 4 1 0 0 4 5 0 1 0 3 10 0 0 1 7 12 0 0 0的計(jì)算:1 = c1 CBB-1 P=7-0,0,0 =7943單純形表：64單純形表:XB CB B-1b 7 12 0 0 0 X1 X2 X3 X4 X5 X3 0 360X4 0 200 X5 0 300 9 4 1 0 0 4 5 0 1 0 3 10 0 0 1904030 7 12 0 0 0主元素65單純形表:XB CB B-1b 7 12 0 0 0 X1 X2 X3 X4 X5 X3 0 360X4 0 200 X5 0 300 9 4 1 0 0 4 5 0 1 0 3 10 0 0 1904

30、030 7 12 0 0 0 X3 0 240 X4 0 50 X2 12 307.8 0 1 0 -0.42.5 0 0 1 -0.50.3 1 0 0 0.13.4 0 0 0 -1.2或1 = c1 CBB-1 P1=7-0,0,12 =3.47.82.5 0.3以10為主元進(jìn)行初等行變換66單純形表:XB CB B-1b 7 12 0 0 0 X1 X2 X3 X4 X5 X3 0 360X4 0 200 X5 0 3009 4 1 0 04 5 0 1 03 10 0 0 19040307 12 0 0 0 X3 0 240X4 0 50 X2 12 307.8 0 1 0 -0.4

31、2.5 0 0 1 -0.50.3 1 0 0 0.130.8201003.4 0 0 0 -1.2或5 = c5 CBB-1 P5=0-0,0,12 =-1.2-0.4-0.5 0.1以10為主元進(jìn)行初等行變換67XB CB B-1b7 12 0 0 0 X1 X2 X3 X4 X5 X3 0 240 X4 0 50 X2 12 307.8 0 1 0 -0.42.5 0 0 1 -0.50.3 1 0 0 0.130.8201003.4 0 0 0 -1.2 X3 0 84 X1 7 20 X2 12 240 0 1 -3.12 1.161 0 0 0.4 -0.20 1 0 0.12 0

32、.160 0 0 -1.36 -0.52以2.5為主元進(jìn)行初等行變換68X *=(20,24,84,0, 0) T ;z *=428注：每一列的含義：B-1(bA)=(B-1b, B-1P1,，B-1Pn)每個(gè)表中的B和B-1的查找:B從初表中找；B-1從當(dāng)前表中找，對(duì)應(yīng)于初表中的I的位置。終表分析最優(yōu)解和(B*)-1的查找。69練習(xí)：用單純形法求解下面的線性規(guī)劃s.t. 3x1 + 5x215 5x1 +2x210 x1 ，x2 0max z= 2.5X1 + X2問題：本題的單純形終表檢驗(yàn)數(shù)有何特點(diǎn)？非基變量x2的檢驗(yàn)數(shù)等于零。70注：（1）解的幾種情況在單純形表上的體現(xiàn)（Max型）：唯一

33、最優(yōu)解：終表非基變量檢驗(yàn)數(shù)均小于零；多重最優(yōu)解：終表非基變量檢驗(yàn)數(shù)中有等于零的；無界解：任意表有正檢驗(yàn)數(shù)相應(yīng)的列均非正；無解：最優(yōu)解的基變量中含有人工變量。（2）Min型單純形表與Max型的區(qū)別僅在于：檢驗(yàn)數(shù)反號(hào)，即令負(fù)檢驗(yàn)數(shù)中最小的對(duì)應(yīng)的變量進(jìn)基；當(dāng)檢驗(yàn)數(shù)均大于等于零時(shí)為最優(yōu)。71線性規(guī)劃 Linear Programming（LP）單純形法的進(jìn)一步討論人工變量法： 當(dāng)一般線性規(guī)劃問題標(biāo)準(zhǔn)化之后，我們可得到一個(gè)顯然的基本可行解（如松弛變量作為基變量的一個(gè)初始基本可行解），這樣我們就可以馬上進(jìn)入單純形表的運(yùn)算步驟。然而，并非所有問題標(biāo)準(zhǔn)化之后我們都可得到一個(gè)顯然的初始基本可行解，這時(shí)就需要我們

34、首先確定出一個(gè)基本可行解作為初始基本可行解。通常采用的是人工變量法來確定這樣的初始基本可行解。這種情況下一般有兩種方法： 1、大M法（罰因子法）；2、兩階段法72線性規(guī)劃 Linear Programming（LP）1、大 M 法（罰函數(shù)法）max z = - 3X1 + X3 x1 + x2 + x3 4s.t. - 2x1 + x2 x3 1 3x2 + x3 = 9 x1 ，x2 ，x3 0 max z = - 3x1 + x3 + 0 x4 + 0 x5 Mx6 Mx7 x1 + x2 + x3 + x4 = 4 s.t. - 2x1 + x2 x3 - x5 + x6 = 1 3x2

35、 + x3 +x7 = 9 x1 ，x2 ，x3 ， x4 ， x5 ， x6 ， x7 073線性規(guī)劃 Linear Programming（LP）LPM max z = - 3x1 + x3 + 0 x4 + 0 x5 Mx6 Mx7 x1 + x2 + x3 + x4 = 4 - 2x1 + x2 x3 - x5 + x6 = 1 3x2 + x3 +x7 = 9 x1 ，x2 ，x3 ， x4 ， x5 ， x6 ， x7 0基XB解B-1bX1X2X3X4X5X6X7X441111000X61-21-10-110X790310001檢驗(yàn)數(shù) j74線性規(guī)劃 Linear Program

36、ming（LP）基XB解B-1bX1X2X3X4X5X6X7X441111000X61-21-10-110X790310001檢驗(yàn)數(shù) j-3-2M4M10-M0075線性規(guī)劃 Linear Programming（LP）基XB解B-1bX1X2X3X4X5X6X7X4411110004X61-21-10-1101X7903100013檢驗(yàn)數(shù) j-3-2M4M10-M00基XB解B-1bX1X2X3X4X5X6X7X4330211-10X21-21-10-110X7660403-31檢驗(yàn)數(shù) j-3+6M01+4M03M-4M076線性規(guī)劃 Linear Programming（LP）基XB解B-

37、1bX1X2X3X4X5X6X7X4330211-101X21-21-10-110-X7660403-311檢驗(yàn)數(shù) j-3+6M01+4M03M-4M0基XB解B-1bX1X2X3X4X5X6X7X400001-1/21/2-1/2X23011/30001/3X11102/301/2-1/21/6檢驗(yàn)數(shù) j00301.5-1.5-M0.5-M77線性規(guī)劃 Linear Programming（LP）基XB解B-1bX1X2X3X4X5X6X7X400001-1/21/2-1/2-X23011/30001/39X11102/301/2-1/21/63/2檢驗(yàn)數(shù) j00301.5-1.5-M0.5-M基XB解B-1bX1X2X3X4X5X6X7X400001-1/21/2-1/2X25/2-1/2100-1/41/41/4X33/23/20103/4-3/41/4檢驗(yàn)數(shù) j-9/2000-3/43/4-M-1/4-M78線性規(guī)劃 Linear Programming（LP）注：采用大 M 法求解線性規(guī)劃問題時(shí)可能出現(xiàn)的幾種情況：1、當(dāng)采用單純形法求解 LPM 得到最優(yōu)解時(shí)，基變量不含任何人工變量，則所得到的最優(yōu)解就是原問題的最優(yōu)解；