[經(jīng)濟(jì)學(xué)]運籌學(xué)第二章線性規(guī)劃-wenkub
2022-10-31 22:39:30 本頁面
【正文】 X4 0 0 0 0 1 1/2 1/2 1/2 X2 3 0 1 1/3 0 0 0 1/3 X1 1 1 0 2/3 0 1/2 1/2 1/6 檢驗數(shù) ?j 0 0 0 0 0 1 1 46 線性規(guī)劃 Linear Programming（ LP） 第 II 階段 基 XB 解 B1b X1 X2 X3 X4 X5 X6 X7 ? X4 0 0 0 0 1 1/2 1/2 1/2 X2 3 0 1 1/3 0 0 0 1/3 X1 1 1 0 2/3 0 1/2 1/2 1/6 檢驗數(shù) ?j 0 0 0 0 0 1 1 3 3/2 47 線性規(guī)劃 Linear Programming（ LP） 第 II 階段 基 XB 解 B1b X1 X2 X3 X4 X5 ? X4 0 0 0 0 1 1/2 X2 3 0 1 1/3 0 0 9 X1 1 1 0 2/3 0 1/2 3/2 檢驗數(shù) ?j 0 0 3 0 3/2 基 XB 解 B1b X1 X2 X3 X4 X5 ? X4 0 0 0 0 1 1/2 X2 5/2 1/2 1 0 0 1/4 X3 3/2 3/2 0 1 0 3/4 檢驗數(shù) ?j 9/2 0 0 0 3/4 48 線性規(guī)劃 Linear Programming（ LP） 1. 目標(biāo)函數(shù)極小化時，解的最優(yōu)判別： ?j ≥ 0 2. 退化： 一個或幾個 基變量 等于零，一個簡單易行的避免退化的方法是 1974年由勃蘭德（ Bland）提出的 Bkand 法則。 對上面 （ 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 ， 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 對應(yīng) I 式 的 單純形表 —— I 表 對應(yīng) B 式 的 單純形表 —— B 表 迭代 31 線性規(guī)劃 Linear Programming（ LP） 單純形表計算步驟舉例 給定線性規(guī)劃問題 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 解 B1b X1 X2 X3 X4 ? X3 120 4 3 1 0 X4 50 2 1 0 1 檢驗數(shù) ?j 50 30 0 0 120/4 50/2 1 1 1/2 1/2 25 020 1 2 0 5 25 20/1 25 2 215 0 1/2 30 5 1533 線性規(guī)劃 Linear Programming（ LP） 人工變量法： 當(dāng)一般線性規(guī)劃問題標(biāo)準(zhǔn)化之后，我們或可得到一個顯然的 基本可行解（如 松弛變量作為 基變量的一個 初始 基本可行解），這樣我們就可以馬上進(jìn)入 單純形表的運算步驟。 表中當(dāng)前 所指 基本可行解即為 最優(yōu)解。 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é)束。 顯然，只有 取 X1 =min（ 120/4， 50/2） =25時，才能使上述不等式成立并且恰使 基變量 X4變?yōu)榱?，這正好滿足非基變量必須取 值 零的條件，所以可 令 X4 出基， 方程變?yōu)椋? 4X1+ X3 =120 3X2
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1