【正文】 的基本原理 如果記 ( 0 ) 1Bz c B b?? 112( , , , )N m m n N Bc c B N? ? ? ? ???? ? ?39。1 1 139。 39。39。 1 39。1( , , ) Tmb B b b b???則典式 (1a)(2a)(3a) 可寫成 ( 0 )1 1 2 239。 39。1 1 1 1 1 2 2 1 139。 39。2 2 1 1 2 2 2 2 239。 39。1 1 2 2m a x..0 ( 1 , 2 , , )m m m m n nm m m m n nm m m m n nm m m m m m m m n n mjz z x x xs t x a x a x a x bx a x a x a x bx a x a x a x bx j n? ? ?? ? ? ?? ? ? ?? ? ? ?? ? ? ?? ? ? ? ?? ? ? ? ?? ? ? ? ?? ? ? ? ???139。39。 39。12( , , , , 0 , , 0) Tmx b b b?是 LP 問題的最優(yōu)解，記為 39。 39。 4 單純形法的基本原理 定理 8 在 LP 問題 的典式 (1b) ～ (3b)中， ( 0 )139。1m a x ( 1 ). . ( 1 , 2 , , ) ( 2 )0 ( 1 , 2 , , ) ( 3 )njjjmni ij j ijmjz z x bs t x a x b i m bx j n b???????? ? ?????? ? ? ?0 39。1 , , , 0 , , 0 Tmx b b?是對應(yīng)于基 B 的一個(gè)基可行解，如果滿足下列條件： (1)有某個(gè)非基變量 xk 的檢驗(yàn)數(shù) σk 0 (m+1 ≤ k ≤n)。 (3) 0 (i=1,2,…,m) , 即 x(0) 為非退化的基可行解。ib則從 x(0)出發(fā)，一定能找到一個(gè)新的基可行解 ? ?( 1 ) ( 1 ) ( 1 ) ( 1 ) ( 1 ) ( 0 )12 , , , .Tnx x x x c x c x? 使 得 第一章 線性規(guī)劃及單純形法 定理 9 在 LP 問題的典式 (1b) ～ (3b)中，如果檢驗(yàn) 數(shù)滿足最優(yōu)準(zhǔn)則 σj ≤ 0 ( j = m+1 ,…,n ) ， 且其中有一 個(gè) σk = 0 ( m+1 ≤ k ≤n )， 則該 LP 問題有無窮多個(gè) 最優(yōu)解。39。 167。 39。 39。 39。 39。 39。 39。 5 單純形法的計(jì)算步驟 列出如下 LP 問題 的初始單純形表。kP1a Step 2 檢驗(yàn)各非基變量 xj 的檢驗(yàn)數(shù) σj , 如果所有 的 σj ≤ 0（ j = 1,2,? , n） ， 則已求得最優(yōu)解 ， 停 止計(jì)算 。否則轉(zhuǎn)入下一 步 。 5 單純形法的計(jì)算步驟 Step 4 根據(jù) ,確定 xk為換入 基變量 ， 又根據(jù)最小比值法則計(jì)算 : 確定 xr為換出基變量 。 ? ?m a x 0 , 1k j j jn? ? ?? ? ? ?39。39。39。139。39。0010kkkrkmnaaPaa?? ???? ???? ???? ??? ????? ???? ???? ???? ??????????39。 返回 Step 2 。 5 單純形法的計(jì)算步驟 思考： 在單純形法中根據(jù) ? ?m a x 0 , 1k j j jn? ? ?? ? ? ?確定 xk為進(jìn)基變量 ， 是否在這次變換中 ， 使目 標(biāo)函數(shù)值提高最大 ？ 如果不是，應(yīng)選擇哪個(gè)變量進(jìn)基，保證這 次變換使得目標(biāo)函數(shù)值提高最大？ 目標(biāo)函數(shù)值能提高多少？ 167。 6 單純形法的進(jìn)一步討論 (1)大 M 法 懲罰法 max w = c1x1 + c2x2 +… + xn –M ( xn+1 +…+ xn+m ) . a11x1 + a12x2 +… + a1nxn + xn+1 = b1 a21x1 + a22x2 +… + a2nxn + xn+2 = b2 …… …… am1x1 + am2x2 +… + amnxn + xn+m = bm xj≥0 （ j = 1,2,… , n, n+1,… , n+m） M 是一個(gè)充分大的正數(shù) 結(jié)論： 設(shè) 1 2 1( , , , , , , ) Tn n n mx x x x x x? ? ? ? ? ????為上述問題的最優(yōu)解 120n n n mx x x? ? ?? ? ?? ? ? ? 如 果 ，則 12( , , , ) Tnx x x? ? ?為原問題的最優(yōu)解，這時(shí)的目標(biāo)函數(shù)值為最優(yōu)值； 則原問題無可行解。 6 單純形法的進(jìn)一步討論 (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） 是否存在可行解，如果存在就找出一 個(gè)初始基可行解； 解之可得： （ a） 如果 wmax 0, 則原問題無可行解，停止計(jì)算； （ 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 不可能全為零，必有某個(gè) a’lj ≠ 0， 這時(shí) xj 不是基變量，與 x n+k 交換即可。 6 單純形法的進(jìn)一步討論 二、關(guān)于退化和循環(huán) 1955 年 Beale 給出如下例子： 4 5 6 71 4 5 6 72 4 5 6 73631m a x 20 6421. . 8 9 041112 3 02210 ( 1 , 2 , , 7 )jz x x x xs t x x x x xx x x x xxxxj? ? ? ?? ? ? ? ?? ? ? ? ?????m a x35( , 0 , 0 , 1 , 0 , 1 , 0) ,44Txz? ??最優(yōu)解： 第一章 線性規(guī)劃及單純形法 Bland 法則： （對極大值問題而言） 則選擇 xk 作為進(jìn)基變量。 即如果 則選擇 xl作為出基變量 。39。39。m in m in 0 , 1rrikrirk rkbbl r a i maa?????? ? ? ? ?? ? ???? 167。 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 的費(fèi)用 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。已知原料每根長 ， 現(xiàn)考慮應(yīng)如何下料，可使所用原料最??？ 解： 一根原料做一套，料頭. 下料方案表 方案 毛坯 /m 方案 1 方案 2 方案 3 方案 4 方案 5 方案 6 方案 7 方案 8 2． 9 2 1 1 1 0 0 0 0 2． 1 0 2 1 0 3 2 1 0 1． 5 1 0 1 3 0 2 3 4 合 計(jì) 7． 3 7． 1 6． 5 7． 4 6． 3 7． 2 6． 6 6． 0 料 頭 0． 1 0． 3 0． 9 0． 0 1． 1 0． 2 0． 8 1． 4 去掉料頭 ≥ 的方案可以嗎？ 167。 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根。 什么原因？ 第一章 線性規(guī)劃及單純形法 完 演講完畢，謝謝觀看！