【正文】 到用非基變量表達(dá)的目標(biāo)函數(shù) ， 其系數(shù)就是檢驗(yàn)數(shù)；第二種算法是利用公式計(jì)算 ， 如 （ 2） M是一個(gè)很大的抽象的數(shù) ， 不需要給出具體的數(shù)值 ，可以理解為它能大于給定的任何一個(gè)確定數(shù)值； ? ? MMM 232)(10)4()(31 ?????????????最優(yōu)解 X＝（ 31/3， 13， 19/3， 0， 0)T；最優(yōu)值 Z＝ 152/3 注意： 51 【 例 】 求解線性規(guī)劃 ????????????0,426385m i n21212121xxxxxxxxZ52 【 解 】 加入松馳變量 x x4化為標(biāo)準(zhǔn)型 ???????????????4,2,1,0426385m i n42132121?jxxxxxxxxxZj在第二個(gè)方程中加入人工變量 x5，目標(biāo)函數(shù)中加上 M x5一項(xiàng)，得到 ?????????????????5,2,1,0426385m i n5421321521?jxxxxxxxxMxxxZj53 用單純形法計(jì)算如下表所示。 ? 人工變量法的基本思路是： 若原線性規(guī)劃問題的系數(shù)矩陣中沒有單位向量，則在每個(gè)約束方程中加入一個(gè)人工變量便可在系數(shù)矩陣中形成一個(gè)單位向量。 j，迭代后為P j ，則有P jBP 39。 32 最優(yōu)解的判別定理 ? 定理 1 最優(yōu)解的判別定理 若 ? ? T( 0 )12 , , , , 0 , , 0mX b b b? ? ??為對(duì)應(yīng)于基 B 的一個(gè)基可行解，對(duì)于一切 j = m +1 , … , n , 有檢驗(yàn)數(shù) ? j≤ 0, 則 X ( 0 ) 為最優(yōu)解。 20 【 例 】 利用單純形列表算法求解例 ????????????0,30340243max21212121xxxxxxxxZ21 【 例 】 用單純形法求解 ????????????02053115232321321321xxxxxxxxx、321 2m ax xxxZ ???22 321 2m a x xxxZ ???【 解 】 將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式： ?????????????????5,2,1,0205311523253214321?jxxxxxxxxxj不難看出 x x5可作為初始基變量，單純法計(jì)算結(jié)果如表 。 本例中 σ 1=3, σ 2=4, σ 3=0, σ 4=0。尋找線性規(guī)劃問題的最優(yōu)解只需比較有限個(gè)頂點(diǎn)處的目標(biāo)函數(shù)值。 3 x1 x2 O 10 20 30 40 10 20 30 40 (15,10) 最優(yōu)解 X=(15,10) 最優(yōu)值 Z=85 402 21 ?? xx 21 ?? xx0,0402212121??????xxxxxx例 21 43m a x xxZ ??4 2 4 6 x1 x2 2 4 6 最優(yōu)解 X=(3,1) 最優(yōu)值 Z=5 (3,1) ???????????????006346321212121xxxxxxxx、min Z=x1+2x2 例 5 2 4 6 x1 x2 2 4 6 X（ 2） ＝（ 3,1） X（ 1） ＝（ 1,3） ???????????????006346321212121xxxxxxxx、min Z=5x1+5x2 例 有無窮多個(gè)最優(yōu)解 即具有多重解 ,通解為 0≤α≤1 當(dāng) α= Ｘ =(x1,x2)=(1,3)+(3,1)=(2,2) 6 2 4 6 x1 x2 2 4 6 ???????????????006346321212121xxxxxxxx、無界解 (無最優(yōu)解 ) max Z=x1+2x2 例 7 x1 x2 O 10 20 30 40 10 20 30 40 50 50 0,05040221212121????????xxxxxxxx無可行解 即無最優(yōu)解 max Z=10x1+4x2 例 8 由以上例題可知，線性規(guī)劃的解有 4種形式： (例 ) (例 ) (例 ) (例 ) 2情形為有最優(yōu)解 4情形為無最優(yōu)解 9 由圖解法得到的啟示 ? 線性規(guī)劃問題求解的基本依據(jù)是：線性規(guī)劃問題的最優(yōu)解總可在可行域的頂點(diǎn)中尋找。目標(biāo)函數(shù) Z=3x1+4x2中 x1的系數(shù)大于零，如果 x1為一正數(shù)，則 Z的值就會(huì)增大，同樣若 x2不為零為一正數(shù)，也能使 Z的值增大；因此只要目標(biāo)函數(shù)中非基變量的系數(shù)大于零，那么目標(biāo)函數(shù)就沒有達(dá)到最大值，即沒有找到最優(yōu)解，判別線性規(guī)劃問題是否達(dá)到最優(yōu)解的數(shù)稱為檢驗(yàn)數(shù)，記作 σ j , j=1,2…, n。建立新的單純形表，此時(shí)基變量中 xk取代了 xl ⑥以 aik為主元素進(jìn)行迭代，把 xk所對(duì)應(yīng)的列向量變?yōu)閱挝涣邢蛄?，即aik變?yōu)?1，同列中其它元素為 0，轉(zhuǎn)第③ 步。 使 x3進(jìn)基 x5出基繼續(xù)迭代 ,得到表 (4)的另一 基本最優(yōu)解 X(1),X(2)是線性規(guī)劃的兩個(gè)最優(yōu)解 ， 它的凸組合 20,),0,0,310,38,314)2( ?? ZX T（)10()1( )2()1( ????? ??? XXX 仍是最優(yōu)解 ， 從而原線性規(guī)劃 有多重最優(yōu)解 。故當(dāng)基變量為X B 時(shí)，新的單純形表就變?yōu)? 基變量 非基變量 BX NX SX XC BB I NB 1? B 1? bB 1? zc jj ? 0 NBCC BN 1?? BC B 1?? 40 單純形法計(jì)算的矩陣描述 從上面兩表可看出，當(dāng)?shù)?，基變量為X B，其在初始單純形表中的系數(shù)矩陣為 B ，則有： （ 1 ） 對(duì)應(yīng)初始單純形表中的單位陣 I ，迭代后的單純形表中為B 1?； （ 2 ） 初始基變量bX S ? ，迭代后的表中bBX B 1??； （ 3 ） 初始單純形表中，約束系數(shù)矩陣為? ? ? ?INBIA , ?，迭代后的表中約束系數(shù)矩陣為? ? ? ? ? ?BNBIIBNBBBIBAB 1111111 , ??????? ?? （ 4 ） 若初始矩 陣中變量x j的系數(shù)向量為P 39。 42 線性規(guī)劃求解的人工變量法 ? 人工變量法 引用人工變量是用單純形法求解線性規(guī)劃問題時(shí)解決可行解問題的常用方法。 線性規(guī)劃求解的大 M法 46 線性規(guī)劃求解的大 M法 max z = c 1 x 1 + c 2 x 2 + … + c n x n M ( x n + 1 + … + x n + m ) a 11 x 1 + a 12 x 2 + … + a 1n x n + x n + 1 = b 1 a 21 x 1 + a 22 x 2 + … + a 2n x n + x n + 2 = b 2 … … a m1 x 1 + a m2 x 2 + … + a mn x n + x n + m = b m x 1 , x 2 , … , x n , x n + 1 … , x n + m ≥ 0 47 【 例 】 用大 M法解 下列線性規(guī)劃 ???????????????????????012210243423m ax321321321321321xxxxxxxxxxxxxxxZ、線性規(guī)劃求解的大 M法舉例 48 【 解 】 首先將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式 ????????????????????????5,2,1,012210243423m ax32153214321321?jxxxxxxxxxxxxxxxZj式中 x4， x5為松弛變量 ， x5可作為一個(gè)基變量 ， 第一 、 三約束中分別加入人工變量 x x7， 目標(biāo)函數(shù)中加入 ―M x6―M x7一項(xiàng) ， 得到人工變量單純形法數(shù)學(xué)模型 用前面介紹的單純形法求解，見下表。 56 【 例 】 用兩階段單純形法求解例 【 】 的線性規(guī)劃 。 65 單純形法計(jì)算可能的循環(huán)現(xiàn)象 ?在求解線性規(guī)劃單純形方法的計(jì)算過程循環(huán)極少出現(xiàn)，但還是可能的