【文章內(nèi)容簡(jiǎn)介】 xn 0 a11 a12 …. a 1n b1 A= a21 a22 …. a 2n b = b2 …………………………… ………. am1 am2 …. a mn bn 0???XbAXCXM a x z如何將一般問題化為標(biāo)準(zhǔn)型： ?若目標(biāo)函數(shù)是求最小值 Min S = CX 令 S’= S, 則 Max S’= CX 如何將一般問題化為標(biāo)準(zhǔn)型： ?若目標(biāo)函數(shù)是求最小值 Min S = CX 令 S’= S, 則 Max S’= CX ?若約束條件是不等式 如何將一般問題化為標(biāo)準(zhǔn)型： ?若目標(biāo)函數(shù)是求最小值 Min S = CX 令 S’= S, 則 Max S’= CX ?若約束條件是不等式 ?若約束條件是“ ?”不等式 n ? aijxj + yi = bi j=1 yi ? 0是非負(fù)的 松馳變量 如何將一般問題化為標(biāo)準(zhǔn)型： ?若約束條件是“ ?”不等式 n ? aijxj zi = bi j=1 zi ? 0是非負(fù)的松馳變量 如何將一般問題化為標(biāo)準(zhǔn)型： ?若約束條件右面的某一常數(shù)項(xiàng) bi0 這時(shí)只要在 bi相對(duì)應(yīng)的約束方程兩邊乘 上 1。 如何將一般問題化為標(biāo)準(zhǔn)型： ?若約束條件右面的某一常數(shù)項(xiàng) bi0 這時(shí)只要在 bi相對(duì)應(yīng)的約束方程兩邊乘上 1。 ?若變量 xj無非負(fù)限制 引進(jìn)兩個(gè)非負(fù)變量 xj’ xj” ? 0 令 xj= xj’ xj” 如何將一般問題化為標(biāo)準(zhǔn)型： ?若約束條件右面的某一常數(shù)項(xiàng) bi0 這時(shí)只要在 bi相對(duì)應(yīng)的約束方程兩邊乘上 1。 ?若變量 xj無非負(fù)限制 引進(jìn)兩個(gè)非負(fù)變量 xj’ xj”=0 令 xj= xj’ xj”（可正可負(fù)） 任何形式的線性規(guī)劃總可以化成標(biāo)準(zhǔn)型 例 6 將下列問題化成標(biāo)準(zhǔn)型 : Min S = x1+2x23x3 . x1+x2+x3 ? 7 x1x2+x3 ? 2 3x1+x2+2x3 = 5 x1,x2 ? 0 x3 無非負(fù)限制 Max S ’ = x12x2+3x3’3x3” . x1+x2+x3’x3”+x4 =7 x1x2+ x3’x3”x5=2 3x1+x2+2x3’2x3” =5 x1, x2,x3’,x3”, x4,x5 ? 0 例 6 將下列問題化成標(biāo)準(zhǔn)型 : Min S = x1+2x23x3 . x1+x2+x3 ? 7 x1x2+x3 ? 2 3x1+x2+2x3 = 5 x1,x2 ? 0 x3 無非負(fù)限制 （二維）線性規(guī)劃問題圖解法： （ 1）滿足約束條件的變量的值，稱 為可行解。 （二維）線性規(guī)劃問題圖解法： （ 1）滿足約束條件的變量的值，稱為可行解 。 （ 2）使目標(biāo)函數(shù)取得最優(yōu)值的可行解，稱為最優(yōu)解。 （二維）線性規(guī)劃問題圖解法： （ 1）滿足約束條件的變量的值，稱為可行解。 （ 2）使目標(biāo)函數(shù)取得最優(yōu)值的可行解，稱為最優(yōu)解。 例 1的數(shù)學(xué)模型 max S=50x1+30x2 . 4x1+3x2 ? 120 2x1+x2 ? 50 x1,x2 ? 0 x2 50 40 30 20 10 10 20 30 40 x1 4x1+3x2 ? 120 由 4x1+3x2 ? 120 x1 ? 0 x2 ? 0 圍成的區(qū)域 x2 50 40 30 20 10 10 20 30 40 x1 2x1+x2 ? 50 由 2x1+x2 ? 50 x1 ? 0 x2 ? 0 圍成的區(qū)域 x2 50 40 30 20 10 10 20 30 40 x1 2x1+x2 ? 50 4x1+3x2 ? 120 可行域 同時(shí)滿足： 2x1+x2 ? 50 4x1+3x2 ? 120 x1 ? 0 x2 ? 0 的區(qū)域 —— 可行域 x2 50 40 30 20 10 10 20 30 40 x1 可行域 O（ 0， 0） Q1（ 25， 0） Q2（ 15， 20） Q3（ 0， 40） 可行域是由約束條件圍成的區(qū)域，該區(qū)域內(nèi)的每一點(diǎn)都是可行解，它的全體組成問題的解集合。 該問題的可行域是由 O，Q1， Q2， Q3作為頂點(diǎn)的凸多邊形 x2 50 40 30 20 10 10 20 30 40 x1 可行域 目標(biāo)函數(shù)是以 S作為參數(shù)的一組平行線 S=50x1+30x2 x2 = S/30（ 5/3） x1 2＜ 5/3＜ 4/3 x2 50 40 30 20 10 10 20 30 40 x1 可行域 當(dāng) S值不斷增加時(shí)，該直線 x2 = S/30（ 5/3） x1 沿著其法線方向向右上方移動(dòng)。 x2 50 40 30 20 10 10 20 30 40 x1 可行域 當(dāng)該直線移到 Q2點(diǎn)時(shí)， S（目標(biāo)函數(shù)）值達(dá)到最大： Max S=50*15+30*20=1350 此時(shí)最優(yōu)解 =（ 15， 20） Q2（ 15， 20） 二個(gè)重要結(jié)論： ?滿足約束條件的可行域一般都構(gòu)成凸多邊形。這一事實(shí)可以推廣到更多變量的場(chǎng)合。 二個(gè)重要結(jié)論： ?滿足約束條件的可行域一般都構(gòu)成凸多邊形。這一事實(shí)可以推廣到更多變量的場(chǎng)合。 ?最優(yōu)解必定能在凸多邊形的某一個(gè)頂點(diǎn)上取得，這一事實(shí)也可以推廣到更多變量的場(chǎng)合。 解的討論： ?最優(yōu)解是唯一解 ； 解的討論： ?最優(yōu)解是唯一解； ?無窮多組最優(yōu)解： 例 1的目標(biāo)函數(shù)由 max S=50x1+30x2 變成： max S=40x1+30x2 . 4x1+3x2 ? 120 2x1+x2 ? 50 x1,x2 ? 0 例 1 max S=50x1+30x2 . 4x1+3x2 ? 120 2x1+x2 ? 50 x1,x2 ? 0 x2 50 40 30 20 10 10 20 30 40 x1 可行域 目標(biāo)函數(shù)是同約束條件： 4x1+3x2 ? 120平行的直線 x2 = S/30（ 4/3） x1 x2 50 40 30 20 10 10 20 30 40 x1 可行域 當(dāng) S的值增加時(shí)，目標(biāo)函數(shù)同約束條件：4x1+3x2 ?120 重合， Q1與 Q2之間都是最優(yōu)解。 Q1（ 0， 40） Q2（ 15， 20） 解的討論： ?無界解： 例： max S=x1+x2 . 2x1+x2 ? 40 x1x2 ? 20 x1,x2 ? 0 x2 50 40 30 20 10 10 20 30 40 x1 該可行域無界，目標(biāo)函數(shù)值可增加到無窮大，稱這種情況為無界解或無最優(yōu)解。