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