【正文】 65 單純形法計(jì)算可能的循環(huán)現(xiàn)象 ?在求解線性規(guī)劃單純形方法的計(jì)算過(guò)程循環(huán)極少出現(xiàn)，但還是可能的。 線性規(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é)模型 用前面介紹的單純形法求解，見(jiàn)下表。故當(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。建立新的單純形表，此時(shí)基變量中 xk取代了 xl ⑥以 aik為主元素進(jìn)行迭代，把 xk所對(duì)應(yīng)的列向量變?yōu)閱挝涣邢蛄?，即aik變?yōu)?1，同列中其它元素為 0，轉(zhuǎn)第③ 步。 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 例 有無(wú)窮多個(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、無(wú)界解 (無(wú)最優(yōu)解 ) max Z=x1+2x2 例 7 x1 x2 O 10 20 30 40 10 20 30 40 50 50 0,05040221212121????????xxxxxxxx無(wú)可行解 即無(wú)最優(yōu)解 max Z=10x1+4x2 例 8 由以上例題可知，線性規(guī)劃的解有 4種形式： (例 ) (例 ) (例 ) (例 ) 2情形為有最優(yōu)解 4情形為無(wú)最優(yōu)解 9 由圖解法得到的啟示 ? 線性規(guī)劃問(wèn)題求解的基本依據(jù)是：線性規(guī)劃問(wèn)題的最優(yōu)解總可在可行域的頂點(diǎn)中尋找。 本例中 σ 1=3, σ 2=4, σ 3=0, σ 4=0。 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)解。 ? 人工變量法的基本思路是： 若原線性規(guī)劃問(wèn)題的系數(shù)矩陣中沒(méi)有單位向量，則在每個(gè)約束方程中加入一個(gè)人工變量便可在系數(shù)矩陣中形成一個(gè)單位向量。 ???????????????????????012210243423m ax321321321321321xxxxxxxxxxxxxxxZ、57 【 解 】 標(biāo)準(zhǔn)型為 ????????????????????????5,2,1,012210243423m ax32153214321321?jxxxxxxxxxxxxxxxZj在第一 、 三約束方程中加入人工變量 x x7后 ， 第一階段問(wèn)題為 ?????????????????????????7,2,1,0122102434m i n732153216432176?jxxxxxxxxxxxxxxxxwj用單純形法求解，得到第一階段問(wèn)題的計(jì)算表如下： 58 Cj 0 0 0 0 0 1 1 b CB XB x1 x2 x3 x4 x5 x6 x7 1 0 1 x6 x5 x7 － 4 1 2 3 － 1 － 2 1 2 [1] － 1 0 0 0 1 0 1 0 0 0 0 1 4 10 1→ λj 2 － 1 － 2↑ 1 0 0 0 1 0 0 x6 x5 x3 － 6 － 3 2 [5] 3 － 2 0 0 1 － 1 0 0 0 1 0 1 0 0 3→ 8 1 λj 6 － 5↑ 0 1 0 0 0 0 0 x2 x5 x3 － 6/5 3/5 － 2/5 1 0 0 0 0 1 － 1/5 3/5 － 2/5 0 1 0 3/5 31/5 11/5 λj 0 0 0 0 0 59 最優(yōu)解為 最優(yōu)值 w=0。 。 第二階段 ，單純形法求解原問(wèn)題 第一階段計(jì)算得到的最終單純形表中除去人工變量，將目標(biāo)函數(shù)行的系數(shù)，換成原問(wèn)題的目標(biāo)函數(shù)后，作為第二階段計(jì)算的初始表，繼續(xù)求解。 （ 5 ） 計(jì)算新的基矩陣的逆矩陣11?B ，求出bB 11? ，重復(fù)（ 2 ）至（ 5 ）。