《運(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分析：初始表迭代后任一表初等行變換初等行變換左乘一個適當(dāng)矩陣SS＝？編輯pptA、X、C可根據(jù)基B分塊

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

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

zj0C0對比初始表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...迭代后單純形表檢驗數(shù)σj編輯ppt例已知初始表和最優(yōu)表如下，請將表中空白處數(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是對偶問題的可行解，目標(biāo)值w=Yb=CBB-1b=maxz◆Y是一般型意義下對偶問題可行解，僅由決策變量取值組成（m維）編輯ppt結(jié)論：當(dāng)采用單純形法求得原問題的一個最優(yōu)解的時候，檢驗行上同時得到對偶問題的一個可行解，且兩者具有相同的目標(biāo)值。利用對偶性質(zhì)，可以證明這個對偶問題的解也為最優(yōu)解。編輯ppt例、以求解下面LP問題以及它的對偶問題過程為例，驗證前述結(jié)論對偶問題原問題編輯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對偶問題最優(yōu)表原問題最優(yōu)表對偶問題最優(yōu)解Y=（y1,y2,y3）=(0,1/4,1/2)松弛變量決策變量剩余變量決策變量原問題最優(yōu)解X=(x1,x2)T=(7/2,3/2)T編輯ppt兩個問題作一比較:1.兩者的最優(yōu)值相同2.從任一個問題的最優(yōu)表，可以直接找到另一個問題的最優(yōu)解，對應(yīng)關(guān)系原問題決策變量原問題松弛變量對偶問題剩余變量對偶問題決策變量編輯ppt例2、用單純形表求解LP問題所得最優(yōu)表如下，試直