【天津大學】《運籌學》（精品課） P4 - 4. 單純形法 教學錄像（1）

大家好,我們在上一節中學習了線性規劃的模型與圖解法, 我們已經知道線性規劃要解決的是在有限的資源條件下如何合理的規劃, 以達到效益最優的問題。 線性規劃的模型是由決策變量、目標函數和約束條件三要素組成, 對於兩個變量的線性規劃模型可以用圖解法求解, 圖解法雖然只能解兩個變量的問題, 但是它可以直觀的得到線性規劃的一些性質, 比如最優解如果存在的話, 必能在可行域的邊界腳點處獲得。 我們接下來就來介紹線性規劃的一般方法, 單純刑法 單純刑法是求解線性規劃的主要算法, 1947年由美國斯坦福大學教授丹傑格提出, 儘管在其後的幾十年中又有一些其他算法問世, 但是單純刑法, 以其簡單實用的特色, 始終保持着主要的算法地位。 早在二戰期間, 在美國空軍服役的科學家丹傑格就提出了單純刑方法, 這個方法當時曾經保密, 直到戰後的1947年, 當丹傑格離開軍隊, 轉任斯坦福大學教授之後, 才公開發表。 丹傑格不僅提出了單純刑法, 而且在線性規劃相關研究領域, 做出了一系列傑出的貢獻, 他被人們譽爲線性規劃之父。 以他的名字命名的丹傑格獎, 成爲運籌學界的最高獎項之一。 接下來我們就來介紹單純刑法, 我們將依次介紹單純刑法的預備知識, 原理步驟和具體實現。 首先來介紹單純刑法的預備知識, 我們已經知道, 由實際問題建立的線性規劃模型, 是形式各異的, 那麼在用單純刑法求解之前, 需要先將模型化爲統一的形式, 這個形式就稱爲標準型, 它的具體形式如下, 我們看到線性規劃的標準型, 仍然是一個線性規劃, 只是它的形式規定爲, 目標是極大型, 極大化z等於cx, 約束的資源約束部分是等式約束, ax等於b, 約束的變量都是要求是非負變量, 在標準型當中的係數矩陣a, 是一個mxn的矩陣, 其中m是約束的個數, 而n是變量的個數, 由線性方程組的知識可知, 我們一般可以設m小於等於n, 也就是方程的個數小於等於變量的個數, 我們在標準型中, 假設a的質是m, 也就是說是滿質的, 因爲a的質最大就是m, 這個要求的直觀解釋就是, 在約束中沒有多餘的約束, 標準型中還規定右端向, 也就是b, 我們在前面已經說過它稱爲資源限制向量, 我們在標準型中規定b, 全部都是非負的, 也就是b大於等於0, 總之標準型的特徵就是極大型等式約束和非負約束, 對於模型建立後不符合標準型的情形, 我們都可以把它先化爲標準形式, 那麼非標準如何化爲標準形式呢? 既然標準型的主要特徵是極大型等式約束和非負約束, 那麼非標準的情形也就是相應的, 目標可能是極小型, 約束可能不是等式約束, 變量可能不都是非負變量, 對於這三種形式, 我們一次說明一下它們怎樣化爲標準型, 先來說目標如果是極小型, 如何化爲極大型呢? 我們知道求一個函數的極小點的問題, 等價於求這個函數的負函數的極大點問題, 如圖可知,求一個曲線fx的極小值點和求它的負函數, 就是負fx的曲線的極大值點是同解的, 因此我們在把極小型化爲極大型的時候, 只需要把目標函數添加負號, 同時把極小號改爲極大號就可以了, 也就是極小型z等於cx, 通過把目標函數加負號, 可以化爲極大化z等於負cx, 比如有這樣一個目標函數是極小化, 它的目標表達式負x1加2x2, 我們要是化爲標準型, 也就是極大型, 就可以把目標函數的表達式加負號, 同時把極小號改爲極大號, 我們把極小型化爲極大型求解之後, 解是同解, 但是最優質相應的最優質, 那個極大型的最優質和你原來要解的這個問題, 原問題的極小型的最優質之間是差一個負號的, 最後在還原的時候要注意, 這是第一種情況, 第二種非標準化標準的情況是, 約束式不等式約束, 這個怎樣化爲等式約束呢? 這是很常見的一種情況, 我們以上一節中立1.1的約束爲例加以說明, 我們在立1.1中, 它的約束部分有資源約束和非賦約束, 資源約束是煤電油三種資源的限量約束, 我們這裏顯示的是其中煤的約束, 煤的約束表達式9X1加4X2小於等於360, 這是一個不等式, 不等式如何化爲等式呢? 直觀上, 一個不等式之所以不等, 是由於不等號的左右兩端有一個差額, 如果我們在不等號的左端, 以這個不等式爲例, 在不等號的左端添加上這個差額, 左右兩端的差額, 那麼這個不等式不就化爲等式了嗎? 這個差額我們可以把它稱爲鬆弛量, 而這個鬆弛量呢, 實際上它也是個變量, 我們把它記爲X3, 在不等式的左邊加上這個X3, 那麼這個不等式就化爲了等式, 這個X3呢, 就是把不等式化爲等式添加的一個鬆弛量, 由於它也是個變量, 我們把它稱作鬆弛變量, 這個鬆弛變量它有沒有實際意義呢? 在這個例子中很明顯, 因爲這個約束, 它的右端360是煤的限量, 左端9X1加4X2是爲了生產甲乙產品, 而需要消耗的煤的實際用量, 那麼左右兩端的差額, 也就是這個X3, 它的含義就是在實際生產之後, 煤的還剩餘量, 因此這裏的鬆弛變量X3的含義, 就是煤資源的剩餘, 一般來說, 在把不等式約束化爲等式約束的時候, 如果是小於等於的不等式約束, 比如以這個煤電油的這個粒子的資源爲例, 那麼這裏的鬆弛變量的含義, 就是資源的剩餘, 好, 我們現在呢, 把整個煤電油的粒子, 也就是粒1.1的約束, 把它都化成標準型, 根據剛纔的分析可知, 只需要在不等式添加鬆弛變量, 就可以把不等式化爲等式了, 那麼這道題需要添加幾個鬆弛變量呢? 我們看到它一共是三個不等式, 我們說的是資源約束部分, 煤電油, 每個不等式都需要添加一個鬆弛變量, 我們依次把它們可以記作X345, 則這個約束呢, 就可以化爲等式約束了, 下面是化爲等式約束之後的表達式, 我們看到在這個表達式當中, 煤的約束是9X1加4X2, 加上了鬆弛變量X3之後等於360, 第二個約束是電的約束4X1加5X2, 也是加上它的鬆弛變量X4之後化爲了等於200, 同樣第三個約束, 添加上它的鬆弛變量X5之後也化爲了等式, 我們注意這裏頭變量寫的形式是每個變量佔一列, 這樣比較整齊和可以便於看出細數矩陣, 那麼我們這個添加的這些鬆弛變量, 它們都是非負變量, 所以我們在最後的非負約束中也要把這些鬆弛變量包括進去, 那麼這些鬆弛變量X345, 它們的實際意義和剛纔分析煤的約束的是一樣的, 分別表示資源煤電油的資源剩餘, 我們再來看一下化爲標準型之後的約束, 很明顯看到鬆弛變量的細數矩陣, 也就是由X3,X4和X5這三個變量在整個約束中的細數部分組成的這一塊, 這個矩陣恰好是一個單位陣, 也就是主對角線爲1, 其餘都爲0的方陣, 那麼我們剛纔通過添加鬆弛變量, 把約束化爲了標準型, 我們剛纔並沒有涉及這個問題的目標, 現在請大家想一下鬆弛變量, 它在約束中增加了鬆弛變量, 原來兩個變量的問題已經變成了五個變量的問題, 那麼原來的那個目標要不要跟着變呢? 要不要跟着增加X3,X4,X5呢? 也就是我們鬆弛變量在目標中的細數是什麼呢? 我們不難分析, 由於鬆弛變量的實際意義是資源剩餘, 既然是資源剩餘, 他們就沒有參加創造價值的勞動, 創造價值的過程, 因此我們這道題, 它的目標是總收入最大化, 這些鬆弛變量資源剩餘沒有參加總收入的過程, 因此他們對總收入的單位貢獻, 也就是價格係數應該是零, 最後我們再來考慮一下, 這個標準型的模型已經化爲五個變量的問題了, 它和原來原問題是兩個變量的問題, 原來的問題和標準型模型之間, 它的解之間有什麼關係呢? 我們用單純型法求解, 就是求解標準型的模型, 通過單純型法可以求得這個標準型的最優解, 以這道題爲例, 它求出來是五個分量, 五個決策變量, 那麼這五個決策變量, 它其中的前兩個分量, 也就是X1和X2, 它是不是原來問題的最優解呢? 我們不難經過分析可以得到, 因爲這個X1和X2, 它是首先滿足標準型的約束, 我們說的是最優解中X1和X2的這兩個分量的值, 首先它是可行的, 它既然是滿足標準型的約束, 那麼不難看到它也滿足我們原來問題的約束, 因此可行, 另外這個標準型的目標和原來的模型的目標是一樣的, 剛纔已經說過鬆弛變量的目標係數是零, 所以這個的最優值也就是原來問題的最優值, 因此我們通過求解標準型得到的最優解, 它其中的前兩個變量, 以這道題爲例, 它的前兩個變量就是原來問題的變量, 就是原來問題的最優解, 綜上所述, 我們不等式約束化爲等式約束的總結呢, 就是通過增加鬆弛變量來把不等式化爲等式, 我們既鬆弛變量組成的向量爲xs, 則對於小於等於不等式這樣的約束化爲標準型之後的形式是在原來約束表達式的基礎之上, 資源部分加上Ixs, 那麼在非復約束呢, 要加上xs, 對於約束式大於等於型的不等式, 我們需要每個左端的每個約束, 約束的左端每個式子要減去鬆弛變量才能化爲等式, 化爲等式之後的形式呢, 如這個表達式所示, 好, 那麼在非標準化標準的第三種情形, 它是說有的模型中有某變量比如xk沒有非復要求, 這樣的變量稱爲自由變量, 這樣的變量怎麼化爲標準型要求的都用非復變量表示呢? 這個時候我們可以令這個自由變量比如xk, 令它用兩個非復變量之差來表示, 比如令xk等於xk一平減去xk兩平, 那麼xk一平和k兩平都是非復變量, 而它們的差既可以是正也可以是負是自由變量, 例如現在有一個現行規劃的模型, 我們大家看到這個模型的目標和資源約束都已經符合標準形式, 但是它的變量部分, 最後的非復約束部分我們看到只寫了x1一個變量, 非復要求中沒有出現x2, 這就說明x2是自由變量, 這個時候我們要化爲標準型呢, 就可以把x2這個自由變量用兩個非復變量之差來表示, 如下面這個表達式所示, 我們在非復約束裏添加了x21平和x2兩平, 拿它的之差來表示了原來模型中x2的位置, 好, 我們的標準型及其非標準如何化爲標準已經介紹完了, 接下來我們再來介紹一組預備知識, 這組預備知識是一組基本概念, 它是單純型法的重要基礎, 首先來說一下第一組概念叫可行解與最優解, 可行解的概念實際上在圖解法中已經說過, 已經知道它就是滿足全體約束的解, 一般用x表示可行就是滿足全體約束的意思, 但是可行解不見得是最優解, 我們可行域中的所有點都是可行解, 那麼什麼叫最優解呢? 最優解就是可行解中最優的那個解, 把它記爲x星, x星要滿足什麼呢? 就是對任意其他可行解x都有cx小於等於cx星, 也就是x星的目標值來得最大, 它要大於等於其他任意可行解的目標值, 與前面的圖解法對應着來看一下直觀的含義, 可行解就是可行域中的全部點, 是一些可行的方案, 而最優解是可行域的邊界上的點, 而且是在這個圖所示是邊界上的一個腳點, 是一個最優的方案, 第二組概念, 我們將介紹基矩陣和基變量的概念, 先來說一下什麼是基矩陣, 基矩陣簡稱基, 它是指係數矩陣A中的m階可逆子陣, 用B來表示, 大寫的字母B來表示, 也就是在係數陣A中m階可逆子陣, 因爲這個係數陣A是m乘n階的, m小於等於n, 那麼它裏邊的一個m階可逆子陣, 是它的一部分m列所組成, 是可逆的一個子陣, 那麼其餘的那些列組成的矩陣就稱爲非基矩陣, 即爲n, 比如說我們現在有一個係數矩陣A, 這個係數矩陣, 它是某線性規劃的約數部分, 約數化爲等式之後, 它的左端的係數組成了矩陣, 這個係數矩陣A是個二乘四的兩行四列, 也就是m等於2, n等於4, 我們以它爲例, 來看一下基矩陣的概念, 我們剛纔已經知道, 所謂基矩陣呢, 就是係數陣A中的m階可逆子陣, 在這個例子中m等於2, 那也就是說, 這個A中的g應該是它其中的二階可逆子陣, 因爲可逆的矩陣都得是方陣, 所以它應該是一個二乘二的一個子方陣, 我們現在直觀上已經可以看出, 在這個A中, 它的最容易看出的就是它的後邊兩列, 也就是它的第三列和第四列, 構成的二階子陣是一個單位陣, 單位陣顯然是可逆的, 單位陣的逆還是單位陣, 所以呢, 這個A中的後兩列就是三四兩列, 就構成A中的一個g, 假如三四兩列是A中的一個g, 它確定爲一個g, 那麼剩下的其餘部分就是第一列和第二列, 這個部分也是一個小子陣, 它就是相應於那個g的非g矩陣, g爲n, 我們顯然看到在A中並不是只有一個g存在, 這個係數陣A中的前邊兩列, 前邊兩列就是一二兩列, 它構成的一個小子陣, 經過驗證, 如果它也是可逆的話, 那它也是一個g, 它如果作爲一個g, 那麼後邊兩列就是它相應的非g部分, 那麼在這個係數陣A中, 可逆子陣可以有多個, 都是由A中的某兩列組成, A中的某兩列組成的子陣, 只要可逆就是一個g, 那麼在這個A中呢, 可以有多個可逆子陣, 也就是有多個g, 每個g只要確定以後, 它的其餘部分組成的子陣就是非g, g爲n, gg爲b, 那麼在一個g子陣, 一個g矩陣確定之後, 它是由A中的若干列所組成, m個列組成, 這些構成g矩陣的列, 我們也給它一個稱呼叫g向量, 所謂g向量就是, g矩陣B中的列, 那麼非g矩陣中的列呢, 就稱爲非g向量, 比如剛纔的例子中, 假如你確定, 後兩列這個單位陣爲一個g, 那麼它的組成向量, 也就是第三和第四列, 就是g向量, 而前兩列是非g矩陣構成, 所以前兩列就稱爲非g向量, 我們一般的, 把A中的列用pj來表示, 也就是說第一列計爲p1, 第二列計爲p2, 第三列計爲p3, 第四列計爲p4, 一般的gA中的列爲pj, 這個j呢就是序號1234, 那麼因爲這個係數矩陣, 是一個線性規劃的約數部分, 約數的這個它的係數組成, 我們剛纔在前面的模型中已經知道, 係數矩陣的每一列, 是與一個變量相對應的, 比如說第一列就是對應於x1, 第二列對應於x2, 也就是說, 這個A的每一列都對應於一個決策變量, 我們就稱這些和g向量對應的決策變量爲g變量, 也就是說, 與g向量pj對應的決策變量xj就稱爲g變量, 即其組成的向量符號爲xb, 那麼與非g向量對應的變量就稱爲非g變量, 即其組成的向量符號爲xn, 好,我們這一組概念是線性規劃解的一組重要概念, 它們都是以g矩陣作爲出發點, 在係數矩陣A中的可逆子陣就是g矩陣, g矩陣中的列就是g向量, g向量相對應的變量就是g變量, 下面我們來看一個例子, 這是某線性規劃的約數, 我們看到它已經化爲了標準形式, 也就是這個約數已經化爲等式約數和非負約數的形式, 現在我們來分析這個線性規劃約數中相應的g矩陣, g向量和g變量, 我們剛纔已經說過g矩陣是係數矩陣A中的可逆子陣, 因此我們先要把係數矩陣把它寫出來, 在本例中係數矩陣A是由四個列兩行四列所組成, 由於這個很簡單, 所以我們很容易看出A中的二階可逆子陣, 由後兩列組成的這個單位陣把它記爲B1, 就是A中的P3和P4組成的是一個單位陣, 它顯然是可逆的, 那麼這個就是一個A中的一個g矩陣, 它相應的列就是g向量爲P3和P4, 那麼g向量相應的g變量就是x3和x4, x3和x4組成的g變量的向量xB就是由x3x4組成的向量, 這是一個g,在這個A中還有其他的可逆子陣, 都是這個A相應的g, 比如說由前兩列組成的子陣也是可逆的, 這個記作B2, 它相應的g向量就是P1和P2, g變量就是x1和x2, 那麼這時的g向量的這個表達式就是xB等於x1x2, 那麼這個每一個g確定了以後, 它相應的g向量和g變量也就確定了, 其餘部分就是非g, 那麼非g相應的列就是非g向量, 相應的變量就是非g變量, 我們在本例的這個係數陣A當中, 我們不難分析出這個A中可能的g一共有多少個呢? 它最多有可能有多少個呢? 因爲每一個g在這道題中, 每一個g就是A中的某兩列組成的子陣, 它是可逆的, 那麼這個A一共有四列, 四列當中選擇不同的兩列組成的方式, 一共就是一個組合數C42, 是六個, 這個六個呢, 它只是一個可能的個數, 就是它最多是這麼多個, 因爲在這六個當中還可能有不可逆的, 也就是這個當中呢, 四個當中選兩列的不同的組合方式一共是六種, 但是這組合出來的六個子陣當中還可能有不可逆的, 只有可逆的子陣纔是g, 一般的來說, m乘n階矩陣A中g的個數最多有多少個? 就是我們剛纔分析的, 最多可能是Cnm個, 剛纔介紹了g矩陣, g向量和g變量的概念, 在此基礎上, 我們將繼續介紹下面一組重要的概念。