運籌學之線性規劃
『運籌OR帷幄』原創
作者：慘綠青年
作者： 慘綠青年 本文首發於數學放映室（https://zhuanlan.zhihu.com/c_157834986）
一個對數學各個方向感興趣的普通大學生。
敬請關注和擴散本公眾號及知乎同名專欄，會邀請全球知名學者陸續發布運籌學、人工智慧中優化理論等相關乾貨、知乎Live及行業動態：
『運籌OR帷幄』大數據人工智慧時代的運籌學--知乎專欄：http://t.cn/RlNoO3P
0.INTRODUCTION
運籌學（operational research）是一門解決一定約束條件下最優解的學科，應用現有的科學技術知識與數學手段，來解決實際生活之中的各種問題，是一門應用學科。在運籌學之下又發展出了許多的分支，如規劃論，排隊論，圖論，決策論等等。
第一講主要來討論運籌學的重要分支線性規劃。
1.Example
在高中時我們已經接觸過最簡單的線性規劃，如A,B兩件商品的利潤分別為2元與3元。同時滿足商品A個數加商品B的個數不超過8個，A的個數不小於四個,B的個數不大於五個。我們可以設商品A的個數為x商品B的個數為 y 。所以上述問題可以表述為：
目標函數： max Z=3 x1+2 x2
約束條件：
解決這類問題的方法是根據約束條件畫出可行域，一般可在可行域的頂點處取到最優解，這種方法叫做圖解法。
但上述例子中Z的值可以隨著x的增大不斷增大，若是畫出約束條件的可行域會發現可行域是無界的。出現這種情況時，往往是因為約束條件考慮不全導致。
2.Example
細心的同學可能注意到了，在傳統的線性規劃中約束條件為一系列不等式，可行域為不等式所圍成的區域。但上述定義之中約束條件的式子顯然是一個個等式並無不等式。造成它原因是什麼呢？二者其實是等價的，可以相互轉換。不等式圍成的可行域等價於約束矩陣的解空間。（證明從略，可以從矩陣秩的角度不變考慮），而用到的轉換方法稱為——鬆弛變數法。
基本思路：約束方程若為≥，則在方程左邊減去一個非負的鬆弛變數，約束方程若為≤，則在方程左邊加上一個非負的鬆弛變數。例如上例中的方程
加入鬆弛變數x3,x4,x5為：
可見此時方程被劃為了標準型，同時目標函數之中新加入的鬆弛變數的係數均為零，實際意義中可理解鬆弛變數為沒有被利用的資源，當然其利潤為零，故係數為零。
故我們可以用這個辦法將不等式可行域轉為標準形式。
注意：max到min的轉換時，只需要講z變為-z即可。
3.Definitions
數學需要更簡明與普通適用的表達形式，我們從上述例子之中抽象出下模型。定義線性規劃問題的標準形式為:
運用矩陣可以寫為
其中：
我們可以認為A矩陣是由約束條件構成的m*n維矩陣。且一般情況下m≤n，表示未知元的個數大於約束條件的個數，而且只有這種情況下才會構成多維解空間，而我們的最優解就在這多為解空間內。
我們稱b為資源向量，C為價值向量，X為決策價值變數向量。（聯繫實例可理解名稱的由來）
4.definitions
可行解：滿足約束條件的解稱為可行解，使目標函數達到最大（小）值的解稱為最優解。
基：約束矩陣A為m*n維矩陣，其rank（A）=m（在線性代數中，一個矩陣A的秩是A的線性獨立的向量的極大數目，記為rank(A)），設B為A之中的m*m階非奇異的子矩陣。那麼稱B為線性規劃問題的一個基。（顯然rank（B）=m，非奇異意思是：≠0），
基可行解：由矩陣知識可知，一個基（滿秩矩陣）一定會求出一個相應的基解。若一個解既為基解又為可行解，則稱為基可行解。可知滿足非負條件的基解均為基可行解。
5.Geometric interpretation
幾何看來有時候要領先於分析，但事實上，幾何的先行於分析，只不過像一個僕人走在主人的前面一樣，是為主人開路的。——西爾維斯特
在使用圖解法時，我們理所當然地認為最優解是在可行域的頂點之上，但其中的原因恐怕大部分人沒有思考過，更沒有去證明過。這一節更像是從幾何的角度給出圖解法的原理（其實更像是代數的角度），同時得出一些有趣的結論。首先我們需要明確這麼幾個定義：
definition 1.5.1
凸集（convex set）： 設K為n維歐式空間的一個點集，若任意兩點的連線上的一點X∈K；則稱K為凸集。
凸集的概念很好理解，直觀地可以理解為集合沒有凹進去的地方，像下圖二有凹進去的地方，所以兩點的連線之上存在不屬於K上的點，故不是凸集。
且凸集的交集仍然為凸集。
另一個注意的地方就是前提必須是在歐氏空間內。（歐氏空間可以不嚴謹地解釋為平坦的空間。）
一個例子
definition 1.5.2
凸組合：設有向量,i=1,2,...,n,如有實數，且
,則為的凸組合。當時，稱為嚴格凸組合。
definition 1.5.3
凸集上無法用不同兩點的線性表示的點為頂點。
這兩個定義都比較好理解，不做多餘解釋。有了這些定義與知識，我們可以試著去推出一些定理。
Theorem 1.5.1
若線性規劃存在可行域，則可行域為凸集。
（證明只寫思路與關鍵步驟，有興趣的讀者可以試著寫出完整的證明）
證明：根據的凸集的定義，每兩點連線上的點都在集合內，我們只需證明這一點即可。即證明任意，滿足,把代入可行域的方程之中，即說明連線任一點滿足方程，故可行域一定為凸集。
引理1：可行解X為基可行解的充要條件為X的正分量對應的係數矩陣非奇異。（係數列向量線性獨立）
Theorem 1.5.2
線性規劃問題的基可行解X對應於可行域D的頂點。
證明：凸集的頂點不可以用兩點的線性組合表示，故能用兩線性表示的都不是頂點，若基可行解對應頂點，則基可行解不可以用兩點的線性表示，出於這個思路我們可以用反證法證明：①若X不是頂點，則它一定不是基可行解。不失一般性我們還要證明②若X不是基可行解，則X一定不是頂點。
先證明①，因為X不是頂點，故可以找兩點X1，X2，使X可以被X1與X2線性表示。其中X1=
。
設X為基可行解，且X對應一基矩陣A（m*m維），且|A|≠0，當j＞m時,故；j
再證明②，若X不是基可行解，則對於對應的係數矩陣|A|=0,即對應的係數列向量P1，P2，P3...Pm線性相關，即存在一組線性相關的數：
，又在基可行解之中有
,用乘以
的每一項，然後再分別加上或減去
。
可得。
分別取X1=,j=1,2...m
X2=,j=1,2,..,m
故X=1/2*X1+1/2*X2，即X為X1與X2的中點。說明在X不是基可行解時，X不對應中點。
故可說明基可行解X對應可行域D的頂點。
引理2：有界凸集K之中，任何一點可以表示為頂點的凸組合。
Theorem 1.5.3
若可行域有界，線性規劃問題的目標函數一定可以在可行域的頂點上達到最優。
證明：設為可行域的幾個頂點，設有一點不為頂點，且目標函數在該點達到最優。則由引理2可知，可以由頂點線性表出，即
故，設頂點之中有最大值,在上式之中用代替每一個X，有
所以得出結論
，所以最大值在頂點上，定理得證。
6.summary
本節介紹了線性規劃的概念與標準形式，討論了加鬆弛變數將不等式劃為標準形式的辦法。最後討論了凸集的性質，得出了幾條結論：線性規劃的可行解構成的集合為凸集或無界域。基可行解對應凸集的頂點，且線性規劃可在凸集的頂點上取到最優解。雖然頂點的個數有限，我們可以用暴力破解法一一求得，再對其進行排序從而找到最優解。但在頂點數目個數較多的時候，這種辦法是不太有效的，如何有效地找到最優解，請點擊這裡運籌學S01E02——單純形法
在此感謝『運籌OR帷幄』審稿人對本文提出了寶貴的意見。
『運籌OR帷幄』審稿人 孫卓，大連海事大學物流系教授，博士生導師，從事交通物流網路優化、計算機模擬等研究。曾獲由阿里巴巴、香港科技大學、美國INFORMS協會舉辦的菜鳥網路全球演算法大賽季軍。開源空間建模框架MicroCity。
轉載請聯繫本公眾號獲得授權
TAG:運籌OR帷幄 |