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

1、對(duì)偶問題的經(jīng)濟(jì)解釋 -影子價(jià)錢.前面講到，在單純形法的每步迭代中，目的函數(shù)取值 ,和檢驗(yàn)數(shù) 中都有乘子 ，那么Y的經(jīng)濟(jì)意義是什么？.設(shè)B是 的最優(yōu)基，由2.12知由此所以變量 的經(jīng)濟(jì)意義是在其它條件不變的情況下，單位資源變化所引起的目的函數(shù)的最優(yōu)值的變化。.由第一章例1的最終計(jì)算表見表1-5可見, ， ， 。這闡明是其它條件不變的情況下，假設(shè)設(shè)備添加一臺(tái)時(shí)，該廠按最優(yōu)方案安排消費(fèi)可多獲利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，目的函數(shù)z=2*4

2、+3*2.5=15.5即比原來的增大1.5。又假設(shè)原資料A添加1kg時(shí)，代表該約束方程的直線由2移至2，相應(yīng)地最優(yōu)解從4，2變?yōu)?.25，1.875，目的函數(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ì)詳細(xì)工廠的詳細(xì)產(chǎn)品而存在的一種特殊價(jià)錢，稱它為影子價(jià)錢。在該廠現(xiàn)有資源和現(xiàn)有消費(fèi)方案的條件下，設(shè)備的每小時(shí)租費(fèi)為1.5元，1kg原資料A的出讓費(fèi)為除本錢外再附加0.125元，1kg原資料B可按本來錢出讓，這是該廠的收入與本人組織消費(fèi)時(shí)獲利相等。影子價(jià)錢

3、隨詳細(xì)情況而異。 .在完全市場經(jīng)濟(jì)的條件下，當(dāng)某種資源的市場低于影子價(jià)錢時(shí)，企業(yè)應(yīng)買進(jìn)該資源用于擴(kuò)展消費(fèi)；而當(dāng)某種資源的市場高于企業(yè)影子價(jià)錢時(shí)，那么企業(yè)的決策者應(yīng)把已有資源賣掉。可見影子價(jià)錢對(duì)市場有調(diào)理作用。 .6對(duì)偶單純形法前節(jié)講到原問題與對(duì)偶問題的解之間的對(duì)應(yīng)關(guān)系性質(zhì)7時(shí)指出：在單純形表中進(jìn)展迭代時(shí)，在b列中得到的是原問題的基可行解，而在檢驗(yàn)數(shù)行得到的是對(duì)偶問題的基解。經(jīng)過過逐漸迭代，當(dāng)在檢驗(yàn)數(shù)行得到對(duì)偶問題的解也是基可行解時(shí)，根據(jù)性質(zhì)2、3可知，已得到最優(yōu)解。即原問題與對(duì)偶問題都是最優(yōu)解。 .根據(jù)對(duì)偶問題的對(duì)稱性，也可以這樣思索：假設(shè)堅(jiān)持對(duì)偶問題的解是基可行解，即， 而原問題在非可行解的

4、根底上，經(jīng)過逐漸迭代到達(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í)，可以得到 。假設(shè)在 中至少有一個(gè)負(fù)分量，設(shè) ,并且在單純形表的檢驗(yàn)數(shù)行中的檢驗(yàn)數(shù)都為非正，即對(duì)偶問題堅(jiān)持可行解，它的各分量是 .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ù)仍堅(jiān)持非正。從原問題來看，經(jīng)過每次迭代，原

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

6、反復(fù)1-4的步驟。下面舉例來闡明詳細(xì)算法.例6 用對(duì)偶單純形法求解 .解 先將這問題化成以下方式，以便得到對(duì)偶問題的初始可行基 建立這個(gè)問題的初始單純形表，見表2-6。 .cj-2-3-400CBXBbX1X2X3X4X500X4X5-3-4-1-2-21-1-31001cj-zj-2-3-400從表2-6看到，檢驗(yàn)數(shù)行對(duì)應(yīng)的對(duì)偶問題的解是可行解。因b列數(shù)字為負(fù)，故需進(jìn)展迭代運(yùn)算。表2-6.換出變量確實(shí)定：按上述對(duì)偶單純形法計(jì)算步驟2，計(jì)算min(-3,-4)=-4故 X5 為換出變量。換入變量確實(shí)定：按上述對(duì)偶單純形法計(jì)算步驟3，計(jì)算.故x1為換入變量。換入、換出變量的所在列、行的交叉處2為

7、主元素。按單純形法計(jì)算步驟進(jìn)展迭代。得表2-7。由表2-7看出，對(duì)偶問題仍是可行解，而b列中仍有負(fù)分量。故反復(fù)上述迭代步驟，得表2-8。 .表2-8中b列數(shù)字全為非負(fù)，檢驗(yàn)數(shù)全為非正，故問題的最優(yōu)解為假設(shè)對(duì)應(yīng)兩個(gè)約束條件的對(duì)偶變量分別為y1和y2，那么對(duì)偶問題的最優(yōu)解為.表2-7cj-2-3-400CBXBbX1X2X3X4X50-2X4X1-1201-5/2-1/21/23/210-1/2-1/2cj-zj0-4-10-1.表2-8cj-2-3-400CBXBbX1X2X3X4X5-3-2X2X12/511/50110-1/57/5-2/5-1/51/5-2/5cj-zj00-3/5-8/5

8、-1/5.從以上求解過程可以看到，對(duì)偶單純形法有以下優(yōu)點(diǎn)：1初始解可以是非可行解，當(dāng)檢驗(yàn)數(shù)都為負(fù)數(shù)時(shí)，就可以進(jìn)展基的變換，這時(shí)不需求參與人工變量，因此可以簡化計(jì)算。 .2當(dāng)變量多于約束條件，對(duì)這樣的線性規(guī)劃問題，用對(duì)偶單純形法計(jì)算可以減少計(jì)算任務(wù)量，因此對(duì)變量較少，而約束條件很多的線性規(guī)劃問題，可先將它變換成偶問題，然后用對(duì)偶單純形法求解。.3 在靈敏度分析中，有時(shí)需求用對(duì)偶單純形法，這樣可使問題的處置簡化。對(duì)偶單純形法的局限性主要是，對(duì)大多數(shù)線性規(guī)劃問題，很難找到一個(gè)初始可行基，因此這方法在求解線性規(guī)劃問題時(shí)很少單獨(dú)運(yùn)用。.用改良單純形法求線性規(guī)劃問題.解： 初始基 是單位陣，基變量 。相應(yīng)地 計(jì)算非基變量檢驗(yàn)數(shù) ，由此可確定x5為換入變量，計(jì)算.對(duì)應(yīng)換出變量為x6。于是得到新的基 .第一步迭代。計(jì)算.非基變量檢