161 •多個最優解。 • 退化解。 對每一個線性規劃問題，確定存在解的情況，並且說明你是如何使用單純形法確定每一種情況的。對於多個最優解的問題，計算出至少兩個最優解。 24. min 3x+3x2 s.t. 26. 25+ 0.5x2≥10 25 ≥ 4 4x+4x2≥32 X 2≥0 max 2x1 +1x2 + 1xs S.t. 28. min S.t. 4x + 252 + 28≥ 4 24+4x2 ≤20 4x：+ 8x2 + 283 ≤ 16 X.220120 -4x，+5x2+5xg 1x2 +1xg≥2 -Ix+1x+ 1xg21 -lxg ≥1 X，220 ≥0 30. 超級體育足球有限公司生產3種不同型別的足球：通用型、大學型和高中型。所有的足球都需要透過以下部門的生產步驟：切割與印染、縫製、檢測與包裝。生產時間和最大可用生產量顯示如下： 生產時間（分鐘） 類型生產時間（分鐘） 類型切剚與印染鐘制檢瀾與包裝通用大學 12 15 3 10 15 4 高中可用時間切劑與印染 8 300 小時縫製 12 200小時檢測與包裝 2 100 小時當前的訂單顯示至少要生產1000個通用型足球。 8.如果公司生產一個通用型足球獲利3美元，生產一個大學型足球獲利5美元，生產—個高中型足球獲利 4 美元，那麼每一種足球各應該生產多少個？這個問題的解會出現什麼情況？為什麼？ b.如果公司透過加班可以使縫製時間增加到300小時，檢測與包裝時間增加到150小時，那麼你有什麼建議？
第6章基於單純形的靈敏度分析與對偶在第3章中，我們將靈敏度分析定義為對線性規劃問題的係數變化如何影響最優解的研究。在本章中，我們將討論怎樣從最終單純形表中得到諸如目標函式係數的範圍、對偶價格以及右端值的範圍的靈敏度分析資訊。本章還會介紹對偶問題。我們將會看到每個線性規劃問題都對應一個對偶問題， 而且這個問題有著重要的經濟學含義。 6.1 基於單純形表的靈敏度分析通常，線性規劃的靈敏度分析包括計算目標函式係數的範圍、右端值和對偶價格。 6.1.1 目標函式係數目標函式係數的靈敏度分析包括給係數值設定範圍，我們稱這個範圍為最優範圍。只要目標函式係數的實際值在最優範圍內，那麼當前的基可行解依然是最優的。基變數的最優範圈是指，當此變數保持為當前的最優基可行解時目標函式係數可取的值。非基變數的最優範圍是指，當此變數保持為非基狀態時目標函式係數可取的值。 在計算一個目標函式係數的最優範圍時，假設問題中的所有其他係數都保持原值；換句話說，一次只允許一個係數發生變化。為了描述計算目標函式係數的最優範圍的過程，回想一下第5章中介紹的高科技公司問題。這個問題的線性規劃重述如下： max SOx， + 40x2 S.L. 3t +5xs 1×2≤ &xi + Sxz≤300 裝配時間行動式機顯示器倉庫空間，½2≥0
第6章基於單純形的費敏度分析與對偶 163 式中x—桌上型電腦的數量； *，—行動式機的數量。 高科技公司問題的最終單純形表如下： 基列 50 0 §z 40 0 50 50 0 40 1 0 0 40 0 0 -%5 --⅝25 1% -⅛ 0 0 1 0 0 0 0 -⅜8 2% 12 8 30 1 980 -2 回想一下，當單純形表被用來解決線性規劃問題時，最優解在淨估計行（c，一z）的所有項都≤0 時得到。因為先前的單純形表滿足這個規則，所以得到的解就是最優解。但是，如果目標函式中的一個係數發生變化而導致一個或多個c一，值為正，那麼當前解就不再是最優解；在這種情況下，必須一次或多次使用額外的單純形迭代來找到新的最優解。目標函式係數的最優範圍取決於對任意的；值都滿足下式的係數的值： C-4≤0 （6-1） 讓我們透過計算c」（每臺桌上型電腦的利潤）的最優範圍來說明這個方法。把c」（而不是50）作為目標函式中x，的係數，則最終單純形表如下： 40 0 40 1 Sz 1 Ci 40 0 ¾/25 一%/28 -⅝/25 64-9 5 0 0 1 0 0 ¾5 ⅝25 - 24 0 5 12 8 30 480 + 30c G一4 64 0 0 0 24-9） 5 S 注意，除了c，代替50，這個表單和先前的最優表單相同。因此，在目標函式係數行和C日列都有一個c，並且；和c一，行因為c，代替了50而重新計算。只要c，的職能滿足所有c，一，≤O，那麼當前解依然是最優解。所以，由S，列我們得到 1-6 5 —≤0 由S，列我們得到透過第一個不等式，我們得到 24-G 5 C-64≤0 或者 C≤64 （6-2） 同理，由第二個不等式，我們得到 24-G≤0 或者 24≤？ （6-3）
164 資料、模型與決策：管理科學篇因為c，必須同時滿足不等式（6-2）和（6-3），所以c，的最優範圍是 24≤C1≤64 （6-4） 為了瞭解高科技公司管理層如何運用靈敏度分析資訊，假設原材料成本的增長使得每臺桌上型電腦的利潤下降至30美元。最優範圍指出當前解（x，=30，*=12，S，=0,S2 =8,S=0）依然是最優解。 為了檢驗這個解，讓我們重新計算c，值下降至30後的最終單純形表。 基列。‘ 30 X2 40 0 30 40 1 0 0 0 0 0 -¾8 0 1 0 12 8 30 30 0 40 0 ¥% -8% 0 0 ⅝ ％ -% 1 380 因為對於所有變數c一2，≤0，解x=30，*=12，S，=0，82 =8，S3=0依然是最優解。也就是說， c=30和c，=50時的最優解相同。但是，要注意到桌上型電腦的單位利潤的下降會導致總利潤從1 980 美元下降到1380美元。 如果單位利潤進一步下降，比如說，降至20美元，結果會怎樣？根據表示式（6-4）給出的c」的最優範圍，我們看到c：=20超出了值域範圍。因此，我們知道這個大變化將使得一個新的基成為最優的。為了檢驗這個新基，我們把最終單純形表中c，的值改為20。 20 40 1 $2 40 0 20 0 20 0 40 0 0 ⅝/25 -%/25 -⅝25 4 -4 0 0 1 0 0 0 0 -⅜5 12 8 30 ⅝/25 -% 1 080 C一果然，當前解（x， =30，*=12,5； =0,52 =8 和S：=0）不再是最優解，因為淨估計行的s，列的元素值大於0。這個結果表明至少要再使用一次單純形迭代來獲得最優解。在先前的表單中繼續使用單純形迭代來驗證新的最優解需要16 今臺桌上型電腦和20件行動式機。 我們用來計算c，的最優範圍的過程適用於所有的基變數。計算非基變數最優範圍的過程更為簡單， 因為非基變數的目標函式係數的變化只會導致最終單純形表中相應的c，一z，的值發生變化。為了說明這個方法，下面我們用高科技公司問題的最終單純形表做演示，表中，的目標函式係數0用係數c，表示： 50 40 0 0 #2 40 0 50 0 1 -½25 0 50 0 40 0 0 1 0 0 0 ⅜8 ⅝/25 2% -2% 12 8 30 1 980 注意，表單中惟一的變化在s，列。運用不等式（6-1）來計算最優範圍，我們得到第6章基於單純形的靈敏度分析與對偶165 因此，：《所以，只要s，的目標函式係數小於或等於44 言，當前解就是鼓優的。由於係數下降的幅度沒有下限，我們給出c，的最優範圍為。《M 相同的方法可以應用於所有的非基變數。在最大化問題中，最優範圍沒有下限，而上限由給出。 因此，任何非基變數的目標函式係數的最優範圍為 9，≤z （6-5） 讓我們來總結計算目標函式係數最優範圍的必要步驟。在以下步驟裡，假設我們的目標是在最大化問題中計算c。的最優範圍，G是x。的係數。記住文中的x，可以表示任一初始決策變數、鬆弛變數或剩餘變數。 計算最優範圍的步驟第一步，用c代替在單純形表中出現的x。的目標函式係數值。 第二步，重新計算每個非基變數的c 一2，的值（如果x。是非基變數，則只需計算c一碗。的值）。 第三步，要滿足c一≤0，則分別當c取上下限時計算不等式。如果c，找到兩個或兩個以上的上限，那麼其中最小的就是最優範圍的上限。如果c找到兩個或兩個以上的下限，那麼其中最大的就是最優範圍的下限。 第四步，如果原問題是一個最小化問題，為了使用單純形法，要將其轉化為最大化問題，然後把第三步得到的不等式乘以-1，再改變不等式號，即得到原最小化問題的最優範圍。 當使用蝦優範圍來確定目標函式係數的變化是否會引起最優解的變化時，我們通常能夠避免用公式表示和求解更改後的線性規劃問題的過程。 6.1.2 右端值在很多線性規劃問題中，我們把右端值（即6，值）作為現有資源。例如，在高科技公司問題中，約束條件1的右端值表示現有的裝配時間，約束條件2的右端值表示現有的行動式機顯示器，而約束條件3表示現有的倉庫空間。對偶價格提供了在此基礎上的附加資源的資訊，其有效範圍由右端值的範圍決定。 對偶價格在第3章中我們已經說明，約束條件右端值每增加一單位所導致的最優解的增加量為對偶價格。°當使用單純形法解決線性規劃問題時，很容易得到對偶價格的值。它們可以在最終單純形表的x，行中找到。為了說明這一點，我們再看一次高科技公司問題的最終單純形表。 蒸列 50 0 40 1 0 Sz 40 0 50 1 50 0 0 40 0 一V28 -⅝/8 ⅛% -1% 0 0 1 0 0 0 0 12 8 30 1980 -2 一些作者常用另一個相關的術語———陰影價格。在最大化問題中，明影價格等同於對偶價格；在最小化問題中，閉影價格和對偶價格的絕對值是相同的，只是符號不同。LINDO/PC 和管理科學家把對偶價格作為電腦輸出的一部分。一些軟體包，比如Excel Solver，也提供陰影價格。
166 資料、模型與決策：管理科學篇 3個鬆弛變數的，值分別為'%，0，2。因此，裝配時間約束、行動式機顯示器約束和倉儲容量約束的對偶價格分別為1%=2.80美元，0.00和29 =5.20美元。對偶價格5.20美元表示倉儲容量的增加將對高科技公司的利潤產生最大的影響。 為了理解為什麼最終單純形表中鬆弛變數的z，值就是對偶價格，讓我們首先考慮鬆弛變數是最優可行解的一部分的情況。每個鬆弛變數的z，值都為零，表示相應約束條件的對偶價格為零。例如， 考忠高科技公司中的一個基變數，鬆弛變數S2。因為在最優解中5=8，所以高科技公司將有8臺便攜式機顯示器閒置。結果，高科技公司的管理層願意花費多少來購買額外的行動式機顯示器？顯然答案是零，因為在最優解中這種部件過多。這種資源的多餘對公司毫無價值，因此，這個約束條件的對偶價格為零。一般地，如果一個鬆弛變數是最優解中的基變數，，值—相對應的對偶價格—為零。 現在考慮非基鬆弛變數—例如，S」。在前面，我們確定，只要S，的目標函式係數（記為c，）在以下範圍內，那麼當前解就仍然是最優的： 這說明量s，不應該再增加，除非它的值大於「%=2.80美元。我們由此可以得出結論，2.80美元是高科技公司每小時裝配桌上型電腦和行動式機的邊際價值。所以，如果可以，高科技公司需要為每小時的額外時間支付2.80美元。相似的說明可以用於每個非基鬆弛變數的z，值。 對於大於或等於約束，對偶價格的值將會小於或等於零，因為右端值增加一單位並無意義，只會使它更難滿足約束條件。對於一個最大化問題，當大於或等於約束條件的右端值增加時，最優值將會下降。對偶價格給出了期望增量——一個負數，因為我們預期減少。結果，大於或等於約束的對偶價格由最優單純形表中的，的相反數給出，2；表示剩餘變數。 最後，等式約束的對偶價格也可以計算出來。它們由相應的人工變數的z，值給出。在此，我們不再詳細解釋這種情況，因為我們建議只要能用相應的人工變數換出基，就立即從單純形表中刪除人工變數列。 小結一下，當使用單純形法解決線性規劃問題時，約束條件的對偶價格包含在最終單純形表中。 表6-1總結了使用單純形法解決最大化問題時，確定不同型別的約束條件的對偶價格的基本規則。 回想一下，當我們遇到最小化問題，使用單純形法之前，透過把目標函式乘以-1來將問題轉化為最大化問題。然而，對偶價格同樣是由z，的值給出，因為在最小化問題中的增加就是最優值的減少。 為了說明計算最小化問題的對偶價格的方法，回想一下我們在第5.7 節裡解決的M&D公司問題， 該問題透過把目標函式乘以-1轉化為等價的最大化問題。這個問題的線性規劃模型和最終單純形表羅列如下，其中x，和*，分別表示產品A和B的數量。 min 2%1 +382 S.t. Lx ≥ 125 Lx + 1x≥350 2x +1x2≤600 對產品A的需求總產量加工時間 X,2≥0 裝刻 -2 1 $1 -2 一3 0 「一3 -2 0 -3 0 1 0 -3 0 0 0 0 1 0 0 0 1 -2 1 4 -4 0 1 -1 1 1 -1 250 100 125 -800
第6章基於單純形的靈敏度分析與對偶 167 根據表6-1中確認每種約束型別的對偶價格的規廁，在表6-2中列出了M&D公司問題中約束條件的對偶價格。 喪6-1 對偶價格在最終單純形表中的體現 （按照約束條件的型別劃分） 約束型別對偶價格決定因素與約東條件相關的鬆弛變數的z；值 ≥ 非與約束條件相關的剩餘變數的，值的相反數與約束條件相關的人工變數的z；值表6-2 M&D公司問題中的對偶價格約束條件對產品A 的需求總產量生產時間約束條件型別 ≥ ≥ ^ 對偶價格 0 -4 1 約束條件1是非束縛性的，其對偶價格為零。約束條件2的對偶價格表明，增加總產量所需的邊際成本為每單位4美元。最後，第三個約束條件的對偶價格表明額外的加工時間所創造的單位價值為 1 美元。 可行範圍我們可以看到，最終單純形表的z，行可以用來確定對偶價格，並由此預計對應於6，一單位變化的目標函式值的變化。只要b：的變化沒有大到使得當前基解不可行，這個方法就是正確的。 所以，我們有必要計算出在保證現有的基變數可行（例如，不能小於零）的條件下b，的變化區域，這個值域可稱為可行範圍。 為了說明6，的變化造成的影響，考慮一下將高科技公司問題中的可行裝配時間從150小時增加到 160 小時。那麼當前基還能產生可行解嗎？如果能，在已知裝配時間約束條件的對偶價格為2.80美元的情況下，我們可以預計到解的值會增加，為10x2.8=28。下面是裝配時間增加10小時後的最終單純形表。 甚列 50 0 40 0 0 0 Xz §z 40 0 50 1 0 50 0 40 0 ⅜25 -⅝5 -⅝/25 1⅘ -1% 0 0 -¾25 ¾/25 ⅝/25 15.2 4.8 28.0 0 2 008 0 -2 同樣包含了基變數x2，82，x，的基是可行的，因為所有的基變數都是非負的。同時也要注意到，正如我們所料，使用對偶價格，最優解的值增加了10x2.80 =28 美元，由1980美元增加到2008美元。 你也許會想我們是否必須徹底重新解決這個問題以找到這個新解。答案是否定的！最終單純形表中惟一的變動（與b，=150時的最終單純形表比較）是基變數的值和目標函式的值。也就是說，只有單純形表的最後一列發生了變化。單純形表新的最後一列的項是把S，列的前4項擴大10倍後增加到原表中。 以前的解，的變化 5，列新解新解= 12 8 30 1980 + 10 -⅜25 = 1%」 15.27 4.8 28.0 22008
168 資料、模型與決策：管理科學篇現在，讓我們思考為什麼這個過程可以用來找到最優解。首先，回憶一下，S，列的每個係數表示增加每單位s，都會導致基變數的減少。換句話說，這些係數告訴我們向解中換人每單位的S，變數會使得多少單位的當前基變數被換出解。但是，將1單位的s，換入解等同於減少1單位的可用裝配時間 （即減少b，）；增加1單位b，（即裝配時間）則導致相反的結果。於是，S，列每一項代表的也是1單位 b，的增加導致的當前基變數的變化。 1單位6，的增加導致目標函式值的變化由那列的z，值（即對偶價格）給出。在前面的例子中，可用裝配時間增加了10個單位。因此，我們將，列的前4項乘以10來得到基變數和最優值的變化。 我們怎樣能夠得知b，的變化已大到使得當前基不可行呢？我們首先以高科技公司問題為例來回答這個問題，然後給出小於或等於約束的一般步驟。接著，討論大於或等於約束的情形。 一開始，我們先演示如何計算在保證當前最優基可行的條件下，6，可以變化的上限和下限。我們已經知道在6，增加10單位時如何找到新的基可行解。一般地，給出b，的變化Ab，則高科技公司問題的基變數的新值由下式決定。 12 + 25 25 FA6， 12 8 +A6： 30 - 25 = 8-S4 （6-6） 25130-元40」 只要每個基變數的新值保持非負，當前基就依然是可行的，因此也是最優的。我們限制6，的變化 （也就是A6，）以保證基變數非負，因此滿足了以下每個條件： 12+240，≥0 （6-7） 8-號2620 （6-8） 30-340，≥0 （6-9） 不等式的左邊表示的是當Ab，代替6，後基變數的新值。 解不等式（6-7）、不等式（6-8）、不等式（6-9），得 46.≥2 一×（-12）=~37.5 46， ≤（-晉）× （-8） =25 Ab，≤（-碧）×（-30）-150 因為3個不等式都要滿足，對b，的最大限制的約束是必須滿足所有當前基變數保持非負。 因此，Ab，必須滿足 -37.S≤Ab， ≤25 （6-10） 可用裝配時間的初值是150小時。因此，b，=150+A0，這裡，b，表示可用裝配時間。我們給不等式（6-10）中的3項同時加上150，得 150-37.5≤150 + 46， ≤150 +25 （6-11） 用6，代替 150+Ab、，從而得到b，的可行範圍： 112.5≤b，≤175 b，的可行範圍的含義是隻要可用裝配時間在112.5和175 小時之間，當前最優基依然是可行的，這也是我們之所以把它稱為可行範圍的原因。 因為b，（即裝配時間）的對偶價格是「%，所以我們知道多一個小時的裝配時間，利潤可以增加第6章基於單純形的靈敏度分析與對偶 169 2.80美元。假設我們把6，增加25，也就是說，b，增加到可行範圍的上限175，利海將增加到1980+ 2.80 x25=2 050 美元，最優基變數的值為 *=12+25x3 25=20 3=8+25x（-號）=0 元，=30+25x（一訪）=25 那麼解將變化嗎？裝配時間的增加導致需要重新審訂最優生產計劃。高科技公司需要加大行動式機的生產，減少桌上型電腦的生產。總的來說，利潤將增加2.80x25=70美元。注意，雖然最優解改變了，但是先前的最優基變數仍是最優的。 我們已經演示了以裝配時間約束為例確定可行範圍的步驟。計算任何小於或等於約束右端值的可行範圍的步驟是相同的。對於通用約束條件i的第一步是計算滿足下列不等式的6；的值域。 a 「o 0： + 46： （6-12） 可m」 LO_ 現在的解（最終單最終單純形表中約束條件i的純形表的最後列） 鬆弛變數相對應的列上述不等式是用來確定Ab，的上限下限的。可行範圍就由下限的最大值和上限的最小值決定。 同理，也可以計算大於或等於約束條件的右端值的可行範圍。基本的步驟是相同的，其中一列對應的剩餘變數是對應具有重要角色的約束條件的。對於一個一般的大於或等於約束條件i，我們首先要計算滿足下列不等式（6-13）的26，的值域。 萬 「o7 •： -4b， ≥ 0： L0」 （6-13） 現在的解（最終單最終單純形表中約束條件i的純形表的最後列） 剩餘變數相對應的列同理，上述不等式是用來確定Ab，的上限和下限的。給出這些界限，可行範圍就很容易確定了。 等式約束右端值的可行範圍也能計算出來。為了計算等式約束條件，我們將最終單純形表中對應人工變數的一列等同於方程（6-12）中的約束條件；。因為我們建議，只要人工變數變成非基的，就從單純形表中除去人工變數所在的列，也不會出現在最終單純形表中。於是，還需要更多的計算來求出等式約束條件的可行範圍。在一些高階教材中有更多的敘述。 只要右端值的變化使6：在可行範圍內，同樣的基依然是可行的和最優的。一旦b，的變化超出可行範圍，我們就不得不重新解決問題以找到由另一組基變數組成的新的最優解。（一些更高深的線性規劃教材還提供了不用完全重新解決問題就能找出最優解的方法。）無論如何，計算6：的可行範圍都是極其有用的管理資訊，在任何線性規劃專案中都是作為管理報告的一部分收錄進去的。可行範圍作為
170 資料、模型與決策：管理科學篇計算機求解問題的一部分尤其有用。 6.1.3 同步變化回顧求最優範圍和可行範圍的步驟，我們注意到一次只允許一個係數發生變化。我們求域的整個過程都建立在一個前提上：其他係數不允許變化。但是，有時當兩個或多個目標函式係數或者兩個或多個右端值同步變化時我們能得出相同的結論。當同步變化滿足100%法則時，相同的結論依然適用。 100% 法則在第3章有所論及，這裡我們再簡單地複習一下。 讓我們把可允許的增加定義為係數在不超過其域上限的範圍內可增加的量，把可允許的減少定義為係數在不超過其域下限的範圍內可減少的量。現在假設兩個或兩個以上的目標函式係數同步變化。 對每個變化的係數，我們計算可允許的增加百分比或可允許的減少百分比。如果所有變化的百分比不超過100%，我們就說滿足了100%法則，這些同步變化不會引起最優解發生變化。但是，只有一個目標函式係數發生變化，那麼係數的變化會引起解的值改變。 同理，如果約束條件右端值發生兩個或多個變化時，我們要再計算一遍每個變化引起的可允許的增加百分比或可允許的減少百分比。如果所有變化的百分比不超過100%，我們就說滿足了100%法則。接著，對偶價格可以用來確定目標函式隨著右端值的變化而發生的值的變化。 註釋與評論 1.有時候，解釋對偶價格和選擇合適的符號會令人困惑。下面的介紹對考慮這個問題有所幫助。 放寬一個≥約束條件是指減少它的右端值，放寬一個≤約東條件是指增加它的右端值。放寬約東條件允許增加值；縮緊約束條件（即減少≤約東條件的右端值或增加≥約東條件的右端值）則有相反的效果。在任何一種情況中，對偶價格的絕對值隨著約東條件的效寬而提高最優解的值。 2.第3章中關於靈敏度分析的註釋與評論同樣適用於此。尤其，回憶起100%法則不適用於目標函式和右端值的同步變化，它僅這用於目標函式或右端值的同步變化。同時也要注意到，這個法則並不意味著不滿足此法則的同步變化必然會引起解的變化。例如，所有的目標函式係數呈等比例變化將不改變最優解，所有的右端值呈等比例變化將不改變對偶價格。 6.2 對偶如果一個線性規劃問題附帶著另一個線性規劃問題，則被附帶著的問題稱為對偶問題。把線性規劃問題的初始模型稱為初始問題，我們來看看初始問題如何轉化為對應的對偶問題。然後，我們來解決對偶線性規劃問題並得出結果。初始-對偶關係的一大特點就是初始問題和對偶問題任一得出的最優解也是另一個問題的最優解。在這種情況下，當初始問題和對偶問題在計算難度上有差別時，我們可以選擇相對簡單的同題來解決。 讓我們回到高科技公司問題。初始模型——初始問題如下： max SOx；+ 40x2 S.t. 3x1 + 5x： ≤ 150 1x≤ 20 8x， + 5x2 ≤ 300 裝配時間行動式機顯示器倉庫空間 X,2≥0 小於或等於約束條件和變數要求非負的最大化問題被稱為最大化問題的標準型。對於標準型的最大化問題，比如高科技公司問題，轉化為對應的對偶問題相對簡單。讓我們列出高科技公司問題的對偶問題，然後確定初始-對偶轉化的過程。高科技公司問題的對偶問題如下：
第6 章基於單純形的靈敏度分析與對偶 171 min S.t. 150u+2042+300us + &ug ≥50 Su + Iuz + Sis ≥40 比，H20 43≥0 最小化問題的標準型是大於或等於約束條件和變數要求非負的最小化問題。因此，最大化問題標準型的對偶問題就是最小化問題的標準型。變數比」、14，和 4，被稱為對偶變數。 根據先前的例子，我們得出求最大化問題標準型的對偶問題的一般方法： 1.對偶問題即最小化問題的標準型。 2. 當初始問題有n個決策變數（在高科技公司問題中n=2），則對偶問題有n個約束條件。對偶問題的第一個約束條件對應於初始問題中的變數x，對偶問題的第二個約束條件對應於初始問題中的變數x，依此類推。 3.當初始向題有 m 個約束條件（在高科技公司問題中m=3），則對偶問題有n個決策變數。對偶變數u，對應於初始問題中的第一個約束條件，對偶變數u，對應於初始問題中的第二個約束條件， 依此類推。 4.初始問題約束條件的右端值成為對偶問題的目標函式係數。 5. 初始問題的目標函式係數成為對偶問題約束條件的右端值。 6. 第i個初始變數的目標函式係數成為對偶問題中第；個約束條件的係數。 以上6步是把最大化問題的標準型轉化為對應的對偶問題（即最小化問題）的標準型所必須滿足的一般要求。即使這些要求最初看來比較麻煩，但是透過一些簡單問題的實際操作，會發現初始一對偶轉化過程相對容易實施。 我們已經建立了高科技公司對偶線性規劃問題的模型，所以現在讓我們來解這個問題。當對偶問題中含有3個變數時，我們使用單純形法。除去剩餘變數S，和§2，得到標準型；增加人工變數a，和 42，得到表單形式；把目標函式乘以-1，得到等價的最大化問題的對偶問題。之後，我們得到了如下所示的初始單純形表： -M 一M -150 -20 -300 0 O -M -M 3 5 0 ⑧ 5 -1 0 0 1 -1 0 -8M 一M -13M M M -M-M -150 +8M -20 +M -300 + 13M -M -M 0 0 1 0 50 40 -90M 在第一次迭代中，將1，導人基，匯出c」。在第二次迭代中，將u，導人基，匯出0。此時，單純形表如下： Hs -300 -150 -150 0 1 -150 0 -20 -12 -8 一300 1 O -300 0 0 -⅝/28 30 -30 0 -%26 12 -12 ¾% ⅒% -1 980 因為淨估計行的所有項都少於或等於0，所以最優解就得到了；即比=1%，42=0，43=39，S1= 0，S2=0。我們已經將對偶問題中的目標函式的負值最大化，所以，對偶問題的最優解的目標函式值
172 資料、模型與決策：管理科學篇為 （-1980）=1980。 初始高科技公司問題的最終單純形表如下： 蒸列 Xz Sz Xi 50 0 40 0 40 0 50 1 0 0 0 -⅜5 0 -⅝25 1 0 -⅝/25 0 50 40 1% 0 2% 12 8 30 1 980 0 0 -1 0 -2 初始問題的最優解是x，=30，*=12，S，=0，S=8，S=0。目標函式的最優值是1980。 從初始目標函式的最優值和對偶目標函式的最優值的關係中我們可以觀察到什麼？二者的目標函數的最優值相同，都為1980。這個關係對於所有的初始線性規劃問題和對偶線性規劃問題都成立， 這一關係可以被表述為性質1。 性質1 如果對偶問題有一個最優解，那麼對應的初始問題也必有一個最優解，反之亦然。而且，對偶問題和初始同題的最優解的值都是相等的。 這個性質告訴我們，即使我們只解出了對偶問題，我們仍可以知道高科技公司將會實現最大值1980美元。 6.2.1 對偶變數的經濟學解釋在對初始解和對偶解的關係做進一步的研究之前，讓我們來考慮對偶變數比4，12和1，的意義或者說是解釋。記住，在建立對偶問題的過程中，每一個對偶變數都對應於初始問題中的一個約束條件。具體而言，u，與裝配時間約束條件相關，1，與行動式機顯示器約束條件相關，而1，與倉庫空間約束條件相關。 為了瞭解和解釋這些對偶變數，讓我們回到關於初始-對偶問題關係的性質1，這一性質指出初始問題和對偶問題的目標函式值一定相等。在最優解中，初始目標函式的結果如下： 50x，+40x2 =1 980 （6-14） 而對偶目標函式為 150u， +20u+300us =1 980 （6-15） 運用式（6-14），使我們的關注點侷限於對於初始目標函式的解釋上。設x，和x，分別為裝配的桌上型電腦和行動式機的數量，我們得到 （每臺桌上型電腦的價格）×（桌上型電腦的數量）＋（每臺行動式機的價格）x（行動式機的數量）= 產品的總價值透過式（6-I5），我們看到對偶目標函式的係數（150，20，300）可以被解釋為可利用資源的數量。 因此，由於初始目標函式和對偶目標函式的最優值是相等的，我們得到 （資源1的數量）4」＋（資源2的數量）442＋（資源3的數量）4；=產品的總價值因此我們看到，對偶變數必須理解為每個單位資源的價值。對於高科技公司問題來說， 4，—單位裝配時間的價值； 4，—單位行動式機顯示器的價值； 4，—單位倉庫空間的價值。 那麼我們以前是否曾經試圖得到這些資源的價值呢？回憶一下在第6.1節中，當我們考慮了右端第6章基於單純形的靈敏度分析與對偶 173 值的靈敏性分析，我們求出了每種資源每增加一單位的價值。這些值被稱為對偶價格，有助於制定是否需要額外的可用資源的決策。 由第6.1節的分析得出如下表所示的高科技公司問題中各種資源的對偶價格。 現在讓我們回到高科技公司對偶問題的最優解。最資源優解中的對偶變數的值為1，=1%=2.80，比2=0，比= — 裝配時間 296 =5.20。對於這個最大化問題而言，對偶變數的值行動式機顯示器和對偶價格是相同的。對於一個最小化問題而言，對偶倉庫空間單位附加價值（對偶價格） $2.80 $0.00 $5.20 價格和對偶變數的絕對值相等但是符號相反。因此，對偶變數的最優值可以確定為最優解中追加的每單位資源或投人的對偶價格。 透過前面的討論，當初始問題是一個產品混合問題時，我們得到如下所示的關於初始問題和對偶問題的解釋。 初始問題給定每一種產品的單位價值，求每種產品應生產多少以使總產出的價值達到最大化。 約束條件要求每種資源的使用量必須小於或等於現有資源的數量。 對偶問題給定每一種資源的現有數量，求每種資源的單位價值以使所用資源的總價值達到最小化。約束條件要求每單位資源的價值大於或等於每單位產出的價值。 6.2.2，用對偶變數確定初始解在這一節的開頭，我們提到初始-對偶關係的一個重要特徵是當得到最優解時，初始問題的最優解值與對偶問題的最優解值相等；參看性質1。但是，問題仍然存在：如果我們僅解對偶問題，那麼我們是否能確定初始變數的最優值？ 回憶一下在第6.1節中，我們指出，當使用單純形表解決了初始問題，初始變數的最優值就會出現在最終單純形表的最右邊的列，對偶價格（即對偶變數的值）在z，行中能夠找到。對偶問題的最終單純形表提供了對偶變數的最優值，因此初始變數值可以在最優對偶表單的z，行中找到。事實上就是這種情況，而這個結果可以被正式地表述為性質2。 性質2 給定與最優對偶解相關的單純形表，則初始決策變數的最優值將會在剩餘變數的項中給出；而初始鬆弛變數的最優值就是變數，的c，一z，項的相反數。 這個性質使我們可以使用高科技公司對偶問題的最終單純形表來確定出最優初始解，即x，=30單位的桌上型電腦和 x，=12單位的行動式機。x，和*，的最優解以及所有鬆弛變數的值，在對偶問題的最終單純形表的z，行和c，一行中給出，如下： M4g -300 -150 -150 0 1 -150 0 -20 -300 -%% 1 ⅝/s 0 -12 -300 -8 0 0 -⅝5 30 -30 0 ⅜ -% 12 -12 -1980 6.2.3 任意原問題的對偶問題高科技公司初始問題提供了對於對偶概念的很好的介紹，因為這個問題是以最大化問題的標準型
174 資料、模型與決策：管理科學篇建立模型的。對於這一形式的初始問題，我們證明了將其轉化為一個對偶同題是比較簡單的。如果初始問題是一個最小化問題的標準型，那麼其對偶問題就是一個最大化問題的標準型。因此，找到最小化問題的標準型的對偶問題也是比較簡單的。考慮如下最小化問題的標準型的線性規劃： min 6oxt， + 282 s.t. Sx-1x2≥ 13 3x+7x≥9 其對偶問題就是下述標準型的最大化問題： max s.t. 13u；+9u2 Su + 3u2≤ 6 -luy + 7u2 ≤2 41,62≥0 儘管我們可以給出一整套將每一種初始問題轉化為與之相關的對偶問題的規則，但是我們相信， 如果首先將任何一個初始問題轉化為一個標準型的等價問題，那麼更容易一些。然後，我們根據步驟來找出最大化或者最小化問題的標準型對偶問題。 min 2x1-3x2 S.t. Ixy +282≤12 4x-2x2≥3 6x- 1x2=10 X1，%≥0 對於最小化問題，我們透過把所有的約束條件轉化為大於或等於形式而得到標準型。約束步驟如下： 第1步：透過將不等式兩邊同乘以-1，把第一個約束條件轉化為大於或等於形式。由此得到 -4-2×≥-12 第2步：約束條件3是一個等式約束。對於一個等式約束條件，我們首先建立兩個不等式：一個為≤形式，一個為≥形式。由此得到 6x，-1x≥10 6x1-1x2≤10 然後，我們將≤約束條件乘以-1，便得到兩個≥約束條件。 6x」-1%2≥10 -6x+1%≥-10 現在初始問題可以透過以下的等價形式來表述： min 2%1-3x2 S.t. -Ix-2%2≥-12 4x-2%2> 3 10 -6x+1x2≥-10 X1X2≥0 現在透過將初始問題轉化為一個標準型的最小化問題，我們就可以簡單地用在這一節前面提到的初始-對偶轉化步驟將原問題轉化為對偶問題。對偶問題°變為 ◎ 注意，第二個約束條件的右端值為負值，因此，我們將約束條件兩邊同乘以-1，以便在使用單純形法解決問題之前使右端值變為正值。
第6章基於單純形的靈敏度分析與對偶 175 max -12u；+3u2+10u- 10u3 S.L. -Iu +4u+ Gu- 6ug≤2 -2M-242- lug+lugs-3 Hj,4420445,4≥0 等式約束條件要求有兩個≥約束，所以我們用w’，和w”來表示與這些約束條件相關的對偶變數。 這個符號提醒我們：’；和u”，都代指原先初始問題的第三個約束條件。因為兩個對偶變數都與一個等式約束條件相關，那麼對於對偶變數的解釋便必須稍微進行一下修改。等式約束條件6x，-1*=10的對偶變數由w'一 ”。在對偶問題的最優解中給出。因此，一個等式約束條件的對偶變數可以為負值。 本章小結在本章中，我們指出瞭如何利用最終單純形表中的資訊來進行靈敏度分析。靈敏度分析包括計算目標函式係數的最優範圍、對偶價格以及右端值的可行範圍。一般而言，靈敏度資訊成為大多數線性規劃計算機軟體的解決報告的一部分。 我們在這裡強調，靈敏度分析是建立在假設基礎上的，這個假設就是一次只允許一個係數發生改變；而其他所有的係數都要保持原有的值。一次改變一個以上的係數，做一些有限的靈敏度分析來看改變的結果也是可行的；在這種情況下，前面提到的100%法則仍然有用。 透過學習對偶，我們看到了原線性規劃問題或者稱為初始問題是如何轉化為與之相關的對偶線性規劃問題的。解初始問題或對偶問題中的一個，都可以得到另一個問題的解。我們學到，對偶變數的值指出了初始問題中的經濟貢獻或者追加資源價值。 專業術語 Fange of optimality 最優範圍不會導致最優解改變的目標函式係數的變化範圍（這時，所有變數的值都保持不變，但是目標函式的值可能發生變化）。 dual price 對偶價格約束條件右端值每增加一單位所導致的最優解的增加量。 range of feasibillty 可行範圍不會導致當前基解變為不可行的b，的變化範圍。解中的各個變數的值都可以發生變化，但是原來的基變數依然是基變數。在該範圍內，約束條件的對偶價格不會發生改變。 dual probler 對偶問題與初始問題相關聯的一個線性規劃問題。由對偶問題的解可以給出初始問題的解。 primal problem 初始問題對於一個線性規劃問題最初建立的模型。 canonical form for a maximization problem 最大化問題的標準型所有約束條件都為小於或等於形式，且決策變數都必須非負的最大化問題。 canonical form for a minimization problem 最小化問題的標準型所有約束條件都為大於或等於形式，且決策變數都必須非負的最小化問題。 dual variable 對偶變數一個對偶線性規劃問題中的變數。它的最優解即為相應原問題的資源的對偶價格。 問題 2. 在高科技公司問題中，我們找出了c的最優解值域，C，為每單位的桌上型電腦的利潤。而在第6.1 節中，我們給出了最終單純形表。請找出下列問題的答案。 a.G的最優範圍。 b.表e，的最優範圍。 c•c，的最優範圍。 d. 假設行動式機（c）的每單位利潤下降至35 美元，那麼最優解將如何改變？而總利潤的新值又為多少？ 4.請參閱問題1的問題解決過程以及最優單純形表。 8.找出6，的可行範圈。 b.找出6的可行範圍。
176 資料、模型與決策：管理科學篇 c.求出6的可行範圍。 6.請回憶第2章中的Par 公司問題，這個問題的線性規劃如下： max 10x + 9x2 S.t. ox+ 1x2≤ 630 ½%1+⅝×2≤600 Ix， +⅜*2 ≤708 Yox，+ ¼xs 135 XX2≥0 這裡，x，表示標準袋產量；*，表示高階袋產量。 最終單純形表為： 切制與印染縫合成型檢公與包裝基列 $z S4 9 9 0 10 0 10 0 0 9 0 0 0 1 0 0 0 10 0 9 0 0 -1⅝ 1 -28 0 0 ™ie 17916 0 0 0 -28 ⅝aa 3%8 ⅝a 0 0 0 1 252 120 540 18 7 668 -1½6 0 0 a.計算標準袋的貢獻毛益的最優範圍。 b.計算高階袋的貢獻毛益的最優範圍。 c.如果高階袋的單位利潤降至7美元，那麼最優解會受到什麼樣的影響？ d.單位高階袋的貢獻毛益達到多少，才會使Par 公司改變其現有的生產計劃？ e•如果高階袋的貢獻毛益可以增至每單位15 美元，那麼最優生產計劃是什麼？在你計算出新的最優解之前，說說你覺得會發生什麼變化。 8.A.計算 Par 公司問題（參見問題6）中的6，從630增至682%後的最終單純形表。 b.如果b，增加得更多，那麼現在的基是否是最優的？如果不是，那麼新的最優基又是多少？ 10. 以下為Par 公司問題（參見問題6）的追加條件： 日.因為使用新機器，用於切割與印染一單位標準袋的時間（約束條件1）稍稍減少。這一減少會對目標函式有何影響？ b.管理層相信透過購買一臺新的縫紉機，一單位標準袋的縫合時間將從½小時減至小時。你認為購買一臺新機器是一個好的投資方案嗎？為什麼？ 12. 參閱問題11。 a.計算6、（原料1的可獲得性）的可行範圍。 b.計算6（原料2的可獲得性）的可行範圍。 c.計算6（原料3的可獲得性）的可行範圍。 d.原料3的對偶價格是多少？在，的值域中，這一對偶價格是否成立？ 14. 思考如下的最終單純形表： xs 3 %0 186/60 42 $%60 0 1 0 ½ -½ ½ ¾0 -⅝0 -½0 -½0 6 0 0 -½ -⅜0 0 1 0 0 0 -%0 -1 1⅔80 125 425 25 $25 1$4/80