【正文】 Max Z = CX . AX=b X ? 0 基，基解，基可行解，可行基。 ⊙ 線性規(guī)劃問題的可行域 D是凸集。 ⊙ 頂點與基可行解相對應(yīng) ⊙ 線性規(guī)劃問題的最優(yōu)解，必定在 D的頂點上達(dá)到。 ⊙ 目標(biāo)函數(shù)在多個頂點上達(dá)到最優(yōu)值。這些頂點的凸組合也是最優(yōu)值。（有無窮多最優(yōu)解）。 第 3節(jié) 線性規(guī)劃 單純形方法 單純形方法基本思路： ?從可行域中某個基可行解（一個頂點）開始（稱為初始基可行解）。 線性規(guī)劃（ 2） 單純形方法 單純形方法基本思路： ?從可行域中某個基可行解（一個頂點）開始（稱為初始基可行解）。 ?如可能，從可行域中求出具有更優(yōu)目標(biāo)函數(shù)值的另一個基可行解（另一個頂點），以改進(jìn)初始解。 線性規(guī)劃（ 2） 單純形方法 單純形方法基本思路： ?從可行域中某個基可行解（一個頂點）開始（稱為初始基可行解）。 ?如可能，從可行域中求出具有更優(yōu)目標(biāo)函數(shù)值的另一個基可行解（另一個頂點），以改進(jìn)初始解。 ?繼續(xù)尋找更優(yōu)的基可行解，進(jìn)一步改進(jìn)目標(biāo)函數(shù)值。當(dāng)某一個基可行解不能再改善時，該解就是最優(yōu)解。 第三節(jié) 線性規(guī)劃 單純形方法 單純形方法基本思路： （一個頂點）開始（稱為初始基可行解）。 ，從可行域中求出具有更優(yōu)目標(biāo)函數(shù)值的另一個基可行解（另一個頂點），以改進(jìn)初始解。 ，進(jìn)一步改進(jìn)目標(biāo)函數(shù)值。當(dāng)某一個基可行解不能再改善時，該解就是最優(yōu)解。 一、消去法 例 1：一個企業(yè)需要同一兩種原材料生產(chǎn)甲乙兩種產(chǎn)品，它們的單位產(chǎn)品所需要的原材料的數(shù)量及所耗費的加工時間各不相同，從而獲得的利潤也不相同（如下表）。那么，該企業(yè)應(yīng)如何安排生產(chǎn)計劃，才能使獲得的利潤達(dá)到最大？ 產(chǎn)品 / 資源 甲 乙可利用的資源總量原材料 1 （噸） 1 2 8原材料 2 （噸） 4 0 16加工時間（小時） 0 4 12解：數(shù)學(xué)模型 max Z = 2x1 + 3x2 . x1+2x2 ≤ 8 4x1 ≤16 4x2 ≤12 x1,x2≥0 解：引進(jìn)松弛變量 x3,x4 ,x5 = 0 數(shù)學(xué)模型標(biāo)準(zhǔn)形式： max Z = 2x1 +3x2 . x1+2x2 +x3 = 8 4x1 +x4 = 16 4x2 +x5 = 12 x1 , x2 , x3 , x4 ,x5 ≥ 0 約束條件的增廣矩陣為： 1 2 1 0 0 8 （ A b)= 4 0 0 1 0 16 0 4 0 0 1 12 顯然 r(A) = r(Ab) = 3 5,該問題有無窮多組解。 令 A=（ P1， P2， P3， P4 ， P5） = 1 2 1 0 0 4 0 0 1 0 0 4 0 0 1 X=（ x1, x2, x3, x4 , x5) A=（ P1， P2， P3， P4 ， P5 ） = 1 2 1 0 0 4 0 0 1 0 0 4 0 0 1 X=（ x1, x2, x3, x4 , x5)T B=(P3， P4 ， P5 ） = 1 0 0 0 1 0 0 0 1 x3, x4 , x5是基變量， x1, x2,是非基變量。 用非基變量表示的方程： x3 = 8 x1 2x2 x4 = 16 4x1 (I) x5 = 12 4x2 Z = 0+ 2x1 +3x2 稱 (I) 為消去系統(tǒng) ， 令非基變量 （ x1 , x2） T=（ 0， 0） T 得基可行解： x(1)=(0,0,8,16,12) T Z1=0 經(jīng)濟(jì)含義： 不生產(chǎn)產(chǎn)品甲乙，利潤為零 。 分析： Z = 0+ 2x1 + 3x2 （分別增加單位產(chǎn)品甲、乙，目標(biāo)函數(shù)分別增加 3，即利潤分別增加 2百元、 3百元。） 增加單位產(chǎn)品對目標(biāo)函數(shù)的貢獻(xiàn)，這就是檢驗數(shù)的概念。 增加單位產(chǎn)品乙（ x2）比甲對目標(biāo)函數(shù)的貢獻(xiàn)大 （檢驗數(shù)最大）， 把非基變量x2換成基變量，稱 x2為換入基變量，而把基變量 x5換成非基變量，稱 x5為換出基變量。 （在選擇出基變量時，一定保證消去系統(tǒng)為正消去系統(tǒng)） （最小比值原則） 增加單位產(chǎn)品甲（ x2）比乙對目標(biāo)函數(shù)的貢獻(xiàn)大（檢驗數(shù)最大），把非基變量x2換成基變量，稱 x2為換入基變量，而把基變量 x5換成非基變量，稱 x5為換出基變量。 （在選擇出基變量時，一定保證消去系統(tǒng)為正消去系統(tǒng)）（最小比值原則） 事實上，當(dāng) x1 =0，有 x3 = 8 2x2≥0 x4 = 16≥0 （ Ⅱ ） x5 = 12 4 x2 ≥0 min(8/2,12/4)=3, 當(dāng) x2=0時， x5=0。 x5換出基變量。 確定了 換入變量 x2 ， 換出變量 x5 以后，得到新的消去系統(tǒng)： x3+2 x2 = 8 x1 （ 1） x3 = 2 x1+（ 1/2） x5 x4 = 164x1 （ 2） (Ⅲ )即： x4 = 164 x1 4x2 = 12 x5 （ 3） x2= 3 （ 1/4） x5 其中（ 1） — 1/2（ 3） Z= 9＋ 2 x1 （ 3/4） x5 令新的非基變量（ x1， x5 ） =（ 0， 0） T 得到新的基可行解： x(2)=(0,3,2, 16 , 0) T S2= 9 經(jīng)濟(jì)含義：生產(chǎn)乙產(chǎn)品 3個，獲得利潤 9百元。 這個方案比前方案好，但是否是最優(yōu)？ 這個方案比前方案好，但是否是最優(yōu)？ 分析： Z= 9＋ 2 x1 （ 3/4） x5 非基變量 x1系數(shù)仍為正數(shù)，確定 x1為換入變量。在保證正消去系統(tǒng)的情況下，確定 x3為換出變量。得到新的消去系統(tǒng)： 這個方案比前方案，但是否是最優(yōu)？ 分析： Z=180x2+（ 3/2） x4 非基變量 x2系數(shù)仍為負(fù)數(shù)，確定 x2為換入變量。在保證常數(shù)項非負(fù)的情況下， x1 換入， x5=0 。 有 x3 = 2x1≥0 x4 = 16 4x1 ≥0 (Ⅵ ) x2= 3 ≥0 min{2,4, }=2 確定 x3為換出變量。得到新的消去系統(tǒng)： x1 = 2x3+（ 1/2)x5 x1 = 2x3+（ 1/2)x5 4x1 + x4 = 16 （ Ⅴ ）即 x4 = 8+ 4x3 2 x5 x2 =3(1/4) x5 x2 =3(1/4) x5 Z = 132x3+（ 1/4） x5 令新的非基變量（ x3， x5 ） =（ 0， 0） T 得到新的基可行解： x(3)=(2,3,0, 16 , 0) T S3=13 經(jīng)濟(jì)含義：生產(chǎn)甲產(chǎn)品 2個，乙產(chǎn)品 3個，獲得利潤 1300元。 分析： Z = 132x3+（ 1/4） x5 x5系數(shù)仍為正數(shù)，確定 x5為換入變量。在保證常數(shù)項非負(fù)的情況下， x5換入， x3=0 。 有 x1 = 2+（ 1/2） x5≥0 x4 = 8 2x5 ≥0 (Ⅵ ) x2= 3（ 1/4） x5 ≥0 min{ ,4,12 }= 4 確定 x4為換出變量。有 x1 （ 1/2） x5 =2x3