線性規(guī)劃問題的可行域

1、精品課程運(yùn)籌學(xué)2.1 2.1 線性規(guī)劃問題的可行域線性規(guī)劃問題的可行域2.2 2.2 線性規(guī)劃問題的最優(yōu)解線性規(guī)劃問題的最優(yōu)解精品課程運(yùn)籌學(xué)2.1 2.1 線性規(guī)劃問題的可行域線性規(guī)劃問題的可行域考慮標(biāo)準(zhǔn)形式的考慮標(biāo)準(zhǔn)形式的LP問題問題 0.minxbAxtsxcTnmmnnRARbRcRx , 0,|xbAxRxDn設(shè)設(shè)nmmA ,)(秩秩精品課程運(yùn)籌學(xué)定義定義1.2.1 Syx )1( 就就稱稱S是是一一個(gè)個(gè)凸凸集集. 凸集凸集凸集凸集不是凸集不是凸集極點(diǎn)極點(diǎn)精品課程運(yùn)籌學(xué)定理定理1.2.1 0,| xbAxRxDn是凸集是凸集. 證證 任任 取取Dyx ,，yxw)1( ， 其其 中中1

2、 , 0 . 由于由于0 x，0 y，故，故0 w. 又又bAx ，bAy ，故，故 bAyAxAw )1( 即即Dw . 精品課程運(yùn)籌學(xué)定理定理1.2.2 任意多個(gè)凸集的交還是凸集任意多個(gè)凸集的交還是凸集. . 證證 如果如果x和和y是是iS中的兩個(gè)點(diǎn)，則中的兩個(gè)點(diǎn)，則 x和和 y必必屬于每一個(gè)屬于每一個(gè)iS，因此它們的凸組合也在每一，因此它們的凸組合也在每一個(gè)個(gè)iS里，從而也在里，從而也在iS里里. 定義定義1.2.2 給定給定1Rb 及非零向量及非零向量nRa ，稱集合，稱集合 |bxaRxHTn 是是nR中中的的一一個(gè)個(gè)超超平平面面. 精品課程運(yùn)籌學(xué)|bxaRxHTn |bxaRxHT

3、n 超平面超平面 是凸集是凸集. H由超平面由超平面 產(chǎn)生了兩個(gè)產(chǎn)生了兩個(gè)閉半空間閉半空間 H都是凸集都是凸集. 精品課程運(yùn)籌學(xué)由于凸集的交還是凸集，因而滿足一組線性等式由于凸集的交還是凸集，因而滿足一組線性等式 pibxaiTi, 1, 與一組線性不等式與一組線性不等式 qppibxaiTi , 1,的的全全體體向向量量x的的集集合合也也是是凸凸集集. （這這里里p或或 q可可以以是是零零.） 定義定義1.2.3 稱稱 , 1,;, 1,|qppibxapibxaRxSiTiiTin 為為多面凸集多面凸集. 精品課程運(yùn)籌學(xué)非空有界的多面凸集稱為非空有界的多面凸集稱為凸多面體凸多面體. 0,|

4、 xbAxRxDn是多面凸集是多面凸集. 定義定義1.2.4 設(shè)設(shè)S為為凸凸集集，Sx .若若對對任任何何Sy ，Sz ，zy ，以以及及任任何何10 ，都都有有 zyx)1( 則則稱稱x為為凸凸集集S的的一一個(gè)個(gè)頂頂點(diǎn)點(diǎn)(極極點(diǎn)點(diǎn)). 頂頂點(diǎn)點(diǎn)精品課程運(yùn)籌學(xué)設(shè)設(shè) c為為nE中中的的一一個(gè)個(gè)凸凸集集，nEd ，0 d，若若對對任任一一Cx 及及0 ， 均均有有Cdx ， 則則稱稱d是是C的的一一個(gè)個(gè)方方向向(direction). 顯顯然然若若d是是C的的方方向向，0 ， 則則dd 1也也是是C的的方方向向. 如如果果一一個(gè)個(gè)方方向向不不能能表表示示成成兩兩個(gè)個(gè)方方向向的的正正線線性性組組合合

5、，即即當(dāng)當(dāng))0,(212211 ddd時(shí)時(shí)，必必有有21dd ， 就就稱稱d是是C的的極極方方向向(extreme direction). 精品課程運(yùn)籌學(xué)定定理理(凸凸多多面面體體的的表表示示) 設(shè)設(shè) 0,| xbAxxD的的所所有有極極點(diǎn)點(diǎn)為為kxx,1， 極極方方向向?yàn)闉閘dd,1， 則則Dx 當(dāng)當(dāng)且且僅僅當(dāng)當(dāng)存存在在一一組組i 與與j ，使使?jié)M滿足足 1, 1, 0, 1, 0111 kiijiljjjkiiiljkidxx 精品課程運(yùn)籌學(xué)2.2 2.2 線性規(guī)劃問題的最優(yōu)解線性規(guī)劃問題的最優(yōu)解(1)(1)兩個(gè)變量線性規(guī)劃問題的圖解法兩個(gè)變量線性規(guī)劃問題的圖解法例例1.2.1 解線性規(guī)劃

6、解線性規(guī)劃 0, 052222.max2121212121xxxxxxxxtsxxz1x2x01A2A3A4A2221 xx3 z5 . 1 z0 z521 xx2221 xxD Tx4 , 1 精品課程運(yùn)籌學(xué)4 z2 z0 z21,AA1x2x01A2A3A4A2221 xx521 xx2221 xxD 0, 052222.max2121212121xxxxxxxxtsxxz2124minxxz 精品課程運(yùn)籌學(xué)例例1.2.2 解線性規(guī)劃解線性規(guī)劃1x2x0 0, 0331.2min21212121xxxxxxtsxxz121 xxAB3321 xx212xxz D精品課程運(yùn)籌學(xué)從圖解法的幾何

7、直觀容易得到下面兩個(gè)重要結(jié)論：從圖解法的幾何直觀容易得到下面兩個(gè)重要結(jié)論：線性規(guī)劃的可行區(qū)域線性規(guī)劃的可行區(qū)域D是若干個(gè)半平面的是若干個(gè)半平面的 交集，交集， 它形成了一個(gè)有界的或無界的凸它形成了一個(gè)有界的或無界的凸 多邊形多邊形.對于給定的線性規(guī)劃問題，如果它有最優(yōu)對于給定的線性規(guī)劃問題，如果它有最優(yōu) 解，最優(yōu)解總可以在解，最優(yōu)解總可以在D的某個(gè)頂點(diǎn)上達(dá)到的某個(gè)頂點(diǎn)上達(dá)到. . 精品課程運(yùn)籌學(xué)111xa212xannxa1121xannxa211xam22xamnmnxa 1b2bmb(2)(2)基本可行解及線性規(guī)劃基本定理基本可行解及線性規(guī)劃基本定理bAx nmmA ,)(秩秩精品課程運(yùn)籌

8、學(xué) 1b2bmbBBxNNx),(NBA NBxxxbAx bxxNBNB bNxBxNB 精品課程運(yùn)籌學(xué) 1b2bmbBBBxExBxB 1NNxB1 bBNxBBxBNB111 bBNxBxNB11 11bB 21bB mbB1 1Bx2BxmBxNBNxBbBx11 0 Nx令令精品課程運(yùn)籌學(xué)11bB 21bB mbB1 1Bx2BxmBx 01bBxbBxB1 0 Nx基本解基本解01 bB若若0 x則則x基本可行解基本可行解B可行基可行基精品課程運(yùn)籌學(xué)定義定義1.2.5設(shè)設(shè)B是秩為是秩為 m的約束矩陣的約束矩陣nmRA 中的一個(gè)中的一個(gè) m階滿秩子方陣，則稱階滿秩子方陣，則稱B為一個(gè)

9、為一個(gè)基基(或或基陣基陣). B中中m個(gè)線性無關(guān)的列向量稱為個(gè)線性無關(guān)的列向量稱為基向量基向量，變量，變量 x中與之對應(yīng)的中與之對應(yīng)的 m個(gè)分量稱為個(gè)分量稱為基變量基變量，其余的分，其余的分量稱為量稱為非基變量非基變量.令所有的非基變量取值為零，令所有的非基變量取值為零，得到的解得到的解 01bBxxxNB，稱為相應(yīng)于，稱為相應(yīng)于 B的的基本解基本解.當(dāng)當(dāng)01 bB時(shí)，稱基本解時(shí)，稱基本解 x為為基本可行基本可行解解，這時(shí)對應(yīng)的基，這時(shí)對應(yīng)的基B稱為稱為可行基可行基. 精品課程運(yùn)籌學(xué) 5 , 4 , 3 , 2 , 1, 052222.min52142132121jxxxxxxxxxxtsxx

10、zj 100110102100112A 1000100011BTx)5 , 2 , 2 , 0 , 0(1 基本可行解基本可行解可行基可行基精品課程運(yùn)籌學(xué) 5 , 4 , 3 , 2 , 1, 052222.min52142132121jxxxxxxxxxxtsxxzj 100110102100112A不可行解不可行解不是可行基不是可行基 1010110022BTx)6 , 3 , 0 , 0 , 1(2 精品課程運(yùn)籌學(xué)定理定理1.2.31.2.3證證：不不妨妨設(shè)設(shè)x的的前前 k個(gè)個(gè)分分量量為為正正分分量量，即即 Tkxxx)0 , 0 ,(1 ，kjxj, 1, 0 若若x是是基基本本可可行

11、行解解，則則取取正正值值的的變變量量必必定定是是基基變變量量，它它們們所所對對應(yīng)應(yīng)的的約約束束矩矩陣陣A中中的的列列向向量量kAA,1是是基基向向量量，故故必必線線性性無無關(guān)關(guān). 精品課程運(yùn)籌學(xué)反反之之，若若kAA,1線線性性無無關(guān)關(guān)，則則必必有有mk .由由于于 x是是可可行行解解，有有bxA ，故故有有 kjjjbAx1.若若mk ，則則),(1kAAB 就就是是一一個(gè)個(gè)基基，x為為B所所對對應(yīng)應(yīng)的的基基本本可可行行解解；若若mk ，因因?yàn)闉閙A )(秩秩，則則一一定定可可以以從從其其余余的的kn 個(gè)個(gè)列列向向量量中中再再挑挑選選出出km ， 不不妨妨設(shè)設(shè)為為mkAA,1 ，使使kAA,1

12、，mkAA,1 構(gòu)構(gòu)成成基基 B，易易知知 x為為相相應(yīng)應(yīng)于于基基B的的基基本本可可行行解解. 精品課程運(yùn)籌學(xué)定理定理1.2.41.2.4 證證 充充分分性性 設(shè)設(shè)x是是可可行行域域 D 的的頂頂點(diǎn)點(diǎn)， 我我們們?nèi)匀栽O(shè)設(shè)它它的的前前k個(gè)個(gè)分分量量取取正正值值，這這時(shí)時(shí)其其對對應(yīng)應(yīng)的的列列kAA,1必必定定是是線線性性無無關(guān)關(guān)的的.事事實(shí)實(shí)上上， 如如果果它它們們相相關(guān)關(guān)， 則則存存在在非非零零向向量量Tkyyy)0 , 0 ,(1 使使得得 kjjjAy10 精品課程運(yùn)籌學(xué)于于是是對對任任一一正正實(shí)實(shí)數(shù)數(shù) 都都有有 kjjjjbAyx1)( kjjjjbAyx1)( 當(dāng)當(dāng)取取yxx 1，yxx

13、 2時(shí)時(shí)總總有有bAxAx 21.因因?yàn)闉閗jxj, 1, 0 ，當(dāng)當(dāng)0 取取的的充充分分小小時(shí)時(shí)有有0, 021 xx， 故故有有DxDx 21,.由由于于0 y， 從從而而21xx ，然然而而 212121xxx 精品課程運(yùn)籌學(xué)這這與與x是是可可行行域域 D 的的頂頂點(diǎn)點(diǎn)矛矛盾盾， 故故kAA,1線線性性無無關(guān)關(guān)，從從而而x是是基基本本可可行行解解. 必必要要性性 設(shè)設(shè)x是是基基本本可可行行解解，設(shè)設(shè)它它的的前前k個(gè)個(gè)分分量量取取正正值值.假假定定存存在在DxDx 21,，21xx 及及10 ，使使 21)1(xxx 這這里里Tnxxx),(1111 ，Tnxxx),(2212 .當(dāng)當(dāng)1

14、kj時(shí)時(shí)，因因?yàn)闉? jx，01 jx，02 jx，故故有有021 jjxx.于于是是由由bAxAx 21可可得得 精品課程運(yùn)籌學(xué) kjjjjAxx1210)(精品課程運(yùn)籌學(xué)一個(gè)一個(gè)LP問題，如果它的所有基本可行解都是非問題，如果它的所有基本可行解都是非退化的，就說該問題是退化的，就說該問題是非退化非退化的，否則說它是的，否則說它是退退化化的的. 非退化非退化 退化退化 唯一的一個(gè)可行基唯一的一個(gè)可行基 可由不止一個(gè)可行基得到可由不止一個(gè)可行基得到 基本可行解基本可行解 0.minxbAxtsxcT個(gè)個(gè)可可行行基基mnc精品課程運(yùn)籌學(xué)定理定理1.2.51.2.5一個(gè)標(biāo)準(zhǔn)形式的一個(gè)標(biāo)準(zhǔn)形式的LP問題問題(1.2.1)，若有可行解，則，若有可行解，則至少有一個(gè)基本可行解至少有一個(gè)基本可行解. 精品課程運(yùn)籌學(xué) kjjjA10 精品課程運(yùn)籌學(xué)易易知知 bAAxxA 00)( 精品課程運(yùn)籌學(xué)精品課程運(yùn)籌學(xué)定理定理1.2.61.2.6若標(biāo)準(zhǔn)形式的若標(biāo)準(zhǔn)形式的LP問題問題(1.2.1)有有限的最優(yōu)值，有有限的最優(yōu)值，則一定存在一個(gè)基本可行解是最優(yōu)解則一定存在一個(gè)基本可行解是最優(yōu)解. （若標(biāo)準(zhǔn)形式的（若標(biāo)準(zhǔn)形式的LP問題的目標(biāo)函數(shù)有有限的最問題的目標(biāo)函數(shù)有有限的最優(yōu)值，則必可在某個(gè)基本可行解處達(dá)到優(yōu)值，則必可在某個(gè)基本可行解處達(dá)到. ）精品課程運(yùn)籌