[管理學(xué)]線性規(guī)劃的圖解法與單純形解法-全文預(yù)覽
【正文】 [ 3] 1 0 1 0 1 1 0 0 1 3 12 5 — 4 5 σ j 2 1 0 0 0 z = 0 單純形法計(jì)算舉例 c j 2 1 0 0 0 C B X B x 1 x 2 x 3 x 4 x 5 b θ i 0 2 0 x 3 x 1 x 5 0 1 1 0 0 1 1/3 0 1/3 0 0 [ 2/3 ] 0 1/3 1 3 4 1 3 12 3/2 σ j 0 1/3 0 2 /3 0 z =8 單純形法計(jì)算舉例 c j 2 1 0 0 0 C B X B x 1 x 2 x 3 x 4 x 5 b θ i 0 2 1 x 3 x 1 x 2 0 0 1 1/2 3/2 1 0 0 1/2 1/2 0 1 0 1/2 3/2 3/2 7/2 3/2 σ j 0 0 0 1/2 1/2 z = 17/2 單純形法計(jì)算的矩陣描述 對(duì)標(biāo)準(zhǔn)形式的線性規(guī)劃問(wèn)題 m a x0z C XA X bX????=≥ 假定存在基 B ，基變量為BX，非基變量為NX，則有 111111()()BNB B N N B N N NB N B NX B b B N Xz C X C X C B b B N X C XC B b C C B N X????????? ? ? ? ?? ? ? 單純形法計(jì)算的矩陣描述 與前面檢驗(yàn)數(shù)計(jì)算公式對(duì)照，可得非基變量檢驗(yàn)數(shù)計(jì)算公式 1N N BC C B N???? 另外，基變（向）量 XB的檢驗(yàn)數(shù)可寫作 1 0B B BC C B B??? ? ? 所以可得標(biāo)準(zhǔn)形式的線性規(guī)劃模型檢驗(yàn)數(shù)計(jì)算的一般計(jì)算公式 1BC C B A???? 單純形法計(jì)算的矩陣描述 再考慮下列線性規(guī)劃問(wèn)題 m a x0z C XA X bX????≤≥ 上式加上松弛變量后為 m a x 00 , 0SSSz CX XA X I X bXX???????≥ ≥ 單純形法計(jì)算的矩陣描述 ? ?m a x z | 0SXCX??? ???? ? ??????????????0,|XXbXXIASS 式中，X S松馳變量，),( 21TxxxX mnnnS ???? ? ， I 為 nm ? 單位矩陣。 ? 最佳換入換出變量確定 ???????????????????????pqpapqabpqq00m i nm a x ??單純形表 c j c 1 c 2 … c m c m + 1 … c m + k … c n c B X B x 1 x 2 … x m x m + 1 … x m + k … x n b θ i c 1 c 2 ? c m x 1 x 2 ? x m 1 0 ? 0 0 1 ? 0 … … … … 0 0 ? 1 a 1 , m + 1 a 2 , m + 1 ? a m , m + 1 … … … a 1 , m + k a 2 , m + k ? a m , m + k … … ?… a 1n a 2n ? a mn b 1 b 2 ? b m θ 1 θ 2 ? θ m ????miijijj acc1? 0 0 … 0 σm + 1 … σ m + k … σ n ???miii bcz1 單純形算法的計(jì)算步驟 ① 將線性規(guī)劃問(wèn)題化成標(biāo)準(zhǔn)型。 換入變量的確定 jnmjj xzz ?????10 ?如果存在多個(gè) σj 0, 則取 0,?? km? 假定存在一個(gè) 我們?nèi)? kmx ?為換入變量。 尋找改進(jìn)的基可行解 ? 當(dāng)檢驗(yàn)?zāi)硞€(gè)基可行解不是最優(yōu)、也非無(wú)界，那么就應(yīng)該從該頂點(diǎn)（基可行解）處出發(fā)，尋找一個(gè)新的能使目標(biāo)函數(shù)值改進(jìn)的相鄰頂點(diǎn)（基可行解）。 在線性規(guī)劃模型中，可以用檢驗(yàn)數(shù) 替代目標(biāo)函數(shù)中的價(jià)值系數(shù) cj。 ? 單純形算法必須解決三個(gè)方面的問(wèn)題： 1. 如何確定初始的基可行解？ 2. 如何進(jìn)行解的最優(yōu)性判別？ 3. 如何尋找改進(jìn)的基可行解？ 確定初始的基可行解 ? 標(biāo)準(zhǔn)型的線性規(guī)劃問(wèn)題 ??????????0m a x1XbxPCXznjjj???????????????100000100001),( 21????? mPPP系數(shù)矩陣中存在一個(gè)單位陣 以單位陣為一初始可行基。尋找線性規(guī)劃問(wèn)題的最優(yōu)解只需比較有限個(gè)頂點(diǎn)處的目標(biāo)函數(shù)值。 如在上例中，只含有 x2 ≤3一個(gè)約束，可行域?yàn)闊o(wú)界， z的取值可無(wú)窮大。如上例。運(yùn)籌學(xué) Operations Research 吳清烈 東南大學(xué)經(jīng)濟(jì)管理學(xué)院 電子商務(wù)系暨管理工程研究所 02583795358, 13337835398, 線性規(guī)劃的圖解法與單純形解法 ? 線性規(guī)劃問(wèn)題的圖解法 ? 線性規(guī)劃單純形解法的原理 ? 線性規(guī)劃單純形解法的計(jì)算步驟 ? 單純形法計(jì)算的矩陣描述 ? 線性規(guī)劃單純形求解的大 M法 ? 線性規(guī)劃單純形求解的兩階段法 ? 線性規(guī)劃單純形求解可能的循環(huán)現(xiàn)象 ? 線性規(guī)劃單純形法的改進(jìn) 線性規(guī)劃問(wèn)題的圖解法 ? 圖解法，就是用作圖的方法求解線性規(guī)劃問(wèn)題。 線性規(guī)劃問(wèn)題的圖解法舉例 max z =2 x1+x2 3x1+x2 ≤12 x1+x2 ≤5 x2 ≤3 x1， x2 ≥0 1 2 3 4 5 1 2 3 4 x2x1Q13 x1+ x2= 1 2 x1+ x2= 5Q2 ( 3 . 5 , 1 . 5 )目 標(biāo) 函 數(shù) 線 z = 0 可 行 域 為O Q1 Q2 Q3 Q4x2 = 3Q4 Q3 ON線性規(guī)劃問(wèn)題求解的幾種可能結(jié)局 ? 存在唯一最優(yōu)解。 ? 存在無(wú)界解（有可行解但無(wú)有界最優(yōu)解） 。 由圖解法得到的啟示 ? 線性規(guī)劃問(wèn)題求解的基本依據(jù)是：線性規(guī)劃問(wèn)題的最優(yōu)解總可在可行域的頂點(diǎn)中尋找。 線性規(guī)劃單純形解法的原理 ? 單純形方法的基本思想 從可行域中的一個(gè)基可行解出發(fā)，判別它是否已經(jīng)是最優(yōu)解，如不是，尋找下一個(gè)基可行解，并且同時(shí)努力使目標(biāo)函數(shù)得到改進(jìn)，如此迭代下去，直到找到最優(yōu)解或判定問(wèn)題無(wú)解為止。方程右邊，得如下形式： 11 , 2 , ,ni i i j jjmx b a x i m????? ? ??最優(yōu)性檢驗(yàn)和解的判別 將上式代入目標(biāo)函數(shù)式中，整理得 jnmjmiijijmiii xaccbcz )(1 11? ???? ???????????miii bcz10 nmjaczmiijij ,1,1????? ??令 jnmjjj xzczz )(10 ??????最優(yōu)性檢驗(yàn)和解的判別 nmjzc jjj
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1