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

1、單純形法求解動態(tài)演示v在求解lp問題時,有人給出了圖解法,但對多維變量時,卻無能為力,于是v美國數(shù)學家gbdantgig(丹捷格)發(fā)明了一種“單純形法”的代數(shù)算法，尤其是方便于計算機運算。這是運籌學史上最輝煌的階段。1學校課堂);,(21ncccctnxxx),(21x一、關(guān)于標準型解的若干基本概念一、關(guān)于標準型解的若干基本概念2學校課堂基矩陣基矩陣 示例:012233. .23max32143214321xxxxxxxtsxxxxz000032020001010 x1 x2x4x3001300321=目標函數(shù)約束條件行列式0基矩陣x1,x2,x3為基變量為基變量,x4為非基變量為非基變量3學

2、校課堂 xt = (xb , xn) t =（ b-1b , 0) t z = cb b-1b 4學校課堂 為了矩陣形求逆計算方便，一般將b轉(zhuǎn)化為單位矩陣。5學校課堂將線性規(guī)劃問題化成標準型。將線性規(guī)劃問題化成標準型。找出或構(gòu)造一個找出或構(gòu)造一個m階單位矩陣作為初始可行基，建立初始單純形表。階單位矩陣作為初始可行基，建立初始單純形表。計算各非基變量計算各非基變量xj的檢驗數(shù)的檢驗數(shù) j=cj-cbpj ，若所有，若所有 j0，則問題已得到，則問題已得到最優(yōu)解，停止計算，否則轉(zhuǎn)入下步。最優(yōu)解，停止計算，否則轉(zhuǎn)入下步。在大于在大于0的檢驗數(shù)中，若某個的檢驗數(shù)中，若某個 k所對應(yīng)的系數(shù)列向量所對應(yīng)的

3、系數(shù)列向量pk0，則此問題，則此問題是無界解，停止計算，否則轉(zhuǎn)入下步。是無界解，停止計算，否則轉(zhuǎn)入下步。根據(jù)根據(jù)max j j0= k原則，確定原則，確定xk為換入變量為換入變量(進基變量進基變量)，再按，再按 規(guī)則計算：規(guī)則計算： =minbi/aik| aik0=bl/ aik 確定確定xbl為換出變量。建立新的為換出變量。建立新的單純形表，此時基變量中單純形表，此時基變量中xk取代了取代了xbl的位置。的位置。以以aik為主元素進行迭代，把為主元素進行迭代，把xk所對應(yīng)的列向量變?yōu)閱挝涣邢蛄浚此鶎?yīng)的列向量變?yōu)閱挝涣邢蛄?，即aik變?yōu)樽優(yōu)?，同列中其它元素為，同列中其它元素為0，轉(zhuǎn)第，

4、轉(zhuǎn)第 步。步。 2、單純形法的計算步驟、單純形法的計算步驟 6學校課堂線性規(guī)劃的例子子0,40025005 . 2516002234max211212121xxxxxxxxxz7學校課堂線性規(guī)劃-標準化v引入變量：s1,s2,s3121231211222312123max501000003002400250,0zxxsssxxsxxsxsx x s s s8學校課堂25040030032121100100101200111sssxx3020102100150maxsssxxz提取系數(shù)，填入表格：s.t.3212100010050maxsssxxzc向量cbcnxbxn基bn jjjzc zj=

5、cbnj每個非基變量的檢驗值9學校課堂初始單純形表迭代次數(shù)基變量cbx1x2s1s2s3b比值1zj=cbnjz=cbb-1biijbajjjzc 10學校課堂初始單純形表迭代次數(shù)基變量cbx1x2s1s2s3b比值1zj=cbnjz=cbb-1biijbajjjzc 目標函數(shù)系數(shù)區(qū)目標函數(shù)系數(shù)區(qū)約束條件系數(shù)區(qū)右端系數(shù)右端系數(shù)檢驗系數(shù)區(qū)檢驗系數(shù)區(qū)基變量區(qū)基變量區(qū)11學校課堂初始單純形表迭代次數(shù)基變量cbx1x2s1s2s3b比值501000001zj=cbnjz=cbb-1b2iiabjjjzc 12學校課堂初始單純形表迭代次數(shù)基變量cbx1x2s1s2s3b比值501000000111003

6、002101040001001250zj=cbnjz=cbb-1b2iiabjjjzc 13學校課堂初始單純形表迭代次數(shù)基變量cbx1x2s1s2s3b比值501000001111003002101040001001250zj=cbnjz=cbb-1b2iiabjjjzc 14學校課堂初始單純形表迭代次數(shù)基變量cbx1x2s1s2s3b比值501000001s1011100300s2021010400s3001001250zj=cbnjz=cbb-1b2iiabjjjzc 15學校課堂初始單純形表迭代次數(shù)基變量cbx1x2s1s2 s3b比值501000001s1011100300s20210

7、10400s3001001250zj=cbnjz=02iiabjjjzc 16學校課堂初始單純形表迭代次數(shù)基變量cbx1x2s1s2 s3b比值501000001s1011100300s2021010400s3001001250zj=cbnj00000z=02iiabjjjzc 0000017學校課堂初始單純形表迭代次數(shù)基變量cbx1x2s1s2 s3b比值501000001s1011100300s2021010400s3001001250zj=cbnj00000z=01000002iiabjjjzc 5018學校課堂初始單純形表迭代次數(shù)基變量cbx1x2s1s2 s3b比值501000001

8、s1011100300s2021010400s3001001250zj=cbnj00000z=0501000002iiabjjjzc 12501400130019學校課堂初始單純形表迭代次數(shù)基變量cbx1x2s1s2 s3b比值501000002s1011100300s2021010400 x201001250zj=cbnjz=cbb-1b2iiabjjjzc 12501400130020學校課堂初始單純形表迭代次數(shù)基變量cbx1x2s1s2 s3b比值501000002s1011100300s2021010400 x210001001250zj=cbnjz=cbb-1b2iiabjjjzc

9、12501400130021學校課堂初始單純形表迭代次數(shù)基變量cbx1x2s1s2 s3b比值501000002s1011100300s2021010400 x210001001250zj=cbnjz=cbb-1b2iiabjjjzc 12501400130022學校課堂初始單純形表迭代次數(shù)基變量cbx1x2s1s2 s3b比值501000002s1011100300s2021010400 x210001001250zj=cbnjz=cbb-1b2iiabjjjzc 12501400130023學校課堂初始單純形表迭代次數(shù)基變量cbx1x2s1s2 s3b比值501000002s101010-

10、150s202001-1150 x210001001250zj=cbnjz=250002iiabjjjzc 24學校課堂初始單純形表迭代次數(shù)基變量cbx1x2s1s2 s3b比值501000002s101010-150s202001-1150 x210001001250zj=cbnj010000100z=250002iiabjjjzc 25學校課堂初始單純形表迭代次數(shù)基變量cbx1x2s1s2s3b比值501000002s101010-150s202001-1150 x210001001250zj=cbnj010000100z=2500050000-1002iiabjjjzc 26學校課堂初始

11、單純形表迭代次數(shù)基變量cbx1x2s1s2s3b比值501000002s101010-150s202001-1150 x210001001250zj=cbnj010000100z=2500050000-1002iiabjjjzc 27學校課堂初始單純形表迭代次數(shù)基變量cbx1x2s1s2 s3b比值501000002s101010-150s202001-1150 x210001001250zj=cbnj010000100z=2500050000-1002iiabjjjzc 215015028學校課堂初始單純形表迭代次數(shù)基變量cbx1x2s1s2 s3b比值501000003s101010-15

12、0s202001-1150 x210001001250zj=cbnj2iiabjjjzc x150 x15029學校課堂初始單純形表迭代次數(shù)基變量cbx1x2s1s2 s3b比值501000003x1501010-150s202001-1150 x210001001250zj=cbnj2iiabjjjzc 30學校課堂初始單純形表迭代次數(shù)基變量cbx1x2s1s2 s3b比值501000003x1501010-150s202001-1150 x210001001250zj=cbnj2iiabjjjzc 31學校課堂初始單純形表迭代次數(shù)基變量cbx1x2s1s2s3b比值501000003x1501010-150s2000-21150 x210001001250zj=cbnjz=275002iiabjjjzc 32學校課堂初始單純形表迭代次數(shù)基變量cbx1x2s1s2s3b比值501000003x1501010-150s2000-21150 x210001001250zj=cbnj5010050050z=275002iiabjjjzc 33學校課堂初始單純形表迭代次數(shù)基