1、滿足約束條件的變量的值滿足約束條件的變量的值, 稱為稱為可行解可行解.所有可行解構成的集合稱為所有可行解構成的集合稱為可行域可行域.使目標函數取得最優值的可行解使目標函數取得最優值的可行解, 稱為稱為最優解最優解.不存在可行解的不存在可行解的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圍成的區域圍成的區域x2504030201010203040 x14x1+3x2 120同時滿足同時滿足: 2x1+x2 504x1+3x2 120 x1 0 x2 0的區域的區域可行域可行域x2504030201010203040 x1O(0,0)Q1(25,0)Q2(15,20)Q3(0, 40)可行域是由約束條件圍成的區域可行域是由約束條件圍成的區域,該區該區域內的每一點都是可行解域內的每一點都是可行解, 的全體組成的全體組成問題的解集合問題的解集合.該問題的可行域是由該問題的可行域是由O,Q1,Q2, Q3作為作為頂點的頂點的凸多邊形凸多邊形x25040302010102

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

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