運(yùn)籌學(xué)第3講-線性規(guī)劃2

1、線性規(guī)劃問題的幾何意義線性規(guī)劃問題的幾何意義 凸集: 設(shè)K是n維歐氏空間的一點(diǎn)集，若任意兩點(diǎn) X(1)K，X(2) K的連線上的所有點(diǎn) X(1)+(1-)X(2)K，(01) 則稱K為凸集。 注：實(shí)心圓，實(shí)心球體，實(shí)心立方體等都是凸集，圓環(huán)不是凸集。從直觀上講，凸集沒有凹入部分，其內(nèi)部沒有空洞。圖中的(a)(b)是凸集，(c)不是凸集。任何兩個(gè)凸集的交集仍為凸集，如圖(d)。線性規(guī)劃問題的幾何意義線性規(guī)劃問題的幾何意義結(jié)論：任何兩個(gè)凸集的交集仍為凸集。 證明：設(shè)A，B為凸集， 則 因此同理 從而所以A與B的交集為凸集。(1)(2),XXAB(1)(2),XXA A為凸集。(1)(2),(1)X

2、XA0,1(1)(2)(1)XXB(1)(2)(1)XXAB線性規(guī)劃問題的幾何意義線性規(guī)劃問題的幾何意義 凸組合：設(shè)X(1)， X(2) ，X(k)是n維歐氏空間En中的k個(gè)點(diǎn)，若存在1，2，k，且0i1, i=1,2,，k， 使 X=1X(1)+2X(2)+kX(k)，則稱X為X(1)， X(2) ，X(k)的凸組合。 （當(dāng)0i1時(shí)，稱為嚴(yán)格凸組合）。 頂點(diǎn)：設(shè)K是凸集，XK；若X不能用不同的兩點(diǎn)X(1)K和X(2)K 的線性組合表示為X=X(1)+(1-)X(2)，(01)，則稱X為K的一個(gè)頂點(diǎn)(或極點(diǎn))。注 右圖中0,Q1,Q2,Q3,Q4都是頂點(diǎn)。線性規(guī)劃問題的幾何意義線性規(guī)劃問題的幾

3、何意義關(guān)于線性規(guī)劃問題的幾個(gè)定理：定理1：若線性規(guī)劃問題存在可行解，則該問題的可行域是凸集。定理2：線性規(guī)劃問題的基可行解X對應(yīng)可行域(凸集)的頂點(diǎn)。定理3：若問題存在最優(yōu)解，一定存在一個(gè)基可行解是最優(yōu)解。（或在某個(gè)頂點(diǎn)取得） 以上證明過程見P16-20. 單純形法 盡管若線性規(guī)劃問題有最優(yōu)解，必可以在某頂點(diǎn)上得到，雖然頂點(diǎn)數(shù)目是有限的(它不大于個(gè))，若采用“枚舉法”找所有基可行解，然后一一比較，最終可能找到最優(yōu)解。但當(dāng)n,m的數(shù)較大時(shí)，這種辦法是行不通的。（m=20，n=40時(shí)，頂點(diǎn)的個(gè)數(shù)有 個(gè)）。112040103 . 1C 如何有效地找到最優(yōu)解，有多種方法，這里僅介紹單純形法(Simpl

4、ex Method)。 單純形法單純形法 單純形：單純形或者n-單純形是和三角形類似的n維幾何體。精確的講，單純形是某個(gè)n維以上的歐幾里得空間中的（n+1）個(gè)仿射無關(guān)（也就是沒有m維平面包含m+1個(gè)點(diǎn)；這樣的點(diǎn)集被稱為處于一般位置）的點(diǎn)的集合的凸包。 0-單純形就是點(diǎn)，1-單純形就是線段，2-單純形就是三角形，3-單純形就是四面體，而4-單純形是一個(gè)五胞體（每種情況都包含內(nèi)部）。 標(biāo)準(zhǔn)n-單純形：是Rn+1的子集： 單純形法單純形法 單純形法的基本思路：根據(jù)前述定理，如果線性規(guī)劃問題存在最優(yōu)解，則可以在基本可行解中找最優(yōu)解。由于基本可行解的個(gè)數(shù)是有限的，所以通過建立一種最優(yōu)性判別準(zhǔn)則，將基本可

5、行解逐一進(jìn)行檢查，就可以在有限次檢查后得到最優(yōu)解。但是，在有些情況下，要找出所有的基本可行解是非常麻煩的，單純形法的優(yōu)越性就在于不用找出全部的基本可行解。 單純形法單純形法 單純形法的基本思路：在得到一個(gè)基本可行解X1后，判斷X1是否是最優(yōu)解，或者判斷此問題沒有最優(yōu)解。如果X1是最優(yōu)解，或者此問題沒有最優(yōu)解，則求解到此為止；若不然，則依據(jù)這個(gè)解X1求出下一個(gè)基本可行解X2，并且X2要比X1對應(yīng)的目標(biāo)函數(shù)值有所改善。對X2重復(fù)剛才的判斷，直到得到問題的解答為止。qX1qX2qX3 單純形法單純形法 單純形法的基本步驟：(1) 確定初始基本可行解X1；(2) 記Xk為求出的第k個(gè)基本可行解，根據(jù)建

6、立的最優(yōu)性準(zhǔn)則，對Xk進(jìn)行檢驗(yàn)，若Xk是最優(yōu)解，則計(jì)算終止; 若不然，則轉(zhuǎn)第(3)步；(3) 若根據(jù)建立的無最優(yōu)解準(zhǔn)則判斷此問題沒有最優(yōu)解，則計(jì)算終止；若不能判定沒有最優(yōu)解，則轉(zhuǎn)第(4)步；(4) 依據(jù)Xk求基本可行解Xk+1，使Z(Xk+1) Z(Xk)，令k=k+1，轉(zhuǎn)回第(2)步。 單純形法單純形法 單純形法的基本步驟： 單純形法單純形法 單純形法的基本步驟：(1) 確定初始的基本可行解X1；- 假設(shè)在約束系數(shù)矩陣中含有單位陣并且bi 0， i=1,2,m，則令單位陣所在列對應(yīng)的變量為基變量，其他變量為非基變量，并令非基變量取零值，可得到初始基本可行解。- 對于所有行約束條件為“”不等式

7、，在每行引入松弛變量化為標(biāo)準(zhǔn)形后，所有松弛變量的系數(shù)矩陣正好為單位矩陣。- 當(dāng)化為標(biāo)準(zhǔn)形后系數(shù)矩陣中不含有單位陣時(shí)，確定初始基本可行解的方法可采用人工變量法。- 首先假設(shè)系數(shù)矩陣含單位陣的情況。 單純形法單純形法 單純形法的基本步驟：(2) 確定最優(yōu)性判別準(zhǔn)則；設(shè)線性規(guī)劃問題(LP)約束系數(shù)矩陣中的前m列為一個(gè)單位陣，其模型有如下形式，其中bi 0，i=1,2,m。目標(biāo)函數(shù)： max z = c1 x1 + c2 x2 + + cn xn 約束條件： s. t. x1 + a1m+1 x m+1 + + a1n xn = b1 x2 + a2m+1 x m+1 + + a2n xn = b2

8、(LP) xm + amm+1 x m+1 + + amn xn= bm x1 ，x2 ， ，xn 0. 單純形法單純形法 單純形法的基本步驟：(2) 確定最優(yōu)性判別準(zhǔn)則；取x1，xm為基變量，xm+1，xn為非基變量?；窘鉃閄1=（b1，b2，bm，0，0）T。將上式約束方程組變?yōu)椋?x1 = b1-（a1m+1 x m+1 + + a1n xn） x2 = b2-（a2m+1 x m+1 + + a2n xn） xm = bm-（ amm+1 x m+1 + + amn xn）代入目標(biāo)函數(shù)中： Z= c1 x1 + c2 x2 + + cn xn 單純形法單純形法 單純形法的基本步驟：(

9、2) 確定最優(yōu)性判別準(zhǔn)則；11111111111()()mjiijmniijjij mmnniiijjjjij mj mmmnniiiijjjjiij mj mmniijij mic xc xc ba xc xcbc accxc xcbxa 記得到目標(biāo)函數(shù)由當(dāng)前解X1的非基變量的線性表示：111,1,mmjjiijii iiccZcbjman11jjnj mZxZ其中Z1即為X1對應(yīng)的目標(biāo)函數(shù)值。 單純形法單純形法 單純形法的基本步驟：(2) 確定最優(yōu)性判別準(zhǔn)則；將上面結(jié)果整理后，可得到與原線性規(guī)劃等價(jià)的模型111max,1,2,0,1,2,njjj mniijjij mjZZxxa xb i

10、mxjn定義：稱此等價(jià)模型為基本可行解X1對應(yīng)的典式。 單純形法單純形法 單純形法的基本步驟：(2) 確定最優(yōu)性判別準(zhǔn)則；定理4：設(shè)X1 =（b1，b2，bm，0，0）T為線性規(guī)劃(LP) 的基本可行解，如果在其對應(yīng)的典式中則X1為最優(yōu)解。注：此定理就是單純形法中的最優(yōu)性判別準(zhǔn)則。0,1,jjmn 單純形法單純形法 單純形法的基本步驟：(2) 確定最優(yōu)性判別準(zhǔn)則；證明：設(shè) 為任一可行解, Z0為其目標(biāo)函數(shù)值。將X0代入基本可行解X1對應(yīng)的典式的目標(biāo)函數(shù)中，有 由式 ，則有 說明Z1為最大值， X1為最優(yōu)解，定理得證。000012(,)TnXxxx00,0,1,jjxjmn 0011jnjj m

11、ZZx00111jnjj mZZxZ 單純形法單純形法 單純形法的基本步驟：(2) 確定最優(yōu)性判別準(zhǔn)則；注：典式中的 稱為基本可行解的檢驗(yàn)數(shù)，確切地說，是X1的非基變量的檢驗(yàn)數(shù)。 為了統(tǒng)一起見，對X1的基變量也規(guī)定檢驗(yàn)數(shù) ，顯然，應(yīng)有 (因?yàn)榈涫街胁缓兞?，?shí)際通過公式計(jì)算也為零) ，即基變量的檢驗(yàn)數(shù)為零。,1,jjmn,1,2,jjm0,1,2,jjm 單純形法單純形法例3.1 為下面線性規(guī)劃問題的一個(gè)基本可行解，試判斷其是否為最優(yōu)解。1(6,2,15,0,0)TX 12345145245345max2266262150,1,2,5jZxxxxxxxxxxxxxxxj 100160101

12、100162A( )3r A 1233123( ,),BP P PIx x x為基矩陣，故為基變量。解:將模型化為基本可行解X1對應(yīng)的典式，X1=(6,2,15,0,0)T 可知，x4,x5為非基變量，約束條件已具有典式形式，只需要將目標(biāo)函數(shù)由非基變量x4,x5線性表示即可： Z=-(6- x4-6x5)+(2+ x4-x5)+2(15- 6x4-2x5)+2 x4+x5=26-8 x4+2x5由此可知 ，其中 不滿足最優(yōu)性準(zhǔn)則，因此不能判斷X1為最優(yōu)解。451238,2,0 520 單純形法單純形法 單純形法的基本步驟：(3) 確定無最優(yōu)解判別準(zhǔn)則；定理5 設(shè)X1為線性規(guī)劃問題的基本可行解，

13、如果在X1對應(yīng)的典式中存在檢驗(yàn)數(shù) ，并且 的約束系數(shù) 皆小于等于零，則該線性規(guī)劃問題的目標(biāo)函數(shù)在可行域上沒有上界，即沒有最優(yōu)解（無界解）。0kkx12,kkm kaaa例 3.2 判斷下面的問題是否沒有最優(yōu)解。1231234135max233560,1,2,5jZxxxxxxxxxxxj 單純形法單純形法解: 取 為基本可行解，對于X1此模型已經(jīng)為典式形式。其中檢驗(yàn)數(shù) ，并且 皆小于等于零，由定理判斷無最優(yōu)解。怎么理解？1(0,0,0,5,6)TX 33013233,1aa 分析：由約束條件可知，對于x3取任何非負(fù)值，此問題都存在可行解 ，目標(biāo)函數(shù)值為 。1(0,0,53,6)TXMMM3ZM

14、故而可知當(dāng)M逐漸增大時(shí)，Z也相應(yīng)增大，當(dāng) 時(shí)， 因此Z為最大值，規(guī)劃無最優(yōu)解。M Z 單純形法單純形法 單純形法的基本步驟：(4) 基本可行解的迭代；定義: 根據(jù)已有的基本可行解求新的基本可行解稱為迭代。定義: 將原基本可行解X1中的某個(gè)非基變量變?yōu)榛兞?，稱為進(jìn)基變量； 將X1的某個(gè)基變量變?yōu)榉腔兞?，稱為出基變量。注: 迭代的過程實(shí)際就是要實(shí)現(xiàn)進(jìn)基變量和出基變量之間 的轉(zhuǎn)換。 單純形法單純形法迭代方法: 設(shè) 為基變量，并且存在檢驗(yàn)數(shù) ，由X1 的典式形式的目標(biāo)函數(shù)的表達(dá)式可知其中Z1為X1對應(yīng)的目標(biāo)函數(shù)值。由于 ，故若選 xk 為進(jìn)基變量時(shí)(一般基變量的取值大于零)，可使目標(biāo)函數(shù)值進(jìn)一步增

15、加。因此確定xk為進(jìn)基變量。11212( ,0,0) , ,TmmXb bbx xx0()kkx為基變量111mmkknnZZxxx0k基本可行解X1的典式形式的約束方程組為11111122112211mmn nmmn nmmmmmn nmxaxa xbxaxa xbxaxa xb在基本可行解中，基變量的個(gè)數(shù)是固定的m個(gè), xk進(jìn)基，則必有一個(gè)基變量轉(zhuǎn)換為非基變量。 單純形法單純形法 為了確定出基變量，首先在典式的約束中，令除xm以外的其余非基變量仍取零值，得到: 根據(jù)這個(gè)關(guān)系式，又考慮到每個(gè)決策變量的可行性，從而選取xk，使其滿足如下的關(guān)系式:111222kkkkmmkkmxa xbxa x

16、bxaxb0,1,2,iiikkxba xim 單純形法單純形法 當(dāng) 時(shí)，因?yàn)閎i 非負(fù)，故只需要 即可; 當(dāng) 時(shí)，則需 。 綜合上面兩種情況，因此，應(yīng)使 xk 滿足0ika 0ika /kiikxba0kx min|0ilkikiiklkbbxaaa注: 因?yàn)樽顑?yōu)性判別準(zhǔn)則和無最優(yōu)解判別定理不成立，故可以保證 的存在性，以及 。0 按照上面的規(guī)則確定的變量xk，當(dāng) 時(shí)，使得原 第l 個(gè)基變量的值變?yōu)?kx0llllkllklkbxbabaa即基變量 xl 成為出基變量。 單純形法單純形法 可以證明，矩陣 仍為可行基，因此得到新的基本可行解 ，其中各分量的值為:111(,)TlllmBPPP

17、PP2111( ,0,0, ,0)TllmXxxxx1112221111110kklllklllkmmmkkjxbaxbaxbaxbaxbaxx其余 根據(jù)X1的典式的表達(dá)式中的目標(biāo)函數(shù)，將X2代入計(jì)算得: 新解比原解有所改善，增量為 211kZZZ k 至此，完成了基本可行解的迭代。 單純形法單純形法 定義: 一般稱 為最小比值規(guī)則，或稱為 規(guī)則，其中的 稱為中心元素（主元）。min|0ilkikiiklkbbxaaalka現(xiàn)將基本可行解的迭代過程歸納如下： 設(shè)已得到基本可行解對應(yīng)的典式形式。(1)取 對應(yīng)的xk為進(jìn)基變量。（主要是提高收斂效率，使得每次的增量 最大。）(2)按最小比值規(guī)則確定

18、xk的值，并確定出基變量。(3)按右式確定新的基本可行解。max|0kjjk1112221111110kklllklllkmmmkkjxbaxbaxbaxbaxbaxx其 余 單純形法單純形法例3.3 根據(jù)基本可行解X1以及典式，迭代求新的基本可行解，并指出目標(biāo)函數(shù)值的增量。1(6,2,15,0,0)TX 其典式為45145245345max268266262150,1,2,5jZxxxxxxxxxxxxjX1的目標(biāo)函數(shù)值為Z1=26解: 由于 ，所以確定x5 為進(jìn)基變量。按最小比值規(guī)則計(jì)算出 因此 ，同時(shí)確定xl為出基變量，取零值，另外x4 為非基變量仍取零值。520155156 2 15m

19、in|0min ,16 12iiibbaaa 51x 單純形法單純形法將這些取值代入X2計(jì)算公式中，得到新的基本可行解為其目標(biāo)函數(shù)值為2(0,1,13,0,1)TX215262 128ZZ 目標(biāo)函數(shù)值的增量為 。52 對X2還應(yīng)繼續(xù)判斷其是否是最優(yōu)解。則問題轉(zhuǎn)化為如何確定新的基本可行解X2的檢驗(yàn)數(shù)。 單純形法單純形法 單純形法的基本步驟：(5) 新的基本可行解的檢驗(yàn)數(shù)的確定。不失一般性，考慮下面的線性規(guī)劃模型:1144155166122442552662334435536630,1,2,6jxa xa xa xbxa xa xa xbxa xa xa xbxj假設(shè)已得到的基本可行解 不是最優(yōu)解

20、。1123( , , ,0,0)TXb b b并假設(shè)經(jīng)過計(jì)算，確定x5為進(jìn)基變量， x1為出基變量， a15為中心元素，得到新的基本可行解 ,223(0,0, ,0)TXb b22253335bbabba 單純形法單純形法 單純形法的基本步驟：(5) 新的基本可行解的檢驗(yàn)數(shù)的確定。 為了判斷X2是否最優(yōu)解，需要對約束方程組進(jìn)行適當(dāng)變換，找出X2對應(yīng)的典式形式。為此，首先要在約束方程組中將新基變量x2, x3, x5顯式表示出來，然后代入目標(biāo)函數(shù)，得到目標(biāo)函數(shù)由新的非基變量的線性表示，從而得到X2對應(yīng)的檢驗(yàn)數(shù)。 這些變換可以經(jīng)過下面的矩陣變換實(shí)現(xiàn)，即根據(jù)約束方程組構(gòu)造矩陣式，對其進(jìn)行初等行變換，

21、變?yōu)榫仃囀?單純形法單純形法 單純形法的基本步驟：(5) 新的基本可行解的檢驗(yàn)數(shù)的確定。141612425262343536345615100010001000aabaaabaaaba111416121242623134363146001100010000aaabaaabaaab即：將進(jìn)基變量x5對應(yīng)的第5列向量化為單位向量，其中將中心元素a15化為1。由上面得到轉(zhuǎn)化后的矩陣式，得到新的基本可行解X2對應(yīng)的典式形式：2114466111144516612112244266231133443663max0,1,2,6jZZxxxa xa xxa xba xxa xa xba xxa xa xbx

22、j 其中 即為新解X2的檢驗(yàn)數(shù)，根據(jù)他們的正負(fù)，可以判斷X2是否最優(yōu)解。146, 單純形法單純形法例3.4 對例3.3中得到的基本可行解X2，判斷其是否是最優(yōu)解。由此可得到在求X2的檢驗(yàn)數(shù)時(shí)用到的矩陣解: 是根據(jù) 得到的，而X1對應(yīng)的典式為2(0,1,13,0,1)TX1(6,2,15,0,0)TX 45145245345max268266262150,1,2,5jZxxxxxxxxxxxxj100160101120016215860002將進(jìn)基變量x5對應(yīng)的第5列向量化為單位向量，將中心元素a15=6化為1，得到: 單純形法單純形法110011661710016611701013331250

23、0033由此矩陣可知， 的檢驗(yàn)數(shù) ，2(0,1,13,0,1)TX12345125,0,033 全部小于等于零，因此X2就是最優(yōu)解。 單純形法單純形法小結(jié) 單純形法的主要步驟：Step1 確定初始的基本可行解X1，求出X1對應(yīng)的典式；Step2 根據(jù)最優(yōu)性準(zhǔn)則判別定理判斷X1是否是最優(yōu)解，若是，算法停止，X1即為最優(yōu)解。否則，根據(jù)無最優(yōu)解判別準(zhǔn)則判斷此線性規(guī)劃是否無最優(yōu)解，若是，算法停止，此規(guī)劃無最優(yōu)解；否則，轉(zhuǎn)Step3；Step3 由 確定xk為進(jìn)基變量，根據(jù)最小比值規(guī)則確定xk的值 ，確定中心元素和出基變量；Step4 采用初等行變換將中心元素化為1，并將中心元素所在列化為單位列向量確定

24、新的基本可行解X2，以及X2對應(yīng)的檢驗(yàn)數(shù)，轉(zhuǎn)Step2。min|0ilkikiiklkbbxaaamax|0kjj 單純形法單純形法 單純形法的求解過程，實(shí)際上是在一系列表格上進(jìn)行的。從這些表格上可以得到基本解、檢驗(yàn)數(shù)等信息，這些表格稱為單純形表。每一個(gè)單純形表相當(dāng)于一個(gè)矩陣，每次迭代就是對矩陣進(jìn)行初等行變換。例3.5 求解下面的線性規(guī)劃問題234123234235max2254626240,1,2,5jZxxxxxxxxxxxxxj 單純形法單純形法解: 單純形表的主要步驟1：構(gòu)造初始單純形表；234123234235max2254626240,1,2,5jZxxxxxxxxxxxxxj單純

25、形表是根據(jù)線性規(guī)劃問題的基本可行解對應(yīng)的典式形式得到的?，F(xiàn)在取X1=(5,0,0,6,24)T求作為初始基本可行解，顯然，模型中目標(biāo)函數(shù)不是典式形式，因此需要將x4=6-x2+4x3代入目標(biāo)函數(shù)Z，經(jīng)整理得到 Z=6+x2+2x3 。 單純形法單純形法構(gòu)造初始單純形表234123234235max2254626240,1,2,5jZxxxxxxxxxxxxxjcj02-210CBXBbx1x2x3x4x50 x15111000 x4601-4100 x52402601cj-zj0 1200iCB表示基變量的系數(shù)，XB表示當(dāng)前基變量，b表示當(dāng)前基變量的取值，cj行為基變量的價(jià)值系數(shù)， 為待填入的

26、按最小比值規(guī)則計(jì)算的值。i 單純形法單純形法解: 單純形表的主要步驟2：迭代求新的基本可行解及其檢驗(yàn)數(shù)；234123234235max2254626240,1,2,5jZxxxxxxxxxxxxxj在上面的單純形表中，x2,x3檢驗(yàn)數(shù)大于零，不滿足最優(yōu)性準(zhǔn)則，需要進(jìn)行迭代。確定中心元素以及進(jìn)、出基變量，將中心元素化為1，中心元素所在列化為單位向量。cj02-210CBXBbx1x2x3x4x50 x151110050 x4601-410-0 x524026014cj-zj0 1200i 單純形法單純形法解: 單純形表的主要步驟2：迭代求新的基本可行解及其檢驗(yàn)數(shù)；234123234235max2

27、254626240,1,2,5jZxxxxxxxxxxxxxjcj02-210CBXBbx1x2x3x4x50 x1112/300-1/63/20 x42207/3012/366/7-2x3401/3101/612cj-zj0 1/320-1/3i 單純形法單純形法解: 單純形表的主要步驟3：繼續(xù)迭代；234123234235max2254626240,1,2,5jZxxxxxxxxxxxxxjcj02-210CBXBbx1x2x3x4x52x23/23/2100-1/40 x437/2-7/20015/4-2x37/2-1/20101/4cj-zj-1/2 000-1/4i 此表格中全部檢驗(yàn)

28、數(shù)均小于等于零，故得到最優(yōu)解 X*=(0,3/2,7/2,37/2,0)T,其對應(yīng)的目標(biāo)函數(shù)值為29/2。最優(yōu)單純形表最優(yōu)單純形表 單純形法單純形法例3.5 用單純形法求解 解: 初始基本可行解為X1=(7,0,0,12,0,10)T,所給模型即為典式，可直接建立單純形表進(jìn)行計(jì)算。23512352342356max323272412438100,1,2,6jZxxxxxxxxxxxxxxxj 單純形法單純形法cj0-130-20CBXBbx1x2x3x4x5x60 x1713-102070 x4120-2410030 x6100-4308110/3cj-zj00 -130-20i 單純形法單純形法cj0-130-20CBXBbx1x2x3x4x5x60 x11015/201/4203x330-1/211/4000 x610-5/20-3/481cj-zj-901/