第三章線性規劃的靈敏度分析與最優解的解釋講授人：朱玉春教授單位：經濟管理學院

2011年西北農林科技大學引言

靈敏度分析是研究當一個線性規劃問題中的系數發生變化時，其對函數最優解的影響程度。運用靈敏度分析，我們可以回答以下問題：1.如果目標函數的系數發生了變化，對最優解會產生什么影響？2.如果改變約束條件的右端值，對最優解會產生什么影響？首先我們將介紹如何使用圖解法進行雙變量線性規劃問題的靈敏度分析，然后介紹如何使用管理科學家軟件得到靈敏度分析報告。本章主要內容3.1靈敏度分析簡介3.2圖解法靈敏度分析3.3靈敏度分析：計算機求解3.4多于兩個決策變量的情況3.5電子通信公司問題3.1靈敏度分析簡介

靈敏度分析對于決策者的重要性不言而喻。在真實世界里，周圍的環境，條件是在不斷變化的。原材料的成本在變，產品的需求在變，公司購買新設備、股票價格的波動，員工流動等等這些都在不斷發生。如果我們要用線性規劃模型去解決實際問題，那模型中的系數就不可能是一成不變的。這些系數的變化會對模型的最優解產生什么樣的影響呢？運用靈敏度分析，我們只需要改變相應的系數就可以得到答案，而不需要建立新的模型。3.1靈敏度分析簡介回憶Par公司的問題：我們已經知道這個問題的最優解是標準袋生產540個，高級袋生產252個，這個最優解的前提是每個標準袋的利潤是10美元，每個高級袋的利潤是9美元。3.1靈敏度分析簡介假設，我們得知由于價格的下降，標準袋的利潤由10美元下降到8.5美元。這時我們可以用靈敏度分析來確定標準袋生產540個，高級袋生產252個是否還是最優解。如果還是，則不必建立新的模型求解了。靈敏度分析還可以用來分析模型中的系數哪個更能左右最優解。比如，管理層認為高級袋的利潤9美元只是一個估計量，如果通過靈敏度分析得到高級袋的利潤在6.67和14.29美元之間變化時，模型的最優解都是540個標準袋和252個高級袋，那么管理層就對9美元這個估計量和模型所得出的最優產量比較滿意。但是，如果靈敏度分析告訴我們只有當高級袋的利潤在8.9和9.25美元之間，模型的最優解才是540個標準袋和252個高級袋，那么管理層就必須思考9美元這個估計量的可信程度有多大了。3.1靈敏度分析簡介

靈敏度分析的另一個用途是分析約束條件的右端值變化對最優解的影響。還是以Par公司為例，在最優產量的情況下，切割與印染部門和成型部門的工作時間已經完全被占用了。如果現在公司增加了這兩個部門的生產能力，那么最優解以及總利潤的值會發生什么樣的變化呢？靈敏度分析可以幫助確定每一個工時的邊際價值，以及在利潤下降之前部門工時的最大增加量。3.2圖解法靈敏度分析

對于雙變量的線性規劃問題，當目標函數的系數或約束條件的右端值變化時，用圖解法對其進行靈敏度分析。我們先思考目標函數的系數變化會對Par公司的最優產量產生什么樣的影響。選擇每個標準袋的利潤是10美元，每個高級袋的利潤是9美元，如果其中一種袋子利潤下降，公司就會削減其產量，如果利潤上升，公司就會增加其產量。究竟利潤變化多少，管理者才應該改變產量呢？現在，模型的最優解540個標準袋和252個高級袋。每個目標函數系數都有一個最優范圍，即目標函數系數在什么范圍內變化，模型的最優解保持不變。3.2圖解法靈敏度分析

3.2.1目標函數系數

認真觀察圖發現，只要目標函數直線的斜率處于直線A（和切割與印染約束線重合）的斜率與直線B（與成型約束線重合）的斜率之間，極點3（S=540，D=252）就是最優解的點。改變目標函數里S和D的系數，引起目標函數直線斜率的變化，即繞著極點3旋轉。只要目標函數直線仍在陰影區域內，極點3仍是最優解。3.2圖解法靈敏度分析

逆時針轉動目標函數直線，使其斜率變成一個絕對值更小的負數，從而斜率變大了。直到與A重合，我們就獲得了多重最優解——在極點3和極點4之間的點都是最優點。因此A的斜率是目標函數直線的上限。順時針轉動目標函數直線，使其斜率變成一個絕對值更大的負數，從而斜率變小了。直到與B重合，我們又獲得了多重最優解——極點3和極點2之間都是最優點。因此B的斜率是目標函數直線斜率的下限。因此，極點3總是最優解點，只要直線B的斜率≤目標函數直線的斜率≤直線A的斜率3.2圖解法靈敏度分析

根據直線A和直線B的表達式，可以算出A的斜率是-7/10，截距是630。B的斜率是-3/2，截距是1062。則直線A和直線B的斜率都已經計算出來了，我們來看保持極點3仍然為最優解點，應滿足條件：-3/2≤目標函數的斜率≤-7/103.2圖解法靈敏度分析

現在讓我們考慮目標直線斜率的一般形式。用CS表示標準袋的利潤，CD表示高級袋的利潤，P表示目標函數值。使用這些標識，目標函數直線可以寫成：P=CSS+CDD

把上面方程寫成斜截式，得到CDD=-CSS+P

以及D=-S(CS/CD)+P/CD

因此我們看到只要滿足下列條件，極點3就仍然為最優解點：-3/2≤-CS/CD≤-7/103.2圖解法靈敏度分析

為了計算標準袋利潤最優的范圍，我們假設高級袋的利潤CD=9，代入上式得-3/2≤-CS/9≤-7/10

從左邊的不等式得到-3/2≤-CS/9或者3/2≥CS/9

從右邊的不等式得到-CS/9≥-7/10或者CS/9≥7/10

綜合標準袋利潤CS的極限，標準袋最優范圍為6.3≤CS≤13.53.2圖解法靈敏度分析

因此，只要標準袋的利潤在6.3美元與13.5美元之間，540個標準袋和252個高級袋總是最優產量。值得注意的是，即使產量不變，總的利潤也可能由于每一個標準袋利潤的變化而變化。這些計算可以重復進行，假設標準袋的利潤為常數CS=10，如此一來，高級袋的利潤的最優范圍就能夠確認，這個范圍是6.67≤CD≤14.29。3.2圖解法靈敏度分析

當目標函數繞最優點旋轉，使之與坐標軸垂直時，像式中出現的那種斜率的上限或下限就不存在了。為了說明這種特殊情況，我們設Par公司的目標函數為18CS+9CD；這樣，圖中，極點2是最優解點，繞著極點2逆時針旋轉目標函數，當目標函數與直線B重合時，就得到了斜率的上限-3/2。所以目標函數斜率上限一定是-3/2。最后當目標函數垂直于坐標軸時，其斜率接近負無窮大，在這種情況下，目標函數的斜率沒有下限，只有上限-3/2。-CS/CD≤-3/23.2圖解法靈敏度分析

按照前面假定的CD的值，仍為常數9，我們得到-CS/9≤-3/2或者CS/9≥3/2

解出CS，得CS≥27/2=13.5

我們注意到，只要CS的值大于等于13.5，極點2仍然是最優解點，因此我們得到以極點2為最優解的CS的范圍，如下13.5≤CS＜∞3.2圖解法靈敏度分析

多系數同時改變目標函數系數的最優范圍只能夠應用于一次只有一個系數發生改變的情況，其他系數都假定保持初值而不發生改變。如果兩個或兩個以上目標函數的系數被同時改變，就有必要進一步判斷最優解會不會也發生變化。對于解決只有兩個變量的問題時，簡單的計算出在新的系數值下目標函數的斜率（-CS/CD），如果這個比值大于等于目標函數斜率的下限，同時小于等于目標函數斜率的上限，那么系數值的變化不會使最優解發生變化。3.2圖解法靈敏度分析

觀察最優范圍，我們得出結論，無論是CS升高到13美元還是使CD降低到8美元（但不是同時改變），都不會帶來最優解的變化。但當CS與CD同時改變時，目標函數斜率的變化導致了最優解的變化。這個結論強調了這樣一個事實：僅僅是通過最優范圍，只能用于判斷在一次改變一個目標函數系數的情況下最優解的變化。3.2圖解法靈敏度分析

3.2.2約束條件右端值的變化

現在讓我們來考慮約束條件右端值的變化對可行域帶來的影響，及其可能對最優解帶來的變化。為了闡明敏感度分析的這方面內容，我們假設Par公司的切割與印染部門增加了10個小時的生產時間，然后來考慮將會有什么發生。切割與印染約束條件的右端值由630變為640，約束條件可寫作7/10S+D≤6403.2圖解法靈敏度分析

獲得10小時的切割與印染時間，我們可以擴展問題的可行域。運用圖解法可以看出，極點S=527.5，D=270.5是最優解點。新的目標函數值為10*527.5+9*270.5=7711.75美元，比原先利潤增加了43.75美元。約束條件右端值每增加一個單位引起的最優值的變化量稱為對偶價格。在這個例子里，切割與印染約束條件的對偶價格為4.375美元。約束條件增加或減少一小時，目標函數值會相應增加或減少4.375美元。3.2圖解法靈敏度分析

在這里，我們要注意的是，對偶價格可能只適用于在右端值僅發生了很小的變動時的情況。隨著所獲得的資源越來越多，從而右端值越來越大，其他的約束條件也可能會約束和限制目標函數值的變化。3.3靈敏度分析：計算機求解

為了使用管理科學家軟件，我們使用小數代替分數。Par公司的問題用小數形式的系數表示如下：

Max10S+9D

s.t.0.7S+D≤630切割與縫合

0.5S+0.83333D≤600縫合

1.0S+0.66667D≤708成型

0.1S+0.25D≤135檢查與包裝

S,D≥03.3靈敏度分析：計算機求解

3.3.1計算機輸出的解釋——第一個例子

回憶Par公司的例子，其中有4個小于或等于約束條件的，都是關于各個生產部門的生產時間。在松弛/剩余變量一欄中，可以看到每個部門的松弛變量值。信息歸總如下：

從上述數據中，我們可以看到束縛性約束條件（切割與印染和成型）在目標函數的最優下，松弛為0。縫合部門有120小時的松弛或未使用的縫合能力，檢查與包裝部門有18小時的松弛。3.3靈敏度分析：計算機求解3.3靈敏度分析：計算機求解這里，約束條件1（切割與印染）和約束條件3（成型）的非零對偶價格分別為4.37496和6.93753。這告訴我們，每額外增加1小時的切割與印染時間會使最優解增加4.37美元，每增加1小時成型時間會使最優解增加6.94美元。看上圖結果，我們看到管理科學家軟件除了提供松弛/剩余變量和對偶價格的約束信息之外，還給出了目標函數系數和約束條件右端值的變化范圍。變量S的最優化范圍是：

6.3≤CS≤13.5

變量D的最優化范圍是：

6.67≤CD≤14.29

這個最優化范圍與圖解法得出的結論是一致的。3.3靈敏度分析：計算機求解

計算機輸出結果的最后一部分右端值范圍給出了對偶價格適用范圍的限制條件。只要約束條件右端值處于系統所給出的下限和上限之間，對偶價格就會給出當右端值增加1時，最優解的增加量。右端值范圍給出了一個對偶價格的適用范圍。如果右端值的變化超出了這個范圍，就需要重解原問題并找出新的對偶價格。我們把這個對偶價格適用的范圍稱作可行域。Par公司問題的可行域匯總如下。

只要右端值在這些范圍之內，系統分析結果中的那些對偶價格就不會改變。右端值如果超過了這些范圍，對偶價格信息會隨之改變。3.3靈敏度分析：計算機求解

3.3.2多系數同時變化

系統靈敏度分析的輸出是基于單函數系數變化的。它假設所有其他系數都保持不變。因此目標函數系數和約束右端值的變化范圍只能適用于單個系數發生變化的情況。然而很多情況下，我們可能更關注兩個或兩個以上系數同時變化時，目標函數將怎樣變化。有些多系數同時變化的分析可能會用到100%法則。下面分析如何應用100%法則。3.3靈敏度分析：計算機求解

假設Par公司的會計部門指出原先的標準袋和高級袋利潤計算有誤，應該是11.5美元和8.25美元。為了確定這樣的變化是否會對最優解產生影響，我們先要定義兩個術語“允許增加量”和“允許減少量”。對于目標函數的系數，允許增加量是在不超過最優范圍的情況下，系數盡可能增加的最大量；而允許減少量是在不低于最優范圍下限的情況下，系數可能減少的最大量。3.3靈敏度分析：計算機求解目標函數系數的100%法則

對所有變化的目標函數系數，計算其占允許增加量和允許減少量的百分比之和。如果和沒有達到100%，最優解就不會改變。但是，100%法則并沒有規定如果各百分比之和達到100%，最優解一定會發生變化。如果100%法則的條件不能被滿足，就必須對問題重新求解，以確定最優解是否發生變化。3.3靈敏度分析：計算機求解

下面100%法則相似的定理也可以用來解決多個約束條件右端值同時發生變化的情況：約束條件右端值的100%法則

對所有變化的右端值，計算其占允許增加量和允許減少量的百分比之和。如果和沒有達到100%，對偶價格就不會改變。下面我們說明在Par公司問題中，多個右端值發生變化時，約束條件右端值的100%法則。3.3靈敏度分析：計算機求解

例如，假設切割與印染部門能獲得額外的20個小時時間，同時成型部門能獲得額外的100小時的時間，切割與印染時間的允許增量是52.36316，成型時間允許增量是192.0，新增的20小時切割與印染時間占約束條件右端值允許增加量的38.19%，額外的100小時成型占了總允許增加量的52.8%。二者百分比和為90.27%，沒有超過100%，因此我們可以得出結論：對偶價格在這里是適用的，并且目標函數值將由此增加20*4.37+100*6.94=781.40.3.3靈敏度分析：計算機求解

3.3.4關于對偶價格解釋的注釋

如前所述，對偶價格是右端值每增加一個單位時對最優值的改進。當約束條件的右端值表示某種資源的可利用量時，對偶價格通常可以解釋為公司對額外支付一單位這種資源所愿意提供的金額。然而這種解釋也并非總是正確的。要理解這個問題，我們先要理解沉沒成本和相關成本的區別。沉沒成本不會受決策影響，無論決策變量為何值，這種成本都會發生。相關成本則取決于決策的制定，這種成本決定于決策變量值的變化。3.3靈敏度分析：計算機求解

重新考慮Par公司的例子。切割印染總時間是630小時，無論生產標準袋還是高級袋，都是按照時間來付工資的，那么時間成本就是一種沉沒成本。如果Par公司只需要為那些切割與印染高爾夫球袋的時間償付工資，那么時間成本就是一種相關成本。所有的相關成本都要在線性規劃的目標函數中有所反映。3.3靈敏度分析：計算機求解

對Par公司而言，我們一直假設公司必須按照工作時間來向工人發工資，不管他們的工作時間是否有效率地被利用。因此，Par公司的勞動時間資源的成本就屬于沉沒成本而不在目標函數中反映出來。當某種資源的成本屬于沉沒成本，對偶價格就可以被解釋為得到額外一個單位這種資源而付出的金額。當某種資源的成本屬于相關成本，對偶價格則可以被解釋為這種資源的價值超過其成本的數額，也就是增加一個這種資源時，公司能付出的最大成本量。3.4多于兩個決策變量的情況

圖解法只能應用于解決雙決策變量的線性規劃問題，而計算機軟件是用來處理多變量和約束條件的線性規劃問題的。在現實生活中，用線性規劃解決的問題經常包含大量的變量和約束條件。

Par公司原來的問題模型如下：3.4多于兩個決策變量的情況

假設管理者希望生產一種輕便的、可以被球手隨身攜帶的球袋模型。設計部門估計每個新球袋將需要0.8小時的切割印染，1小時縫合，1小時成型和0.25小時檢查包裝。管理者認為每個輕便袋可以獲利12.85美元。修改模型，加入新的決策變量，得模型：Max10S+9D+12.85Ls.t.0.7S+D+0.8L≤6300.5S+0.83333D+L≤630S+0.66667D+L≤7080.1S+0.25D+0.25L≤135S,D,L≥03.4多于兩個決策變量的情況3.4多于兩個決策變量的情況3.4多于兩個決策變量的情況3.4多于兩個決策變量的情況

計算機輸出結果表明，S和L的減少的成本都為0，這是因為相應的決策變量值在最優解處已經是正值。變量D的減少的成本為1.15003，表明高級袋的利潤至少增加到9+1.15003=10.15003美元，D才能變成一個正值。假設我們使D的系數正好增加1.15003美元，在用管理科學家軟件來重解原問題。3.4多于兩個決策變量的情況3.4多于兩個決策變量的情況

我們注意到，盡管D的值已經是正數最優解的值仍然沒有變。換言之，當D利潤的增量正好等于其減少的成本時，能得到多重最優解。如果換一個軟件解決問題，目標函數中D的系數正好是10.15003，D將不再是正值。這是因為軟件得出了一個不同的最優解。但是，如果D的利潤增加量超過1.15003美元，它在最優解處就不再是0。3.4多于兩個決策變量的情況

假設管理者審核了解決方案后發現，他們會放棄所有不生產高級袋的方案，并要求高級袋的產量至少達到標準袋的30%。表示如下：D≥0.3S或者-0.3S+D≥0

把這個新的約束條件加入Par公司的模型中運用管理科學家軟件進行重解，我們得到下圖的最優解。3.4多于兩個決策變量的情況3.4多于兩個決策變量的情況

我們來解釋約束條件的對偶價格，這一約束要求高級袋產量至少要達到標準袋產量30%。其對偶價格為-1.38，表明如果右端值增加一個單位，將使利潤減少1.38美元。因此，-1.38的對偶價格告訴我們，如果約束條件變為如下形式，最優解將會怎么變化。D≥0.3S+13.4多于兩個決策變量的情況

對-1.38的對偶價格比較正確的解釋可以表述如下：如果高級袋的產量由30%的標準袋產量提高一個單位，總利潤會減少1.38美元。相反，如果使得30%的最低要求減少一個單位(D≥0.3S-1)，總利潤會增加1.38美元。3.4多于兩個決策變量的情況

3.4.2牧草農場問題

我們來看一個三決策變量的最小化問題。牧草農場公司一直在試驗一種特殊的賽馬食品。該食品的成分包括標準的馬飼料產品，一種富含維生素的燕麥，以及一種新型維生素和礦物質飼料添加劑。下表歸納了每磅食品的營養價值和各種成分的成本。3.4多于兩個決策變量的情況3.4.3建立牧草農場問題的模型建立牧草農場的線性規劃模型之前，我們需要引入如下3個變量：S——標準馬飼料的量E——高營養燕麥的量

A——維生素和礦物質飼料添加劑的量運用數據，總成本最小的目標函數可以表示如下：Min0.25S+0.50E+3A成分A的約束：0.8S+0.2E≥3成分B的約束：S+1.5E+3A≥6成分C的約束：S+0.6E+2A≥4最多6磅的混合重量的約束：S+E+A≤63.4多于兩個決策變量的情況

合并所有約束條件，加上非負約束，完整的牧草農場問題的線性規劃模型表述如下：3.4多于兩個決策變量的情況

3.4.4牧草農場問題的計算機求解和解釋

用管理科學家軟件解決牧草農場問題的結果如圖所示。取近似后最優解為每天的食品中包含3.51磅的標準馬飼料，0.95磅的高營養燕麥和1.54磅維生素和礦物質飼料添加劑。因此，各成分的單位成本分別為0.25美元、0.5美元、3.00美元，因此總的成本為：3.4多于兩個決策變量的情況3.4多于兩個決策變量的情況

觀察計算機輸出的松弛/剩余部分，約束條件2的值為3.554.由于約束2是大于等于型的，因此3.554是剩余值。由于約束1和約束3的剩余值都是0，因而我們看到最優混合中，成分A和成分C剛好滿足最低要求。此外，約束4的剩余值也是0，說明最優解中每天的飼料重量正好是6磅。3.4多于兩個決策變量的情況

成分A的約束條件（約束條件1）的對偶價格為-1.22.合理解釋這個值，首先我們看它的符號為負，因此我們知道如果增加其右端值，將使得最優解變得更壞。在最小化問題中，“更壞”意味著總成本的增加，因此，右端值一單位的增加會使總成本上升1.22美元。反過來，也可以說右端值每減少一個單位，總成本下降1.22美元。觀察右端值范圍部分，我們看見只要右端值在1.143到3.368之間，上述解釋就是合理的。3.4多于兩個決策變量的情況

假設牧草農場的管理者想重新考慮馬匹的最大進食量，約束條件的對偶價格為0.92，表明右端值每增加一個單位，總成本就會減少0.92美元。右端值范圍部分顯示，在右端值增加到8.478之前，這種解釋都是正確的。所以，如果約束條件4的右端值由6增加到8，總成本就會減少2*0.92或者說1.84美元。切記，這種變化可能導致可行域的變化，由此可以獲得新的最優解。3.4多于兩個決策變量的情況

結果輸出目標函數系數范圍S下限-0.393，在實際問題中，我們認為S下限為0。由此得到，無論標準飼料的價格下降多少，最優解都不會改變。即使牧草農場免費獲得標準飼料，最優解仍然是3.51磅的標準飼料，0.95磅的高營養燕麥和1.54磅維生素和礦物質飼料添加劑。然而，標準飼料單位成本的減少，都會引起總成本的減少。目標函數系數S和A是沒有上限限制的，如果增加A的值，比如從每磅3美元增加到每磅13美元，最優解不變，總成本增加10倍。我們對計算機輸出結果所做的靈敏度分析的解釋，只有在問題中其他系數不變的情況下才有效。3.5電子通信公司問題

這里我們討論的電子通信公司問題是一個最大化問題，這個問題包括4個決策變量，2個小于等于形式的約束條件，1個等于形式的約束條件和1個大于等于形式的約束條件。我們的目標是建立一個簡單的數學模型，使用管理科學家軟件求出模型最優解，對求出的解進行解釋，并進行靈敏度分析。3.5電子通信公司問題

讓我們來看這個例子，電子通信公司主要生產雙向便攜式無線報話機。該公司最近開發了一種新產品，這種產品的通信范圍可以覆蓋22英里，適合企業和個人使用。該新產品的分銷渠道是：航海器材經銷店商用器材經銷店全國范圍的連鎖零售店直接郵購3.5電子通信公司問題

由于分銷和促銷成本的差異，產品的利潤也因銷售渠道的不同而不同。此外，廣告費用和人力成本也與銷售渠道有關。下表介紹了電子通信公司不同銷售渠道的銷售利潤、廣告費用和人工成本。廣告預算5000美元，每個銷售渠道的最大個人銷售時間是1800小時，公司現階段決定制造的產品數600件，此外，全國連鎖零售店要求最少銷售150件產品。電子通信面臨的問題是如何制定一個分銷策略，使其總的銷售利潤最大。表3-2電子通信公司的利潤、廣告費用和銷售時間3.5電子通信公司問題

3.5.1建模

我們首先寫出電子通信公司的目標函數和約束條件。約束條件1廣告支出≤廣告預算約束條件2銷售時間≤最大可用時間約束條件3產品生產數量=公司要求產量約束條件4零售分銷量≥合同要求的最低分銷量下面定義決策變量M——航海器材經銷店銷售產品數量B——商用器材經銷店銷售產品數量R——全國連鎖零售店銷售產品數量D——直接郵購產品數量3.5電子通信公司問題目標函數：Mas90M+84B+70R+60D現在設立約束條件。廣告預算5000美元10M+8B+9R+15D≤5000銷售時限1800小時2M+3B+3R≤1800現階段公司要求生產600件產品，所以M+B+R+D=600最后全國連鎖零售店至少賣出150件產品R≥1503.5電子通信公司問題綜合所有約束條件，電子通信公司問題的完整線性規劃模型如下：Max90M+84B+