[經(jīng)濟(jì)學(xué)]運(yùn)籌學(xué)第二章線性規(guī)劃(編輯修改稿)
2024-11-12 22:39 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 1 a21 a22 … a2n … … … … … … am1 am2 … amn 1 ?1 ?2 … ?m ?j = cj – zj ? c1 c2 … 0 … 0 ?j = cj – zj ? ?1 ? 2 … ? n ?n+1 … ?n+m 25 線性規(guī)劃 Linear Programming（ LP） 上面 的 單純形表還可以表示成矩陣的形式 基 解 X XS ? XS b A I ?j ? C 0 基 解 XB XN XS ? XS b B N I ?j ? CB CN 0 26 線性規(guī)劃 Linear Programming（ LP） 由單純形表進(jìn)行 迭代步驟： 1. 選擇 Xj 入基：當(dāng) ?j 行中 cj= max { ci∣c i ? 0} 2. 選擇 Xi 出基：當(dāng) ?i = min{(bi/aij)∣a ij ? 0} 3. 換基 迭代：當(dāng)確定了 入基變量 Xj 、出基變量 Xi 后，以 aij 作為主元對(duì) 單純形表進(jìn)行初等行變換（取 主 運(yùn)算），即將 aij 所在列除采用初等行變換 將 aii 變換為 1外的其余元素都 變換為 0。注意這種 變換只能采用初等行變換 ! 27 線性規(guī)劃 Linear Programming（ LP） 最優(yōu)解檢驗(yàn)： 當(dāng)?shù)M(jìn)行至某一步時(shí)， ? j 行中所有 檢驗(yàn)數(shù)均小于等于零，則 迭代結(jié)束。 表中當(dāng)前 所指 基本可行解即為 最優(yōu)解。 當(dāng)?shù)M(jìn)行至某一步時(shí)， ? j 行中所有 檢驗(yàn)數(shù)均小于等于零，且此時(shí)至少有一個(gè) 非基變量所對(duì)應(yīng)的 檢驗(yàn)數(shù) rk等于零，則原線性規(guī)劃問(wèn)題有無(wú)窮多個(gè) 最優(yōu)解。 當(dāng)?shù)M(jìn)行至某一步時(shí)， ? j 行中至少有一個(gè) 檢驗(yàn)數(shù) rk 大于零，且該檢驗(yàn)數(shù)對(duì)應(yīng)的 列中 a1k ， a2k ， … amk ， 均 小 于等于 零，則原線性規(guī)劃問(wèn)題 最優(yōu)解無(wú)界（ max Z→ +∞ ）。 28 線性規(guī)劃 Linear Programming（ LP） 其中 b ≥ 0 ， I 是 m?m 單位 矩陣。 對(duì)上面 （ I 式 ） 經(jīng)過(guò)迭代， 并設(shè)最終的最優(yōu)基矩陣為 B,不妨設(shè)B 為 A 的首 m 列，則將（ I 式 ）改寫(xiě)后有 單純形方法的矩陣描述： 設(shè)線性規(guī)劃問(wèn)題 max Z = CX max Z = CX + 0XS . AX ≤ b . AX + I XS = b （ I 式 ） X ≥ 0 X ， XS ≥ 0 29 線性規(guī)劃 Linear Programming（ LP） max Z = CBXB + CNXN + 0XS . BXB + NXN + I XS = b XB ， XN， XS ≥ 0 max Z = CB B 1+（ CN CB B 1） XN CB B 1XS . XB + B 1NXN + B 1XS = B 1b XB ， XN， XS ≥ 0 B 式中 最優(yōu) 目標(biāo)函數(shù)值 Z*= CB B 1 ，檢驗(yàn)數(shù) CN CB B 1 ≤ 0 ， CB B 1 ≤ 0 單純形方法 迭代 （ I 式） （ B 式 ） 30 線性規(guī)劃 Linear Programming（ LP） 單純形方法的矩陣描述： 基 解 XB XN XS ? XS b B N I ?j ? CB CN 0 基 解 XB XN XS ? XB B 1b I B 1N B 1 ?j ? 0 CN CB B –1N CB B 1 對(duì)應(yīng) I 式 的 單純形表 —— I 表 對(duì)應(yīng) B 式 的 單純形表 —— B 表 迭代 31 線性規(guī)劃 Linear Programming（ LP） 單純形表計(jì)算步驟舉例 給定線性規(guī)劃問(wèn)題 max z = 50X1 + 30X2 . 4X1+3X2 ≤ 120 2X1+ X2 ≤ 50 X1， X2 ≥ 0 max z = 50X1 + 30X2 . 4X1+ 3X2 + X3 = 120 2X1+ X2 + X4 = 50 X1， X2 ， X3 ， X4 ≥ 0 32 線性規(guī)劃 Linear Programming（ LP） 基 XB
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1