工程優(yōu)化課件第5章線性規(guī)劃

1、第五章線性規(guī)劃 線性規(guī)劃問題舉例 線性規(guī)劃的標(biāo)準(zhǔn)形式及圖解法 線性規(guī)劃的基本概念及基本性質(zhì) 單純形法 兩階段法及大 M 法 線性規(guī)劃的對偶理論修正單純形法對偶單純形法XiDian University1線性規(guī)劃問題舉例例 1:某工廠擁有 A、B、C三種類型的設(shè)備，生產(chǎn)甲、乙兩種產(chǎn)品。每件產(chǎn)品在生產(chǎn)中需要占用的設(shè)備機(jī)時數(shù)，每件產(chǎn)品可以獲得的利潤以及三種設(shè)備可利用的時數(shù)如下表所示，問題：工廠應(yīng)如何安排生產(chǎn)可獲得最大的總利潤？解：設(shè)變量 xi 為第i 種（甲、乙）產(chǎn)品的生產(chǎn)件數(shù)（ i 1，2）。XiDian University根據(jù)題意，我們知道兩種產(chǎn)品的生產(chǎn)受到設(shè)備能力（機(jī)時數(shù)）的限制。該問題建立

2、的數(shù)學(xué)規(guī)劃模型如下：XiDian University產(chǎn)品甲產(chǎn)品乙設(shè)備能力（h）設(shè)備A3265設(shè)備B2140設(shè)備C0375利潤（元/件）15002500maxz = 1500x1 + 2500x2目標(biāo)函數(shù)約束條件3x1 + 2x2 65s.t.2x1 + x2 403x2 75x1 0, x2 0XiDian University例 2（運(yùn)輸問題）一個制造廠要把若干單位的產(chǎn)品從 A1 , A2 兩個倉庫發(fā)送到零售點(diǎn)B1 , B2 , B3 , B4 。倉庫 Ai 能供應(yīng)產(chǎn)品的數(shù)量為ai (i = 1, 2) ，零售點(diǎn)Bj 所需產(chǎn)品的數(shù)量為bj ( j = 1, 2, 3, 4) 。假設(shè)能供應(yīng)的

3、總量等于需要的總24量，即 ai=bj。且已知從倉庫 Ai 運(yùn)一個單位i=1j =1的產(chǎn)品到Bj的運(yùn)價(jià)為cij 。問應(yīng)如何安排運(yùn)輸，XiDian University才能既滿足各地的需要，又使所花費(fèi)的運(yùn)輸總費(fèi)用最?。拷猓杭俣ㄟ\(yùn)費(fèi)與運(yùn)量成正比。設(shè)由倉庫 Ai 運(yùn)往零售點(diǎn)Bj的貨物數(shù)量為 xij24，S 為運(yùn)輸總費(fèi)用，則min S = i=1cij xij= ais.t.xijij = bjxijji=xij 0,i = 1,2,j = 1,2,3,4XiDian University以上兩個例子,從數(shù)學(xué)上來講,它們的共同特征是:(1) 每個問題都用一組決策變量( x1 , x2 ,L, xn )

4、表示某一方案,這組未知數(shù)的值就代表一個具體的方案,通常要求這些未知數(shù)取值是非負(fù)的。(2)條件(稱為約束條件),這些條存在一定的件都可以用關(guān)于決策變量的一組線性等式或不XiDian University或不等式來表示。(3)都有一個目標(biāo)要求,并且這個目標(biāo)可表示為這組決策 變量的線性函數(shù)(稱為目標(biāo)函數(shù)),按研究問題的不同,要求目標(biāo)函數(shù)實(shí)現(xiàn)最大化或最小化。滿足以上三個條件的數(shù)學(xué)模型稱為線性規(guī)劃數(shù)學(xué)模型。XiDian University在一組線性等式或不等式的約束條件之下，求一個線性函數(shù)的最大值或最小值的問題，稱為線性規(guī)劃問題。其一般形式為(1.1)和(1.2)形式。(Min)Max z = c1

5、x1 + c2 x2 +L+ cn xn(1.1)+ a12 x2 +L+ a1n xn (=, )b1s.t.a11 x1a21 x1+ a22 x2 +L+ a2n xn (=, )b2LL(1.2)+ am2 x2 +L+ amn xn (=, )bmam1 x1x1 , x2 ,L, xn 0XiDian University2線性規(guī)劃的標(biāo)準(zhǔn)形式和圖解法一、線性規(guī)劃問題的標(biāo)準(zhǔn)形式一般的線性規(guī)劃問題總可以寫成下列標(biāo)準(zhǔn)形式：nmin cj x j j =1(2.1)n aij x j j =1x j 0= bii = 1,2,L,m (2.2)(LP)s.t.j = 1, 2,L, n(2

6、.3)令c = (c , c ,L, c)Tn-價(jià)格系數(shù)或成本系數(shù)，12右端向量b = (b , b ,L, b )T , b 0, i = 1, 2,L, m ，12miXiDian Universityx = (x , x ,L, x)T12n a11 A1a1ninLL LA = a = M = ( PLP )ai11n約束矩陣aamn m Am1劃問題（LP）也可寫成：min cT xs.t. Ax = bx 0于是，線或XiDian Universitymin cT xs.t. Ai x = bix 0i = 1, 2,L, m或min cT xn Pj x j= bs.t.j =1

7、x 0XiDian University滿足約束條件(2.2），(2.3)的向量 x 是可行解.全體可行解構(gòu)成LP 的可行域.當(dāng)可行域?yàn)榭占瘯r，稱此線性規(guī)劃無可行解或無解。當(dāng)可行域非空，但目標(biāo)函數(shù)值在可行域上無界， 則稱此線性規(guī)劃無界或無最優(yōu)解.結(jié)論：線性規(guī)劃問題（LP）的可行域是凸集.各種形式的線性規(guī)劃都可化為標(biāo)準(zhǔn)形線性規(guī)劃：XiDian Universitymin(-c)T x ；1.若給出的是max cT x ，則可轉(zhuǎn)化為n2.若約束條件中含有不等式 aij x j bi ，增加松弛j =1 0xn+i變 量， 把 上 述 約 束 化 為 等 式 約 束n aij x j + xn+i=

8、 bi ，而目標(biāo)函數(shù)保持不變；j =1n3.若約束條件中含有不等式 aij x j bi ，增加松弛j =1變量 xn+i 0 ，把上述約束化為等式約束XiDian Universityn aij x j - xn+i= bi ；j =14.若第i 個等式約束中bi 0j x jjR從而得到使得目標(biāo)函數(shù)值減少的新的基本可行解。為此，在原來的n - m 個非基變量中，使得XiDian Universityn - m - 1 個變量仍取零值，而另一個非基變量，比如 xk 增大，即取正值，以便實(shí)現(xiàn)我們的目的。x j ( j R)那么如何確定下標(biāo)k 呢？由（*）式，當(dāng)取值相同時， s （正數(shù)）越大，目

9、標(biāo)函數(shù)至下j降得越多，因此選擇 xk ，使得s k = maxs j jR這里假定s k 0 ， xk 由零變?yōu)檎龜?shù)后，得到方程= B-1b - B-1 p x= b - yk x組 Ax = b 的解 xBkkXiDian Universityk是m 維列向量， b = B-1b, yk= B-1 pk其中b 和 yk，將 xB 按分量寫出來，即xykbB111xykBbxB = = - 22 xk2MMMxykbm m m BxN = (0, 0,LTxk , 0,L, 0)在新得到的點(diǎn)處，目標(biāo)函數(shù)值是XiDian Universityf = CBBb - s xT-1kk再來分析怎樣確定

10、 xk 的取值。一方面，由上式，xk 取值越大函數(shù)值下降越多；另一方面，根據(jù) xB的表達(dá)式，xk 的取值受到可行性的限制，它不能= B-1 pk 0 時），對某個i ，當(dāng)無限的增大（當(dāng) ykx 0 0 0ykx時， k 取任何值時，總成立，而當(dāng)Biix= b - yk x 0yk時，為保證，就必須取值Biiikibix x 0。因此，為了使，應(yīng)令kkyiBX D an Universityix= min bi| yk 0 =brkikykyirbr后，原來的基變量 xB= 0 ，得到新的可xk 取值行解kyrrx = (xT, x,L, x, 0, x, 0,L, x , 0,L, 0)B1B

11、2Br-1Br+1k這個解一定是基本可行解。這是因?yàn)樵瓉淼幕鵅 = ( pB , pB ,L, pB ,L, pB)12rm中的m 個列是線性無關(guān)的，其中不包含 pk ，由于XiDian University= B-1 pk ，故ykmp= Byk =ky pkiBii=1是向量組 pB , pB12,L, pBr ,L, pBm即 pk的線性組合， 0ykpp且系數(shù) r。因此，用取代后，得到的Brk向量組 pB , pB ,L, pk ,L, pB12m也是線性無關(guān)的。因此，新的可行解 x 的正分量對應(yīng)的列向量是線性無關(guān)的，故 x 為基本可行解。XiDian University經(jīng)上述轉(zhuǎn)換，

12、 xk 由原來的非基變量變成基變量，而原來的基變量 xB變成非基變量。在新的可r行解處，目標(biāo)函數(shù)值比原來減少了s k xk 。重復(fù)以上過程，可以進(jìn)一步改進(jìn)基本可行解，直至（*） 中所有s j 均非正數(shù)，以致任何一個非基變量取正值都不能使目標(biāo)函數(shù)值減少為止。選取哪個基變量離基及哪個非基變量進(jìn)基的具體方法如下：XiDian University（1）確定進(jìn)入基的變量s k = maxs| s j 0 ，則取 xk 為進(jìn)入一般的，令j基的變量， Pk 為進(jìn)入基的向量。（2）確定離開基的變量（a） 設(shè)已確定xk 為進(jìn)基變量，令bl 0= minbi 0 | b 0,1 i m，ikbblkik由此確定

13、變量 xl 由基變量化為非基變量。XiDian University（b）對原來的 T(B)進(jìn)行適當(dāng)變換，使第k 列變?yōu)閱挝幌蛄浚渲械趌 個分量為 1，構(gòu)造新基 B 的T (B) = (b/ )單純形為ij= blj, j = 0,1,L, n/bljblk- bljb= b, j = 0,1,L, n, i = 0,1,L, m, i l/bljijikblkXiDian University定理 4.1（最優(yōu)性判別定理）若在極小化問題中,對于某個基本可行解,所有s 0 ,則這個基本可行解是最優(yōu)解；若在極大j化問題中, 對于某個基本可行解, 所有s 0 ,則中j這 個基本可行解是最優(yōu)解。其

14、s= CB Bp - c j = 1, 2,L, n-1jj稱為檢驗(yàn)數(shù)。jXiDian University例1考慮標(biāo)準(zhǔn)線性規(guī)劃min f = 2x1 + x2x1 + x2 + x3-x1 + x26x1 + 2x2= 5= 0= 21s.t.+ x4+ x5x1 ,L, x5 0x3 , x4 , x5考 慮 基 變 量x = (0, 0, 5, 0, 21)T對 應(yīng) 的 基 本 可 行 解x , x， 非 基 變 量的 判 別 數(shù)12s1 = -2 0,s 2= -1 cT x 。新的基本可行解 x ，則3單純形方法的基本步驟（以極小化問題為例）假設(shè)已有一個可行基 B = (Pj , P

15、j ,L, Pj12m) ，作對應(yīng)于基B 的單純形表T (B) ，如果所有的檢驗(yàn)數(shù)都小于或等于 0，則XiDian UniversityStep1:Step2:關(guān)于基B 的基本可行解便是（LP）的最優(yōu)解，算法結(jié)束；否則轉(zhuǎn) step3；若檢驗(yàn)數(shù)中有s r 0 ，使T (B) 中 xr 所在Step3:-BP = (bmr ) 0 ，則（LP）無最優(yōu)1, b,L, b的列r1r2r解，算法終止，否則轉(zhuǎn) step4；Step4:令r 為最大正檢驗(yàn)數(shù)中指標(biāo)最小者，即r = minl | s l = max s j s j 0取 xr為進(jìn)基變量；令 js 為比值最小的行中指標(biāo)最XiDian Univer

16、sity小者，即| bk 0= min bi 0 ,1 i mj = min jskbbbir 0krir取 x j 為離基變量。sStep5: 換基迭代：以bsr 為主元進(jìn)行s,r旋轉(zhuǎn)變換，得到新的單純形表T (B% ) ，以 B% 取代 B，返回 step2。注：對極大化問題，可給出類似的步驟，只是確定進(jìn)基變量的準(zhǔn)則不同，應(yīng)令s l= min s j 。s j 0 ，-k 0 ，則此線性規(guī)劃沒有最1BP且相應(yīng)的列向量優(yōu)解.定理 4.3對于非退化的線性規(guī)劃問題，從任何基本可行解開始，經(jīng)有限次迭代，或達(dá)到一個最優(yōu)基本可行解，或得出線性規(guī)劃問題無界的結(jié)論.注：對于退化情形，可以證明，如果最優(yōu)解存

17、在， 只要采取一定的措施，也能做到有限步收斂。XiDian University例 1 求解線性規(guī)劃問題min f = -2x1 - x2x1 + x2 + x3-x1 + x26x1 + 2x2= 5= 0= 21s.t.+ x4+ x5x j 0, j = 1, 2,L, 5解：取可行基為B = (P3 , P4 , P5 ) ，對應(yīng)的基本可行解為x = (0, 0, 5, 0, 21)T，1建立初始單純形表T (B) 如下：XiDian University2. maxs1, s2=2= s1, r =1,所以x1 為進(jìn)基變量.3. x1 對應(yīng)的的列向量中有正分量存在，bk 0= min

18、bi 0521= 21,1 i m = min,bkrbir166bir 0iXiDian UniversityxBx1x2x3x4x5x3 x4 x511100-11010620015021f210000取s=3,故x5 為離基變量；故x1對應(yīng)列與x5對應(yīng)行的相交處的b31=6為主元素,4.以b31=6為主元進(jìn)行旋轉(zhuǎn)變換得新的單純形表；xBx1x2x3x4x5x3 x4 x102/30-1/604/311/611/301/63/27/27/2f01/300-1/3XiDian University-75.maxs2=1/3= s2, 所以r=2，故x2 為進(jìn)基變量；6. x2對應(yīng)的列向量中有

19、正分量存在，bk 0, i mminbir 0min,bkr4 / 3 1 / 36ir取s=1,故x3 為離基變量；故x2對應(yīng)列與x5對應(yīng)行的相交處的b21=2/3為主元素；7.以b21=2/3為主元進(jìn)行旋轉(zhuǎn)變換得新的單純形表；XiDian University8. 這時，檢驗(yàn)數(shù)全部小于等于0，即目標(biāo)函數(shù)已不可能再減小，于是得到最優(yōu)解：x = (11/4,9/4,0,1/2,0)T目標(biāo)函數(shù)的最小值為： f = -31/4XiDian UniversityxBx1x2x3x4x5x2 x4 x1013/20-1/400-211/210-1/201/49/41/211/400-1/20-1/4-

20、31/45初始基本可行解的求法用單純形法解線性規(guī)劃時，需要先有一個初始基本可行在前邊例子中，約束矩陣中含有，且b 0 ，則可取初始基本可一個單位矩陣行基 B = I，即可得到一個基本可行解，但在一般情況下，難以憑觀察得出初始可行基，甚至有無可行基都難以判定基本可行解的一般方此有必要給出尋找初始XiDian University考慮標(biāo)準(zhǔn)形式的線性規(guī)劃問題：cT x Ax = bx 0mins.t.(LP)不妨設(shè)b 0 ，但并不要求 A 為行滿秩矩陣。對于一般標(biāo)準(zhǔn)型的線性規(guī)劃問題，約束方程組的系數(shù)矩陣中不包含單位矩陣。本節(jié)給出引進(jìn)人工變量，構(gòu)造一個單位矩陣，從而得到初始基XiDian Univer

21、sity本可行解的方法。尋找初始基本可行解的方法主要有兩階段法和大M 法。一兩階段法算法的第一階段：用單純形法消去人工變量（如可能的話），即把人工變量換成非基變量，求出（LP）的一個基本可行解。m對 上 述 （ LP ）， 引 入 0(i = 1,L, m) 后，XiDian University個 人 工 變 量xn+i用單純形方法求解如下的輔助問題（ALP）min g = eT xa s.t.Ax + xa = bx 0, xa 0me為 分 量 全 為 1其 中的維 列 向 量 ，xa= (x)T,L, x是n+1n+m x = 0 人工變量構(gòu)成的m 維列向量。顯然， x b 為 a （

22、ALP）的一個基本可行解。XiDian University設(shè)（ALP）是非退化的，求解（ALP）得到的最 x優(yōu)基本可行解是 x ，此時必有下列情形之一：a情形 1： xa 0 ，這時（LP）無可行解。因?yàn)?x = x 則 0 是（ALP）如果（LP）有可行解的可行解，在此點(diǎn)，（ALP）目標(biāo)函數(shù)值g = 0 x + eT 0 = 0 eT xa ，而eT xa 是（ALP）的最優(yōu)值。XiDian University情形 2： xa = 0 ，且 xa 的分量都是非基變量，此 x = x 時m 個基變量都是原來的變量，又知 x 0 a是（ALP）的基本可行解，因此 x = x 是（LP） 的一

23、個基本可行解。情形 3： xa = 0 ，且 xa 的某些分量是基變量，這時可用主元消去法把原來變量中的某些非基變量引進(jìn)基，替換出基變量中的人工變量，再開始XiDian University兩階段法的第二階段。應(yīng)指出，為替換出人工變量而采用的主元消去法，在主元選擇上，并不要求遵守單純形法確定離進(jìn)基變量的規(guī)則。設(shè) xn+s 為基變量，則（ALP）關(guān)于B 的單純形表中xn+s 所在的第s 行對應(yīng)的方程為xn+ s + bsj x j + bs,n+i xn+i= 0（*）jJiI這里J 為 x1,L, xn中非基變量的指標(biāo)集，I 為人工變量中非基變量的指標(biāo)集。XiDian University=

24、0( j J ) ，表明第s 個方若（*）式中所有的bsj程是多余的，應(yīng)刪去，這相當(dāng)于從B 的單純形表中刪去第s 行。若（*）中存在r J , 使bsr 0 ，則以bsr為主元進(jìn)行轉(zhuǎn)軸運(yùn)算，得到（ALP）的新的單純形表，它對應(yīng)的基本可行解仍為（ALP）的最優(yōu)解，但新的基變量中減少了一個人工變量xn+s ，若新的基變量中還有人工變量，重復(fù)此法，經(jīng)有限次，必能化為情形 2。XiDian University綜上所述，對不具有明顯可行基的（LP），可先用單純形法求解輔助性性規(guī)劃問題（ALP），解的結(jié)果或者說明（LP）無可行解，或者找到（LP）的一個基本 可行解，然后再從這個基本可行解開始應(yīng)用單純形法求解（LP），此即兩階段法的第二階段。將目標(biāo)函數(shù) g 用非基變量表示如下：mmnmnmg = xn+i= (b - ai