【正文】 σ j 基變量 1 10 0 0 1/3 0 1/3 10 5/3 1 1/3 40 5/3 0 4/3 30 1 0 3/5 1/5 18 0 1 1/5 2/5 4 0 0 1 1 將 3化為 1 乘以1/3后得到 30 18 17 最優(yōu)解 X=(18， 4， 0， 0)T，最優(yōu)值 Z=70 O 20 30 10 40 (3,4) X(3)=(18,4) 最優(yōu)解 X=(18,4) 最優(yōu)值 Z=70 402 21 ?? xx 21 ?? xx??????????????0,30340243m a x432142132121xxxxxxxxxxxxZX(1)=(0,0) 20 10 x2 x1 30 0,0402212121??????xxxxxxX(2)=(0,10) 18 單純形表 c j c 1 c 2 … c m c m +1 … c m + k … c n c B X B x 1 x 2 … x m x m +1 … x m + k … x n b θ i c 1 c 2 ? c m x 1 x 2 ? x m 1 0 ? 0 0 1 ? 0 … … … … 0 0 ? 1 a 1 , m +1 a 2 , m +1 ? a m , m +1 … … … a 1 , m + k a 2 , m + k ? a m , m + k … … ?… a 1n a 2n ? a mn b 1 b 2 ? b m θ 1 θ 2 ? θ m ????miijijj acc1? 0 0 … 0 σm +1 … σ m + k … σ n ???miii bcz1 單純形法全過程的計(jì)算 ， 可以用列表的方法計(jì)算更為簡潔 ， 這種表格稱為單純形表 。建立新的單純形表，此時(shí)基變量中 xk取代了 xl ⑥以 aik為主元素進(jìn)行迭代，把 xk所對(duì)應(yīng)的列向量變?yōu)閱挝涣邢蛄?，即aik變?yōu)?1，同列中其它元素為 0，轉(zhuǎn)第③ 步。目標(biāo)函數(shù)中含有基變量 x4,由第二個(gè)約束得到 x4=6+x1－ x2，并代入目標(biāo)函數(shù)消去 x4得 1 2 1 2 1 22 2 ( 6 ) 6Z x x x x x x? ? ? ? ? ? ? ?＝26 XB x1 x2 x3 x4 x5 b θ x3 x4 x5 1 1 6 [1] 1 2 1 0 0 0 1 0 0 0 1 5→ 6 21 5 6 21/2 λj 1 1↑ 0 0 0 x2 x4 x5 1 2 4 1 0 0 1 1 2 0 1 0 0 0 1 5 1 11 λj 2 0 1 0 0 表中 λj≥0,j=1,2,… ,5所以最優(yōu)解為 X=(0,5,0,1,11,)最優(yōu)值 Z=2x1－ 2x2－ x4=－ 2 5－ 1=－ 11 極小值問題 ,注意判斷標(biāo)準(zhǔn) ,選進(jìn)基變量時(shí) ,應(yīng)選 λj0的變量 xj進(jì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)解 。 34 唯一最優(yōu)解的判斷： 最優(yōu)表中所有非基變量的檢驗(yàn)數(shù) 非零 ,則線規(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。求出初始解： ??????????????01bBXXNB （ 2 ） 計(jì)算非基變量NX的檢驗(yàn)數(shù)N? ， NBCC BNN 1???? ，若0?N?已得到最優(yōu)解，停止計(jì)算，若還存在Njj ?? ,0? ，轉(zhuǎn)入下一步。 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é)模型 用前面介紹的單純形法求解，見下表。 54 線性規(guī)劃求解的兩階段法 兩階段法的基本思路是： 第一階段 ，首先不考慮原問題是否存在基可行解 ， 先求解一個(gè)目標(biāo)函數(shù)中只包含人工變量的線性規(guī)劃問題，即令目標(biāo)函數(shù)中其他變量的系數(shù)取零，人工變量的系數(shù)取某個(gè)正的常數(shù) ( 一般取 1) ，在保持原問題約束條件不變的情況下求這個(gè)目標(biāo)函數(shù)極小化時(shí)的解。 56 【 例 】 用兩階段單純形法求解例 【 】 的線性規(guī)劃 。 64 解的判斷 唯一最優(yōu)解的判斷： 最優(yōu)表中所有非基變量的檢驗(yàn)數(shù)小于零 ,則線 規(guī)劃具有唯一最優(yōu)解 多重最優(yōu)解的判斷 :最優(yōu)表中存在非基變量的檢驗(yàn)數(shù)為零 ,則線則性規(guī)劃具有多重最優(yōu)解。 65 單純形法計(jì)算可能的循環(huán)現(xiàn)象 ?在求解線性規(guī)劃單純形方法的計(jì)算過程循環(huán)極少出現(xiàn)，但還是可能的。 67 復(fù)習(xí)舉例 有兩個(gè)變量的線性規(guī)劃問題 ?????????????0,1m ax2121211xxxxaxxxz （ 1 ） 證明本題當(dāng)且僅當(dāng)1?a 時(shí)為可行