單純形法基本原理及實例演示

1、單純形法基本原理及實例演示第1頁，共34頁，2022年，5月20日，3點18分，星期二線性規(guī)劃問題標(biāo)準(zhǔn)型的矩陣形式： Max Z = CX （a） s.t. AX=b （ b） X 0 （c） a11 a12 . a1n b1 A= a21 a22 . a2n b = b2 am1 am2 . amn bm一、關(guān)于標(biāo)準(zhǔn)型解的若干基本概念第2頁，共34頁，2022年，5月20日，3點18分，星期二基矩陣 示例:000032020001010 x1x2x4x3001300321=目標(biāo)函數(shù)約束條件行列式0基矩陣X1,x2,x3為基變量,x4為非基變量第3頁，共34頁，2022年，5月20日，3點18

2、分，星期二因為B為基, 故有 XB +B-1N XN = B-1b， 解得可行解XB=B-1b-B-1NXN，代入目標(biāo)函數(shù)Z， Z = CB B-1b + (CN- CB B-1N ) XN 令非基變量XN = 0 ，則有 XT = (XB , XN) T =（ B-1b , 0) T Z = CB B-1bAX=bZ = CX設(shè) A=（B , N）（B為一個基，即線性無關(guān)向量組R(A)=R(B)） XT= (XB , XN) T （XB 為基變量，XN為非基變量） C= (CB , CN) （CB 為基變量系數(shù)，CN為非基變量系數(shù)）則有： Z= (CB , CN) (XB , XN) T=

3、CB XB+CN XN AX =（ B , N） (XB , XN) T = B XB+ N XN = b1、單純形法原理：第4頁，共34頁，2022年，5月20日，3點18分，星期二Z = CB B-1b + (CN- CB B-1N ) XN如果CN- CB B-1N小于0，無論XN取任何大于0值，只會讓Z變小，因此我們可以通過CN- CB B-1N來判斷Z取得是不是最大值。如果存在一個CN- CB B-1N大于0，則說明Z的值會隨著XN增大而增大，說明Z有調(diào)整的余地。定理一：若某個基本可行解所對應(yīng)的檢驗向量CN- CB B-1N =0第19頁，共34頁，2022年，5月20日，3點18分

4、，星期二初始單純形表迭代次數(shù)基變量CBx1X2s1s2S3b比值501000002S1011100300S2021010400 x201001250Zj=CBNjZ=CBB-1b可行解XB=B-1b-B-1NXN=0第20頁，共34頁，2022年，5月20日，3點18分，星期二初始單純形表迭代次數(shù)基變量CBx1X2s1s2S3b比值501000002S1011100300S2021010400 x210001001250Zj=CBNjZ=CBB-1b第21頁，共34頁，2022年，5月20日，3點18分，星期二初始單純形表迭代次數(shù)基變量CBx1X2s1s2S3b比值501000002S1011

5、100300S2021010400 x210001001250Zj=CBNjZ=CBB-1b第22頁，共34頁，2022年，5月20日，3點18分，星期二初始單純形表迭代次數(shù)基變量CBx1X2s1s2S3b比值501000002S1011100300S2021010400 x210001001250Zj=CBNjZ=CBB-1b第23頁，共34頁，2022年，5月20日，3點18分，星期二初始單純形表迭代次數(shù)基變量CBx1X2s1s2S3b比值501000002S101010-150S202001-1150 x210001001250Zj=CBNjZ=25000第24頁，共34頁，2022年，

6、5月20日，3點18分，星期二初始單純形表迭代次數(shù)基變量CBx1X2s1s2S3b比值501000002S101010-150S202001-1150 x210001001250Zj=CBNj010000100Z=25000第25頁，共34頁，2022年，5月20日，3點18分，星期二初始單純形表迭代次數(shù)基變量CBx1X2s1s2S3b比值501000002S101010-150S202001-1150 x210001001250Zj=CBNj010000100Z=2500050000-100第26頁，共34頁，2022年，5月20日，3點18分，星期二初始單純形表迭代次數(shù)基變量CBx1X2s

7、1s2S3b比值501000002S101010-150S202001-1150 x210001001250Zj=CBNj010000100Z=2500050000-100第27頁，共34頁，2022年，5月20日，3點18分，星期二初始單純形表迭代次數(shù)基變量CBx1X2s1s2S3b比值501000002S101010-150S202001-1150 x210001001250Zj=CBNj010000100Z=2500050000-100第28頁，共34頁，2022年，5月20日，3點18分，星期二初始單純形表迭代次數(shù)基變量CBx1X2s1s2S3b比值501000003S101010-1

8、50S202001-1150 x210001001250Zj=CBNjx150 x150第29頁，共34頁，2022年，5月20日，3點18分，星期二初始單純形表迭代次數(shù)基變量CBx1x2s1s2S3b比值501000003x1501010-150S202001-1150 x210001001250Zj=CBNj第30頁，共34頁，2022年，5月20日，3點18分，星期二初始單純形表迭代次數(shù)基變量CBx1x2s1s2S3b比值501000003x1501010-150S202001-1150 x210001001250Zj=CBNj第31頁，共34頁，2022年，5月20日，3點18分，星期二初始單純形表迭代次數(shù)基變量CBx1X2s1s2S3b比值501000003x1501010-150S2000-21150 x210001001250Zj=CBNjZ=27500第32頁，共34頁，2022年，5月20日，3點18分，星期二初始單純形表迭代次數(shù)基變量CBx1X2s1s2S3b比值501000003x1501010-150S2000-21150 x210001001250Zj=CBNj5010050050Z=27500第33頁，共34頁，2022年，5月20日，3點18分，星期