【正文】 ,1 ??????再令 01njjjmz z x????? ?稱為檢驗數 。 最優(yōu)解的判別定理 ? 定理 3 有 無界解的判別定理 若? ? T( 0 ) 12 , , , , 0 , , 0mX b b b? ? ??為對應于基 B 的一個基可行解，存在某個非基變量對應的檢驗數 ? m + k 0, 并且對應的變量系數,i m ka ??≤ 0 ， i = 1,2, , … , m , 則該線性規(guī)劃問題有無界解（或無有界最優(yōu)解）。 ? 我們希望：每變換一次，就得到一個新的基可行解，并且是盡可能使目標函數值改進的基可行解。 lx尋找改進的基可行解 ? 可以證明 ( x1, x2,…, xl1, xl+1, …, xm, xm+k)所對應的 m個列向量 P1, P2,…, Pl1, Pl+1, …, Pm, Pm+k線性無關，因而B=(P1, P2,…, Pl1, Pl+1, …, Pm, Pm+k)是一個新基。建立新的單純形表，此時基變量中 xk取代了 xl ⑥以 aik為主元素進行迭代，把 xk所對應的列向量變?yōu)閱挝涣邢蛄?，即aik變?yōu)?1，同列中其它元素為 0，轉第③ 步。 j，迭代后為P j ，則有P jBP 39。 （ 3 ） 根據? ? kjjj??? ?? 0|m a x ，所對應的非基變量kX 為換入變量，計算kPB1? ，若01 ?? kPB 那問題無解，停止計算，否則進行下一步。 ? 人工變量法的基本思路是： 若原線性規(guī)劃問題的系數矩陣中沒有單位向量，則在每個約束方程中加入一個人工變量便可在系數矩陣中形成一個單位向量。 線性規(guī)劃求解的人工變量法 對于如下線性規(guī)劃問題 m a x z =c1 x1+ c2 x2+ …+ cn xn a11 x1+ a12 x2+ …+ a1nxn = b1 a21 x1+ a22 x2+ …+ a2nxn = b2 … … am1 x1+ am2 x2+ …+ amnxn = bm x1, x2,…, xn ≥ 0 線性規(guī)劃求解的人工變量法 分別對每個約束方程中加入一個人工變量 x n + 1 … , x n + m 得到 m a x z = c 1 x 1 + c 2 x 2 + … + c n x n 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 ?為了使加入人工變量后線性規(guī)劃問題的最優(yōu)目標函數值不受影響，我們賦予人工變量一個很大的負價值系數 M (M為任意大的正數 )。也就是，給原問題加入人工變量，構造僅含人工變量的目標函數，并要求最小化。 第一階段的線性規(guī)劃問題可寫為： m i n w = x6+ x7 x1+ x2+ x3+ x4 = 4 2 x1+ x2 x3 x5+ x6=1 3 x2+ x3 + x7= 9 x1, x2, x3, x4, x5, x6, x7≥ 0 線性規(guī)劃求解兩階段法舉例 cj 0 0 0 0 0 1 1 CB XB x1 x2 x3 x4 x5 x6 x7 b θi 0 x4 1 1 1 1 0 0 0 4 4 1 x6 – 2 [ 1] – 1 0 – 1 1 0 1 1 1 x7 0 3 1 0 0 0 1 9 3 ?j – 2 4 0 0 – 1 0 0 0 x4 3 0 2 1 1 – 1 0 3 1 0 x2 – 2 1 – 1 0 – 1 1 0 1 –– 1 x7 [ 6] 0 4 0 3 – 3 1 6 1 ?j 6 0 4 0 3 – 4 0 0 x4 0 0 0 1 – 1/ 2 1/ 2 – 1/ 2 0 0 x2 0 1 1/ 3 0 0 0 1/ 3 3 0 x1 1 0 2/ 3 0 1/ 2 – 1/ 2 1/ 6 1 ?j 0 0 0 0 0 – 1 – 1 w =0 線性規(guī)劃求解兩階段法舉例 第二階段：在單純表中除去人工變量，變換目標函數，繼續(xù)求解。T*)0,1,0,1,0,0,43(?X，45*?Z。 勃蘭特 (Bland)法 1974 年由勃蘭特 ( B l a n d ) 提出了一個避免出現循環(huán)現象的簡便規(guī)則： （ 1 ）選取0?σ j 中下標最小的非基變量x k為換入變量，即取m in( | 0)jkj ???； （ 2 ）按? 規(guī)則計算時，若出現兩個和兩個以上的最小比值時，選取下標最小的基變量為換出變量。由于相鄰兩次迭代的差異在于：lx的換出與kx的換入。 線性規(guī)劃單純形法的改進舉例 第一步迭代，計算 ?? 210. PB??????????402， 112014?????????????， E1=?????????? ?41000102101，10111?? ? BEB=1 0 1 20 1 00 0 1 4??????????? 非基變量檢驗數 ? ? ? ? ? ?1 1 11111 0 1 2 1 02 , 0 0 , 0 , 3 0 1 0 4 0 2 , 3 40 0 1 4 0 1N N BBNCC?????? ? ? ?? ? ? ?? ? ? ?? ? ? ?? ? ? ?? ? ? ? 對應的換入變量為1x，計算 111() 2 1 6m in ( ) 0 m in , , 214()ikik iBbBPBP???????? ??? ? ? ??? ???????? 對應的換出變量為3x，由此得到新的基? ?2 1 4 2,B P P P?，? ?2 1 4 2,B x x xX ?，? ?2 2 , 0 , 3BC ?， ? ?2 0 , 0NC ?。 復習舉例 已知某線性規(guī)劃問題用單純形法計算得到的初始單純形表及最終單純形表的部分，請將表中空白處數字填上： cj→ 2 1 1 0 0 0 C XB b x1 x2 x3 x4 x5 x6 0 x4 60 0 x5 10 0 x6 20 3 1 1 1 2 1 1 cj zj ? … ? ? 0 x4 2 x1 1 x2 1 1 2 0 1/2 1/2 0 1/2 1/2 cj zj