任務三　線性規(guī)劃的單純形法

前面介紹的圖解法雖然簡單、直觀，容易理解，但是，它只能解決2個決策變量的線性規(guī)劃問題，對更為復雜的問題則無能為力。所以，我們需要尋找這種問題的一般解法，20世紀40年代末，單茨格（Dantzig）提出的單純形法，完美地解決了線性規(guī)劃問題。

3.1　單純形法的一些基本概念

在線性規(guī)劃中，設(shè)A為約束條件的m×n階系數(shù)矩陣（設(shè)n＞m），其秩為m，B是矩陣A的一個m×m的滿秩子矩陣，那么我們稱B是線性規(guī)劃問題的一個基。

基變量：B中每一列所對應的變量叫基變量，其余的叫非基變量。

基本可行解：一般地，如果包括松弛變量在內(nèi)的變量個數(shù)為n，方程個數(shù)為m，那么在標準形式中，有n-m個變量等于0的可行解叫做基本可行解。

最優(yōu)解：滿足目標函數(shù)要求的基本可行解為最優(yōu)解。最優(yōu)解對應的基為最優(yōu)基。

矩陣的初等變換：將矩陣的一行同乘以一個數(shù)；將矩陣的一行同乘以一個數(shù)，再加到另外一行上去。

3.2　單純形法的理論依據(jù)

單純形法解決線性規(guī)劃問題的理論依據(jù)：線性規(guī)劃問題的可行域是n維向量空間Rn中的多面凸集，其最優(yōu)值如果存在必在該凸集的某頂點處達到。頂點所對應的可行解稱為基本可行解。

單純形法的基本思想：先找出一個基本可行解，對它進行鑒別，看是否是最優(yōu)解；若不是，則按照一定法則轉(zhuǎn)換到另一改進的基本可行解，再鑒別；若仍不是，則再轉(zhuǎn)換；按照這個方法重復進行。因基本可行解的個數(shù)有限，故經(jīng)有限次轉(zhuǎn)換后必能得出問題的最優(yōu)解。如果問題無最優(yōu)解也可用此法判別。單純形法是從某一基本可行解出發(fā)，連續(xù)地尋找相鄰的基本可行解，直到達到最優(yōu)的迭代過程，其實質(zhì)是解線性方程組。

3.3　線性規(guī)劃的標準形式

線性規(guī)劃問題是求一個線性目標函數(shù)在一組線性約束條件下的最大值或最小值問題。在線性規(guī)劃模型中，目標函數(shù)根據(jù)實際問題的要求可以求最大值，也可以求最小值；每一個約束條件可能是相等約束，也就是約束函數(shù)等于資源常量項，也可能是不等約束，也就是約束函數(shù)大于資源常量項或約束函數(shù)小于資源常量項。資源常量項可能非負也可能非正，決策變量取值范圍可能非負，可能非正，甚至可能無限制。因此，線性規(guī)劃模型的形式是多種多樣的，這給求解線性規(guī)劃問題帶來了諸多不便。為了求解的方便，我們可以先把線性規(guī)劃模型轉(zhuǎn)化成標準形式，然后再進行求解。所有的線性規(guī)劃模型都可以轉(zhuǎn)化為標準形式。下面我們介紹線性規(guī)劃的標準形式。

線性規(guī)劃的標準形式為

它也常寫成向量形式

線性規(guī)劃的標準形式必須滿足以下四個條件：

（1）目標函數(shù)極大化；

（2）約束條件的右端常數(shù)項非負；

（3）所有的約束條件必須為等式；

（4）決策變量非負。

那么，如何將線性規(guī)劃轉(zhuǎn)化為標準形式呢？

（1）如果目標函數(shù)為求極小值，即minz＝CX，因為minz＝-max（-z），所以我們可以令z′＝-z＝-CX，這時，目標函數(shù)就變成maxz′＝-CX，轉(zhuǎn)化后的問題與原問題有相同的最優(yōu)解。

（2）如果約束條件為不等式，那么將它轉(zhuǎn)化為等式時，可以引入一個松弛變量xn＋1（非負），這時原不等式就變?yōu)?/p>

如果約束條件是不等式，這時可以引入剩余變量xn＋1（非負），這時原不等式就變?yōu)?/p>

也就是說，如果原不等式左邊小于等于右邊，就讓左邊加上一個非負數(shù)，使得兩邊相等；如果原不等式左邊大于等于右邊，就讓左邊減去一個非負數(shù)，使得兩邊相等。

（3）如果右端常數(shù)項小于0，只需兩邊同乘以-1即可。

（4）如果決策變量無非負約束，這時可以分為以下兩種情況討論：

①決策變量xj≤0，可以令，這里非負。

②若xj為自由變量，即xj可為任意實數(shù)，可令，且，將變換后的變量代入原模型，則轉(zhuǎn)化后的問題和轉(zhuǎn)化前的問題具有相同的最優(yōu)解。

例2-3-1　將下列線性規(guī)劃問題轉(zhuǎn)化為標準形式。

解：第一步，目標函數(shù)乘以-1，轉(zhuǎn)化為最大化。即

maxz＝-x1＋2x2-3x3

第二步，在第一個約束條件中引入松弛變量x4，在第二個約束條件中引入剩余變量x5，即

x1＋x2＋x3＋x4＝7

x1-x2＋x3-x5＝2

第三步，在第三個約束條件等式兩邊同乘以-1，使等式右邊為非負。即

-3x1＋x2＋2x3＝5

第四步，將無約束的x3轉(zhuǎn)化為x3＝x6-x7，把它代入原問題中，因此，可以得到原問題的標準形式

3.4　單純形法的求解

例2-3-2　用單純形法求解線性規(guī)劃。

解：先把線性規(guī)劃問題化為標準型：

這時我們可以得到約束條件的增廣矩陣：

取單位矩陣所在的列對應的變量為基變量，其余變量為非基變量，獲得基本可行解X＝（0，0，15，24，5）T。列出一個初始單純形表，見表2-3-1。

表2-3-1的最后一行，我們稱為目標函數(shù)行。從目標函數(shù)行我們可以看出，現(xiàn)在z＝0，也就是說目標函數(shù)值為0。那么這個基本可行解是不是最優(yōu)解呢？判定方法是：單純形表中目標函數(shù)行對應于非基變量的元素，我們把它稱為檢驗數(shù)。而當所有檢驗數(shù)都非正時，就得到了最優(yōu)解，否則解仍然可以改善。

事實上，如果檢驗數(shù)有正數(shù)，那么以該檢驗數(shù)為系數(shù)的非基變量取值大于0時，目標函數(shù)值就仍然可以增大，所以這個解不是最優(yōu)解；而當所有檢驗數(shù)非正時，非基變量取值為0，目標函數(shù)已取得極大值，所以這個解就是最優(yōu)解。

在表2-3-1中的檢驗數(shù)，2和1均為正數(shù)，因此，解仍然可以改善。把原來的一個非基變量換為基變量，使得目標函數(shù)值增大。因為x1的價值系數(shù)更大，所以如果把x1變?yōu)榛兞浚繕撕瘮?shù)值會增加更快。選擇將x1換為基變量，稱為進基變量。因為換入了一個基變量，因此，有一個原來的基變量會被換出，稱之為離基變量。

選定進基變量后，可以用最小比值法，，確定6作為主元，即要化為1的元素。這個元素不能為負，不能為0。可以把主元用括號標志出來，如表2-3-2所示。

接下來，通過初等行變換，把主元化為1，把主元列其他元素全部都變?yōu)?，結(jié)果如表2-3-3所示。

檢查檢驗數(shù)，仍有正數(shù)，證明目標函數(shù)值還能增大，所以讓正的檢驗數(shù)所對應的變量x2作為進基變量，用最小比值法，所以主元定為。再次進行初等行變換，得到表2-3-4。

觀察表2-3-4的目標函數(shù)行，所有檢驗數(shù)都非正，這時我們就得到了最優(yōu)解，把它代入到目標函數(shù)，得到最優(yōu)值。

由此，我們總結(jié)出單純形法的基本步驟為：

（1）建立線性規(guī)劃問題模型，并將其化為標準形式。

（2）在標準形式的基礎(chǔ)上做出初始單純形表，求出檢驗數(shù)。

（3）確定檢驗數(shù)中最大正數(shù)所在的列為主元列，選擇主元列所對應的非基變量為進基變量。

（4）按最小比值原則，用常數(shù)列各數(shù)除以主元列相對應的正商數(shù)，取其最小比值，該比值所在的行為主元行；主元列與主元行交叉的元素為主元，主元所對應的基變量為出基變量。

（5）對含常數(shù)列的增廣矩陣用初等變換把主元變?yōu)?，主元所在的列的其余元素化為0。

（6）計算檢驗數(shù)，直到全部檢驗數(shù)小于等于0，迭代終止，基變量對應的常數(shù)列為最優(yōu)解，代入目標函數(shù)得最優(yōu)目標函數(shù)值。

例2-3-3　用單純形法求解線性規(guī)劃。

解：（1）先將上述問題化為標準形式。

（2）在標準形式的基礎(chǔ)上做出初始單純形表（見表2-3-5），求出檢驗數(shù)。

（3）檢驗數(shù)4，5都是正數(shù)，還能找到更優(yōu)的解。因此，我們要進行初等行變換。選擇檢驗數(shù)比較大的5所對應變量x2作為進基變量。

（4）用最小比值法確定主元，，所以主元定為1。進行初等行變換，把主元變?yōu)?，主元列其他元素變?yōu)?，見表2-3-6。

（5）觀察目標函數(shù)行的檢驗數(shù)，發(fā)現(xiàn)4仍然為正數(shù)，于是選擇4所對應變量x1為進基變量。

（6）用最小比值法確定主元，，進行初等行變換，把主元變?yōu)?，主元列其他元素變?yōu)?，見表2-3-7。

（7）觀察目標函數(shù)行的檢驗數(shù)，發(fā)現(xiàn)3仍然為正數(shù)，于是選擇3所對應變量x4為進基變量。

（8）用最小比值法確定主元，，進行初等行變換，把主元變?yōu)?，主元列其他元素變?yōu)?，見表2-3-8。

觀察表2-3-8中目標函數(shù)的檢驗數(shù)，全部非正，這時我們就找到了該線性規(guī)劃問題的最優(yōu)解。最優(yōu)解為X＝（4，2，0，1，0）T，去掉松弛變量和剩余變量，最優(yōu)解為X＝［4，2］T，代入目標函數(shù)得最優(yōu)值z＝26。

有的時候，當?shù)玫阶顑?yōu)解之后，檢驗數(shù)并不全部為負，而是有0存在。這時，把檢驗數(shù)為0的一列作為進基變量，再次進行迭代，會得到另外一組最優(yōu)解，代表該線性規(guī)劃有無窮多最優(yōu)解。只要是已得到最優(yōu)解的單純形表中出現(xiàn)了檢驗數(shù)為0的情況，一般該問題都有著無窮多最優(yōu)解。

同理，如果單純形表中某非基變量的檢驗數(shù)為正，但此時該非基變量所對應列所有元素非正，那么該問題無最優(yōu)解。