[理學(xué)]運(yùn)籌學(xué)清華大學(xué)課件第一章-資料下載頁(yè)
2025-10-10 00:36本頁(yè)面
【正文】 )T O(0,0) X(1)=(0 3 2 16 0)T Q4(0,3) X(2)=(2 3 0 8 0)T Q3(2,3) x2 x1 ① ② Q1 Q2(4,2) ③ Q3(2,3) Q4 * O(0,0) 45 167。 4 單純形法的進(jìn)一步討論 人工變量法 大 M法（ M為很大的正數(shù)） 法則：對(duì)于 max問(wèn)題，人工變量在目標(biāo)函數(shù)中的價(jià)值系數(shù)為 M； 對(duì)于 min問(wèn)題，人工變量在目標(biāo)函數(shù)中的價(jià)值系數(shù)為 M。 []min z = x1 + 5x2 + 0x3+0x4 2x1 + 3x2 + x3 = 6 2x1 + x2 – x4 = 1 x1,x2,x3, x4 ≥ 0 解： min z = x1 + 5x2 + 0x3 + 0x4 +Mx5 ： x5為人工變量 2x1 + 3x2 + x3 = 6 2x1 + x2 –x4 + x5 = 1 x1,x2,x3,x4,x5 ≥ 0 列單純形表求解。 46 min z = x1 + 5x2 + 0x3 + 0x4 +Mx5 2x1 + 3x2 + x3 = 6 2x1 + x2 –x4 + x5 = 1 x1,x2,x3,x4,x5 ≥ 0 對(duì)于 min問(wèn)題，若 min{?j0}= ?k ,則 xk為 入基變量。 這里： x1為入基變量， x5為出基變量， a21=2為主元。 1 5 0 0 M cB xB b x1 x2 x3 x4 x5 θ 0 x3 6 2 3 1 0 0 6/2 M x5 1 [2] 1 0 1 1 1/2 12M 5M 0 M 0 47 進(jìn)一步迭代 1 5 0 0 M cB xB b x1 x2 x3 x4 x5 θ 0 x3 5 0 2 1 1 1 1 x1 1/2 1 1/2 0 1/2 1/2 0 9/2 0 1/2 M+1/2 1 5 0 0 M cB xB b x1 x2 x3 x4 x5 θ 0 x3 6 2 3 1 0 0 6/2 M x5 1 [2] 1 0 1 1 1/2 12M 5M 0 M 0 48 因?yàn)樗??j≥ 0 ，于是得問(wèn)題的最優(yōu)解： 最優(yōu)解： X*=(x1 x2 x3 x4 x5)T =(1/2 0 5 0 0)T 目標(biāo)函數(shù)最小值： Z*=1/2 2. 兩階段法 由于大 M不是一個(gè)確定的數(shù)，所以大 M法適宜于手工 計(jì)算，而不適合求解。為此，引入兩階段法。 第一階段： 給線性規(guī)劃加入人工變量，并構(gòu)造輔助規(guī)劃。輔助 規(guī)劃的目標(biāo)函數(shù)為 min w =xn+1+…… +xn+m 這里 xn+1,…… ,xn+m為人工變量。 49 以人工變量為初始基變量 ,列表計(jì)算。若本階段無(wú)最優(yōu)解，表示原線性規(guī)劃無(wú)解，停止計(jì)算；若有最優(yōu)解，則轉(zhuǎn)第二階段。 第二階段： 在第一階段最優(yōu)表中，去掉人工變量，換上原問(wèn)題目標(biāo)函數(shù)，作為本階段初始表，以此用單純形法進(jìn)行迭代運(yùn)算，求出結(jié)果。 ??????????????????????????????????mnjxmibxxaxxwjiinnjjijmnn,1,0,1,m i n1150 例 13 用兩階段法求解 min z = x1 + 5x2 2x1 + 3x2 ≤6 2x1 + x2 ≥1 x1,x2 ≥ 0 解：第一階段： 將問(wèn)題化為等式約束 引進(jìn)人工變量 x5得 輔助規(guī)劃： min z = x1 + 5x2+0x3+0x4 min w = x5 2x1 + 3x2 +x3 = 6 2x1 + 3x2 +x3 = 6 2x1 + x2 –x4 = 1 2x1 + x2 –x4 +x5 = 1 x1,x2 ,x3,x4≥ 0 x1,x2,x3,x4,x5 ≥ 0 51 min w = x5 2x1 + 3x2 +x3 = 6 2x1 + x2 –x4 +x5 = 1 x1,x2,x3,x4,x5 ≥ 0 CB XB b 0 x1 0 x2 0 x3 0 x4 1 x5 ?i 0 x3 6 2 3 1 0 0 6/2 1 x5 1 [2] 1 0 1 1 1/2 2 1 0 1 0 0 x3 5 0 2 1 1 1 0 x1 1/2 1 1/2 0 1/2 1/2 0 0 0 0 1 52 第一階段有最優(yōu)解。 第二階段：去掉人工變量，換上原線性規(guī)劃目標(biāo)函數(shù)（見(jiàn)下表）。 最優(yōu)解： X*=(1/2 0 5 0)T Z*=1/2 CB XB b 1 x1 5 x2 0 x3 0 x4 0 x3 5 0 2 1 1 1 x1 1/2 1 1/2 0 1/2 0 9/2 0 1/2 53 幾個(gè)問(wèn)題 若存在兩個(gè)以上相同的最小比值，就會(huì)出現(xiàn)退化解。理論上講，退化解可能使計(jì)算出現(xiàn)循環(huán)，從而得不到最優(yōu)解。然而，實(shí)際問(wèn)題中很少出現(xiàn)這種情況。 ?；话氵x下標(biāo)小的變量入基可任取其中一個(gè)變量入值，有兩個(gè)或兩個(gè)以上相同、檢驗(yàn)數(shù)相同)(}0{m a x1?jj?有相同值，、最小比值相同}0{m i n239。39。39。?ikabiaiki54 當(dāng)計(jì)算中出現(xiàn)最小比值相同的情況時(shí)，可按 Bland規(guī)則來(lái)計(jì)算。 Bland 規(guī)則： ①在 σ j0中，選下標(biāo)小的非基變量入基； ②對(duì)相同的最小比值，選下標(biāo)小的基變量出基。 ., ,2,10,m i nm i n3得問(wèn)題的最優(yōu)解時(shí)數(shù)滿足當(dāng)所有非基變量的檢驗(yàn)問(wèn)題對(duì)于問(wèn)題最優(yōu)解的判別、njzcjjj??????第二章 σ j與 ?i的計(jì)算同 max問(wèn)題 。 55 習(xí)題 P45， ,并指出單純形法迭代的每一步相當(dāng)于圖形上的哪一個(gè)頂點(diǎn)？ ????????????0,24261553 2m a x)1(21212121xxxxxxxxz??????????????0,18231224 52m ax)2(21212121xxxxxxx
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1