線性規(guī)劃問(wèn)題的圖解法-四維空間展開(kāi)

1、滿(mǎn)足約束條件的變量的值滿(mǎn)足約束條件的變量的值, 稱(chēng)為稱(chēng)為可行解可行解.所有可行解構(gòu)成的集合稱(chēng)為所有可行解構(gòu)成的集合稱(chēng)為可行域可行域.使目標(biāo)函數(shù)取得最優(yōu)值的可行解使目標(biāo)函數(shù)取得最優(yōu)值的可行解, 稱(chēng)為稱(chēng)為最優(yōu)解最優(yōu)解.不存在可行解的不存在可行解的LP問(wèn)題稱(chēng)該問(wèn)題稱(chēng)該LP問(wèn)題無(wú)解問(wèn)題無(wú)解, 其可域行為其可域行為空集空集.例例1 解下面的解下面的LP問(wèn)題問(wèn)題 max S=50 x1+30 x2 s.t. 4x1+3x2 120 2x1+x2 50 x1, x2 0 x2504030201010203040 x1x2504030201010203040 x12x1+x2 50由由2x1+x2 50 x1

2、 0 x2 0圍成的區(qū)域圍成的區(qū)域x2504030201010203040 x14x1+3x2 120同時(shí)滿(mǎn)足同時(shí)滿(mǎn)足: 2x1+x2 504x1+3x2 120 x1 0 x2 0的區(qū)域的區(qū)域可行域可行域x2504030201010203040 x1O(0,0)Q1(25,0)Q2(15,20)Q3(0, 40)可行域是由約束條件圍成的區(qū)域可行域是由約束條件圍成的區(qū)域,該區(qū)該區(qū)域內(nèi)的每一點(diǎn)都是可行解域內(nèi)的每一點(diǎn)都是可行解, 的全體組成的全體組成問(wèn)題的解集合問(wèn)題的解集合.該問(wèn)題的可行域是由該問(wèn)題的可行域是由O,Q1,Q2, Q3作為作為頂點(diǎn)的頂點(diǎn)的凸多邊形凸多邊形x25040302010102

3、03040 x1目標(biāo)函數(shù)是以目標(biāo)函數(shù)是以s作為作為參數(shù)的一組平行線參數(shù)的一組平行線x2 = s/30-(5/3)x1x2504030201010203040 x1當(dāng)當(dāng)S值不斷增加時(shí)值不斷增加時(shí), 該直線該直線x2 = S/30-(5/3)x1沿著其法線方向向右上方沿著其法線方向向右上方移動(dòng)移動(dòng).x2504030201010203040 x1當(dāng)該直線移到當(dāng)該直線移到Q2點(diǎn)時(shí)點(diǎn)時(shí),s(目目標(biāo)函數(shù)標(biāo)函數(shù))值達(dá)到最大值達(dá)到最大: max s=50*15+30*20=1350此時(shí)最優(yōu)解此時(shí)最優(yōu)解=(15,20)Q2(15,20)可行域可行域目標(biāo)函數(shù)等值線目標(biāo)函數(shù)等值線最優(yōu)解最優(yōu)解64-860 x1x2例

4、例2 解下面的解下面的LP問(wèn)題問(wèn)題max z=x1+3x2s.t. x1+ x26-x1+2x28x1 0, x20滿(mǎn)足約束條件的可行域一般都構(gòu)成凸多邊形滿(mǎn)足約束條件的可行域一般都構(gòu)成凸多邊形.這一事實(shí)可這一事實(shí)可以推廣到更多變量的場(chǎng)合以推廣到更多變量的場(chǎng)合.最優(yōu)解必定能在凸多邊形的某一個(gè)頂點(diǎn)上取得最優(yōu)解必定能在凸多邊形的某一個(gè)頂點(diǎn)上取得,這一事實(shí)這一事實(shí)也可以推廣到更多變量的場(chǎng)合也可以推廣到更多變量的場(chǎng)合.例例1 max S=50 x1+30 x2 s.t. 4x1+3x2 120 2x1+x2 50 x1, x2 0例例1的目標(biāo)函數(shù)由的目標(biāo)函數(shù)由 max s=50 x1+30 x2變成變成

5、: max s=40 x1+30 x2 s.t. 4x1+3x2 120 2x1+x2 50 x1, x2 0 x2504030201010203040 x1x2504030201010203040 x1Q1(25, 0)Q2(15, 20)例例: max s=x1+x2 s.t. -2x1+x2 40 x1-x2 20 x1, x2 0 x2504030201010203040 x1該可行域無(wú)界該可行域無(wú)界,目標(biāo)函數(shù)值可增加目標(biāo)函數(shù)值可增加到無(wú)窮大到無(wú)窮大,稱(chēng)這種情況為無(wú)界解或稱(chēng)這種情況為無(wú)界解或無(wú)最優(yōu)解無(wú)最優(yōu)解.例例: : max s=2x1+3x2 s.t. x1+2x2 8 x1 4 x2 3 -2x1+x2 4 x1, x2 0該問(wèn)題可行域?yàn)榭占搯?wèn)題可行域?yàn)榭占?即無(wú)即無(wú)可行解