運(yùn)籌學(xué)-or(參考版)
2024-10-11 16:05本頁(yè)面
【正文】 7 原問題的檢驗(yàn)數(shù)對(duì)應(yīng)對(duì)偶問題的一個(gè)基本解 XB=B1b， XN=0 檢驗(yàn)數(shù)為： CNCBB1N， CBB1 令 Y=CBB1得 Ys1=0， Ys2= CNCBB1N 證畢 min ω=Yb YBYs1=CB YNYs2=CN Y, Ys1， Ys2≥0 YS=（ YS1， YS2） 證明 : 原問題 對(duì)偶問題 max z =CX min ω=Yb AX+ Xs =b YAYs=C X, Xs ≥0 Y, Y s≥0 檢驗(yàn)數(shù)性質(zhì)：原問題檢驗(yàn)數(shù)行對(duì)應(yīng)其對(duì)偶問題的一個(gè)基解 , 關(guān)系如下 : XB XN Xs 0 CNCBB1N CBB1 Ys1 Ys2 Y 。 1/8 1/8 0 1 0 14 0 0 3/2 1/8 0 0125051321???*** ,.,.yyy經(jīng)濟(jì)意義：在其它條件不變的情況下 ， 單位資源變化所引起的目標(biāo)函數(shù)的最優(yōu)值的變化 。 Z*=CX*=Y*b =(y1*,y2*, …,y m*) b1 b2 ﹕ ﹒ bm =y1*b1+y2*b2+…+y m*bm 當(dāng)某個(gè)右端常數(shù) bi bi+1時(shí) bi+1 yi* +yi*(bi+1) =Y*b+yi* =Z*+yi* 第 I種資源的影子價(jià)格是第 i個(gè)約束條件的右端常數(shù)增加一個(gè)單位時(shí)，目標(biāo)函數(shù)增加的數(shù)量 甲 乙 可用量 機(jī)械設(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。 5 對(duì)偶問題的經(jīng)濟(jì)解釋 — 影子價(jià)格 (P)的最終單純形表中松弛變量的檢驗(yàn)數(shù)對(duì)應(yīng)(D)的最優(yōu)解 。可知，單純形法是在解（ P ）時(shí)，保持 ( P) 解的可行性，改進(jìn)（ D ）解的可行性，最后當(dāng)?shù)玫綄?duì)偶的基可行解時(shí)， 也就得到 了 (P) 、 (D) 的最優(yōu)解。 試用對(duì)偶理論找出 其 對(duì)偶問題的最優(yōu)解 . 7 、 ( P ) 的單純形表的檢驗(yàn)數(shù)行對(duì)應(yīng) ( D ) 的一個(gè)基解，其對(duì)應(yīng)關(guān)系是 X X S C C B B 1A C B B 1 Y S Y ( 證略 ) 意義：?jiǎn)渭冃畏ǖ^程中，檢驗(yàn)數(shù)的相反數(shù)對(duì)應(yīng)對(duì)偶變量基解的值 Y = C B B 1， Y S = C + C B B 1A 。 證畢 例 5 已知線性規(guī)劃問題 minω = 2x1 + 3x2 + 5x3 + 2x4 + 3x5 x1 + x2 + 2x3 + x4 + 3x5 ≥ 4 2x1 x2 + 3x3 + x4 + x5 ≥ 3 xj ≥ 0,j = 1,2,3,4,5 已知其 對(duì)偶問題的最優(yōu)解為 y1* = 4/5, y2* = 3/5； z = 5。 證明 : 原問題 對(duì)偶問題 max z =CX min ω=Yb AX+ Xs =b YAYs=C X, Xs ≥0 Y, Y s≥0 z =(YAYs)X=YAXYsX ω=Y(AX+Xs)=YAX+YXs 若 Y(0)Xs=0和 YsX(0) =0, 則 Y(0)b=Y(0)AX(0)=CX(0)，根據(jù)性質(zhì)4可知 X(0),Y(0)為最優(yōu)解。 其中 Xs=(xs1,xs2,…,x sm)T， xs1,xs2,…,x sm 分別是原問題的松弛變量 . Ys=(ys1,ys2,…,y sn)T ， ys1,ys2,…,y sn分別是對(duì)偶問題的剩余變量。由此原問題也無(wú)最優(yōu)解。 例 4 已知線性規(guī)劃問題 max z = x1 + x2 x1 + x2 + x3 ≤ 2 2x1 + x2 x3 ≤ 1 x1 , x2 , x3≥0
物理相關(guān)推薦
鄂ICP備17016276號(hào)-1