系統(tǒng)工程考試復(fù)習(xí)資料(編輯修改稿)
2024-09-19 17:27 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 一個(gè)初始基 ,x x4為基變量 ， x x2為非基變量 ， 令 x1=0、 x2=0由約束方程知 x3= x4=30得到初始基本可行解 X(1)=(0,0,40,30)T 系統(tǒng)工程概論 線 性 規(guī) 劃 LP的數(shù)學(xué)模型 標(biāo)準(zhǔn)型 圖解法 單純形法 人工變量法 以上得到的一組基可行解是不是最優(yōu)解，可以從目標(biāo)函數(shù)中的系數(shù)看出。目標(biāo)函數(shù) Z=3x1+4x2中 x1的系數(shù)大于零，如果 x1為一正數(shù)，則 Z的值就會(huì)增大，同樣若 x2不為零為一正數(shù)，也能使 Z的值增大；因此只要目標(biāo)函數(shù)中非基變量的系數(shù)大于零，那么目標(biāo)函數(shù)就沒(méi)有達(dá)到最大值，即沒(méi)有找到最優(yōu)解，判別線性規(guī)劃問(wèn)題是否達(dá)到最優(yōu)解的數(shù)稱為檢驗(yàn)數(shù)，記作 λj , j=1,2…, n。 本例中 λ1=3,λ2=4,λ3=0,λ4= 31（ a）。 最優(yōu)解判斷標(biāo)準(zhǔn) 當(dāng)所有檢驗(yàn)數(shù) λj≤0（ j=1， … ， n）時(shí)，基本可行解為最優(yōu)解。 當(dāng)目標(biāo)函數(shù)中有基變量 xi時(shí)，利用約束條件將目標(biāo)函數(shù)中的 xi消去即可求出檢驗(yàn)數(shù)。 系統(tǒng)工程概論 線 性 規(guī) 劃 LP的數(shù)學(xué)模型 標(biāo)準(zhǔn)型 圖解法 單純形法 人工變量法 進(jìn)基列 出基行 bi /ai2， ai20 θi 表 31 (a) XB x1 x2 x3 x4 b x3 2 1 1 0 40 x4 1 3 0 1 30 λj 3 4 0 0 (b) x3 x4 λj (c) x1 x2 λj 基變量 1 10 18 0 0 1/3 0 1/3 10 5/3 1 － 1/3 30 40 5/3 0 － 4/3 30 1 0 3/5 － 1/5 18 0 1 － 1/5 － 2/5 4 0 0 － 1 － 1 將 3化為 1 乘以1/3后得到 LP的數(shù)學(xué)模型 標(biāo)準(zhǔn)型 圖解法 單純形法 人工變量法 動(dòng)畫演示 單純形法全過(guò)程的計(jì)算 ， 可以用列表的方法計(jì)算更為簡(jiǎn)潔 ， 這種表格稱為單純形表 （ 表 31） 。 計(jì)算說(shuō)明： ，列出初始單純形表，求出檢驗(yàn)數(shù)。其中基變量的檢驗(yàn)數(shù)必為零； ： （ a） 若 λj≤０ （ j＝１ ， ２ ， … ， n） 得到最優(yōu)解； （ b） 某個(gè) λk0且 aik≤０ （ i=1， 2,… ,m） 則線性規(guī)劃具有無(wú)界解 。 （ c） 若存在 λk0且 aik (i=1,… ,m)不全非正 ， 則進(jìn)行換基； 系統(tǒng)工程概論 線 性 規(guī) 劃 LP的數(shù)學(xué)模型 標(biāo)準(zhǔn)型 圖解法 單純形法 人工變量法 ： （ a） 設(shè) λk0, xk為進(jìn)基變量 ， 求最小比值： iL i kikbm i n a 0a?????????第 Ｌ 個(gè)比值最小 ， 選最小比值對(duì)應(yīng)行的基變量為出基變量 ， 若有相同最小比值 ， 則任選一個(gè) 。 aLk為主元素； (b） 求新的基可行解：用初等行變換方法將 aik 化為 1, k列其它元素化為零 （ 包括檢驗(yàn)數(shù)行 ） 得到新的可行基及基本可行解 ， 再判斷是否得到最優(yōu)解 。 系統(tǒng)工程概論 線 性 規(guī) 劃 LP的數(shù)學(xué)模型 標(biāo)準(zhǔn)型 圖解法 單純形法 人工變量法 【 例 】 用單純形法求解 1 2 3ma x Z x 2 x x? ? ?1 2 31 2 31 2 32 x 3 x 2 x 1 51x x 5 x 2 03x x x 0? ? ????? ? ?????? 、【 解 】 將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式： 1 2 3ma x Z x 2 x x? ? ?1 2 3 41 2 3 5j2 x 3 x 2 x x 151x x 5 x x 203x 0, j 1 , 2, , 5? ? ? ????? ? ? ???????不難看出 x x5可作為初始基變量，單純法計(jì)算結(jié)果如表 32所示 。 系統(tǒng)工程概論 線 性 規(guī) 劃 LP的數(shù)學(xué)模型 標(biāo)準(zhǔn)型 圖解法 單純形法 人工變量法 表 32 Cj 1 2 1 0 0 b θ CB XB x1 x2 x3 x4 x5 0 x4 2 － 3 2 1 0 15 0 x5 1/3 1 5 0 1 20 λj 1 2 1 0 0 0 x4 2 x2 λj 1 x1 2 x2 λj 1/3 1 5 0 1 20 3 0 17 1 3 75 1/3 0 － 9 0 － 2 － 20 25 60 1 0 17/3 1/3 1 25 0 1 28/9 － 1/9 2/3 35/3 0 0 － 98/9 － 1/9 － 7/3 線 性 規(guī) 劃 LP的數(shù)學(xué)模型 標(biāo)準(zhǔn)型 圖解法 單純形法 人工變量法 動(dòng)畫演示 什么是最大流？ ① ② ③ ④ ⑤ ⑥ 4 8 4 4 1 2 2 6 7 9 容量 ：在某時(shí)期內(nèi)弧 (i， j)上的最大通過(guò)能力。記為 C (i， j)或 Cij 在上圖中， C12=4， C13＝ 8， C23＝ 4等，怎樣安排運(yùn)輸方案，才能使在某一時(shí)期內(nèi)從 v1運(yùn)到 v6的物資最多，這樣的問(wèn)題就是最大流問(wèn)題， 網(wǎng)絡(luò)中所有流起源于一個(gè)叫做 發(fā)點(diǎn) 的節(jié)點(diǎn)（源） 所有的流終止于一個(gè)叫做 收點(diǎn) 的節(jié)點(diǎn) 其余所有的節(jié)點(diǎn)叫做 中間點(diǎn) （轉(zhuǎn)運(yùn)點(diǎn)） 通過(guò)每一條弧的流只允許沿著弧的箭頭方向流動(dòng) 目標(biāo) 是使得從發(fā)點(diǎn)到收點(diǎn)的總流量最大 系統(tǒng)工程概論 圖 與 網(wǎng) 絡(luò) 最短路問(wèn)題 最大流問(wèn)題 基本概念 流量： 弧 (i， j)的實(shí)際通過(guò)量，記為 f (i， j)或 f ij 可行流 ：如果 f ij滿足：
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1