線性規(guī)劃問題的圖解法-四維空間展開

1、滿足約束條件的變量的值滿足約束條件的變量的值, 稱為稱為可行解可行解.所有可行解構(gòu)成的集合稱為所有可行解構(gòu)成的集合稱為可行域可行域.使目標函數(shù)取得最優(yōu)值的可行解使目標函數(shù)取得最優(yōu)值的可行解, 稱為稱為最優(yōu)解最優(yōu)解.不存在可行解的不存在可行解的LP問題稱該問題稱該LP問題無解問題無解, 其可域行為其可域行為空集空集.例例1 解下面的解下面的LP問題問題 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同時滿足同時滿足: 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)的每一點都是可行解域內(nèi)的每一點都是可行解, 的全體組成的全體組成問題的解集合問題的解集合.該問題的可行域是由該問題的可行域是由O,Q1,Q2, Q3作為作為頂點的頂點的凸多邊形凸多邊形x25040302010102

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

4、例2 解下面的解下面的LP問題問題max z=x1+3x2s.t. x1+ x26-x1+2x28x1 0, x20滿足約束條件的可行域一般都構(gòu)成凸多邊形滿足約束條件的可行域一般都構(gòu)成凸多邊形.這一事實可這一事實可以推廣到更多變量的場合以推廣到更多變量的場合.最優(yōu)解必定能在凸多邊形的某一個頂點上取得最優(yōu)解必定能在凸多邊形的某一個頂點上取得,這一事實這一事實也可以推廣到更多變量的場合也可以推廣到更多變量的場合.例例1 max S=50 x1+30 x2 s.t. 4x1+3x2 120 2x1+x2 50 x1, x2 0例例1的目標函數(shù)由的目標函數(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該可行域無界該可行域無界,目標函數(shù)值可增加目標函數(shù)值可增加到無窮大到無窮大,稱這種情況為無界解或稱這種情況為無界解或無最優(yōu)解無最優(yōu)解.例例: : max s=2x1+3x2 s.t. x1+2x2 8 x1 4 x2 3 -2x1+x2 4 x1, x2 0該問題可行域為空集該問題可行域為空集,即無即無可行解