第二節(jié)單純形法

單純形法是求解線性規(guī)劃的主要算法，1947年由美國(guó)斯坦福大學(xué)教授丹捷格（G.B.Dantzig）提出。盡管在其后的幾十年中，又有一些算法問(wèn)世，但單純形法以其簡(jiǎn)單實(shí)用的特色始終保持著絕對(duì)的“市場(chǎng)”占有率。

單純形法是一種迭代的算法（設(shè)計(jì)在單純形表上實(shí)現(xiàn)），它的思想是在可行域的角點(diǎn)（稱為基本可行解）中尋優(yōu)。檢驗(yàn)這個(gè)角點(diǎn)是否最優(yōu)否是停止確定一個(gè)初始角點(diǎn)?尋找一個(gè)更好的角點(diǎn)??1.將模型化為標(biāo)準(zhǔn)型

標(biāo)準(zhǔn)型的特征：Max型、等式約束、非負(fù)約束一、單純形法的步驟非標(biāo)準(zhǔn)形式如何化為標(biāo)準(zhǔn)1)Min型化為Max型

加負(fù)號(hào)

因?yàn)椋笠粋€(gè)函數(shù)的極小點(diǎn)，等價(jià)于求該函數(shù)的負(fù)函數(shù)的極大點(diǎn)。注意：Min型化為Max型求解后，最優(yōu)解不變，但最優(yōu)值差負(fù)號(hào)。

2)

不等式約束化為等式約束分析：以例1.1中煤的約束為例之所以“不等”是因?yàn)樽笥覂蛇呌幸粋€(gè)差額，稱為“松弛量”，若在左邊加上這個(gè)松弛量，則化為等式。而這個(gè)松弛量也是變量，記為X3

，則有X3稱為松弛變量。問(wèn)題：它的實(shí)際意義是什么？

——

煤資源的“剩余”。練習(xí)：請(qǐng)將例1.1的約束化為標(biāo)準(zhǔn)型解：增加松弛變量則約束化為易見(jiàn)，增加的松弛變量的系數(shù)恰構(gòu)成一個(gè)單位陣I。2.建立初始單純形表

前提：模型的系數(shù)陣A中含I（單位陣）。否則用人工變量法。初始單純形表的結(jié)構(gòu)全體變量名變量的價(jià)格系數(shù)約束系數(shù)陣與A中的I相應(yīng)的變量（稱基變量）名基變量的價(jià)格系數(shù)約束右端項(xiàng)例1.5：列出例1.1標(biāo)準(zhǔn)模型的初始單純形表3.檢驗(yàn)該單純形表是否最優(yōu)檢驗(yàn)數(shù)：每個(gè)變量的檢驗(yàn)數(shù)等于該變量的價(jià)格系數(shù)減去與該變量的系數(shù)列之積。法則：如果全體檢驗(yàn)數(shù)均非正，則本表為最優(yōu)，相應(yīng)的最優(yōu)解否則轉(zhuǎn)4。例1.6：檢驗(yàn)例1.1的初始單純形表是否最優(yōu)相應(yīng)于x1的系數(shù)列練習(xí)：計(jì)算x2的檢驗(yàn)數(shù)。由于檢驗(yàn)數(shù)中有正的，故本表不是最優(yōu)。練習(xí)：寫出下列線性規(guī)劃的標(biāo)準(zhǔn)型和初始單純形表，并檢驗(yàn)該表是否最優(yōu)。由于檢驗(yàn)數(shù)中有正的，故本表不是最優(yōu)。確定一個(gè)初始角點(diǎn)檢驗(yàn)這個(gè)角點(diǎn)是否最優(yōu)尋找一個(gè)更好的角點(diǎn)否是停止下一步？4.計(jì)算下一張單純形表（1）確定本表的進(jìn)基、出基變量和主元

?選本表正檢驗(yàn)數(shù)中最大者，其相應(yīng)的變量xk進(jìn)基；

?計(jì)算與xk的系數(shù)列之比（記，稱檢驗(yàn)比）,選中最小者相應(yīng)的變量xl出基（注意：當(dāng)xk的系數(shù)列中有零或負(fù)值時(shí)，相應(yīng)不算）；

?

xk列與xl行的交叉元即主元。[]例如（2）基于主元計(jì)算下一張單純形表

?用初等行變換方法，先將主元消成1，再用此1將其所在列的其余元消成0，所得結(jié)果寫在新表上；

?轉(zhuǎn)第3步（即檢驗(yàn)新表是否最優(yōu)）。[]例如例1.7：用單純形法求解例1.1問(wèn)題：標(biāo)準(zhǔn)模型的A中是否含I？——松弛變量系數(shù)恰好構(gòu)成I。[][][]（請(qǐng)解釋其實(shí)際意義）練習(xí)：用單純形法求解下面的線性規(guī)劃

[]總結(jié)表的規(guī)律：表中基變量的系數(shù)列有何特征？基變量的檢驗(yàn)數(shù)有何特征？——均為單位向量列；——均為零。例1.8：填出表中空白：?jiǎn)栴}：如果空白的不是基變量列怎么辦呢？3.表上每一列的含義：4.每張表上B-1的位置在哪？——對(duì)應(yīng)于初表中