【文章內(nèi)容簡(jiǎn)介】 + x2 + x3 + x4 x5= 4 xi ≥ 0, i = 1,2,…,5 2 理論分支 例題 1 對(duì)于約束方程組 x1 x2 + 2 x3 = 1 x1 + x2 + x3 =1 x1 , x2 , x3 ≥0 系數(shù)矩陣 基 退化解 非退化解 2 理論分支 例 題 2 對(duì)于約束方程組 系數(shù)矩陣 基 退化解 非退化解 x1 + x2 x3 = 1 x1 x2 x3 = 2 x1 , x2 , x3 ≥0 6 線性規(guī)劃解的性質(zhì) 設(shè) Ｄ 是 n 維歐氏空間的一個(gè)點(diǎn)集 ， 連接Ｄ中任意兩點(diǎn) X、 Y 的線段仍在Ｄ內(nèi) ， 則稱 Ｄ 為凸集 。 凸集的 概念 X Y X Y ● ● ● ● ● ● 圖中每個(gè)點(diǎn)都是由 n 維坐標(biāo)表示的，這個(gè) n 維坐標(biāo)與 向量是一致的，而向量是與線性規(guī)劃問題的解是一致的。 =1 =u =1u 1≥ u ≥0 x y z Z= x+ ( y x) u = ( 1 u) x+ u y 任一點(diǎn)的表示方法 令 X Y 之間的相對(duì)長(zhǎng)度為 1， X Z之間的長(zhǎng)度站整個(gè)長(zhǎng)度 的 比例為 U， 6 線性規(guī)劃問題解的性質(zhì) 設(shè) 集合 R是 n 維線性空間 ， 如果其中任意兩點(diǎn) X 和 Y ，如果對(duì)于任意 1 ≥ u ≥ 0， 都有 ( 1 u ) x + u y 仍然屬于 R ， 則可說 R 為凸集 。 （ 1） 基本概念 凸集數(shù)學(xué)表述 頂點(diǎn) 設(shè) 集合 R 是一個(gè)凸集 ， Z 是這個(gè)集合中中的一點(diǎn) ， 如果在此集合中找不到兩個(gè)不同的點(diǎn) X 和 Y ， 使 Z = ( 1 u ) x+ u y ， 1 ≥ u ≥0 成立 ， 則可說 Z 點(diǎn)為 S凸集的頂點(diǎn) 。 x1 x2 x1 x2 頂點(diǎn)的直觀解釋 （ 2） 線性規(guī)劃問題解的性質(zhì)定理 定理 1 線性規(guī)劃問題的可行解集 R 為凸集 。 首先 ， 線性規(guī)劃問題的可行解 X=(x1 , x2 , … , xn)是一個(gè) n 維向量 ， 它可以看成是一個(gè)由 n 個(gè)坐標(biāo)構(gòu)成的點(diǎn) 。 線性規(guī)劃問題可能有不止一個(gè)可行解 ,也就是說可能有很多個(gè)這樣的點(diǎn) ， 這些點(diǎn)就構(gòu)成了一個(gè)集合 ， 很顯然這個(gè)集合就是一個(gè) n 維歐氏空間 ， 我們要證明的結(jié)論 ， 就是這個(gè)集合是一個(gè) 凸集 。 X Y 線性規(guī)劃問題所有的解 所構(gòu)成的集合 證明這個(gè)問題的基本思路 也就是，已知 X 和 Y 是線性規(guī)劃問題的兩個(gè)不同的解，要證明這 兩個(gè)解的連線中間的任意一個(gè)點(diǎn)也是線性規(guī)劃問題的解，也就是 ( 1 u) x+ u y 也是一個(gè)解，也就是它也屬于集合 R。 證明過程 設(shè)任意 X 和 Y ∈ R， 目標(biāo)是要證明對(duì)于任意 1≥ u ≥0, Z= u X + ( 1 u) Y ∈ R A Z = A （ u X + ( 1 u) Y） 因?yàn)?X、 Y ∈ R， 所以 X ≥0， Y ≥0， 而且 AX = B AY = B = A uX + A ( 1 u) Y = u B + ( 1 u) B = B 定理 2 凸集的頂點(diǎn)對(duì)應(yīng)于基本可行解 。 首先 ， 線性規(guī)劃問題的可行解 X=(x1 , x2 , … , xn)是一個(gè) n 維向量 ， 它可以看成是一個(gè)由 n 個(gè)坐標(biāo)構(gòu)成的點(diǎn) 。 線性規(guī)劃問題可能有不止一個(gè)可行解 ,也就是說可能有很多個(gè)這樣的點(diǎn) ， 這些點(diǎn)就構(gòu)成了一個(gè)集合 ， 上面已經(jīng)證明這個(gè)集合是一個(gè) 凸集 。 此定理說 ， 這個(gè)凸集的頂點(diǎn)是基本可行解 , 同樣基本可行解也必是這個(gè)凸集的頂點(diǎn) . 首先還要理解基本可行解的含義 , 基本可行解是線性規(guī)劃問題系數(shù)矩陣一個(gè)特定的基所對(duì)應(yīng)的可行解 .基本解首先是一個(gè)可行解 , 然后它還是一個(gè)基本解 . 可行域 R 必要性的證明 也就是已知線性規(guī)劃問題的一個(gè)解 X 是這個(gè)線性規(guī)劃問題可行解集合 (可行域 ) R 的頂點(diǎn) ,要證明 X 是此線性規(guī)劃問題的一個(gè)基本可行解 . 簡(jiǎn)單地加以分析 在這個(gè)問題中 ,已經(jīng)知道了 X 線性規(guī)劃問題可行解集合 (可行域 ) R 的頂點(diǎn) , 那么 X 就肯定是一個(gè)可行解了 . 關(guān)鍵是要如何再證明這個(gè)可行解是一個(gè)基本解了 . 可行域 R X 設(shè) X = (x1 , x2 , … , xn)T ,中有 K 個(gè)分量大于 0 , 不失一般性可以設(shè)其前 K 個(gè)分量大于 0 , 則 X =(x1 , x2 , … , xK , 0 , 0 , … , 0 )T 那么約束條件 AX=B 中 AX 的就可以寫成 AX= ??????mnmmnnaaaaaaaaa????212222111211??????x1 X2 … xK 0 … 0 = (P1, P2,…,P k) x1 X2 … xK x1 X2 … xK 0 … 0 ????????????mnnnmkmmkkaaaaaaaaaaaa?????????21212222111211= P1 P2 … Pk … Pn ????????????mnnnmkmmkkaaaaaaaaaaaa?????????21212222111211= x1 X2 … xK 0 … 0 = x1 P1+ x2 P2+…+ xk Pk 最終整理結(jié)果就是： 那么 ,如果我們能夠證明 P1,P2,…,Pk 是線性無(wú)關(guān)的 , 則由 P1,P2,…,Pk 列向量所構(gòu)成的矩陣 = x1 P1+ x2 P2+…+ xk Pk x1 X2 … xK 0 … 0 ????????????AX= mnnnmkmmkkaaaaaaaaaaaa?????????21212222111211P1 P2 … Pk … Pn 中的 K個(gè)列向量是線性無(wú)關(guān)的 ,則說明必然存在一個(gè) K階子矩陣 BK是非奇異矩陣 ,也就說明 BK是一個(gè)基 .這樣 ,也就證明了 X是一個(gè)基本可行解 . 所以整個(gè)問題就轉(zhuǎn)化為證明向量 P1,P2,…,Pk 是線性無(wú)關(guān)的 ， 用反證法來(lái)證明這個(gè)問題。 ????????????mkmmkkaaaaaaaaa?????212222111211P1 P2 … Pk 假設(shè) P1,P2,…,Pk 是線性相關(guān)的 , 則必然存在 K個(gè)不全為 0的數(shù)， y1, y2, … , yk,使 y1 P1+ y2 P2+…+ yk Pk =0 成立。 = x1 P1+ x2 P2+…+ xk Pk x1 X2 … xK 0 … 0 ????????????AX= mnnnmkmmkkaaaaaaaaaaaa?????????21212222111211P1 P2 … Pk … Pn 假設(shè) 是線性相關(guān)的 則必然存在 個(gè)不全為 的數(shù)， …使 成立。????????? y1 P1+ y2 P2+…+ yk Pk= (P1, P2,…,P k) y1 y2 … yK (P1, P2,…,P k,0, …0 ) y1 y2 … yK 0 … 0 = = AY 而 =0 我們?cè)賮?lái)看向量 X X =(x1 , x2 , … , xK , 0 , 0 , … , 0 ) T 因?yàn)? X 是可行解，所以 X中的每個(gè)分量 x1 , x2 , … , xK 都必然大于 0 ， 那么就可以取足夠小的數(shù) ε， 使 X+ εY＞ 0， X—εY＞ 0 因?yàn)?AX=B , AY=0那么 A（ X+ εY ） = A X+ ε A Y =B+0=B 同理 A（ X— εY ） = B 這說明 X+ εY ， X—εY都分別是線性規(guī)劃問題的解。 而 X=1/2（ X+ εY） + 1/2 （ X—εY） 這說明點(diǎn) X 是點(diǎn)（ X+ εY） 和點(diǎn) （ X—εY） 的中間點(diǎn)。是中間點(diǎn)就不是頂點(diǎn)。這與已知相互矛盾，說明假設(shè)不成立。也就證明向量 P1,P2,…,Pk 是線性無(wú)關(guān)的，進(jìn)而證明了解 X 是線性規(guī)劃問題的一個(gè)基本可行解。 充分性的證明留給同志們自己課下學(xué)習(xí) 定理 3 如果可行域 R 有界 ， 則線性規(guī)劃問題的目標(biāo)函數(shù)一定在其頂點(diǎn)處達(dá)到最大值 。 有界可行域 R 無(wú)界可行域 R A B C D 用反證法來(lái)證明這個(gè)問題 ， 設(shè) X（ 1） ， X（ 2） …… X（ h） 是可行域的頂點(diǎn) ， 而 X（ 0） 不是可行域的頂點(diǎn) ， 但目標(biāo)函數(shù)卻在 X（ 0） 處達(dá)到了最大值 。 有界可行域 R X（ 1） X（ 2） X（ H） …… 首先我們來(lái)證明 X（ 0） 可用其他頂點(diǎn)進(jìn)行線性表示 。 即 X（ 0） =u1 X（ 1） +u2 X（ 2） +… + uh X（ h） ,而且u1 +u2 +… + uh =1 X（ 0） 首先我們來(lái)證明 X（ 0） 可用其他頂點(diǎn)進(jìn)行線性表示 。 即 X（ 0） =u1 X（ 1） +u2 X（ 2）+… + uh X（ h） ,而且 u1 +u2 +… + uh =1 有界可行域 R X（ I） X（ L） X（ Y） …… X（ 0） 我們以二維可行域?yàn)槔齺?lái)證明這個(gè)問題