運籌學第2章教材課件學習資料

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

CBB-1A≤0。令Y=CBB-1，則有不等式C-YA≤0或YA≥C成立。由于松弛變量XS對應(yīng)價格向量CS=0，則有不等式σS=CS-CBB-1I≤0或CBB-1≥0(即Y≥0)成立。同時，希望資源價格Y和數(shù)量b的乘積越小越好，即minW=Yb，則對偶問題見數(shù)學模型(2-4)，本教材稱模型(2-3)和模型(2-4)為常規(guī)形式。下一頁返回2.2對偶問題的數(shù)學模型2.2.2非常規(guī)線性規(guī)劃模型的對偶形式本教材定義“約束條件為等式”或“決策變量取值無約束”的模型為非常規(guī)模型。(1)約束條件為等式。若原問題模型為下一頁返回上一頁2.2對偶問題的數(shù)學模型因AX=b<=>b≤AX≤b，原模型可轉(zhuǎn)化為根據(jù)模型(2-3)和模型(2-4)可轉(zhuǎn)化為對偶形式，化簡過程如下:下一頁返回上一頁2.2對偶問題的數(shù)學模型最終得到非常規(guī)線性規(guī)劃問題的對偶模型為(2)決策變量取值無約束。已知線性規(guī)劃模型:令X=X′-X″，模型轉(zhuǎn)化過程如下:下一頁返回上一頁2.2對偶問題的數(shù)學模型即2.2.3原問題與對偶問題模型對應(yīng)關(guān)系通過對常規(guī)和非常規(guī)對偶模型的推導(dǎo)，可得出原問題與對偶問題模型的對應(yīng)關(guān)系，如表2-2所示。根據(jù)表中對應(yīng)關(guān)系，不僅可以快速寫出一般線性規(guī)劃問題模型的對偶形式，也可以求出特殊線性規(guī)劃問題(如運輸問題)模型的對偶形式。返回上一頁2.3對偶問題的性質(zhì)2.3.1對稱性定理對稱性定理:對偶問題的對偶是原問題。[2-9]證明模型(2-4)是模型(2-3)的對偶形式。證明:首先對模型(2-4)做出如下處理:目標函數(shù)等式兩端同乘以“-1”，則“min(-W)=Y(-b)”成立。約束條件兩端同乘以“-1”則“Y(-A)≤(-C)”成立，則模型(2-4)變?yōu)橄乱豁摲祷?.3對偶問題的性質(zhì)令W′-W，則模型(2一9)變?yōu)樵O(shè)對偶變量為X,Z′=-Z，寫出其對偶形式目標函數(shù)等式兩端同乘“-1"，約束不等式兩端同乘“-1"，模型(2-11)變?yōu)橄乱豁摲祷厣弦豁?.3對偶問題的性質(zhì)顯然，模型(2-12)與模型(2-3)相同。證畢。對稱性定理說明，原問題的對偶形式對應(yīng)于對偶問題，對偶問題的對偶形式是原問題。對于兩個互為對偶的問題，可以將其中任何一個問題當作原問題，另外一個則是對偶問題。2.3.2弱對偶定理弱對偶定理:設(shè)X和Y分別是原問題和對偶問題的可行解，則必有CX≤Yb.下一頁返回上一頁2.3對偶問題的性質(zhì)證明:對于原問題和對偶問題模型(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有最優(yōu)解的充要條件是它們同時具有可行解。證明:①必要條件:若P和D有最優(yōu)解，則它們同時有可行解。下一頁返回上一頁2.3對偶問題的性質(zhì)②充分條件:若P和D同時有可行解，那么它們有最優(yōu)解。2.3.3強對偶定理強對偶定理可以有三種表述形式:第一種:原問題P(max)有最優(yōu)解的充要條件是對偶問題D(min)有最優(yōu)解，且兩個問題的最優(yōu)目標函數(shù)值相等。證明:必要性。若原問題有最優(yōu)解，則對偶問題有最優(yōu)解。①存在性。②相等性。充分性可由對稱性定理得到證明。證畢。下一頁返回上一頁2.3對偶問題的性質(zhì)第二種:對于原問題P(max)和對偶問題D(min)，若P無界，則D不可行;若D無界，則P不可行。該定理可由弱對偶定理證明。需要注意的是:該定理的逆不成立。因為，當P無可行解時，其對偶問題或者無可行解，或者具有無界解。第三種:若X和Y分別是P(max)和D(min)的可行解，則它們分別為原問題和對偶問題最優(yōu)解的充要條件是CX*=Y*b。強對偶定理表明，當原問題(或?qū)ε紗栴})達到最優(yōu)時，對偶問題(或原問題)也一定達到最優(yōu)，且兩者對應(yīng)的最優(yōu)目標函數(shù)值相等。下一頁返回上一頁2.3對偶問題的性質(zhì)2.3.4互補松弛定理互補松弛定理:如果x和Y分別為原問題和對偶問題的可行解，它們分別為原問題和對偶問題最優(yōu)解的充要條件是:(C-YA)X=0與Y(b-AX)=0。證明:必要性。若X和Y分別為原問題和對偶問題最優(yōu)解，則(C-YA)X=0與Y(b-AX)=0同時成立。X和Y分別為原問題和對偶問題的可行解，則AX≤b,YA≥C.充分性。如果X和Y分別為原問題和對偶問題的可行解，它們分別為原問題和對偶問題最優(yōu)解的充要條件是:(C-YA)X=0與Y(b-AX)=0。下一頁返回上一頁2.3對偶問題的性質(zhì)互補松弛定理經(jīng)常表示為:該定理表明，在線性規(guī)劃問題的最優(yōu)解中，如果對應(yīng)某一約束條件的對偶變量取值為非零，則該約束條件為嚴格等式;反之，如果原問題約束條件為嚴格不等式，則其對應(yīng)的對偶變量一定為零。2.3.5對偶最優(yōu)解定理最優(yōu)解定理表達了原問題最終單純形表中變量的檢驗數(shù)與對偶問題最優(yōu)解之間的關(guān)系。在原問題最終單純形表中，松弛變量檢驗數(shù)的相反數(shù)對應(yīng)于對偶問題原變量的取值，原變量檢驗數(shù)的相反數(shù)對應(yīng)于對偶問題松弛變量的取值。這個定理與兩個互為對偶問題的最優(yōu)解有關(guān)，因此本教材稱其為“對偶最優(yōu)解定理”。下一頁返回上一頁2.3對偶問題的性質(zhì)2.3.6影子價格(1)影子價格的提出。影子價格(ShadowPrice)又稱計算價格、預(yù)測價格、最優(yōu)價格，是荷蘭經(jīng)濟學家詹恩·丁伯根在20世紀30年代末首次提出來的，并將其定義為“在均衡價格的意義上表示生產(chǎn)要素或產(chǎn)品內(nèi)在的或真正的價格”。薩繆爾遜認為，“影子價格反映資源在得到最佳使用時的價格”。聯(lián)合國把影子價格定義為“一種投入(比如資本、勞動力和外匯)的機會成本或它的供應(yīng)量減少一個單位給整個經(jīng)濟帶來的損失”。影子價格是運用線性規(guī)劃的數(shù)學模型計算得出的，是反映社會資源獲得最佳配置的一種價格。下一頁返回上一頁2.3對偶問題的性質(zhì)關(guān)于影子價格，存在著不同的表述:影子價格是資源和產(chǎn)品在完全自由竟爭市場中的供求均衡價格;影子價格是沒有市場價格的商品或服務(wù)的推算價格，它代表著生產(chǎn)或消費某種商品的機會成本;影子價格為商品或生產(chǎn)要素的邊際增量所引起的社會福利的增加值。

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

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

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

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