《管理運(yùn)籌學(xué)》02-單純形法

1、編輯課件1 編輯課件22.1 單純形法的基本思想單純形法的基本思想2.2 單純形法的計算過程單純形法的計算過程2.3 人工變量法人工變量法2.4 單純形法補(bǔ)遺單純形法補(bǔ)遺第第2章章 單純形法單純形法編輯課件3 單純形法的基本思想單純形法的基本思想 單純形法有三種形式：單純形法有三種形式： 方程組形式方程組形式 表格形式表格形式 矩陣形式矩陣形式2.1.1 方程組形式的單純形法方程組形式的單純形法：由一個基本可行解轉(zhuǎn)化為另一個基本可行解。：由一個基本可行解轉(zhuǎn)化為另一個基本可行解。s.t. x1 +x3 = 8 2x2 +x4 = 12 3x1 + 4x2 +x5 = 36 x1 ， x2 ，x3

2、，x4，x5 0 max z = = 3x1+5x2z - -3x1 - -5x2 = 0例例1 范例范例等價改寫為等價改寫為s.t. z -3x1 -5x2 = 0 x1 + +x3 = 8 2x2 +x4 = 12 3x1+4x2 +x5 = 36 x1 ， x2 ，x3，x4，x5 0 max z目標(biāo)方程目標(biāo)方程編輯課件4 單純形法的基本思想單純形法的基本思想 0 00 1 00 0 1 當(dāng)前基：當(dāng)前基：m階階排列陣排列陣 目標(biāo)方程目標(biāo)方程中：一切基變量中：一切基變量 的系數(shù)的系數(shù) j = 0Z - -3x1 - -5x2 = x1 +x3 = 8 2x2 +x4 = 12 3x1 +

3、4x2 +x5 = 36 ()0最優(yōu)性檢驗：最優(yōu)性檢驗：j 0 ？初始基本可行解初始基本可行解 X0 = (0, 0, 8, 12, 36)T z0 = 排列陣排列陣： 每行每列有且僅有一個元素每行每列有且僅有一個元素為為 ，其余元素全為，其余元素全為 的方陣。的方陣。1 = - -3 02 = - -5 0當(dāng)前解當(dāng)前解 X0 非優(yōu)；非優(yōu)；+0 x3+0 x4+0 x5須由須由X0 轉(zhuǎn)化為另一個基本可行解轉(zhuǎn)化為另一個基本可行解 X1。滿足滿足的的方程組方程組稱為稱為()。：讓：讓X0 中的一個中的一個非基變量非基變量進(jìn)基進(jìn)基，去替換原來的一個，去替換原來的一個（離基離基）。）。編輯課件5 單純

4、形法的基本思想單純形法的基本思想x1仍為非基變量，其值為仍為非基變量，其值為0。x3 = 8x4 = 12 - -2x2x5 = 36 - -4x2 x2 12/2 x2 36/4w （） ： x2 min ，12/2，36/4 = 6 x2 = min ，12/2，36/4 = x4x4為為離基變量離基變量w 進(jìn)基進(jìn)基（）：）： 在在中選擇中選擇進(jìn)基進(jìn)基。 min jj0 = k xk 進(jìn)基進(jìn)基 min - -3，- -5 = - -5= 2 x2 進(jìn)基進(jìn)基z -3x1 -5x2 = x1 +x3 = 8 2x2 +x4 = 12 3x1 + 4x2 +x5 = 36 ()0由由 有有編輯課

5、件6 單純形法的基本思想單純形法的基本思想 0主列主列進(jìn)基進(jìn)基主元主元 z - - 3x1 - - 5 x2 = 0 x1 +x3 = 8 2 x2 +x4 = 12 3x1 + 4 x2 +x5 = 36 ()min以以主列主列中中為為，同行，同行為為，求，求；按按確定確定和和，以及，以及。編輯課件7 () x1 +x3 = 8 3x1 - -2x4 +x5 = 12 得得稱為單純形法的一次稱為單純形法的一次迭代迭代。z- - 3x1 - -5x2 = 0 x1 +x3 = 8 2x2 +x4 = 12 3x1 + 4x2 +x5 = 36 ()20 x2 + x4 = 6 12 z -3x

6、1 + x4 = 30052的的是把是把變?yōu)樽優(yōu)樽冏優(yōu)闉?，其余變?yōu)?，其余變?yōu)?。用用將將X0 轉(zhuǎn)化為轉(zhuǎn)化為另一個基本另一個基本可行解可行解 。 單純形法的基本思想單純形法的基本思想編輯課件8 單純形法的基本思想單純形法的基本思想() x1 - - x4 + x5 = 4 2 31 3x2 + x4 = 6 12() x1 +x3 = 8 3 x1 - -2x4 + x5 = 12 x2 + x4 = 6 12 z- -3x1 + x4 = 30052 x3 + x4 - - x5 = 4 2 31 3 z + x4 +x5 = 42012得得 min10編輯課件9 單純形法的基本思想單純形法

7、的基本思想2.1.2 單純形法的幾何意義單純形法的幾何意義D(0,6)O(0,0)C(4,6)B(8,3)A(8,0)x1x2z = 0脊線脊線編輯課件10 單純形表單純形表范例范例: 基于基于cj 基基 解解 x1 x2 x3 x4 x5 3 5 0 0 0比比 值值 1 0 1 0 0 x3x4 x5 81236 0 2 0 1 000 0 3 4 0 0 1 檢驗行檢驗行35 單純形法的計算過程單純形法的計算過程s.t. x1 + +x3 = = 8 2x2 + +x4 = = 12 3x1 + + 4x2 + +x5 = = 36 x1 ， x2 ，x3，x4，x5 0 max z =

8、 = 3x1+ +5x2 = T檢驗行檢驗行= cj ,Tj=1,2,n編輯課件11 單純形法的計算過程單純形法的計算過程初始單純形表初始單純形表的一般形式的一般形式編輯課件12 單純形法的計算過程單純形法的計算過程 2.2.2 單純形法的計算步驟單純形法的計算步驟把把LP問題化為問題化為。在系數(shù)陣中找出或構(gòu)造一個在系數(shù)陣中找出或構(gòu)造一個作為初始作為初始 可行基，建立可行基，建立。: 若所有檢驗數(shù)若所有檢驗數(shù)j 0，就得到一個，就得到一個 最優(yōu)基本解，停止計算；否則轉(zhuǎn)最優(yōu)基本解，停止計算；否則轉(zhuǎn)4 。: 在所有在所有j 0中中, 只要有一個只要有一個r 0 所對應(yīng)的系數(shù)列向量所對應(yīng)的系數(shù)列向量

9、 ar 0，即一切，即一切 air 0 ， i=1, 2, , m 則該則該LP問題問題，停止計算；否則轉(zhuǎn)，停止計算；否則轉(zhuǎn)5 。編輯課件13 單純形法的計算過程單純形法的計算過程 先按先按 min jj 0 =aikbiakb編輯課件14 單純形法的計算過程單純形法的計算過程2 2. .2 2. .3 3 單純形法計算之例單純形法計算之例范例范例cj 基基 解解 x1 x2 x3 x4 x5 3 5 0 0 0比比 值值 1 0 1 0 0 x3x4 x5 812 36 0 2 0 1 000 0 3 4 0 0 1 0 - -3 - -5 0 0 0- -6 9min2編輯課件15 單純形

10、法的計算過程單純形法的計算過程cj 基基 解解 x1 x2 x3 x4 x5 3 5 0 0 0比比 值值 1 0 1 0 0 x3x4 x5 81236 0 2 0 1 000 0 3 4 0 0 1 0 - -3 - -5 0 0 0- -6 9min2x3x2 x5 05 01/2 8 1 0 1 0 0- -25/2 4min 1600012300130- -30008 - -編輯課件16 單純形法的計算過程單純形法的計算過程cj 基基 解解 x1 x2 x3 x4 x5 3 5 0 0 0比比 值值 1 0 1 0 0 x3x2 x5 8612 0 1 0 1/2 005 0 3 0

11、 0 - -2 1 30 - -3 0 0 5/2 0 x3x2 x1 05 36 0 1 0 1/2 04 0 0 1 2/3 - -1/3 4 1 0 0 - -2/3 1/342 0 0 0 1/2 18- - 4min3X*= (4, 6, 4, 0, 0)T, z* = 42編輯課件17 單純形法的計算過程單純形法的計算過程s.t.max z = 3x1+2x2 -2x1 +x2 2 x1 -3x2 3 x1 ， x2 0 s.t.max z = 3x1+2x2 -2x1 +x2 +x3 = 2 x1 -3x2 +x4 = 3 x1，x2 ，x3， x4 0 cj 基基 解解 x1

12、x2 x3 x4 3 2 0 0 - -2 1 1 0 x3x4 23 1 - -3 0 100 0 - -3 - -2 0 01 3 - -3 0 1x3x1 03 8 - -5 1 2 9 - -11 0 3解無界解無界例例2 2 求解下述求解下述LP問題問題編輯課件18 人工變量法人工變量法 考慮考慮標(biāo)準(zhǔn)型標(biāo)準(zhǔn)型 (M)： 分別給每個約束方程分別給每個約束方程一個非負(fù)變量一個非負(fù)變量 a11x1 +a12x2+a1nxn + +xn+1n+1 = b1 (0) a12x1 +a22x2+a2nxn + +xn+2n+2 = b2 (0) am1x1+am2x2+amnxn + +xn+m

13、n+m = bm(0)n個個 xn+1, xn+2, , xn+m 稱為稱為人工變量人工變量。 初始基本可行解：初始基本可行解：( ( ) ) = ( 0, 0, , 0, b1, b2, , bm )T編輯課件19 人造解人造解 X0 不是原不是原問題的基本可行解。問題的基本可行解。 但若能通過單純形法的迭代步驟，將虛擬但若能通過單純形法的迭代步驟，將虛擬 的人工變量都替換出去，都變?yōu)榉腔兞浚吹娜斯ぷ兞慷继鎿Q出去，都變?yōu)榉腔兞浚?人工變量人工變量xn+ +1 = xn+ +2 = = xn+ +m = 0），則），則X0的的 前前n個分量就構(gòu)成原個分量就構(gòu)成原問題的一個基本可行解。問

14、題的一個基本可行解。 反之，若經(jīng)過迭代，不能把人工變量都變反之，若經(jīng)過迭代，不能把人工變量都變 為非基變量，則表明原為非基變量，則表明原問題問題無可行解無可行解。 人工變量法人工變量法編輯課件20 人工變量法人工變量法 大大M法法 在原問題的目標(biāo)函數(shù)中添上全部人工變量，并令其系數(shù)在原問題的目標(biāo)函數(shù)中添上全部人工變量，并令其系數(shù) 都為都為- -M，而而M是一個是一個充分大的正數(shù)充分大的正數(shù)。即。即 max z = c1x1 + c2x2 + c3x3 + + cnxn M( xn+1 + xn+2 + xn+m ) 由于問題目標(biāo)要求最大化，因此迭代必然趨向于把具有充分小系由于問題目標(biāo)要求最大化，

15、因此迭代必然趨向于把具有充分小系數(shù)的人工變量從基變量中替換出去。數(shù)的人工變量從基變量中替換出去。 若迭代最終得到若迭代最終得到，而且，而且中中，則，則的的前前n個分量就構(gòu)成原問題的一個個分量就構(gòu)成原問題的一個；否則，原問題；否則，原問題。 若迭代結(jié)果是若迭代結(jié)果是，而且，而且中中， 則原問題也則原問題也；否則，原問題；否則，原問題。編輯課件21 人工變量法人工變量法 例例3 3 用大用大M法求解下述法求解下述LPLP問題問題 max z = 3x1 x2 2x3 3x1+ 2x2 3x3 = 6 x1 2x2 + x3 = 4 x1， x2， x3 0 max z = 3x1 x2 2x3 3

16、x1+ 2x2 3x3 +x4 = 6 Mx4x1 2x2 + x3 + x5 = 4Mx5x1， x2， x3 ， x4， x5 0s.t.解解s.t.編輯課件22 人工變量法人工變量法cj 基基 解解 x1 x2 x3 x4 x5 0 0 0 - M - M比比 值值 3 2 - -3 1 0 x4x5 64 1 - -2 1 0 1- - M- - M - -10M - -4M- -3 1 2M +2 0 0243 2 1 2/3 - -1 1/3 0 x1x5 0- - M 2 0 - -8/3 2 - -1/3 16- -2M 0 8M/3+3 - -2M- -1 4M/3+1 02

17、 3- -2 x1x3 1 0 - - 4/3 1 -1/6 1/2 3 1 - -2/3 0 1/6 1/2 7 0 5/3 0 M+5/6 M+1/2min X* = ( 3, 0, 1 )T, z* = 7 編輯課件23 人工變量法人工變量法 兩階段法兩階段法 階段階段 求解求解人造極大問題人造極大問題 max w = - -xn+1 - -xn+2 - - - -xn+m s.t. 因為人工變量因為人工變量 xn+1, xn+2, , xn+m 0 所以所以 max w 0(1) 若若w* 0，則原問題，則原問題無可行解無可行解，停止計算；，停止計算；(2) ，且人工變量都不是基變量，

18、則轉(zhuǎn)入，且人工變量都不是基變量，則轉(zhuǎn)入階段階段： 求解原問題求解原問題；編輯課件24 人工變量法人工變量法(3) ，但，但“”存在人工變量，例如該列第存在人工變量，例如該列第 行的基變量行的基變量 xB是人工變量，同時該行的前是人工變量，同時該行的前n個系數(shù)個系數(shù)aj全都是全都是0，這說明，這說明 原問題的該約束方程式多余的，那么刪去第原問題的該約束方程式多余的，那么刪去第 行及行及xB列，類列，類 似情況全都這樣刪去相應(yīng)行、列；轉(zhuǎn)入似情況全都這樣刪去相應(yīng)行、列；轉(zhuǎn)入階段階段；(4) ，且存在人工變量，且存在人工變量xB是基變量，但該行的前是基變量，但該行的前n個系數(shù)個系數(shù) 中存在中存在ak0

19、 ，則以，則以ak為主元進(jìn)行一次換基運(yùn)算，可使原變?yōu)橹髟M(jìn)行一次換基運(yùn)算，可使原變 量量xk取代人工變量取代人工變量xB作為基變量，類似可將這類人工變量全作為基變量，類似可將這類人工變量全 部都由基變量變?yōu)榉腔兞浚晦D(zhuǎn)入部都由基變量變?yōu)榉腔兞?；轉(zhuǎn)入階段階段。 編輯課件25 階段階段 求解求解 建立建立的的初始單純形表初始單純形表。只需把。只需把階段階段的的修改如下：修改如下： (1) 刪去人工變量刪去人工變量 xn+1，xn+2 ， ， xn+m諸列；諸列； (2) 把把cj行與行與cj列的數(shù)字換成原問題目標(biāo)函數(shù)的相應(yīng)系數(shù)列的數(shù)字換成原問題目標(biāo)函數(shù)的相應(yīng)系數(shù); (3) 重新計算重新計算z0和

20、和j ，用以取代原檢驗行中相應(yīng)數(shù)字。，用以取代原檢驗行中相應(yīng)數(shù)字。 然后用單純形法進(jìn)行迭代，直到運(yùn)算結(jié)束。然后用單純形法進(jìn)行迭代，直到運(yùn)算結(jié)束。 人工變量法人工變量法s.t.3x1 +2x2 3x3 +x4 = 6x1 2x2 + x3 + x5 = 4x1， x2 ， x3， x4， x5 0例例4 4max w = x4 x5編輯課件26 人工變量法人工變量法cj 基基 解解 x1 x2 x3 x4 x5 0 0 0 - - 1 - -1比比 值值 3 2 - -3 1 0 x4x5 64 1 - -2 1 0 1- -1- -1 - -10 - - 4 0 2 0 0243 2 1 2/

21、3 - -1 1/3 0 x1x5 0- -1 2 0 - -8/3 2 - -1/3 1 - -2 0 8/3 - -2 4/3 02min 3- -2 x1x3 0 0 - - 4/3 1 - -1/6 1/2 0 1 - -2/3 0 1/6 1/2 0 0 0 0 1 1編輯課件27 人工變量法人工變量法 階段階段：求解原問題：求解原問題 1 0 - - 4/3 1 3 1 - -2/3 0 x1x3 X* = ( 3, 0, 1 )T, z* = 7 3 - -1 - -2 3- -2 x1 x2 x3cj基基解解編輯課件28 單純形法補(bǔ)遺單純形法補(bǔ)遺 的相持及其突破的相持及其突破

22、進(jìn)基變量按最小檢驗數(shù)規(guī)則選定，如果出進(jìn)基變量按最小檢驗數(shù)規(guī)則選定，如果出現(xiàn)兩個或更多個現(xiàn)兩個或更多個j0同時達(dá)到最小而相持時同時達(dá)到最小而相持時,則應(yīng)：則應(yīng)：從相持的檢驗數(shù)從相持的檢驗數(shù)k 所對應(yīng)的變量所對應(yīng)的變量 xk中中, ,作為進(jìn)基量作為進(jìn)基量。編輯課件29 單純形法補(bǔ)遺單純形法補(bǔ)遺 的相持及其突破的相持及其突破與與 cj 基基 解解 x1 x2 x3 x4 x5 3 5 0 0 0比比 值值 1 0 1 0 0 x3x4 x5 812 24 0 2 0 1 000 0 3 4 0 0 1 0 - -3 - -5 0 0 06 6min4 6 3/4 1 0 0 1/4x3x4 x2 0

23、0 5 0 - -3/2 0 0 1 - -1/2 8 1 0 1 0 1 30 3/4 0 0 0 5/4X*= (0, 6, 8, 0, 0)T, z* = 30 編輯課件30 是一重要問題，關(guān)鍵在于是一重要問題，關(guān)鍵在于突破離基變量的相持必然導(dǎo)致一個突破離基變量的相持必然導(dǎo)致一個的基本可行的基本可行解，這就有可能造成單純形法的迭代步驟陷入一個解，這就有可能造成單純形法的迭代步驟陷入一個周而復(fù)始的周而復(fù)始的過程。過程。 避免避免的方法有：的方法有： 攝動法攝動法； 辭典序法辭典序法； 布蘭德法布蘭德法根據(jù)根據(jù)攝動法攝動法，避免，避免的的準(zhǔn)則準(zhǔn)則是：是： 單純形法補(bǔ)遺單純形法補(bǔ)遺從相持的離基變量中，選擇從相持的離基變量中，選擇離基。離基。編輯課件31 在在最優(yōu)最優(yōu)單純形表單純形表中中： 若有一個或更多個若有一個或更多個非基變量非基變量xj的檢驗數(shù)的檢驗數(shù)j = 0，則該問題有無窮則該問題有無窮多個最優(yōu)解多個最優(yōu)解； 單純形法補(bǔ)遺單純形法補(bǔ)遺 多重最優(yōu)解多重最優(yōu)解每次都選一個這樣的每次都選一個這樣的 xj 進(jìn)基進(jìn)基，就能得到其它最優(yōu)基本解就能得到其它最優(yōu)基本解； 若問題有若問題有r 個最優(yōu)極點解個最優(yōu)極點