改進(jìn)單純形法課件

單純形法的矩陣描述1單純形法的矩陣描述1設(shè)線性規(guī)劃問題可以用如下矩陣形式表示：目標(biāo)函數(shù)maxz=CX

約束條件AX≤b非負(fù)條件X≥02設(shè)線性規(guī)劃問題可以用如下矩陣形式表示：2

將該線性規(guī)劃問題的約束條件加入松弛變量后，得到標(biāo)準(zhǔn)型：maxz=CX+0Xs

AX+IXs=bX，X

s≥0其中，I是m×m單位矩陣。3將該線性規(guī)劃問題的約束條件加入松弛變量后，得到

若以Xs為基變量，并標(biāo)記成XB，可將系數(shù)矩陣(A，I)分為(B，N)兩塊。B是基變量的系數(shù)矩陣，N是非基變量的系數(shù)矩陣。并同時將決策變量也分為兩部分：

相應(yīng)地可將目標(biāo)函數(shù)系數(shù)C分為兩部分：CB和CN，分別對應(yīng)于基變量XB和非基變量XN，并且記作:

C=（CB,CN）4若以Xs為基變量，并標(biāo)記成XB，可若經(jīng)過迭代運算后，可表示為：相應(yīng)有:5若經(jīng)過迭代運算后，可表示為：5線性規(guī)劃問題可表示為：6線性規(guī)劃問題可表示為：6將（2-2）式移項及整理后得到：7將（2-2）式移項及整理后得到：7令非基變量=0，由上式得到：8令非基變量=0，由上式得到：8（1）非基變量的系數(shù)表示為：9（1）非基變量的系數(shù)表示為：9（2）θ規(guī)則表示為：RHS值表示選用>0的分量換入變量的系數(shù)向量10（2）θ規(guī)則表示為：10（3）單純形表與矩陣表示的關(guān)系:11（3）單純形表與矩陣表示的關(guān)系:11單純形表中的數(shù)據(jù):基變量非基變量等式右邊系數(shù)矩陣檢驗數(shù)12單純形表中的數(shù)據(jù):基變量非基變量等式右邊系數(shù)小結(jié)1）掌握矩陣的運算；2）理解基矩陣的作用；3）了解矩陣運算與單純表的關(guān)系。13小結(jié)1）掌握矩陣的運算；13改進(jìn)單純形法求解線性規(guī)劃問題的關(guān)鍵是計算B-1。以下介紹一種比較簡便的計算B-1的方法。14改進(jìn)單純形法求解線性規(guī)劃問題的關(guān)鍵是計算B-1。14

設(shè)mn系數(shù)矩陣為A，求其逆矩陣時，可先從第1列開始。以a11為主元素,進(jìn)行變換：15設(shè)mn系數(shù)矩陣為A，求其逆矩陣時，可先從第1列開始然后構(gòu)造含有（1）列，而其他列都是單位列的矩陣可得到：16然后構(gòu)造含有（1）列，而其他列都是單位列的矩陣可得到：16而后以第2列的為主元素，進(jìn)行變換:然后構(gòu)造含有（2）列，而其他列都是單位列的矩陣:可得到:17而后以第2列的為主元素，進(jìn)行變換:然后構(gòu)造含有（重復(fù)以上的步驟，直到獲得:可見，En…E2E1=A-1。用這方法可以求得單純形法的基矩陣B的逆矩陣B-1

18重復(fù)以上的步驟，直到獲得:可見，En…E2E1=A-1。18以例1為例進(jìn)行計算。19以例1為例進(jìn)行計算。19第1步：確定初始基，初始基變量;確定換入，換出變量（1）確定初始基和初始基變量：

（2）計算非基變量的檢驗數(shù)，確定換入變量。20第1步：確定初始基，初始基變量;確定換入，換出變量（1）確定(3)確定換出變量表示選擇>0的元素（4）基變換計算將新的基單位矩陣。計算：21(3)確定換出變量表示選擇>0的元素（4）基變換計算21（5）計算非基變量的系數(shù)矩陣（6）計算RHS22（5）計算非基變量的系數(shù)矩陣22第1步計算結(jié)束后的結(jié)果:計算非基變量的檢驗數(shù)，確定換入變量：23第1步計算結(jié)束后的結(jié)果:計算非基變量的檢驗數(shù)，確定換入變量：確定換出變量：由此得到新的基：24確定換出變量：由此得到新的基：24計算RHS第2步計算結(jié)束后的結(jié)果：25計算RHS第2步計算結(jié)束后的結(jié)果：25第3步：計算非基變量（x3,x5）的檢驗數(shù):確定換出變量:26第3步：計算非基變量（x3,x5）的檢驗數(shù):確定換出變量:新的基:計算B的逆矩陣：27新的基:計算B的逆矩陣：27計算非基變量的檢驗數(shù):得到最優(yōu)解：目標(biāo)函數(shù)的最優(yōu)值為：28計算非基變量的檢驗數(shù):得到最優(yōu)解：目標(biāo)函數(shù)的最優(yōu)值為：28此課件下載可自行編輯修改，供參考！部分內(nèi)容來源于網(wǎng)絡(luò)，如有侵權(quán)請與我聯(lián)系刪除！完整編輯ppt此課件下載可自行編輯修改，供參考！完整編輯ppt單純形法的矩陣描述30單純形法的矩陣描述1設(shè)線性規(guī)劃問題可以用如下矩陣形式表示：目標(biāo)函數(shù)maxz=CX

約束條件AX≤b非負(fù)條件X≥031設(shè)線性規(guī)劃問題可以用如下矩陣形式表示：2

將該線性規(guī)劃問題的約束條件加入松弛變量后，得到標(biāo)準(zhǔn)型：maxz=CX+0Xs

AX+IXs=bX，X

s≥0其中，I是m×m單位矩陣。32將該線性規(guī)劃問題的約束條件加入松弛變量后，得到

若以Xs為基變量，并標(biāo)記成XB，可將系數(shù)矩陣(A，I)分為(B，N)兩塊。B是基變量的系數(shù)矩陣，N是非基變量的系數(shù)矩陣。并同時將決策變量也分為兩部分：

相應(yīng)地可將目標(biāo)函數(shù)系數(shù)C分為兩部分：CB和CN，分別對應(yīng)于基變量XB和非基變量XN，并且記作:

C=（CB,CN）33若以Xs為基變量，并標(biāo)記成XB，可若經(jīng)過迭代運算后，可表示為：相應(yīng)有:34若經(jīng)過迭代運算后，可表示為：5線性規(guī)劃問題可表示為：35線性規(guī)劃問題可表示為：6將（2-2）式移項及整理后得到：36將（2-2）式移項及整理后得到：7令非基變量=0，由上式得到：37令非基變量=0，由上式得到：8（1）非基變量的系數(shù)表示為：38（1）非基變量的系數(shù)表示為：9（2）θ規(guī)則表示為：RHS值表示選用>0的分量換入變量的系數(shù)向量39（2）θ規(guī)則表示為：10（3）單純形表與矩陣表示的關(guān)系:40（3）單純形表與矩陣表示的關(guān)系:11單純形表中的數(shù)據(jù):基變量非基變量等式右邊系數(shù)矩陣檢驗數(shù)41單純形表中的數(shù)據(jù):基變量非基變量等式右邊系數(shù)小結(jié)1）掌握矩陣的運算；2）理解基矩陣的作用；3）了解矩陣運算與單純表的關(guān)系。42小結(jié)1）掌握矩陣的運算；13改進(jìn)單純形法求解線性規(guī)劃問題的關(guān)鍵是計算B-1。以下介紹一種比較簡便的計算B-1的方法。43改進(jìn)單純形法求解線性規(guī)劃問題的關(guān)鍵是計算B-1。14

設(shè)mn系數(shù)矩陣為A，求其逆矩陣時，可先從第1列開始。以a11為主元素,進(jìn)行變換：44設(shè)mn系數(shù)矩陣為A，求其逆矩陣時，可先從第1列開始然后構(gòu)造含有（1）列，而其他列都是單位列的矩陣可得到：45然后構(gòu)造含有（1）列，而其他列都是單位列的矩陣可得到：16而后以第2列的為主元素，進(jìn)行變換:然后構(gòu)造含有（2）列，而其他列都是單位列的矩陣:可得到:46而后以第2列的為主元素，進(jìn)行變換:然后構(gòu)造含有（重復(fù)以上的步驟，直到獲得:可見，En…E2E1=A-1。用這方法可以求得單純形法的基矩陣B的逆矩陣B-1

47重復(fù)以上的步驟，直到獲得:可見，En…E2E1=A-1。18以例1為例進(jìn)行計算。48以例1為例進(jìn)行計算。19第1步：確定初始基，初始基變量;確定換入，換出變量（1）確定初始基和初始基變量：

（2）計算非基變量的檢驗數(shù)，確定換入變量。49第1步：確定初始基，初始基變量;確定換入，換出變量（1）確定(3)確定換出變量表示選擇>0的元素（4）基變換計算將新的基單位矩陣。計算：50(3)確定換出變量表示選擇>0的元素（4）基變換計算21（5）計算非基變量的系數(shù)矩陣（6）計算RHS51（5）計算非基變量的系數(shù)矩陣22第1步計算結(jié)束后的結(jié)果:計算非基變量的檢驗數(shù)，確定換入變量：52第1步計算結(jié)束后的結(jié)果:計算非基變量的檢驗數(shù)，確定換入變量：確定換出變量：由此得到新的基：53確定換出變量：由此得到新的基：24計算RHS第2步計算結(jié)束后的結(jié)果：54計算RHS第2步計算結(jié)束后的結(jié)果：25第3步：計算非基變量（x3,x5