本章涉及知識(shí)點(diǎn)
1、線性規(guī)劃的定義
2、可行區(qū)域、目標(biāo)函數(shù)、可行解和最優(yōu)解
3、轉(zhuǎn)線性規(guī)劃為標(biāo)準(zhǔn)型
4、轉(zhuǎn)線性規(guī)劃為松弛型
5、單純形算法的思想和例子
6、避免退化—Bland規(guī)則
7、廣義單純形算法的步驟
8、約束條件為負(fù)數(shù)情況下存在的問(wèn)題
9、構(gòu)造輔助線性規(guī)劃函數(shù)
10、從輔助線性規(guī)劃函數(shù)還原目標(biāo)函數(shù)
11、輔助線性函數(shù)的求解步驟
12、完整的單純形算法步驟
13、python編程實(shí)現(xiàn)單純形算法
14、實(shí)驗(yàn)驗(yàn)證單純形算法處理不同線性規(guī)劃問(wèn)題
一、線性規(guī)劃的定義
我們來(lái)看一個(gè)實(shí)際問(wèn)題：
假設(shè)你是一個(gè)單位的采購(gòu)經(jīng)理，你有2000元經(jīng)費(fèi)，需要采購(gòu)單價(jià)為50元的若干桌子和單價(jià)為20元的若干椅子，你希望桌椅的總數(shù)盡可能的多，但要求椅子數(shù)量不少于桌子數(shù)量，且不多于桌子數(shù)量的1.5倍，那你需要怎樣的一個(gè)采購(gòu)方案呢？
于是我們可以假設(shè)桌子數(shù)量和椅子數(shù)量為x1和x2，為此我們的目標(biāo)函數(shù)為
而約束條件可以寫(xiě)為
上述既包含目標(biāo)函數(shù)，又含有約束條件，就可以抽象為一個(gè)線性規(guī)劃問(wèn)題，即在有限的資源和若干競(jìng)爭(zhēng)約束下，求某個(gè)目標(biāo)函數(shù)的最大化或最小化的最優(yōu)策略
二、可行區(qū)域、目標(biāo)函數(shù)、可行解和最優(yōu)解
我們由上述案例來(lái)看，因?yàn)槭侵挥袃蓚€(gè)變量屬于二維空間，我們?cè)诘芽栕鴺?biāo)系中畫(huà)出約束條件和目標(biāo)函數(shù)
從二維空間中我們可以看出，紫色區(qū)域就是滿足所有約束條件的安全區(qū)域，包括最優(yōu)解也必須在其中，我們把這個(gè)區(qū)域叫做可行域。紅色函數(shù)即是目標(biāo)函數(shù)，而要求目標(biāo)函數(shù)達(dá)到最大值或最小值，就是平行的移動(dòng)目標(biāo)函數(shù)，讓目標(biāo)函數(shù)在可行域上達(dá)到截距最大(最小)。圖中的A、B、C三個(gè)點(diǎn)都屬于目標(biāo)函數(shù)與可行域的交點(diǎn)，我們稱之為可行解，而使得目標(biāo)函數(shù)達(dá)到最大(最小)的可行解被我們定義為最優(yōu)解，其對(duì)應(yīng)于圖中的A點(diǎn)
至此我們可以總結(jié)出線性規(guī)劃的幾個(gè)特征
（1）線性規(guī)劃的可行域總是一個(gè)凸集
（2）目標(biāo)函數(shù)的可行解(包括最優(yōu)解)一定出現(xiàn)在可行域的一個(gè)頂點(diǎn)上
（3）目標(biāo)函數(shù)可以是直線(二維空間)或者超平面(高維空間)的線性變化，所以它的局部最優(yōu)解實(shí)際上就是全局最優(yōu)解
三、轉(zhuǎn)線性規(guī)劃為標(biāo)準(zhǔn)型
為了統(tǒng)一用一種數(shù)學(xué)模型來(lái)描述任意線性規(guī)劃問(wèn)題，我們定義了兩種規(guī)范形式：標(biāo)準(zhǔn)和松弛
線性規(guī)劃的標(biāo)準(zhǔn)形式為
其中A，x和b都是向量形式，我們可以將任意一個(gè)線性規(guī)劃轉(zhuǎn)化為標(biāo)準(zhǔn)形式
（1）如果目標(biāo)函數(shù)是求max，那么乘以-1使目標(biāo)函數(shù)轉(zhuǎn)化為求min
（2）如果約束條件有>=約束，同理乘以-1將約束變?yōu)?lt;=
我們將開(kāi)頭的案例轉(zhuǎn)化為標(biāo)準(zhǔn)形式如下：
可以看到，線性規(guī)劃的標(biāo)準(zhǔn)型，是滿足不等式約束的一個(gè)目標(biāo)線性函數(shù)最小化(最大化)過(guò)程
四、轉(zhuǎn)線性規(guī)劃為松弛型
在求解線性規(guī)劃算法中，我們更喜歡用等式約束來(lái)等價(jià)描述不等式約束，為此我們引入松弛形式
為了將約束條件都變?yōu)榈仁?，我們需要引入松弛變量進(jìn)入x向量，下面我們將開(kāi)頭案例轉(zhuǎn)化為松弛形式如下：
可以看到松弛變量的意義，就是度量了等式約束與原不等式約束之間的松弛或差別，我們的單純形算法都是建立在線性規(guī)劃的松弛形式上
五、單純形算法的思想和例子
我們以開(kāi)頭案例，來(lái)一步步介紹單純形算法的思想
我們將松弛變量單獨(dú)提到等式左邊，將松弛形式等價(jià)的變?yōu)?/p>
在上述的等式中，我們將等式左邊的部分稱之為基本變量，而右邊部分稱之為非基本變量
現(xiàn)在我們考慮這個(gè)狀態(tài)下的基本解，其計(jì)算方式為：將等式右邊的所有非基本變量設(shè)為0，然后單獨(dú)計(jì)算左邊的基本變量值，為此我們得到第一個(gè)基本解為
而這組基本解沒(méi)有違反任意約束條件，即該基本解就是一個(gè)可行解，也就是可行區(qū)域的一個(gè)頂點(diǎn)。這里需要說(shuō)明一點(diǎn)，基本解完全存在不是可行解的情況，這種情況需要引入輔助線性函數(shù)做等效變化，我們放在第八點(diǎn)來(lái)說(shuō)明。
下面我們選出當(dāng)前目標(biāo)函數(shù)中第一個(gè)系數(shù)為負(fù)數(shù)的非基本變量，需要將其變化為基本變量，為此我們選出x1，我們也將這個(gè)非基本變量稱為替入變量
緊接著我們需要在約束條件里找到一個(gè)對(duì)當(dāng)前替入變量x1最嚴(yán)格的一個(gè)約束，我們計(jì)算出第一個(gè)約束里x1可以增大到0，第二個(gè)約束里x1可以增大到無(wú)窮，第三個(gè)約束里x1可以增大到400，因此第一個(gè)約束條件對(duì)x1更為嚴(yán)格，我們選擇第一個(gè)約束，而這個(gè)約束里的基本變量我們稱為替出變量，得到x1 = x2 - x3，將其帶入當(dāng)前的約束集合變化得到
上述的過(guò)程我們定義為一個(gè)轉(zhuǎn)動(dòng)(pivot)，而一次轉(zhuǎn)動(dòng)的目的，就是在當(dāng)前的目標(biāo)函數(shù)里選擇一個(gè)替入變量，然后在約束集合里選擇一個(gè)約束（替換變量），最后替換這組替入變量和替出變量的角色位置，其本質(zhì)就是用替出變量來(lái)表示替入變量的代數(shù)式，至于選擇替入變量和替處變量的規(guī)則，我們遵循Bland規(guī)則（單獨(dú)在第六點(diǎn)講解）
經(jīng)過(guò)第一次旋轉(zhuǎn)，此時(shí)的基本解變?yōu)?/p>
經(jīng)過(guò)第一次旋轉(zhuǎn)，此時(shí)的目標(biāo)函數(shù)的值變?yōu)?
接下來(lái)我們需要不斷的執(zhí)行轉(zhuǎn)動(dòng)過(guò)程，直到目標(biāo)函數(shù)無(wú)法改進(jìn)，即目標(biāo)函數(shù)的系數(shù)全部為非負(fù)數(shù)
由于目標(biāo)函數(shù)里任然存在系數(shù)為負(fù)數(shù)的項(xiàng)，我們繼續(xù)執(zhí)行第二次轉(zhuǎn)動(dòng)，選擇替入/替出的算法和第一次轉(zhuǎn)動(dòng)一樣，我們從當(dāng)前的目標(biāo)函數(shù)里選擇x2為替入變量，在約束集合里因?yàn)榈谝粋€(gè)和第二個(gè)約束都可以讓x2增大到無(wú)窮，而第三個(gè)約束可以讓x2增大到2000/70，為此我們選擇第三個(gè)約束條件的x5為替出變量，得到x2 = 2000/70 + 5/7*x3 - 1/70 * x5，將其帶入當(dāng)前的約束集合變化得到
經(jīng)過(guò)第二次旋轉(zhuǎn)，此時(shí)的基本解變?yōu)?/p>
經(jīng)過(guò)第二次旋轉(zhuǎn)，此時(shí)的目標(biāo)函數(shù)的值變?yōu)?4000/70
由于目標(biāo)函數(shù)里任然存在系數(shù)為負(fù)數(shù)的項(xiàng)，我們繼續(xù)執(zhí)行第三次轉(zhuǎn)動(dòng)，同理，我們選擇x3為替入變量，選擇第二個(gè)約束里的x4作為替出變量，得到x3 = 1000/80*x4-14/16*x4-1/160*x5，將其帶入當(dāng)前的約束集合變化得到
經(jīng)過(guò)第三次旋轉(zhuǎn)，此時(shí)的基本解變?yōu)?/p>
經(jīng)過(guò)第三次旋轉(zhuǎn)，此時(shí)的目標(biāo)函數(shù)的值變?yōu)?35000/560=-62.5
而此時(shí)此刻，我們的目標(biāo)函數(shù)里已經(jīng)沒(méi)有系數(shù)為負(fù)數(shù)的項(xiàng)了，說(shuō)明我們無(wú)法在繼續(xù)增大(減小)目標(biāo)函數(shù)，算法達(dá)到了收斂，停止轉(zhuǎn)動(dòng)，此時(shí)求出的基本解就是線性規(guī)劃的最優(yōu)解！這個(gè)解也解釋了在案例里，最優(yōu)的方案是購(gòu)買25張桌子，37張椅子（椅子數(shù)量為整數(shù)），總的購(gòu)買了25 + 37 = 62張桌椅，總花費(fèi)了25*50+37*20=1990元
六、避免退化—Bland規(guī)則
我們從案例出發(fā)一步步介紹了單純形算法的思想，經(jīng)過(guò)一系列的旋轉(zhuǎn)，最終得到了最優(yōu)解和目標(biāo)值，其中在旋轉(zhuǎn)的操作里，我們涉及到替入變量和替出變量的選擇，這一步至關(guān)重要，因?yàn)樗鼘Q定目標(biāo)函數(shù)的變化和是否需要繼續(xù)旋轉(zhuǎn)，如果選擇不當(dāng)，我們的算法非常有可能進(jìn)入循環(huán)旋轉(zhuǎn)，并且不會(huì)停止，我們把這個(gè)現(xiàn)象稱之為退化
可以說(shuō)退化是導(dǎo)致單純形算法不會(huì)收斂的唯一原因，那么如何避免退化呢？在這里我們使用Bland規(guī)則來(lái)選擇替入和替出變量
Bland規(guī)則定義：在執(zhí)行換基操作（即選擇替入和替出變量并交換二者角色）的時(shí)候，我們總是選擇下標(biāo)最小的非基本變量去滿足左側(cè)的基本變量
替入變量選擇：在目標(biāo)函數(shù)中，選擇系數(shù)為負(fù)數(shù)的第一個(gè)非基本變量
替出變量選擇：在約束集合中，選擇對(duì)當(dāng)前替入變量約束最緊的第一個(gè)基本變量
七、廣義單純形算法的步驟
下面我們總結(jié)一下廣義上單純形算法的主要步驟
（1）從原線性規(guī)劃問(wèn)題中找到第一個(gè)基本解（必須是可行解）
（2）根據(jù)Bland規(guī)則，執(zhí)行旋轉(zhuǎn)操作
（3）重復(fù)第2步直到算法收斂
其中第二步和第三步都是圍繞著旋轉(zhuǎn)操作執(zhí)行的，而我們需要重視的是第一步，因?yàn)閺膸缀蔚慕嵌壬峡?，我們知道線性規(guī)劃的可行解都是出現(xiàn)在可行域的頂點(diǎn)上，而單純形算法的每一次旋轉(zhuǎn)，都可以得到一個(gè)可行解，說(shuō)明每一次的旋轉(zhuǎn)其實(shí)是從可行域的一個(gè)頂點(diǎn)游走到另一個(gè)頂點(diǎn)，所以算法的第一步，我們必須讓單純形算法落在可行域的一個(gè)頂點(diǎn)上！也就是說(shuō)需要初始化的基本解，必須是可行解！
案例里第一次我們的基本解就是可行解（因?yàn)闆](méi)有違反任何約束），但是有一些線性規(guī)劃問(wèn)題中我們的基本解，不一定就是可行解
八、基本解不是可行解的情況
下面我們來(lái)看另外一個(gè)案例2
要解這個(gè)線性規(guī)劃，我們按照單純形算法的思想，先轉(zhuǎn)化為松弛型
接下來(lái)我們進(jìn)行單純形算法的第一步，找到一個(gè)基本可行解，而此時(shí)的基本解為
注意觀察，此時(shí)的基本解不滿足原線性規(guī)劃的第二個(gè)約束條件，因?yàn)?+0=0>=1是不成立的！所以現(xiàn)在的基本解根本不在可行域的頂點(diǎn)上，不是線性規(guī)劃的可行解！
因此此時(shí)不能進(jìn)入單純形算法來(lái)求解，我們需要思考為什么會(huì)產(chǎn)生基本解不是可行解的情況
注意看到上述案例的第二個(gè)約束條件存在負(fù)數(shù)約束，這也是導(dǎo)致我們的第一個(gè)基本解不滿足該約束的問(wèn)題所在，因此我們可以總結(jié)出單純形算法的第一步需要分類討論
（1）如果約束集合里不存在負(fù)數(shù)約束，說(shuō)明初始化的基本解就是可行解，可以順利執(zhí)行單純形算法
（2）如果約束集合里存在負(fù)數(shù)約束，說(shuō)明初始化的基本解并不是可行解，需要進(jìn)行原線性規(guī)劃問(wèn)題的等效變化來(lái)找到一個(gè)可行解，再執(zhí)行單純形算法
當(dāng)我們要求解的線性規(guī)劃出現(xiàn)了上述第二種情況，就需要引入構(gòu)造輔助線性規(guī)劃函數(shù)來(lái)進(jìn)行原線性規(guī)劃的變形
九、構(gòu)造輔助線性規(guī)劃函數(shù)
我們以案例2，來(lái)一步步介紹輔助線性規(guī)劃函數(shù)的意義
我們?cè)诎咐?的標(biāo)準(zhǔn)形式上，繼續(xù)構(gòu)造一個(gè)新的線性規(guī)劃函數(shù)
我們引入新的變量x0，且x0的系數(shù)是-1(用于第一次旋轉(zhuǎn)的時(shí)候?qū)⑺械呢?fù)數(shù)約束系數(shù)變?yōu)檎龜?shù))，顯然當(dāng)x0=0的時(shí)候，說(shuō)明原線性規(guī)劃組有解。我們寫(xiě)出其松弛形式為
同理，我們將右側(cè)非基本變量視為0，計(jì)算出左側(cè)的基本變量，則第一個(gè)基本解為
顯然這個(gè)解違反了原線性規(guī)劃的第二個(gè)不等式約束，為此我們對(duì)引入的新變量x0做第一個(gè)旋轉(zhuǎn)操作：
將非基本變量x0作為替入變量，并且在約束集合里選一個(gè)約束系數(shù)最小的那一行的基本變量作為替出變量，進(jìn)行旋轉(zhuǎn)操作
顯然當(dāng)前約束集合里約束系數(shù)min(2,-1)=-1，為此我們選擇x4作為替出變量，得到x0=1-x1-x2+x4，將其帶入當(dāng)前的約束集合變化得到
經(jīng)過(guò)第一次旋轉(zhuǎn)，此時(shí)的基本解變?yōu)?/p>
經(jīng)過(guò)第一次旋轉(zhuǎn)，此時(shí)的目標(biāo)函數(shù)的值變?yōu)?
從第一次旋轉(zhuǎn)我們可以看到，由于x0的系數(shù)為-1，經(jīng)過(guò)一次旋轉(zhuǎn)，為此我們已經(jīng)將原約束集合里所有的負(fù)數(shù)約束變?yōu)榱苏龜?shù)約束，這也是開(kāi)頭我們引入x0的原因！
接下來(lái)我們需要求解這個(gè)輔助線性規(guī)劃，我們使用單純形算法求解即可，每次旋轉(zhuǎn)選取的替入/替出變量規(guī)則一樣，如果能解出輔助線性規(guī)劃的目標(biāo)函數(shù)最優(yōu)值x0=0，那么就說(shuō)明原線性規(guī)劃有解。我們從目標(biāo)函數(shù)里選擇x1為替入變量(系數(shù)為負(fù)數(shù)的第一項(xiàng))，選擇第二個(gè)約束的x0作為替出變量，得到x1=1-x2+x4-x0，將其帶入當(dāng)前的約束集合變化得到
經(jīng)過(guò)第二次旋轉(zhuǎn)，此時(shí)的基本解變?yōu)?/p>
可以看到此時(shí)的基本解已經(jīng)同時(shí)滿足了原線性規(guī)劃的所有約束條件，即此時(shí)的基本解在可行域的頂點(diǎn)上，是一個(gè)基本可行解！
此時(shí)的目標(biāo)函數(shù)的值變?yōu)?，說(shuō)明了原線性規(guī)劃是有解的，并且我們已經(jīng)成功的找到了一個(gè)基本可行解(頂點(diǎn))
十、從輔助線性規(guī)劃函數(shù)還原目標(biāo)函數(shù)
經(jīng)過(guò)輔助線性規(guī)劃的求解，我們已經(jīng)成功的找到一個(gè)基本可行解，接下來(lái)，我們需要恢復(fù)原線性規(guī)劃的目標(biāo)函數(shù)，等效還原的方法為
等效還原目標(biāo)函數(shù)：用此時(shí)的基本變量替換原目標(biāo)函數(shù)中的基本變量
原目標(biāo)函數(shù)為
可以看到x1和x2為原來(lái)的基本變量，而此時(shí)的基本變量為x1和x3，我們代替x1即可
由于x0=0，我們將其去掉，最終我們得到了經(jīng)過(guò)輔助線性函數(shù)等效變化后的一個(gè)新的線性規(guī)劃
可以看到這個(gè)線性規(guī)劃的基本解就是可行解，我們順利完成了單純形算法的第一步：從原線性規(guī)劃問(wèn)題中找到第一個(gè)基本可行解，那么我們就可以繼續(xù)用單純形算法的第二三步來(lái)順利求解之！
十一、輔助線性函數(shù)的求解步驟
下面我們總結(jié)一下輔助線性函數(shù)的求解步驟
（1）引入x0的列變量，且系數(shù)為-1，構(gòu)造輔助線性規(guī)劃函數(shù)
（2）輔助線性規(guī)劃的目標(biāo)函數(shù)為x0
（3）選擇x0作為替入變量，同時(shí)選擇當(dāng)前約束集合中約束系數(shù)最小的那一行的基本變量作為替出變量，進(jìn)行第一次旋轉(zhuǎn)操作，將所有約束系數(shù)變?yōu)榉秦?fù)數(shù)
（4）使用單純形算法求解當(dāng)前輔助線性規(guī)劃函數(shù)，如果解出輔助線性函數(shù)的目標(biāo)函數(shù)的最優(yōu)解為0，證明原線性規(guī)劃函數(shù)有解，否則證明原線性規(guī)劃函數(shù)無(wú)解
（5）如果求解后x0仍然是基本變量，則在x0作為基本變量的那一行約束條件里，將x0作為替出變量，同時(shí)在此時(shí)的目標(biāo)函數(shù)里找到第一個(gè)系數(shù)不為0的變量作為替入變量，進(jìn)行旋轉(zhuǎn)操作，將x0變?yōu)榉腔咀兞?/b>
（6）經(jīng)過(guò)上述第一次旋轉(zhuǎn)和求解輔助線性函數(shù)，得到了第一組基本可行解，則等效的還原原問(wèn)題的目標(biāo)函數(shù)（用當(dāng)前的基本變量替換原目標(biāo)函數(shù)中的基本變量），并且去掉x0的那一列
（7）執(zhí)行單純形算法的第二步和第三步
十二、完整的單純形算法步驟
考慮到存在求解輔助線性函數(shù)，我們也總結(jié)出單純形算法的完整步驟
（1）將線性規(guī)劃的標(biāo)準(zhǔn)矩陣轉(zhuǎn)化為松弛矩陣
（2）如果約束系數(shù)矩陣?yán)锊淮嬖谪?fù)數(shù)，找到基本可行解，轉(zhuǎn)到步驟(5)
（3）如果約束系數(shù)矩陣?yán)锎嬖谪?fù)數(shù)，沒(méi)有找到基本可行解，則構(gòu)造輔助線性規(guī)劃函數(shù)，轉(zhuǎn)到步驟(4)
（4）求解輔助線性規(guī)劃函數(shù)，找到基本可行解，還原原目標(biāo)函數(shù)，轉(zhuǎn)到步驟(5)
（5）根據(jù)Bland規(guī)則，執(zhí)行矩陣旋轉(zhuǎn)操作
（6）重復(fù)步驟(5)直到算法收斂
十三、python編程實(shí)現(xiàn)單純形算法
下面我們用python編程實(shí)現(xiàn)單純形算法的各個(gè)求解步驟
十四、實(shí)驗(yàn)驗(yàn)證單純形算法處理不同線性規(guī)劃問(wèn)題
最后我們測(cè)試幾個(gè)線性規(guī)劃的問(wèn)題，來(lái)測(cè)試算法
下面我們來(lái)算兩個(gè)四維空間的線性規(guī)劃
可以看到單純形算法可以在多項(xiàng)式時(shí)間內(nèi)，計(jì)算出線性規(guī)劃的最優(yōu)解
案例代碼見(jiàn)：線性規(guī)劃-單純形算法
