運籌學(第四版)清華大學出版社《運籌學》教材編寫組-第2章

1、2021/3/10清華大學出版社1二、線性規(guī)劃與目標規(guī)劃n第2章 線性規(guī)劃與單純形法n第3章 對偶理論與靈敏度分析n第4章 運輸問題n第5章 線性目標規(guī)劃2021/3/10清華大學出版社2第2章 線性規(guī)劃與單純形法線性規(guī)劃與單純形法n第1節(jié) 線性規(guī)劃問題及其數(shù)學模型n第2節(jié) 線性規(guī)劃問題的幾何意義n第3節(jié) 單純形法n第4節(jié) 單純形法的計算步驟n第5節(jié) 單純形法的進一步討論n第6節(jié) 應(yīng)用舉例2021/3/10清華大學出版社3第1節(jié) 線性規(guī)劃問題及其數(shù)學模型v2.1.1 問題的提出v2.1.2 圖解法v2.1.3 線性規(guī)劃問題的標準形式v2.1.4 線性規(guī)劃問題的解的概念2021/3/10清華大學

2、出版社4第1節(jié) 線性規(guī)劃問題及其數(shù)學模型 線性規(guī)劃是運籌學的一個重要分支。線性規(guī)劃在理線性規(guī)劃是運籌學的一個重要分支。線性規(guī)劃在理論上比較成熟，在實用中的應(yīng)用日益廣泛與深入。特別論上比較成熟，在實用中的應(yīng)用日益廣泛與深入。特別是在電子計算機能處理成千上萬個約束條件和決策變量是在電子計算機能處理成千上萬個約束條件和決策變量的線性規(guī)劃問題之后，線性規(guī)劃的適用領(lǐng)域更為廣泛了。的線性規(guī)劃問題之后，線性規(guī)劃的適用領(lǐng)域更為廣泛了。從解決技術(shù)問題的最優(yōu)化設(shè)計到工業(yè)、農(nóng)業(yè)、商業(yè)、交從解決技術(shù)問題的最優(yōu)化設(shè)計到工業(yè)、農(nóng)業(yè)、商業(yè)、交通運輸業(yè)、軍事、經(jīng)濟計劃和管理決策等領(lǐng)域都可以發(fā)通運輸業(yè)、軍事、經(jīng)濟計劃和管理決策

3、等領(lǐng)域都可以發(fā)揮作用。它已是現(xiàn)代科學管理的重要手段之一。解線性揮作用。它已是現(xiàn)代科學管理的重要手段之一。解線性規(guī)劃問題的方法有多種，以下僅介紹規(guī)劃問題的方法有多種，以下僅介紹單純形法單純形法 。2021/3/10清華大學出版社52.1.1 問題的提出2.1.1 2.1.1 問題的提出問題的提出 例例 1 某工廠在計劃期內(nèi)要安排生產(chǎn)、兩種產(chǎn)品，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺時及A、B兩種原材料的消耗，如表1-1所示。資源 產(chǎn) 品 擁有量設(shè) 備1 2 8臺時原材料 A 40 16 kg原材料 B04 12 kg每生產(chǎn)一件產(chǎn)品每生產(chǎn)一件產(chǎn)品可獲利可獲利2 2元，每生產(chǎn)一件產(chǎn)品元，每生產(chǎn)一件產(chǎn)品可獲利可

4、獲利3 3元，問應(yīng)如何安排計劃使該工廠獲利最多元，問應(yīng)如何安排計劃使該工廠獲利最多? ? 2021/3/10清華大學出版社62.1.1 問題的提出稱它們?yōu)闆Q策變量。產(chǎn)品的數(shù)量，分別表示計劃生產(chǎn)設(shè)III,21xx12416482212121x;x;xx,x ,x這是約束條件。即有量的限制的數(shù)量多少，受資源擁生產(chǎn)021x,x,即生產(chǎn)的產(chǎn)品不能是負值這是目標。最大如何安排生產(chǎn)，使利潤,用數(shù)學關(guān)系式描述這個問題用數(shù)學關(guān)系式描述這個問題2021/3/10清華大學出版社72.1.1 問題的提出0124164823221212121x ,xxxxx:xxzmax約束條件目標函數(shù)得到本問題的數(shù)學模型為:這就是

5、一個最簡單的線性規(guī)劃模型。這就是一個最簡單的線性規(guī)劃模型。2021/3/10清華大學出版社82.1.1 問題的提出 例例 2 靠近某河流有兩個化工廠(見圖1-1)，流經(jīng)第一化工廠的河流流量為每天500萬立方米，在兩個工廠之間有一條流量為每天200萬立方米的支流。 圖1-1化工廠1每天排放含有某種有害物質(zhì)的工業(yè)污水2萬立方米，化工廠2每天排放的工業(yè)污水為1.4萬立方米。從化工廠1排出的污水流到化工廠2前，有20%可自然凈化。根據(jù)環(huán)保要求，河流中工業(yè)污水的含量應(yīng)不大于0.2%。因此兩個工廠都需處理一部分工業(yè)污水?；S1處理污水的成本是1000元/萬立方米,化工廠2處理污水的成本是800元/萬立方

6、米。問:在滿足環(huán)保要求的條件下，每廠各應(yīng)處理多少工業(yè)污水，在滿足環(huán)保要求的條件下，每廠各應(yīng)處理多少工業(yè)污水，使兩個工廠處理工業(yè)污水的總費用最小。使兩個工廠處理工業(yè)污水的總費用最小。2021/3/10清華大學出版社92.1.1 問題的提出設(shè)設(shè)：化工廠1每天處理的污水量為x1萬立方米；化工廠2每天處理的污水量為x2萬立方米100027004128021000250022211)x.()x(.)x(工廠后的水質(zhì)要求：經(jīng)第工廠前的水質(zhì)要求：經(jīng)第建模型之前的分析和計算2021/3/10清華大學出版社102.1.1 問題的提出0,4 . 126 . 18 . 018001000min212121121xx

7、xxxxxxxz約束條件目標函數(shù)得到本問題的數(shù)學模型為：2021/3/10清華大學出版社112.1.1 問題的提出l每一個線性規(guī)劃問題都用一組決策變量 表示某一方案，這組決策變量的值代表一個具體方案。一般這些變量的取值是非負且連續(xù)的；l都有關(guān)于各種資源和資源使用情況的技術(shù)數(shù)據(jù)，創(chuàng)造新價值的數(shù)據(jù)；l存在可以量化的約束條件，這些約束條件可以用一組線性等式或線性不等式來表示;l都有一個達到某一目標的要求，可用決策變量的線性函數(shù)(稱為目標函數(shù))來表示。按問題的要求不同，要求目標函數(shù)實現(xiàn)最大化或最小化。nx,x,x21)n,j;m,i (c;ajij11上述兩個問題具有的共同特征：上述兩個問題具有的共同

8、特征：2021/3/10清華大學出版社122.1.1 問題的提出nmmnmmnnnccbbbaaaaaaaaamxxx212121222211121121c21價值系數(shù)動活資源決策變量決策變量及各類系數(shù)之間的對應(yīng)關(guān)系2021/3/10清華大學出版社132.1.1 問題的提出).(x,x ,xb),(xaxaxa).(b),(xaxaxab),(xaxaxa).(xcxcxczmax(min)nmnmmmnnnnnn310211121221122222121112121112211約束條件目標函數(shù)線性規(guī)劃模型的一般形式2021/3/10清華大學出版社142.1.2 圖解法1.2 1.2 圖解法圖

9、解法例1是一個二維線性規(guī)劃問題，因而可用作圖法直觀地進行求解。12121212max2328416412,0zxxxxxxx x2021/3/10清華大學出版社152.1.2 圖解法表示一簇平行線33212zxx2132xxzmax目標值在（4，2）點，達到最大值142021/3/10清華大學出版社162.1.2 圖解法（1）無窮多最優(yōu)解(多重最優(yōu)解)，見圖1-4。（2）無界解，見圖1-5-1。（3）無可行解，見圖1-5-2。通過圖解法，可觀察到線性規(guī)劃的解可能出現(xiàn)的幾種情況：2021/3/10清華大學出版社172.1.2 圖解法目標函數(shù) max z=2x1+4x2 圖1-4 無窮多最優(yōu)解（多

10、重最優(yōu)解）2021/3/10清華大學出版社182.1.2 圖解法ox ,xxxxxxxzmax2121121242圖1-5-1 無界解2021/3/10清華大學出版社19 當存在相互矛盾的約束條件時，線性規(guī)劃問題的可行域為空集。例如，如果在例1的數(shù)學模型中增加一個約束條件: 則該問題的可行域即為空集空集，即無可行解，85 . 121xx無可行解的情形2.1.2 圖解法2021/3/10清華大學出版社2085 . 121xx增加的約束條件圖1-5-2 不存在可行域2.1.2 圖解法2021/3/10清華大學出版社212.1.3 線性規(guī)劃問題的標準型式11 12211 11221121 12222

11、21 12212:maxzca,0nnnnnnmmmnnmnMxc xc xxa xa xba xa xa xba xaxaxbx xx 目標函數(shù)：約束條件：2.1.3 線性規(guī)劃問題的標準型式線性規(guī)劃問題的標準型式2021/3/10清華大學出版社222.1.3 線性規(guī)劃問題的標準型式n,j;bbbb;aaaP;xxxX;c,c,cCn,j,xbxPCXzmax:Mmmjjjjnnjnjjj 212102121212111約束條件：目標函數(shù)：用向量形式表示的標準形式線性規(guī)劃線性規(guī)劃問題的幾種表示形式2021/3/10清華大學出版社232.1.3 線性規(guī)劃問題的標準型式用矩陣形式表示的標準形式線性

12、規(guī)劃用矩陣形式表示的標準形式線性規(guī)劃Tnnmnmn x,x,xX;P,P,PaaaaAXbAXCXzmax:M21m12111111bbb0000決策變量向量：；資源向量：零向量：系數(shù)矩陣：約束條件：目標函數(shù)：2021/3/10清華大學出版社242.1.3 線性規(guī)劃問題的標準型式kkkxxx(1) 若要求目標函數(shù)實現(xiàn)最小化，即min z =CX，則只需將目標函數(shù)最小化變換求目標函數(shù)最大化，即令z= z，于是得到max z= CX。(2) 約束條件為不等式。分兩種情況討論：l若約束條件為“”型不等式，則可在不等式左端加入非負松弛變量，把原“”型不等式變?yōu)榈仁郊s束；l若約束條件為“”型不等式，則可

13、在不等式左端減去一個非負剩余變量(也稱松弛變量)，把不等式約束條件變?yōu)榈仁郊s束。(3) 若存在取值無約束的變量xk,可令 0,kkxx如何將一般線性規(guī)劃轉(zhuǎn)化為標準形式的線性規(guī)劃如何將一般線性規(guī)劃轉(zhuǎn)化為標準形式的線性規(guī)劃2021/3/10清華大學出版社252.1.3 線性規(guī)劃問題的標準型式例例3 將例1的數(shù)學模型化為標準形式的線性規(guī)劃。例1的數(shù)學模型在加入了松馳變量后變?yōu)?212345123121412521212345max23max230002828416416412412,0,0zxxzxxxxxxxxxxxxxxxxx xx x x x x2021/3/10清華大學出版社262.1.3

14、線性規(guī)劃問題的標準型式例例4 將下述線性規(guī)劃問題化為標準形式線性規(guī)劃為無約束3213213213213210533732x;x ,xxxxxxxxxxxxxzmin(1) 用x4x5替換x3，其中x4，x50；(2) 在第一個約束不等式左端加入松弛變量x6；(3) 在第二個約束不等式左端減去剩余變量x7；(4) 令z= z，將求min z 改為求max z即可得到該問題的標準型。2021/3/10清華大學出版社272.1.3 線性規(guī)劃問題的標準型式例例4 例4的標準型12456712456124571245124567max23()00()7()232()5,0zxxxxxxxxxxxxxxx

15、xxxxxx x x x x x2021/3/10清華大學出版社282.1.4 線性規(guī)劃問題的解概念v1.可行解v2.基v3.基可行解v4.可行基2021/3/10清華大學出版社292.1.4 線性規(guī)劃問題的解的概念v定義滿足約束條件(1-5)、(1-6)式的解X=(x1,x2，xn)T，稱為線性規(guī)劃問題的可行解，其中使目標函數(shù)達到最大值的可行解可行解稱為最優(yōu)解最優(yōu)解。)(n ,j,x)(m,i ,bxa)(xczmaxjnjijijnjjj61210512141111. 可行解可行解2021/3/10清華大學出版社302.1.4 線性規(guī)劃問題的解的概念為基變量。為基向量，為線性規(guī)劃問題的基。

16、稱階非奇異子矩陣中的是系數(shù)矩陣), 2 , 1(x), 2 , 1(P,B0BAjj21212222111211mjmjPPPaaaaaaaaaBmmBmmmmmmm2. 基，基向量，基變量基，基向量，基變量2021/3/10清華大學出版社312.1.4 線性規(guī)劃問題的解的概念是基可行解43210Q,Q,Q,Q,滿足非負條件（1-6）的基解，稱為基可行解. 基可行解的非零分量的數(shù)目不大于m，并且都是非負的。3 基可行解基可行解2021/3/10清華大學出版社322.1.4 線性規(guī)劃問題的解的概念l 對應(yīng)于基可行解的基，稱為可行基。l 約束方程組(1-5)具有的基解的數(shù)目最多是 個，一般基可行解

17、的數(shù)目要小于基解的數(shù)目。l 以上提到了幾種解的概念，它們之間的關(guān)系可用圖1-6表明。l 說明：當基解中的非零分量的個數(shù)小于m時，該基解是退化解。在以下討論時，假設(shè)不出現(xiàn)退化的情況。 mnC4 可行基可行基2021/3/10清華大學出版社332.1.4 線性規(guī)劃問題的解的概念mnC不同解之間的關(guān)系不同解之間的關(guān)系2021/3/1034P552.1（1），2.2（1）(無需列初始單純形表）作業(yè)2021/3/10清華大學出版社35第2節(jié) 線性規(guī)劃問題的幾何意義v2.2.1 基本概念v2.2.2 幾個定理2021/3/10清華大學出版社36 2.2.1 基本概念v凸集v凸組合v頂點2021/3/10清

18、華大學出版社372.2.1 基本概念v定義設(shè)K是n維歐氏空間的一點集，若任意兩點X(1)K，X(2)K的連線上的所有點X(1)+(1)X(2)K，(01)，則稱K為凸集。圖1-71.凸集凸集2021/3/10清華大學出版社382.2.1 基本概念v實心圓，實心球體，實心立方體等都是凸集，圓環(huán)不是凸集。從直觀上講，凸集沒有凹入部分，其內(nèi)部沒有空洞。圖1-7中的(a)(b)是凸集，(c)不是凸集。v圖1-2中的陰影部分是凸集。v任何兩個凸集的交集是凸集，見圖1-7(d)2021/3/10清華大學出版社392.2.1 基本概念v設(shè)X(1)，X(2)，X(k)是n維歐氏空間En中的k個點。若存在1，2

19、，k，且0i1, i=1,2,，k 使 X=1X(1)+2X(2)+kX(k) 則稱X為X(1)，X(2)，X(k)的一個凸組合（當0i1時，稱為嚴格凸組合）。kii112. 凸組合凸組合2021/3/10清華大學出版社402.2.1 基本概念v設(shè)K是凸集，XK；若X不能用不同的兩點X(1)K和X(2)K的線性組合表示為 X=X(1)+(1)X(2)，(01) 則稱X為K的一個頂點(或極點)。 圖中的0，Q1, Q2, Q3, Q4都是頂點。3. 頂點頂點2021/3/10清華大學出版社412.2.2 幾個定理v定理定理1 若線性規(guī)劃問題存在可行域，則其可行域 是凸集。1,0njjjjDXP

20、xbx2021/3/10清華大學出版社422.2.2 幾個定理v定理1的證明：只需證明D中任意兩點連線上的點必然在D內(nèi)即可。設(shè) 是D內(nèi)的任意兩點；且X(1)X(2)。 TnTnxxxXxxxX222212112111,則有 njjjjnjjjjnjxbxPnjxbxP122111, 2 , 1, 0, 2 , 1, 0, 令 X=(x1，x2，xn)T為 x(1),x(2)連線上的任意一點，即 X=X(1)+(1-)X(2) (01) X 的每一個分量是 21)1 (jjjxxx，將它代入約束條件， 得到 2021/3/10清華大學出版社432.2.2 幾個定理 bbbbxPxPxPxxPxP

21、njnjjjjjnjjjnjnjjjjjj11221111211又因 01 , 0, 0,21jjxx，所以 xj0，j=1,2,n。 由此可見 XD，D 是凸集。 證畢。 2021/3/10清華大學出版社442.2.2 幾個定理v引理引理 1 線性規(guī)劃問題的可行解X=(x1,x2,，xn)T為基可行解的充要條件是：X的正分量所對應(yīng)的系數(shù)列向量是線性獨立的。證證: : (1) 必要性由基可行解的定義可知。 (2) 充分性若向量P1，P2，Pk線性獨立， 則必有 km；當 k=m 時，它們恰構(gòu)成一個基，從而 X=(x1,x2,xk,00)為相應(yīng)的基可行解。當 km 時， 則一定可以從其余的列向量

22、中取出 m-k 個與 P1，P2，Pk 構(gòu)成最大的線性獨立向量組，其對應(yīng)的解恰為 X， 所以根據(jù)定義它是基可行解。 2021/3/10清華大學出版社452.2.2 幾個定理v定理定理2 線性規(guī)劃問題的基可行解X對應(yīng)于可行域D的頂點。 證：證：不失一般性，假設(shè)基可行解X的前m個分量為正。 故 現(xiàn)分兩步來討論，分別用反證法。mjjjbxP12021/3/10清華大學出版社462.2.2 幾個定理 (1) 若X不是基可行解，則它一定不是可行域D的頂點。 根據(jù)引理1，若X不是基可行解，則其正分量所對應(yīng)的系數(shù)列向量P1，P2，Pm線性相關(guān)，即存在一組不全為零的數(shù)i,i=1,2,m，使得 1P1+2P2+

23、mPm=0 (1-9)用一個數(shù)0乘(1-9)式再分別與(1-8)式相加和相減，得 (x11)P1+(x22)P2+(xm m)Pm=b (x1+1)P1+(x2+2)P2+(xm+m)Pm=b 2021/3/10清華大學出版社472.2.2 幾個定理 因X 不是可行域D的頂點，故在可行域D中可找到不同的兩點 X(1)=(x1(1),x2(1),xn(1)T X(2)=(x1(2),x2(2),xn(2)T 使得 X=X(1)+(1) X(2) ， 01 設(shè)X是基可行解，對應(yīng)的向量組P1Pm線性獨立，故當jm時，有xj=xj(1)=xj(2)=0。由于X(1)，X(2)是可行域的兩點，因而滿足

24、mjmjjjjjbxPbxP1121與 （2）若X不是可行域D的頂點，則它一定不是基可行解。 mjjjjxxP1210將兩式相減，得 因X(1)X(2)，所以上式中的系數(shù)不全為零，故向量組P1,P2,，Pm線性相關(guān)，與假設(shè)矛盾，即X不是基可行解。2021/3/10清華大學出版社482.2.2 幾個定理v引理引理2 若K是有界凸集，則任何一點XK可表示為K的頂點的凸組合。 本引理的證明從略，用以下例子說明本引理的結(jié)論。v例例5 設(shè)X是三角形中任意一點，X(1)，X(2)和X(3)是三角形的三個頂點，試用三個頂點的坐標表示X(見圖1-8)圖1-82021/3/10清華大學出版社492.2.2 幾個

25、定理 解：解：任選一頂點X(2)，做一條連線XX(2)，并延長交于X(1)、X(3)連接線上一點X。因為X是X(1)、X(3)連線上一點，故可用X(1)、X(3)線性組合表示為X=X(1)+(1)X(3) 01 又因X是X與X(2)連線上的一個點，故X=X+(1 )X(2) 01 將X的表達式代入上式得到X=X(1)+(1)X(3)+(1)X(2)=X(1)+(1 )X(3)+(1)X(2) 令 1=,2=(1 ),3=(1 )，得到X=1X(1)+2X(2)+3X(3)ii=1, 0i12021/3/10清華大學出版社502.2.2 幾個定理v定理定理 3 若可行域有界，則線性規(guī)劃問題的目標

26、函數(shù)一定可以在其可行域的頂點上達到最優(yōu)。 證：證： 設(shè)X(1),X(2)，X(k)是可行域的頂點，若X(0)不是頂點，且目標函數(shù)在X(0)處達到最優(yōu)z*=CX(0)(標準型是z=max z)。 因X(0)不是頂點，所以它可以用D的頂點線性表示為 代入目標函數(shù)得 011,0,1kkiiiiiiiXx kikiiiiiCXXCCX1102021/3/10清華大學出版社512.2.2 幾個定理在所有的頂點中必然能找到某一個頂點X(m)，使CX(m)是所有CX(i)中最大者。并且將X(m)代替(1-10)式中的所有X(i)，得到 mkimikiiiCXCXCX11由此得到 CX(0)CX(m)根據(jù)假設(shè)

27、CX(0)是最大值，所以只能有 CX(0)=CX(m)即目標函數(shù)在頂點X(m)處也達到最大值。 2021/3/10清華大學出版社522.2.2 幾個定理 1X， 2X， kX 11,0,1kkiiiiiiXX有時，目標函數(shù)可能在多個頂點處達到最大，這時在這些頂點的凸組合上也達到最大值，這時線性規(guī)劃問題有無限多個最優(yōu)解。假設(shè)是目標函數(shù)達到最大值的頂點，則對這些頂點的凸組合，有 kiiikiiiXCXCXC112021/3/10清華大學出版社532.2.2 幾個定理 kimXCi, 2 , 1,設(shè)：于是：另外，若可行域為無界，則可能無最優(yōu)解，也可能有最優(yōu)解，若有最優(yōu)解，也必定在某頂點上得到。mmX

28、Ckii12021/3/10清華大學出版社54基本結(jié)論l線性規(guī)劃問題的所有可行解構(gòu)成的集合是凸集，也可能為無界域，它們有有限個頂點，線性規(guī)劃問題的每個基可行解對應(yīng)可行域的一個頂點。l若線性規(guī)劃問題有最優(yōu)解，必在某頂點上得到。雖然頂點數(shù)目是有限的，若采用“枚舉法”找所有基可行解，然后一一比較，最終必然能找到最優(yōu)解。但當n,m較大時，這種辦法是行不通的，所以要繼續(xù)討論如何有效尋找最優(yōu)解的方法。本課程將主要介紹單純形法單純形法。2021/3/10清華大學出版社55第第3節(jié)節(jié) 單純形法單純形法v2.3.1 舉例v2.3.2 初始基可行解的確定v2.3.3 最優(yōu)性檢驗與解的判斷v2.3.4 基變換v2.

29、3.5 迭代（旋轉(zhuǎn)運算）2021/3/10清華大學出版社56單純形法求解線性規(guī)劃的思路： 一般線性規(guī)劃問題具有線性方程組的變量數(shù)大于一般線性規(guī)劃問題具有線性方程組的變量數(shù)大于方程個數(shù)，這時有不定的解。但可以從線性方程組中方程個數(shù)，這時有不定的解。但可以從線性方程組中找出一個個的單純形，每一個單純形可以求得一組解，找出一個個的單純形，每一個單純形可以求得一組解，然后再判斷該解使目標函數(shù)值是增大還是變小，決定然后再判斷該解使目標函數(shù)值是增大還是變小，決定下一步選擇的單純形。這就是迭代，直到目標函數(shù)實下一步選擇的單純形。這就是迭代，直到目標函數(shù)實現(xiàn)最大值或最小值為止。這樣，問題就得到了最優(yōu)解，現(xiàn)最大

30、值或最小值為止。這樣，問題就得到了最優(yōu)解，先舉一例來說明。先舉一例來說明。2021/3/10清華大學出版社572.3.1 舉例例例6 試以例1來討論如何用單純形法求解。解：已知本例的標準型為：)111 (00032max54321xxxxxz5 , 2 , 10124)121 (164825241321jxxxxxxxxj2021/3/10清華大學出版社582.3.1 舉例約束條件(1-12)式的系數(shù)矩陣為從(1-12)式可看到x3,x4,x5的系數(shù)構(gòu)成的列向量100010040004121,54321PPPPPA100,010,001543PPP2021/3/10清華大學出版社592.3.1

31、 舉例P3 ,P4,P5是線性獨立的，這些向量構(gòu)成一個基B 。對應(yīng)于B的變量x3,x4,x5為基變量. 124)121 (164825241321xxxxxxx從(1-12)式中可以得到（1-13）)131 (412416282514213xxxxxxx2021/3/10清華大學出版社602.3.1 舉例將(1-13)式代入目標函數(shù)(1-11)：得到當令非基變量x1=x2=0，便得到z=0。這時得到一個基可行解X(0) X(0)=(0,0,8,16,12)T 本基可行解的經(jīng)濟含義是：工廠沒有安排生產(chǎn)產(chǎn)品、，資源都沒有被利用，所以工廠的利潤為z=0。)111 (00032max54321xxxx

32、xz)141 (32021xxz2021/3/10清華大學出版社612.3.1 舉例 從分析目標函數(shù)的表達式從分析目標函數(shù)的表達式(1-14)可以看到：可以看到： 非基變量非基變量x1,x2(即沒有安排生產(chǎn)產(chǎn)品即沒有安排生產(chǎn)產(chǎn)品，)的系的系數(shù)都是正數(shù)，因此將非基變量變換為基變量，目標數(shù)都是正數(shù)，因此將非基變量變換為基變量，目標函數(shù)的值就可能增大。從經(jīng)濟意義上講，安排生產(chǎn)函數(shù)的值就可能增大。從經(jīng)濟意義上講，安排生產(chǎn)產(chǎn)品產(chǎn)品或或，就可以使工廠的利潤指標增加。所以，就可以使工廠的利潤指標增加。所以只要在目標函數(shù)只要在目標函數(shù)(1-14)的表達式中還存在有正系數(shù)的的表達式中還存在有正系數(shù)的非基變量，這

33、表示目標函數(shù)值還有增加的可能，就非基變量，這表示目標函數(shù)值還有增加的可能，就需要將非基變量與基變量進行對換。需要將非基變量與基變量進行對換。2021/3/10清華大學出版社622.3.1 舉例v如何確定換入、換出變量一般選擇正系數(shù)最大的那個非基變量x2為換入變量，將它換到基變量中，同時還要確定基變量中哪一個換出來成為非基變量。可按以下方法來確定換出變量：o分析(1-13)式，當將x2定為換入變量后，必須從x3,x4,x5中確定一個換出變量，并保證其余的變量仍然非負，即x3,x4,x50。2021/3/10清華大學出版社632.3.1 舉例v如何確定換入、換出變量當x1=0時，由(1-13)式得

34、到)151 (041201602825423xxxxx)131 (412416282514213xxxxxxx2021/3/10清華大學出版社642.3.1 舉例v如何確定換入、換出變量當x2取何值時，才能滿足非負要求呢？ 從(1-15)式可看出，只有選擇 x2=min(8/2,-,12/4)=3時，才能使(1-15)式成立。 因當x2=3時，基變量x5=0，這就決定用x2去替換x5。 以上數(shù)學描述說明，每生產(chǎn)一件產(chǎn)品，需要用掉的各種資源數(shù)為(2，0，4)。由這些資源中的薄弱環(huán)節(jié)，就確定了產(chǎn)品的產(chǎn)量。 這里就是由原材料B的數(shù)量確定了產(chǎn)品的產(chǎn)量x2=12/4=3件。2021/3/10清華大學出版

35、社652.3.1 舉例v如何確定換入、換出變量為了求得以x3,x4,x2為基變量的一個基可行解和進一步分析問題，需將(1-13)中x2的位置與x5的位置對換，得到)131 (412416282514213xxxxxxx )161 (312424161825214123xxxxxxx2021/3/10清華大學出版社662.3.1 舉例v將(1-16)式中x2的系數(shù)列向量變換為單位列向量。其運算步驟是：v=/4；=-2;=,v并將結(jié)果仍按原順序排列有： 1713413241612125214513xxxxxxx高斯消去法高斯消去法2021/3/10清華大學出版社672.3.1 舉例v再將(1-17

36、)式代入目標函數(shù)(1-11)式得到2021/3/10清華大學出版社682.3.1 舉例 從目標函數(shù)的表達式(1-18)可看到，非基變量x1的系數(shù)是正的，說明目標函數(shù)值還可以增大，即X(1)還不是最優(yōu)解。 于是，再用上述方法確定換入、換出變量，繼續(xù)迭代，得到另一個基可行解X(2)X(2)=(2,3,0,8,0)T 再經(jīng)過一次迭代，又得到一個基可行解X(3)X(3)=(4,2,0,0,4)T 而這時得到目標函數(shù)的表達式是： z=141.5x3 0.125x4 (1-19) 再檢查(1-19)式，可見所有非基變量x3,x4的系數(shù)都是負數(shù)，這說明若要用剩余資源x3,x4，就必須支付附加費用。 所以當x

37、3=x4=0時，即不再利用這些資源時，目標函數(shù)達到最大值。所以X(3)是最優(yōu)解。即當產(chǎn)品生產(chǎn)4件，產(chǎn)品生產(chǎn)2件時，工廠可以得到最大利潤。2021/3/10清華大學出版社69小結(jié)v通過上例，可將每步迭代得到的結(jié)果與圖解法做一對比。v例1的線性規(guī)劃問題是二維的，即有兩個變量x1,x2。當加入松弛變量x3,x4,x5后，變換為高維的。這時可以想象，滿足所有約束條件的可行域是高維空間中的凸多面體(凸集)。該凸多面體上的頂點，就是基可行解。初始基可行解為 X(0)=(0,0,8,16,12)T，對應(yīng)于圖1-2中的原點(0，0)；X(1)=(0,3,2,16,0)T對應(yīng)于圖中的Q4點(0，3)； X(2)

38、=(2，3，0，8，0)T對應(yīng)于Q3點(2，3)；最優(yōu)解X(3)=(4，2，0，0，4)T相當于圖中的 Q2點(4，2)。從初始基可行解X(0)開始迭代，依次得到X(1)，X(2)，X(3)，相當于圖中的目標函數(shù)平移時，從0點開始，首先碰到Q4，然后碰到Q3，最后達到Q2。2021/3/10清華大學出版社702.3.2 初始基可行解的確定v為了確定初始基可行解，要首先找出初始可行基，其方法如下。(1)直接觀察(2)加松弛變量(3)加非負的人工變量2021/3/10清華大學出版社712.3.2 初始基可行解的確定從線性規(guī)劃問題的系數(shù)構(gòu)成的列向量Pj(j=1,2,n)中，通過直接觀察，找出一個初始

39、可行基11max1 201 2101,2,njjjnjjjjzc xP xbxjn111,21mPPPB(1)直接觀察直接觀察2021/3/10清華大學出版社722.3.2 初始基可行解的確定 對所有約束條件為“”形式的不等式，利用化標準型的方法，在每個約束條件的左端加上一個松弛變量。經(jīng)過整理，重新對xj及aij (i=1,2,m; j=1,2,n)進行編號，則可得下列方程組（x1,x2,xm 為松弛變量）：njxbxaxaxbxaxaxbxaxaxjmnmmmmmnnmmnnmm, 2 , 1, 022111,2211,221111, 11(2)加松弛變量加松弛變量2021/3/10清華大學

40、出版社732.3.2 初始基可行解的確定于是，(1-22)中含有一個mm階單位矩陣，初始可行基B即可取該單位矩陣。將(1-22)式每個等式移項得111,21mPPPBnmmmmmmnnmmnnmmxaxabxxaxabxxaxabx11,211, 222111, 1112312021/3/10清華大學出版社742.3.2 初始基可行解的確定令xm+1=xm+2=xn=0，由(1-23)式可得xi=bi (i=1,2,m)得到一個初始基可行解。又因bi0(在1-3節(jié)中已做過規(guī)定)，所以得到一個初始基可行解 X=(x1,x2,xm,0，0)T nm個 =(b1,b2,bm,0，0)T nm個202

41、1/3/10清華大學出版社752.3.2 初始基可行解的確定v對所有約束條件為“”形式的不等式及等式約束情況，若不存在單位矩陣時，可采用人造基方法。即對不等式約束，減去一個非負的剩余變量，再加上一個非負的人工變量；對于等式約束，再加上一個非負的人工變量v這樣，總能在新的約束條件系數(shù)構(gòu)成的矩陣中得到一個單位矩陣。(3)加非負的人工變量加非負的人工變量2021/3/10清華大學出版社762.3.3 最優(yōu)性檢驗與解的判別v由于線性規(guī)劃問題的求解可能出現(xiàn)唯一最優(yōu)解、無窮多最優(yōu)解、無界解和無可行解等四種情況，因此，需要建立解的判別準則。一般情況下，經(jīng)過迭代后(1-23)式變成 241, 2 , 1,1n

42、mjjijiinixabx2021/3/10清華大學出版社772.3.3 最優(yōu)性檢驗與解的判別將 代入目標函數(shù)(1-20)式，整理后得251)(11111111111111111 minmjjmiijijiinmjjjnmjjijmiimiiinmjjjnmjjijmiimiiinmjjjminmjjijiiminmjjjiinjjjxaccbcxcxacbcxcxacbcxcxabcxcxcxcznmjmijxijaibix1), 2 , 1,(2021/3/10清華大學出版社782.3.3 最優(yōu)性檢驗與解的判別mimiijijiinmjaczbcz110, 1,nmjjjjxzczz10)

43、261 (于是nmjzcjjj, 1設(shè)27110nmjjjxzz令2021/3/10清華大學出版社792.3.3 最優(yōu)性檢驗與解的判別 若 為對應(yīng)于基B的一個基可行解，且對于一切j=m+1,n，有j0，則X(0)為最優(yōu)解。稱j為檢驗數(shù)。 TmbbbX0 , 0 ,2101.最優(yōu)解的判別定理最優(yōu)解的判別定理2021/3/10清華大學出版社802.3.3 最優(yōu)性檢驗與解的判別 若 為一個基可行解，對于一切j=m+1，,n，有j0，又存在某個非基變量的檢驗數(shù)m+k=0，則線性規(guī)劃問題有無窮多最優(yōu)解。 證證: 只需將非基變量xm+k換入基變量中，找到一個新基可行解X(1)。因m+k=0，由(1-27)

44、知z=z0，故X(1)也是最優(yōu)解。由2.2節(jié)的定理3可知，X(0)和X(1)連線上所有點都是最優(yōu)解。 TmbbbX0 , 0 ,2102.無窮多最優(yōu)解判別定理無窮多最優(yōu)解判別定理2021/3/10清華大學出版社812.3.3 最優(yōu)性檢驗與解的判別 若 為一基可行解， 有一個m+k0，并且對i=1,2,，m，有ai,m+k0，那么該線性規(guī)劃問題具有無界解(或稱無最優(yōu)解)。 證證: 構(gòu)造一個新的解 X(1)，它的分量為 TmbbbX0 , 0 ,210 kmjnmjxxabxjkmkmiii并且, 1; 0011,13無界解判別定理無界解判別定理2021/3/10清華大學出版社822.3.3 最優(yōu)

45、性檢驗與解的判別 因 ，所以對任意的0都是可行解，把x(1)代入目標函數(shù)內(nèi)，得到z=z0+m+k 因m+k0，故當+，則z+，故該問題目標函數(shù)無界。0,kmia2021/3/10清華大學出版社832.3.3 最優(yōu)性檢驗與解的判別v其它情形以上討論都是針對標準型的，即求目標函數(shù)極大化時的情況。當要求目標函數(shù)極小化時，一種情況是將其化為標準型。如果不化為標準型，只需在上述1，2點中把j0改為j0，第3點中將m+k0改寫為m+k0即可。2021/3/10清華大學出版社842.3.4 基變換v若初始基可行解X(0)不是最優(yōu)解及不能判別無界時，需要找一個新的基可行解。v具體做法是從原可行解基中換一個列向

46、量(當然要保證線性獨立)，得到一個新的可行基，稱為基變換。為了換基，先要確定換入變量，再確定換出變量，讓它們相應(yīng)的系數(shù)列向量進行對換，就得到一個新的基可行解。2021/3/10清華大學出版社851.換入變量的確定v由(1-27)式可知，當某些j0時，若xj增大，則目標函數(shù)值還可以增大。這時需要將某個非基變量xj換到基變量中去(稱為換入變量)。v若有兩個以上的j0，那么選哪個非基變量作為換入變量呢?為了使目標函數(shù)值增加得快，從直觀上看應(yīng)選j0中的較大者，即由 應(yīng)選擇xk為換入變量。kjj 0max2021/3/10清華大學出版社862.換出變量的確定v設(shè)P1，P2，Pm是一組線性獨立的向量組，它

47、們對應(yīng)的基可行解是X(0)，將它代入約束方程組(1-21)得到 miiibPx10281其他的向量Pm+1,Pm+2,Pm+t,Pn都可以用P1，P2，Pm線性表示。若確定非基變量xm+t為換入變量，必然可以找到一組不全為0的數(shù)(i=1,2,m)使得29101,1,miitmitmmiitmitmPPPP或2021/3/10清華大學出版社872.換出變量的確定在(1-29)式兩邊同乘一個正數(shù)，然后將它加到(1-28)式上，得到 301m1i,011,0bPPxbPPPxtmitmiimimiitmitmii或2021/3/10清華大學出版社882.換出變量的確定2021/3/10清華大學出版社

48、892.換出變量的確定 00,min0ili m tii m tl m txx2021/3/10清華大學出版社902.換出變量的確定v新的基可行解為 01011,0001,0,0,0,lm tl m tllmm m tl m tl m tlm txXxxxx第 個分量第個分量2021/3/10清華大學出版社912.換出變量的確定v由此得到由X(0)轉(zhuǎn)換到X(1)的各分量的轉(zhuǎn)換公式 lixlixxxtmlltmitmllii,0,0012021/3/10清華大學出版社922.換出變量的確定這里 是原基可行解X(0)的分量； 是新基可行解X(1)的各分量；vi,m+t是換入向量Pm+t對應(yīng)原來一組

49、基向量的坐標。v現(xiàn)在的問題是，這個新解X(1)的m個非零分量對應(yīng)的列向量是否獨立?事實上，因為X(0)的第一個分量對應(yīng)于X(1)的相應(yīng)分量是零，即 0,0tmllx 0ix 1ix2021/3/10清華大學出版社932.換出變量的確定其中 ,01x均不為零，根據(jù)規(guī)則(最小比值)， l,m+t0。X(1)中的 m 個非零分量對應(yīng)的 m 個列向量是 Pj(j=1,2,m,jl)和Pm+t。若這組向量不是線性獨立， 則一定可以找到不全為零的數(shù)j，使 mjjjtmljPaP1)311 (,mjjtmjtmPP1,)321 (,成立。又因?qū)?1-32)式減(1-31)式得到mjltmljjtmjPPa1

50、,0)(2021/3/10清華大學出版社942.換出變量的確定由于上式中至少有l(wèi),m+t0，所以上式表明P1，P2，Pm是線性相關(guān)，這與假設(shè)相矛盾。由此可見，X(1)的m個非零分量對應(yīng)的列向量Pj(j=1,2,m,jl)與Pm+t是線性獨立的，即經(jīng)過基變換得到的解是基可行解。實際上，從一個基可行解到另一個基可行解的變換，就是進行一次基變換。從幾何意義上講，就是從可行域的一個頂點轉(zhuǎn)向另一個頂點。 2021/3/10清華大學出版社952.3.5 迭代(旋轉(zhuǎn)運算)上述討論的基可行解的轉(zhuǎn)換方法是用向量方程描述的，在實際計算時不太方便，因此下面介紹系數(shù)矩陣法系數(shù)矩陣法?？紤]以下形式的約束方程組mnmkm

51、kmmmmlnklkmmllnnkkmmnnkkmmbxaxaxaxbxaxaxaxbxaxaxaxbxaxaxax11,ln11,22211, 2211111, 11331一般線性規(guī)劃問題的約束方程組中加入松弛變量或人工變量后，很容易得到上述形式2021/3/10清華大學出版社962.3.5 迭代(旋轉(zhuǎn)運算)lklikikiiabaab0min設(shè)x1,x2,xm為基變量，對應(yīng)的系數(shù)矩陣是mm單位陣I，它是可行基。令非基變量xm+1,xm+2,xn為零，即可得到一個基可行解。若它不是最優(yōu)解，則要另找一個使目標函數(shù)值增大的基可行解。這時從非基變量中確定xk為換入變量。顯然這時為在迭代過程中可表示

52、為0minlklikikiiabaab,ikiab其中 是經(jīng)過迭代后對應(yīng)于 的元素值。ikiab ,2021/3/10清華大學出版社972.3.5 迭代(旋轉(zhuǎn)運算)按規(guī)則確定xl為換出變量，xk, xl的系數(shù)列向量分別為個分量第 lPaaaaPlmklkkkk0010;212021/3/10清華大學出版社982.3.5 迭代(旋轉(zhuǎn)運算)為了使xk與xl進行對換，須把Pk變?yōu)閱挝幌蛄?，這可以通過(1-33)式系數(shù)矩陣的增廣矩陣進行初等變換來實現(xiàn)。)341 (1111ln11,1,11, 111mlmnnmkmmlkmlkmnkmmlbbbaaaaaaaaabxxxxxx2021/3/10清華大學

53、出版社992.3.5 迭代(旋轉(zhuǎn)運算)351 (, 1 , 0 , 0 ,1, 0ln1,lkllklkmllkabaaaaa變換的步驟是：(1) 將增廣矩陣(1-34)式中的第l行除以al k，得到(2) 將(1-34)式中xk列的各元素，除al k變換為1以外，其他都應(yīng)變換為零。其他行的變換是將(1-35)式乘以aik(il)后，從(1-34)式的第i行減去，得到新的第i行。,1ln,1n0,0,0,0,l mikli mikiikiiklklklklkaabaaaaabaaaaa2021/3/10清華大學出版社1002.3.5 迭代(旋轉(zhuǎn)運算)由此可得到變換后系數(shù)矩陣各元素的變換關(guān)系式l

54、iablibaabbliaaliaaaaalklilkikiilkljiklkljijij; 是變換后的新元素。 ,iijba2021/3/10清華大學出版社1012.3.5 迭代(旋轉(zhuǎn)運算)(3) 經(jīng)過初等變換后的新增廣矩陣是)361 (01010100011,ln1,111, 1111mmnmmlkmklmllknmlkknkmmlbaaaabaaabaaaabxxxxxx2021/3/10清華大學出版社1022.3.5 迭代(旋轉(zhuǎn)運算)(4) 由(1-36)式中可以看到x1,x2,xk,，xm的系數(shù)列向量構(gòu)成mm單位矩陣;它是可行基。當非基變量xm+1,，xl,xn為零時，就得到一個基可

55、行解X(1) 1111,0,0,0,0,0TllmkXbbbbb在上述系數(shù)矩陣的變換中，元素al k稱為主元素主元素，它所在列稱為主元列，它所在行稱為主元行，元素al k位置變換后為1。 2021/3/10清華大學出版社1032.3.5 迭代(旋轉(zhuǎn)運算)例例7 7 試用上述方法計算例6的兩個基變換。 解：例6的約束方程組的系數(shù)矩陣寫成增廣矩陣1216810040010040012154321bxxxxx當以x3,x4,x5為基變量，x1,x2為非基變量，令x1,x2=0，可得到一個基可行解X(0)=(0,0,8,16,12)T2021/3/10清華大學出版社1042.3.5 迭代(旋轉(zhuǎn)運算)現(xiàn)

56、用x2去替換x5，于是將x3,x4, x2的系數(shù)矩陣變換為單位矩陣，經(jīng)變換后為31624/10010010042/1010154321bxxxxx 令非基變量x1,x5=0，得到新的基可行解X(1)=(0,3,2,16,0)T2021/3/10105P562.4，2.5作業(yè)2021/3/10清華大學出版社106第4節(jié) 單純型法的計算步驟v2.4.1 單純型表v2.4.2 計算步驟2021/3/10清華大學出版社1072.4.1 單純型表v為了便于理解計算關(guān)系，現(xiàn)設(shè)計一種計算表，稱為單純形表，其功能與增廣矩陣相似。v將(1-22)式與目標函數(shù)組成n+1個變量，m+1個方程的方程組。2021/3/

57、10清華大學出版社108線性規(guī)劃的方程組0111111221122111111nnmmmmmnmnmmmmnnmmnnmmxcxcxcxczbxaxaxbxaxaxbxaxax2021/3/10清華大學出版社109線性規(guī)劃的方程組v為了便于迭代運算，可將上述方程組寫成增廣矩陣形式1211,1112,122,112101000010000110mmnmnmnm mmnmmmnzxxxxxbaabaabaabccccc2021/3/10清華大學出版社110線性規(guī)劃的方程組v若將z看作不參與基變換的基變量，它與x1,x2,xm的系數(shù)構(gòu)成一個基，這時可采用行初等變換將c1,c2,cm變換為零，使其對應(yīng)

58、的系數(shù)矩陣為單位矩陣。得到miiimmiininmimiimmnmmnmnmnmmbcbbbaccaccaaaaaabxxxxxz121111,11,21, 211, 11210001000001000010表1-22021/3/10清華大學出版社111線性規(guī)劃的方程組v表1-2的說明XB列中填入基變量，這里是x1，x2,，xm；CB列中填入基變量的價值系數(shù)，這里是c1,c2,cm；它們是與基變量相對應(yīng)的；b列中填入約束方程組右端的常數(shù)；cj行中填入基變量的價值系數(shù)c1,c2,cn；i列的數(shù)字是在確定換入變量后，按規(guī)則計算后填入；最后一行稱為檢驗數(shù)行，對應(yīng)各非基變量xj的檢驗數(shù)是miijijn

59、jacc1, 2 , 1,2021/3/10清華大學出版社1122.4.2 計算步驟v表1-2稱為初始單純形表，每迭代一步構(gòu)造一個新單純形表。v計算步驟：(1) 按數(shù)學模型確定初始可行基和初始基可行解，建立初始單純形表。(2) 計算各非基變量xj的檢驗數(shù)， 檢查檢驗數(shù)，若所有檢驗數(shù) 則已得到最優(yōu)解，可停止計算。否則轉(zhuǎn)入下一步。miijijjacc1,0,1,2,jjmmn2021/3/10清華大學出版社1132.4.2 計算步驟(3)在j0,j=m+1,n中，若有某個k對應(yīng)xk的系數(shù)列向量Pk0，則此問題是無界，停止計算。 否則，轉(zhuǎn)入下一步。(4) 根據(jù)max(j0)=k，確定xk為換入變量，

60、按規(guī)則計算可確定xl為換出變量，轉(zhuǎn)入下一步lklikikiabaab0min2021/3/10清華大學出版社1142.4.2 計算步驟(5) 以alk為主元素進行迭代(即用高斯消去法或稱為旋轉(zhuǎn)運算)，把xk所對應(yīng)的列向量 將XB列中的xl換為xk，得到新的單純形表。重復(2)(5)，直到終止。行第變換laaaaPmklkkkk0100212021/3/10清華大學出版社1152.4.2 計算步驟v現(xiàn)用例1的標準型來說明上述計算步驟v(1) 取松弛變量x3,x4,x5為基變量，它對應(yīng)的單位矩陣為基。這就得到初始基可行解X(0)=(0,0,8,16,12)Tv將有關(guān)數(shù)字填入表中，得到初始單純形表，