第2章對偶規劃2.1對偶問題的提出2.2對偶問題的數學模型2.3對偶問題的性質2.4對偶單純形法2.5靈敏度分析與參數分析返回2.1對偶問題的提出【例2-1】某廠擬在計劃期(如一周)內安排生產甲、乙兩種產品，經預測，生產每單位產品所消耗的原材料、設備工時以及所獲利潤情況如表2-1所示。假設所生產的產品能全部售出，問:該廠在計劃期內如何安排生產才能獲得最大的利潤?為保持利潤水平不降低，資源出售或出租的最低價格應是多少?解:這是一個已知資源、求利潤最大化的生產計劃問題，根據題意，可設甲、乙產品的產量分別為x1和x2，則該線性規劃問題數學模型為下一頁返回上一頁2.1對偶問題的提出同時，也可以將A,B,C,D四種資源出售或出租以獲得利潤，假設出售材料A和B及出租設備C和D所得單位利潤分別為y1,y2,y3和y4(千元)，為解決上述問題需要同時滿足以下三個條件:①保持利潤水平不降低。用于生產兩種產品的資源若將其出售和出租，應不低于自行生產帶來的利潤，于是有“2y1+y2+4y3+0y4≥2”和“2y1+2y2+0y3+4y4≥3”成立。②資源價格最低。為使資源成功出售和出租，希望價格越低越好，因此:minW=12y1+8y2+16y3+12y4。下一頁返回上一頁2.1對偶問題的提出③資源價格非負。資源出售和出租的價格不能為負值，因此必須滿足:y1，y2，y3，y4≥0。綜上，可以獲得一個新的數學模型:模型(1-1)與模型(2-2)互為對偶模型，可看出兩者的參數之間存在對應關系。返回上一頁2.2對偶問題的數學模型2.2.1常規線性規劃模型的對偶形式原問題數學模型可用矩陣形式表達:若原問題具有最優解，其檢驗數必定小于或等于零，即σ≤0或C-

CBB-1A≤0。令Y=CBB-1，則有不等式C-YA≤0或YA≥C成立。由于松弛變量XS對應價格向量CS=0，則有不等式σS=CS-CBB-1I≤0或CBB-1≥0(即Y≥0)成立。同時，希望資源價格Y和數量b的乘積越小越好，即minW=Yb，則對偶問題見數學模型(2-4)，本教材稱模型(2-3)和模型(2-4)為常規形式。下一頁返回2.2對偶問題的數學模型2.2.2非常規線性規劃模型的對偶形式本教材定義“約束條件為等式”或“決策變量取值無約束”的模型為非常規模型。(1)約束條件為等式。若原問題模型為下一頁返回上一頁2.2對偶問題的數學模型因AX=b<=>b≤AX≤b，原模型可轉化為根據模型(2-3)和模型(2-4)可轉化為對偶形式，化簡過程如下:下一頁返回上一頁2.2對偶問題的數學模型最終得到非常規線性規劃問題的對偶模型為(2)決策變量取值無約束。已知線性規劃模型:令X=X′-X″，模型轉化過程如下:下一頁返回上一頁2.2對偶問題的數學模型即2.2.3原問題與對偶問題模型對應關系通過對常規和非常規對偶模型的推導，可得出原問題與對偶問題模型的對應關系，如表2-2所示。根據表中對應關系，不僅可以快速寫出一般線性規劃問題模型的對偶形式，也可以求出特殊線性規劃問題(如運輸問題)模型的對偶形式。返回上一頁2.3對偶問題的性質2.3.1對稱性定理對稱性定理:對偶問題的對偶是原問題。[2-9]證明模型(2-4)是模型(2-3)的對偶形式。證明:首先對模型(2-4)做出如下處理:目標函數等式兩端同乘以“-1”，則“min(-W)=Y(-b)”成立。約束條件兩端同乘以“-1”則“Y(-A)≤(-C)”成立，則模型(2-4)變為下一頁返回2.3對偶問題的性質令W′-W，則模型(2一9)變為設對偶變量為X,Z′=-Z，寫出其對偶形式目標函數等式兩端同乘“-1"，約束不等式兩端同乘“-1"，模型(2-11)變為下一頁返回上一頁2.3對偶問題的性質顯然，模型(2-12)與模型(2-3)相同。證畢。對稱性定理說明，原問題的對偶形式對應于對偶問題，對偶問題的對偶形式是原問題。對于兩個互為對偶的問題，可以將其中任何一個問題當作原問題，另外一個則是對偶問題。2.3.2弱對偶定理弱對偶定理:設X和Y分別是原問題和對偶問題的可行解，則必有CX≤Yb.下一頁返回上一頁2.3對偶問題的性質證明:對于原問題和對偶問題模型(2-3)和模型(2-4)，

X是原問題的可行解，則有:AX≤b,X≥0;Y是對偶問題的可行解，則有YA≥C,Y≥0。在“AX≤b”兩端左乘“Y”，有YAX≤Yb;在“YA≥C”兩端右乘“X”，有YAX≥CX。因此，不等式"CX≤AX≤Yb”成立，即CX≤Yb。證畢。推論:原問題P和對偶問題D有最優解的充要條件是它們同時具有可行解。證明:①必要條件:若P和D有最優解，則它們同時有可行解。下一頁返回上一頁2.3對偶問題的性質②充分條件:若P和D同時有可行解，那么它們有最優解。2.3.3強對偶定理強對偶定理可以有三種表述形式:第一種:原問題P(max)有最優解的充要條件是對偶問題D(min)有最優解，且兩個問題的最優目標函數值相等。證明:必要性。若原問題有最優解，則對偶問題有最優解。①存在性。②相等性。充分性可由對稱性定理得到證明。證畢。下一頁返回上一頁2.3對偶問題的性質第二種:對于原問題P(max)和對偶問題D(min)，若P無界，則D不可行;若D無界，則P不可行。該定理可由弱對偶定理證明。需要注意的是:該定理的逆不成立。因為，當P無可行解時，其對偶問題或者無可行解，或者具有無界解。第三種:若X和Y分別是P(max)和D(min)的可行解，則它們分別為原問題和對偶問題最優解的充要條件是CX*=Y*b。強對偶定理表明，當原問題(或對偶問題)達到最優時，對偶問題(或原問題)也一定達到最優，且兩者對應的最優目標函數值相等。下一頁返回上一頁2.3對偶問題的性質2.3.4互補松弛定理互補松弛定理:如果x和Y分別為原問題和對偶問題的可行解，它們分別為原問題和對偶問題最優解的充要條件是:(C-YA)X=0與Y(b-AX)=0。證明:必要性。若X和Y分別為原問題和對偶問題最優解，則(C-YA)X=0與Y(b-AX)=0同時成立。X和Y分別為原問題和對偶問題的可行解，則AX≤b,YA≥C.充分性。如果X和Y分別為原問題和對偶問題的可行解，它們分別為原問題和對偶問題最優解的充要條件是:(C-YA)X=0與Y(b-AX)=0。下一頁返回上一頁2.3對偶問題的性質互補松弛定理經常表示為:該定理表明，在線性規劃問題的最優解中，如果對應某一約束條件的對偶變量取值為非零，則該約束條件為嚴格等式;反之，如果原問題約束條件為嚴格不等式，則其對應的對偶變量一定為零。2.3.5對偶最優解定理最優解定理表達了原問題最終單純形表中變量的檢驗數與對偶問題最優解之間的關系。在原問題最終單純形表中，松弛變量檢驗數的相反數對應于對偶問題原變量的取值，原變量檢驗數的相反數對應于對偶問題松弛變量的取值。這個定理與兩個互為對偶問題的最優解有關，因此本教材稱其為“對偶最優解定理”。下一頁返回上一頁2.3對偶問題的性質2.3.6影子價格(1)影子價格的提出。影子價格(ShadowPrice)又稱計算價格、預測價格、最優價格，是荷蘭經濟學家詹恩·丁伯根在20世紀30年代末首次提出來的，并將其定義為“在均衡價格的意義上表示生產要素或產品內在的或真正的價格”。薩繆爾遜認為，“影子價格反映資源在得到最佳使用時的價格”。聯合國把影子價格定義為“一種投入(比如資本、勞動力和外匯)的機會成本或它的供應量減少一個單位給整個經濟帶來的損失”。影子價格是運用線性規劃的數學模型計算得出的，是反映社會資源獲得最佳配置的一種價格。下一頁返回上一頁2.3對偶問題的性質關于影子價格，存在著不同的表述:影子價格是資源和產品在完全自由竟爭市場中的供求均衡價格;影子價格是沒有市場價格的商品或服務的推算價格，它代表著生產或消費某種商品的機會成本;影子價格為商品或生產要素的邊際增量所引起的社會福利的增加值。

(2)影子價格的含義。下面以生產計劃問題為例，說明影子價格的含義。在線性規劃問題模型中，右端項表示資源的限制使用量，當某一項資源增加一個數值后，目標函數得到新的最大值時，目標函數最大值的增量與資源的增量的比值，就是這項資源的影子價格。也就是說，影子價格是在其他條件不變的情況下，單位資源變化所引起的目標函數最優值的變化，即單位資源對目標函數值的貢獻。下一頁返回上一頁2.3對偶問題的性質影子價格可以直接利用對偶模型求得。然而，在線性規劃中，有限資源的配置與價格互為對偶問題，從經濟意義上看，有限資源的配置與價格則是同一問題的兩個方面，所以既能解決有限資源最佳配置問題，也能解決最優價格一影子價格問題。當使用單純形法求解線性規劃問題時，對偶問題的最優解就是影子價格。求影子價格時可不用求解原問題的對偶問題，根據對偶最優解定理，只需要將原問題最終單純形表中的松弛變量的檢驗數乘以“-1”，就得到了對偶問題的最優解，也就是原問題約束條件右端常數項所對應資源的影子價格。這種方法通常用于求解影子價格。

(3)影子價格的經濟解釋。下一頁返回上一頁2.3對偶問題的性質日常生活中，影子的大小隨光線的不同而不同。影子價格就如同市場價格的影子，可以高于或低于市場價格。當影子價格低于市場價格時，說明某項資源用于生產所帶來的收益小于用于出售獲得的收益，應優先考慮出售資源;當影子價格高于市場價格時，說明某項資源用于生產所帶來的收益大于用于出售獲得的收益，應將資源用于生產。因此，影子價格是一種機會成本，可為生產管理者、決策者提供決策依據。在市場經濟條件下，當某種資源的市場價格低于影子價格時，可以買進這種資源，擴大生產;相反地，當市場價格高于影子價格時，可賣出這種資源來獲取更大的利潤。下一頁返回上一頁2.3對偶問題的性質當然隨著資源的買賣，它的影子價格也將隨之發生變化，直到影子價格與市場價格相等時，即可停止資源的買賣。(4)影子價值與影子價格。事實上，價值和價格是兩個不同的概念，因此影子價值不同于影子價格。影子價值含義比較廣泛，既包括影子價格，也包括影子利潤。因此，在解決實際問題時，應對影子價值和影子價格進行區分:若原問題求利潤最大，則對偶問題最優解就是影子利潤;若原問題求產值最大，則對偶問題最優解就是影子價格。影子價格和影子利潤存在以下關系:影子價格=資源成本+影子利潤(2-13)返回上一頁2.4對偶單純形法2.4.1原理與特點

(1)定義與原理。對偶單純形法是用對偶性質求解線性規劃問題的一種方法。不要誤解為專門用于求解對偶問題的單純形法。通過對普通單純形法和對偶單純形法的比較可以找到對偶單純形法的求解思路。普通單純形法:在迭代過程中，在保持原問題可行(XB=B-1b≥0)的條件下，向對偶問題可行(YA≥C)的方向迭代，從而實現σ=C-CBB-1A≤0(C-YA≤0或YA≥C)。與此相反，對偶單純形法的思路是在保持對偶問題可行(C-CBB-1A≤0)的條件下，向原問題可行(B-1b≥0)的方向迭代，最終實現XB≥0。下一頁返回2.4對偶單純形法(2)特點。對偶單純形法具有以下優點:①初始解是非可行解時，無須引入人工變量，可以簡化計算;②若約束方程個數(m)較少時，計算更加方便。2.4.2求解步驟對偶單純形法求解步驟如下:①將原問題的數學模型標準化。②列出初始單純形表。③判優。下一頁返回上一頁2.4對偶單純形法若所有B-1bi非負，且所有檢驗數非正，最優;否則，進行以下步驟:④按法則:，確定出基變量。⑤按法則:，確定入基變量。⑥以alk為主元素進行迭代(方法同普通單純形法)，得到新的基可行解。⑦重復上述(2)~(6)步，直至獲得最優解?？梢?，對偶單純形法擅長解決決策變量多、約束條件少的線性規劃問題，計算步驟少、簡單。返回上一頁2.5靈敏度分析與參數規劃線性規劃研究的是一定條件下的最優化問題，但實際的資源環境和技術條件是可變的，而且基礎數據往往是測算估計的數值。靈敏度分析又稱敏感性分析或優化后分析，用于研究基礎數據發生波動后對最優解的影響，或者說研究最優解對數據變化的敏感程度，即最優解在多大的范圍內波動才不影響最優基。因此，靈敏度分析要解決的問題包括兩個方面:參數在什么范圍變化而最優解或最優基不變?已知參數的變化范圍，考查最優解(最優基)是否改變?具體為:①可用資源的數量發生變化，會使得右邊限制常數bi發生變化。②由于市場條件發生變化，會使得價值系數cj發生變化。③由于生產工藝的改進，會使得單耗(約束條件系數或叫技術系數)aij，發生變化。下一頁返回2.5靈敏度分析與參數規劃④為使資源得到充分利用，增加生產項目，會增加變量個數。⑤為提高產品質量，增加資源種類，會增加約束條件個數。因此，靈敏度分析主要是指各類因素發生變化對原規劃問題最優解(原最優決策方案)的影響分析，即這些因素在什么范圍內變化時，原規劃問題最優解或最優基不變。各類因素發生變化可以分為以下兩種情況。第一種情況:多種因素同時發生變化，原最優解可能發生變化，一般從頭開始迭代計算，求出新最優解。第二種情況:單種因素單方面發生變化，原最優解可能發生變化，此時不必從頭開始迭代計算，只要在原最優表中進行分析計算，即可求出新最優解。下一頁返回上一頁2.5靈敏度分析與參數規劃2.5.1價值系數的靈敏度分析價值系數的靈敏度分析的研究內容是:cj在什么范圍內變化時，最優解不變。

(1)求非基變量系數CN的變化范圍。設非基變量系