[理學(xué)]運籌學(xué)清華大學(xué)課件第一章(參考版)
2024-10-22 00:36本頁面
【正文】 55 習(xí)題 P45， ,并指出單純形法迭代的每一步相當(dāng)于圖形上的哪一個頂點？ ????????????0,24261553 2m a x)1(21212121xxxxxxxxz??????????????0,18231224 52m ax)2(21212121xxxxxxxxz。 Bland 規(guī)則： ①在 σ j0中，選下標(biāo)小的非基變量入基； ②對相同的最小比值，選下標(biāo)小的基變量出基。39。基一般選下標(biāo)小的變量入基可任取其中一個變量入值，有兩個或兩個以上相同、檢驗數(shù)相同)(}0{m a x1?jj?有相同值，、最小比值相同}0{m i n239。然而，實際問題中很少出現(xià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 幾個問題 若存在兩個以上相同的最小比值，就會出現(xiàn)退化解。 ??????????????????????????????????mnjxmibxxaxxwjiinnjjijmnn,1,0,1,m i n1150 例 13 用兩階段法求解 min z = x1 + 5x2 2x1 + 3x2 ≤6 2x1 + x2 ≥1 x1,x2 ≥ 0 解：第一階段： 將問題化為等式約束 引進人工變量 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)解。若本階段無最優(yōu)解，表示原線性規(guī)劃無解，停止計算；若有最優(yōu)解，則轉(zhuǎn)第二階段。輔助 規(guī)劃的目標(biāo)函數(shù)為 min w =xn+1+…… +xn+m 這里 xn+1,…… ,xn+m為人工變量。為此，引入兩階段法。 這里： x1為入基變量， x5為出基變量， a21=2為主元。 []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 列單純形表求解。 0 σ j []用單純形法求解 max z = x1 + 3x2 x1 + 2x2 ≤ 8 4x1 ≤ 16 4x2 ≤ 12 x1,x2 ≥ 0 41 解：①標(biāo)準(zhǔn)化，建立單純形表 引入松弛變量 x3， x4， x5為初始基變量 max z = x1 + 3x2 + 0x3 + 0x4 + 0x5 x1 + 2x2 + x3 = 8 4x1 + x4 = 16 4x2 + x5 = 12 x1,x2,x3,x4,x5 ≥ 0 cB xB b x1 x2 x3 x4 x5 θ 1 3 0 0 0 0 x3 8 1 2 1 0 0 0 x4 16 4 0 0 1 0 0 x5 12 0 4 0 0 1 此時的解： x(0) = (0 0 8 16 12)T z(0) = 0 42 ②解的判別 ∵ σ 1=1 σ 2=3 0 ∴x (0)非最優(yōu)解 ③基變換 max{σ 1,σ 2} = 3 = σ 2 x2入基 min{8/2,12/4} = 12/4 x5出基 1 3 0 0 0 cB xB b x1 x2 x3 x4 x5 θ 0 x3 8 1 2 1 0 0 0 x4 16 4 0 0 1 0 0 x5 12 0 4 0 0 1 8/2 12/4 1 3 0 0 0 43 此時的解： x(1)=(0 3 2 16 0)T z(1)=9 x(1)非最優(yōu) x1入基 x3出基 0 x3 2 1 0 1 0 1/2 2/1 0 x4 16 4 0 0 1 0 16/4 3 x2 3 0 1 0 0 1/4 1 0 0 0 3/4 1 x1 2 1 0 1 0 1/2 0 x4 8 0 0 4 1 2 3 x2 3 0 1 0 0 1/4 0 0 1 0 1/4 1 3 0 0 0 此時的解： x(2)=(2 3 0 8 0)T z(2)=11 x(2)為最優(yōu)解 即： 最優(yōu)解： x* = (2 3 0 8 0)T 最大值： z* = 11 44 X(0)=(0 0 8 16 12)T O(0,0) X(1)=(0 3 2 16 0)T Q4(0,3) X(2)=(2 3 0 8 0)T
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1