《運(yùn)籌學(xué)》胡運(yùn)權(quán)清華版-2-02單純形算法的矩陣表

單純形法的矩陣描述編輯pptC0基系數(shù)基列常數(shù)列XXS0XSbAIcj-

zjC0初始單純形表線性規(guī)劃問題：標(biāo)準(zhǔn)型：一、初始單純形表編輯ppt二、迭代后的單純形表（當(dāng)前可行基——B）

基列常數(shù)列XXSXB？？？cj-

zj？？？則表結(jié)構(gòu)編輯ppt分析：初始表迭代后任一表初等行變換初等行變換左乘一個(gè)適當(dāng)矩陣SS＝？編輯pptA、X、C可根據(jù)基B分塊

現(xiàn)求基B所對(duì)應(yīng)的基可行解與目標(biāo)值：左乘B-1令非基變量XN，XS＝0基解目標(biāo)值編輯ppt基列常數(shù)列XXSXBB-1b？？cj-

zj-CBB-1b？？迭代后表基列常數(shù)列XXSXSbAIcj-

zj0C0對(duì)比初始表B-1AB-1C-CBB-1A-CBB-1B-1×第1行-CBB-1×第1行＋第2行編輯ppt三、其他形式的初始表與迭代后單純形表基列常數(shù)列XBXNXSXSbBNIcj-

zj0CBCN0基列常數(shù)列XBXNXSXBB-1bIB-1NB-1cj-

zj-CBB-1b0CN-CBB-1N-CBB-1單純形乘子編輯ppt初始表基列常數(shù)列x1...xj...xnXSXSbP1

...Pj...PnIcj-

0基列常數(shù)列x1...xj...xnXS

XBB-1bB-1P1

...B-1Pj

...B-1Pn

B-1

cj-

zj-CBB-1b

...cj-CBB-1Pj...迭代后單純形表檢驗(yàn)數(shù)σj編輯ppt例已知初始表和最優(yōu)表如下，請(qǐng)將表中空白處數(shù)字填上。cj2-11000CBXBbx1x2x3x4x5x60x4603111000x5101-120100x62011-1001cj-zj2-110000x41-1-22x101/21/2-1x20-1/21/2cj-zj.............................................................編輯ppt解：cj2-11000CBXBbx1x2x3x4x5x60x4603111000x5101-120100x62011-1001cj-zj2-110000x41-1-22x101/21/2-1x20-1/21/2cj-zj.............................................................B-1B=（P4，P1，P2）編輯ppt解：cj2-11000CBXBbx1x2x3x4x5x60x4603111000x5101-120100x62011-1001cj-zj2-110000x41-1-22x101/21/2-1x20-1/21/2cj-zj.............................................................B-1B-1b?10155編輯ppt解：cj2-11000CBXBbx1x2x3x4x5x60x4603111000x5101-120100x62011-1001cj-zj2-110000x4101-1-22x11501/21/2-1x250-1/21/2cj-zj.............................................................B-1B-1P3?11/2-3/2010001編輯ppt解：cj2-11000CBXBbx1x2x3x4x5x60x4603111000x5101-120100x62011-1001cj-zj2-110000x4100011-1-22x115101/201/21/2-1x2501-3/20-1/21/2cj-zj00-3/20-3/2-1/2.............................................................編輯ppt四、最優(yōu)表基列常數(shù)列XXSXBB-1bB-1AB-1cj-

zj-CBB-1bC-CBB-1A

-CBB-1若B是最優(yōu)基，則下表是最優(yōu)表根據(jù)最優(yōu)性判定定理即：記Y=CBB-1YYY是對(duì)偶問題的可行解，目標(biāo)值w=Yb=CBB-1b=maxz◆Y是一般型意義下對(duì)偶問題可行解，僅由決策變量取值組成（m維）編輯ppt結(jié)論：當(dāng)采用單純形法求得原問題的一個(gè)最優(yōu)解的時(shí)候，檢驗(yàn)行上同時(shí)得到對(duì)偶問題的一個(gè)可行解，且兩者具有相同的目標(biāo)值。利用對(duì)偶性質(zhì)，可以證明這個(gè)對(duì)偶問題的解也為最優(yōu)解。編輯ppt例、以求解下面LP問題以及它的對(duì)偶問題過程為例，驗(yàn)證前述結(jié)論對(duì)偶問題原問題編輯ppt

21000

01505100

0

24620100511001

21000表1：初始表B-1原問題編輯ppt

21000

01505100

2

412/601/600104/60-1/61

01/30-1/30表2：迭代中B-1原問題編輯ppt

21000

015/20015/4-15/2

2

7/21001/4-1/213/2010-1/43/2000-1/4-1/2表3：最優(yōu)表B-1原問題編輯ppt基列常數(shù)列1/41/2-5/410-1/41/415/2011/2-3/2cj-zj-15/200-7/2-3/2

基列常數(shù)列15/27/23/20015/4-15/21001/4-1/2010-1/43/2cj-zj000-1/4-1/2對(duì)偶問題最優(yōu)表原問題最優(yōu)表對(duì)偶問題最優(yōu)解Y=（y1,y2,y3）=(0,1/4,1/2)松弛變量決策變量剩余變量決策變量原問題最優(yōu)解X=(x1,x2)T=(7/2,3/2)T編輯ppt兩個(gè)問題作一比較:1.兩者的最優(yōu)值相同2.從任一個(gè)問題的最優(yōu)表，可以直接找到另一個(gè)問題的最優(yōu)解，對(duì)應(yīng)關(guān)系原問題決策變量原問題松弛變量對(duì)偶問題剩余變量對(duì)偶問題決策變量編輯ppt例2、用單純形表求解LP問題所得最優(yōu)表如下，試直