線性規(guī)劃對偶問題ppt課件-wenkub.com
2025-04-30 01:34 本頁面
【正文】 檢驗數(shù) ?j又可以稱為是第 j 種產(chǎn)品的 相對價值系數(shù) –影子價格在新產(chǎn)品開發(fā)決策中的應用 ? 企業(yè)在新產(chǎn)品投產(chǎn)前，可以利用影子價格，通過分析新產(chǎn)品使用資源的經(jīng)濟效果，以決定新產(chǎn)品是否應該投產(chǎn)。 –對影子價格為零的資源，則考慮如何加以利用，或轉讓，或充分利用 –影子價格在企業(yè)經(jīng)營決策中的作用 ? 影子價格不同市場價格，它是根據(jù)企業(yè)本身的資源情況、資源消耗系數(shù)、產(chǎn)品價值系數(shù)計算出來的一種價格，是新增資源所創(chuàng)造的價值，是邊際價格。 –將 yi看作一種附加值或附加價格，它取決于企業(yè)對第 i種資源使用效果的一種評價。 ? 影子價格 yi隨著目標函數(shù)、約束條件的經(jīng)濟意義和測度單位不同而有種種不同的具體內(nèi)容。如果 原規(guī)劃模型 屬于 在一定資源約束條件下，按一定的生活消耗生產(chǎn)一組產(chǎn)品并尋求總體效益目標函數(shù)最大化問題 ，那么其 對偶模型 屬于 對本問題中每一資源以某種方式進行估值以便得出與最優(yōu)生產(chǎn)計劃相一致的一個企業(yè)的最低總價值 。 yi=? W/?bi ? 影子價格是一種動態(tài)價格，也是一種機會成本。 單純形法 對偶單純形法 從一個初始基可行解出發(fā) 從一個初始正則解出發(fā) 檢驗數(shù)可 正可負 保持右邊常數(shù)非負（即解的可行性） 右邊常數(shù) 可正可負 保持檢驗數(shù)非負（即解的正則性） 檢驗數(shù)均非負，則為最優(yōu)解 常數(shù)均非負，則為最優(yōu)解 對偶單純形法的步驟 ? 確定換出變量：在負的基變量中選擇最小的基變量為換出變量； ? 確定換入變量：用換出變量的那一行具有負值的系數(shù)分別去除同列的檢驗數(shù)，取絕對值最小者所對應的變量為換入變量； ? 進行迭代變換（分別進行行、列變換）； ? 進行最優(yōu)性檢驗：如果所得的基本解都是非負的，則此解即為最優(yōu)解，反之繼續(xù)迭代，直至所有基變量為非負的數(shù)值為止。如果可行，即為最優(yōu)解。 121 2 31 2 3m a x 2. . 2 10 , 1 , 2 , 3iZ x xx x xs t x x xxi??? ? ? ???? ? ? ??????? 證明：首先看到該問題存在可行解，如 X=(0,0,0)，而上述問題的對偶問題為： 由第一個約束條件可知對偶問題無可行解，因原問題有可行解，故無最優(yōu)解（若原問題有最優(yōu)解，則對偶問題也有最優(yōu)解）。試用互補松馳性找出其對偶問題的最優(yōu)解。 AX+Xs=b。 m a x . . ,0TssZ C XA X I X bstXX???????m in . . ,0TTssW b YA Y I Y CstYY?? ???????? 證明： ? 原問題 對偶問題 Max Z=CX Min W=Yb AX+Xs=b YAYs=C X,Xs?0 Y,Ys ?0 Z=CX=(YAYs)X=YAXYsX W=Yb=Y(AX+Xs)=YAX+YXs 充分性： P58 必要性： P58 ? 該定理的隱含結論： –當一對對偶規(guī)劃達到 最優(yōu) 時，若一個問題的某個變量為正數(shù)，則相應的另一個問題的約束必取等式；或者一個問題中的約束條件取不等式，則相應的另一個問題的變量必為零。 ? ⑤對偶定理：若原問題有最優(yōu)解，則對偶問題也有最優(yōu)解，且最優(yōu)目標函數(shù)值相等。 –例： –說明：無界性質并不存在逆（例見： P57） ??????????????0,0442..4m a x21212121xxxxxxtsxxZ? ④可行解是最優(yōu)解的條件： –設 X*是原問題的可行解， Y*是對偶問題的可行解，當 CTX*=bTY*時， X*， Y*是最優(yōu)解。但為了在市場實現(xiàn)交易，在滿足上述條件的基礎上， W應盡可能小。從而得到如下線性規(guī)劃模型： Min W=1600y1+2500y2+400y3 2y1+?3 . 2y1+5y2+y3 ?4 y y y3 ?0 線性規(guī)劃原問題和對偶問題 原問題： Max Z=c1x1+…+c nxn a11x1+…+a 1nxn?b1 a21x1+…+a 2nxn?b2 . … … am1x1+…+a mnxn ?bm X1,…,x n?0 對偶問題： Min W=b1y1+…+b mym a11y1+…+a m1ym ? c1
教學課件相關推薦
鄂ICP備17016276號-1