單純形法的計(jì)算步驟

1、Page 1例例1.8 用單純形法求下列線性規(guī)劃的最優(yōu)解用單純形法求下列線性規(guī)劃的最優(yōu)解 0,30340243max21212121xxxxxxxxZ解：解：1）將問(wèn)題化為標(biāo)準(zhǔn)型，加入松馳變量將問(wèn)題化為標(biāo)準(zhǔn)型，加入松馳變量x3、x4則標(biāo)準(zhǔn)型為則標(biāo)準(zhǔn)型為: 0,30340243max432142132121xxxxxxxxxxxxZPage 22）求出線性規(guī)劃的初始基可行解，列出初始單純形表。）求出線性規(guī)劃的初始基可行解，列出初始單純形表。cj3400icB基基bx1x2x3x40 x34021100 x430130134003)1020(3)(2141131 acacc1 檢驗(yàn)數(shù)檢驗(yàn)數(shù)j Pa

2、ge 33）進(jìn)行最優(yōu)性檢驗(yàn)）進(jìn)行最優(yōu)性檢驗(yàn)如果表中所有檢驗(yàn)數(shù)如果表中所有檢驗(yàn)數(shù) ，則表中的基可行解就是問(wèn)題的最優(yōu)解，計(jì)算停，則表中的基可行解就是問(wèn)題的最優(yōu)解，計(jì)算停止。否則繼續(xù)下一步。止。否則繼續(xù)下一步。0 j4）從一個(gè)基可行解轉(zhuǎn)換到另一個(gè)目標(biāo)值更大的基可行解，）從一個(gè)基可行解轉(zhuǎn)換到另一個(gè)目標(biāo)值更大的基可行解，列出新的單純形表列出新的單純形表確定換入基的變量。選擇確定換入基的變量。選擇 ，對(duì)應(yīng)的變量，對(duì)應(yīng)的變量xj作為換入作為換入變量，當(dāng)有一個(gè)以上檢驗(yàn)數(shù)大于變量，當(dāng)有一個(gè)以上檢驗(yàn)數(shù)大于0時(shí)，一般選擇最大的一時(shí)，一般選擇最大的一個(gè)檢驗(yàn)數(shù)，即：個(gè)檢驗(yàn)數(shù)，即： ，其對(duì)應(yīng)的，其對(duì)應(yīng)的xk作為作為換入變

3、量。換入變量。確定換出變量。根據(jù)下式計(jì)算并選擇確定換出變量。根據(jù)下式計(jì)算并選擇 ，選最小的選最小的對(duì)應(yīng)基對(duì)應(yīng)基變量作為換出變量。變量作為換出變量。0 j0|max jjk 0minikikiLaabPage 4用換入變量用換入變量xk替換基變量中的換出變量，得到一個(gè)新的基。替換基變量中的換出變量，得到一個(gè)新的基。對(duì)應(yīng)新的基可以找出一個(gè)新的基可行解，并相應(yīng)地可以畫出對(duì)應(yīng)新的基可以找出一個(gè)新的基可行解，并相應(yīng)地可以畫出一個(gè)新的單純形表。一個(gè)新的單純形表。5）重復(fù)）重復(fù)3）、）、4）步直到計(jì)算結(jié)束為止。）步直到計(jì)算結(jié)束為止。Page 5cj3400icB基變量基變量bx1x2x3x40 x34021

4、100 x430130134000 x34x23x14x2j j j 換入列換入列bi /ai2，ai204010換換出出行行將將3化為化為15/311801/301/31011/3303005/304/3乘乘以以1/3后后得得到到103/51/518011/52/540011Page 6例例1.10 用大用大M法解下列線性規(guī)劃法解下列線性規(guī)劃 012210243423max321321321321321xxxxxxxxxxxxxxxZ、解：首先將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式解：首先將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式 5 , 2 , 1, 012210243423max32153214321321jxxxxxxx

5、xxxxxxxxZj系數(shù)矩陣中不存在單位矩系數(shù)矩陣中不存在單位矩陣，無(wú)法建立初始單純形陣，無(wú)法建立初始單純形表。表。Page 7故人為添加兩個(gè)單位向量，得到人工變量單純形法數(shù)學(xué)模型：故人為添加兩個(gè)單位向量，得到人工變量單純形法數(shù)學(xué)模型： 7 , 2 , 1, 012210243423max732153216432176321jxxxxxxxxxxxxxxMxMxxxxZj其中：其中：M是一個(gè)很大的抽象的數(shù)，不需要給出具體的數(shù)值，可以理解為它能大于是一個(gè)很大的抽象的數(shù)，不需要給出具體的數(shù)值，可以理解為它能大于給定的任何一個(gè)確定數(shù)值；再用前面介紹的單純形法求解該模型，計(jì)算結(jié)果見(jiàn)下給定的任何一個(gè)確定

6、數(shù)值；再用前面介紹的單純形法求解該模型，計(jì)算結(jié)果見(jiàn)下表。表。 Page 8cj32-100-M-MCBXBbx1x2x3x4x5x6x7i0 x64-431-10104-Mx5101-1201005-Mx712-21000113-2M2+M-1+2M-M0 x63-650-1013/5-Mx58-3300108/3-1x312-210005-6M5M0-M002x23/56/5101/50-Mx531/53/5003/5131/3-1x311/52/5012/505 00002x213010123x131/310015/3-1x319/300102/3000-5-25/3j j j j Page 9單純性法小結(jié)單純性法小結(jié):建建立立模模型型個(gè)個(gè) 數(shù)數(shù)取取 值值右右 端端 項(xiàng)項(xiàng)等式或等式或不等式不等式極大或極小極大或極小新加變量新加變量系數(shù)系數(shù)兩兩個(gè)個(gè)三個(gè)三個(gè)以上以上x(chóng)j0 xj無(wú)無(wú)約束約束xj 0 bi 0bi 0=maxZminZxs xa求求解解圖圖解解法、法、單單純純形形法法單純單純形法形法不不處處理理令令xj = xj - xj xj 0 x