文章申明
文章作者：臧永森
臧永森：清華大學(xué)工業(yè)工程系在讀博士，研究方向：運籌優(yōu)化算法的設(shè)計與應(yīng)用、數(shù)據(jù)統(tǒng)計分析、大數(shù)據(jù)技術(shù)與應(yīng)用，戚銘堯老師團隊
責(zé)任編輯：閻泳楠
文章由『運籌OR帷幄』原創(chuàng)發(fā)布，如需轉(zhuǎn)載請在公眾號后臺獲取轉(zhuǎn)載須知

---

編者按

此文屬于電子書線性規(guī)劃專題第三章單純形法的內(nèi)容。在前面的文章中，我們?yōu)橐雴渭冃畏ń榻B了可行域、最優(yōu)解、可行解、基解、基可行解等基礎(chǔ)概念，也闡述了它們之間的關(guān)系（具體可見文章《在單純形法之前》）。在明確了這些基本概念之后，這一節(jié)我們來探討單純形法的思想邏輯和求解步驟。

我們已經(jīng)知道，優(yōu)化問題的最優(yōu)解一定是基可行解，那么如何找到最優(yōu)的基可行解就是最優(yōu)化問題的求解思路。因此，單純形法在求解過程，就是不斷地尋求變量出入基的循環(huán)迭代過程，每次迭代都達到降低目標(biāo)函數(shù)值（或增大目標(biāo)函數(shù)值）的目的，最終得到最優(yōu)解。那么在迭代過程中，如何使解在改善過程中向著最優(yōu)解的方向盡快地收斂呢？我們下面用比較直觀的方式來解析這個過程。

單純形法的基本思想與邏輯

本文采用的思路參考Dimitris Bertsimas和 John N. Tsitsiklis在 Introduction to Linear Optimization一書中提出的方法[1]。考慮如下標(biāo)準(zhǔn)線性規(guī)劃問題：

我們將矩陣A拆分為n個列元素：A1, A2, A3,, An，那么我們可以將問題看成是滿足非負約束（4）、凸約束（3）以及約束（5）的最小化問題。

結(jié)合式（3）和（5）我們可以看出，原優(yōu)化問題轉(zhuǎn)化為求解能夠構(gòu)造出（b, z）的使得z值最小的關(guān)于（Ai, ci）的凸組合。為了更好地理解它們之間的幾何關(guān)系，我們將一個平面視作包含A的一個m維空間，將與ci相關(guān)的成本項看作是一維垂直數(shù)軸，這時每一個點（Ai, ci）都可以唯一在該三維坐標(biāo)系中表示出來，如圖1所示：

圖1 線性規(guī)劃問題1—4的“列幾何”圖示

我們將（b, z）同樣視為一條垂直線表示在圖1中，這條垂直線叫做需求線，其與平面的交點是（b, 0）點。需求線與（Ai, ci）的凸組合在幾何上有一定的關(guān)系，它們或相交或相離，這取決于我們對（Ai, ci）凸組合的選取，選取的凸組合不一樣，幾何關(guān)系就不同。很容易能理解，如果需求線和凸組合相交，說明（b, z）可以用相應(yīng)的凸組合表示出來，也就表明這個凸組合就是原問題的一個可行解；而如果相離，則說明這個凸組合不滿足能夠表達（b, z）的條件，也就不是原問題的可行解。所有的凸組合構(gòu)成了一個凸包，如果需求線能夠與凸包相交，那么原問題就存在可行解，如果需求線不能與凸包相交，說明原問題無解。進一步將圖1抽象，得到圖2，從圖中我們可以看出，點I、H、G就是三個不同的凸組合與需求線的交點，也就是原問題的三個可行解。

圖2 可行解的“列幾何”圖示

經(jīng)過上面的分析我們得知，要找到最優(yōu)解，就是找到與需求線相交的使得z值最小的凸組合。那么如何找這樣的凸組合呢？首先引入兩個定義：

如果向量

是線性獨立的，那么向量

被稱為Rn空間中的仿射獨立或者仿射無關(guān)，其中k<=n。

2. 在Rn空間中由k+1個仿射無關(guān)向量組成的凸包被稱為k維單純形。

對模型（1—4）來說，總共有m+1個等式約束，假定約束系數(shù)矩陣是滿秩的，那么一個基可行解將對應(yīng)m+1個線性獨立的列向量，也就意味著有m+1個基點，根據(jù)上述定義，由基點之間的差向量線性獨立可以得到其仿射獨立，由此可以知道它們組成的凸包是m維單純形。

假設(shè)m維單純形與需求線相交于點（b, z），由（5）知用來表示（b, z）的線性組合的權(quán)重向量是xi ，該向量就是一個基可行解，也就對應(yīng)我們上節(jié)所分析的基變量的內(nèi)容，當(dāng)然z就是相應(yīng)的目標(biāo)函數(shù)值。我們用圖2做一個解釋，陰影區(qū)域的三角形CDF，就是一個2維單純形，其與需求線的交點H點就是基可行解，點C、D、F是基點。

我們對二維單純形CDF做一些改變，會發(fā)現(xiàn)相應(yīng)的z值（與需求線的交點）也會變化，比如我們令基點B取代基點F，單純形變?yōu)锽CD，這時可行解變?yōu)镮點，相應(yīng)的z值較之前有所增長。類似地，若點E取代點C成為基點，單純形由CDF變?yōu)镋DF，可行解就出現(xiàn)在G點，此時z值有所減小。從這些變化中我們找出這樣一個規(guī)律，當(dāng)且僅當(dāng)新加入基的點在當(dāng)前單純形平面上方（下方）時，所得的交點（即可行解）對應(yīng)的z值會增大（減小）。

如果我們更加形象地描述這個基點變化的過程，就如同用手抓住單純形CDF的基點C，保持D點和F點固定不變，用力向上拉（向下拉），將C點拉到B點（E點），也就產(chǎn)生了新的單純形BCD（EDF）。單純形法的旋轉(zhuǎn)迭代過程，就是不斷找到基點向上拉（向下拉）到新基點形成新單純形的過程。

單純形法的求解過程

簡單總結(jié)一下單純形法的求解原理。先找到一個基可行解，然后從非基解中找一個比較有前途的點入基，替換掉基可行解中有待改善的基點，從而達到改善目標(biāo)函數(shù)的目的，如此重復(fù)迭代，直至無法找到可以入基的點。

下面我們用一個例題來演示單純形法的求解過程。用單純形法求解如下LP問題：

第一步：將上述LP轉(zhuǎn)化為標(biāo)準(zhǔn)形式，目的是能夠在初始單純形表中很容易地獲得初始基可行解。

第二步，將標(biāo)準(zhǔn)LP列入第0個單純形表，如表1：

表1 單純形表0

上述單純形表中可以看出初始基變量是（s1,s2,s3），從表中找一個能夠入基的變量，要求該變量入基后能夠使得目標(biāo)函數(shù)值增大量最大。決策變量在第0行的系數(shù)看成是這個變量的縮減成本，就是當(dāng)這個變量增加1時，目標(biāo)函數(shù)z的值將減少的量。比如x1的系數(shù)是-2，就說明當(dāng)x1每增加1，z值將減少-2，也就是增加2。因此如果我們要選擇能夠使目標(biāo)函數(shù)增加量最大的量入基，應(yīng)該選擇第0行中系數(shù)最小的負值（讀者可以考慮下為什么必須是負值）。因此這里選擇x2入基。

那如何選擇出基變量呢？這里我們采用比值法，用右端項的值（即rhs列）除以出基變量對應(yīng)的列系數(shù)（紅色線框標(biāo)注），從中選擇最小的比值對應(yīng)的基變量出基。如果不選擇最小比值對應(yīng)的基變量出基，將會導(dǎo)致后面的迭代過程出現(xiàn)負的右端項，相應(yīng)行的基變量將為負值，這與LP標(biāo)準(zhǔn)型的變量非負約束相違背，因此這種操作是不被允許的。所以，表1中的比值優(yōu)勝者是3，因此s3出基（藍色線框標(biāo)注）。

第三步：通常我們會在x2所在列與s3所在行交匯點圈一個圈，也就是元素4。這表示這一點是我們的轉(zhuǎn)軸點，通過初等變化，將該元素所在的行與列的其他元素變?yōu)?，該元素本身變?yōu)?，得到下一個單純形表，如表2所示：

表2 單純形表1

第四步：繼續(xù)在第0行找負系數(shù)對應(yīng)的入基變量，發(fā)現(xiàn)x1對應(yīng)的系數(shù)是-2，可以入基。同時比值運算發(fā)現(xiàn)s1對應(yīng)的變量需要出基，因此第一行、x1列對應(yīng)的元素1是轉(zhuǎn)軸點，圈一個圈，并進行列運算，得表3：

表3 單純形表2

第五步：繼續(xù)上述計算，注意這里因為入基變量s3對應(yīng)的列有負值，在比值運算時直接賦值為空，因為比值只看正值，如果將負值也考慮進來取最小比值，同樣將導(dǎo)致負的右端項。通過入基變量選取和比值測試，對元素2圈圈，做行列變換，得表4：

表4 單純形表3

第六步：最新表中發(fā)現(xiàn)第0行的所有元素均為正值，此時選取任何變量入基，都會使得z值因為正的縮減成本而降低，很顯然這對于最大化問題來說是不利的。因此，上表已經(jīng)達到最優(yōu)狀態(tài)，單純形法迭代結(jié)束。

綜上，原問題最優(yōu)解就是

本文主要介紹了單純形法的基本邏輯思路，以及具體的求解過程，接下來我們將繼續(xù)帶領(lǐng)大家探索單純形法求解過程中可能出現(xiàn)的幾種解，以及單純形法的變形求解方法。，希望大家繼續(xù)關(guān)注【優(yōu)化】板塊，電子書線性規(guī)劃專題的科普文。

參考文獻：
[1] Dimitris Bertsimas, John N. Tsitsiklis, Introduction to Linear Optimization. Athena Scientific, Belmont, Massachusetts. P120—123.

相關(guān)文章推薦

此文屬于電子書線性規(guī)劃專題第三章單純形法的內(nèi)容。單純形法是求解線性規(guī)劃問題的有效算法。在具體介紹單純形法之前，我們需要先認識求解線性規(guī)劃問題中的兩組重要概念：（1）可行域與最優(yōu)解；（2）基變量與基可行解。

點擊藍色標(biāo)題，即可閱讀《在單純形法之前》

其他

【優(yōu)化】優(yōu)化理論科普叢書專題征稿之線性規(guī)劃理論

---

號外！『運籌OR帷幄』入駐知識星球！！隨著算法崗位對專業(yè)人才要求的提高，面試題越來越難。『運籌OR帷幄』特建立【算法崗面試求職招聘】知識星球，邀請業(yè)界資深算法工程師，幫助大家解答面試題中的疑點難點，分享成功面試經(jīng)驗。內(nèi)容涵蓋運籌學(xué)、數(shù)據(jù)科學(xué)、人工智能等和算法相關(guān)的專業(yè)。讓大家面對算法面試更加游刃有余。豪華嘉賓陣容
目前星球特邀入駐的嘉賓（曾）就職的公司包括（不斷擴展中）：
騰訊、百度、阿里（菜鳥、達摩院、盒馬）、華為、微軟、英偉達、順豐科技、曠視、SAP、NEC、美團、蘇寧、福特、阿里媽媽、東芝、松下、佳能、拼多多、環(huán)球易購、攜程、滴滴、京東、杉數(shù)科技、Sabre、悠樺林、Pier、奇弦智能、Momenta等
掃碼加入！

加入『運籌OR帷幄』知識星球的好處

• 中國你能說出名字的幾乎所有大廠（資深）算法工程師入駐
• 歐美數(shù)家大廠（資深）軟件工程師入駐
• 以上所有公司獨家內(nèi)推機會
• 簡歷修改指導(dǎo)
• 面試咨詢， 模擬面試
• 得到一對一指導(dǎo)、解答工作中的疑惑
• 多家Offer選擇指導(dǎo)
• 以面試題為學(xué)習(xí)資料學(xué)習(xí)真正的算法干貨，從小白變成大咖
• 不定期的線上、線下交流會和聚會,拓展人脈。

---

歡迎關(guān)注『運籌OR帷幄』公眾號

點擊查看『運籌OR帷幄』志愿者招募介紹及加入方式：

總結(jié)

以上是生活随笔為你收集整理的单纯形法表格法例题详解_优化 |运筹学线性规划单纯形法之求解的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。