【正文】 ? ?4 1 13 3 35x 82= B b B P x = xx 71?? ? ? ? ??? ? ? ? ?? ? ? ???20 （ 4） 求改進(jìn)了的基本可行解 對(duì)約束方程組的增廣矩陣施以初等行變換 ， 使換入變量 x3所對(duì)應(yīng)的系數(shù)列向量 變換成換出變量 x4所對(duì)應(yīng)的單位向量 , 注意保持基變量 x5的系數(shù)列向量 為單位向量不變 。X14BB 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???? ? ? ? ? ? ????? ? ? ? ? ? ???? ? ? ? ? ??? ????第一行除以２ 第二行減去第一行 21 —————————————————————————— 可得改進(jìn)的基本可行解 。 基本可行解 目標(biāo)函數(shù)值 易見目標(biāo)函數(shù)值比原來的 Z=1增加了， 再轉(zhuǎn)向步驟 (2) 3510B = ( P P ) =01??????13BB N 25N411x1x C = ( 3 ,1 )1 0 422X = ,X = x ,B = ,N = , ,b =x C = ( 5 ,2 , 1 )0 1 5 1 33x22???????? ? ? ? ??????? ? ? ? ???? ? ? ? ? ??? ????????1NB4X = 0 X = B b =3? ???? ????X=(0 ,0 ,4 , 0 , 3 ) T1B4Z = C B b = ( 3 , 1 ) 1 53? ?? ?????C =(5 ,2 , 3 , 1 , 1 )?C =(5 ,2 , 3 , 1 , 1 )?111 1 0 41 2 2 1 0 8 22 53 4 1 0 1 7 13 0 1 322???? ?????????35x x 1 2 4x ,x , x22 （ 2） 檢驗(yàn) 是否最優(yōu)。 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)? ，取 為換入變量。39。 ， 基變量 ， 非基變量 基本可行解 目標(biāo)函數(shù)值 比 Z=15增加了，再轉(zhuǎn)向步驟 (2) 3110B = ( P P ) =01??????2B3B N 4N152 3 1 1 7xC = ( 3 ,5 )x 10 5 5 5 5X = ,X = x ,B = ,N = , ,b =C = ( 2 , 1 ,1 )x 0 1 6 1 2 6x5 5 5 5? ? ? ???? ? ? ??? ????? ? ? ??? ????? ? ? ????? ??? ? ? ???? ? ? ?1NB175X = 0 X = B b=65??????? ????????6 1 7X = ( ,0 , , 0 , 0 )55T1B17815Z = C B b = ( 3 ,5 )6 55??????????????C =(5 ,2 , 3 , 1 , 1 )?C =(5 ,2 , 3 , 1 , 1 )?31x ,x 2 4 5x ,x , x3 172 111 011 1 0 45 5 5 522 5 661 1 23 0 1 3 1022 5 5 5 5???????? ??? ??26 （ 2） 檢驗(yàn) 是否最優(yōu)。39。39。 如果不是最優(yōu)又可以通過檢驗(yàn)向量確定合適的換入變量 。 ?在單純形法求解過程中 ， 每一個(gè)基本可行解Ｘ都以 某個(gè)經(jīng)過初等行變換的 約束方程組中的單位矩陣 Ι 為可行基 。 Xm X m+1 Xm+2 1213241 2 5jm inZ = x 2xx x 4x x 3x 2x x 8x 0 j 1,2 ,3,4 ,5????????? ? ??? ???，1239。1 2 1 2m inZ = x 2x m a x x + 2xZ??33 0 1 0 1 0 3 x2 2 0 0 1 2 1 2 x3 0 0 1 0 1 0 3 x2 2 4/1 1 0 1 0 0 4 x3 0 3/1 0 1 0 1 0 3 x4 0 _ 1 0 1 0 0 4 x3 0 0 0 0 0 1 8 Z’ 1 0 0 2 1 2 x1 1 1 0 0 2 0 6 Z’ 2/1 1 0 0 2 1 2 x5 0 1 2 0 0 0 0 Z’ 8/2 1 2 0 0 1 8 x5 0 x1 x2 x3 x4 x5 b XB CB Θ 1 2 0 0 0 C 最優(yōu)解 最優(yōu)值 ? ?X 2 , 3 , 2 , 0 , 0 T? ? 39。 事實(shí)上若以 x4為換入變量 ， 以 x3為換出變量 ， 再進(jìn)行一次迭代 ， 可得一下單純形表： 最優(yōu)解 最優(yōu)值 最優(yōu)解的一般表示式 39。 N N Bσ = C C N 0?? ?j j m + km in σ /σ 0 ,m + 1 j n = σ??36 ?借助人工變量求初始的基本可行解 若約束方程組含有 “ ≥ ” 不等式 ， 那么在化標(biāo)準(zhǔn)形時(shí)除了在方程式左端減去剩余變量 ， 還必須在左端加上一個(gè)非負(fù)的人工變量 。 加上人工變量以后 ， 線性規(guī)劃的基本可行解不一定是原線性規(guī)劃的問題的基本可行解 。 因?yàn)榇藭r(shí)只需去掉基本可行解中的人工變量部分 ， 剩余部分即為原線性規(guī)劃的一個(gè)基本可行解 ． 而這正是我們引入人工變量的主要目的 。 但是我們可以從 X(0)出發(fā)進(jìn)行迭代 ， 一旦所有的人工變量都從基變量迭代出來 ， 變成只能取零值的非基變量 ， 那么我們實(shí)際上已經(jīng)求得了原線性規(guī)劃問題的一個(gè)初始的基本可行解 。 n +ix (i= 1 ,2 , m )( 0) 1 2 mX =( 0,0, ,0,b ,b , b ) Tni j j ij= 1j a x =b ,i=1,2,...,m x 0,j=1,2,....,n?? ??? ???ni j j n+ i ij= 1j a x + x = b , i= 1 ,2 ,. .. ,m x 0 ,j= 1 ,2 ,. .. ., n + m???? ???39 ? 大 M法 大 M法首先將線性規(guī)劃問題化為標(biāo)準(zhǔn)型 。 否則在約束方程組的左邊加上若干個(gè)非負(fù)的人工變量 ， 使人工變量對(duì)應(yīng)的系數(shù)列向量與其它變量的系數(shù)列向量共同構(gòu)成一個(gè)單位矩陣 。 為了求得原問題的初始基本可行解 ， 必須盡快通過迭代過程把人工變量從基變量中替換出來成為非基變量 。 這樣只要基變量中還存在人工變量 ， 目標(biāo)函數(shù)就不可能實(shí)現(xiàn)極大化 。 假如在單純形最優(yōu)表的基變量中還包含人工變量 ， 則說明原問題無可行解 。 40 例 用大 M法求解下面的線性規(guī)劃問題 : 解： 首先將原問題化為標(biāo)準(zhǔn)型 添加人工變量 ， 并在目標(biāo)函數(shù)中分別賦予 Ｍ 121212212m a x Z = x +2 xx x 2 x x 1 x 3 x ,x 0??????????? ???1 2 31 2 425j x x x 2 x x x 1 x x 3 x 0 ,j 1 ,2 ,3 ,4 ,5???????????? ?? ??1 2 6 71 2 3 61 2 4 725jm a xZ = x + 2x M x M x x x x x 2 x x x x 1 x x 3 x 0, j 1, 2, 3, 4, 5, 6, 7? ? ???? ? ??????? ? ? ??67x ,x41 0 1 1/2 1/2 0 1/2 1/2 3/2 X2 2 1 0 1/2 1/2 0 1/2 1/2 1/2 X1 1 1 1 0 1 0 0 1 1 X2 2 1/2 2 0 1 1 0 1 1 1 X6 M 1/1 1 1 0 1 0 0 1 1 X7 M 2/1 1 1 1 0 0 1 0 2 X6 M 0 0 1/2 3/2 0 1/2M 3/2M 5/2 Z 0 0 1/2 1/2 1 1/2 1/2 3/2 X5 0 1+2M 0 M 2+M 0 0 22M 2M Z 2/1 1 0 0 1 1 0 1 2 X5 0 1 2+2M M M 0 0 0 3M Z 3/1 0 1 0 0 1 0 0 3 X5 0 X1 x2 x3 x4 x5 x6 x7 b XB CB θ 1 2 0 0