133 討論圖4-15與圖4-17中的資訊與圖44中給出的解決方案基本相同。回想一下，Excel 的敏感度分析報告用影子價格來描述一個約束條件的右端值增加一個單位時最優方案值的變化。管理科學家軟體和 LINDO 用對偶價格來描述一個約束條件的右端值增加一個單位時最優方案值的變化。對於最大化問題，影子價格和對偶價格是相同的，但對於最小化同題，影子價格和對偶價格是完全相反的符號。由於Hewlitt公司問題涉及到最小化， 所以 Excel敏感度分析報告（圖4-17）中的影子價格是管理科學家軟體解決方案（圖44）中對偶價格的相反效。
第5章線性規劃的單純形法題的決策變數相當多，以至於難以用圖解法有效進行解決，這就需要使用代數法。應用最廣泛的用於解決線性規劃問題的代數法稱為單純形法。°基於這種方法編寫的計算機程式一般能解決具有數幹個變量和約束條件的線性規劃問題。專欄5-1中介紹了 Delta 航空公司的航班配置問題，描述瞭如何解決含有60 000 個變數和40000個約束條件的線性規劃問題。 專欄5-1、實踐中的管理科學 Delta 航空公司的航班配置 Delta 航空公司在它的 Coldstart計劃中，使用線性和整數規劃方法解決航班配置問題。這個專案的問題在於如何為各條航線分配班機和為乘客分配座位。航空公司的盈利依賴於在一天中合適的時間將合適的班機分配給合適的航線。班機的座位是一個時效性極強的商品；如果班機起飛時還有一個空座位，那麼這個座位的潛在利潤就永遠消失了。建立航班配置模型的主要目標是最小化運作成本和乘容收入損失。約東條件包括航班的可獲得性、機場飛機起飛和降落時間的平衡以及維護要求。 成功的為航線分配班機的Coldstart 模型顯示了現在可以解決的線性規規劃的規模。Coldstart的日常業務模型一般包含了大約60 000 個變數和40 000個約東條件。解決航班配置問題的第一步是將模型轉化為線性規劃模型。模型建立者的報告已經成功地解決了這些問題，並堅信 Coldstart模型的應用在今後3年中將為 Delta 航空公司節省3億美元。 資料來源：R. Subramanian,R. P. Scheff, Jr.，J. D.Quillinan, D.S. Wiper, and R. E. Marsten， "Coldstart: Fleet Assignment at Delta Air Lines，"Interfaces （January/February 1994）：104-120. 一些計算機程式碼用一種稱為內部點解的解題程式來解決線性規劃問題，這套程式對處理較複雜的問題十分有效，但單純形法仍然是使用最廣泛的方法。
第5章線性規劃的單純形法 135 5. 1 單純形法的代數方法讓我們先介紹一下我們將用來演示單純形法的問題。高科技產業公司進口電子元件用來裝配兩種不同型別的個人電腦。一種叫做桌上型電腦，另一種叫做行動式機。高科技產業集團管理層的目標致力於制定兩種產品的周生產計劃。 桌上型電腦每臺利潤為50美元，行動式機每臺利潤為40美元。為了下週的正常生產，裝配時間最長為150 小時。每臺桌上型電腦需要3小時的裝配時間，每臺行動式機需要5小時的裝配時間。另外，高科技產業集團目前只有20臺行動式機顯示器的庫存，因此，最多隻能裝配20臺行動式機。最後，只有 300平方英尺的倉庫空間存放新產品。每臺桌上型電腦需要佔用8平方英尺的倉庫空間，每臺行動式機需要佔用5平方英尺的倉庫空間。 為了給高科技公司的問題建立一個線性規劃模型，我們將使用以下的決策變數： x，—桌上型電腦的數量； x，行動式機的數量。 這個問題的完整數學模型如下： max s.t. SOx， +40x2 3x，+5*≤150 1x≤ 20 84，+5x，≤300 裝配時間行動式機顯示器倉庫空間 41，22≥0 給每個約束條件新增一個鬆弛變數，我們可以得到這個問題的標準型。 max s.t. S0x， +40* +03，+03 +053 3x，+5#+13 1% 8$，+5*2 +13 =150 = 20 +18， =300 （5-1） （5-2） （5-3） （5-4） （5-5） 5.1.1 單純形法的代數性質約束條件式（5-2）~式（5-4）組成了一個含有5個變數的3 單純形法是喬治•丹齊克在美國空軍個線性方程的系統。無論何時，一個線性方程組中的變數個服役時提出的，於1949年第一次發表。 數多於方程個數時，我們將得到無數個解。單純形法可以看做是為這種方程組尋找最優解的代數過程。在前面的例子中，最優解就是使目標函式式（5-1）最大化且滿足式（5-5）非負條件和式（5-2）~式（5-4）方程組的解。 5.1.2 確定基本解在高科技公司的約束條件中，變數個數（5）大於方程個數（3），用單純形法求解的方法為：設2 個變數為零值，再求出剩下的3個變數的值。例如，如果我們令*=0，S，=0，約束條件方組就變成： 3% =150 （5-6） 152 = 20 （5-7） 8x， +1$3=300 （5-8） 透過式（5-6）解出x，得到 3x，=150
136 資料、模型與決策：管理科學篇因此，*，=150/3 =50。由式（5-7）得到5=20。最後，將x，=50代人式（5-8），得到結果 8 ×50 +1S：=300 解出S，得到S=-100。 因此，我們得到5個變數的3個線性方程的解： 基是透過令5個變數中的2個為零，然 X= 50 後同步解3個方程求出另外3個變數的售而 X= 0 得到的。理論上，只有當3個等式線性獨 S，= 0 立時，我們才能求得解。幸運的是，單純 S2= 20 形法可以保證基變數在每個迭代過程都存在解。 Sg= -100 這個解通常稱為這個線性規劃問題的本解，簡稱基。對於求基的一般過程，我們必須考慮一個包含個變數和m個線性方程且n大於m的標準型線性規劃模型。 基為了確定基，令n-m 個變數為零，然後解 n個線性約束方程求得剩下的 m 個變數的值。° 對高科技公司的問題，首先令任意2個變數的值為零，然後求解其他3個線性方程，得到另外3 個變數的值，從而得到基。我們將設為零值的n-n個變數稱為非基變數，把其他m個變數稱為基變量。因此，在前面的例子中，*，和s，是非基變數，X，§2，Sg為基變數。 5.1.3 基本可行解一個基可能是可行的，也可能是不可行的。基可行解是指滿足非負條件的基。令，和了，為零， 然後解出x，52，§3，得到的基不是基可行解，因為$=-100。然而，假設我們把x，和x，作為非基變數，令%=0，x=0，那麼就很容易求得相應的基。由於x，=x=0，3個約束方程簡化為： 151 = 150 182 20 1sg =300 60 則最終解是： 50 X= 0 *= 0 40 S，=150 30 ⑥ $2= 20 Ss =300 ③ 20 （4 顯示器數量這個解是基可行解，因為所有的變數都滿足非負條件。 右圖表示出了高科技公司問題所有的約束方程和基。點 10 1~⑤是基可行解；點⑥~⑨是不可行的基。令*=0,S」=0， 裝配時間得到的相應基為點⑨；令x，=0，*=0，得到的基可行解為可行 10 20 30 40 50 域中的點①。 圖5-1 只顯示了高科技公司問題的基可行解，注意，每個解都是可行域的極點。在第2章中我們指出，線性規劃問題的最優解可以在極點中找到。因為每個極點對應一個基可行解，所以我們可以總結出高科技公司問題有一個最優基可行解。°單純形法就是從一個基可行解（極點）移動到另一個基可行解，直到找到最優解的選代過程。 ◎ 有些時候，無法找到包含m個等式和n個變數的等式組的惟一解，但是使用單純形法卻不會遇到這種情況。 這裡我們只考慮存在最優解的情況。對於無可行解和無界解的情況，沒有最優解，因此也就不可能有最優基礎可行解。
第5章線性規劃的單純形法 137 5.2 表格形式 60 求含有m 個約束條件和n個變數的線性方程組的基可行解是單純形法的起點。表格形式的目的是提供初始基可行解。 回想一下高科技公司問題，標準型如下： max S. l. 5Ox， +40x+05，+051+08 50 40 倉儲能力 30 3x， +5x+1s， 1x 8x，+5x2 顯示器數量 20 +13 = 150 = 20 +1s；=300 10 可行城當將所有滿足小於或等於約束條件的線性規劃問題寫成標準型時，可以很容易找到一個基可行解。我 10 20 30 裝配時間小上； 40 50 們只需要令決策變數的值為0，然後解出鬆弛變數的桌上型電腦值。注意，在這個過程中，令鬆弛變數的值等於約束圖5-1 高科技產業問題的可行域和極點方程的右端值。對於高科技公司問題，我們得到x， =0,X，=0,S=150,Sz =20，$3 =300，作為初始基可行解。 如果我們進一步研究高科技公司問題的標準型，就能發現有兩個屬性使我們能找到一個初始可行解。第一個屬性要求滿足以下條件： a.對於每個約束方程，方程中的m 個基變數必有一個變數的係數為1，而方程中其他基變數的系數都為0。 b.只在一個約束方程中出現的基變數的係數均為1。 當滿足以上條件時，每個約束方程有且只有一個基變數的係數為1，並且對於每個約束方程，基變數都是不同的。因此，如果將n-m個非基變數的值設為0，那麼基變數的值就等於約束方程右邊的值。 使我們能找到基可行解的第二個屬性要求約束方程的右端值非負。非負性保證了透過令基變數等於方程的右端值而得到的基為可行解。 滿足這兩個屬性的線性規劃問題被認為是表格形式。因此，我們看到高科技公司問題的標準型符合表格形式。實際上，對於小於或等於約束條件和右端值非負的線性規劃問題，其標準型和表格形式是相同的。在本章的後面，我們將會講解對於標準型和表格形式不相同的線性規劃問題如何建立表格形式。 綜上所述，運用單純形法求解線性規劃問題必須採取以下3個步驟： 第一步，建立方程式模型。 第二步，透過增加鬆弛變數或減少多餘變數，將模型轉化為標準型。 第三步，建立表格形式。 5.3 建立初始單純形表在把線性規劃模型轉化為表格形式後，我們得到一個可以用來開始建立單純形表的初始基可行解。為了給單純形法的計算提供一種簡便的方法，我們首先要建立初始單純形表。 初始單純形表的一部分是表格，它包含了線性規劃的表格形式列出的所有係數。如果我們採用常規符號： —目標函式中變數j的係數；
138 資料、模型與決策：管理科學篇 b一一約束條件；的右端值； -變數；在約束條件i中的係數。 這部分初始單純形表如下表所示： a11 412 azi 422 ••• Qin azn b • ••• • ． ． am amz.. amn 因此，對於高科技公司問題，我們得到的初始單純形表為： 50 40 0 0 0 3 0 8 5 1 5 1 0 0 0 1 0 0 150 0 20 1 300 接著，我們考慮將目標函式係數，即所有的右端值或所有的約束條件係數寫成組的形式。對於這種分組，我們將使用以下常規變數： c 行——目標函式係數； 6 列—約束方程的右端值； A 矩陣——約束方程中m行和n列變數的係數。 使用這些符號，這部分初始單純形表如下所示： c行 A 矩陣 6列為了幫助我們記憶每一列包含的變數係數，我們把每列對應的變數直接寫在相應的列的位置上。 透過增加變數，我們得到： 50 40 0 0 0 3 5 1 0101 8 5 0 0 0 0 0 1 150 20 300 單純形表的這個部分滿足問題的表格形式，因此很容易求得基可行解。首先，我們注意到對於每個基變數，其相應列的惟一非零位置的值為1。這樣的列被稱為單位列或單位向量。第二，表中的每一行都與基變數相關。每行在與基變數相應的列單元格中的值為1。然後每個基變數的值等於其相關行中的6。本例中，行1與基變數S，相關，因為這一行在，對應的列單元格中的值為1。因此，S」的值就等於右端值b：S，=6，=150。依此類推，S =6：=20，Sg=6，=300。 從初始基可行解進一步得到更優的基可行解，為此單純形法就必須產生一個能夠使目標函式值更優的新的基可行解。要達到這個目的，就要求改變基變數的設定：我們選擇一個當前的非基變數，使之成為基變數，並選擇一個當前的基變數，使之成為非基變數。 為了方便計算，我們在單純形表中增加兩個新列。其中一列記為“基”，另一列記為“c”。在基列中，我們列出當前基變數，在c。列中，我們列出每個基變數對應的目標函式係數。對於高科技公司問題，結果如下：
第5章線性規劃的單純形法 139 莝列 50 40 0 0 0 0 0 3 ‘3 5 1 5 0 0 0 0 0 0 1 150 20 300 注意，在基列中S，列在了基變數的首位，因為它的值由第一個約束方程的右端值賦予。而8，列在第二位，S，列在第三位，基列和右端值給出了初始基可行解，S， =150，82 =20， S3 =300。 我們能否找出一個新的基可行解來最佳化目標函式的值呢？為了檢測其可能性，我們在表的底部增加兩行。將第一行記為，它表示如果A矩陣中第j列對應的一單位變數放入基列後目標函式值的減小值。將第二行記為c，一石，它表示如果A矩陣中第；列對應的一單位變數放人解列後，目標函式值的淨變數。我們將c一2；稱為淨估計行。 讓我們首先來看z，行是如何計算出來的。假設我們考慮將非基變數x，增加一個單位，就是將x，= 0變為x，=1。為了使得這種變化仍能滿足約束條件方程，一些其他變數值也需要改變。從下文可以看出，單純形法要求只對基變數做必要的變化。例如，對第一個約束方程 3x； +5%+1s， =150 這個約束方程中當前的基變數是§」。假設x，仍然是值為0的非基變數，如果x，的值增加1，然後S，必須減少3以滿足約束方程。相似地，如果我們使x、增加1（保持*，=0），我們就可以從第二個和第三個方程中看出，§.並不減小，但S，將減小8。 透過分析所有的約束方程，我們看到x，所在列的係數表示當非基變數x，從O增加到1時當前基變董的減小值。一般來說，所有的係數列都可以這樣解釋。例如，如果我們設x，為值等於1的基變量，則了，將減小5，S.將減小1，且s：將減小5。 回想一下，單純形表的c。列的值是當前基變數的目標函式係數。因此，為了計算z，行的值（當x， 增加1時目標函式值的減小量），我們可以將c。列中的元素與矩陣A 中的對應元素相乘來獲得產品的總量。由此，我們可以得到： 2#0×3+0×0+0×8=0 2=0×5+0×1+0×5=0 23=0×1+0×0+0×0=0 “4=0x0+0×1+0×0=0 2s =0×0+0×0+0×1=0 因為x，的目標函式係數是c，=50，則c，一，的值是50。在當前基列中增加一個單位的，直接結果就是利潤增加50美元。因此，在x，對應的淨估計行中，我們填人50。依此類推，我們可以計算其餘變量的c，一值。結果如下面的單純形表所示： S， $z 0 0 0 50 0 8 0 50 40 5 1 5 0 40 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 150 20 300 0 0 目標函式的值在這個表的最後一列的，行中，我們可以看到一個黑體的0。這個0是當前基可行解對應的目標
140 資料、模型與決策：管理科學篇函式的值。它是透過將c。列的目標函式係數與相應的表中最後一列的基變數的值相乘計算出來的，為 0×150+0×20+0×300=0。 現在我們已經完成了整個初始單純形表。它顯示初始基可行解（*，=0，*2=0，S， =150,S2 =20， S； =300）有一個值為0的目標函式值或利潤。另外，c；一z；或淨估計行的值將幫助我們改進初始基可行解，從而得到一個更優的基可行解。 5.4 改進解從淨估計行可以看到，每單位桌上型電腦（x」）的目標函式值的增加量為50，每單位行動式機（*） 的目標函式值的增加量為40。因為*，引起的單位增量最大，所以我們選擇它作為變數放入基列。接著我們必須決定把哪一個當前基變數改為非基變數。 在討論如何計算z，的值時，我們注意到x，列的每個係數代表了因增加一單位x，而引起的對應基變數的減小量。從第一行我們看到生產每單位桌上型電腦將佔用3小時裝配時間，使，減小3。在當前的解中，S，=150，x，=0。因此，如果只考慮這一行，x，的最大值可能為： 3%，=150 解得： *.=50 如果x，等於50（x，保持值為0的非基變數），為了滿足第一個約束條件，S，將減小到0： 3x， +5x2 +1s， =150 考忠第二行，0x，+*2+32=20，我們看到x，的係數是0。因此，增加x，對了2不會產生影響，也就是說，增加x，不能使第二行中的基變數（82）變為0。x」增加，$，將保持不變。 最後，第三行中x，的係數是8，我們每增加1單位x，將會引起S，減小8個單位。因為ss的當前值是300，我們可以透過解 8x，=300 找到在s，成為值為0的非基變數前的x，的最大可能值。所以，我們看到x，不能超過30% =37.5。 同時考慮這三行約束條件，我們看到第三行的約束性最大。也就是說，生產37.5單位的桌上型電腦將使得對應鬆弛變數變成非基變數，值為§=0。 為了做出儘可能生產更多的桌上型電腦的決策，我們必須改變在基可行解中變數的設定，這意味著得到一個新的基列。單純形法透過選擇一個非基變數代替當前的一個基變數將一個基可行解向另一個推進。從一個基可行解向另一個推進的過程叫做迭代。我們現在來總結選擇一個非基變數使之成為基變量和選擇一個基變數使之成為非基變數的規則。 向基列中加入一個新變數的標準從淨估計行（c；一z）中選擇會引起目標函式值單位增加量最大的變數加人基。在持平的情況下， 遵循慣例，選擇靠左列對應的變數加人基。 把一個變數從當前基中移出的標準（最小比例測試） 假設引入的基變數與單純形表A部分的j列相對應。對每一個i行，計算出每個大於0的Q.的 6./a。的比率值。對應最小比率的基變數將被從基中移出。在持平的情況下，我們就遵循慣例，選擇持平行中最上邊一行對應的變數。 為了演示相關的計算，我們在表的右側增加一列，表示為比率b./ag。
第5 章線性規劃的單純形法 141 50 40 0 0 0 0 3 5 1 0 0 150 0 0 0 L50 =50 3 20 0 8 0 0 1 300 300 一=37.5 2， 0 0 0 0 0 50 40 0 0 0 我們看到在c一3，行中，“一，=50是最大的正值。因此，我們選擇x，作為新的基變數。檢查Q 的b，/0， 比率是否大於0，我們看到b,/031 =300/8 =37.5，是所有比率的最小值。因此，選擇將第三行對應的當前基變數（ss）移出基。在表中我們將 a1 =8打圈，表示第一列對應的變數進入基，第三行對應的基變數被移出基。採用常用線性規劃術語，我們稱打圈的元素為旋轉元素。包含旋轉元素的列和行相應地稱為旋轉列和旋轉行。 為了改進當前解x，=0，*=0,S， =150,S =20,S，=300，我們將x，增大到37.5。生產37.5單位的桌上型電腦的利潤為50x37.5=1875（元）。要生產37.5單位的桌上型電腦，S：將被減小到0。因此，工！ 將替換s，原來在基中的位置，成為新的基變數。 5.5 計算下一張表我們想要更新單純形表，使與新的基變數相對應的列成為單位列。這樣，它的值就由對應行的右端值賦予。我們希望新表中x，對應的列看起來和原表中S，對應的列相同，所以我們的目標是使A矩陣中x，對應的列變為： 0 0 1 我們轉換單純形表使得它仍然表示與約束方程組等價的方法是使用以下介紹的基本行操作。 基本行操作 1. 將任何行（方程）乘以一個非零數。 2. 將任何行（方程）增加或減少成倍的另一行（方程）的結果來替換此行（方程）。 對一個同是線性方程組的這些基本行操作的應用不會改變方程組的解，但是，基本行操作將改變變數的係數和右端值。 進行基本行操作的目的是把約束方程組轉換為一個容易找出新的基可行解的表單。相應地，我們進行基本行操作必須依照規則，把變數進人基的列轉換為一個單位列。需要強調的是，原約束方程的可行解與透過基本行操作更改過的約束方程的可行解相同。但是，單純形表中的許多數值因為進行了此類行操作還是會發生變化。因此，當前得到單純形表元素的方法可能會導致困惑。 到目前為止，我們沒有對問題的表格形式的矩陣q、6列係數和單純形表中對應的係數做出任何區分。實際上，我們演示了初始單純形表的形成是把問題表格形式給出的ay、9，和b，元素相應地放入單純形表。為了避免對隨後的單純形表產生困惑，我們將把含有初始q，值的部分記為有，把含有初始 b.值的部分記為萬。藉助於單純形表，我們把A中的元素表示為，把中的元素表示為石。在隨後
142 資料、模型與決策：管理科學篇的單純形表中，基本行操作將改變表單元素，上劃線符號應當可以避免困惑，這些困惑產生在當我們要區分（1）表格形式的原約束條件係數a，和右端值b，及（2）單純形表元素G，和萬，時。 現在讓我們來看看怎樣透過基本行操作來建立高科技公司問題的下一個表單。回想一下，我們的目標是將單純形表萬部分中對應於x，的列轉換成單位列，也就是說使 ai =0 a1.=0 an1=1 令as =1，我們進行第一步基本行操作，把旋轉行（行3）乘以，得到等價方程 ⅛（8x， +5x+08，+08 +18：）=⅜×300 或 1x，+⅝X+0S，+05+⅜S：=75 我們把更新後的單純形表中的式（5-9）稱為新的旋轉行。 令a=0，我們進行第二步基本行操作，先將新的旋轉行乘以3，得到等價方程 3 x（1x， +⅝8：+05，+05：+ ⅜8：） =3×79 （5-9） 或 3x，+ ⅝%+05，+05+ 953=220 （5-10） 把式（5-10）從單純形表的行1對應的方程中減去，就完成了第二步基本行操作。因此，去掉係數為零的項後，我們得到 （3x，+5*：+15，）-（3x， +⅝X，+⅜3）=150-244 或 Ox，+29X，+15，-⅜3，=756 （5-11） 因為1=0，所以不需要對單純形表的第二行做任何更改。用式（5-11）和式（5-9）的係數替換對應的行1和行3，我們得到新的單純形表，如下： 基列 50 40 0 0 0 $z 0 0 50 0 0 1 1 ⅝ 1 0 0 0 I 0 -⅜ 0 ⅛ 20 7⅝ 1 875 C， 令非基變數 *，和了，等於零，我們可以得到以下新的基可行解： S，=⅞ $2 =20 ×1=⅞⅝ 這個解也是由新單純形表的最後一列得出。對應於這個解的利潤是透過列給出的基變數的解值乘以ca列給出的對應的目標函式係數得到的，為 0×½+0×20+50×½=1875 5.5.1 解釋選代結果在我們的例子中，初始基可行解是 4.=0 *2=0 S， =150 $2 =20 S； =300
第5章線性規劃的單純形法 143 對應的利潤為0美元。單純形法的一次選代使我們得到另一個基可行解，目標函式值為1875美元。這個新的基可行解為 75 X= 2 在圖5-2中，我們看到初始基可行解對應於極點①。第一次迭代使我們移向利潤的單位最大增長值的方向，即沿著x軸的方向。我們從極點①在x，軸的方向上移動，直到在不違反任何約束條件的情況下無法移得更遠為止。在一次迭代之後，我們得到的表單給出了一個基可行解，對應的是極點②。 我們注意到在圖5-2中，在極點②倉庫空間約束條件和S，=0共同起約束作用，而另兩個約束條件包含鬆弛變數。從單純形表我們看到，這兩個鬆弛變數是由S，=7⅝和 S=20給出的。 75 S；= 2 S2 =20 S=0 60 5040 30 倉庫空潤顯示器數量 20 5.5.2 向更優解移動 10 可行域裝配時間要找到一個更優的基可行解，我們需要計算新的單純形表的z，和c一，行。回想一 10 20 30 40 下，2，行的元素是產品的總量，是透過將單桌上型電腦純形表c。列的元素和對應的矩陣有中各列圖 5-2 高科技公司問題的可行域和極點的元素相乘得到的。因此，我們得到 2：=0×0 +0×0+50×1=50 zz =0×⅔⅝ +0×1+50×⅝=25% 2， =0×1+0×0+50×0=0 2=0×0+0×1+50×0=0 2s=0×（-⅜）+0×0+50×⅜=2 從c，中減去z，計算新的淨估計行，我們得到以下單純形表： 50 一X 50 S §s 0 0 50 0 0 4000 25 I 0 一 0 1 ⅝00 0 -⅜ 0 ⅛ ™⅝ 20 ™⅝ 50 20%00 1875 0 7%00 讓我們來分析一下c一行，看看是否能夠向基中換入一個新的變數，而且繼續改進目標函式的值。接著按照該把哪個變數換人基的規則，我們選擇x，因為它在c一，行中有最大正係數。 要決定當x，導人時哪個變數從基中換出，我們必須計算每個行；的比率6./ag（記住，我們只在 a2大於0時計算這個比率）。然後，我們選擇最小比率對應的變數換出基。像以誼一樣，我們在單純形表中增加一列來顯示這些比率。
144 資料、模型與決策：管理科學篇五基列 ⑨ 50 40 0 0 0 0 0 1 0 -⅜ = 12 §z 0 0 1 0 1 0 20 50 1 0 0 ⅛ 2%= 20 2 =60 ⅝ 50 0 260/ 7% 0 0 0 0 1875 -$% 因為12是最小比率，所以s，將換出基。旋轉元素是a2 =35，即上表中打圈的元素。非基變數*， 現在在行1中必須變為基變數。這個要求意味著我們必須進行基本行操作，把x，列轉變成在行1中有一個元素為1的單位列，即我們要將表單的第二列轉換成以下形式： 1 0 0 我們可以透過以下基本行操作來完成這個變化： 第一步，行1（旋轉行）的每個元素乘以9S，使a2=1。 第二步，行2減去新的行1，使an =0。 第三步，將新的旋轉行乘以⅝，並從行3中減去其結果，使as2 =0。 經過這些行操作後產生的新單純形表的結果如下： 藝列 50 0 $z 40 0 50 一z 50 0 40 1 0 0 40 0 O ⅝/as -⅝/25 1% -1% 0 0 1 0 0 0 0 $/25 12 8 30 1 980 -29 注意，基變數的值是*=12，S2 =8，x， =30，對應的利潤為40×12+0×8+50×30 =1980。 現在我們必須決定是否向基中換入其他變數從而得到另一個基可行解。觀察淨估計行，我們看到每個元寮都是零或負數。因為對非基變數S，和了，9，一z，都小於或者等於零，所以此時任何把非基變量換人基的行為都會使得目標函式的當前值減小。因此，這個表單就表示最優解。一般而言，單純形法使用以下準則來確定何時得到最優解。 鍛憂準則當淨估計列（c，-z，）的所有元素都為零或負數時，線性規劃問題得到最優解。在這種情況下，最優解就是當前基可行解。 從圖5-2，我們可以看到用圖解法來表示使用單純形法決定最優解的過程。初始基可行解對應於初始價（x，=0，x =0,S=150,S2=20,S=300）。第一次迭代將x，導人基並將S，換出。第二個基可行解對應於極點②（*） =75，*=0,S1=75，S2 =20，§3=0）。在下一次選代中，“，被換人基，S， 移出。這次迭代使我們移動到極點③，並且得到最優解（x」 =30，*2 =12,S」 =0,82 =8, 83=0）。 對於只有兩個決策變數的高科技公司問題，我們可以選擇使用圖解法或者單純形法。對於多於兩第5章線性規劃的單純形法 145 個變數的問題，我們一般使用單純形法。 5.5.3 解釋最優解透過最終單純形表，我們找到高科技公司問題的最優解，它包含了基變數x」、X2、$，和非基變數 SjSs： x，=30 X=12 S1=0 &= 8 §= 0 目標函效值是1980美元。如果管理者想要使總利潤最大化，那麼高科技應該生產30單位的桌上型電腦和 12單位的行動式機。當§=8時，管理者應該注意到有8個未使用的行動式機顯示器。而且，因為 S.=0，§=0，所以沒有任何鬆弛變數與裝配時間約束和倉庫空間約束相關聯。也就是說，這些約束條件都是束縛性的。因此，如果有可能獲得多餘的裝配時間或倉庫空間，管理者應該考慮這麼做。 圖5-3顯示了使用管理科學家軟體包得到的高科技公司問題的計算機解。最優解是x， =30，42= 12，目標函式值為1980美元。實現最優解的鬆弛變數值是S，=0，S2 =8，S3=0。縮減成本列的值由最終單純形表的淨估計行得到。注意，與x，和*，對應的列的c，一，值都為0。對偶價格是最終單純形表的3個松馳蠻量的z，信。從最終表單，我們看到約束條件！的對偶價格是S，對應的z，值，為26= 2.8。相似地，約束條件2 的對偶價格為0，約束條件3的對偶價格為29 =5.2。在第6章研究靈敏度分析時，我們將進-步討論如何使用單純形法計算對偶價格。 OPTIMAL SOLUTION Objective Function Value = Variable 1980.000 Value Reduced Costs ×1 X2 Constraint 1 2 3 30.000 12.000 Slack/Surplus ---- 0.000 8.000 0.000 0.000 0.000 Dual Prices --- 2.800 0.000 5.200 圈5-3 管理科學軟體對高科技公司問題的解答 5.5.4 單純形法小結現在讓我們來總結一下使用單純形法解決線性規劃問題的步驟。我們假設問題只有小於或等於約束條件並求最大化。 第一步：建立問題的線性規劃模型。 第二步：給每個約束條件增加鬆弛變數，得到標準型。這也是為含有所有小於或等於約束條件且右端值非負的問題提供了識別初始基可行解所必需的表格形式。 第三步：建立初始單純形表。 第四步：選擇淨估計行中最大值元素對應的非基變數換人基。這個變數決定旋轉列，即與換人變量相對應的列。 第五步：在j為旋轉列，a>0時，選擇最小比率B，/，所在行為旋轉行。這個旋轉行是當變數；為換人基時換出基的變數所在行。 第六步：進行必要的基本行操作，把換人變數的列轉換成一個在旋轉行有一個1的單位列。 a.旋轉行的每個元素分別除以旋轉元素（旋轉行和旋轉列相交處的元素）。 b.透過加上或減去新旋轉行的一個適當的倍數，使得旋轉列的所有其餘位置為零。當行操作完成
146 資料、模型與決策：管理科學篇後，新的基可行解的值可以從表單的石列得出。 第七步：測試最優解。如果對於所有列有c一2，≤0，那麼解就是最優的。否則，就需要再回到第四步。 對於有等於和大於或等於約束條件的問題，步驟基本相同，只是建立表格形式的工作略微複雜。 我們會在第5.6 節中進行相應討論。最小化問題的相應變動會在第5.7節中講解。 註釋與評論淨估計行的元素提供了線性規劃的計算機解的減少的成本。回想一下在第3章中，我們把減少的成本定義為，在假設目標函式的對應變數達到正值最優解前，目標函式係數的改變數。一般地，縮減成本是淨估計行中元素的絕對值。 5.6 單純形表的一般形式當線性規劃問題包含小於或等於約束條件且右端值非負時，很容易建立表單，我們只需要簡單地給每個約束條件新增一個鬆弛變數。但是，如果線性規劃包含大於或等於、等於約束條件或右端值為負時，建立表單就會複雜一些。本節描述了在這種情況下如何建立表單，以及如何使用單純形法解決等於、大於或等於約束條件的線性規劃問題。 5.6.1 大於等於約束假設在高科技公司問題中，管理者想要保證兩種產品的產量總和至少為25單位。這個要求就需要在當前線性規劃中加入以下約束條件： 2：+4≥25 加入此約束條件後對問題做出如下修改： maX 8.t. 5Ox，+40x 3x，+5%，≤150 1%≤ 20 8x，+5x，≤300 1x， +14≥25 裝配時間行動式機顯示器倉庫空間最小總產量首先，我們用3個鬆弛變數和1個剩餘變數寫出問題的標準型，如下； max SOx， +40x，+0S，+ OSz+0Sg+OSA S.t. 3x，+5x+1s1 1x 8x，+5%2 +182 +13 1x，+182 =150 = 20 =300 -15.= 25 （5-12） （5-13） （5-14） （5-15） X，X，S1,S2,Sg,S.≥0 現在讓我們考慮如何獲得一個初始基可行解來開始單純形法。之前，我們設x，=0，*2=0，並選揮松馳變數作為初始基變數。對於修改後的高科技公司問題，建議設x， =0， =0，並選擇鬆弛變數和剩餘變數作為初始基變數。得到基： ×=0 4=0 $：=150 82 =20 Ss =300 SA=-25 顯然，這個解不是基可行解，因為s。=-25違反了非負要求。難點在於當問題包含了大於或等於約束條件時，標準型和表格形式不等價。
第5章線性規劃的單純形法 147 為了建立表格形式，我們需要採用一個數學技巧，它藉助於鬆弛變數S，S，和一個記為c。的新變量找到一個初始基可行解。新變數構成了這個數學技巧。變數c。實際上與高科技公司問題無關，它只是幫助我們建立表格形式，並且得到初始基可行解。這個人為製造出來用於開始單純形法的新變數稱為人工變數。 人工變數的符號和A矩陣中元素使用的符號很相似。為了避免產生混淆，回想一下A矩陣的元素 （約束條件係數）通常有兩個下標，而人工變數只有一個下標。 隨著人工變數的加人，我們可以將問題的標準型轉換成表格形式。我們把人工變數a。加入到約束條件式（5-15）中，得到如下表格形式的方程組： 3x」+5%2+151 = 150 1%2 8x，+5x2 +1s2 +153 = 20 = 300 1x，+1x2 - 1s4 +Iaa= 25 ’注意，人工變數的下標表示與之相應的約束條件。因此，a。是對應於第四個約束條件的人工變數。 因為變數S，S2，S：和c。都分別出現在不同的約束條件中，係數都為1，而且右端值都是非負的， 所以表格形式的兩個要求都得到了滿足。我們現在可以透過令x，=*=S，=0，得到一個初始基可行解。全部的解為 x=0 X2=0 $，=150 $= 20 Ss =300 S.=0 Q，= 25 對於實際的高科技公司問題，這個解是可行的嗎？不，它是不可行的。它不滿足約束條件4，即 25單位的生產總量要求。我們必須清楚地區分表格形式的基可行解和真實問題的可行解。線性規劃問題的表格形式的基可行解並不總是真實問題的可行解。 建立表格形式的目的是得到用來開始單純形法的初始基可行解。因此我們看到，在任何需要引入人工變數的時候，初始單純形解對於真實問題來說一般都是不可行的。這個情況並不像看起來那麼麻煩，因為我們只需要在單純形法的最後一次選代中得到真實問題的可行解。因此，在得到最優解之前找到一種方法保證從基可行解中除去所有人工變數，就可以消除麻煩。 在得到最優解之前保證從基可行解中除去所有人工變數的方法是透過在目標函式中給每個人工變量分配一個巨大的成本來實現的。例如，在修改後的高科技公司問題中，我們給人工變數a，配置一個非常大的負數作為它的利潤係數。因此，如果這個變數在基中，它將會充分削減利潤。結果，這個變量就會被儘早地換出基，而這正是我們所希望的。 選取一個非常大的負數如-100 000 作為利潤係數，我們可以把每個人工變數的利潤係數標記為 -M。在這裡，假設 M 代表一個非常大的數。這個符號使我們很容易明瞭單純形表中依賴於人工變數的利潤係數的元素。用一M作為人工變數“。在修改後的高科技公司問題中的利潤係數，我們可以將何題的表格形式的目標函式寫成如下形式： mnax 5Ox，+40x： +05， +05+08：+0s4-Ma， 問題的初始單純形表如下： 50 3 0 40 5 0 以 Q4 0 o -M -M 50+ M -M 40+M 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 -M 0 150 20 300 25 -25M M -M -M 0
148 資料、模型與決策：管理科學篇這個表單對應的解是s， =150，S2 =20，S； =300，Q， =25，x，=*， =5，=0。根據單純形表，這個解是基可行解，因為所有的變數都大於或等於0，且n-m=7-4=3個變數等於0。 因為c，一，=50+M是淨估計行的最大值，我們看到x，將在單純形法的第一次迭代中變成基變量。單純形法的進一步計算顯示出在基中x，將會替代0A。下面的單純形表是第一次迭代的結果。 第一次迭代的結果 50 40 2 0 0 0 S」 Sa Ss 0 1 0 0 50 50 10 -3 1 50 -10 0 0 0 0 0 0 0 0 0 0 3 0 8 -1 -50 50 -M -3 0 -8 1 50 -M- 50| 75 20 100 25 1 250 9一z 當人工變數c。=0時，單純形表中的基可行解也是實際高科技公司問題的一個可行解。另外，因為a，只是我們新增的為了得到初始基可行解的一個人工變數，所以我們現在從單純形表中除去與之對應的列。實際上，無論何時我們使用人工變數，只要已經把它們從基可行解中刪除了，就能把它們從單純形表中除去。 當需要使用人工變數來獲得初始基可行解時，用來刪除人工變數的迭代被稱為單純形法的第一階段。當所有的人工變數都從基中換出後，第一階段就完成了，並且獲得了實際問題的一個基可行解。 因此，透過從當前單純形表中去除“。對應的列，第一階段結束時，我們得到了如下所示的單純形表： 50 40 2 0 0 $i $2 Ss 1 50 -3 1 0 1 0 0 0 0 0 1 0 0 3 ⑧ -1 75 20 100 25 50 10 50 0 -100 0 0 00 -50 50 1 250 現在我們已經準備好進入單純形法的第二階段。這個階段只是簡單地進行移出所有人工變數之後的單純形法的計算。在下一次迭代時，C一a，=50對應的變數S。被換人解中，變數s：被刪除。這次迭代後的單純形表為： 華列 50 0 40 0 0 Sa 0 -⅜ 0 ⅛ 0 0 ™ 20 50 G一 0 1 50 0 1 -⅜ ⅝ 20% 7⅝ 0 0 1 0 0 0 0 $% 1 0 0 0 ™ 1 875
第5 章線性規劃的單純形法 149 我們還需要另一次迭代。這次*，進人解，s，被刪除了。這次迭代之後，下面的單純形表顯示已經得到最優解。 40 50 0 40 Sa Ss 50 0 1 50 0 0 40 0 0 ¾/25 -⅝2 ⅜5 -⅝25 1% -1% 0 0 1 0 0 -½25 ¾25 ⅔5 ⅝8 0 0 0 0 0 0 12 8 17 30 1 980 0 0 G -2 結果，修改後的高科技公司問題的最優解和原問題的解相同。但是，單純形法要求用更多次的迭代來達到極點，因為我們需要多進行一次迭代以在第一階段中刪除人工變數（aa）。 幸運的是，當我們透過使用人工變數得到初始單純形表時，我們不需要關心一次特殊的迭代產生的基對於實際間題是否可行。我們只需要遵循單純形法的規則。如果我們達到了最優迭代（所有c，一 2，≤O），且所有人工變數都從解中刪除了，那麼我們就得到了最優解。另一方面，如果我們達到最優迭代且一個或多個人工變數仍以正值的形式留在解中，那麼所求的問題就沒有可行解。這種特殊的情況將在第5.8 節中進一步討論。 5.6.2 等式約束當線上性規劃問題中出現了一個等式約束條件時，我們需要新增一個人工變數來獲得表格形式和初始基可行解。例如，約束條件1為 6x， +4x-5x =30 我們可以簡單地新增一個人工變數a」，在初始單純形表中建立一個基可行解。加人人工變數後， 約束條件方程變為 6x， +442-5xg +la， =30 現在可以選擇a，作為該行的基變數，它的值由右端值賦予。當我們透過給每個等式約束條件新增人工變數來建立表單時，單純形法完全按照以前的步驟進行。 5.6.3 消除負的右端值線性規劃問題的表格形式的一個特性就是約束條件的右端值都是非負的。為一個線性規劃問題建模時，我們可能發現一個或多個約束條件有負的右端值。為了看看這種情況是怎麼發生的，假設高科技公司問題的管理者要求行動式機的數量*，必須小於或等於除去5臺內部使用之後的桌上型電腦的數量 x。我們可以將約束條件表示如下： 4≤X，-5 （5-16） 不等式兩邊都減去x，把兩個變數都放到了不等式的左邊，得一X+X≤-5 （5-17） 因為這個約束條件有一個負的右端值，所以我們可以透過將不等式兩邊都乘以-1使之成為一個右端值非負的不等式。這樣做的話，將不等式的兩邊乘以-1，將會改變不等號的方向。 因此，為了把不等式（5-17）轉換成右端值為非負的等價不等式，我們把兩邊乘以-1，得到 *-X：≥5 （5-18） 我們現在有了一個可接受的非負右端值。這個約束條件的表格形式現在可以透過減去一個剩餘變數和
150 資料、模型與決策：管理科學篇新增一個人工變數來獲得。 對於一個大於或等於約束條件，兩邊乘以-1，就得到一個等價的小於或等於約束條件。例如， 假設我們有如下的大於或等於約束條件： 6x，+3%2-4x≥-20 兩邊乘以-1，就得到一個右端值非負的等價約束條件，即如下所示的小於或等於約束條件： -6x，-3%+4%，≤20 我們可以透過新增一個鬆弛變數來建立這個約束條件的表格形式。 對於一個右端值為負的等式約束，我們可以簡單地把兩邊乘以-1，就得到一個右端值非負的等式約束。接著新增一個人工變數，就可以建立起表格形式。 5.6.4 小結：建立單純形表第一步，如果線性規劃問題的原模型包含一個或多個右端值為負的約束條件，那麼就把每個約束條件兩邊都乘以-1。兩邊乘以-1，將改變不等號的方向。這一步提供了右端值非負的等價線性規劃模型。 第二步，對於≤約束條件，透過新增一個鬆弛變數來獲得等式約束條件。鬆弛變數的目標函式系數設為零。它提供了約束條件的表格形式，並且鬆弛變數成為了初始基可行解中的一個基變數。 第三步，對於≥約束條件，透過減去一個剩餘變數來獲得等式約束條件，然後再新增一個人工變量得到表格形式。剩餘變數的目標函式係數設為零。人工變數的目標函式係數設為-M。人工變數成為初始基可行解中的一個基變數。 第四步，對於等式約束條件，透過新增一個人工變數，得到表格形式。人工變數的目標函式係數設為-M。人工變數成為初始基可行解中的一個基變數。 為了實際應用這些步驟，將下面問題轉換為表格形式，然後建立初始單純形表： max 6xi + 3iz + 4t + 1xa S.t. -2x1- ½x + lxg- 6x = -60 Ix + lxs + %xs 20 -Ixz-5xs ≤ -50 為了在約束條件1和3中除去負右端值，我們採用第一步。約束條件兩邊都乘以-1，我們得到如下的等價線性規劃模型： max 6xy + 3k + 4xg+ lxs 2x1 + ½x2- Ixs+ 6x =60 1x + lxs + ⅜X ≤ 20 1x2 + 5xs ≥50 Xi, X2, g,X4≥0 注意，約束條件3中的不等號≤因為乘以-1而改變了方向。透過對約束條件1採用第四步，對約束條件2採用第二步，對約束條件3採用第三步，我們得到下面的表格形式： max 6x， + 3x + 4ig + lx + 0sz + 0ss - Ma， -Mas 2x1 +½x2- 1xg + 6xg + lal 1x + ltg + ⅔x + lsz lx2 + 5xs - 1ss =60 = 20 + lag =50
第5 章線性規劃的單純形法 151 與此表格形式相應的初始單純形表如下： 基列 6 3 4 0 -M -M 41 §z 4g 一M 0 -M 0 O 1 一1 1 5 ⑥ ⅔ 0 0 1 0 1 0 0 0 -1 60 20 50 -110M -2M 6+2M -⅝M -4M -6M O 3+½M 4+4M 1+6M 0 M -M -M 0 一M 0 注意，我們將旋轉元素打上了圈，表示在第一次迭代時x，將換人基，而a，將換出基。 註釋與評論我們已經演示了怎樣將右端值為負的約束條件轉換成右端值為正的等價約束條件。實際上，將線性規劃公式化且包含負右端值並沒有錯誤。但是，如果你想要使用一般的單純形法來解決線性規劃問題，那麼你必須先更改約來條件，以消除負右端值。 5.7 解最小化問題我們可以透過兩種方法使用單純形法來解決求最小化的問題。第一種方法要求我們改變將變數換人基的規則。回想一下，在求最大化的情況下，我們選擇最大的正值c；-2，對應的變數作為下一個換人基的變數，因為c，一z，的值可告訴我們如果j列中一單位的變數被放人解中會導致的目標函式的增量。為了解決求最小化問題，我們只需要簡單地把這個規則顛倒。也就是說，我們選擇最小的負值 C，一2，對應的變數作為下一個換人基的變數。當然，這個方法意味著要對最優解的終止規則做出相應改變。使用這個方法解決求最小化的問題，我們將在淨估計行中的每個值都等於零或正值時終止。 解決求最小化問題的第二種方法是我們將在這本書中使用的。它是建立在任何求最小化問題都能透過把目標函式乘以-1而轉換成等價的求最大化問題的事實基礎上。對相應的最大化問題的求解將提供最小化問題的最優解。 讓我們透過第2章中用單純形法解決 M&D 化學公司問題的例子來演示第二種方法。回想一下這個問題，管理者想要在對產品 A有需求約束、有最小總產量要求和有加工時間約束的情況下，最小化生產兩種產品的成本。M&D 化學公司問題的數學表述顯示如下： min 2x， + 3x2 S.t. 1x ≥ 125 對產品A的需求 Ix +lx2 >350 總產量 2% +1x2 ≤600 加工時間 212≥0 為了用單純形法解決這個問題，我們先要將目標函式乘以-1，把最小化問題轉換成如下等價的最大化問題： max -2%-3x2 s.t. Ix ≥ 125 對產品A的需求 1x + 1x2≥350 總產量 251+ Ix2 ≤ 600 加工時間
152 資料、模型與決策：管理科學篇這個問題的表格形式如下： max S.t. -2%-3x2 + 0s + 052 + OSs- Man- Maz Ix -18 lxy + 1x2 - 1S2 2x +1x2 X，X20S1,S2:S30 01,02≥0 + lag + 15g = 125 + laz = 350 = 600 初始單純形表如下： Ss -M -M 0 G一 -2 -3 0 0 ① 0 -1 1 0 2 1 0 -2M -M M 0 -1 0 M -2+2M -3+M-M-M 0 一M 1 -M 0 0 125 350 0 600 0 -M -M -475M 0 0 0 第一次迭代後，x，被換入基，而a，被換出。從表單中除去q，列後，第一次迭代的結果如下： 蒸雞 4z Ss -2 -M 0 -2 1 0 0 -2 0 -3 0 1 -M 0 -1 1 ② 2-M 0 0 0 -I 0 0 1 M 0 -3+M -2+M 一M0 -M 0 0 -M 0 125 225 350 -250-225M 接著進行單純形法的兩次迭代，得到如下的最終單純形表： -2 1 Yx Si -2 -3 0 0 -2 0 -3 0 0 0 0 0 1 1 1 0 一2 -1 0 1 1 1 -30 4 1 00 -4-1 250 100 125 -800 目標函式值-800必須乘以-1，以獲得原最小化問題的目標函式值。因此，最優解的最小總成本為800 美元。 在下一節，我們將討論嘗試解決任何線性規劃問題時可能出現的一些重要的特殊情況。我們將僅考慮最大化問題的情況，因為我們認為所有的最小化問題都能透過把目標函式乘以-1而轉換為等價的最大化問題。 5.8 特例在第2 章中我們討論了當用圖解法來解決線性規劃問題時，不可行性、無界性和多項最優解是怎麼出現的。當使用單純形法時，這些特殊的情況也會出現。另外，一個被稱為退化的特殊情況理論上會使第5章線性規劃的單純形法 153 單純形法複雜化。在本節中，我們將演示在使用單純形法時這些特殊情況是怎樣被發現和處理的。 5.8.1 無可行解當無法找到滿足所有約束條件（包括非負約束條件）的線性規劃的解時，不可行性出現。現在讓我們看看，當使用單純形法時，不可行性是怎樣被發現的。 在第5.6節中討論人工變數時，我們提到當最最佳化準則顯示獲得最優解且一個或多個人工變數仍以正值留在解中時，不可行性被發現。作為這種情況的說明，讓我們來考慮高科技產業模型的另一種修改。假設，管理者加上了一個混合總產量最小為50單位的要求。修改後的問題模型如下： max 5Ox， +40x2 S.t. 3x+ 5x2s150 裝配時間 lx2≤20 行動式機顯示器 8x + 5X2 ≤ 300 倉庫空間 lx， + 1x2≥ 50 最小總產量 X，½2≥0 單純形法的兩次迭代產生下面的表單： $2 基列9 40 0 50 -M 50 0 40 O 0 0 0 -M %25 -%/5 44 1 0 -⅝25 0 -½25 0 1 0 0 -⅜25 ½25 ⅝28 -⅔5 0 0 0 -1 0 0 12 8 30 8 50 40 70+3M 130 +2M 0 M 1980-8M -M 25 25 170 - 3M G一 0 0 -130- 2M 0 -M 0 25 25 注意，對於所有的變數，G一，≤0。因此，按照最最佳化準則，這應該是最優解。但是這個解對於修改後的高科技公司問題是不可行的，因為人工變數G、=8在解中出現。解x，=30和x，=12使得混合總產量為42 單位，不滿足約束條件4至少50單位的要求。人工變數以Q，=8的值存在於解中的事實告訴我們，最終解8單位違反了第四個約束條件（1x，+1x，≥50）。 如果管理者有興趣瞭解前三個約束條件中的哪一個阻止了滿足總產量的要求，那麼部分答案可以從最終單純形表中得到。注意，S， =8，但是8，和了，為0。這告訴我們裝配時間和倉庫容量約束條件混合在一起。因為沒有足夠的可用裝配時間和倉庫容量，所以我們無法滿足最小混合總產量的要求。 管理者指出需要額外的可用裝配時間和倉庫空間來滿足總產量要求。如果沒有更多的時間和空間，那麼管理者將不得不降低總產量的要求，至少要降低8單位。 綜上所述，如果沒有解能夠同時滿足所有的約束條件，那麼一個線性規劃就是不可行的。當一個或多個人工變數仍以正值形式留在最終解中時，我們就認為是不可行的。最後，我們注意到，有≤約束條件和非負右端值的線性規劃問題總是有一個可行解的。因為，在這種情況下對於各種問題沒有必要引入人工變數來建立初始單純形表，最終解也不可能包含人工變數。 5.8.2 無解對於最大化問題，如果在不違反任何約束條件的情況下，一個線性規劃的解的值可以無限大，那
154 效據、模型與決策：管理科學篇麼我們說這個線性規劃是無界的。因此，當無界性出現時，一般我們都能找到所求問題的方程式中的錯誤。 引入變數的矩陣中列的係數表示一單位引入變數被換人解後，當前每個基變數的減小量。假設對於一個特殊的線性規劃問題，我們得到了一個點，在這個點上，運用換人基的規則確定換人變數是 *。假如對於這個變數，G2一2 =5，而且列2中所有的。都≤0。因此，引入解的每單位x，都使目標函式增加5個單位。此外，因為對於所有；有a。≤0，所以無論我們引人多少個單位的*2，沒有一個當前基變數會變成零值。因此，我們可以向解中引入無數多個x2，並且同時保持解的可行性。因為每單位*，使目標函式增加5，所以我們將有一個無界解。因此，我們判定無界性情況的方法是對應於引人變數的列中的所有a，都小於或等於0。 為了說明這個概念，讓我們來考慮下面的無界性問題的例子： max 20x+ 10x2 S.L. LX ≥2 1x2≤5 X， ≥0 我們從第一個約束條件方程中減去一個剩餘變數，在第二個約束條件方程中新增一個鬆弛變數 S2，就得到了標準型。接著我們向第一個約束條件方程新增一個人工變數a，就得到了表格形式。在初始單純形表中，基變數是a」和S2。在換人x，和換出*，的第一次迭代後，單純形表如下： 本列 20 10 O 0 Ki 20 0 一1 0 2 S2 0 0 0 1 5 20 0 -20 0 40 0 10 20 0 因為S，有最大的正值c，一，所以我們知道可以透過把S，換人基，從而最快地增加目標函式值。 但是a=-1，，ans=0，所以我們無法為任何。>0計算其6,/ag比率，因為Qg沒有一個值是大於參的。這個結果表示這個線性規劃的解是無界的，因為每單位換人基的s，提供了額外一個單位的x，（因為a=-1）且使得零單位的52從解中去除（因為 s=0）。因為S，是剩餘變數，並且可以解釋為x 與所要求的最小量的差值，所以單純形表表示我們可以引人任意多的我們所需要的s，而不會違反任何約束條件。這說明我們可以在x，所需要的最小量的基礎上使其無限大。因為x，對應的目標函式係數是正值，所以對目標函式值沒有上限。 綜上所述，如果我們可以將最優解的值任意加大而不會違反任何約束條件，那麼一個最大化線性規劃就具有無界性。當應用單純形法時，如果在某次迭代時，單純形法要求我們向解中引入變數j且j 列中所有的，都小於或等於零，那麼就存在無界性線性規劃。 我們強調無界解的情況在實際的成本最小化或利潤最大化問題中不會出現，因為我們不可能將成本削減到負的無限小，或者將利潤上升到正的無限大。因此，如果我們遇到了有無界解的線性規劃問題時，我們應該仔細地再檢查一下所求問題的方程式，以確定方程中是否有錯誤。 5.8.3 多個最優解有兩個或多個最優解的線性規劃被稱為有多個最優解。當使用單純形法時，直到最終單純形表完成後才能判斷一個線性規劃是否有多個最優解。如果一個線性規劃有多個最優解，將會有一個或多個非基變數的c，等於零。 為了說明使用單純形法時多個最優解的情況，我們考慮把高科技公司同題的目標函式從 50x，+
第5章線性規劃的單純形法 155 40x，改變成30x，+50x。這樣做之後，我們得到了修改後的線性規劃，如下： max 30x + S0x2 S.t. 3x +5x2≤ 150 1x2≤ 20 8xi + 5x2≤ 300 X,2≥0 這個問題的最終單純形表如下： 基列 §s 50 0 30 30 0 0 1 30 0 50 1 0 0 50 0 0 0 10 -10 0 1 2% -⅝ 0 0 0 0 1 0 0 0 20 20% 1 500 G一淨估計行中所有的值都小於或等於零，表示已經找到了一個最優解。這個最優解是x， =39，X2= 20,S」 =0,S2 =0,Sg=209。目標函式值為1 500。 觀察最優單純形表的淨估計行，我們看到非基變數$2的c，一2，值等於0，它表示這個線性規劃可能有多個最優解。換句話說，因為淨估計行中S2對應的元素為零，所以我們可以將S，換人基而不改變解的值。在換人S2後得到的表單如下： 30 0 50 O O 0 0 -⅜5 以q 50 0 30 30 0 0 0 50 0 -⅝5 10 -10 0 0 ⅝8 0 0 12 8 30 1 500 正如表單所示，我們有了一個不同的基可行解：*，=30，*2 =12,S，=0,82 =8，Ss =0。但是，這個新解也是一個最優解，因為對於所有j，都有c，一z，≤0。另一種確認這個解也是最優解的方法是確認解的值依然保持為1 500。 綜上所述，當使用單純形法時，我們可以透過判斷在最終單純形表中是否有一個或多個非基變數的c一z，等於零來確認存在多個最優解的可能性。 5.8.4 退化如果一個線性規劃有一個或多個基變數值為零，那麼我們就稱這個線性規劃退化。退化不會對圖解法造成任何特別的麻煩。但是理論上，當使用單純形法來解決一個線性規劃問題時，退化會造成一些麻煩。 為了看看一個退化線性規劃是怎樣產生的，我們考慮對高科技公司問題的裝配時間約束條件的右端值做出改變。例如，如果對於可用時間用175來替換150，那會怎麼樣呢？修改後的線性規劃如下： max SOxj + 40x2 S.t. 3x+ 5X2≤175 裝配時間增加到175小時 1x2 ≤20 行動式機顯示器 8xi + 5x2 ≤300 倉庫空間巧， ≥0
156 資料、模型與決策：管理科學篇第一次迭代後的單純形表如下： 莝列 S1 S2 50 40 1 50 ⅝ 50 0 250/ 7% 0 1 0 0 0 0 0 0 0 0 0 G一 0 -% 0 ⅛ $% -$% 120 20 1875 淨估計行中的元素表示x，應該換人基。透過計算合適的比率來確定旋轉行，我們得到： 124 =20 ai2 •！ 20 -=20 1 = 60 ig2 ⅝ 我們看到第一行和第二行的結果相等，這表示我們將在下一次迭代中得到一個退化基可行解。回想一下，在相等的情況下，我們按照慣例選擇最上面的一行作為旋轉行。在這裡，意味著s，將被換出基。但是，由於最小比率相等，我們看到行2中的基變數S，也將變為零。因為它不會被換出基，所以在這次迭代後我們將會有一個值為零的基變數。這一次迭代後的單純形表如下： 50 40 0 0 0 $z 40 0 50 0 1 50 0 1 0 0 40 0 -⅝25 -%/25 79/28 -79/2 0 1 0 0 0 -%8 ⅜8 ⅝ 20 0 25 180/28 2 050 -180% 如預期的那樣，我們得到包含一個零值基變數，的基可行解。無論何時，B，/a，的最小比率相等， 那麼下一個表單總會有一個值為零的基變數。因為在先前的例子中，我們處於最優解的情況，所以我們並不關心解中的8是否為零。但是，如果獲得最優解之前的某次迭代過程出現退化，那麼理論上， 單純形法有可能迴圈。也就是說，計算過程可能會在相同的非最優基可行解之間交替，而無法獲得最優解。在實踐中，迴圈並不是一個顯著的困難。因此，我們不推薦在單純形法中加入任何特殊的步驟來消除退化發生的可能性。如果在進行單純形運演算法則時，萬，/a，的最小比率相等的情況出現，那麼我們推薦簡單地選擇最上面的行作為旋轉行。 註釋與評論 1.我們已經指出，在遇到終止規則時仍有一個或多個人工變數以正值留在解中的情況下，可以確認不可行性。這個要求並不是指所有的人工變數都必須是非基變數以得到一個可行解。一個人工變數可以以零值存在於解中。 2.對於一個無界性問題，必須存在一個無界可行域，但是存在一個無界可行域並不能保證這個問題是無界性的。一個最小化問題可能是有界的，然而一個具有相同可行域的最大化問題是無界的。
第5章線性規劃的單純形法 157 本章小結在本章中，我們介紹了單純形法作為解決線性規劃問題的一種代數演算法。雖然單純形法可以透過筆算來解決一些簡單的線性規劃問題，但是它在解決較複雜的問題時會變得非常麻煩。因此，必須使用計算機軟體在可以接受的時間內來解決複雜的線性規劃問題。大多數計算機軟體的計算步驟都是建立在單純形法的基礎上的。 我們介紹了建立線性規劃的表格形式是如何成為使用單純形法為一個線性規劃問題求解做準備的必要步驟的，包括怎樣將大於或等於約束條件、等於約束條件和魚右端值約束條件轉換成表格形式。 對於大於或等於約束條件和等於約束條件的線性規劃，我們透過新增人工變數來得到表格形式。我們為每個人工變數設一個目標函式係數-M，其中-M是一個非常大的數。如果實際問題存在一個可行解，那麼在用單純形法得到它的最最佳化標準之前，所有人工變數將會被換出解（或者值為零）。我們透過使用迭代方法將人工變數從解中移出，這稱為單純形法的第一階段。 本章介紹瞭解決量小化同題的兩種技巧。第一種方法包括改變向解中引入變數的規則和改變最最佳化標準。 第二種方法是透過將目標函式乘以-1來獲得一個等價的最大化問題。透過這種變化，任何最小化問題都能使用最大化問題所要求的步驟來解決，但是最優解的值必須乘以-1，以獲得原最小化問題的最優值。 作為對本章內容的回顧，我們現在給出使用單純形法解決線性規劃問題的詳細步驟。 第一步，建立問題的線性規劃模型。 第二步，透過以下操作定義一個等價的線性規劃： 日.將每個右端值為負的約束條件乘以-1，並且改變約束條件不等好的方向。 b.對於最小化問題，透過把目標函式乘以-1將問題轉換成最大化問題。 第三步，透過新增適當的鬆弛變數和剩餘變數來建立線性規劃的標準型。 第四步，透過建立線性規劃的表格形式來獲得初始基可行解。所有線性規劃在獲得初始單純形表之前必須建立表格形式。 第五步，建立初始單純形表，保留用單純形法所要求的計算過程。 第六步，選擇最大的c，一，對應的非基變數換人基。該變數對應的列即為旋轉列。 第七步，選擇有最小B，/ay比率a>0的行作為旋轉行。這個比率是用來決定當變數；換人基時，哪個變數被換出基。這個比率還表示在第；行的基變數變為零值之前，有多少個單位的變數；可以被引入解中。 第八步，進行必要的基本行操作，將旋轉列轉換成單位列。 a.將旋轉行中的每個元素除以旋轉元素。其結果是得到一個新的旋轉行，在與旋轉列的交點處為1。 b.透過新增或減去一個適當的新旋轉行的倍數，在旋轉列的所有其他位置得到零值。 第九步，測試最優性。如果對於所有的列都有c一z，≤0，那麼我們就有最優解。否則，返回第六步。 在第5.8節中，我們討論了當用單純形法解決線性規劃問題時，不可行性、無界性、多個最優解、退化的特殊情況是如何出現的。 專業術語 simplex method 單純形法解決線性規劃問題的一種代數方法。單純形法透過使用基本行操作從一個基可行解 （極點）到另一個基可行解，直到獲得最優解為止。 basic solution 基（基本解） 當一個線性規劃的標準型有n個變數和m個約束條件時，基是透過設定n-m個變數等於零，並且求解另外 m個變數的約束條件方程而得到的。如果存在一個惟一解，那麼它就是一個基。 nonbasicvariable 非基變數在一個基中，n-m個設為零值的變數。 basic variable 基變散在一個基中，m個不等於零的變數。 basic feasible solution 基可行解一個可行的基。也就是說，這個解滿足非負約束條件。一個基可行解與一個極點相對應。 tableau form 表格形式在建立初始單純形表之前，線性規劃必須被寫成的形式。當一個線性規劃以表格形式表示時，它的A矩陣包含了m個與基變數相對應的單位列。同時這些基變數的值是由6列給出的。進一步的要求是6列中的元素必須大於或等於零。 simplex tableau 單純形表用來明確單純形法所要求的計算過程所使用的一個表格。
158 資料、模型與決策：管理科學篇 unit column or unit vector 單位列或單位向量一個矩陣中的一個向量或列，除了一個位置以外，其他所有位置的值都為0，惟一的非零位置的值為1。單純形表中每一個基變數都有一個單位列。 basis 基在當前解中不被要求必須等於零值的一組變數。組成基的變數被稱為基變數，其餘的變數被稱為非基變數。 net evaluation row 淨估計行對每一個變數（列），單純形表中包含的c一的行。 iteration 選代從一個基可行解向另一個移動的過程。 pivot element 旋轉元素在單純形表中同時位於旋轉行和旋轉列中的元素。 pivotcolumn 旋轉列在單純形表中與將被換人解的非基變數相對應的列。 pivot row 旋轉行在單純形表中與將被換出解的基變數相對應的行。 elementary row operations 基本行操作在不改變方程組解的情況下對方程組進行的操作。 artificial variable 人工變數對於原線性規劃問題沒有實際意義，只是單純地用來建立一個基可行解以開始單純形法的一個變數。為人工變數設定一個目標函式係數一M，M 在這裡是一個非常大的正數。 phaseI第一階段當人工變數存在於初始單純形表中時，第一階段指的是刪除人工變數所需要的單純形法的迭代。在第一階段的最後，單純形表中的基可行解對於實際問題同樣可行。 degeneracy 退化當有一個或多個基變數為零值時。 問題 2. 分析以下線性規劃問題： max S.t. Xi+2X2 *+5x2≤10 2x + 6x2 ≤ 16 X122≥0 a.將同題寫成標準型。 b. 對於這個問題，在基中有多少個變數將被設為零值？ c•找到所有的基，並且指出哪些是可行的。 d.透過計算每一個基可行解的值，找到最優解。 4.分析以下線性規劃問題： max S.t. 60x， +90x2 15x， + 45x2 ≤90 Sxi+ 5x≤ 20 X1122≥0 a.將同題寫成標準型。 b. 建立包含目標函式係數、約束條件中變數係數和右側常數的部分單純形表。 6. 下面是一個部分完成的初始單純形表： 5 2 3 20 2 0 25 0 -½ •0 1 0 0 0 0 0 0 40 30 15 a.完成這個初始表單。 b.將同題寫成表格形式。
第5章線性規劃的單純形法 159 c.什麼是初始基？它是否與原來的對應？解釋原因。 d. 在這個初始解中目標函式值是多少？ e.對於下一次迭代，哪一個變數應該換人基，哪一個應該換出基？ f. 下一個解中將會有多少個換人變數？在進行第一次迭代前，你認為第一次迭代後目標函式值將會是多少？ 8.使用單純形法找出最優解。 8. 回憶一下第2.1 節中的 Par公司問題。這個問題的數學模型如下： max 10x+9x2 S.t. Zox + Ix2 ≤ 630 切割與印染 ½x+⅝x2 ≤ 600 縫合 1x1 + ⅔x2≤ 708 成型 ½ox +¼*2≤135 檢查與包裝 219X2≥0 這裡，x，表示標準袋產量；表示高階袋產量。 2.使用單純形法確定對於每一個模型，Par公司應該生產多少個袋子？ b.透過這些生產量，Par 公司可以有多少利潤？ c.對於每一步操作，生產計劃時間為多少個小時？ d.在每一步操作中，鬆弛時間是多少？ 10. 解決以下線性規劃問題： max S.t. Sxy + Sx2 + 24x3 15x， + 422+ 12x；≤2800 ISx，+8x2 ≤ 6000 X1 + 8x； ≤1200 X1.X22g≥0 12. 假設一個公司使用2種原材料生產3種產品。每一一種產品使用的原材料如右表。 如果這個公司有100磅的可用原材料I和200磅原材料 I I 產品A 71b sib 產品B 6lb 4lb 產品C 3b 21b 的可用原材料I，並且如果3種產品的單位利潤分別為20美元、20美元和15美元，則應該各生產多少單位相應的產品能使利潤最大化？ 14. Ye Olde Cording 葡萄酒釀造廠在Peoria生產3種不同型別的德國葡萄酒：海德堡甜酒、海德堡普通酒和德國幹酒。每一種酒生產1加侖所需的原材料、人工和利潤如下： A籌葡萄酒酒 B簭葡萄酒糖（磅） （蒲式耳） （蒲式耳） 人工 （小時） 海德堡甜酒海德堡普通酒德國幹酒 2 0 0 2 2 1 0 2 3 1 每加侖的利潤（美元） 1.00 1.20 2.00 如果該廠在下一週有150蒲式耳（合8加侖）的A等葡萄，150蒲式耳的B等葡萄，80磅的白糖和 225小時的人工，3種酒怎樣組合生產可以使公司的利潤最大化？ a. 使用單純形法求解。 b.說明所有的鬆弛變數。 c.原材料中哪一種的增長可以增加公司的利潤？ 16.為以下的線性規劃問題建立表格形式（不需要求解）：
160 資料、模型與決策：管理科學篇 18. 解決下面的線性規劃問題： min 4x， + Sxz + 3%s S.t. 4x + 2%≥20 1x2- 1xg ≤ -8 1x1- 2×2 = -5 2x1 +Ixz + lxg≤ 12 X1.%201g≥0 min 84x， + 4x2+ 30xs s.t. Bty + Ix+ 3xs≤ 240 16xy + 1x+ •7xg≥480 8x1-1x+ 4xg ≥160 20. OBDB 塑膠袋公司生產3種家庭用塑膠垃圾袋：一種20加侖的垃圾袋、一種30加侖的垃圾袋和一種33加侖的樹葉雜草袋。使用購買來的塑膠原料生產每一種終端產品需要有3個步驟：切割、成型和包裝。生產每一種袋子的每一個步驟所需要的生產時間和每一個步驟的最大生產時間如下（注意，生產時間數是以生產一盒袋子為單位的）： 袋子型別 20加侖切斛 2 生產時間（秒/盒） 成型 2 包裝 3 30 加侖 33 加侖可用時間 3 2 4 3 2小時 3 3 小時 4 小時如果 OBDB 的生產利潤為：生產每一盒20加侖的袋子獲利0.10美元，生產每一盒30加侖的袋子獲利 0.15 美元，生產每一盒33加侖的袋子獲利0.20美元，那麼最優的產品組合是怎樣的？ 22.Uforia 公司出售兩種品牌的香水：刺激和性情 No.1。Uforia 公司在百貨商店出售其產品，同時還僱用了由 3個人組成的銷售小組去拜訪顧客，進行單獨銷售。每一個銷售代表出售一瓶香水所需要的時間依個人經驗和能力的不同而不同。Uforia 公司的3位銷售代表的平均所用時間資料如下： 每瓶的平均銷傳時間（分鐘） 錆悔代衰銷售代表剩瀲性情 No.1 約翰 10 15 裡德每瓶的平均銷傳時間（分鐘） 刺激性情 No.1 12 6 布倫達 15 10 每個月，每位銷售代表花費在銷售這兩種產品上的時間大約為80小時。刺激和性情No.1每瓶的銷售利潤分別為30美元和25 美元。下一個月，對於兩種香水，每位銷售人員應該出售多少瓶才能使公司的利潤最大化？（提示：使 =約輸出售的刺激香水瓶數， =約輸出售的性情 No. 1 香水瓶數，*，=布倫達出售的刺激香水瓶數，依此類推。） 注意，在問題23~29中，我們提供了會有以下一個或多個情況的線性規則例子： •最優解。 • 無可行解。 • 無外解。