[經(jīng)濟(jì)學(xué)]運(yùn)籌學(xué)第二章線性規(guī)劃(參考版)
2024-10-19 22:39本頁面
【正文】 3. 無可行解的判別： 在采用人工變量求解線性規(guī)劃問題得到最優(yōu)解時(shí)，如果基變量中仍含有 非零人工變量 ，則原問題無可行解。這種情況下一般有兩種方法： 大 M法（罰因子法） 兩階段法 34 線性規(guī)劃 Linear Programming（ LP） max z = 3X1 + X3 x1 + x2 + x3 ≤ 4 2x1 + x2 – x3 ≥ 1 3x2 + x3 = 9 x1 ， x2 ， x3 ≥ 0 LPM max z = 3x1 + x3 + 0x4 + 0x5 – Mx6 – Mx7 x1 + x2 + x3 + x4 = 4 2x1 + x2 – x3 x5 + x6 = 1 3x2 + x3 +x7 = 9 x1 ， x2 ， x3 ， x4 ， x5 ， x6 ， x7 ≥ 0 35 線性規(guī)劃 Linear Programming（ LP） 大 M 法求解線性規(guī)劃問題的具體方法與前面的一般單純形法相同，就是將 M當(dāng)作一個(gè)充分大的數(shù)來處理。然而，并非所有 問題標(biāo)準(zhǔn)化之后我們都可得到一個(gè)顯然的 初始基本可行解， 這時(shí)就需要我們首先確定出一個(gè) 基本可行解作為 初始 基本可行解。 28 線性規(guī)劃 Linear Programming（ LP） 其中 b ≥ 0 ， I 是 m?m 單位 矩陣。 當(dāng)?shù)M(jìn)行至某一步時(shí)， ? j 行中所有 檢驗(yàn)數(shù)均小于等于零，且此時(shí)至少有一個(gè) 非基變量所對(duì)應(yīng)的 檢驗(yàn)數(shù) rk等于零，則原線性規(guī)劃問題有無窮多個(gè) 最優(yōu)解。注意這種 變換只能采用初等行變換 ! 27 線性規(guī)劃 Linear Programming（ LP） 最優(yōu)解檢驗(yàn)： 當(dāng)?shù)M(jìn)行至某一步時(shí)， ? j 行中所有 檢驗(yàn)數(shù)均小于等于零，則 迭代結(jié)束。 22 線性規(guī)劃 Linear Programming（ LP） 單純形表 對(duì)于給定的線性規(guī)劃問題： max Z = c1x1 + c2x2 + … + xn a11x1 + a12x2 + … + a1nxn≤ b1 a21x1 + a22x2 + … + a2nxn≤ b2 . … … … am1x1 + am2x2 + … + amnxn≤ bm xj ≥ 0 （ j=1， 2 … n） 對(duì)此問題添加 m個(gè)松弛變量后，可得下面線性規(guī)劃問題并且是 典式的形式。 此時(shí)松弛變量都是 非基變量 （ 取值為零 ） ，這表明資源已用 盡；并且目標(biāo)函數(shù)值 Z3 =1350 5X3 15X4中非基變量 X3， X4的系數(shù)全為負(fù)值，說明目標(biāo)函數(shù)已無法進(jìn)一步改善，因此該解已是最優(yōu)解。 由于 目標(biāo)函數(shù) Z2 =1250+5X225X4中 X2的系數(shù)仍為正，該解 X2仍不是最優(yōu)解。由 典式 以及變量必須取正值的條件，我們可以得到下列不等式關(guān)系： X3 = 120 4X1 3X2 ≥0 X4= 50 2X1 X2 ≥0 18 線性規(guī)劃 Linear Programming（ LP） 因?yàn)榈?X2仍為 非基變量 （ 仍會(huì)令其取值為零 ） ，則上式可簡(jiǎn)化為： 120 4X1 ≥0 50 2X1 ≥0 由此可以看出，雖然我們希望 X1入基后取正值，且取值越大目標(biāo)值增加越大，但是， X1又得受到 約束。對(duì)于求目標(biāo)函數(shù)極大化的問題，我們希望目標(biāo)值增加得越快越好，因此系數(shù)最大的 X1入基。并且換基后仍需滿足： 新的解仍是基本 可行解； 目標(biāo)函數(shù)值將得到改善。只要將目標(biāo)函數(shù)中 系數(shù)為正的某 非基變量 與某一基變量地位對(duì)換。應(yīng)尋找更好的解。因此 ?。?X3， X4為基變量； X1， X2為非基變量。 10 線性規(guī)劃 Linear Programming（ LP） 單純形法迭代原理及其思路 單純形法的初步討論 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 化為 標(biāo)準(zhǔn)型 11 線性規(guī)劃 Linear Programming（ LP） 此線性規(guī)劃問題 轉(zhuǎn)化為了一個(gè)含有四個(gè)變量的 標(biāo)準(zhǔn)形 線性規(guī)劃問題， X3， X4為松弛變量。 基本定理 2 X是線性規(guī)劃問題的 基本可行解的充要條件 為 是 X 是凸集 S={ X | AX = b， X ≥0 }的極點(diǎn)。本節(jié)討論單純形法的基本概念、原理及算法。1 線性規(guī)劃 Linear Programming（ LP） 單 純 形 方 法 2 線性規(guī)劃 Linear Programming（ LP） 單純形方法是 1947年首先發(fā)明的。近 50年來，一直是求解線性規(guī)劃的最有效的方法之一，被廣泛應(yīng)用于各種線性規(guī)劃問題的求解。 3 線性規(guī)劃 Linear Programming（ LP） 給定線性規(guī)劃問題（標(biāo)準(zhǔn)形式） max z = c1x1 + c2x2 + … + xn a11x1 + a12x2 +… + a1nxn = b1 a21x1 + a22x2 +… + a2nxn = b2 . … … … … … am1x1 + am2x2 +… + amnxn = bm xj ≥ 0 （ j=1， 2 … n） 4 線性規(guī)劃 Linear Programm
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1