【正文】 7 線性規(guī)劃應(yīng)用舉例 剩余料頭最少 min z = + x2 ++0x4 + + ++ . 2x1+x2+x3 +x4 ≥100 2x2+x3 +3x5 + 2x6 +x7 ≥100 x1 +x3+3x4 +2x6 +3x7+4x8 ≥100 xj ≥0 ( j=1,…,8 ) 用單純形法求解可得： x*=（ 0， 0， 0， 100， 0， 50， 0， 0） T， 最少的剩余料頭為 10m， 但原料使用了 150根。 7 線性規(guī)劃應(yīng)用舉例 季度 j 生產(chǎn)能力 （ aj） 生產(chǎn)成本（ dj） 需求量（ bj） 1 30 15． 0 20 2 40 14． 0 20 3 20 15． 3 30 4 10 14． 8 10 方法二 設(shè)第 i 季度生產(chǎn)而用于第 j 季度末交貨的產(chǎn) 品數(shù)量為 xij 噸 . 需求約束： x11=20 x12+x22=20 x13+x23+x33=30 x14+x24+x34+x44=10 生產(chǎn)能力約束： x11 + x12 + x13+ x14 ≤ 30 x22 +x23 +x24 ≤ 40, x33 +x34 ≤20, x44 ≤ 10 xij 的費用 cij= di+( ji ) min z =15 x11 + + + +14x22 + + + + + . x11=20 x11 + x12 + x13+ x14 ≤30 x12+x22=20 x22 +x23 +x24 ≤40 x13+x23+x33=30 x33 +x34 ≤20 x14+x24+x34+x44=10 x44 ≤10 xij ≥0 i =1,…,4。39。 即如果 則選擇 xl作為出基變量 。 6 單純形法的進一步討論 (2)兩階段法 第一階段 ： max z = c1x1 + c2x2 +… + xn (1c) . a11x1 + a12x2 +… + a1nxn = b1 a21x1 + a22x2 +… + a2nxn = b2 …… …… . (2c) am1x1 + am2x2 +… + amnxn = bm xj≥0 （ j = 1,2,… , n） (3c) w = – xn+1 – xn+2 –… – +m (1d) .t. a11x1 + a12x2 +… + a1nxn + xn+1 = b1 a21x1 + a22x2 +… + a2nxn + xn+2 = b2 …… …… (2d) am1x1 + am2x2 +… + amnxn + xn+m = bm xj≥0 （ j = 1,2,… , n, n+1,… , n+m） (3d) 判斷原 LP 問題 （ 1c） ~ （ 3c） 是否存在可行解，如果存在就找出一 個初始基可行解； 解之可得： （ a） 如果 wmax 0, 則原問題無可行解，停止計算； （ b） 如果 wmax = 0, 且人工變量都不是基變量，則轉(zhuǎn)入 第二階段； 第一章 線性規(guī)劃及單純形法 （ c） 如果 wmax = 0, 但仍有取零的人工變量為基變量； x1 x2 … xn xn+1 … xn+k … xn+m b a’l1 a’l2 … a’ln a’ln+1 … 1 … a’n+m 0 如 x n+k =0 是基變量，在最終單純形表中： a’l1 a’l2 … a’ln 不可能全為零，必有某個 a’lj ≠ 0， 這時 xj 不是基變量，與 x n+k 交換即可。 5 單純形法的計算步驟 思考： 在單純形法中根據(jù) ? ?m a x 0 , 1k j j jn? ? ?? ? ? ?確定 xk為進基變量 ， 是否在這次變換中 ， 使目 標函數(shù)值提高最大 ？ 如果不是，應(yīng)選擇哪個變量進基，保證這 次變換使得目標函數(shù)值提高最大？ 目標函數(shù)值能提高多少？ 167。0010kkkrkmnaaPaa?? ???? ???? ???? ??? ????? ???? ???? ???? ??????????39。139。39。 5 單純形法的計算步驟 Step 4 根據(jù) ,確定 xk為換入 基變量 ， 又根據(jù)最小比值法則計算 : 確定 xr為換出基變量 。kP1a Step 2 檢驗各非基變量 xj 的檢驗數(shù) σj , 如果所有 的 σj ≤ 0（ j = 1,2,? , n） ， 則已求得最優(yōu)解 ， 停 止計算 。 39。 39。 39。 167。ib則從 x(0)出發(fā)，一定能找到一個新的基可行解 ? ?( 1 ) ( 1 ) ( 1 ) ( 1 ) ( 1 ) ( 0 )12 , , , .Tnx x x x c x c x? 使 得 第一章 線性規(guī)劃及單純形法 定理 9 在 LP 問題的典式 (1b) ～ (3b)中，如果檢驗 數(shù)滿足最優(yōu)準則 σj ≤ 0 ( j = m+1 ,…,n ) ， 且其中有一 個 σk = 0 ( m+1 ≤ k ≤n )， 則該 LP 問題有無窮多個 最優(yōu)解。1 , , , 0 , , 0 Tmx b b?是對應(yīng)于基 B 的一個基可行解，如果滿足下列條件： (1)有某個非基變量 xk 的檢驗數(shù) σk 0 (m+1 ≤ k ≤n)。 4 單純形法的基本原理 定理 8 在 LP 問題 的典式 (1b) ～ (3b)中， ( 0 )139。12( , , , , 0 , , 0) Tmx b b b?是 LP 問題的最優(yōu)解，記為 39。39。 39。 39。 39。 1 39。 39。 4 單純形法的基本原理 如果記 ( 0 ) 1Bz c B b?? 112( , , , )N m m n N Bc c B N? ? ? ? ???? ? ?39。 基變量用非基變量表示： 2 1 34 1 3112033212033x x xx x? ? ?? ? ?代入目標函數(shù)： z =500+20/3 x1 25/3 x3 令非基變量 x1= x3=0 z=500 基可行解 x(1)=(0,20,0,20)T 大于零！ 第一章 線性規(guī)劃及單純形法 132 1 34 1 320 2550033112033212033z x xx x xx x x? ? ?? ? ?? ? ?因為 x1 的系數(shù)大，所以 x1 換入基變量。 4 單純形法的基本原理 z =15 x1+25 x2 x3 = 60 x1 3x2 x4 = 40 x1 x2 因為 x2 的系數(shù)大，所以 x2 換入基變量。 （ 年 ） 167。 20 135050 ! 1020 ! 30 !C ? ? ?即約 150萬年 如果計算一個基可行解只需要 1 秒，那么計算所有 的基可行解需要： 13 6 360024365 180。 推論 2 如果 LP 問題有最優(yōu)解，則一定可在可行解集 D 的極點上達到。 ( 1 ) ( 2 ) ( )kx x x， ， ，定義 7 設(shè)凸集 兩點 表示為 則稱 x 為 S 的一個極點（或頂點）。 幾何意義：如果集合中任意兩點連線上的一切點都在 該集合中，則稱該集合為凸集。 如果 x* 是基本解，則定理成立； 如果 x* 不是基本解，則由定理 2的證明過程可構(gòu)造兩個可行解 ( 1 ) * ( 2 ) *x x x x? ? ? ?? ? ? ?它的非零分量的個數(shù)比 x* 的減少，且有 ， ( 1 ) * ( 2 ) *, ( 8 )c x c x c c x c x c? ? ? ?? ? ? ?又因為 x* 是最優(yōu)解，故有 * ( 1 ) * ( 2 ), ( 9)c x c x c x c x??由式（ 8）和（ 9）知，必有 ( 1 ) ( 2 ) *0,c c x c x c x?? ? ? ?故 即 x(1),x(2) 仍為最優(yōu)解。 這樣經(jīng)過有限次重復(fù)之后 ， 必可找到一個可行解 使它的非零分量對應(yīng)的列向量線性無關(guān) ， 故可行解 必為基可行解 。 (2) 如果 p1,p2,…,pk線性相關(guān) ， 則必存在一組不全為零的數(shù) δ1,δ2, …,δk 使得 10 ( 5 )kjjjp???? 第一章 線性規(guī)劃及單純形法 假定有 δi≠0， =m in 0 ( 6)i iix??????????????( 2 )xx ????(1 ) ????12( , , , , 0 , , 0) Tk? ? ? ?? 0 ( 1 , 2 , ..., ) ( 7 )jjx j n??? ? ?( 1 ) ( 2 )0 , 0 ,??1 1 1()n n nj j j j j j jj j jx p x p p b?? ? ?? ? ?? ? ? ?? ? ?( 1 ) ( 2 ),A x b A x b??(1) (2),xx取 作 其中 由（ 6）式知，必有 即 又因為由（ 5）式知 故有， ，即 也是 LP的兩個可行解。 定理 定理 3 稱為 LP 問題的基本定理 定理 2 證明 向前 定理 3 證明 LP 問題是一個組合優(yōu)化問題 167。 一個 LP問題 ， 如果它的 所有基可行解都是非退化的就稱該是非退化的 ， 否 則就稱它是退化的 。 記： ? ?1 1 1112, , ,mnm m m nm m naaNaap p p??????????????則 A = ( B, N ) 167。 3 線性規(guī)劃問題解的基本性質(zhì) 討論如下 LP 問題： ? ?m a x ( 1 ). . 20 ( 3 )z c xs t Ax bx???? ?12, , , nc c c c? ? ? 價 值 向 量? ?12, , , Tnx x x x? ? ?? ?12, , , , 0Tmib b b b b? ? ? ? 右 端 向