[企業(yè)管理]MBA運籌學2第二-五章線性規(guī)劃

1、irwin/mcgraw-hill the mcgraw-hill companies, inc., 1999第二三四五章第二三四五章 線性規(guī)劃線性規(guī)劃2.1 線性規(guī)劃問題與標準形式線性規(guī)劃問題與標準形式2.2 線性規(guī)劃問題的幾何解釋線性規(guī)劃問題的幾何解釋2.3 單純型法方法單純型法方法irwin/mcgraw-hill the mcgraw-hill companies, inc., 1999問題的提出（問題的提出（1）【例】派公司是一個生產(chǎn)高爾夫器材的小型公司，公司決定生產(chǎn)中高價位的高爾夫袋。產(chǎn)品的生產(chǎn)過程有四個程序：切割并印染原材料、縫合、成型、檢查和包裝，不同價位高爾夫袋生產(chǎn)程序的耗時

2、信息如下表，表中還列出了派公司在本輪生產(chǎn)過程中每個部門的最大生產(chǎn)時間。irwin/mcgraw-hill the mcgraw-hill companies, inc., 1999問題的提出（問題的提出（2）會計部門的數(shù)據(jù)表明，生產(chǎn)一個標準袋的利潤是10美元，生產(chǎn)一個高級袋的利潤是9美元。如何安排兩種產(chǎn)品的生產(chǎn)才能使公司獲得最大利潤？耗時/標準袋耗時/高檔袋最大生產(chǎn)時間切割印染0.70.71 1630630縫合0.50.55/65/6600600成型1 12/32/3708708檢查包裝0.10.10.250.25135135irwin/mcgraw-hill the mcgraw-hill

3、companies, inc., 1999問題的提出（問題的提出（3）設x1、x2分別為兩種高爾夫袋的生產(chǎn)量，則該計劃問題可用如下數(shù)學模型表示為：0,13525. 01 . 07083/26006/55 . 06307 . 0. .910max212121212121xxxxxxxxxxtsxxsirwin/mcgraw-hill the mcgraw-hill companies, inc., 19992.1 線性規(guī)劃問題與標準形式線性規(guī)劃問題與標準形式 典例典例1-生產(chǎn)計劃問題生產(chǎn)計劃問題例例2. 某工廠在計劃期內(nèi)要生產(chǎn)產(chǎn)品i和產(chǎn)品ii這兩種產(chǎn)品，已知生產(chǎn)單位產(chǎn)品所需的設備臺時及a、b兩種

4、設備計劃期的有效臺時，如下表：問如何安排生產(chǎn)最有利？ 產(chǎn)品 i 產(chǎn)品 ii 設備有效臺時 設備 a 2 2 8 設備 b 0 2 4 單位產(chǎn)品利潤 1 元 2 元 解 設產(chǎn)品i和產(chǎn)品ii的產(chǎn)量分別為x1和x2件, 利潤為z, 則: z = x1 + 2 x2max目標函數(shù) 2 x1 + 2 x2 8 0 x1 + 2 x2 4 x1 , x2 0約束條件s.t.非負條件irwin/mcgraw-hill the mcgraw-hill companies, inc., 1999irwin/mcgraw-hill the mcgraw-hill companies, inc., 1999abov

5、e,irwin/mcgraw-hill the mcgraw-hill companies, inc., 1999irwin/mcgraw-hill the mcgraw-hill companies, inc., 1999irwin/mcgraw-hill the mcgraw-hill companies, inc., 1999 典例典例2-配料問題配料問題 z = 3x1 + 2 x2min目標函數(shù) 12 x1 + 3 x2 4 2 x1 + 3 x2 2 3 x1 + 15 x2 5 x1 + x2 = 1 x1 , x2 0約束條件s.t.irwin/mcgraw-hill the

6、mcgraw-hill companies, inc., 1999典例典例3-食譜問題食譜問題例3食品營養(yǎng)成份大米白菜雞蛋豬肉營養(yǎng)成份的需要量(周)蛋 白 質(zhì)a11a12a13a14b1某維生素a21a22a23a24b2某礦物質(zhì)a31a32a33a34b3單 價(元)c1c2c3c4問在滿足營養(yǎng)的條件下,如何安排食譜最有利?解:設每人每周食用大米、白菜、雞蛋、豬肉的數(shù)量分別為x1、 x2、 x3、 x4z=c1x1+ c2x2+ c3x3+ c4x4mina11x1+ a12x2+ a13x3+ a14x4 b1=a21x1+ a22x2+ a23x3+ a24x4 = b2a31x1+ a

7、32x2+ a33x3+ a34x4 = b3x1, x2 , x3 , x4 0irwin/mcgraw-hill the mcgraw-hill companies, inc., 1999 食譜問題的拓展食譜問題的拓展食品營養(yǎng)成份大米白菜雞蛋豬肉食品n營養(yǎng)成份的需要量(周)蛋 白 質(zhì)a11a12a13a14a1nb1某維生素a21a22a23a24a2nb2某礦物質(zhì)a31a32a33a34a3nb3營養(yǎng)成份 mam1am2am3am4amnbn單 價(元)c1c2c3c4cn問在滿足營養(yǎng)的條件下,如何安排食譜最有利?z=c1x1+ c2x2+ c3x3+ c4x4 + . + cnxnmi

8、na11x1+ a12x2+ a13x3+ a14x4 +.+ a1nxn = b1a21x1+ a22x2+ a23x3+ a24x4 +.+ a2nxn = b2a31x1+ a32x2+ a33x3+ a34x4 +.+ a3nxn = b3am1x1+ am2x2+ am3x3+ am4x4 +.+ amnxn = bmx1, x2 , x3 , . xn 0數(shù)學模型irwin/mcgraw-hill the mcgraw-hill companies, inc., 1999new bedford steel煉焦煤供應問題 ashleybedfordconsoldunbyearlamf

9、lorencegastonhopt 供應量 (千噸/年） 300 600 510 655 575 680 450490工會（u）/非工會（n） u u n u n u n n 卡車（t）/ 鐵路（r） r t r t t t r r可燃率（%） 15 16 18 20 21 22 23 25 價格 (/ 噸） 49.50 50.00 61.00 63.50 66.50 71.00 72.5080.00new bedford steel (nbs)是一家小型的煉鋼企業(yè)。煉焦煤是一家小型的煉鋼企業(yè)。煉焦煤(coking coal)是是nbs公司煉鋼時所必需的一種原材料，每年的需求量是公司煉鋼時所必

10、需的一種原材料，每年的需求量是100至至150萬噸?，F(xiàn)在到了萬噸?，F(xiàn)在到了該公司計劃明年生產(chǎn)的時候了，他們收到了來自八家供應商的報價。該公司計劃明年生產(chǎn)的時候了，他們收到了來自八家供應商的報價。irwin/mcgraw-hill the mcgraw-hill companies, inc., 1999new bedford steel煉焦煤供應問題irwin/mcgraw-hill the mcgraw-hill companies, inc., 1999nbs供應問題的數(shù)學表達變量：a = 從 ashley 處定購的煉焦煤量（千噸）b = 從 bedford 處定購的煉焦煤量（千噸）c =

11、 從 consol 處定購的煉焦煤量（千噸）d = 從 dunby 處定購的煉焦煤量（千噸）e = 從 earlam 處定購的煉焦煤量（千噸）f = 從 florence處定購的煉焦煤量（千噸）g = 從 gaston 處定購的煉焦煤量（千噸）h = 從 hopt 處定購的煉焦煤量（千噸）irwin/mcgraw-hill the mcgraw-hill companies, inc., 1999供應成本成：49.5a + 50b + 61c + 63.5d + 66.5e + 71f + 72.5g + 80h供應約束：a + b + c + d + e + f + g + h = 1,22

12、5工會煤礦的約束：a + b c + d e + f g h 0卡車運輸量約束：b + d + e + f 720火車運輸量約束：a + c + g + h 650平均可燃率約束：可改寫成： 4a 3b c + d + 2e + 3f + 4g + 6h 0各煤礦的煉焦煤供應量約束：a 300，b 600，c 510，d 655，e 575，f 680，g 450， h 490非負約束：a 0，b 0，c 0，d 0，e 0，f 0，g 0，h 019hgfedcbah25g23f22e21d20c18b16a15irwin/mcgraw-hill the mcgraw-hill compan

13、ies, inc., 1999nbs的煉焦煤供應問題的線性最優(yōu)化模型的煉焦煤供應問題的線性最優(yōu)化模型minimize cost=49.5a+50b+61c+63.5d+66.5e+71f+72.5g+80hsubject to：supply：a + b + c + d + e + f + g + h = 1,225union：a + b c + d e + f g h 0truck：b + d + e + f 720rail： a + c + g + h 650vol： 4a 3b c + d + 2e + 3f + 4g + 6h 0acap：a 300bcap：b 600ccap：c 51

14、0dcap：d 655ecap：e 575fcap： f 680gcap：g 450hcap：h 490nonnegativity conditions：a0, b0, c0, d0, e0, f0, g0, h0irwin/mcgraw-hill the mcgraw-hill companies, inc., 1999nbs的煉焦煤供應問題的線性最優(yōu)化模型的煉焦煤供應問題的線性最優(yōu)化模型求解，得：a= 55千噸， b=600千噸， c= 0千噸， d= 20千噸， e=100千噸， f= 0千噸， g=450千噸， h= 0千噸；最小成本 = 73,267.50千美元；平均供應成本 = 7

15、3,267.50 / 1,225 = 59.81美元/噸irwin/mcgraw-hill the mcgraw-hill companies, inc., 1999二、線性規(guī)劃數(shù)學模型的幾種表達形式二、線性規(guī)劃數(shù)學模型的幾種表達形式一般形式一般形式目標函數(shù)： max （min） z = c1 x1 + c2 x2 + + cn xn 約束條件： s.t. a11 x1 + a12 x2 + + a1n xn （ =, ）b1 a21 x1 + a22 x2 + + a2n xn （ =, ）b2 am1 x1 + am2 x2 + + amn xn （ =, ）bm x1 ，x2 ， ，xn

16、 0簡寫形式形式目標函數(shù)： max （min） z = 約束條件： s.t. （ =, ）bi , i=1,2,. m xj 0 , j=1 , 2 , . n 1njjjc x1nijjjaxirwin/mcgraw-hill the mcgraw-hill companies, inc., 1999向量形式c=(c1 , c2, , cn ) 價值向量,二、線性規(guī)劃數(shù)學模型的幾種表達形式二、線性規(guī)劃數(shù)學模型的幾種表達形式12mbbbb限定向量12jjjmjaapa變量xj對應的系數(shù)列向量12nxxxx1(min)(,)0njjjm axzcxp xbx irwin/mcgraw-hill

17、the mcgraw-hill companies, inc., 1999二、線性規(guī)劃數(shù)學模型的幾種表達形式二、線性規(guī)劃數(shù)學模型的幾種表達形式矩陣形式111212122212nnmmmnaaaaaaaaaa約束條件系數(shù)矩陣max(min)( , )0zcxaxbx irwin/mcgraw-hill the mcgraw-hill companies, inc., 1999第二節(jié)第二節(jié) 線性規(guī)劃問題的標準形式線性規(guī)劃問題的標準形式一、標準形式標準形式目標函數(shù)： max z = c1 x1 + c2 x2 + + cn xn 約束條件： s.t. a11 x1 + a12 x2 + + a1n

18、xn = b1 a21 x1 + a22 x2 + + a2n xn = b2 am1 x1 + am2 x2 + + amn xn = bm x1 ，x2 ， ，xn 0max0zcxaxbx或即:同時滿足如下四個條件:目標函數(shù)求極大約束條件全為等式約束條件右端常數(shù)項全為非負變量取值全為非負irwin/mcgraw-hill the mcgraw-hill companies, inc., 19992.1 線性規(guī)劃問題與標準形式線性規(guī)劃問題與標準形式 為了今后討論的方便，我們稱以下兩種形式的線性規(guī)劃問題為線性規(guī)劃的規(guī)范形式（canonical form）：minzctxs.t.axb x0m

19、axzctx s.t.axbx0 irwin/mcgraw-hill the mcgraw-hill companies, inc., 19992.1 線性規(guī)劃問題與標準形式線性規(guī)劃問題與標準形式 而稱以下的形式為標準形式（standard form）： max zctxs.t.axb x0 對于各種非標準形式的線性規(guī)劃問題，我們總可以通過以下的變換，將其轉(zhuǎn)化為標準形式。1 極小化目標函數(shù)的問題2 約束條件不是等式的問題3 變量無符號限制的問題irwin/mcgraw-hill the mcgraw-hill companies, inc., 19991 極小化目標函數(shù)的問題極小化目標函數(shù)的問

20、題設目標函數(shù)為nnxcxcxcz2211min令zz，則以上極大化問題和極小化問題有相同的最優(yōu)解，即nnxcxcxcz2211 max但必須注意，盡管以上兩個問題的最優(yōu)解相同，但他們最優(yōu)解的目標函數(shù)值卻相差一個符號，即minzmax z irwin/mcgraw-hill the mcgraw-hill companies, inc., 19992 約束條件不是等式的問題約束條件不是等式的問題設約束條件為 ( i=1,2,m)可以引進一個新的變量xn+i，使它等于約束右邊與左邊之差顯然xn+i也具有非負約束，即xn+i0，這時新的約束條件成為當約束條件為bxaxaxaninii2211xbax

21、axaxniiiiinn()1122iinniniibxxaxaxa2211axaxaxbiiinni1122irwin/mcgraw-hill the mcgraw-hill companies, inc., 1999 2 約束條件不是等式的問題約束條件不是等式的問題時，類似地令則同樣有xn+i0，新的約束條件成為ininiiinbxaxaxax)(2211 為了使約束由不等式成為等式而引進的變量xn+i稱為“松弛變量”。如果原問題中有若干個非等式約束，則將其轉(zhuǎn)化為標準形式時，必須對各個約束引進不同的松弛變量。xa xa xa xbn iiiinni()1122a xaxa xxbiiinn

22、n ii1122irwin/mcgraw-hill the mcgraw-hill companies, inc., 19993 變量無符號限制的問題變量無符號限制的問題 在標準形式中，每一個變量都有非負約束。當一個變量xj沒有非負約束時，可以令xj=xj-xj” 其中xj0，xj”0 即用兩個非負變量之差來表示一個無符號限制的變量，當xj的符號取決于xj和xj”的大小。irwin/mcgraw-hill the mcgraw-hill companies, inc., 19992.2 線性規(guī)劃問題的幾何解釋線性規(guī)劃問題的幾何解釋對于只有兩個變量的線性規(guī)劃問題，可以在二維直角坐標平面上表示線性

23、規(guī)劃問題。max z= x1+3x2s.t x1+x26 -x1+2x28 x1, x2 0例1.4.1的線性規(guī)劃問題的可行域如圖1.4.1中陰影部分所示。irwin/mcgraw-hill the mcgraw-hill companies, inc., 19992.2 線性規(guī)劃問題的幾何解釋線性規(guī)劃問題的幾何解釋123456xz=0z=3z=6z=9z=12z=15.3013456約 束 條 件 （ 1）約 束 條 件 （ 2）c-1-8-2-3-4-5-6-7x21irwin/mcgraw-hill the mcgraw-hill companies, inc., 19992.2 線性規(guī)

24、劃問題的幾何解釋線性規(guī)劃問題的幾何解釋在以上問題中，目標函數(shù)等值線在平行移動過程中與可行域的最后一個交點是b點，這就是線性規(guī)劃問題的最優(yōu)解，這個最優(yōu)解可以由兩直線x1+x2=6-x1+2x2=8的交點求得xx12431 43, 最優(yōu)解的目標函數(shù)值為 346314334321xxzirwin/mcgraw-hill the mcgraw-hill companies, inc., 19992.2 線性規(guī)劃問題的幾何解釋線性規(guī)劃問題的幾何解釋定義定義1.4.3 設s是n維空間中的一個點集。若對任意n維向量x1s，x2s，且x1x2，以及任意實數(shù)（01），有x=x1+(1-)x2s則稱s為n維空間中

25、的一個凸集。點x稱為點x1和x2的凸組合。以上定義有明顯的幾何意義，它表示凸集s中的任意兩個不相同的點連線上的點（包括這兩個端點），都位于凸集s之中。圖1.4.2表示二維平面中一些凸集和非凸集的例子。irwin/mcgraw-hill the mcgraw-hill companies, inc., 19992.2 線性規(guī)劃問題的幾何解釋線性規(guī)劃問題的幾何解釋xxxxxx121212xxxxxx121212(a)凸集 (b)凸集 (c)凸集 (d)非凸集 (e)非凸集(d)非凸集 (f)非凸集 irwin/mcgraw-hill the mcgraw-hill companies, inc.,

26、 19992.2 線性規(guī)劃問題的幾何解釋線性規(guī)劃問題的幾何解釋定義定義1.4.4 設s為一凸集，且xs，x1s，x2s。對于01，若x x=x1+(1-)x x2則必定有x=x x1=x x2，則稱x為s的一個極點。運用以上的定義，線性規(guī)劃的可行域以及最優(yōu)解有以下性質(zhì)：1、若線性規(guī)劃的可行域非空，則可行域必定為一凸集。2、若線性規(guī)劃有最優(yōu)解，則最優(yōu)解至少位于一個極點上。這樣，求線性規(guī)劃最優(yōu)解的問題，從在可行域內(nèi)無限個可行解中搜索的問題轉(zhuǎn)化為在其可行域的有限個極點上搜索的問題。最后，來討論線性規(guī)劃的可行域和最優(yōu)解的幾種可能的情況。1、可行域為封閉的有界區(qū)域2、可行域為非封閉的無界區(qū)域可行域為非封

27、閉的無界區(qū)域irwin/mcgraw-hill the mcgraw-hill companies, inc., 19992.2 線性規(guī)劃問題的幾何解釋線性規(guī)劃問題的幾何解釋3、可行域為空集，因而沒有可行解。以上幾種情況的圖示如下：(a)可行域有界 (b)可行域有界 (c)可行域無界 唯一最優(yōu)解 唯一最優(yōu)解 唯一最優(yōu)解 irwin/mcgraw-hill the mcgraw-hill companies, inc., 19992.2 線性規(guī)劃問題的幾何解釋線性規(guī)劃問題的幾何解釋(d)可行域無界 (e)可行域無界 (f)可行域為空集 多個最優(yōu)解 目標函數(shù)無界 無可行解 圖1.4.3線性規(guī)劃可行

28、域和最優(yōu)解的幾種情況 irwin/mcgraw-hill the mcgraw-hill companies, inc., 19992.3 單純形法方法單純形法方法 設線性規(guī)劃的約束條件為ax=bx0其中a為mn的矩陣，nm，秩a=m，b為m1向量。定義定義2.6 線性規(guī)劃的基(basis) 設b是a矩陣中的一個非奇異的mm子矩陣，則稱b為線性規(guī)劃的一個基(矩陣).定義定義2.72.7設b是線性規(guī)劃的一個基（矩陣），線性規(guī)劃的解:稱為線性規(guī)劃與基b b對應的基礎解。若其中b b-1b b0 0，則稱以上的基礎解為一基礎可行解，相應的基b b稱為可行基。定理定理2.1 線性規(guī)劃的基礎可行解就是可

29、行域的極點。線性規(guī)劃的基礎可行解就是可行域的極點。 0bbxxx1nbirwin/mcgraw-hill the mcgraw-hill companies, inc., 19992.3 單純形法方法單純形法方法1 單純形原理的矩陣描述單純形原理的矩陣描述 2 單純形表單純形表 3 初始基礎可行解初始基礎可行解 4 退化和循環(huán)退化和循環(huán) irwin/mcgraw-hill the mcgraw-hill companies, inc., 19991 單純形原理的矩陣描述單純形原理的矩陣描述設標準的線性規(guī)劃問題為max z=ctxs.t.ax=b(1.6.1)x0并設a=a1，a2，an其中a

30、j(j=1，2，n)是a矩陣的第j個列向量。b=a1，a2，am是a的一個基。irwin/mcgraw-hill the mcgraw-hill companies, inc., 19991 單純形原理的矩陣描述單純形原理的矩陣描述這樣，矩陣a可以分塊記為a=b，n，相應地，向量x和c可以記為 并設r為非基變量的下標集合。利用以上的記號，（1.6.1）中的等式約束ax=b可以寫成bxb+nxn=b即xb=b-1b-b-1nxn(1.6.2)這就是在約束條件中，基變量用非基變量表出的形式。 xxxcccbnbn,irwin/mcgraw-hill the mcgraw-hill companie

31、s, inc., 19991 單純形原理的矩陣描述單純形原理的矩陣描述對于一個確定的基b，目標函數(shù)z可以寫成 ztbtntbnbtbntncx ccxxcxc x,.將(1.6.2)式代入以上目標函數(shù)表達式，得到目標函數(shù)z用非基變量表出的形式 zbtnntnbtbtntncbbbnxc xc bbc bncx()()1111irwin/mcgraw-hill the mcgraw-hill companies, inc., 19991 單純形原理的矩陣描述單純形原理的矩陣描述(1.6.2)和(1.6.3)式表示，非基變量的任何一組確定的值，基變量和目標函數(shù)都有一組確定的值與之對應。特別，當xn

32、=0時，相應的解 xxxbb0bn1就是對應于基b的基礎解。如果b是一個可行基，則有 xxxbb00bn1irwin/mcgraw-hill the mcgraw-hill companies, inc., 19991 單純形原理的矩陣描述單純形原理的矩陣描述下面我們來詳細說明如何實現(xiàn)以上步驟。步驟1、獲得初始基礎可行解的一般化的方法將在下一節(jié)中敘述。在這里，我們假定已經(jīng)獲得了一個初始的可行基b，基b對應的基礎解為 xxxbb0bn1當前的目標函數(shù)值為zbtbbt01c xc b birwin/mcgraw-hill the mcgraw-hill companies, inc., 19991

33、 單純形原理的矩陣描述單純形原理的矩陣描述步驟2、確定進基的非基變量xk由(1.6.1)可知，當前目標函數(shù)值用非基變量用非基變量表出的形式是 zzcxbtbtntnbtjjjj rc b bc b ncxc b a1101()()令c b abtjjz1irwin/mcgraw-hill the mcgraw-hill companies, inc., 19991 單純形原理的矩陣描述單純形原理的矩陣描述則 rjjjjxczzz)(0如果對于所有jr，有zj-cj0，則任何非基變量xj的值由0開始增加都不會使z減少，因此當前基b已是最優(yōu)基，相應的基礎可行解xxxb b0bn1如果有kr，使zk

34、-ck0，則非基變量xk的增加將會使目標函數(shù)值減少。為了使目標函數(shù)值下降得快一些，一般選取滿足 irwin/mcgraw-hill the mcgraw-hill companies, inc., 19991 單純形原理的矩陣描述單純形原理的矩陣描述 zczc zckkj rjjjjmax|0的非基變量xk為進基變量。由于除xk以外的非基變量的值均保持為0不變，這時目標函數(shù)可以表示為 zzzcxzzcxjjjj rkkk00()()步驟3、確定基變量中離基的變量xbr在(1.6.2)中，令irwin/mcgraw-hill the mcgraw-hill companies, inc., 19

35、991 單純形原理的矩陣描述單純形原理的矩陣描述 bb byba1111bbbyyyrmjjjrjmj則(1.6.2)可以表示為 xbba xbybjjj rjjj rx1當進基變量xk的值由0增加到某一正值，其余非基變量均保持為0時，上式成為 irwin/mcgraw-hill the mcgraw-hill companies, inc., 19991 單純形原理的矩陣描述單純形原理的矩陣描述xbybkkx即 xxxbbbyyyxbbrbmrmrkmkk111kirwin/mcgraw-hill the mcgraw-hill companies, inc., 19991 單純形原理的矩陣

36、描述單純形原理的矩陣描述在(1.6.6)中，有以下幾種情形：（1）如果向量yk中所有的分量yik0，則xk的增加將不會使任何xbi(i=1，2，.，m)減少，這時xk可無限增加，同時所有的基變量仍保持非負。同時由于xk在目標函數(shù)中的系數(shù)zk-ck0，由(1.6.5)可知當xk增加時目標函數(shù)將無限減少，即目標函數(shù)無界。（2）如果向量yk中至少有一個分量yik0，則xk由0開始增加將會使相應的基變量xbi的值由當前的值bi開始減少。當xk增加到 min|10 i miikikrrkbyybyirwin/mcgraw-hill the mcgraw-hill companies, inc., 199

37、91 單純形原理的矩陣描述單純形原理的矩陣描述相應的基變量xbr=0，而其余的基變量xbi0（i=1，2，.，m，ir），這時基變量xbr離基，它在基b中相應的列向量abr將換出基矩陣，進基變量xk在a矩陣中相應的列向量ak將取代基矩陣b中abr的位置，得到新的可行基 b=ab1，ab2，abr-1，ak，abr+1，abm新的基b相應的基變量的值為 xbbbrbmkkmmkkrrkrrkmmkrrkxxxbyxxbyxbybybybyby111k11kirwin/mcgraw-hill the mcgraw-hill companies, inc., 19991 單純形原理的矩陣描述單純形原

38、理的矩陣描述b相應的非基變量的值為xn=0b對應的目標函數(shù)值為步驟4、由新的基b重新確定非基變量集合r，并重新計算(1.6.4)以判定b是否為最優(yōu)基。若不是，計算(1.6.4)(1.6.8)以實現(xiàn)進一步的基變換。 zzzcxzzcbykkkkkrrk00()()irwin/mcgraw-hill the mcgraw-hill companies, inc., 19992 單純形表單純形表 單純形算法的實質(zhì)是將非基變量視為一組參數(shù)，并將目標函數(shù)和基變量都表示成為由非基變量表示的形式。即（1.6.2）和（1.6.3）兩式。這樣就可以討論當非基變量變化時，目標函數(shù)和基變量隨之變化的情況。我們可以用

39、一個矩陣來表示單純形法迭代中所需要的全部信息，這就是所謂的單純形表。設線性規(guī)劃問題為max z=ctxs.t. ax=b(1.7.1)x0并設b是a的一個可行基，并記a=b b，n，相應地將目標函數(shù)系數(shù)向量c以及變量x表示為 irwin/mcgraw-hill the mcgraw-hill companies, inc., 19992 單純形表單純形表 cccxxxbnbn,則(1.7.1)可表為0xxbxxnbxxccnbnbnbtntbtsz,. .max即 irwin/mcgraw-hill the mcgraw-hill companies, inc., 19992 單純形表單純形表

40、 zbtbntnbnbnc xc xbxnxbxx00,將(1.7.3)的系數(shù)寫成矩陣形式，有zxbxnrhs10-cbt-cnt0bnbirwin/mcgraw-hill the mcgraw-hill companies, inc., 19992 單純形表單純形表稱以上矩陣為線性規(guī)劃問題的系數(shù)矩陣（并不是單純形表）。為了將約束中的基變量用非基變量表出，用b-1左乘以上系數(shù)矩陣的后m行，得到 zxbxnrhs1-cbt0-cnt0ib-1nb-1b為了將第一行中的目標函數(shù)z用非基變量xn表出，在矩陣的后m行左乘cbt后加到第一行上，消去基變量在目標函數(shù)中的系數(shù)，得到irwin/mcgraw-hill the mcgraw-hill companies, inc., 19992 單純形表單純形表zxbxnrhs10tcbtb-1bcbtb-1n-cnt0ib-1nb-1b以上矩陣的第一行與(1.6.3)完全等價，后m行與(1.6.2)完全等價。這一矩陣稱為與基b對應的單純形表。單純形表可以由系數(shù)矩陣經(jīng)過一系列行變換得到，這些行變換使