運(yùn)籌學(xué)課件：第2章影子價(jià)格

1、對(duì)偶問題的經(jīng)濟(jì)解釋 -影子價(jià)格,前面講到，在單純形法的每步迭代中，目標(biāo)函數(shù)取值 ,和檢驗(yàn)數(shù) 中都有乘子 ，那么Y的經(jīng)濟(jì)意義是什么,設(shè)B是 的最優(yōu)基，由（2.12）知 由此 所以變量 的經(jīng)濟(jì)意義是在其它條件不變的情況下，單位資源變化所引起的目標(biāo)函數(shù)的最優(yōu)值的變化,由第一章例1的最終計(jì)算表（見表1-5）可見, ， ， 。這說明是其它條件不變的情況下，若設(shè)備增加一臺(tái)時(shí)，該廠按最優(yōu)計(jì)劃安排生產(chǎn)可多獲利1.5元；原材料A增加1kg，可多獲利0.125元；原材料B增加1kg，對(duì)獲利無影響,從圖2-1可看到，設(shè)備增加一臺(tái)時(shí)，代表該約束條件的直線由（1）移至（1），相應(yīng)地最優(yōu)解由（4，2）變?yōu)椋?，2.5），

2、目標(biāo)函數(shù)z=2*4+3*2.5=15.5即比原來的增大1.5。又若原材料A增加1kg時(shí)，代表該約束方程的直線由（2）移至（2），相應(yīng)地最優(yōu)解從（4，2）變?yōu)椋?.25，1.875），目標(biāo)函數(shù)z=2*4.25+3*1.875=14.125，比原來的增加0.125。原材料B增加1kg時(shí)，該約束方程的直線由（3）移至（3），這時(shí)的最優(yōu)解不變,yi的值代表對(duì)第i種資源的估價(jià)。這種估價(jià)是針對(duì)具體工廠的具體產(chǎn)品而存在的一種特殊價(jià)格，稱它為”影子價(jià)格”。在該廠現(xiàn)有資源和現(xiàn)有生產(chǎn)方案的條件下，設(shè)備的每小時(shí)租費(fèi)為1.5元，1kg原材料A的出讓費(fèi)為除成本外再附加0.125元，1kg原材料B可按原成本出讓，這是該廠

3、的收入與自己組織生產(chǎn)時(shí)獲利相等。影子價(jià)格隨具體情況而異,在完全市場(chǎng)經(jīng)濟(jì)的條件下，當(dāng)某種資源的市場(chǎng)低于影子價(jià)格時(shí)，企業(yè)應(yīng)買進(jìn)該資源用于擴(kuò)大生產(chǎn)；而當(dāng)某種資源的市場(chǎng)高于企業(yè)影子價(jià)格時(shí)，則企業(yè)的決策者應(yīng)把已有資源賣掉?？梢娪白觾r(jià)格對(duì)市場(chǎng)有調(diào)節(jié)作用,6對(duì)偶單純形法,前節(jié)講到原問題與對(duì)偶問題的解之間的對(duì)應(yīng)關(guān)系（性質(zhì)7）時(shí)指出：在單純形表中進(jìn)行迭代時(shí)，在b列中得到的是原問題的基可行解，而在檢驗(yàn)數(shù)行得到的是對(duì)偶問題的基解。通過過逐步迭代，當(dāng)在檢驗(yàn)數(shù)行得到對(duì)偶問題的解也是基可行解時(shí)，根據(jù)性質(zhì)2、3可知，已得到最優(yōu)解。即原問題與對(duì)偶問題都是最優(yōu)解,根據(jù)對(duì)偶問題的對(duì)稱性，也可以這樣考慮：若保持對(duì)偶問題的解是基可行

4、解，即， 而原問題在非可行解的基礎(chǔ)上，通過逐步迭代達(dá)到基可行解，這樣也得到了最優(yōu)解。其優(yōu)點(diǎn)是原問題的初始解不一定要是基可行解?？蓮姆腔尚薪忾_始迭代,這方法是,設(shè)原問題 又設(shè)B是一個(gè)基。不失一般性，令B=（P1，P2，Pm），它對(duì)應(yīng)的變量為 XB=(x1，x2，xm,當(dāng)非基變量都為零時(shí)，可以得到 。若在 中至少有一個(gè)負(fù)分量，設(shè) ,并且在單純形表的檢驗(yàn)數(shù)行中的檢驗(yàn)數(shù)都為非正，即對(duì)偶問題保持可行解，它的各分量是,1.對(duì)應(yīng)基變量x1，x2，xm的檢驗(yàn)數(shù)是 2.對(duì)應(yīng)非基變量xm+1,，xn的檢驗(yàn)數(shù)是,每次迭代是將基變量中的負(fù)分量xl取出，支替換非基變量中的xk,經(jīng)基變換，所有檢驗(yàn)數(shù)仍保持非正。從原問題

5、來看，經(jīng)過每次迭代，原問題由非可行解往可行解靠近。當(dāng)原問題得到可行解時(shí)，便得到了最優(yōu)解,對(duì)偶單純形法的計(jì)算步驟： （1）根據(jù)線性規(guī)劃問題，列出初始單純形表。檢查b列的數(shù)字，若都為非負(fù)，檢驗(yàn)數(shù)都為非正，則已得到最優(yōu)解。停止計(jì)算。若檢查b列的數(shù)字時(shí)，至少還有一個(gè)負(fù)分量，檢驗(yàn)數(shù)保持非正，那么進(jìn)行以下計(jì)算,2） 確定換出變量 按 對(duì)應(yīng)的基變量 xl 為換出變量,3） 確定換入變量 在單純形表中檢查xl所在行的各系數(shù) , 若所有 ，則無可行解，停止計(jì)算。若存在 ，計(jì)算 按 規(guī)則所對(duì)應(yīng)的列的非基變量 xk 為換入變量，這樣才能保持得到的對(duì)偶問題解仍為可行解,4）以 為主無素，按原單純形法在表中進(jìn)行迭代運(yùn)算

6、，得到新的計(jì)算表。 重復(fù)（1）-（4）的步驟。 下面舉例來說明具體算法,例6 用對(duì)偶單純形法求解,解 先將這問題化成下列形式，以便得到對(duì)偶問題的初始可行基,建立這個(gè)問題的初始單純形表，見表2-6,從表2-6看到，檢驗(yàn)數(shù)行對(duì)應(yīng)的對(duì)偶問題的解是可行解。因b列數(shù)字為負(fù)，故需進(jìn)行迭代運(yùn)算,表2-6,換出變量的確定：按上述對(duì)偶單純形法計(jì)算步驟（2），計(jì)算min(-3,-4)=-4 故 X5 為換出變量。 換入變量的確定：按上述對(duì)偶單純形法計(jì)算步驟（3），計(jì)算,故x1為換入變量。換入、換出變量的所在列、行的交叉處”2”為主元素。按單純形法計(jì)算步驟進(jìn)行迭代。得表2-7。 由表2-7看出，對(duì)偶問題仍是可行解，

7、而b列中仍有負(fù)分量。故重復(fù)上述迭代步驟，得表2-8,表2-8中b列數(shù)字全為非負(fù)，檢驗(yàn)數(shù)全為非正，故問題的最優(yōu)解為 若對(duì)應(yīng)兩個(gè)約束條件的對(duì)偶變量分別為y1和y2，則對(duì)偶問題的最優(yōu)解為,表2-7,表2-8,從以上求解過程可以看到，對(duì)偶單純形法有以下優(yōu)點(diǎn),1）初始解可以是非可行解，當(dāng)檢驗(yàn)數(shù)都為負(fù)數(shù)時(shí)，就可以進(jìn)行基的變換，這時(shí)不需要加入人工變量，因此可以簡(jiǎn)化計(jì)算,2）當(dāng)變量多于約束條件，對(duì)這樣的線性規(guī)劃問題，用對(duì)偶單純形法計(jì)算可以減少計(jì)算工作量，因此對(duì)變量較少，而約束條件很多的線性規(guī)劃問題，可先將它變換成偶問題，然后用對(duì)偶單純形法求解,3） 在靈敏度分析中，有時(shí)需要用對(duì)偶單純形法，這樣可使問題的處理簡(jiǎn)化。對(duì)偶單純形法的局限性主要是，對(duì)大多數(shù)線性規(guī)劃問題，很難找到一個(gè)初始可行基，因而這方法在求解線性規(guī)劃問題時(shí)很少單獨(dú)應(yīng)用,用改進(jìn)單純形法求線性規(guī)劃問題,解,初始基 是單位陣，基變量 。相應(yīng)地 計(jì)算非基變量檢驗(yàn)數(shù) ，由此可確定x5