[經(jīng)濟(jì)學(xué)]運籌學(xué)第二章線性規(guī)劃-展示頁
2024-10-25 22:39本頁面
【正文】 復(fù)上述 迭代過程得到： X2入基， X3出基，則新的 典式 方程變?yōu)椋? X1 = 15 + X2 =20 X3 + 2X4 Z3 =1350 5X3 15X4 20 線性規(guī)劃 Linear Programming（ LP） 第三個 基本可行解 X3 =（ 15， 20， 0， 0） T，其對應(yīng)的目標(biāo)函數(shù)值 Z3=1350 。 21 線性規(guī)劃 Linear Programming（ LP） 單純形法小結(jié)： 單純形法是這樣一種 迭代算法 —— 如下圖 … X1 Z1 保持 單調(diào)增 保持 可行 性 保持 可行 性 保持 可行 性 保持 可行 性 保持 單調(diào)增 保持 單調(diào)增 保持 單調(diào)增 X2 X3 ... Xk Z2 Z3 ... Zk 當(dāng) Zk 中 非基變量 的系數(shù)的系數(shù)全為負(fù)值時，這時的 基本可行解 Xk 即是線性規(guī)劃問題的最優(yōu)解， 迭代結(jié)束。 23 線性規(guī)劃 Linear Programming（ LP） 線性規(guī)劃的典式 max Z = c1x1 + c2x2 + … + xn a11x1 + a12x2 +… + a1nxn + xn+1 = b1 a21x1 + a22x2 +… + a2nxn + xn+2 = b2 . … am1x1 + am2x2 +… + amnxn + xn+m = bm xj ≥ 0 （ j=1， 2 … n， n+1， n+2， … n+m） 24 線性規(guī)劃 Linear Programming（ LP） 將上面 典式中各變量及系數(shù)填寫在一張表格中就形成下面的單純形表 cj ? c1 c2 … +1 … +m ? CB 基 解 x1 x2 … xn xn+1 … xn+1 0 0 0 0 xn+1 xn+2 … xn+m b1 b2 … bm a11 a12 … a1n 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 作為主元對 單純形表進(jìn)行初等行變換（取 主 運算），即將 aij 所在列除采用初等行變換 將 aii 變換為 1外的其余元素都 變換為 0。 表中當(dāng)前 所指 基本可行解即為 最優(yōu)解。 當(dāng)?shù)M(jìn)行至某一步時， ? j 行中至少有一個 檢驗數(shù) rk 大于零，且該檢驗數(shù)對應(yīng)的 列中 a1k ， a2k ， … amk ， 均 小 于等于 零，則原線性規(guī)劃問題 最優(yōu)解無界（ max Z→ +∞ ）。 對上面 （ I 式 ） 經(jīng)過迭代， 并設(shè)最終的最優(yōu)基矩陣為 B,不妨設(shè)B 為 A 的首 m 列，則將（ I 式 ）改寫后有 單純形方法的矩陣描述： 設(shè)線性規(guī)劃問題 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 ，檢驗數(shù) CN CB B 1 ≤ 0 ， C
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1