這一部分對(duì)應(yīng)書上第四章（P16-P26），其難度比前三章大得多琼娘。個(gè)人建議先粗讀了解這個(gè)方法的思路嗦枢，再精讀把握具體技巧攀芯。建議學(xué)習(xí)時(shí)間為2個(gè)小時(shí)。單純形法是求解線性規(guī)劃問題的通用方法文虏，百度百科中有十分詳細(xì)的說(shuō)明侣诺，可以對(duì)照地閱讀學(xué)習(xí)。
為方便查閱氧秘，再link一下教材年鸳。
基本概念
假設(shè)我們討論的LP問題有個(gè)變量與
個(gè)限制條件。
單純形(Simplex) 和代數(shù)拓?fù)渲械膯涡问且粋€(gè)單詞丸相，但是不清楚二者有沒有關(guān)系搔确。這里指的就是可行域在
維空間中對(duì)應(yīng)的那個(gè)圖形，這里為求一般性提到了n維空間灭忠，但在學(xué)習(xí)的時(shí)候不妨假設(shè)
膳算，反正書上是這樣默認(rèn)的。此時(shí)單純形對(duì)應(yīng)的就是二維平面中的一個(gè)多邊形弛作。單純形方法不是幾何的（類比之前的作圖法）涕蜂，但是借助幾何可以更好地理解這一解法。
-
LP問題的正則形式(Canonical form)是原LP問題的一種變形映琳，滿足：
- 所有的限制條件都寫為等號(hào)形式机隙；
- 所有的變量都是非負(fù)的。
- 最大值問題
其將原限制條件（可能是大于等于或小于等于）寫為等式的方法是引入一個(gè)大于零的松弛變量(slack variable)萨西。概念不難有鹿，詳見P16最底下那塊兒。值得注意的是一個(gè)限制條件至多只會(huì)引入一個(gè)松弛變量原杂。
下圖是將LP化為正則形式的一個(gè)例子。
將LP問題化為正則形式
-
基本解(Basic solution) 對(duì)于有
個(gè)變量（包括松弛變量您机，與
個(gè)限制條件的正則形式的LP問題穿肄，基本解的定義為至少有
個(gè)變量為0的可行解
- 基本解是一個(gè)重要的概念年局，不妨先不加理解地記住其定義。
- 基本解對(duì)應(yīng)的是可行域的頂點(diǎn)咸产。（注意矢否，可行解即可行域中的點(diǎn)）。
- 每一個(gè)可行域的頂點(diǎn)都是基本解 這一點(diǎn)非常重要脑溢，但是書上只提到而沒有詳細(xì)說(shuō)明僵朗。下面給出一種證明。
Proof:
觀察：可行域的每一個(gè)頂點(diǎn)一定是維平面的交（考慮線性方程組有唯一解的條件屑彻，對(duì)線性代數(shù)不是很熟悉的朋友可以先默認(rèn)這一點(diǎn)验庙。）。注意社牲，反之不然粪薛。
考慮任意-條件违寿。
好像沒我想象的那么簡(jiǎn)單，先不寫了熟空。- 基本解中被設(shè)置為0的變量被稱為非基本變量(non-basic variable)藤巢，未被設(shè)置為0的則稱為基本變量(basic variable)。這兩個(gè)概念之后也要用到息罗，注意不要記反了掂咒。
- 所有的基本變量合在一起成為基(basis)。
-
字典(Dictionary)是一種表示阱当、記錄變量的方式俏扩，簡(jiǎn)單點(diǎn)說(shuō)就是用非基本變量表示基本變量和目標(biāo)函數(shù)。如圖所示：
箭頭右邊就是一種字典表示- 字典表示與基本變量的選取有關(guān)弊添。
基本概念部分大概就是這些录淡。第一次看不用要求自己完全理解，不妨先繼續(xù)往下學(xué)習(xí)再慢慢理解這些概念油坝。
思路簡(jiǎn)介
單純形方法的示意圖如下：
簡(jiǎn)單地說(shuō)就是先找到一個(gè)可行解（假如存在的話）嫉戚，之后再不斷地優(yōu)化這個(gè)解。
具體地澈圈，為了對(duì)可行解進(jìn)行優(yōu)化彬檀，書上提到了一種操作。由于書上沒有為這個(gè)操作命名瞬女，為方便起見窍帝，在此我們管這種操作叫“優(yōu)化操作”。優(yōu)化操作是單純形方法的核心步驟诽偷，單純形法說(shuō)白了就是對(duì)一個(gè)基本解實(shí)施若干次優(yōu)化操作后得到最優(yōu)解的過(guò)程坤学。下面我們來(lái)討論什么是優(yōu)化操作疯坤。
優(yōu)化操作
我們先從一下四點(diǎn)直觀的認(rèn)識(shí)入手。
- 首先深浮，優(yōu)化操作將一個(gè)可行解變?yōu)榱硗庖粋€(gè)可行解压怠。
- 由于之前提到過(guò)可行域的頂點(diǎn)一定對(duì)應(yīng)一個(gè)基本解，因此優(yōu)化操作一定將基本解變換為基本解飞苇。
- 回憶基本解的定義菌瘫，自然地可以想到優(yōu)化操作調(diào)整變量的取值，將非基本變量變?yōu)榛咀兞坎伎ǎ瑢⒒咀兞孔優(yōu)榉腔咀兞俊?/strong>
- 更加自然地可以想到：優(yōu)化操作使得目標(biāo)函數(shù)的取值增加雨让。注意，一個(gè)解對(duì)應(yīng)著目標(biāo)函數(shù)的一個(gè)取值羽利。
由于書上根本就沒有優(yōu)化操作的概念宫患，所以在此我自己給出其定義：
定義 優(yōu)化操作
優(yōu)化操作給某一個(gè)非基本變量一非負(fù)增量，使得目標(biāo)函數(shù)增加且使一個(gè)基本變量變?yōu)?这弧。除此之外娃闲，不存在比該增量更小的增量使得該非基本變量加上此增量后存在一個(gè)基本變量為0。
我們稱增加的這個(gè)非基本變量為輸入變量匾浪，變?yōu)?的這個(gè)基本變量為輸出變量皇帮。因?yàn)檩斎胱兞咳〈溯敵鲎兞砍蔀樾碌幕＃ɑ亩x可以在前面找到蛋辈。）
通俗一點(diǎn)地說(shuō)就是選擇一個(gè)非基本變量属拾，讓其不斷增加，要求：
- 目標(biāo)函數(shù)增加冷溶。注意渐白，非基本變量增加時(shí)目標(biāo)函數(shù)不一定增加。
- 當(dāng)某一個(gè)基本變量變?yōu)?時(shí)停止逞频。此即定義的第二句話纯衍。
注意，由于如果一個(gè)變量的增加導(dǎo)致目標(biāo)函數(shù)的增加以及另一個(gè)變量的減少苗胀，那么假如減少的變量可以無(wú)限制地減襟诸，則目標(biāo)函數(shù)就會(huì)無(wú)限制地增。好在由定義可知每個(gè)變量都必須是非負(fù)的基协，所以這種情況不會(huì)發(fā)生歌亲。
回到主題。之前提到單純形法即對(duì)一個(gè)基本解實(shí)施若干次優(yōu)化操作后得到最優(yōu)解的過(guò)程澜驮。我們先不考慮最優(yōu)解的存在性陷揪，且斷言：任意非基本變量增加不使得目標(biāo)函數(shù)增加等價(jià)于目標(biāo)函數(shù)取得最大值。這是因?yàn)橛捎诜?hào)的限制，非基本變量只能增加悍缠，而所有的變量都可以被非基本變量表示揩慕。因此非基本變量的增加包含了所有變量的各種變化。
當(dāng)無(wú)法再進(jìn)行優(yōu)化操作時(shí)有兩種可能扮休。一種是任意非基本變量的增加不使得目標(biāo)函數(shù)增加。此時(shí)目標(biāo)函數(shù)取最大值拴鸵。另外一種情況是任意非基本變量的增加不使得某一基本變量變?yōu)?玷坠。注意，LP問題的標(biāo)準(zhǔn)形式中對(duì)于變量的所有限制最終都會(huì)歸結(jié)于符號(hào)限制劲藐，因此若基本變量不會(huì)變?yōu)?八堡，則非基本變量可以無(wú)限地增加。此時(shí)LP問題無(wú)界聘芜。
還有一點(diǎn)需要注意的是優(yōu)化操作一定會(huì)在有限步后結(jié)束兄渺，之后會(huì)講到這一點(diǎn)。
經(jīng)過(guò)上述討論我們對(duì)單純形算法的核心步驟應(yīng)該有一個(gè)大致的了解了汰现。
單純形算法：實(shí)施步驟
下面是一個(gè)小小的總結(jié)
1. 準(zhǔn)備工作
- 將LP問題化為正則形式挂谍。
- 找到一個(gè)基本解，建立初始字典瞎饲。（具體方法書上P23有講口叙。）
2. 優(yōu)化操作
- 如果目標(biāo)函數(shù)中所有變量的系數(shù)都是負(fù)的，那么目標(biāo)函數(shù)已經(jīng)取最大值嗅战。此時(shí)將非基本變量設(shè)為0妄田，借此解出基本變量與目標(biāo)函數(shù)的值。返回這組值驮捍。
- 如果目標(biāo)函數(shù)中存在正系數(shù)變量疟呐，取之為輸入變量。如果無(wú)法進(jìn)行優(yōu)化操作东且，則LP問題無(wú)界启具。如果可以進(jìn)行優(yōu)化操作，那就進(jìn)行一下優(yōu)化操作苇倡。
- 建立對(duì)應(yīng)的新字典富纸，重復(fù)之前步驟。
單純形算法到此結(jié)束
習(xí)題(P20)
- 要挑選哪個(gè)變量作為輸入變量旨椒，哪個(gè)作為輸出變量晓褪？
滿足定義就行。 - 優(yōu)化操作是否會(huì)在有限步后結(jié)束综慎？
是涣仿。因?yàn)閮?yōu)化操作本質(zhì)上是對(duì)可行域頂點(diǎn)的枚舉，而頂點(diǎn)只有有限個(gè)，且不重復(fù)取到好港。不重復(fù)的原因是每一個(gè)頂點(diǎn)唯一地對(duì)應(yīng)著目標(biāo)函數(shù)的一個(gè)值愉镰，而優(yōu)化算法使得目標(biāo)函數(shù)增加。 - 如何將其他LP問題形式轉(zhuǎn)化為標(biāo)準(zhǔn)形式钧汹？
這在第二章中講過(guò)丈探。 - 如何找到初始字典？
見書上第23頁(yè)拔莱。
