運籌學(xué)課件：第2章影子價格

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

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

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

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

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

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

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