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

1、Page 1整理課件例例1.8 用單純形法求下列線性規(guī)劃的最優(yōu)解用單純形法求下列線性規(guī)劃的最優(yōu)解 0,30340243max21212121xxxxxxxxZ解：解：1）將問題化為標(biāo)準(zhǔn)型，加入松馳變量將問題化為標(biāo)準(zhǔn)型，加入松馳變量x3、x4則標(biāo)準(zhǔn)型為則標(biāo)準(zhǔn)型為: 0,30340243max432142132121xxxxxxxxxxxxZPage 2整理課件2）求出線性規(guī)劃的初始基可行解，列出初始單純形表。）求出線性規(guī)劃的初始基可行解，列出初始單純形表。3)1020(3)(2141131 acacc1 檢驗(yàn)數(shù)檢驗(yàn)數(shù)j Page 3整理課件3）進(jìn)行最優(yōu)性檢驗(yàn)）進(jìn)行最優(yōu)性檢驗(yàn)如果表中所有檢驗(yàn)數(shù)如果

2、表中所有檢驗(yàn)數(shù) ，則表中的基可行解就是問題的最優(yōu)解，計(jì)算停，則表中的基可行解就是問題的最優(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作為作為換入變量。換入變量。確定換出變量。根據(jù)下式計(jì)算并選擇確定換出變量。根據(jù)

3、下式計(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 5整理課件j j j 換入列換入列bi /ai2，ai204010換換出出行行將將3化為化為15/311801/301/3

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