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

1、整理課件3.2 線性規(guī)劃問題的基本解整理課件基本概念基本概念： 可行解、可行域、最優(yōu)解、基、基變量、基陣、基本可可行解、可行域、最優(yōu)解、基、基變量、基陣、基本可行解行解整理課件給定一個線性規(guī)劃問題給定一個線性規(guī)劃問題LP 11221 1 max.nnzc xc xc x 1111221121122222112212.1.2.0,0,01.3nnnnmnnmmmns taxaxaxbaxaxaxbaxaxaxbxxx 一、基本概念一、基本概念：整理課件1、可行解、可行解 (a feasible solution)滿足約束條件的滿足約束條件的X稱為線性規(guī)劃問題的稱為線性規(guī)劃問題的可行解可行解;Tn

2、xxxX,21所有可行解的集合稱為所有可行解的集合稱為可行域可行域 (feasible region),使目標(biāo)函數(shù)使目標(biāo)函數(shù)(1.1)達到最大值的可行解稱為達到最大值的可行解稱為最優(yōu)解最優(yōu)解(an optimal solution)。 1122nnmaxz = c x +c x +c x1.1 11112211211222221122121.2. .0,0,01.3nnnnmmmnnmnaxaxaxbaxaxaxbs taxaxaxbxxx 整理課件2、基、基(base)nPPP,21即即,21nPPPA是是A的的m個列向量個列向量,設(shè)設(shè)12,mjjjPPP是線性無關(guān)的是線性無關(guān)的，如果如果j

3、mjjPPP,21則稱則稱jmjjPPP,211 . 1max2211nnxcxcxcz11112211211222221122121.2. .0,0,01.3nnnnmmmnnmna xa xa xba xaxaxbs taxaxaxbxxx為基向量。為基向量。記約束方程系數(shù)矩陣記約束方程系數(shù)矩陣A的列向量是的列向量是整理課件3、基變量、基變量(basic variables)構(gòu)成線性規(guī)劃問題的一組基向量構(gòu)成線性規(guī)劃問題的一組基向量,設(shè)設(shè)12,jjjmPPP則對應(yīng)的變量則對應(yīng)的變量 12,jjjmxxx稱為稱為基變量基變量，其余的向量稱為其余的向量稱為非基向量非基向量，其余的變量稱為其余的變

4、量稱為非基變量非基變量(non-basic-variable)，稱為稱為基基或或基陣基陣(basic matrix)。矩陣矩陣 12 ,jjjmBPPP整理課件約束方程約束方程A的系數(shù)矩陣為：的系數(shù)矩陣為：321001001002001 A12345321001001002001 其其 列列 向向 量量 ：，PPPPP分別是變量分別是變量54321,xxxxx的系數(shù)向量。的系數(shù)向量。例例12153maxxxz12314525123432184212,0 xxxxxxxxxxxx 整理課件543,PPP向量組向量組 是線性無關(guān)組是線性無關(guān)組 1345 ,BP P P是此問題的一個基是此問題的一個

5、基其中其中 為基變量，而為基變量，而 是非基變量。是非基變量。345,xxx12,xx2153maxxxz0,12241823543215241321xxxxxxxxxxxx321001001002001 A整理課件向量組向量組 是線性無關(guān)組是線性無關(guān)組542,PPP321001001002001 A2153maxxxz0,12241823543215241321xxxxxxxxxxxx245,xxx 是基變量，是基變量， 2245 ,BP P P是此問題的一個基是此問題的一個基31,xx而而 是非基變量。是非基變量。整理課件（2）設(shè)）設(shè)B是是A的一個的一個m階子矩陣，則階子矩陣，則B是線性規(guī)

6、劃問題是線性規(guī)劃問題的基陣，當(dāng)且僅當(dāng)?shù)幕?，?dāng)且僅當(dāng)B是可逆陣是可逆陣 。0B（3）基的個數(shù)）基的個數(shù)Cnm注：注：（1）基不一定唯一）基不一定唯一100200100100123A2153maxxxz0,12241823543215241321xxxxxxxxxxxx整理課件4、基解、基解 jmjjPPPB,21 12 ,BjjjmXxxxNX現(xiàn)令所有的非基變量都等于現(xiàn)令所有的非基變量都等于0，即，即0 NX設(shè)設(shè) 是線性規(guī)劃問題是線性規(guī)劃問題LP的一基陣，的一基陣，表示基變量向量，表示基變量向量，表示非基變量向量。表示非基變量向量。整理課件則約束方程則約束方程(1.2)可化為：可化為： 112

7、21 4 .jjjjjmjmBPxPxPxbBXb1 BXB b100 B bX它是一個它是一個m個變量個變量m個方程組成的線性方程組，個方程組成的線性方程組，B又是可逆又是可逆陣，從而得出陣，從而得出(1.4)的唯一解的唯一解得出約束方程得出約束方程(1.2)至少含有至少含有n-m個個0元的解元的解 稱之為相應(yīng)于基稱之為相應(yīng)于基B的一個的一個基本解或基解基本解或基解(a basic solution)。整理課件5、基可行解、基可行解設(shè)設(shè) 是對應(yīng)于基陣是對應(yīng)于基陣B的一個基解，的一個基解，100 B bX0010bBX010bBX如果如果 則稱則稱 為一個為一個基本可行解或基可行基本可行解或基

8、可行解解.(a basic feasible solution)；相應(yīng)的基相應(yīng)的基B也稱為也稱為可行基可行基(feasible base)。整理課件在上例在上例1中，中，對應(yīng)于對應(yīng)于 的基解為的基解為是一個基可行解，是一個基可行解，對應(yīng)于對應(yīng)于 的基解為的基解為而不是基可行解。而不是基可行解。 10 0 18 4 12 ,TX1B2B 20 9 0 46 。,X思考題：試列出例思考題：試列出例1中問題的所有基解、基可行解。中問題的所有基解、基可行解。2153maxxxz0,12241823543215241321xxxxxxxxxxxx100200100100123A整理課件 注：給定線性規(guī)劃

9、問題注：給定線性規(guī)劃問題LP，其基可行，其基可行解的數(shù)目是有限個，不會超過解的數(shù)目是有限個，不會超過 。 圖圖1給出了線性規(guī)劃問題的解的關(guān)系。給出了線性規(guī)劃問題的解的關(guān)系。mnC可行解基解基可行解圖圖1非可行解整理課件121231245223504260014 max,jZxxxxxxxxxj11322120(P)4041BB ，P P、，12BB和和12BB、1.設(shè)線性規(guī)劃設(shè)線性規(guī)劃取基取基分別指出分別指出對應(yīng)的基變量和非基變量，對應(yīng)的基變量和非基變量，是不是可行基是不是可行基求出基本解，并說明求出基本解，并說明整理課件1若線性規(guī)劃無最優(yōu)解則其可行域無界。若線性規(guī)劃無最優(yōu)解則其可行域無界。（ ）2凡基本解一定是可行解。凡基本解一定是可行解。 （ ）2判斷題（你認為下列命題是否正確，判斷題（你認為下列命題是否正確，對正確的打?qū)φ_的打“”；錯誤的打；錯誤的打“”。）。）3線性規(guī)劃的最優(yōu)解一定是基本最優(yōu)解。（線性規(guī)劃的最優(yōu)解一定是基本最優(yōu)解。（ ）4線性規(guī)劃的最優(yōu)解是可行解。（線性規(guī)劃的最優(yōu)解是可行解。（ ）5可行解是基本解。（可行解是基本解。（ ）整理課件3.線性規(guī)劃可行域的頂點一定是（線性規(guī)劃可行域的頂點一定是（ ）。）。A.基本可行解基本可行解B.非基本解非基本解C.非可行解非可行解D.最優(yōu)解最優(yōu)解4. X是線性規(guī)劃的基本可行