運(yùn)籌學(xué)之線性規(guī)劃及單純形法

1、 Operations Research 第一章 線性規(guī)劃及單純形法第一章 線性規(guī)劃及單純形法 線性規(guī)劃線性規(guī)劃（Linear Programming，簡稱，簡稱LP）運(yùn)籌學(xué)的一個(gè)重要分支，是運(yùn)籌學(xué)中研究較早、發(fā)展較運(yùn)籌學(xué)的一個(gè)重要分支，是運(yùn)籌學(xué)中研究較早、發(fā)展較快、理論上較成熟和應(yīng)用上極為廣泛的一個(gè)分支。快、理論上較成熟和應(yīng)用上極為廣泛的一個(gè)分支。 19471947年年G.B. Dantying提出了一般線性規(guī)劃問題求解提出了一般線性規(guī)劃問題求解的方法的方法單純形法之后，線性規(guī)劃的理論與應(yīng)用都得單純形法之后，線性規(guī)劃的理論與應(yīng)用都得到了極大的發(fā)展。到了極大的發(fā)展。 6060年來，隨著計(jì)算機(jī)的

2、發(fā)展，線性規(guī)劃已廣泛應(yīng)用年來，隨著計(jì)算機(jī)的發(fā)展，線性規(guī)劃已廣泛應(yīng)用于工業(yè)、農(nóng)業(yè)、商業(yè)、交通運(yùn)輸、經(jīng)濟(jì)管理和國防等各于工業(yè)、農(nóng)業(yè)、商業(yè)、交通運(yùn)輸、經(jīng)濟(jì)管理和國防等各個(gè)領(lǐng)域，成為現(xiàn)代化管理的有力工具之一。個(gè)領(lǐng)域，成為現(xiàn)代化管理的有力工具之一。1 線性規(guī)劃問題及其數(shù)學(xué)模型e.g. 1 資源的合理利用問題問：如何安排生產(chǎn)計(jì)劃，使得既能充分利用現(xiàn)有資源又使總利潤最大？ 表 1 產(chǎn)品 資源 甲 乙 庫存量 A 1 3 60 B 1 1 40 單件利潤 15 25 某工廠在下一個(gè)生產(chǎn)周期內(nèi)生產(chǎn)甲、乙兩種產(chǎn)品，要消耗A、B 兩種資源，已知每件產(chǎn)品對(duì)這兩種資源的消耗，這兩種資源的現(xiàn)有數(shù)量和每件產(chǎn)品可獲得的利潤如

3、表 1。第一章 線性規(guī)劃及單純形法max z = 15x1 +25x2s.t. x1 + 3x2 60 x1 + x2 40 x1，x2 0 解 ： 設(shè) x1，x2 為下一個(gè)生產(chǎn)周期產(chǎn)品甲和乙的產(chǎn)量； 約束條件：Subject tox1 + 3x2 60 x1 + x2 40 x1，x2 0目標(biāo)函數(shù)：z = 15 x1 +25 x2 表 1 產(chǎn)品 資源 甲 乙 庫存量 A 1 3 60 B 1 1 40 單件利潤 15 25決策變量決策變量1 線性規(guī)劃問題及其數(shù)學(xué)模型e.g. 2 營養(yǎng)問題 假定在市場上可買到 B1,B2,Bn n 種食品，第 i 種食品的單價(jià)是 ci , 另外有 m 種營養(yǎng)

4、A1,A2,Am。設(shè) Bj內(nèi)含有 Ai 種營養(yǎng)數(shù)量為 aij (i=1m,j=1n)，又知人們每天對(duì) Ai 營養(yǎng)的最少需要量為 bi。見表2： 表 2 食品 最少 營養(yǎng) B1 B2 Bn 需要量 A1 a11 a12 a1n b1 A2 a21 a22 a2n b2 Am am1 am2 amn bm 單 價(jià) c1 c2 cn 試在滿足營養(yǎng)要求的前提下，確定食品的購買量，使食品的總價(jià)格最低。第一章 線性規(guī)劃及單純形法 表 2 食品 最少 營養(yǎng) B1 B2 Bn 需要量 A1 a11 a12 a1n b1 A2 a21 a22 a2n b2 Am am1 am2 amn bm 單 價(jià) c1 c2

5、 cn 解 ： 設(shè) xj 為購買食品 Bj 的數(shù)量 ( j=1,2,n )（i = 1,2,m）xj0 （j = 1,2,n）0 0 xj lj1m innjjjzc x1. .nijjijs ta xb1 線性規(guī)劃問題及其數(shù)學(xué)模型三個(gè)基本要素三個(gè)基本要素：Note：1、善于抓住關(guān)鍵因素，忽略對(duì)系統(tǒng)影響不大的因素；善于抓住關(guān)鍵因素，忽略對(duì)系統(tǒng)影響不大的因素；2、可以把一個(gè)大系統(tǒng)合理地分解成可以把一個(gè)大系統(tǒng)合理地分解成 n 個(gè)子系統(tǒng)處理。個(gè)子系統(tǒng)處理。1、決策變量決策變量 xj0 2、約束條件約束條件 一組決策變量的線性等式或不等式一組決策變量的線性等式或不等式3、目標(biāo)函數(shù)目標(biāo)函數(shù) 決策變量的線

6、性函數(shù)決策變量的線性函數(shù)第一章 線性規(guī)劃及單純形法 max（min）z = c1x1 + c2x2 + + cnxns.t. a11x1 + a12x2 + + a1nxn （或=，）b1 a21x1 + a22x2 + + a2nxn （或=，）b2 am1x1 + am2x2 + + amnxn （或=，）bm xj 0 （j = 1,2,n）其中aij、bi、cj（i = 1,2,m；j = 1,2,n）為已知常數(shù) 線性規(guī)劃問題的一般形式：線性規(guī)劃問題的一般形式：1 線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)劃問題的標(biāo)準(zhǔn)形式： max z = c1x1 + c2x2 + + cnxns.t. a11

7、x1 + a12x2 + + a1nxn = b1 a21x1 + a22x2 + + a2nxn = b2 am1x1 + am2x2 + + amnxn = bm xj 0 （j = 1,2,n） bi 0 （i = 1,2,m） 特點(diǎn)：特點(diǎn)：1 1、目標(biāo)函數(shù)為極、目標(biāo)函數(shù)為極大化；大化；2 2、除決策變量的、除決策變量的非負(fù)約束外，所有非負(fù)約束外，所有的約束條件都是等的約束條件都是等式，且右端常數(shù)均式，且右端常數(shù)均為非負(fù)；為非負(fù)；3 3、所有決策變量、所有決策變量均非負(fù)均非負(fù)。 第一章 線性規(guī)劃及單純形法如何轉(zhuǎn)化為標(biāo)準(zhǔn)形式？如何轉(zhuǎn)化為標(biāo)準(zhǔn)形式？1、目標(biāo)函數(shù)為求極小值，即為： 。njjjx

8、cz1minnjjjxcz1max 因?yàn)榍?min z 等價(jià)于求 max (-z)，令 z = - z，即化為： 2、約束條件為不等式，njinjijbxxa11njijijbxa1njijijbxa1xn+1 0松弛變量如何處理？如何處理？1 線性規(guī)劃問題及其數(shù)學(xué)模型、右端項(xiàng)右端項(xiàng)b bi i 0 0時(shí)，只需將等式兩端同乘（時(shí)，只需將等式兩端同乘（-1-1）則右端項(xiàng)必大于零則右端項(xiàng)必大于零 4 4、決策變量無非負(fù)約束、決策變量無非負(fù)約束 設(shè)設(shè) xj 沒有非負(fù)約束，若沒有非負(fù)約束，若 xj 0 0，可令，可令 xj = - = - xj ，則則 xj 0 0； 又若又若 xj 為自由變量，即為

9、自由變量，即 xj 可為任意實(shí)數(shù)，可為任意實(shí)數(shù)，可令可令 xj = = xj - xj，且，且 xj , xj 00第一章 線性規(guī)劃及單純形法e.g. 3試將 LP 問題min z = -x1+2x2-3x3 s.t. x1+x2+x3 7 x1-x2+x3 2 -3x1+x2+2x3 = -5 x1,x2 0 化為標(biāo)準(zhǔn)形式。解：令 x3= x4 - x5 其中x4、x5 0；對(duì)第一個(gè)約束條件加上松弛變量 x6 ；對(duì)第二個(gè)約束條件減去松弛變量 x7 ；對(duì)第三個(gè)約束條件兩邊乘以“-1” ；令 z=-z 把求 min z 改為求 max zmax z= x1-2x2+3x4- 3x5 s.t. x

10、1+x2+x4-x5+x6=7 x1-x2+x4-x5-x7=2 3x1-x2-2x4+2x5=5 x1,x2,x4,x5,x6,x70 1 線性規(guī)劃問題及其數(shù)學(xué)模型LP的幾種表示形式：), 2 , 1(0), 2 , 1(. .max11njxmibxatsxczjinjjijnjjj12,ncc cc價(jià)值向量m ax(1). .(2)0(3)zcxs tAxbx1m ax. .0njjjzcxs tp xbx決策向量Tnxxxx,21右端向量0,21iTmbbbbb列向量的第為jAaaapTmjjjj,21系數(shù)矩陣mnmmnnaaaaaaaaaA2122221112112 線性規(guī)劃問題的圖

11、解法定義定義1 在在LP LP 問題中，凡滿足約束條件問題中，凡滿足約束條件(2)(2)、(3)(3)的的 解解 x = (x1,x2,xn)T 稱為稱為LP 問題的可行解，問題的可行解， 所有可行解的集合稱為可行解集（或可行域）。所有可行解的集合稱為可行解集（或可行域）。 記作記作 D= x | Ax = b ,x0 。定義定義2 設(shè)設(shè)LP問題的可行域?yàn)閱栴}的可行域?yàn)镈 D，若存在，若存在x x* *D D，使得，使得 對(duì)任意的對(duì)任意的xD 都有都有c x*c x，則稱，則稱x x* *為為LP LP 問題問題 的最優(yōu)解，相應(yīng)的目標(biāo)函數(shù)值稱為最優(yōu)值，的最優(yōu)解，相應(yīng)的目標(biāo)函數(shù)值稱為最優(yōu)值， 記

12、作記作 z*=c x*。m ax(1). .(2)0(3)zcxs tAxbx2 線性規(guī)劃問題的圖解法max z = 15x1 +25x2s.t. x1 + 3x2 60 x1 + x2 40 x1，x2 0 (40,0)(0,0)BC(30,10)12360 xx1240 xxO(0,20)AL1L2Z=250目標(biāo)函數(shù)變形：目標(biāo)函數(shù)變形：x2=-3/5 x1+z/25x2x1最優(yōu)解最優(yōu)解： x1=30 x2 =10最優(yōu)值最優(yōu)值：zmax=700B B點(diǎn)是使點(diǎn)是使z z達(dá)到最達(dá)到最大的唯一可行點(diǎn)大的唯一可行點(diǎn)第一章 線性規(guī)劃及單純形法LPLP問題圖解法的基本步驟問題圖解法的基本步驟：1、在平面

13、上建立直角坐標(biāo)系；在平面上建立直角坐標(biāo)系；2、圖示約束條件，確定可行域和頂點(diǎn)坐標(biāo)；圖示約束條件，確定可行域和頂點(diǎn)坐標(biāo)；3、圖示目標(biāo)函數(shù)（等值線）和移動(dòng)方向；圖示目標(biāo)函數(shù)（等值線）和移動(dòng)方向；4、尋找最優(yōu)解。尋找最優(yōu)解。2 線性規(guī)劃問題的圖解法max z =3x1 + 5.7x2 s.t. x1 + 1.9x2 3.8 x1 - 1.9x2 3.8 x1 + 1.9x2 11.4 x1 - 1.9x2 -3.8 x1 ，x2 0 x1x2ox1 - 1.9 x2 = 3.8 x1 + 1.9 x2= 3.8x1 + 1.9 x2 = 11.4（7.6,2）D0=3 x1 +5.7 x2 max

14、Z min Z（3.8,4）34.2 = 3 x1 +5.7 x2 可行域可行域x1 - 1.9 x2 = -3.8(0,2)(3.8,0) 綠色線段上的所有點(diǎn)綠色線段上的所有點(diǎn)都是最優(yōu)解都是最優(yōu)解,即有無窮多即有無窮多最優(yōu)解。最優(yōu)解。Zman=34.2第一章 線性規(guī)劃及單純形法max z = 2x1 + 2x2 s.t. 2x1 x2 2 -x1 + 4x2 4 x1，x2 01222xx1244xxOA(,0)x1x2Note:可行域?yàn)闊o界區(qū)域，可行域?yàn)闊o界區(qū)域，目標(biāo)函數(shù)值可無限目標(biāo)函數(shù)值可無限增大，即解無界。增大，即解無界。稱為無最優(yōu)解稱為無最優(yōu)解?？尚杏?yàn)闊o界可行域?yàn)闊o界區(qū)域一定無最區(qū)

15、域一定無最優(yōu)解嗎？優(yōu)解嗎？2 線性規(guī)劃問題的圖解法由以上兩例分析可得如下重要結(jié)論：由以上兩例分析可得如下重要結(jié)論：1、LP LP 問題從解的角度可分為：問題從解的角度可分為： 有可行解有可行解 無可行解無可行解有唯一最優(yōu)解有唯一最優(yōu)解b. 有無窮多最優(yōu)解有無窮多最優(yōu)解C. 無最優(yōu)解無最優(yōu)解2、LP LP 問題若有最優(yōu)解，必在可行域的某個(gè)頂點(diǎn)上取問題若有最優(yōu)解，必在可行域的某個(gè)頂點(diǎn)上取 到；若有兩個(gè)頂點(diǎn)上同時(shí)取到，則這兩點(diǎn)的連線上到；若有兩個(gè)頂點(diǎn)上同時(shí)取到，則這兩點(diǎn)的連線上 任一點(diǎn)都是最優(yōu)解。任一點(diǎn)都是最優(yōu)解。2 線性規(guī)劃問題的圖解法圖解法優(yōu)點(diǎn)：圖解法優(yōu)點(diǎn)：直觀、易掌握。有助于了解解的結(jié)構(gòu)。直觀

16、、易掌握。有助于了解解的結(jié)構(gòu)。圖解法缺點(diǎn)：圖解法缺點(diǎn)：只能解決低維問題，對(duì)高維無能為力。只能解決低維問題，對(duì)高維無能為力。3 線性規(guī)劃問題解的基本性質(zhì)討論如下 LP 問題：m ax(1). .20(3)zc xs tAxbx12,ncc cc價(jià)值向量12,Tnxx xx12,0Tmibbbbb 右 端 向 量111212122212nnmmmnaaaaaaAaaa其中系數(shù)矩陣決策向量 假設(shè) A 的秩為 m ,且只討論 m 0, x20, xk 0，分兩種情況討論： 如果 p1, p2, pk 線性無關(guān)，即 x 的非零分量對(duì)應(yīng)的列向量線性無關(guān)，則由定理1知，它是LP 的一個(gè)基本可行解，定理成立。

17、(2) 如果p1,p2,pk線性相關(guān)，則必存在一組不全為零的數(shù) 1,2, ,k 使得10(5)kjjjp第一章 線性規(guī)劃及單純形法假定有i0，=min0(6)iiix(2)xx(1)xx12(,0,0)Tk 0 (1,2,., )(7)jjxjn(1)(2)0,0,xx111()nnnjjjjjjjjjjxpx ppb(1)(2),AxbAxb(1)(2),xx取作其中由（6）式知，必有即又因?yàn)橛桑?）式知故有，即也是LP的兩個(gè)可行解。3 線性規(guī)劃問題解的基本性質(zhì) 再由 的取法知，在式 (7) 的諸式中，至少有一個(gè)等于零，于是所作的可行解 中，它的非零分量的個(gè)數(shù)至少比 x 的減少1，如果這些非

18、零分量所對(duì)應(yīng)的列向量線性無關(guān)，則 為基可行解，定理成立。 否則，可以從 出發(fā)，重復(fù)上述步驟，再構(gòu)造一個(gè)新的可行解 ，使它的非零分量的個(gè)數(shù)繼續(xù)減少。這樣經(jīng)過有限次重復(fù)之后，必可找到一個(gè)可行解使它的非零分量對(duì)應(yīng)的列向量線性無關(guān)，故可行解必為基可行解。證畢。(1)(2)xx或(1)(2)xx或(1)(2)xx或(3)(4)xx或( )(1)ssxx或( )(1)ssxx或返回0 (1,2,., )(7)jjxjn3 線性規(guī)劃問題解的基本性質(zhì)定理定理 3 3 證明證明設(shè)*12(,)nxxxx是 LP 的一個(gè)最優(yōu)解。如果 x* 是基本解，則定理成立；如果 x* 不是基本解，則由定理2的證明過程可構(gòu)造兩個(gè)

19、可行解(1)*(2)*xxxx它的非零分量的個(gè)數(shù)比 x* 的減少，且有 ， (1)*(2)*,(8)cxcxccxcxc 又因?yàn)?x* 是最優(yōu)解，故有*(1)*(2),(9)cxcxcxcx由式（8）和（9）知，必有(1)(2)*0,ccxcxcx 故 即x(1),x(2) 仍為最優(yōu)解。如果 x(1)或 x(2) 是基可行解，則定理成立。否則，按定理2證明過程，可得基可行解 x(s)或x(s+1),使得( )*(1)*sscxcxcxcx 或即得基可行解 x(s)或x(s+1)為最優(yōu)解。返回第一章 線性規(guī)劃及單純形法LP 問題解的幾何意義定義 5 設(shè)集合 是 n 維歐氏空間中的一個(gè)點(diǎn)集，如果

20、及實(shí)數(shù) (1)(2)(1)xxSnSR(1)(2)xxS、0,1都有則稱 S 是一個(gè)凸集。幾何意義：如果集合中任意兩點(diǎn)連線上的一切點(diǎn)都在 該集合中，則稱該集合為凸集。 Note: 空集和單點(diǎn)集也是凸集。3 線性規(guī)劃問題解的基本性質(zhì)定義定義 6 6 設(shè) 則稱( )1,0,1,2, ,1kiniiixRik且，(1)(2)( )12kkxxxx為點(diǎn) 的一個(gè)凸組合。(1)(2)( )kxxx，定義定義 7 7 設(shè)凸集 兩點(diǎn) 表示為 則稱 x 為 S 的一個(gè)極點(diǎn)（或頂點(diǎn)）。 ,nSR xSxS如果 不能用 中不同的(1)(2)xx，(1)(2)(1)(01)xxx定理定理 4 LP 問題的可行解集,0

21、DxAxb x是凸集。第一章 線性規(guī)劃及單純形法定理定理 5 5 設(shè)設(shè) D 為為 LP 問題的可行解集，問題的可行解集， ，則，則 x 是是 D的極點(diǎn)的充分必要條件是的極點(diǎn)的充分必要條件是 x 為為 LP 問題的基可行解。問題的基可行解。xDprove推論推論 1 1 如果如果 LP 問題的可行解集非空，則極點(diǎn)集合也問題的可行解集非空，則極點(diǎn)集合也一定非空，且極點(diǎn)的個(gè)數(shù)是有限的一定非空，且極點(diǎn)的個(gè)數(shù)是有限的。推論推論 2 2 如果如果 LP 問題有最優(yōu)解，則一定可在可行解集問題有最優(yōu)解，則一定可在可行解集 D 的極點(diǎn)上達(dá)到。的極點(diǎn)上達(dá)到。定理定理 6 6 設(shè)設(shè) LP 問題在多個(gè)極點(diǎn)問題在多個(gè)極

22、點(diǎn) x(1),x(2),x(k) 處取到最優(yōu)處取到最優(yōu)解，則它們的凸組合，即解，則它們的凸組合，即*( )110,1kkiiiiiixx也是也是 LP 問題的最優(yōu)解問題的最優(yōu)解. .（此時(shí)，該（此時(shí)，該LPLP 問題有無窮多最優(yōu)解）問題有無窮多最優(yōu)解）3 線性規(guī)劃問題解的基本性質(zhì)Note:1、如何判斷如何判斷 LP 問題有最優(yōu)解；問題有最優(yōu)解；2、計(jì)算復(fù)雜性問題。計(jì)算復(fù)雜性問題。 設(shè)有一個(gè)設(shè)有一個(gè)5050個(gè)變量、個(gè)變量、2020個(gè)約束等式的個(gè)約束等式的 LP LP 問題，則問題，則 最多可能有最多可能有 個(gè)基。個(gè)基。20135050!4.7 1020!30!C即約即約150150萬年萬年 如果

23、計(jì)算一個(gè)基可行解只需要如果計(jì)算一個(gè)基可行解只需要 1 秒，那么計(jì)算所有秒，那么計(jì)算所有 的基可行解需要：的基可行解需要：1364.7101.510360024365（ 年 ）4 單純形法的基本原理 單純形法單純形法（Simplex Method）是是19471947年由年由 G.B.Dantzig 提出，是解提出，是解 LP 問題最有效的算法之一，問題最有效的算法之一，且已成為整數(shù)規(guī)劃和非線性規(guī)劃某些算法的基礎(chǔ)且已成為整數(shù)規(guī)劃和非線性規(guī)劃某些算法的基礎(chǔ)。 基本思路：基本思路： 基于基于 LP 問題的標(biāo)準(zhǔn)形式，先設(shè)法找到一個(gè)基可問題的標(biāo)準(zhǔn)形式，先設(shè)法找到一個(gè)基可行解，判斷它是否是最優(yōu)解，如果是則

24、停止計(jì)算；否行解，判斷它是否是最優(yōu)解，如果是則停止計(jì)算；否則，則轉(zhuǎn)換到相鄰的目標(biāo)函數(shù)值不減的一個(gè)基可行解則，則轉(zhuǎn)換到相鄰的目標(biāo)函數(shù)值不減的一個(gè)基可行解. .（兩個(gè)基可行解相鄰是指它們之間僅有一個(gè)基變量不（兩個(gè)基可行解相鄰是指它們之間僅有一個(gè)基變量不相同）。相同）。第一章 線性規(guī)劃及單純形法單純形法引例單純形法引例 首先，化原問首先，化原問題為標(biāo)準(zhǔn)形式：題為標(biāo)準(zhǔn)形式：12341310,1101Appppx3, x4 是基變量.34,Bpp是可行基，基變量用非基變量表示：基變量用非基變量表示：x3 = 60 -x1 - 3x2 x4 = 40 -x1 - x2代入目標(biāo)函數(shù)：代入目標(biāo)函數(shù)：z =15

25、 x1+25 x2令非基變量令非基變量 x1= x2=0z=0 基可行解基可行解 x(0)=(0,0,60,40)T是最優(yōu)解嗎？max z = 15x1 +25x2s.t. x1 + 3x2 60 x1 + x2 40 x1，x2 0 max z = 15x1 + 25x2 + 0 x3 + 0 x4 s.t. x1 + 3x2 + x3 = 60 x1 + x2 + x4=40 x1，x2 , x3, x4 0 4 單純形法的基本原理z =15 x1+25 x2x3 = 60 -x1 - 3x2 x4 = 40 -x1 - x2因?yàn)橐驗(yàn)閤2 的系數(shù)大，所以的系數(shù)大，所以x2 換入基變量。換入

26、基變量。x3 = 60 - 3x2 0 x4 = 40 - x2 0誰換出？誰換出？如果如果 x4 換出，則換出，則x2 = 40， x3 = -60，不可行不可行。如果是如果是“+ +”會(huì)怎樣？會(huì)怎樣？如果如果 x3 換出，則換出，則x2 = 20， x4 = 20。260 40min,2031x取最小比值法則最小比值法則所以所以 x3 換出。換出?；兞坑梅腔兞勘硎荆夯兞坑梅腔兞勘硎荆?13413112033212033xxxxxx代入目標(biāo)函數(shù)：代入目標(biāo)函數(shù)：z =500+20/3 x1- 25/3 x3令非基變量令非基變量 x1= x3=0 z=500 基可行解基可行解 x(1)=

27、(0,20,0,20)T大于零！大于零！第一章 線性規(guī)劃及單純形法13213413202550033112033212033zxxxxxxxx因?yàn)橐驗(yàn)閤1 的系數(shù)大，所以的系數(shù)大，所以x1 換入基變量。換入基變量。12020min,301233x因所以所以 x4 換出。換出?；兞坑梅腔兞勘硎荆夯兞坑梅腔兞勘硎荆?34234313022111022xxxxxx代入目標(biāo)函數(shù)：代入目標(biāo)函數(shù)：z =700 5 x3 10 x4令非基變量令非基變量 x3= x4=0 z=700 基可行解基可行解 x(2)=(30,10,0,0)T 因?yàn)榉腔兞康南禂?shù)都小于零，因?yàn)榉腔兞康南禂?shù)都小于零， 所以所

28、以 x(2)=(30,10,0,0)T 是最優(yōu)解是最優(yōu)解 zmax=700 4 單純形法的基本原理 目標(biāo)函數(shù)用非基變量表示時(shí)，非基變量的系數(shù)目標(biāo)函數(shù)用非基變量表示時(shí)，非基變量的系數(shù) 稱為稱為檢驗(yàn)數(shù)檢驗(yàn)數(shù)(40,0)(0,0)(0,20)ABC(30,10)12360 xx1240 xxOL1L2Z=250 x2x1x(0)=(0,0,60,40)T z=0 x(1)=(0,20,0,20)T z=500 x(2)=(30,10,0,0)T z=700 第一章 線性規(guī)劃及單純形法單純形法的基本原理單純形法的基本原理max(1). .(2)0(3)ijmnzcxs tAxbxAaAm=秩 （ ）

29、=1111max()(1 ). .(2 )0,0(3 )BNBNBNBNzc B bcc B N xastxB NxB baxxa稱稱(1a)(2a)(3a)為為LP問題對(duì)應(yīng)于問題對(duì)應(yīng)于基基 B 的典則形式（典式）的典則形式（典式）. .Ax = bBNBxNxb基變量用非基變量表示：基變量用非基變量表示：11BNxB NxB b11BNxB bB Nx代入目標(biāo)函數(shù)：代入目標(biāo)函數(shù)：1111,()()BBNBBNNNBNNNBNBNxzcxccc xc xxcB bB Nxc xc B bcc B N x4 單純形法的基本原理如果記如果記(0)1Bzc B b112(,)NmmnNBcc B N

30、111111(,)mnmnmmmnaaNB Nppaa11( ,)TmbB bbb則典式則典式(1a)(2a)(3a) 可寫成( 0 )11221111122112211222221122m ax. .0(1, 2,)mmmmnnmmmmnnmmmmnnmm mmm mmm nnmjzzxxxs txaxaxaxbxaxaxaxbxaxaxaxbxjn 1jjBjjBjcc Bpcc p第一章 線性規(guī)劃及單純形法(0)11max(1 ). .(1,2,) (2 )0 (1,2, )(3 )njjj mniijjij mjzzxbstxa xbimbxjnb定理定理 7 在在 LP 問題問題 的

31、典式的典式 (1b) (3b)中，中，如果有如果有0 (1,2, )jjmmn則對(duì)應(yīng)于基則對(duì)應(yīng)于基 B 的基可行解的基可行解(0)12( ,0,0)Tmxb bb是是 LP 問題的最優(yōu)解，記為問題的最優(yōu)解，記為12( ,0,0)Tmxb bb相應(yīng)的目標(biāo)函數(shù)最優(yōu)值相應(yīng)的目標(biāo)函數(shù)最優(yōu)值 z*=z(0)此時(shí)，基此時(shí)，基B B稱稱為最優(yōu)基為最優(yōu)基11,0,BNBNBcc B Acc B N4 單純形法的基本原理定理定理 8 在在 LP 問題問題 的典式的典式 (1b) (3b)中，中，(0)11max(1 ). .(1,2,) (2 )0 (1,2, )(3 )njjj mniijjij mjzzxb

32、stxa xbimbxjnb 01,0,0Tmxbb是對(duì)應(yīng)于基是對(duì)應(yīng)于基 B 的一個(gè)基可行解，如果滿足下列條件：的一個(gè)基可行解，如果滿足下列條件：(1)(1)有某個(gè)非基變量有某個(gè)非基變量 xk 的檢驗(yàn)數(shù)的檢驗(yàn)數(shù) k 0 (m+1 k n);(2)(2)aik(i=1,2,m) 不全小于或等于零，即至少有一個(gè)不全小于或等于零，即至少有一個(gè) aik0 (i=1,2,m) ;(3) (3) 0 (i=1,2,m) ,即即x(0) 為非退化的基可行解。為非退化的基可行解。ib則從則從 x(0)出發(fā)，一定能找到一個(gè)新的基可行解出發(fā)，一定能找到一個(gè)新的基可行解 (1)(1)(1)(1)(1)(0)12,.

33、Tnxxxxcxcx使得第一章 線性規(guī)劃及單純形法定理定理 9 在在 LP 問題的典式問題的典式 (1b) (3b)中，如果檢驗(yàn)中，如果檢驗(yàn)數(shù)滿足最優(yōu)準(zhǔn)則數(shù)滿足最優(yōu)準(zhǔn)則 j 0 ( j = m+1 ,n )，且其中有一且其中有一個(gè)個(gè) k = 0 ( m+1 k n )，則該則該 LP 問題有無窮多個(gè)問題有無窮多個(gè)最優(yōu)解。最優(yōu)解。這在應(yīng)用這在應(yīng)用中很有價(jià)中很有價(jià)值值定理定理 10 在在 LP 問題的典式問題的典式 (1b) (3b)中，如果有某中，如果有某個(gè)非基變量的檢驗(yàn)數(shù)個(gè)非基變量的檢驗(yàn)數(shù)k 0 ( m+1 k n )，且有且有0 (1,2,)0ikkaimp即則該則該 LP 問題解無界（無最

34、優(yōu)解）。問題解無界（無最優(yōu)解）。5 單純形法的計(jì)算步驟單純形表( 0 )11221111122112211222221122m ax. .0(1, 2,)mmmmnnmmmmnnmmmmnnmm mmm mmm nnmjzzxxxs txaxaxaxbxaxaxaxbxaxaxaxbxjn c c1 c2 cm cm+1 cm+2 cncBxB x1 x2 xm xm+1 xm+2 xnbc1c2cmx1x2xm 1 0 0 a1m+1 a1m+2 a1n 0 1 0 a2m+1 a2m+2 a2n 0 0 1 amm+1 amm+2 amnb1b2bm檢驗(yàn)數(shù)檢驗(yàn)數(shù) 0 0 0 -z(0)n2

35、m1m第一章 線性規(guī)劃及單純形法如何得到單純形表？1111max()(1 ). .(2 )0,0(3 )BNBNBNBNzc B bcc B N xastxB NxB baxxa cAb檢驗(yàn)數(shù)0B-1b- cB B-1b -z0 I B-1NB-1b 0 N檢驗(yàn)數(shù) B NcB cN I B-1N 0 cN-cB B-1N5 單純形法的計(jì)算步驟e.g.4 列出如下列出如下 LP 問題問題的初始單純形表。的初始單純形表。max z = 4x1 + 3x2 + 2x3 + 5x4 s.t. x1 + 3x2 + x3 + 2x4 = 5 4x1+ 2x2+3x3 +7x4 = 17 x1，x2 ，x

36、3 ，x4 0不妨已知不妨已知x3 、x4 為可行基變量為可行基變量 ccBxB25x3x4檢驗(yàn)數(shù)4 3 2 5x1 x2 x3 x4131242374325b51701-70126-3105-2-117101140-12x(0)=(0,0,1,2 )Tz0 = 12第一章 線性規(guī)劃及單純形法單純形法求解單純形法求解 LP 問題的計(jì)算步驟：問題的計(jì)算步驟：Step 1 找出初始可行基，列初始單純形表找出初始可行基，列初始單純形表, ,確定初確定初始基可行解；始基可行解；jjkP1ka Step 2 檢驗(yàn)各非基變量檢驗(yàn)各非基變量 xj 的檢驗(yàn)數(shù)的檢驗(yàn)數(shù) j , 如果所有如果所有 的的 j 00（

37、j j = 1,2, = 1,2, , n n），則已求得最優(yōu)解，停），則已求得最優(yōu)解，停 止計(jì)算。否則轉(zhuǎn)入下一步；止計(jì)算。否則轉(zhuǎn)入下一步； Step 3 在所有的在所有的 j 0 0 中，如果有某個(gè)中，如果有某個(gè)k 00，所對(duì)，所對(duì) 應(yīng)的應(yīng)的 xk 的系數(shù)列向量的系數(shù)列向量pk00（即（即 aik00，i =1,2, m），則此問題解無界，停止計(jì)算。否則轉(zhuǎn)入下一），則此問題解無界，停止計(jì)算。否則轉(zhuǎn)入下一 步步; ;5 單純形法的計(jì)算步驟Step 4 根據(jù)根據(jù) , ,確定確定 xk為換入為換入基變量，又根據(jù)最小比值法則計(jì)算基變量，又根據(jù)最小比值法則計(jì)算: :確定確定xr為換出基變量。轉(zhuǎn)入下一步

38、為換出基變量。轉(zhuǎn)入下一步; ;max0,1kjjjn min0,1irikikrkbbaimaa 120010kkkrkmnaaPaa rka Step 5 以以 為主元進(jìn)行換基變換，用初等行變換將為主元進(jìn)行換基變換，用初等行變換將 xk 所對(duì)應(yīng)的列向量變換成單位列向量，即所對(duì)應(yīng)的列向量變換成單位列向量，即同時(shí)將檢驗(yàn)數(shù)行中的第同時(shí)將檢驗(yàn)數(shù)行中的第k個(gè)元素也個(gè)元素也變換為零，得到新的單純形表。變換為零，得到新的單純形表。返回返回Step 2 。第一章 線性規(guī)劃及單純形法max z = 15x1 +25x2s.t. x1 + 3x2 60 x1 + x2 40 x1，x2 0 max z = 15

39、x1 +25x2+ 0 x3 + 0 x4s.t. x1 + 3x2 + x3 = 60 x1 + x2 + + x4 = 40 x1，x2 ， x3 ， x4 0 00 ccBxB00 x3x4檢驗(yàn)數(shù)15 25 0 0 x1 x2 x3 x413101101152500b6040001x(0)=(0,0,60,40 )Tz0 = 0 x21/3-500 x(1)=(0,20,0,20 )Tz1 = 500 x10-700 x(2)=(30,10,0,0 )Tz2 = 7001/2檢驗(yàn)數(shù)檢驗(yàn)數(shù)都小于都小于等于零等于零x(2)為最優(yōu)解為最優(yōu)解 zmax = 70060/340/12531/312

40、000-1/312020/3-25/3020/1/320/2/3152/32/310-1/23/2300-1/2100-5-105 單純形法的計(jì)算步驟思考：思考：在單純形法中根據(jù)在單純形法中根據(jù)max0,1kjjjn 確定確定 xk為進(jìn)基變量，是否在這次變換中，使目為進(jìn)基變量，是否在這次變換中，使目標(biāo)函數(shù)值提高最大？標(biāo)函數(shù)值提高最大？ 如果不是，應(yīng)選擇哪個(gè)變量進(jìn)基，保證這如果不是，應(yīng)選擇哪個(gè)變量進(jìn)基，保證這次變換使得目標(biāo)函數(shù)值提高最大？次變換使得目標(biāo)函數(shù)值提高最大？目標(biāo)函數(shù)值能提高多少？目標(biāo)函數(shù)值能提高多少？6 單純形法的進(jìn)一步討論一、初始可行基的求法一、初始可行基的求法 max z = c1

41、x1 + c2x2 + cnxn (1c) s.t. a11x1 + a12x2 + a1nxn = b1 a21x1 + a22x2 + a2nxn = b2 . (2c) am1x1 + am2x2 + amnxn = bm xj0 （j = 1,2, n） (3c) a11x1 + a12x2 + a1nxn + xn+1 = b1 a21x1 + a22x2 + a2nxn + xn+2 = b2 am1x1 + am2x2 + amnxn + xn+m = bm xj0 （j = 1,2, n, n+1, n+m）人工變?nèi)斯ぷ兞苛?、試算法、試算法人造基本解人造基本解： x0 = (

42、0,0,0,b1,bm)T2、人工變、人工變 量法量法6 單純形法的進(jìn)一步討論(1)(1)大大 M M 法法懲罰法 max w = c1x1 + c2x2 + cnxn M ( xn+1 +xn+m ) s.t. a11x1 + a12x2 + a1nxn + xn+1 = b1 a21x1 + a22x2 + a2nxn + xn+2 = b2 am1x1 + am2x2 + amnxn + xn+m = bm xj0 （j = 1,2, n, n+1, n+m）M 是一個(gè)充是一個(gè)充分大的正數(shù)分大的正數(shù)結(jié)論：結(jié)論： 設(shè)121(,)Tnnnmxxxxxx為上述問題的最優(yōu)解為上述問題的最優(yōu)解12

43、0nnn mxxx1、如果 ，則則12( ,)Tnx xx為原問題的最優(yōu)解，這時(shí)的目標(biāo)函數(shù)值為最優(yōu)值；為原問題的最優(yōu)解，這時(shí)的目標(biāo)函數(shù)值為最優(yōu)值；則原問題無可行解。則原問題無可行解。12,nnn mxxx2、如果 不不全為零，全為零，第一章 線性規(guī)劃及單純形法e.g.5用大用大 M 法求解法求解max z = 3x1 - x2 x3s.t. x1 - 2x2 + x3 11 -4x1 + x2 +2 x3 3 -2x1 + x3 = 1 x1，x2 ， x3 0 max z = 3x1 - x2 x3 + 0 x4+ 0 x5 -M x6 -M x7s.t. x1 - 2x2 + x3 + x

44、4 = 11 -4x1 + x2 +2 x3 - x5 + x6 = 3 -2x1 + x3 + x7 = 1 xj 0 ( j = 1,2,7)解解： 引入松弛變量引入松弛變量 x4， x5 和人工變量 x6， x7 得 ccBxB-M0 x4x6檢驗(yàn)數(shù)檢驗(yàn)數(shù) 3 -1 -1 0 0 -M -Mx1 x2 x3 x4 x5 x6 x7131011012-100b110001-2-4-20011x7-M3-1-100-M-M3-4MM-12M-10-M0-M3M3-6MM-13M-10-M004M11/13/21/1x3-113-201100-1100100-11-211M-100-M1-3M

45、M+11/11x2-13001-22-5121000-1-1-M2112/3x13001/3-2/32/3-5/340012/3-4/34/3-7/39000-1/3-1/32/3-M-23 101-M1/3-M 200-0.2M 0 ? 由于人工變量由于人工變量 x6 = x7 = 0, 所以所以, ,得原問題的最優(yōu)解得原問題的最優(yōu)解 x*=(4,1,9,0,0)T 目標(biāo)函數(shù)最優(yōu)值目標(biāo)函數(shù)最優(yōu)值 zmax = 2 Note: 在計(jì)算過程中在計(jì)算過程中, ,某個(gè)人工變量一旦變?yōu)榉腔兞磕硞€(gè)人工變量一旦變?yōu)榉腔兞? ,則該列可被刪去則該列可被刪去 6 單純形法的進(jìn)一步討論(2)(2)兩階段法兩

46、階段法第一階段第一階段： max z = c1x1 + c2x2 + cnxn (1c) s.t. a11x1 + a12x2 + a1nxn = b1 a21x1 + a22x2 + a2nxn = b2 . (2c) am1x1 + am2x2 + amnxn = bm xj0 （j = 1,2, n） (3c) max w = xn+1 xn+2 xn+m (1d) s.t. a11x1 + a12x2 + a1nxn + xn+1 = b1 a21x1 + a22x2 + a2nxn + xn+2 = b2 (2d) am1x1 + am2x2 + amnxn + xn+m = bm

47、xj0 （j = 1,2, n, n+1, n+m） (3d) 判斷原判斷原LP 問題問題（1c） （3c）是否存在可行解，如果存在就找出一是否存在可行解，如果存在就找出一個(gè)初始基可行解；個(gè)初始基可行解；解之可得：解之可得：（a）如果如果 wmax 00（11j jn n）中下標(biāo)）中下標(biāo)最小的檢驗(yàn)數(shù)最小的檢驗(yàn)數(shù)k 所對(duì)應(yīng)的非基變量所對(duì)應(yīng)的非基變量xk作為進(jìn)基變量，作為進(jìn)基變量，即如果即如果min0,1jkjjn(2) 選擇出基變量：當(dāng)按選擇出基變量：當(dāng)按 規(guī)則計(jì)算此值時(shí)，如果規(guī)則計(jì)算此值時(shí)，如果存在存在n n 個(gè)個(gè) ，同時(shí)達(dá)到最小值，就選其中下標(biāo)，同時(shí)達(dá)到最小值，就選其中下標(biāo)最小的那個(gè)基變量作

48、為出基變量。即如果最小的那個(gè)基變量作為出基變量。即如果 則選擇則選擇x xl l作為出基變量。作為出基變量。rr kbaminmin0,1rrikrirkrkbblraimaa 7 線性規(guī)劃應(yīng)用舉例e.g.6 生產(chǎn)計(jì)劃問題生產(chǎn)計(jì)劃問題 某工廠明年根據(jù)合同，每個(gè)季度末向銷售公司提供產(chǎn)某工廠明年根據(jù)合同，每個(gè)季度末向銷售公司提供產(chǎn)品，有關(guān)信息如表，若當(dāng)季生產(chǎn)的產(chǎn)品過多，季末有積余，品，有關(guān)信息如表，若當(dāng)季生產(chǎn)的產(chǎn)品過多，季末有積余，則一個(gè)季度每積壓一噸產(chǎn)品需支付存貯費(fèi)則一個(gè)季度每積壓一噸產(chǎn)品需支付存貯費(fèi)0.20.2萬元萬元. . 現(xiàn)該廠現(xiàn)該廠考慮明年的最佳生產(chǎn)方案，使該廠在完成合同的情況下，全考慮

49、明年的最佳生產(chǎn)方案，使該廠在完成合同的情況下，全年的生產(chǎn)費(fèi)用最低年的生產(chǎn)費(fèi)用最低. .試建立線性規(guī)劃模型試建立線性規(guī)劃模型. .季度 j生產(chǎn)能力（aj）生產(chǎn)成本（d dj j）需求量（bj）13015020240140203201533041014810第一章 線性規(guī)劃及單純形法解：解：方法一方法一設(shè)工廠第設(shè)工廠第 j 季度生產(chǎn)產(chǎn)品季度生產(chǎn)產(chǎn)品 xj 噸噸需求約束：需求約束：第一季度末需交貨第一季度末需交貨 20 20 噸，噸， x1 1 20第二季度末需交貨第二季度末需交貨 20 20 噸，噸， x1 1-20+-20+x2 20這是上季末這是上季末交貨后積余交貨后積余第三季度末需交貨第三季

50、度末需交貨 30 30 噸，噸， x1 1+ +x2 -40+-40+x3 30第四季度末需交貨第四季度末需交貨 10 10 噸，噸， x1 1+ +x2 + +x3 -70-70 + +x4 = 10生產(chǎn)能力約束：生產(chǎn)能力約束：00 xj aj j =1,2,3,4=1,2,3,4季度 j生產(chǎn)能力（aj）生產(chǎn)成本（d dj j）需求量（bj）13015020240140203201533041014810生產(chǎn)、存儲(chǔ)費(fèi)用：生產(chǎn)、存儲(chǔ)費(fèi)用：第一季度：第一季度：1515x1第二季度第二季度: 14: 14x2+0.2(x1 1-20-20)第三季度第三季度: 15.3: 15.3x3+0.2(x1

51、 1+ +x2 -40-40)第四季度第四季度: 14.8: 14.8x4 +0.2(x1 1+ +x2 + +x3 -70-70 )min z =15.6x1 +14.4x2 +15.5x3 + 14.8x4 -26 s.t. x1 1+ +x2 40 , 40 , x1 1+ +x2 + +x3 7070 x1+x2 +x3 + x4 =80, 20 x130,030,0 x240,040,0 x320,020,0 x410.10.7 線性規(guī)劃應(yīng)用舉例季度 j生產(chǎn)能力（aj）生產(chǎn)成本（d dj j）需求量（bj）13015020240140203201533041014810方法二方法二設(shè)第設(shè)第 i 季度生產(chǎn)而用于第季度生產(chǎn)而用于第 j 季度末交貨的產(chǎn)季度末交貨的產(chǎn)品