最佳化 | 在單純形法之前

編者按：

此文屬於電子書

線性規劃

專題第三章單純形法的內容。單純形法是求解線性規劃問題的有效演算法。在具體介紹單純形法之前，我們需要先認識求解線性規劃問題中的兩組重要概念：（1）可行域與最優解；（2）基變數與基可行解。

作者：臧永森

清華大學工業工程系在讀博士生，研究方向：運籌最佳化演算法設計與應用、資料統計分析、大資料技術與應用，

戚銘堯

老師團隊

文章發表於

微信公眾號【運籌OR帷幄】：

最佳化 | 在單純形法之前

歡迎原連結轉發，轉載請私信

@運籌OR帷幄

獲取資訊，盜版必究。

敬請關注和擴散本專欄及同名公眾號，會邀請

全球知名學者

釋出運籌學、人工智慧中最佳化理論等相關乾貨、知乎Live及行業動態：『運籌OR帷幄』大資料人工智慧時代的運籌學

單純形法由美國數學家George Bernard Dantzig在1947年擔任美國空軍司令部數學顧問時提出，旨在解決空軍軍事規劃問題，之後成為解決線性規劃問題比較通用的有效演算法。在具體介紹單純形法之前，我們需要先來認識求解線性規劃問題中的兩組重要概念：（1）可行域與最優解；（2）基變數與基可行解。

可行域與最優解

談線性規劃問題目的就是要進行求解獲取最優解，要理解最優解就不得不提可行域，可行域和最優解是線性規劃問題中最為重要的兩個概念。

線性規劃問題的

可行域

指的是滿足線性規劃問題所有約束條件（包含符號約束等各種約束）的所有點的集合，每個點叫做可行解。

最優解

是指可行域中使得目標函式取得最小值（對於最小化問題）或最大值（對於最大化問題）的某一個或某些點，相應的函式值就是最優值。

用一個比較生動的例子來解釋上述兩個概念：假設某個週末小明來到採摘園享受輕鬆時光，採摘園有三塊相鄰的採摘區，分別屬於三家農戶：老張、老李、老王，老張種植草莓，老李種植的西瓜，老王則種植了葡萄，雖然三塊採摘區相鄰，但三家農戶分別做自己的生意互不相往來。小明決定到老李家採摘西瓜，老李做生意的規定是：每位顧客只能進入園區一次，只能吃或者帶走一個西瓜，進入園區的門票是20元人民幣。

當小明進入老李的西瓜園區後，就可以來分析我們的可行域和最優解了。雖然老李家的西瓜園區與隔壁的草莓園區、葡萄園區相鄰，但是小明是不可以進入草莓園區和葡萄園區進行採摘的，因為他買的是老李家的門票，而

草莓園區

和葡萄園區不屬於老李，如果進入草莓園區或者葡萄園區，老張或者老王就要找小明或者老李討說法了。也就是說，小明只能在西瓜園區進行採摘，那麼西瓜園區就是小明的採摘範圍，這個採摘範圍就可以看成是小明活動的可行域。

那最優解對於小明來說是啥呢？小明花了20元錢進入採摘園，老李規定他只能享用一個西瓜，那麼正常情況下小明會選擇一個最大又最熟的西瓜來吃或者帶走，這樣才會使得進入園區的利益最大化，也就是我們俗話說的“對得起那20塊錢”。而西瓜園區內成百上千個西瓜都是小明可以選擇的，這些可以選擇的西瓜可以看成是小明的可行解，而最大的最熟的那個就是最優解。當然，如何從所有西瓜中找到最大最熟的那一個，就是如何求解線性規劃問題的研究範圍了。

把上述場景簡化並抽象到座標系中，就是一個簡單的線性規劃問題模型，令x、y分別代表採摘園區的長度和寬度，水果在園區的位置對應相應的座標點，假設西瓜大小與成熟度和座標點存在某種線性關係，那麼模型可以粗略表示如下圖1所示：

圖1 可行域與最優解通俗粗略解釋圖示

把上述例子繼續抽象簡化，將其設計為精確的線性規劃問題，可以抽象為如下模型：

畫出上述模型的圖示，如圖2所示，其中藍色填充區域為該模型的可行域，紅色直線表示模型的目標函式，綠色剪頭表示紅線向上移動能夠使得目標函式值增大，移動的過程中不能超出可行域（藍色區域），因此能夠使目標函式取得最大值的點，就是黑色標註點（12，6），這一點就是該模型的最優解，相應的最優值為z =x+y=12+6=18。