【正文】 ??TTB B N NBNBNfs t f c x c xBx N x bxx1. 構(gòu)造單純形表 ? ?,?A B N標(biāo)準(zhǔn)形式的線性規(guī)劃 標(biāo)準(zhǔn)形式繼續(xù)等價(jià)于 ? ?1111m in..+ 0 +0 , 0BNT T TB B N N BBNfs t x B N x B bf x c B N c x c B bxx??????? ? ???11????BNx B N x B b11????T T TB B B N Bc x c B N x c B b11??? ? ?T T TB B B N Bx c B N x c B b 0? ? ? ?T T TB N B N Nf c B x c B b c x? ?110 ??? ? ? ? ?T T TB N N Bf x c B N c x c B b?把 約束方程的系數(shù) 置于表中，就得到了所謂的單純形表 . 1列 cBTB1 b B1b 右端 m行 B1N Im 0 xN xB f nm列 m列 1列 1行 cBT B1N cNT 0 1 目標(biāo)函數(shù)值 判別數(shù) 基變量的值 使用表格形式的單純形方法 1. 構(gòu)造單純形表 ? ?1111m in..+ 0 +0 , 0BNT T TB B N N BBNfs t x B N x B bf x c B N c x c B bxx??????? ? ???A中若存在 m階的單位矩陣 表格容易構(gòu)造 xB f zk ck ymk yrk y1k … … zj cj … zm+1 –cm+1 0 … 0 … 0 … … ymj … ymm+1 1 … 0 … 0 … … … … … yrj … yrm+1 0 … 1 … 0 … … … … … y1j … y1m+1 0 … 0 … 1 初始單純形表 … 1x rx mx… 1xrxmx… … fjx 1brbmb… … … … … … … … … … … … … … kx… … 1mx ?TBcb使用表格形式的單純形方法 1. 構(gòu)造單純形表 xk是進(jìn)基變量 ， 是離基變量； rx主元 rxrx把 xk 所對(duì)應(yīng)的列向量 pk 變成 所對(duì)應(yīng)的列向量，即是單位向量。 把 xk 和 的位置對(duì)換， zk ck ymk yrk y1k … … zj cj … zm+1 –cm+1 0 … 0 … 0 … … ymj … ymm+1 1 … 0 … 0 … … … … … yrj … yrm+1 0 … 1 … 0 … … … … … y1j … y1m+1 0 … 0 … 1 … 1x rx mx… 1xrxmx… … fjx 1brbmb… … … … … … … … … … … … … … kx… … 1mx ?Bcb使用表格形式的單純形方法 2. 高斯主元消去法 主元 將 yrk 變?yōu)?1， yik ( i ≠ r)以及 zk –ck都變?yōu)?0 把 pk 變成 對(duì)應(yīng)的單位向量？ rx作業(yè) : P157 對(duì)應(yīng)的新的目標(biāo)函數(shù)值即為： 10 ()? ? ?k k kf f z c x使用表格形式的單純形方法 2. 高斯主元消去法 39。 ?rj rj rky y y以 yrk 為主元素進(jìn)行 Gauss消元 : 將第 r 行每個(gè)元素除以 yrk : 將第 r 行每個(gè)元素乘以 – yik / yrk 加到第 i 行 (i = 1, , m , i ≠ r) 將第 r 行每個(gè)元素乘以 – (zk –ck) / yrk 加到檢驗(yàn)數(shù)行 ? ?39。 ??ij ij ik rk rjy y y y y? ? ? ?39。 ()? ? ? ? ?j j j j k k rk rjz c z c z c y y? rkrkbxy0 ()? ? ?rkkrkbf z cy經(jīng)過(guò) Gauss消元后，針對(duì)于新基 B1 的基本可行解為： ( 1 ), 1 , 2 , ..., ,0 , , 1 , ..., 1 , 1 ,riikrkrirkbb y i m i rybx i kyi r m k k?? ? ?????????? ? ? ? ????? ?1( 1 ) 1 1 1, ..., , 0 , , 0 , ..., , 0 , ..., 0 Tr r kx x x x x???使用表格形式的單純形方法 2. 高斯主元消去法 步驟 3：在所有 ?j 0, j∈ RN 中，若有一個(gè) ?j 對(duì)應(yīng)的系數(shù)列向量 yj ? 0，則此問(wèn)題沒(méi)有有限最優(yōu)解，停止計(jì)算，否則轉(zhuǎn) 步 驟 4； 使用表格形式的單純形方法 步驟 1：找出初始可行基，確定初始基本可行解 ，建立初始單 純形表； 步驟 2：檢查對(duì)應(yīng)于非基變量的檢驗(yàn)數(shù) ?j = zj cj, j∈ RN , 若所有 ?j ? 0 , j∈ RN , 則已得到最優(yōu)解 , 停止計(jì)算 。 否則轉(zhuǎn) 步驟 3 步驟 4：根據(jù) max {?j |?j 0, j∈ RN } = ?k ,確定 xk 為進(jìn)基變量。 m in 0 , 1ir ikrk ikb b y i myy???? ? ? ? ?????確定 xr 為離基變量 (即為新基的非基變量 ), 轉(zhuǎn) 步驟 6； 步驟 5：再根據(jù) 步驟 6： 以 yrk 為主元素進(jìn)行 Gauss消元，轉(zhuǎn) 步驟 2。 使用表格形式的單純形方法 例 1. 利用單純形算法求解 如下的線性規(guī)劃問(wèn)題。 解 ： 1. 寫出線性規(guī)劃的標(biāo)準(zhǔn)型 使用表格形式的單純形方法 1212121212m a x 2 32 2 12284 164 12,0?????????z x xxxxxxxxx121 2 31 2 415261 2 3 4 5 6m in 2 32 2 12284 164 12, , , , , 0? ? ?? ? ?? ? ??????z x xx x xx x xxxxxx x x x x xA中存在 4階單位矩陣 選取 作為基變量， 3 4 5 6, , ,x x x x得到一個(gè)基本可行解 ( 0 , 0 , 12 , 8 , 16 , 12) Tx ? 2. max{?1, ?2}=3= ?2, 所以 x2 為進(jìn)基變量 . 3. p2的坐標(biāo)有正分量存在 ， 因?yàn)?3與 x6 那一行相對(duì)應(yīng)，所以 x6 為離基變量；故 x2對(duì)應(yīng)列與 x6對(duì)應(yīng)行的相交處的 4為主元素； xB x1 x2 x3 x4 x5 x6 2 2 1 0 0 0 1 2 0 1 0 0 4 0 0 0 1 0 0 4 0 0 0 1 x3 x4 x5 x6 12 8 16 12 2 3 22212 8 12m in { | 0 } m in , , 3224iriiribb yyy??? ? ? ?????121 2 31 2 415261 2 3 4 5 6m i n 2 32 2 12284 164 12, , , , , 0? ? ?? ? ?? ? ??????z x xx x xx x xxxxxx x x x x xbc 2 3 0 0 0 0 1 ? ???Tj B j jc B P c ??TB j jc P c?6 4 3 ?j0 0 0 0 cB 0 0 0 0 4. 以“ 4”為主元素 Gauss消去，進(jìn)行行初等變換 xB x1 x2 x3 x4 x5 x6 x3 x4 x5 x2 bc 2 3 0 0 0 0 ? ?jcB 0 0 0 3 2 0 1 0 0 1/2 6 2 0 0 0 0 3/4 3 2 4 0 1 0 0 0 1/4 3 4 0 0 0 1 0 16 1 0 0 1 0 1/2 2 這行除以 4 xB x1 x2 x3 x4 x5 x6 2 2 1 0 0 0 1 2 0 1 0 0 4 0 0 0 1 0 0 4 0 0 0 1 x3 x4 x5 x6 12 8 16 12 2 3 bc 2 3 0 0 0 0 ?6 4 3 ?j0 0 0 0 cB 0 0 0 0 這行不變 第 4行的 1/2加到這行 第 4行的 1/2加到這行 第 4行的 3/4加到檢驗(yàn)數(shù)行 5. max{?1}=2= ?1, 所以 x1 為進(jìn)基變量 . 6. p1的坐標(biāo)有正分量存在 ， 因?yàn)?2與 x4 那一行相對(duì)應(yīng)，所以 x4 為離基變量；故 x1對(duì)應(yīng)列與 x4對(duì)應(yīng)行的相交處的 1為主元素； 1116 2 16m in { | 0 } m in , , 22 1 4iriiribb yyy??? ? ? ?????7. 以“ 1”為主元素Gauss消元，進(jìn)行行初等變換 xB x1 x2 x3 x4 x5 x6 x3 x1 x5 x2 bc 2 3 0 0 0 0