單純形法基本原理及實例演示[教師助手]

1、單純形法求解動態(tài)演示 v在求解LP問題時,有人給出了圖解法,但對 多維變量時,卻無能為力,于是 v美國數(shù)學(xué)家GBDantgig(丹捷格)發(fā)明了 一種“單純形法”的代數(shù)算法，尤其是 方便于計算機運算。這是運籌學(xué)史上最 輝煌的階段。 1學(xué)校課堂 );,( 21n cccC T n xxx),( 21 X 一、關(guān)于標準型解的若干基本概念一、關(guān)于標準型解的若干基本概念 2學(xué)校課堂 基矩陣基矩陣 示例: 0 1 22 33 . . 23max 321 43 2 1 4321 xxx xx x x ts xxxxz 00 00 3 20 20 0 01 01 0 x1 x2x4x3 0 0 1 3 0 0

2、 3 2 1 = 目標函數(shù) 約束條件 行列式0 基矩陣 X1,x2,x3為基變量為基變量,x4為非基變量為非基變量 3學(xué)校課堂 XT = (XB , XN) T =（ B-1b , 0) T Z = CB B-1b 4學(xué)校課堂 為了矩陣形求逆計算方便， 一般將B轉(zhuǎn)化為單位矩陣。5學(xué)校課堂 將線性規(guī)劃問題化成標準型。將線性規(guī)劃問題化成標準型。 找出或構(gòu)造一個找出或構(gòu)造一個m階單位矩陣作為初始可行基，建立初始單純形表。階單位矩陣作為初始可行基，建立初始單純形表。 計算各非基變量計算各非基變量xj的檢驗數(shù)的檢驗數(shù) j=Cj-CBPj ，若所有，若所有 j0，則問題已得到，則問題已得到 最優(yōu)解，停止計

3、算，否則轉(zhuǎn)入下步。最優(yōu)解，停止計算，否則轉(zhuǎn)入下步。 在大于在大于0的檢驗數(shù)中，若某個的檢驗數(shù)中，若某個 k所對應(yīng)的系數(shù)列向量所對應(yīng)的系數(shù)列向量Pk0，則此問題，則此問題 是無界解，停止計算，否則轉(zhuǎn)入下步。是無界解，停止計算，否則轉(zhuǎn)入下步。 根據(jù)根據(jù)max j j0= k原則，確定原則，確定xk為換入變量為換入變量(進基變量進基變量)，再按，再按 規(guī)則計算：規(guī)則計算： =minbi/aik| aik0=bl/ aik 確定確定xBl為換出變量。建立新的為換出變量。建立新的 單純形表，此時基變量中單純形表，此時基變量中xk取代了取代了xBl的位置。的位置。 以以aik為主元素進行迭代，把為主元素進

4、行迭代，把xk所對應(yīng)的列向量變?yōu)閱挝涣邢蛄?，即所對?yīng)的列向量變?yōu)閱挝涣邢蛄?，即aik 變?yōu)樽優(yōu)?，同列中其它元素為，同列中其它元素為0，轉(zhuǎn)第，轉(zhuǎn)第 步。步。 2、單純形法的計算步驟、單純形法的計算步驟 6學(xué)校課堂 線性規(guī)劃的例子子 0, 400 25005 . 25 160022 34max 21 1 21 21 21 xx x xx xx xxz 7學(xué)校課堂 線性規(guī)劃-標準化 v引入變量：s1,s2,s3 12123 121 122 23 12123 max50100000 300 2400 250 ,0 zxxsss xxs xxs xs x x s s s 8學(xué)校課堂 250 400 3

5、00 3 2 1 2 1 10010 01012 00111 s s s x x 3020102100150maxsssxxz 提取系數(shù)，填入表格： s.t. 3 2 1 2 1 00010050max s s s x x z C向量 CBCN XB XN 基BN jjj zc Zj=CBNj 每個非基 變量的檢 驗值 9學(xué)校課堂 初始單純形表 迭代 次數(shù) 基變 量 CB x1X2s1s2S3 b 比值 1 Zj=CBNj Z=CBB-1b i ij b a jjj zc 10學(xué)校課堂 初始單純形表 迭代 次數(shù) 基變 量 CB x1X2s1s2S3 b 比值 1 Zj=CBNj Z=CBB-1

6、b i ij b a jjj zc 目標函數(shù)系數(shù)區(qū)目標函數(shù)系數(shù)區(qū) 約束條件 系數(shù)區(qū) 右端系數(shù)右端系數(shù) 檢驗系數(shù)區(qū)檢驗系數(shù)區(qū) 基變量區(qū)基變量區(qū) 11學(xué)校課堂 初始單純形表 迭代 次數(shù) 基變 量 CB x1x2s1s2s3 b 比值 50100000 1 Zj=CBNj Z=CBB-1b 2i i a b jjj zc 12學(xué)校課堂 初始單純形表 迭代 次數(shù) 基 變 量 CB x1X2s1s2S3 b 比值 50100000 0 11100300 21010400 01001250 Zj=CBNj Z=CBB-1b 2i i a b jjj zc 13學(xué)校課堂 初始單純形表 迭代 次數(shù) 基 變 量

7、 CB x1x2s1s2s3 b 比值 50100000 1 11100300 21010400 01001250 Zj=CBNj Z=CBB-1b 2i i a b jjj zc 14學(xué)校課堂 初始單純形表 迭代 次數(shù) 基 變 量 CB x1x2s1s2s3 b 比值 50100000 1 S1011100300 S2021010400 S3001001250 Zj=CBNj Z=CBB-1b 2i i a b jjj zc 15學(xué)校課堂 初始單純形表 迭代 次數(shù) 基變 量 CB x1 X2s1s2 S3 b 比值 50 100 00 0 1 S1011100300 S2021010400

8、S3001001250 Zj=CBNj Z=0 2i i a b jjj zc 16學(xué)校課堂 初始單純形表 迭代 次數(shù) 基變 量 CB x1 X2s1s2 S3 b 比值 50 100 00 0 1 S1011100300 S2021010400 S3001001250 Zj=CBNj 00000 Z=0 2i i a b jjj zc 000 0 0 17學(xué)校課堂 初始單純形表 迭代 次數(shù) 基變 量 CB x1 X2s1s2 S3 b 比值 50100000 1 S1011100300 S2021010400 S3001001250 Zj=CBNj 00000 Z=0 100 000 2i

9、i a b jjj zc 50 18學(xué)校課堂 初始單純形表 迭代 次數(shù) 基變 量 CB x1 X2s1s2 S3 b 比值 50 100 00 0 1 S1011100300 S2021010400 S3001001250 Zj=CBNj 00000 Z=0 50100000 2i i a b jjj zc 1 250 1 400 1 300 19學(xué)校課堂 初始單純形表 迭代 次數(shù) 基變 量 CB x1 X2s1s2 S3 b 比值 50 100 00 0 2 S1011100300 S2021010400 x201001250 Zj=CBNj Z=CBB-1b 2i i a b jjj zc

10、 1 250 1 400 1 300 20學(xué)校課堂 初始單純形表 迭代 次數(shù) 基變 量 CB x1 X2s1s2 S3 b 比值 50 100 00 0 2 S1011100300 S2021010400 x210001001250 Zj=CBNj Z=CBB-1b 2i i a b jjj zc 1 250 1 400 1 300 21學(xué)校課堂 初始單純形表 迭代 次數(shù) 基變 量 CB x1 X2s1s2 S3 b 比值 50 100 00 0 2 S1011100300 S2021010400 x210001001250 Zj=CBNj Z=CBB-1b 2i i a b jjj zc 1

11、 250 1 400 1 300 22學(xué)校課堂 初始單純形表 迭代 次數(shù) 基變 量 CB x1 X2s1s2 S3 b 比值 50 100 00 0 2 S1011100300 S2021010400 x210001001250 Zj=CBNj Z=CBB-1b 2i i a b jjj zc 1 250 1 400 1 300 23學(xué)校課堂 初始單純形表 迭代 次數(shù) 基變 量 CB x1 X2s1s2 S3 b 比值 50 100 00 0 2 S101010-150 S202001-1150 x2 100 01001250 Zj=CBNj Z=25000 2i i a b jjj zc 2

12、4學(xué)校課堂 初始單純形表 迭代 次數(shù) 基變 量 CB x1 X2s1s2 S3 b 比值 50 100 00 0 2 S101010-150 S202001-1150 x2 100 01001250 Zj=CBNj 010000100 Z=25000 2i i a b jjj zc 25學(xué)校課堂 初始單純形表 迭代 次數(shù) 基變 量 CB x1X2s1s2S3 b 比值 50 100 00 0 2 S101010-150 S202001-1150 x2 100 01001250 Zj=CBNj 010000100 Z=25000 50000-100 2i i a b jjj zc 26學(xué)校課堂

13、初始單純形表 迭代 次數(shù) 基變 量 CB x1X2s1s2S3 b 比值 50 100 00 0 2 S101010-150 S202001-1150 x2 100 01001250 Zj=CBNj 010000100 Z=25000 50000-100 2i i a b jjj zc 27學(xué)校課堂 初始單純形表 迭代 次數(shù) 基變 量 CB x1X2s1s2 S3 b 比值 50 100 00 0 2 S101010-150 S202001-1150 x2 100 01001250 Zj=CBNj 010000100 Z= 25000 50000 -100 2i i a b jjj zc 2

14、150 1 50 28學(xué)校課堂 初始單純形表 迭代 次數(shù) 基變 量 CB x1X2s1s2 S3 b 比值 50 100 00 0 3 S101010-150 S202001-1150 x2 100 01001250 Zj=CBNj 2i i a b jjj zc x1 50 x150 29學(xué)校課堂 初始單純形表 迭代 次數(shù) 基變 量 CB x1x2s1s2 S3 b 比值 50 100 00 0 3 x1501010-150 S202001-1150 x2 100 01001250 Zj=CBNj 2i i a b jjj zc 30學(xué)校課堂 初始單純形表 迭代 次數(shù) 基變 量 CB x1x

15、2s1s2 S3 b 比值 50 100 00 0 3 x1501010-150 S202001-1150 x2 100 01001250 Zj=CBNj 2i i a b jjj zc 31學(xué)校課堂 初始單純形表 迭代 次數(shù) 基變 量 CB x1X2s1s2S3 b 比值 50 100 000 3 x1501010-150 S2000-21150 x2 100 01001250 Zj=CBNj Z= 27500 2i i a b jjj zc 32學(xué)校課堂 初始單純形表 迭代 次數(shù) 基變 量 CB x1X2s1s2S3 b 比值 50 100 000 3 x1501010-150 S2000-21150 x2 100 01001250 Zj=CBNj 5010050050 Z= 27500 2i i a b jjj zc 33學(xué)校課堂 初