【正文】 ?判別方法： 無最優(yōu)解判別定理 在求解極大化的線性規(guī)劃問題過程中 ， 若某單純形表的檢驗(yàn) 行存在某個(gè)大于零的檢驗(yàn)數(shù) ， 但是該檢驗(yàn)數(shù)所對應(yīng)的非基變量 的系數(shù)列向量的全部系數(shù)都為負(fù)數(shù)或零 ， 則該線性規(guī)劃問題 無最優(yōu)解 ， 1 1B m + k m + kX = B b B P x 1B m + k m + kZ =C B b+ σxm +k 0? ?1 m + kB P 0? m + kx ? ? ?可以 Z ? ??可以 52 例 試用單純形法求解下列線性規(guī)劃問題： 解：引入松弛變量 x3,x4化為標(biāo)準(zhǔn)型 12121212m a x Z = 2 x + 2 x x x 11 x x 22x 0 ,x 0????????????121 2 31 2 4jm a xZ = 2x + 2x x x x 11 x x + x 22x 0, j 1, 2, 3, 4? ? ????????????C 2 2 0 0 θ C XB B x1 x2 x3 x4 0 X3 1 1 1 1 0 0 X4 2 1/2 1 0 1 Z 0 2 2 0 0 1= 20?因 但 所以原問題 無最優(yōu)解 11P = 012?????????53 ? 退化解 當(dāng)線性規(guī)劃問題的基本可行解中有一個(gè)或多個(gè)基變量取零值時(shí) ，稱此基本可行解為退化解 。 表明原問題已經(jīng)得了一個(gè)初始的基本可行解 ， 可轉(zhuǎn)入第二階段繼續(xù)計(jì)算；否則說明原問題沒有可行解 ， 可停止計(jì)算 。 但是我們可以從 X(0)出發(fā)進(jìn)行迭代 ， 一旦所有的人工變量都從基變量迭代出來 ， 變成只能取零值的非基變量 ， 那么我們實(shí)際上已經(jīng)求得了原線性規(guī)劃問題的一個(gè)初始的基本可行解 。 Xm X m+1 Xm+2 X = ( 0 , 0 , 4 , 0 , 3 ) T1N N B1 2 411122σ =C C B N =( 5,2, 1) (3,1)5 1322=( 5,2, 1) ( 4,6,1) =( 1, 4, 2) σ σ σ???????????????X = ( 0 , 0 , 4 , 0 , 3 ) T13BB N 25N411x1x C = ( 3 , 1 )1 0 422X = , X = x , B = , N = , , b =x C = ( 5 , 2 , 1 )0 1 5 1 33x22???????? ? ? ? ??????? ? ? ? ???? ? ? ? ? ??? ????????1 10? ??23 （ 3） 基本可行解 的改進(jìn) ① 選取換入變量 因?yàn)? ，取 為換入變量。 1B?1BX =B b?1BN?1Bb?NX =016 且改進(jìn)了的基本可行解 只是在Ｘ的基變量的基礎(chǔ)上用一個(gè)換入變量替代其中一個(gè)換出變量，其它的基變量仍然保持不變。 1 1BNX =B b B NX1BZ= C B b1N N B m + 1 m + 1 n=C C B N= ( , , )? ? ? ?BBNN 1 1B B N N B N N N 1 1B N B NXZ = CX = ( C C )X= C X + C X = C ( B b B N X ) + C X= C B b + ( C C B N ) X??????10 定理 1：最優(yōu)解判別定理 對于線性規(guī)劃問題 若某個(gè)基本可行解所對應(yīng)的檢驗(yàn)向量 ， 則這個(gè)基本可行解就是最優(yōu)解。 單純形法的一般步驟如下： （ 1） 尋找一個(gè)初始的基本可行解 。 基由系數(shù)矩陣Ａ中 m個(gè)線性無關(guān)的系數(shù)列向量構(gòu)成 。 1N N B=C C B N?m + 1m + 21B m + 1, m + 1, nnxxZ C B b+ ( σ σ σ )x?????????????12 換入變量和換出變量的確定 ： ?換入變量的確定 — 最大增加原則 假設(shè)檢驗(yàn)向量 ， 若其中有兩個(gè)以上的檢驗(yàn)數(shù)為正，那么為了使目標(biāo)函數(shù)值增加得快些，通常要用 “ 最大增加原則 ” ，即選取最大正檢驗(yàn)數(shù)所對應(yīng)的非基變量為換入變量，即若 則選取對應(yīng)的 為換入變量， 由于 且為最大， 因此當(dāng) 由零增至正值， 可使目標(biāo)函數(shù)值 最大限度的增加。X17 1 2 3 4 51 2 3 41 2 3 51 2 3 4 5m a xZ =5 x 2x 3x x xx 2x 2x x 83x 4x x x 7 x ,x ,x ,x ,x 0? ? ? ?? ? ? ???? ? ? ??? ??1 2 2 1 0A=3 4 1 0 1??????8b7???????C = ( 5 , 2 , 3 , 1 , 1 )?例 1 解： (１ )確定初始的基本可行解。 檢驗(yàn)向量 因?yàn)樗袡z驗(yàn)數(shù)均小于零， 所以 是最優(yōu)解， 1N N B2 4 52 3 15 5 5σ =C C B N =( 2, 1,1) (3,5)6 1 25 5 536 4 7 26 9 2=( 2, 1,1) ( , , ) =( , , )5 5 5 5 5 5 σ σ σ???????????????6 1 739。Z = Z = x + 2 x39。 以單位矩陣為初始基 ， 即可求得一個(gè)初始的基本可行解 。 ? ?X 0 , 3 , 1 , 2 , 0 T? ?48 ?單純形表與線性規(guī)劃問題的討論 ?無可行解 通過大Ｍ法或兩階段法求初始的基本可行解 。 54 例 求解下述線性規(guī)劃問題： 解： 引入松弛變量 化標(biāo)準(zhǔn)型 1 2 3 41 2 3 41 2 3 4 3jm a xZ =3x 80x +2x 24xx 32x 4x 36x 0x 24x x 6x 0 x 1 x 0,j 1,2,3, 4??????????? ??? 1 2 3 41 2 3 4 51 2 3 4 637jm a xZ = 3x 80 x + 2x 24 xx 32 x 4x 36 x x 0x 24 x x 6 x x 0 x x 1 x 0, j 1, 2, 3, 4, 5, 6, 7? ? ???? ? ??????? ???5 6 7x ,x ,x55 0 0 0 24 2 80 3 0 Z 5 6 0 42 0 8 0 5 Z 1 0 0 0 1 0 0 1 x3 2 1 2 0 6 0 24 1 1 x1 3 3 2 1 30 0 8 0 3 x5 0 0 3 0 42 5 8 0 0 Z 1 1 0 0 1 0 0 1 x7 0 0 1 0 6 1 24 1 0 x1 3 0 1 1 30 3 8 0 0 x5 0 1 1 0 0 1 0 0 1 x7 0 0 0 1 0 6 1 24 1 0 x6 0 0 0 0 1 36 4 32 1 0 x5 0 x7 x6 x5 x4 x3 x2 x1 b XB CB 0 0 0 24 2 80 3 C θ 第一次迭代中使用了攝動(dòng)法原理 ， 選擇下標(biāo)為 6的基變量 x6離基 。Z = Z故引入人工變量 ， 并利用大 M法求解 78x ,x1 2 31 2 3 41 3 52 3 639。 否則最優(yōu)解中剔除人工變量的剩余部分即為原問題的初始基本可行解 。 因?yàn)槿斯ぷ兞渴窃诩s束方程已為等式的基礎(chǔ)上 ， 人為的加上去的一個(gè)新變量 ， 因此 加入人工變量后的約束方程組與原約束方程組是不等價(jià)的 。 ? 每一個(gè)基本可行解所對應(yīng)的目標(biāo)函數(shù)值 通過目標(biāo)函數(shù)值可以觀察單純形法的每次迭代是否能使目標(biāo)函數(shù)值有效地增加 ， 直至求得最優(yōu)目標(biāo)函數(shù)為止 。 32P=1?????? 41P0???????50P=1?????? 11 1 1 0 41 2 2 1 0 8 223 4 1 0 1 73 4 1 0 1 7111 1 0 422 5 13 0 1 322??????????????????????????????????????? 39。 1BbX= 0???????1 m + kB P 0?m +k 0? ?證：令 ，則得新的可行解 將上式代入 因?yàn)? , 故當(dāng) λ→+∞ 時(shí)， Z→+∞ 。 ? 結(jié)論：在線性規(guī)劃標(biāo)準(zhǔn)化過程中設(shè)法得到一個(gè) m階單位矩陣 I作為初始可行基Ｂ ， 1BbX= 0??????? 1 1 1B N B N N BA X =b B X +N X =b X =B b B N X X =0,X =B b? ? ?7 ? 若在化標(biāo)準(zhǔn)形式前 ， 約束方程中有 “ ≥ ” 不等式 ， 那么在化標(biāo)準(zhǔn)形時(shí)除了在方程式左端減去剩余變量使不等式變 成等式以外 ， 還必須在左端再加上一個(gè)非負(fù)新變量 ， 稱為 人工變量 ． ? 若在化標(biāo)準(zhǔn)形式前 ， 約束方程中有等式方程 ， 那么可以直接在 等式左端添加人工變量 。1 第二章 單純形法 ? 單純形法的一般原理 ? 表格單純形法 ? 借助人工變量求初始的基本可行解 ? 單純形表與線性規(guī)劃問題的討論 ? 改進(jìn)單純形法 2 考慮到如下線性規(guī)劃問題 其中Ａ一個(gè) m n矩陣 ， 且秩為 m， ｂ總可以被調(diào)整為一個(gè) m維非負(fù)列向量 ， Ｃ為 n維行向量 ， Ｘ為 n維列向量 。 但是求逆陣Ｂ 1也是一件麻煩的事 。 xlBX14 定理 3：無最優(yōu)解判別定理 若 是一個(gè)基本可行解 ， 有一個(gè)檢驗(yàn)數(shù) ， 但是 ， 則該線性規(guī)劃問題無最優(yōu)解 。 ② 選取換出變量 且 ， 選取 x4為換出變量 . 8 7 8m i n ,2 1 2?? ?????X = ( 0 , 0 , 0 , 8 , 7 ) T11382B b= , B P 071??? ? ? ???? ? ? ?? ? ? ?14BB N 25N3xx C = ( 1 ,1 )1 0 1 2 2 8X = ,X = x ,B = ,N = , ,b =x C = ( 5 ,2 ,3 )0 1 3 4 1 7x???? ? ? ? ? ? ????? ? ? ? ? ? ???? ?