單純形法（simplicial method）是求解線性規(guī)劃問題的一種行之有效的方法。其基本思想是從一個(gè)基本可行解出發(fā)，求一個(gè)使目標(biāo)函數(shù)值有所改善的基本可行解；通過不斷改進(jìn)基本可行解，力圖達(dá)到最優(yōu)基本可行解。
單純形法起源于線性規(guī)劃問題的研究，20世紀(jì)30年代末期，蘇聯(lián)數(shù)學(xué)家康托羅維奇（Leonid Kantorovich）和美國(guó)經(jīng)濟(jì)學(xué)家里昂惕夫（Wassily Leontief）分別在制造業(yè)、經(jīng)濟(jì)學(xué)領(lǐng)域做出了線性規(guī)劃的初次嘗試，但他們的工作沒有受到重視。第二次世界大戰(zhàn)期間，美國(guó)空軍成立了研究小組來研究資源優(yōu)化問題，1947 年，數(shù)學(xué)家丹齊格（George Bernard Dantzig）推導(dǎo)得出線性規(guī)劃的標(biāo)準(zhǔn)形式和解決線性規(guī)劃問題的單純形法，并于兩年后在最優(yōu)化的第一次會(huì)議上做了報(bào)告。后來，計(jì)算機(jī)學(xué)家約翰·馮·諾依曼（John von Neumann）寄予了他肯定和支持，并提出了線性規(guī)劃的對(duì)偶形式。但是，隨著涉及更多變量復(fù)雜問題的嘗試，對(duì)于單純形法的改進(jìn)需求越來越迫切。1974年，維利·勃蘭特（R.G. Bland）通過提出一種簡(jiǎn)便的規(guī)則解決了最優(yōu)解的循環(huán)問題，周勤學(xué)等學(xué)者針對(duì)該法則給出了改進(jìn)的形式。2000年，美國(guó)物理學(xué)會(huì)和計(jì)算機(jī)協(xié)會(huì)推舉單純形法為“本世紀(jì)前十名的算法之一”，進(jìn)一步肯定了其應(yīng)用價(jià)值，該方法也許會(huì)適用于更大的模型。
單純形法的求解可以通過變換單純形表來實(shí)現(xiàn)，而對(duì)于選取初始可行基這一關(guān)鍵步驟，通常采用大法和二階段法這兩種方法。單純形法經(jīng)過改進(jìn)，可以節(jié)省計(jì)算機(jī)的儲(chǔ)存量和計(jì)算量，提升求解效率。而對(duì)于求解模糊化的線性規(guī)劃模型，也需對(duì)方法進(jìn)行相應(yīng)的調(diào)整。此外，單純形法在現(xiàn)實(shí)世界中應(yīng)用廣泛，如在工程學(xué)中，通過建立土石方動(dòng)態(tài)調(diào)配模型，采用單純形法求出最優(yōu)調(diào)配方案，可以滿足施工強(qiáng)度在填筑、開采、運(yùn)輸?shù)确矫娴母黜?xiàng)要求。
簡(jiǎn)史
早期研究
單純形法起源于線性規(guī)劃問題的研究，20世紀(jì)上半葉，社會(huì)生產(chǎn)力飛速發(fā)展，資源分配工作成為企業(yè)管理面臨的一大難題。20世紀(jì)30年代末期，蘇聯(lián)數(shù)學(xué)家康托羅維奇（Leonid Kantorovich）和美國(guó)經(jīng)濟(jì)學(xué)家里昂惕夫（Wassily Leontief）分別在制造業(yè)以及經(jīng)濟(jì)學(xué)領(lǐng)域做出了線性規(guī)劃的初次嘗試，但他們的工作沒有受到重視。第二次世界大戰(zhàn)期間，美國(guó)空軍成立了研究小組來研究資源優(yōu)化問題，1947 年，數(shù)學(xué)家丹齊格（George Bernard Dantzig）推導(dǎo)得出線性規(guī)劃的標(biāo)準(zhǔn)形式和解決線性規(guī)劃問題的單純形法，并于兩年后在最優(yōu)化的第一次會(huì)議上做了報(bào)告。后來，計(jì)算機(jī)學(xué)家約翰·馮·諾依曼（John von Neumann）寄予了他支持和肯定，并提出了線性規(guī)劃的對(duì)偶形式。
后續(xù)發(fā)展
但是，隨著涉及更多變量復(fù)雜問題的嘗試，對(duì)于單純形法的改進(jìn)需求越來越迫切。1952年，丹齊格（Dantzig）和奧頓（Orden）提出了對(duì)偶問題相應(yīng)的定理，后來，丹齊格（Dantzig）于1954年給出了改進(jìn)的單純形法。20世紀(jì)70年代之后，人們對(duì)于線性規(guī)劃計(jì)算的時(shí)間復(fù)雜性進(jìn)行了研究，克萊（Klee）和米尼什（Minth）指出單純形法是具有指數(shù)時(shí)間復(fù)雜度的。1974年，維利·勃蘭特（R.G. Bland）通過提出一種簡(jiǎn)便的規(guī)則解決了最優(yōu)解的循環(huán)問題。后來，隨著電子計(jì)算機(jī)的進(jìn)步，萊斯大學(xué)的比克斯比（Bob Bixby）的CPLEX軟件、IBM的佛利斯特（John Forrest）的OSL軟件，提高了單純形法的求解速度。1989年，周勤學(xué)等學(xué)者針對(duì)維利·勃蘭特法則給出改進(jìn)的形式。2000年，美國(guó)物理學(xué)會(huì)和計(jì)算機(jī)協(xié)會(huì)推舉單純形法為“本世紀(jì)前十名的算法之一”，進(jìn)一步肯定了其應(yīng)用價(jià)值，該方法也許會(huì)適用于更大的模型。
方法內(nèi)容
線性規(guī)劃：最優(yōu)化中理論成熟，方法有效，應(yīng)用廣泛的一個(gè)分支。它研究線性的目標(biāo)函數(shù)的極值，而自變量必須滿足一組線性等式與不等式組成的約束條件。
一般線性規(guī)劃問題總可以寫成下列標(biāo)準(zhǔn)形式：
（1.1.1）
或用矩陣表示：
（1.1.2）
其中是矩陣，是維行向量，是維列向量。
單純形法的基本思想：若線性規(guī)劃（標(biāo)準(zhǔn)形式）有最優(yōu)解，則必存在最優(yōu)基本可行解，因此求解線性規(guī)劃問題歸結(jié)為尋找最優(yōu)基本可行解。單純形方法的基本思想，就是從一個(gè)基本可行解出發(fā)，求一個(gè)使目標(biāo)函數(shù)值有所改善的基本可行解；通過不斷改進(jìn)基本可行解，力圖達(dá)到最優(yōu)基本可行解。使用該方法求解需滿足如下條件：
（1）最優(yōu)性條件，即在求解問題的過程中，保證獲得的新的基本可行解不會(huì)比原來的基本可行解更差。
（2）可行性條件，即在求解過程中，保證從一個(gè)基本可行解出發(fā)，在計(jì)算過程中只會(huì)碰到基本可行解。
相關(guān)概念
對(duì)于線性規(guī)劃標(biāo)準(zhǔn)模型的矩陣形式（1.1.2），，，， ，矩陣的秩。
基、基變量與非基變量
矩陣 中任意一個(gè)階的非奇異子陣稱為線性規(guī)劃問題的一個(gè)基，設(shè)
那么對(duì)應(yīng)的變量稱為基變量，而其余的變量稱為非基變量。
基本解、基本可行解與可行基
對(duì)于基，在中，令非基變量全為零，可唯一地確定出一個(gè)解
稱為線性規(guī)劃問題（1.1.1）的一個(gè)基本解。
如果基本解又滿足非負(fù)限制，即，則被稱為基本可行解，基本可行解對(duì)應(yīng)的基稱為可行基。
計(jì)算步驟
單純形表
單純形表是應(yīng)用單純形法的基本工具，其功能與增廣矩陣相似。
求解思路：方程組
與目標(biāo)函數(shù)組成個(gè)變量，個(gè)方程的方程組
若將看作不參與基變換的基變量，它與的系數(shù)構(gòu)成一個(gè)基，這時(shí)可采用行初等變換將變換為零，使其對(duì)應(yīng)的系數(shù)矩陣為單位矩陣。得到
可根據(jù)上述增廣矩陣設(shè)計(jì)計(jì)算表。
每迭代一步可以構(gòu)造一個(gè)新的單純形表。
具體步驟
（1）找出初始可行基，確定初始基可行解，建立初始單純形表。
（2）檢驗(yàn)各非基變量的檢驗(yàn)數(shù)是
，若
則已得到最優(yōu)解，可停止計(jì)算。否則轉(zhuǎn)入下一步。
（3）在中，若有某個(gè)對(duì)應(yīng)的系數(shù)列向量，則此問題是無界，停止計(jì)算。否則，轉(zhuǎn)入下一步。
（4）根據(jù)，確定為換入變量，按規(guī)則計(jì)算
可確定為換出變量，轉(zhuǎn)入下一步。
（5）以為主元素進(jìn)行迭代（即用高斯消去法或稱為旋轉(zhuǎn)運(yùn)算），把所對(duì)應(yīng)的列向量
變換為第行
將列中的換為，得到新的單純形表。重復(fù)（2）~（5），直至終止。
求解初始可行基
初始可行基的選取是單純形法的關(guān)鍵步驟。以下為初始可行基的兩種尋求方法，即大法和二階段法。
大M法
基本思想：大法就是在約束方程中加入人工變量后，對(duì)于每一個(gè)人工變量，在目標(biāo)函數(shù)中增加一項(xiàng)“”（是充分大的正數(shù)），構(gòu)成一個(gè)新的目標(biāo)函數(shù)，只要有一個(gè)人工變量取正值，則新的目標(biāo)函數(shù)就不可能取得最大值，故可用這種方法來迫使所有人工變量的取值為零。
二階段法
基本思想：如果約束不等式是“”或者是約束方程式，則初始可行基不能直接得到。對(duì)于如下形式的線性規(guī)劃問題，不能直接應(yīng)用單純形法來求解。
為此，可引進(jìn)松弛變量來把線性規(guī)劃問題化為以下形式。
其中是足夠大的數(shù)。然后利用單純形法求出原問題的一個(gè)基本可行解，再利用單純形法求出原問題的最優(yōu)解。這樣兩次應(yīng)用單純形法求解線性規(guī)劃問題的方法叫做二階段法。
特殊結(jié)果
多重解
一般地，在一個(gè)線性規(guī)劃問題的最優(yōu)基對(duì)應(yīng)的單純形表中，如果非基變量對(duì)應(yīng)的檢驗(yàn)數(shù)都是負(fù)數(shù)，則最優(yōu)解是唯一的；如果非基變量對(duì)應(yīng)的檢驗(yàn)數(shù)中有零，那么這一問題的最優(yōu)解可能不只一個(gè)，而一旦求得另一個(gè)最優(yōu)解，就可得到無窮多個(gè)最優(yōu)解。
無界解
若某基變量的檢驗(yàn)數(shù)是，且的系數(shù)列向量，則此問題屬于解無界的情形，無最優(yōu)解。
退化與循環(huán)
退化：線性規(guī)劃的單純形法計(jì)算中出現(xiàn)退化基可行解的現(xiàn)象就稱為退化，在線性規(guī)劃的求解過程中，退化是一種比較常見的現(xiàn)象。
循環(huán)：?jiǎn)渭冃畏ㄓ?jì)算中用規(guī)則確定換出變量時(shí)，有時(shí)存在兩個(gè)以上相同的最小比值，這樣在下一次迭代中就有一個(gè)或幾個(gè)基變量等于零，這就出現(xiàn)退化解。這時(shí)換出變量，迭代后目標(biāo)函數(shù)值不變。這里不同基表示為同一頂點(diǎn)。可構(gòu)造一個(gè)特例，當(dāng)出現(xiàn)退化時(shí)，進(jìn)行多次迭代，而基從又返回到，即出現(xiàn)計(jì)算過程的循環(huán)，便永遠(yuǎn)達(dá)不到最優(yōu)解。
勃蘭特規(guī)則：避免出現(xiàn)循環(huán)的一種方法。可表示為：
（1）選取中下標(biāo)最小的非基變量為換入變量，即；
（2）當(dāng)按規(guī)則計(jì)算存在兩個(gè)和兩個(gè)以上最小比值時(shí)，選取下標(biāo)最小的基變量為換出變量。
方法變形
改進(jìn)單純形法
單純形法的計(jì)算是從初始單純形表經(jīng)過多次迭代，最后得到單純形表的。每經(jīng)過一次迭代，都要計(jì)算一個(gè)單純形表，計(jì)算量很大。但是，采用單純形法求解的最終目的是求得問題的最優(yōu)解，而在迭代過程中出現(xiàn)的一系列單純形表中某些數(shù)據(jù)的計(jì)算實(shí)際上是多余的。在利用計(jì)算機(jī)進(jìn)行計(jì)算時(shí)，為了節(jié)省存儲(chǔ)量和計(jì)算量，需要對(duì)單純形法進(jìn)行改進(jìn)。此外，改進(jìn)單純形法的每次迭代是可以直接從原始數(shù)據(jù)出發(fā)進(jìn)行計(jì)算的，這樣還可以減少累積誤差的產(chǎn)生。
基本步驟：
（1）確定初始可行基，并求出的逆矩陣。通常取單位矩陣為初始可行基，這時(shí)。
（2）求出
得到關(guān)于的基本可行解:。
（3）求出。若，則停止計(jì)算，上述基本可行解為最優(yōu)解。否則轉(zhuǎn)到（4）。
（4）若存在非基變量的檢驗(yàn)數(shù)，且，則停止計(jì)算，問題無最優(yōu)解。否則，若，則取為入基變量。
（5）求出主列：
（6）按法則求出:
(為基變量的下標(biāo)）
這時(shí)，取為出基變量，從而可以得到新的可行基，再返回到（1）。
對(duì)偶單純形法
對(duì)偶單純形法是運(yùn)用對(duì)偶原理求解原問題的一種方法，而不是求解對(duì)偶問題的單純形法。它和單純形法的主要區(qū)別在于：?jiǎn)渭冃畏ㄔ谡麄€(gè)迭代的過程中，始終保持原問題的可行性，即常數(shù)列0，而檢驗(yàn)數(shù)（即）由有正分量逐步變?yōu)槿浚醋優(yōu)闈M足，是對(duì)偶問題的可行解），這樣就同時(shí)得到原問題和對(duì)偶問題的最優(yōu)解。對(duì)偶單純形法則是在整個(gè)迭代過程中，始終保持對(duì)偶問題的可行性，即全部檢驗(yàn)數(shù)，而常數(shù)列由有負(fù)分量逐步變?yōu)槿浚醋優(yōu)闈M足原問題的可行性），同時(shí)得到原問題和對(duì)偶問題的最優(yōu)解。
基本步驟：
（1）根據(jù)線性規(guī)劃問題，列出初始單純形表。設(shè)檢驗(yàn)數(shù)全都小于或等于零，檢驗(yàn)列的數(shù)字，若全是非負(fù)數(shù)，則已得到最優(yōu)解，停止計(jì)算。否則，轉(zhuǎn)入下一步。
（2）確定換出變量，若
則確定對(duì)應(yīng)的基變量為換出變量。
（3）確定換入變量，在單純形表中檢查所在行的各系數(shù)，若所有，則無可行解，停止計(jì)算。若存在，則計(jì)算：
于是按所對(duì)應(yīng)的列確定為換入變量，這樣才能保證所得的檢驗(yàn)數(shù)仍都小于或等于零。
（4）以為主元素，按單純形法在表中進(jìn)行換基運(yùn)算，得到新的單純形表。
重復(fù)以上各步，直至為止，最后得到，即為所求的最優(yōu)解。
類似理論
多項(xiàng)式時(shí)間算法
多項(xiàng)式時(shí)間算法也可以用于線性規(guī)劃問題的求解。如果存在和的一個(gè)多項(xiàng)式，使得該問題的任何實(shí)例都可以在計(jì)算時(shí)間（或次數(shù)）之內(nèi)解出，則稱該問題存在多項(xiàng)式時(shí)間算法，簡(jiǎn)稱多項(xiàng)式算法，而稱為算法的計(jì)算復(fù)雜性。
區(qū)別：?jiǎn)渭冃畏m然操作簡(jiǎn)單易行，但不是求解線性規(guī)劃問題的優(yōu)良算法。由哈奇揚(yáng)（Khachiyan）提出的求解線性規(guī)劃的橢球法可以避免單純形法最壞情形下的指數(shù)時(shí)間問題，但是，該方法在實(shí)際應(yīng)用中比單純形法慢。另一種多項(xiàng)式時(shí)間內(nèi)點(diǎn)法由卡馬卡（Karmarkar）提出，它避免了哈奇揚(yáng)橢球算法的不可操作性。
下山單純形法
下山單純形法是一種直接搜索算法，主要用于無約束函數(shù)優(yōu)化問題的局部搜索。其核心思想為：比較單純形各頂點(diǎn)對(duì)應(yīng)的適應(yīng)度函數(shù)值，并以此作為判斷各點(diǎn)好壞的依據(jù)，將通過反射、膨脹和收縮三種操作得出的新點(diǎn)替換原單純形中最差的點(diǎn)，形成新的單純形，從而通過迭代而逼近最優(yōu)點(diǎn)。下山單純形法具有高效的局部搜索能力，已經(jīng)在很多領(lǐng)域取得了成功的應(yīng)用。
聯(lián)系：二者雖然名稱相似，但單純形法求解線性規(guī)劃問題，而下山單純形法求解無約束函數(shù)問題，它們是沒有直接關(guān)聯(lián)的兩種算法。
推廣
模糊線性規(guī)劃
對(duì)于經(jīng)典的線性規(guī)劃模型，其中的任何部分都可以用適當(dāng)?shù)姆绞綄⒅：Ｆ┤鐮顟B(tài)系數(shù)可以是模糊數(shù)，約束條件可以寫成模糊集，目標(biāo)函數(shù)也可以表示為模糊集或模糊函數(shù)等。選取不同的模糊對(duì)象與模糊方式會(huì)導(dǎo)致不同類型的模糊線性規(guī)劃問題（FLP）。
例：如下述模糊線性規(guī)劃問題
這里，，向量，和有相應(yīng)的維數(shù)且假設(shè)。模糊條件（2）是某種彈性約束，意指“近似小于等于”，也就是隨著（2）式右端常數(shù)項(xiàng)（看作參變量）的變化增大，近似的模糊隸屬度也會(huì)逐漸減少。于是，個(gè)約束條件可分別由個(gè)模糊集表達(dá)，其隸屬函數(shù)單調(diào)遞減。
新單純形算法
關(guān)于求解模糊線性規(guī)劃問題的一種新的單純形算法，就是應(yīng)用單純形法先求解與（FLP）相應(yīng)的普通線性規(guī)劃問題；然后，通過模糊約束集與模糊目標(biāo)集的隸屬度的比較，獲得的最優(yōu)值；最后，將模糊約束集與模糊目標(biāo)集的交集的最優(yōu)隸屬度代入最優(yōu)單純形表中，即可求得模糊線性規(guī)劃問題的解。
例題分析
例：用單純形方法解下列問題：
解：引進(jìn)松弛變量，把上述問題化成標(biāo)準(zhǔn)形式：
建立初始單純形表：
初表中的判別數(shù)用定義式
算出。由于此例是極大化問題，判別數(shù)中有負(fù)數(shù)，因此可求改進(jìn)的基本可行解。由于最小判別數(shù)
，
因此取第1列作為主列。根據(jù)最小比值規(guī)則，取第2行作為主行。以為主元，進(jìn)行主元消去，得下表:
再以為主元，進(jìn)行主元消去，得到
判別數(shù)均非負(fù)，達(dá)到最優(yōu)。最優(yōu)解
，
目標(biāo)函數(shù)的最優(yōu)值
。
應(yīng)用
工程學(xué)
鋼鐵冶煉
脫氧合金化是鋼鐵冶煉的過程中最重要的工藝環(huán)節(jié)之一， 在保證鋼水質(zhì)量的同時(shí)，為了最大限度地降低合金鋼的生產(chǎn)成本，基于數(shù)學(xué)模型建立一種自動(dòng)配料模型是各個(gè)鋼鐵企業(yè)為了提高企業(yè)競(jìng)爭(zhēng)力亟待解決的問題。選取代表元素C、Mn并利用參考爐次法對(duì)其收得率進(jìn)行計(jì)算，通過對(duì)偶單純形法對(duì)相關(guān)數(shù)據(jù)以及收得率的預(yù)測(cè)結(jié)果，可建立綜合的單純形法合金配料模型，再對(duì)數(shù)據(jù)進(jìn)行計(jì)算分析，最終通過MATLAB軟件求解，從而可以得到鋼水脫氧合金化的最優(yōu)配料方案。
土石方施工
土石方動(dòng)態(tài)調(diào)配優(yōu)化平衡是大型土石方工程施工中的核心問題。通過分析土石方平衡調(diào)配系統(tǒng)涉及到的各個(gè)影響因素，以全過程總調(diào)配費(fèi)用最低為目標(biāo)函數(shù)，綜合考慮調(diào)配過程中定量和定性化的約束條件，可以構(gòu)建出土石方動(dòng)態(tài)調(diào)配模型，并采用單純形法進(jìn)行求解，從而求出最優(yōu)調(diào)配方案。實(shí)例驗(yàn)證的結(jié)果表明，單純形法簡(jiǎn)便易行，能夠快速獲得調(diào)配結(jié)果，最終得到的調(diào)配方案可以滿足施工強(qiáng)度在填筑、開采、運(yùn)輸?shù)确矫娴母黜?xiàng)要求。
經(jīng)濟(jì)學(xué)
生產(chǎn)作業(yè)計(jì)劃在企業(yè)競(jìng)爭(zhēng)中尤為重要，企業(yè)需要加強(qiáng)自身生產(chǎn)計(jì)劃管理水平，才能對(duì)可利用資源進(jìn)行充分計(jì)劃與統(tǒng)籌，滿足客戶對(duì)于產(chǎn)品的不同需求。在生產(chǎn)作業(yè)計(jì)劃中，圖解法是尋求最優(yōu)解的一種有效方法。但是，對(duì)于三種以上產(chǎn)品的生產(chǎn)作業(yè)計(jì)劃問題，圖解法無能為力。單純形法可以解決這一難題，基本思想是針對(duì)企業(yè)生產(chǎn)作業(yè)計(jì)劃進(jìn)行建模，編制出初始單純形矩陣，對(duì)矩陣進(jìn)行換基迭代，讓其變成簡(jiǎn)單矩陣，這樣可以提高運(yùn)算效率。
參考資料 >
simplex method.britannica.2024-05-18