單純形法基本原理及實(shí)例演示

1、單純形法基本原理及實(shí)例演示第1頁(yè)，共34頁(yè)，2022年，5月20日，3點(diǎn)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頁(yè)，共34頁(yè)，2022年，5月20日，3點(diǎn)18分，星期二基矩陣 示例:000032020001010 x1x2x4x3001300321=目標(biāo)函數(shù)約束條件行列式0基矩陣X1,x2,x3為基變量,x4為非基變量第3頁(yè)，共34頁(yè)，2022年，5月20日，3點(diǎn)18

2、分，星期二因?yàn)锽為基, 故有 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為一個(gè)基，即線性無關(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頁(yè)，共34頁(yè)，2022年，5月20日，3點(diǎn)18分，星期二Z = CB B-1b + (CN- CB B-1N ) XN如果CN- CB B-1N小于0，無論XN取任何大于0值，只會(huì)讓Z變小，因此我們可以通過CN- CB B-1N來判斷Z取得是不是最大值。如果存在一個(gè)CN- CB B-1N大于0，則說明Z的值會(huì)隨著XN增大而增大，說明Z有調(diào)整的余地。定理一：若某個(gè)基本可行解所對(duì)應(yīng)的檢驗(yàn)向量CN- CB B-1N =0第19頁(yè)，共34頁(yè)，2022年，5月20日，3點(diǎn)18分

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

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

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

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

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