【正文】 當(dāng) x2=6時， x4=0，所以 x4為換出變量。由此得到線性規(guī)劃（ 1）的一個新的基 B2和 一組新的基變量與非基變量。 B2=(P1 ,P2 ,P5 ), XB2=（ x1， x2， x5)T， XN2=（ x3， x4)T 51 求另一個更好的 基礎(chǔ) 可行解 將 （ 1)約束方程中對應(yīng)于基 B2的非基變量 x3和 x4移到方程的右邊后可得 ?????????????7810252421321xxxxxxxx(8) 21262435432431??????????????xxxxxxxx令非基變量 x3=x4=0，可得 另 一 基礎(chǔ) 可行解 X(2) = (2， 6， 0， 0， 1)T 此時，對應(yīng)于 X(2)的目標(biāo)函數(shù) f (X(2) )=6x1+4x2=36 f (X(1) )=30 （ 七 ）最優(yōu)檢驗 將（ 8）式代入 (1)的目標(biāo)函數(shù)后可得 f (X)=362x32x4 （ 9） 從目標(biāo)函數(shù)（ 9）可 知 ，非基變量 x3和 x4的系數(shù)都是 負(fù) 數(shù)， 所以X(2)是最優(yōu)解。即 X*= X(2) = (2， 6， 0， 0， 1)T ,f (X*)=36 三、求初始基礎(chǔ)可行解（背景模型， MAX, ≤) 52 設(shè)線性規(guī)劃問題為 ,2,1 ,0,2,1 ,..)(max11??????????????njxmibxatsxcxfjinjjijnjjj????????????????????? ,2,1 ,0,2,1 ,)(max 11mnjxmibxaxxcxfjimnmjjijimnjjj??另設(shè) bi?0 (i=1,2,…,m) 。標(biāo)準(zhǔn)化后，若對 xj和 aij重新編號，則約束方程可化為 變量 x1， x2， … ， xm作為初始基變量，其余變量作為初始非基變量 ，并 令 xm+1=xm+1=…=x n+m=0， 則得 初始本可行解 ),0,0,...,0b..., ,b ,(b Tm21( 0) ?X四、最優(yōu)檢驗 53 對于標(biāo)準(zhǔn)化線性規(guī)劃問題 (2)，經(jīng)過若干次迭代后，如果對 xj及aij重新編號，則約束方程可化為 ,2,1 139。39。 mixabxmnmjjijii ???? ????其中， b’i和 a’ij表示經(jīng)過若干次迭代后，當(dāng)前的右端系數(shù)和技術(shù)系數(shù)，以便區(qū)別于原始的右端系數(shù) bi和技術(shù)系數(shù) aij。將 上 式代入 （ 2）的 目標(biāo)函數(shù)后可得 ??? ??? ?????????????????????????mnmjjjjjmiijimimnmjjiimnmjjjmimnmjjijiixzczxaccbcxcxabcxf10139。1 139。11 139。39。)( )( ) ()( 139。0 ???miiibcz 139。??miijij acz機會成本 54 在一般情況下，目標(biāo)函數(shù)值 OBJ計算公式和機會成本計算公式可寫成 四、最優(yōu)檢驗 ,139。0 ?????Ii mkkibczOBJ ,139。0 ?????Iimkki bczOBJ ,139。???Iimkkjij acz Jj 0,139。 ?????? ???Iimkkjijjjj acczc?其中， I為基變量的下標(biāo)集。 最優(yōu)檢驗條件為 其中， J表示非基變量的下標(biāo)集。 對于 基變量 的 檢驗數(shù)為 0,139。 ??????? ???iiIjmkkijiiii ccacczc?因為 基變量的技術(shù)系數(shù)滿足： aij=1, 當(dāng) i=j aij=0, 當(dāng) i?j 五、 求另一個更好的 基礎(chǔ) 可行解 55 若某一 基礎(chǔ) 可行解經(jīng)過最優(yōu)檢驗表明不是最優(yōu)解，則需要設(shè)法求得另一個更好的 基礎(chǔ) 可行解。求另一個更好的 基礎(chǔ) 可行解的主要步驟如下： 確定換入變量； 確定換出變量； 通過基變換或初等變換求得另一個更好的 基礎(chǔ)可行解。 我們已在前面例子中說明了這種初等變換方法的 基礎(chǔ) 思路。下一小節(jié)我們將用單純形表進一步說明這種初等變換方法。 56 單純形法表及單純形法 I V I I I I I Ix1x2… xnxn+ 1xn+ 2… xn + mCBXBb c1c2… cncn+ 1cn+ 2… cn + mc1 ?= cn+ 1xn+ 1b1a11a12… a1 n1 0 … 0c2 ?= cn+ 2xn+ 2b2a21a22… a2 n0 1 … 0? ? ? ? ? ? ? ? ? ? ?cm ?= cn + mxn + mbmam 1am 2… amn0 0 … 1O B Jz1z2… znzn+ 1zn+ 2… zn + mc1 z1c2 z2… cnzncn+ 1zn+ 1cn+ 2zn+ 2… cn + mzn + m57 例 試列出下面線性規(guī)劃問題的初始單純型表 ???????????????0,12023310032..244540)(max321321321321xxxxxxxxxtsxxxxfx1x2x3x4x5CBXBb 40 45 24 0 00 x 4 1 0 0 2 3 1 1 00 x 5 1 2 0 3 3 2 0 1 O B J = 0 zj? 0 0 0 0 0 cj zj? 40 45 24 0 0單純形法 步驟 58 求初始 基礎(chǔ) 可行解 將線性規(guī)劃模型標(biāo)準(zhǔn)化，建立初始單純形表，求初始 基礎(chǔ) 可行解。 最優(yōu)檢驗：對任一基礎(chǔ)可行解 X，若其所有檢驗數(shù) ?j =cj? zj?0， j?J 則 X為最優(yōu)解，即 X*=X，計算最優(yōu)解所對應(yīng)的最優(yōu)目標(biāo)函數(shù)值f(X*)，算法停止。否則轉(zhuǎn) 3。 求另一個更好的 基礎(chǔ) 可行解 1） 確定入變量 xk 若 }0{ ?? ? jJjk Max ??則 xk為換入變量； 2） 確定換出變量 xl* 計算 39。39。39。39。39。,1}0|{lklikikimil abaabMin ?????若 ?l為空集，則為無界解，算法停止。否則與右端系數(shù) b’l 同一行的基變量 xl*為換出變量。轉(zhuǎn) 3） 3）初等變換，得到另一個更好的 基礎(chǔ) 可行解 將入變量 xk所在列 k，出變量 xl*所在行 l的主元技術(shù)系數(shù) a’l k變換為 1，主元 a’l k 所在列的其余元變換為 0。更換基變量（用入變量 xk替換出變量 xl*）及其價值系數(shù)，得到另一個更好的 基礎(chǔ) 可行解。轉(zhuǎn) 2。