運籌學線性規(guī)劃理論及應用講解

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

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

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

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

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

6、（噸）147000（千塊）4000 (千工日）要求在充分利用各種資源條件下使建造住宅的總面積為最大，求建造方案。11 解: 設今年計劃修建磚混、壁板、大模住宅各為 x1,x2, x3, 為總面積,則本問題的數(shù)學模型為: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)的尼古拉也夫斯克城住宅興建計劃采用了上述模型，共用了12個變量，10個約束條件。12練習：某畜牧廠每日要為牲畜購買飼料以使其獲取A、B、C、D四種養(yǎng)分。市場上可選擇的飼料有M、N兩種。有關數(shù)據(jù)如下：試決定買M與N二種飼料各多少公斤而使支出的總費用為最少？ 售價 （元/公斤） 每公斤含營養(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解：設購買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ù)學模型線性規(guī)劃模型的一般形式：以MAX型、約束為例決策變量: x1 , , xn目標函數(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 稱為價格系數(shù)向量， A 稱為技術系數(shù)矩陣，b 稱為資源限制向量。17線性規(guī)劃 Linear Programming（LP）2.線性規(guī)劃問題的求解：（圖解法） 如何求解一般的線性規(guī)劃呢？ 下面我們分析一下簡單的情況 只有兩個決策變量的線性規(guī)劃問題，這時可以通過圖解的方法來求解。圖解法具有簡單、直觀、便于初學者窺探線性規(guī)劃基本原理和幾何意義等優(yōu)點。18圖解法是用畫圖的方式求解線性規(guī)劃的一種方法。它雖然只能用于解二維（兩個變量）的問題，但其主要作用并不在于求解，而是在于能夠直觀地說明線性規(guī)劃解的一些重要性質(zhì)。19線

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

11、解法的結(jié)果得到例1的最優(yōu)解，還可將其代入目標函數(shù)求得相應的最優(yōu)目標值z=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此點是唯一最優(yōu)解，且最優(yōu)目標函數(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 綠色線段上的所有點都是最優(yōu)解這種情形為有無窮多最優(yōu)解，但是最優(yōu)目標函數(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）可行域此點是唯一最優(yōu)解27練習：用圖解法求解下面的線性規(guī)劃。min z = 6x1 +4 x2 s.t. 2x1 + x2 1 3x1 + 4x2 1.5 x1 ，x2 028二維線性規(guī)劃的可行域是一個什么形狀？多邊形，而且是“凸”形的多邊形。最優(yōu)解在什么位置獲得？在邊界，而且是在某個頂點獲得。29線性規(guī)劃 Linear Programming（LP）圖解法的啟示線性規(guī)劃問題解的可能情況 a.唯一最優(yōu)解 b.無窮多最優(yōu)解 c.無解（沒有有界最優(yōu)解，無可行解）若線性規(guī)劃問題的可行域非空，則可行域是一個凸集；若線性規(guī)劃問題的最優(yōu)解存在，則一定可以在可行域的凸集的某個

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

16、法。32線性規(guī)劃 Linear Programming（LP）線性規(guī)劃問題的標準形式（預備知識一）1、目標函數(shù)極大化 “ max ”2、等式約束條件 “ = ” 3、變量非負 “ 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）化標準形式的一般步驟1、目標函數(shù)極小化“極大化”2、約束條件的右端項 bi0 “bi0

17、” 3、約束條件為不等式 或 “=”4、取值無約束（自由）變量“非負變量”5、取值非正變量“非負變量”34線性規(guī)劃 Linear Programming（LP）給定線性規(guī)劃問題（標準形式）max z = c1x1 + c2x2 + + cnxn a11x1 + a12x2 + a1nxn = b1 a21x1 + a22x2 + a2nxn = b2s.t. am1x1 + am2x2 + amnxn = bm xj 0 （j=1，2 n）標準型的特征：max型；等式約束；非負約束35練習：將例1的約束化為標準型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ōu)解 基矩陣、基變量 基解（基本解） 基可行解 38（1）可行解與最優(yōu)解可行解：滿足全體約束的解，記為X；最優(yōu)解：可行解中最優(yōu)的，記為X*，則對任可行解X，有CXCX*. 直觀上，可行解是可行域中的點，是一個可行的方案；最優(yōu)解是可行域中的頂點，是一個最優(yōu)的方案。39（2）基矩陣和基變

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

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

21、行解（簡稱基可行解）。45在上例中求相應于基B1和B2的可行解，它們是否基本可行解？解：B1=00 1B2-1=1/5 2/52/5 -1/5B1-1b=13 相應于基B1的基本解為X=（0，0，1，3）T，是基本可行解。B2=22 -1B1-1=00 1B2 -1b=7/5-1/5 相應于基B2的基本解為X=（7/5，-1/5，0，0）T，不是基本可行解。46上二組概念間的聯(lián)系：系數(shù)陣A中可找出若干個基B每個基B都對應于一個基本解非負的基本解就是基本可行解問題1：幾種解之間的關系是什么？問題2：基本可行解是可行域中的哪些點？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 的極點。基本定理 3 給定線性規(guī)劃問題， A是秩為 m 的 mn 矩陣， （i） 若線性規(guī)劃問題存在可行解，則必存在基本可行性解 （ii）若線性規(guī)劃問題存在有界最優(yōu)解，則必存在有界最優(yōu)基本可行解。48（1）線性規(guī)劃的可行域是一個凸多面體。（2）線性規(guī)劃可行域的頂點與基本可行解一一對應。（3）線性規(guī)劃的最優(yōu)解（若存在的話）必能在可行域的頂點獲得。49單純形法的步驟確定初始基可行解檢驗其是否最優(yōu)是stop

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

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

25、善”，令0對應的Pk進基出基：保證“可行”，令XB=B-1b-B-1NXN0可決定出基方法：令k=max j0 對應的Pk進基；令l =min i =（B -1b）i/(B -1Pk) i |(B-1Pk)i 0 對應的Pl出基；i稱作檢驗比。55 以例1為例，可按上述單純形法的步驟求出其最優(yōu)解，其大致的過程如下。（1）先將模型化為標準型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) 確定初始基可行解、檢驗 1 1B0=,B

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

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

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

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

34、首先確定出一個基本可行解作為初始基本可行解。通常采用的是人工變量法來確定這樣的初始基本可行解。這種情況下一般有兩種方法： 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檢驗數(shù) j74線性規(guī)劃 Linear Program

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

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