[理學(xué)]運(yùn)籌學(xué)清華大學(xué)課件第一章-閱讀頁(yè)
2024-11-03 00:36本頁(yè)面
【正文】 x1,x2,x3,x4 ≥ 0 化標(biāo)準(zhǔn)型 取 x x4為基變量 ,令非基變量 x1= x2=0 ∴ 初始基可行解： X(0) = (0 0 3 4)T ? ? ? ? B , 1 0 3 2 0 1 2 1 434321 ppppppA ????????? 則系數(shù)矩陣32 觀察法 []max z = x1 + 3x2 + 2x3 + x4 x1 + 2x2 + 3x3 = 3 3x2 + x3 + x4 = 4 x1,x2,x3,x4 ≥ 0 選 XB = (x1 x4)T 令 x2 = x3 = 0 則 初始基可行解： X(0) = (3 0 0 4)T ? ? ? ? B , 1 1 3 00 3 2 1 :414321 ppppppA ????????? 則解33 人工基 []max z = x1 + 2x2 + 3x3 x1 + 3x2 + 2x3 = 3 2x1 + x2 + x3 = 4 x1,x2,x3 ≥ 0 分析： A = 1 3 2 2 1 1 ∵ 找不到單位矩陣基 ∴ 引入人工變量為初始基變量（ 2個(gè)） 34 最優(yōu)性的檢驗(yàn)與解的判別 ????????????????????????????mnjxmibxxaxcxczjnjiinjijmiininnjjj,1 0,1 m a x 111對(duì)于? ?代入目標(biāo)函數(shù)為非基變量可行為基變量設(shè) ,1, ,1, 1??????????????njjijiinjinxabxnjxmix35 則 ??? ??? ? ???? ????? ? ?????????????njjjnjjjjnjmijijinjmiiinnjminjjijiinjjxZxzcZxaccbcxabcxcz10101 111 1 1 )( )( )(??????? ????miijinjjjjmiiin aczzcbcZ110 , , ?其中36 解的判別： 1. 若 ，則此時(shí)的基可行解為最優(yōu)解； 2. 若存在某個(gè)非基變量 的檢驗(yàn)數(shù) ，且 ，則該線性規(guī)劃問(wèn)題具有無(wú)界解（或稱無(wú)最優(yōu)解）； 3. 若所有 ，又，對(duì)于某個(gè)非基變量 有 ，則該線性規(guī)劃問(wèn)題具有無(wú)窮多最優(yōu)解。39。39。39。39。lkllklikikiiiiikikiiaxlabaabaab??????????????? ??? ? 為入基變量。 39 單純形表 展開如下： a11x1 + a12x2 + + a2nxn + xn+2 = b2 +2 ┆ ┆ ┆ am1x1 + am2x2 + + xn + +1xn+1 + + ? nxn + 0xn+1 + +1 xn xn+1 a1n 1 amn 0 σ n 0 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。 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為 入基變量。 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ī)劃。 49 以人工變量為初始基變量 ,列表計(jì)算。 第二階段： 在第一階段最優(yōu)表中，去掉人工變量，換上原問(wèn)題目標(biāo)函數(shù)，作為本階段初始表，以此用單純形法進(jìn)行迭代運(yùn)算，求出結(jié)果。 第二階段：去掉人工變量，換上原線性規(guī)劃目標(biāo)函數(shù)（見(jiàn)下表）。理論上講，退化解可能使計(jì)算出現(xiàn)循環(huán)，從而得不到最優(yōu)解。 。39。?ikabiaiki54 當(dāng)計(jì)算中出現(xiàn)最小比值相同的情況時(shí)，可按 Bland規(guī)則來(lái)計(jì)算。 ., ,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)題
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1