[經(jīng)濟(jì)學(xué)]運(yùn)籌學(xué) 第二章 線性規(guī)劃-預(yù)覽頁(yè)
【正文】 3=1350 。 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 作為主元對(duì) 單純形表進(jìn)行初等行變換（取 主 運(yùn)算），即將 aij 所在列除采用初等行變換 將 aii 變換為 1外的其余元素都 變換為 0。 當(dāng)?shù)M(jìn)行至某一步時(shí)， ? j 行中至少有一個(gè) 檢驗(yàn)數(shù) rk 大于零，且該檢驗(yàn)數(shù)對(duì)應(yīng)的 列中 a1k ， a2k ， … amk ， 均 小 于等于 零，則原線性規(guī)劃問題 最優(yōu)解無界（ max Z→ +∞ ）。通常采用的是人工變量法來確定這樣的初始 基本可行解。 49 作業(yè) (第三版 ) 習(xí)題： (1)(3) (1) (1) (1)(3) 50 練習(xí)題 用單純形法求解 : max Z = 2X1 X2 + X3 3X1 + X2 + X3 ≤ 60 . X1 X2 + 2X3 ≤ 10 X1 + X2 X3 ≤ 20 X1， X2 ， X3 ≥ 0 51 練習(xí)題 用單純形法求解 : max Z = 6X1 +2 X2 + 10X3 +8X4 5X1 + 6X2 4X3 4X4 ≤ 20 . 3X1 3X2 +2X3 +8X4 ≤25 4X1 2X2 + X3 +3X4 ≤ 10 X1， X2 ， X3 ， X4≥ 0 52 練習(xí)題 用單純形法求解 : max Z = X1 +6X2 + 4X3 X1 + 2X2 + 2X3 ≤ 13 . 4X1 4X2 + X3 ≤20 X1 + 2X2 + X3 ≤ 17 X1 ≥ 1 ， X2 ≥ 2 ， X3 ≥3 53 練習(xí)題 用大 M法和兩階段法求解 : max Z = X1 +2 X2 + 3X3 X4 X1 + 2X2 +3X3 = 15 . 2X1 + X2 + 5X3 =20 X1 + 2X2 + X3 +X4 = 10 X1， X2 ， X3 ， X4≥ 0 54 作業(yè) (第二版 ) 習(xí)題： (1)(3) (1) (1) (1)(3)
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1