運籌學-or-資料下載頁
2025-09-30 16:05本頁面
【正文】 為嚴格不等式；由互補松弛性得 x2* = x3* = x4* = 0 因 y1 ,y2 ? 0，原問題的兩個約束條件應取等式，故有 x1* + 3x5* = 4 2x1* + x5* = 3 求解后得 x1* = 1， x5* = 1 故原問題的最優(yōu)解為 X* = (1,0,0,0,1)T 最優(yōu)值為 ω* = 5 練習： 若已知 原問題的最優(yōu)解為 X* = (1,0,0,0,1)T ω = 5。 試用對偶理論找出 其 對偶問題的最優(yōu)解 . 7 、 ( P ) 的單純形表的檢驗數(shù)行對應 ( D ) 的一個基解，其對應關系是 X X S C C B B 1A C B B 1 Y S Y ( 證略 ) 意義：單純形法迭代過程中，檢驗數(shù)的相反數(shù)對應對偶變量基解的值 Y = C B B 1， Y S = C + C B B 1A 。由于有大于零的檢驗數(shù)，故對應的對偶解為不可行解； 最終單純表中檢驗數(shù)都非正，故此時對應的對偶解為基可行解，也是最優(yōu)解?？芍?，單純形法是在解（ P ）時，保持 ( P) 解的可行性，改進（ D ）解的可行性，最后當?shù)玫綄ε嫉幕尚薪鈺r， 也就得到 了 (P) 、 (D) 的最優(yōu)解。 檢驗數(shù)行 167。 5 對偶問題的經濟解釋 — 影子價格 (P)的最終單純形表中松弛變量的檢驗數(shù)對應(D)的最優(yōu)解 。 當某約束條件的右端常數(shù)增加一個單位時（假設原問題的最優(yōu)基不變），原問題的目標函數(shù)最優(yōu)值增加的數(shù)量。 Z*=CX*=Y*b =(y1*,y2*, …,y m*) b1 b2 ﹕ ﹒ bm =y1*b1+y2*b2+…+y m*bm 當某個右端常數(shù) bi bi+1時 bi+1 yi* +yi*(bi+1) =Y*b+yi* =Z*+yi* 第 I種資源的影子價格是第 i個約束條件的右端常數(shù)增加一個單位時，目標函數(shù)增加的數(shù)量 甲 乙 可用量 機械設備 1 2 8 原材料 A 4 0 16 原材料 B 0 4 12 X(3)=(4， 2， 0， 0, 4)T， z3 =14 cj 2 3 0 0 0 CB XB b x1 x2 x3 x4 x5 2 0 3 x1 x5 x2 4 4 2 1 0 0 0 0 1 2 189。 3/2 189。 1/8 1/8 0 1 0 14 0 0 3/2 1/8 0 0125051321???*** ,.,.yyy經濟意義：在其它條件不變的情況下 ， 單位資源變化所引起的目標函數(shù)的最優(yōu)值的變化 。 影子價格 產品 資源 Ⅰ Ⅱ 現(xiàn)有資源數(shù) 鋼材 1 2 100（噸） 煤 2 2 180（噸） 機時 1 6 240（小時） 利潤（萬元） 1 3 0,24061802210023m a x2121212121?????????xxxxxxxxxxZx1 x2 x3 x4 x5 z XB 135 0 0 3/4 0 1/4 x1 30 1 0 3/2 0 1/2 x4 50 0 0 5/2 1 1/2 x2 35 0 1 1/4 0 1/4 X*=(30,35,0,50,0)T, Z*=135 y1*=3/4 y2*=0, y3*=1/4 影子價格 經濟意義： 在其它條件不變的情況下 ， 單位資源變化所引起的目標函數(shù)的最優(yōu)值的變化 。 7 原問題的檢驗數(shù)對應對偶問題的一個基本解 XB=B1b， XN=0 檢驗數(shù)為： CNCBB1N， CBB1 令 Y=CBB1得 Ys1=0， Ys2= CNCBB1N 證畢 min ω=Yb YBYs1=CB YNYs2=CN Y, Ys1， Ys2≥0 YS=（ YS1， YS2） 證明 : 原問題 對偶問題 max z =CX min ω=Yb AX+ Xs =b YAYs=C X, Xs ≥0 Y, Y s≥0 檢驗數(shù)性質：原問題檢驗數(shù)行對應其對偶問題的一個基解 , 關系如下 : XB XN Xs 0 CNCBB1N CBB1 Ys1 Ys2 Y
物理相關推薦
鄂ICP備17016276號-1