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

1、編輯課件1 編輯課件22.1 單純形法的基本思想單純形法的基本思想2.2 單純形法的計(jì)算過(guò)程單純形法的計(jì)算過(guò)程2.3 人工變量法人工變量法2.4 單純形法補(bǔ)遺單純形法補(bǔ)遺第第2章章 單純形法單純形法編輯課件3 單純形法的基本思想單純形法的基本思想 單純形法有三種形式：?jiǎn)渭冃畏ㄓ腥N形式： 方程組形式方程組形式 表格形式表格形式 矩陣形式矩陣形式2.1.1 方程組形式的單純形法方程組形式的單純形法：由一個(gè)基本可行解轉(zhuǎn)化為另一個(gè)基本可行解。：由一個(gè)基本可行解轉(zhuǎn)化為另一個(gè)基本可行解。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 范例范例等價(jià)改寫(xiě)為等價(jià)改寫(xiě)為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àn)：最優(yōu)性檢驗(yàn)：j 0 ？初始基本可行解初始基本可行解 X0 = (0, 0, 8, 12, 36)T z0 = 排列陣排列陣： 每行每列有且僅有一個(gè)元素每行每列有且僅有一個(gè)元素為為 ，其余元素全為，其余元素全為 的方陣。的方陣。1 = - -3 02 = - -5 0當(dāng)前解當(dāng)前解 X0 非優(yōu)；非優(yōu)；+0 x3+0 x4+0 x5須由須由X0 轉(zhuǎn)化為另一個(gè)基本可行解轉(zhuǎn)化為另一個(gè)基本可行解 X1。滿足滿足的的方程組方程組稱(chēng)為稱(chēng)為()。：讓?zhuān)鹤孹0 中的一個(gè)中的一個(gè)非基變量非基變量進(jìn)基進(jìn)基，去替換原來(lái)的一個(gè)，去替換原來(lái)的一個(gè)（離基離基）。）。編輯課件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 得得稱(chēng)為單純形法的一次稱(chēng)為單純形法的一次迭代迭代。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)化為另一個(gè)基本另一個(gè)基本可行解可行解 。 單純形法的基本思想單純形法的基本思想編輯課件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 檢驗(yàn)行檢驗(yàn)行35 單純形法的計(jì)算過(guò)程單純形法的計(jì)算過(guò)程s.t. x1 + +x3 = = 8 2x2 + +x4 = = 12 3x1 + + 4x2 + +x5 = = 36 x1 ， x2 ，x3，x4，x5 0 max z =

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

9、 ar 0，即一切，即一切 air 0 ， i=1, 2, , m 則該則該LP問(wèn)題問(wèn)題，停止計(jì)算；否則轉(zhuǎn)，停止計(jì)算；否則轉(zhuǎn)5 。編輯課件13 單純形法的計(jì)算過(guò)程單純形法的計(jì)算過(guò)程 先按先按 min jj 0 =aikbiakb編輯課件14 單純形法的計(jì)算過(guò)程單純形法的計(jì)算過(guò)程2 2. .2 2. .3 3 單純形法計(jì)算之例單純形法計(jì)算之例范例范例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、法的計(jì)算過(guò)程單純形法的計(jì)算過(guò)程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 單純形法的計(jì)算過(guò)程單純形法的計(jì)算過(guò)程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 單純形法的計(jì)算過(guò)程單純形法的計(jì)算過(guò)程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解無(wú)界解無(wú)界例例2 2 求解下述求解下述LP問(wèn)題問(wèn)題編輯課件18 人工變量法人工變量法 考慮考慮標(biāo)準(zhǔn)型標(biāo)準(zhǔn)型 (M)： 分別給每個(gè)約束方程分別給每個(gè)約束方程一個(gè)非負(fù)變量一個(gè)非負(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個(gè)個(gè) xn+1, xn+2, , xn+m 稱(chēng)為稱(chēng)為人工變量人工變量。 初始基本可行解：初始基本可行解：( ( ) ) = ( 0, 0, , 0, b1, b2, , bm )T編輯課件19 人造解人造解 X0 不是原不是原問(wèn)題的基本可行解。問(wèn)題的基本可行解。 但若能通過(guò)單純形法的迭代步驟，將虛擬但若能通過(guò)單純形法的迭代步驟，將虛擬 的人工變量都替換出去，都變?yōu)榉腔兞浚吹娜斯ぷ兞慷继鎿Q出去，都變?yōu)榉腔兞浚?人工變量人工變量xn+ +1 = xn+ +2 = = xn+ +m = 0），則），則X0的的 前前n個(gè)分量就構(gòu)成原個(gè)分量就構(gòu)成原問(wèn)題的一個(gè)基本可行解。問(wèn)

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

15、因此迭代必然趨向于把具有充分小系數(shù)的人工變量從基變量中替換出去。數(shù)的人工變量從基變量中替換出去。 若迭代最終得到若迭代最終得到，而且，而且中中，則，則的的前前n個(gè)分量就構(gòu)成原問(wèn)題的一個(gè)個(gè)分量就構(gòu)成原問(wèn)題的一個(gè)；否則，原問(wèn)題；否則，原問(wèn)題。 若迭代結(jié)果是若迭代結(jié)果是，而且，而且中中， 則原問(wèn)題也則原問(wèn)題也；否則，原問(wèn)題；否則，原問(wèn)題。編輯課件21 人工變量法人工變量法 例例3 3 用大用大M法求解下述法求解下述LPLP問(wèn)題問(wèn)題 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 人工變量法人工變量法 兩階段法兩階段法 階段階段 求解求解人造極大問(wèn)題人造極大問(wèn)題 max w = - -xn+1 - -xn+2 - - - -xn+m s.t. 因?yàn)槿斯ぷ兞恳驗(yàn)槿斯ぷ兞?xn+1, xn+2, , xn+m 0 所以所以 max w 0(1) 若若w* 0，則原問(wèn)題，則原問(wèn)題無(wú)可行解無(wú)可行解，停止計(jì)算；，停止計(jì)算；(2) ，且人工變量都不是基變量，

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

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

20、和j ，用以取代原檢驗(yàn)行中相應(yīng)數(shù)字。，用以取代原檢驗(yàn)行中相應(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 人工變量法人工變量法 階段階段：求解原問(wèn)題：求解原問(wèn)題 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)基變量按最小檢驗(yàn)數(shù)規(guī)則選定，如果出進(jìn)基變量按最小檢驗(yàn)數(shù)規(guī)則選定，如果出現(xiàn)兩個(gè)或更多個(gè)現(xiàn)兩個(gè)或更多個(gè)j0同時(shí)達(dá)到最小而相持時(shí)同時(shí)達(dá)到最小而相持時(shí),則應(yīng)：則應(yīng)：從相持的檢驗(yàn)數(shù)從相持的檢驗(yàn)數(shù)k 所對(duì)應(yīng)的變量所對(duì)應(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 是一重要問(wèn)題，關(guān)鍵在于是一重要問(wèn)題，關(guān)鍵在于突破離基變量的相持必然導(dǎo)致一個(gè)突破離基變量的相持必然導(dǎo)致一個(gè)的基本可行的基本可行解，這就有可能造成單純形法的迭代步驟陷入一個(gè)解，這就有可能造成單純形法的迭代步驟陷入一個(gè)周而復(fù)始的周而復(fù)始的過(guò)程。過(guò)程。 避免避免的方法有：的方法有： 攝動(dòng)法攝動(dòng)法； 辭典序法辭典序法； 布蘭德法布蘭德法根據(jù)根據(jù)攝動(dòng)法攝動(dòng)法，避免，避免的的準(zhǔn)則準(zhǔn)則是：是： 單純形法補(bǔ)遺單純形法補(bǔ)遺從相持的離基變量中，選擇從相持的離基變量中，選擇離基。離基。編輯課件31 在在最優(yōu)最優(yōu)單純形表單純形表中中： 若有一個(gè)或更多個(gè)若有一個(gè)或更多個(gè)非基變量非基變量xj的檢驗(yàn)數(shù)的檢驗(yàn)數(shù)j = 0，則該問(wèn)題有無(wú)窮則該問(wèn)題有無(wú)窮多個(gè)最優(yōu)解多個(gè)最優(yōu)解； 單純形法補(bǔ)遺單純形法補(bǔ)遺 多重最優(yōu)解多重最優(yōu)解每次都選一個(gè)這樣的每次都選一個(gè)這樣的 xj 進(jìn)基進(jìn)基，就能得到其它最優(yōu)基本解就能得到其它最優(yōu)基本解； 若問(wèn)題有若問(wèn)題有r 個(gè)最優(yōu)極點(diǎn)解個(gè)最優(yōu)極點(diǎn)