現(xiàn)代企業(yè)運(yùn)籌學(xué)管理方案-wenkub
2023-03-17 11:42:43 本頁(yè)面
【正文】 ??0,037342..21212121yyyyyyyyts問(wèn)題的導(dǎo)出 A B C 擁有量 工 時(shí) 1 1 1 3 材 料 1 4 7 9 單件利潤(rùn) 2 3 3 ?????????21)9,3(minyyW???????????????????????????????????????????????0332714111..2121yyyyts???????????321)3,3,2(maxxxxZ???????????????????????????????????????????????????????????00093741111..321321xxxxxxts對(duì)偶問(wèn)題的定義 nn xcxcxcZ ???? ?2211ma x?????????????????????????????????????????????????????0,..212121212222111211nmnmnmmnnxxxbbbxxxaaaaaaaaats?????????mm ybybybW ???? ?2211min?????????????????????????????????????????????????????0,..212121212221212111mnmmnnnmmyyycccyyyaaaaaaaaats?????????對(duì)稱形式的對(duì)偶問(wèn)題 對(duì)偶問(wèn)題的定義 對(duì)稱形式的對(duì)偶問(wèn)題 CXZ ?m ax TT YbW ?min ???????0..TTTTYCYAts?????0..XbAXts對(duì)偶問(wèn)題的定義 對(duì)偶問(wèn)題的特點(diǎn) ?若原問(wèn)題目標(biāo)是求極大化，則對(duì)偶問(wèn)題的目標(biāo)是極小化，反之亦然 ?原問(wèn)題的約束系數(shù)矩陣與對(duì)偶問(wèn)題的約束系數(shù)矩陣互為轉(zhuǎn)置矩陣 ?極大化問(wèn)題的每個(gè)約束對(duì)應(yīng)于極小化問(wèn)題的一個(gè)變量，其每個(gè)變量對(duì)應(yīng)于對(duì)偶問(wèn)題的一個(gè)約束。 最優(yōu)性準(zhǔn)則定理 定理 2－ 2 最優(yōu)性準(zhǔn)則定理 若 X和 Y分別是互為對(duì)偶的線性規(guī)劃的可行解 ， 且使 CX=Yb， 則 X和 Y分別是相應(yīng)線性規(guī)劃問(wèn)題的最優(yōu)解 證明：由弱對(duì)偶定理可知 ， 對(duì)任意可行解有 ， CX≤Yb 因此對(duì)于 X和 Y也將分別有 CX≤Yb CX≤Yb 又因?yàn)? CX=Yb 故有 Yb ≤Yb CX≤CX 主對(duì)偶定理 定理 2－ 3 （ 主對(duì)偶定理 ） 若原始問(wèn)題和對(duì)偶問(wèn)題兩者均可行 ，則兩者均有最優(yōu)解 ， 且此時(shí)目標(biāo)函數(shù)值相同 。 當(dāng) B是原問(wèn)題的最優(yōu)基時(shí)， Y=CBB1就是影子價(jià)格向量 。 由檢驗(yàn)數(shù)的計(jì)算方法可知： ? =C ?A 若 A中有單位子矩陣，則在最優(yōu)表中有： ijjc ?? ?? jji c ?? ?? CB XB cj 2 3 3 0 0 ? xj b x1 x2 x3 x4 X5 0 x4 3 1 1 1 1 0 3/1 0 x5 9 1 4 7 0 1 9/1 2 x1 1 1 0 1 4/3 1/3 3 x2 2 0 1 2 1/3 1/3 －Ｚ 8 0 0 1 5/3 1/3 對(duì)偶單純形法 對(duì)偶單純形法并不是求解對(duì)偶問(wèn)題解的方法，而是利用對(duì)偶理論求解原問(wèn)題的解的方法。 93max yyW ???????????????????????????0,.... ..,037342..51521421321yyyyyyyyyyyts CB XB cj 3 9 0 0 0 ? yj b y1 y2 y3 y4 y5 0 Y3 2 1 1 1 0 0 0 Y4 3 1 4 0 1 0 0 Y5 3 1 7 0 0 1 －Ｚ 0 3 9 0 0 0 對(duì)偶單純形法舉例 CB XB cj 3 9 0 0 0 yj b y1 y2 y3 y4 y5 0 Y3 2 1 1 1 0 0 0 Y4 3 1 4 0 1 0 0 Y5 3 1 7 0 0 1 －Ｚ 0 3 9 0 0 0 9 Y2 2 1 1 1 0 0 0 Y4 5 3 0 4 1 0 0 Y5 11 6 0 7 0 1 －Ｚ 0 6 0 9 0 0 對(duì)偶單純形法舉例 CB XB cj 3 9 0 0 0 xj b y1 y2 y3 y4 y5 0 Y3 2 1 1 1 0 0 0 Y4 3 1 4 0 1 0 0 Y5 3 1 7 0 0 1 －Ｚ 0 3 9 0 0 0 3 Y1 2 1 1 1 0 0 0 Y4 1 0 3 1 1 0 0 Y5 1 0 6 1 0 1 －Ｚ 6 0 6 3 0 0 最小比值 0 6/3 3/1 0 0 最小比值 3/1 9/1 0 0 0 對(duì)偶單純形法舉例 CB XB cj 3 9 0 0 0 xj b y1 y2 y3 y4 y5 3 Y1 2 1 1 1 0 0 0 Y4 1 0 3 1 1 0 0 Y5 1 0 6 1 0 1 －Ｚ 6 0 6 3 0 0 3 Y1 5/3 1 0 4/3 1/3 0 9 Y2 1/3 0 1 1/3 1/3 0 0 Y5 1 0 0
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1