【正文】 , 故當(dāng) λ→+∞ 時(shí)， Z→+∞ 。 為保持解的可行性，可以按最小比值原則確定換出變量： 若 B 1 2 mX =( x , x , x ) T111im + k i 1 1m + k i m + k( B b)( B b)m in /(B P ) 0 ,1 i m =( B P ) ( B P )ll? ?? ????? ??m+kx 1 1 1 1B N B m + k m + kX = B b B N X X = B b B P x?m+kP m+kxm+kx則選取對(duì)應(yīng)的基變量 為換出變量。 現(xiàn)在需在 中確定一個(gè)基變量為換出變量。 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ù)所對(duì)應(yīng)的非基變量為換入變量，即若 則選取對(duì)應(yīng)的 為換入變量， 由于 且為最大， 因此當(dāng) 由零增至正值， 可使目標(biāo)函數(shù)值 最大限度的增加。 具體做法是： ?先從檢驗(yàn)數(shù)為正的非基變量中確定一個(gè)換入變量 ， 使它從非基變量變成基變量 （ 將它的值從零增至正值 ） ， ?再?gòu)脑瓉?lái)的基變量中確定一個(gè)換出變量 ， 使它從基變量變成非基變量 （ 將它的值從正值減至零 ） 。 定理 2：無(wú)窮多最優(yōu)解判別定理 若 是一個(gè)基本可行解，所對(duì)應(yīng)的檢驗(yàn)向量 ，其中存在一個(gè)檢驗(yàn)數(shù) σ m+k=0， 則線(xiàn)性規(guī)劃問(wèn)題有無(wú)窮多最優(yōu)解。若 σ N的每一個(gè)檢驗(yàn)數(shù)均小于等于 0，即 σ N≤0 ，那么現(xiàn)在的基本可行解就是最優(yōu)解。 8 ?判斷現(xiàn)行的基本可行解是否最優(yōu) 假如已求得一個(gè)基本可行解 將這一基本可行解代入目標(biāo)函數(shù)，可求得相應(yīng)的目標(biāo)函數(shù)值 其中 分別表示基變量和 非基變量所對(duì)應(yīng)的價(jià)值系數(shù)子向量。 ? 結(jié)論：在線(xiàn)性規(guī)劃標(biāo)準(zhǔn)化過(guò)程中設(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ù)新變量 ， 稱(chēng)為 人工變量 ． ? 若在化標(biāo)準(zhǔn)形式前 ， 約束方程中有等式方程 ， 那么可以直接在 等式左端添加人工變量 。 ?為了求得基本可行解 ， 必須求基Ｂ的逆陣Ｂ 1。 ?即使系數(shù)矩陣Ａ中找到了一個(gè)基 B， 也不能保證該基恰好是可行基 。 基由系數(shù)矩陣Ａ中 m個(gè)線(xiàn)性無(wú)關(guān)的系數(shù)列向量構(gòu)成 。 4 ? 確定初始的基本可行解 確定初始的基本可行解等價(jià)于確定初始的可行基，一旦初始的可行基確定了，那么對(duì)應(yīng)的初始基本可行解也就唯一確定 為了討論方便，不妨假設(shè)在標(biāo)準(zhǔn)型線(xiàn)性規(guī)劃中，系數(shù)矩陣Ａ中前 m個(gè)系數(shù)列向量恰好構(gòu)成一個(gè)可行基，即 Ａ =（ＢＮ），其中 Ｂ =（Ｐ 1， Ｐ 2， … Ｐ m）為基變量 x1， x2， … xm的系數(shù)列向量 構(gòu)成的可行基， Ｎ =(Ｐ m+1， Pm+2， … Pn)為非基變量 xm+1， xm+2， … xn的 系數(shù)列向量構(gòu)成的矩陣。 （ 2） 檢查現(xiàn)行的基本可行解是否最優(yōu) ， 如果為最優(yōu) ， 則停止迭代 ， 已找到最優(yōu)解 ， 否則轉(zhuǎn)一步 。 其基本思路是從一個(gè)初始的基本可行解出發(fā) ， 尋找一條達(dá)到 最優(yōu)基本可行解的最佳途徑 。 這個(gè)重要的定理啟發(fā)了 Dantzig的單純形法 ， 即將尋優(yōu)的目標(biāo)集中在 D的各個(gè)頂點(diǎn)上 。1 第二章 單純形法 ? 單純形法的一般原理 ? 表格單純形法 ? 借助人工變量求初始的基本可行解 ? 單純形表與線(xiàn)性規(guī)劃問(wèn)題的討論 ? 改進(jìn)單純形法 2 考慮到如下線(xiàn)性規(guī)劃問(wèn)題 其中Ａ一個(gè) m n矩陣 ， 且秩為 m， ｂ總可以被調(diào)整為一個(gè) m維非負(fù)列向量 ， Ｃ為 n維行向量 ， Ｘ為 n維列向量 。 根據(jù)線(xiàn)性規(guī)劃基本定理： 如果可行域Ｄ ={ Ｘ ∈ Ｒ n / ＡＸ =ｂ ， Ｘ ≥ 0}非空有界 ， 則Ｄ上的最優(yōu)目標(biāo)函數(shù)值Ｚ =ＣＸ一定可以在Ｄ的一個(gè)頂點(diǎn)上達(dá)到 。 m a x Z = CXA X = bX0?????單純形法的一般原理 3 Dantzig的單純形法把尋優(yōu)的目標(biāo)集中在所有基本可行解 （ 即可行域頂點(diǎn) ） 中 。 單純形法的一般步驟如下： （ 1） 尋找一個(gè)初始的基本可行解 。 （ 3） 移至目標(biāo)函數(shù)值有所改善的另一個(gè)基本可行解 ， 然后轉(zhuǎn)會(huì)到步驟 （ 2） 。 5 所以約束方程 就可以表示為 BBNNXA X = ( B N ) = B X + N X = bX?????? 用可行基Ｂ的逆陣Ｂ 1左乘等式兩端，再通過(guò)移項(xiàng)可推得： 若令所有非基變量 , 則基變量 由此可得初始的基本可行解 1BbX=0???????AX=b 1 1BNX =B b B NX1BX =B bNX =06 ? 問(wèn)題： ?要判斷 m個(gè)系數(shù)列向量是否恰好構(gòu)成一個(gè)基并不是一件容易的事 。 但是要判斷 m個(gè)系數(shù)列向量是否線(xiàn)性無(wú)關(guān)并非易事 。 因?yàn)椴荒鼙ＷC基變量Ｘ B=Ｂ 1b≥ 0。 但是求逆陣Ｂ 1也是一件麻煩的事 。 為了設(shè)法得到一個(gè) m階單位矩陣 I作為初始可行基Ｂ，可在性規(guī) 劃標(biāo)準(zhǔn)化過(guò)程中作如下處理： ? 若在化標(biāo)準(zhǔn)形式前， m個(gè)約束方程都是 “ ≤ ” 的形式， 那么在化標(biāo)準(zhǔn)形時(shí)只需在一個(gè)約束不等式左端都加上一個(gè)松弛變 量 xn+i (i=12… m)。 1BbX= 0???????11B N BBbZ = C X = ( C C ) = C B b0???????B 1 2 m N m + 1 m + 2 nC = ( c , c , c ) , C = ( c , c , c )9 要判定 是否已經(jīng)達(dá)到最大值，只需將 代入目標(biāo)函數(shù)，使目標(biāo)函數(shù)用非 基變量 表示，即： m + 1m + 2 1 1B N N B m + 1, m + 1, nnxxC B b + σ X C B b + (σ σ σ )x????????????? 其中 稱(chēng)為非基變量Ｘ N的檢驗(yàn)向量，它的各個(gè)分量稱(chēng)為檢驗(yàn)數(shù)。 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)解判別定理 對(duì)于線(xiàn)性規(guī)劃問(wèn)題 若某個(gè)基本可行解所對(duì)應(yīng)的檢驗(yàn)向量 ， 則這個(gè)基本可行解就是最優(yōu)解。 ? ?nm a x Z = C X , D = X R /A X = b ,X 0??1N N B=C C B N 0? ?1BbX= 0???????1N N B=C C B N 0? ?m + 1m + 21B m + 1, m + 1, nnxxZ C B b+ ( σ σ σ )x?????????????11 ? 基本可行解的改進(jìn) 如果現(xiàn)行的基本可行解Ｘ不是最優(yōu)解 ， 即在檢驗(yàn)向量 中存在正的檢驗(yàn)數(shù) ， 則需在原基本可行解Ｘ的基礎(chǔ)上尋找一個(gè)新的基本可行解 ， 并使目標(biāo)函數(shù)值有所改善 。 由此可得一個(gè)新的基本可行解 ， 由 可知 ， 這樣的變換一定能使目標(biāo)函數(shù)值有所增加 。 1N N B m + 1 m + 2 n=C C B N =( , , )? ? ? ?? ?j j m + km a x σ /σ 0 ,m + 1 j n = σ??m+kxm+kxm+k 0? ?m + 1m + 21B m + 1, m + 1, nnxxZ C B b+ ( σ σ σ )x?????????????13 ? 換出變量的確定 — 最小比值原則 如果確定 為換入變量，方程 其中 為Ａ中與 對(duì)應(yīng)的系數(shù)列向量。 當(dāng) 由零慢慢增加到某個(gè)值時(shí)， 的非負(fù)性可能被打破。 xlBX14 定理 3：無(wú)最優(yōu)解判別定理 若 是一個(gè)基本可行解 ， 有一個(gè)檢驗(yàn)數(shù) ， 但是 ， 則該線(xiàn)性規(guī)劃問(wèn)題無(wú)最優(yōu)解 。 1 1 1 1B m + k m + k m + kX = B b B P x B b B P ?? m + 1 1 1B m + 1 m + k n B m + knxZ =C B b+( σ , σ , σ ) C B b+σx?????????? ?????????m + kx , ( 0 )????m+k 0? ?15 ? 用初等變換求改進(jìn)了的基本可行解 假設(shè)Ｂ是線(xiàn)性規(guī)劃 的可行基 ， 則 令非基變量 ，則基變量 。 1BbX= 0???????BNXA X = b ( B N ) bX??? ? ?????m a x Z = C X , A X = b , X 0?B 1 1NX( I , B N ) = B bX??????? 用逆陣 左乘約束方程組的兩端，等價(jià)于對(duì)方程組施以一系列的初等 “ 行變換 ” 。 1B?1BX =B b?1BN?1Bb?NX =016 且改進(jìn)了的基本可行解 只是在Ｘ的基變量的基礎(chǔ)上用一個(gè)換入變量替代其中一個(gè)換出變量，其它的基變量仍然保持不變。為了求得改進(jìn)的基本可行解 ，只需對(duì)增廣矩陣 施行初等行變換，將換入變量的系數(shù)列向量變換成換出變量所對(duì)應(yīng)的單位向量即可。X 1 1( I , B N , B b )BNX( B , N ) = bX??????39。 ，基變量 ，非基變量 。 檢驗(yàn)向量 因?yàn)?σ 1=3， σ 3=4 均大于零， 所以 不是最優(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???? ? ? ? ? ? ????? ? ? ? ? ? ???? ? ? ? ? ??? ????N 1 2 3=