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

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

2、信息如下表，表中還列出了派公司在本輪生產(chǎn)過程中每個(gè)部門的最大生產(chǎn)時(shí)間。irwin/mcgraw-hill the mcgraw-hill companies, inc., 1999問題的提出（問題的提出（2）會(huì)計(jì)部門的數(shù)據(jù)表明，生產(chǎn)一個(gè)標(biāo)準(zhǔn)袋的利潤(rùn)是10美元，生產(chǎn)一個(gè)高級(jí)袋的利潤(rùn)是9美元。如何安排兩種產(chǎn)品的生產(chǎn)才能使公司獲得最大利潤(rùn)？耗時(shí)/標(biāo)準(zhǔn)袋耗時(shí)/高檔袋最大生產(chǎn)時(shí)間切割印染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）設(shè)x1、x2分別為兩種高爾夫袋的生產(chǎn)量，則該計(jì)劃問題可用如下數(shù)學(xué)模型表示為：0,13525. 01 . 07083/26006/55 . 06307 . 0. .910max212121212121xxxxxxxxxxtsxxsirwin/mcgraw-hill the mcgraw-hill companies, inc., 19992.1 線性規(guī)劃問題與標(biāo)準(zhǔn)形式線性規(guī)劃問題與標(biāo)準(zhǔn)形式 典例典例1-生產(chǎn)計(jì)劃問題生產(chǎn)計(jì)劃問題例例2. 某工廠在計(jì)劃期內(nèi)要生產(chǎn)產(chǎn)品i和產(chǎn)品ii這兩種產(chǎn)品，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺(tái)時(shí)及a、b兩種

4、設(shè)備計(jì)劃期的有效臺(tái)時(shí)，如下表：?jiǎn)柸绾伟才派a(chǎn)最有利？ 產(chǎn)品 i 產(chǎn)品 ii 設(shè)備有效臺(tái)時(shí) 設(shè)備 a 2 2 8 設(shè)備 b 0 2 4 單位產(chǎn)品利潤(rùn) 1 元 2 元 解 設(shè)產(chǎn)品i和產(chǎn)品ii的產(chǎn)量分別為x1和x2件, 利潤(rùn)為z, 則: z = x1 + 2 x2max目標(biāo)函數(shù) 2 x1 + 2 x2 8 0 x1 + 2 x2 4 x1 , x2 0約束條件s.t.非負(fù)條件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目標(biāo)函數(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)成份大米白菜雞蛋豬肉營(yíng)養(yǎng)成份的需要量(周)蛋 白 質(zhì)a11a12a13a14b1某維生素a21a22a23a24b2某礦物質(zhì)a31a32a33a34b3單 價(jià)(元)c1c2c3c4問在滿足營(yíng)養(yǎng)的條件下,如何安排食譜最有利?解:設(shè)每人每周食用大米、白菜、雞蛋、豬肉的數(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)養(yǎng)成份大米白菜雞蛋豬肉食品n營(yíng)養(yǎng)成份的需要量(周)蛋 白 質(zhì)a11a12a13a14a1nb1某維生素a21a22a23a24a2nb2某礦物質(zhì)a31a32a33a34a3nb3營(yíng)養(yǎng)成份 mam1am2am3am4amnbn單 價(jià)(元)c1c2c3c4cn問在滿足營(yíng)養(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ù)學(xué)模型irwin/mcgraw-hill the mcgraw-hill companies, inc., 1999new bedford steel煉焦煤供應(yīng)問題 ashleybedfordconsoldunbyearlamf

9、lorencegastonhopt 供應(yīng)量 (千噸/年） 300 600 510 655 575 680 450490工會(huì)（u）/非工會(huì)（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 價(jià)格 (/ 噸） 49.50 50.00 61.00 63.50 66.50 71.00 72.5080.00new bedford steel (nbs)是一家小型的煉鋼企業(yè)。煉焦煤是一家小型的煉鋼企業(yè)。煉焦煤(coking coal)是是nbs公司煉鋼時(shí)所必需的一種原材料，每年的需求量是公司煉鋼時(shí)所必

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

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

12、5工會(huì)煤礦的約束：a + b c + d e + f g h 0卡車運(yùn)輸量約束：b + d + e + f 720火車運(yùn)輸量約束：a + c + g + h 650平均可燃率約束：可改寫成： 4a 3b c + d + 2e + 3f + 4g + 6h 0各煤礦的煉焦煤供應(yīng)量約束：a 300，b 600，c 510，d 655，e 575，f 680，g 450， h 490非負(fù)約束：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īng)問題的線性最優(yōu)化模型的煉焦煤供應(yīng)問題的線性最優(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īng)問題的線性最優(yōu)化模型的煉焦煤供應(yīng)問題的線性最優(yōu)化模型求解，得：a= 55千噸， b=600千噸， c= 0千噸， d= 20千噸， e=100千噸， f= 0千噸， g=450千噸， h= 0千噸；最小成本 = 73,267.50千美元；平均供應(yīng)成本 = 7

15、3,267.50 / 1,225 = 59.81美元/噸irwin/mcgraw-hill the mcgraw-hill companies, inc., 1999二、線性規(guī)劃數(shù)學(xué)模型的幾種表達(dá)形式二、線性規(guī)劃數(shù)學(xué)模型的幾種表達(dá)形式一般形式一般形式目標(biāo)函數(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簡(jiǎn)寫形式形式目標(biāo)函數(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 ) 價(jià)值向量,二、線性規(guī)劃數(shù)學(xué)模型的幾種表達(dá)形式二、線性規(guī)劃數(shù)學(xué)模型的幾種表達(dá)形式12mbbbb限定向量12jjjmjaapa變量xj對(duì)應(yīng)的系數(shù)列向量12nxxxx1(min)(,)0njjjm axzcxp xbx irwin/mcgraw-hill

17、the mcgraw-hill companies, inc., 1999二、線性規(guī)劃數(shù)學(xué)模型的幾種表達(dá)形式二、線性規(guī)劃數(shù)學(xué)模型的幾種表達(dá)形式矩陣形式111212122212nnmmmnaaaaaaaaaa約束條件系數(shù)矩陣max(min)( , )0zcxaxbx irwin/mcgraw-hill the mcgraw-hill companies, inc., 1999第二節(jié)第二節(jié) 線性規(guī)劃問題的標(biāo)準(zhǔn)形式線性規(guī)劃問題的標(biāo)準(zhǔn)形式一、標(biāo)準(zhǔn)形式標(biāo)準(zhǔn)形式目標(biāo)函數(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í)滿足如下四個(gè)條件:目標(biāo)函數(shù)求極大約束條件全為等式約束條件右端常數(shù)項(xiàng)全為非負(fù)變量取值全為非負(fù)irwin/mcgraw-hill the mcgraw-hill companies, inc., 19992.1 線性規(guī)劃問題與標(biāo)準(zhǔn)形式線性規(guī)劃問題與標(biāo)準(zhǔn)形式 為了今后討論的方便，我們稱以下兩種形式的線性規(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ī)劃問題與標(biāo)準(zhǔn)形式線性規(guī)劃問題與標(biāo)準(zhǔn)形式 而稱以下的形式為標(biāo)準(zhǔn)形式（standard form）： max zctxs.t.axb x0 對(duì)于各種非標(biāo)準(zhǔn)形式的線性規(guī)劃問題，我們總可以通過以下的變換，將其轉(zhuǎn)化為標(biāo)準(zhǔn)形式。1 極小化目標(biāo)函數(shù)的問題2 約束條件不是等式的問題3 變量無符號(hào)限制的問題irwin/mcgraw-hill the mcgraw-hill companies, inc., 19991 極小化目標(biāo)函數(shù)的問題極小化目標(biāo)函數(shù)的問

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

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

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

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

25、的一個(gè)凸集。點(diǎn)x稱為點(diǎn)x1和x2的凸組合。以上定義有明顯的幾何意義，它表示凸集s中的任意兩個(gè)不相同的點(diǎn)連線上的點(diǎn)（包括這兩個(gè)端點(diǎn)），都位于凸集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 設(shè)s為一凸集，且xs，x1s，x2s。對(duì)于01，若x x=x1+(1-)x x2則必定有x=x x1=x x2，則稱x為s的一個(gè)極點(diǎn)。運(yùn)用以上的定義，線性規(guī)劃的可行域以及最優(yōu)解有以下性質(zhì)：1、若線性規(guī)劃的可行域非空，則可行域必定為一凸集。2、若線性規(guī)劃有最優(yōu)解，則最優(yōu)解至少位于一個(gè)極點(diǎn)上。這樣，求線性規(guī)劃最優(yōu)解的問題，從在可行域內(nèi)無限個(gè)可行解中搜索的問題轉(zhuǎn)化為在其可行域的有限個(gè)極點(diǎn)上搜索的問題。最后，來討論線性規(guī)劃的可行域和最優(yōu)解的幾種可能的情況。1、可行域?yàn)榉忾]的有界區(qū)域2、可行域?yàn)榉欠忾]的無界區(qū)域可行域?yàn)榉欠?/p>

27、閉的無界區(qū)域irwin/mcgraw-hill the mcgraw-hill companies, inc., 19992.2 線性規(guī)劃問題的幾何解釋線性規(guī)劃問題的幾何解釋3、可行域?yàn)榭占蚨鴽]有可行解。以上幾種情況的圖示如下：(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àn)榭占?多個(gè)最優(yōu)解 目標(biāo)函數(shù)無界 無可行解 圖1.4.3線性規(guī)劃可行

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

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

30、j(j=1，2，n)是a矩陣的第j個(gè)列向量。b=a1，a2，am是a的一個(gè)基。irwin/mcgraw-hill the mcgraw-hill companies, inc., 19991 單純形原理的矩陣描述單純形原理的矩陣描述這樣，矩陣a可以分塊記為a=b，n，相應(yīng)地，向量x和c可以記為 并設(shè)r為非基變量的下標(biāo)集合。利用以上的記號(hào)，（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 單純形原理的矩陣描述單純形原理的矩陣描述對(duì)于一個(gè)確定的基b，目標(biāo)函數(shù)z可以寫成 ztbtntbnbtbntncx ccxxcxc x,.將(1.6.2)式代入以上目標(biāo)函數(shù)表達(dá)式，得到目標(biāo)函數(shù)z用非基變量表出的形式 zbtnntnbtbtntncbbbnxc xc bbc bncx()()1111irwin/mcgraw-hill the mcgraw-hill companies, inc., 19991 單純形原理的矩陣描述單純形原理的矩陣描述(1.6.2)和(1.6.3)式表示，非基變量的任何一組確定的值，基變量和目標(biāo)函數(shù)都有一組確定的值與之對(duì)應(yīng)。特別，當(dāng)xn

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

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

34、-ck0，則非基變量xk的增加將會(huì)使目標(biāo)函數(shù)值減少。為了使目標(biāo)函數(shù)值下降得快一些，一般選取滿足 irwin/mcgraw-hill the mcgraw-hill companies, inc., 19991 單純形原理的矩陣描述單純形原理的矩陣描述 zczc zckkj rjjjjmax|0的非基變量xk為進(jìn)基變量。由于除xk以外的非基變量的值均保持為0不變，這時(shí)目標(biāo)函數(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當(dāng)進(jìn)基變量xk的值由0增加到某一正值，其余非基變量均保持為0時(shí)，上式成為 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的增加將不會(huì)使任何xbi(i=1，2，.，m)減少，這時(shí)xk可無限增加，同時(shí)所有的基變量仍保持非負(fù)。同時(shí)由于xk在目標(biāo)函數(shù)中的系數(shù)zk-ck0，由(1.6.5)可知當(dāng)xk增加時(shí)目標(biāo)函數(shù)將無限減少，即目標(biāo)函數(shù)無界。（2）如果向量yk中至少有一個(gè)分量yik0，則xk由0開始增加將會(huì)使相應(yīng)的基變量xbi的值由當(dāng)前的值bi開始減少。當(dāng)xk增加到 min|10 i miikikrrkbyybyirwin/mcgraw-hill the mcgraw-hill companies, inc., 199

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

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

39、一個(gè)矩陣來表示單純形法迭代中所需要的全部信息，這就是所謂的單純形表。設(shè)線性規(guī)劃問題為max z=ctxs.t. ax=b(1.7.1)x0并設(shè)b是a的一個(gè)可行基，并記a=b b，n，相應(yīng)地將目標(biāo)函數(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為了將第一行中的目標(biāo)函數(shù)z用非基變量xn表出，在矩陣的后m行左乘cbt后加到第一行上，消去基變量在目標(biāo)函數(shù)中的系數(shù)，得到irwin/mcgraw-hill the mcgraw-hill companies, inc., 19992 單純形表單純形表zxbxnrhs10tcbtb-1bcbtb-1n-cnt0ib-1nb-1b以上矩陣的第一行與(1.6.3)完全等價(jià)，后m行與(1.6.2)完全等價(jià)。這一矩陣稱為與基b對(duì)應(yīng)的單純形表。單純形表可以由系數(shù)矩陣經(jīng)過一系列行變換得到，這些行變換使