運籌學大學課件1-3線性規(guī)劃解的性質(zhì)文檔

第三節(jié)線性規(guī)劃解的性質(zhì)線性規(guī)劃解的概念凸集及其頂點幾個基本定理的證明繼續(xù)返回線性規(guī)劃問題解的概念標準型可行解:滿足AX=b,X>=0的解X稱為線性規(guī)劃問題的可行解。全部可行解的集合稱為可行域。最優(yōu)解：使目標函數(shù)Z=CX達到最大值的可行解稱為最優(yōu)解。

基：若B是矩陣A中m×m階非奇異子矩陣（|B|≠0），則B是線性規(guī)劃問題的一個基。不妨設(shè)：

,j=1，2，…,m——

基向量。，j=1，2，…,m

——

基變量。,j=m+1,…,n

——

非基變量。線性規(guī)劃問題解的概念

求解

線性規(guī)劃問題解的概念基解：稱上面求出的X解為基解,基解個數(shù)不超過Cnm個基可行解：非負的基解X稱為基可行解,每一個基可行解的非零分量個數(shù)不會超過m個.可行基：對應(yīng)基可行解的基稱為可行基線性規(guī)劃問題解的概念T基變量令可求出：0...21====++nmmxxx

線性規(guī)劃解的關(guān)系圖

非可行解可行解

基可行解

基解線性規(guī)劃問題解的概念

最優(yōu)解？

例：求基解、基可行解、最優(yōu)解。線性規(guī)劃問題解的概念10051045Y20452017Y35005410Y

40550-120N5100-50415N652.5001.517.5Y7540-3022N

2430019Y00

00是否基可行解最優(yōu)解線性規(guī)劃問題解的概念解：

：求基解、基可行解、最優(yōu)解。練習：線性規(guī)劃問題解的概念凸集及其頂點凸集：凸集及其頂點

頂點:若K是凸集，X∈K；若X不能用不同的兩點的線性組合表示為：則X為頂點.

凸集凸集及其頂點定理1:若線性規(guī)劃問題存在可行域,則其可行域:是凸集.

幾個基本定理的證明證明:幾個基本定理的證明{})0,3==XbAXXD

只要驗證X在D中即可

引理：可行解X為基可行解

X的正分量對應(yīng)的系數(shù)列向量線性無關(guān)定理3：若線性規(guī)劃問題有最優(yōu)解，則一定存在一個基可行解是最優(yōu)解。定理2：線性規(guī)劃問題的基可行解X

對應(yīng)于可行域D的頂點。證明：反證法。分兩步。幾點結(jié)論：線性規(guī)劃問題的可行域是凸集。基可行解與可行域的頂點一一對應(yīng)，可行域有有限多個頂點。最優(yōu)解必在頂點上得到。圖解法9—8—7—6—5—4—3—2—1—0x2| | | | | | | | |1 2 3 4 5 6 7 8 9x1x1+2x2

84x1

164x2

16可行域BCDEA可行域為凸集目標函數(shù)不同時等值線的斜率不同最優(yōu)解在頂點產(chǎn)生

目標函數(shù)等值線的斜率最優(yōu)解圖解法9—8—7—6—5—4—3—2—1—0x2| | | | | | | | |1 2 3 4 5 6 7 8 9x1x1+2x2

84x1

164x2

16可行域BCDEA可行域為凸集目標函數(shù)不同時等值線的斜率不同最優(yōu)解在頂點產(chǎn)生

目標函數(shù)等值線的斜率最優(yōu)解圖解法9—8—7—6—5—4—3—2—1—0x2| | | | | | | | |1 2 3 4 5 6 7 8 9x1x1+2x2

84x1

164x2

16可行域BCDEA可行域為凸集目標函數(shù)不同時等值線的斜率不同最優(yōu)解在頂點產(chǎn)生