運(yùn)籌學(xué) 基本可行解的幾何意義

課堂練習(xí)1-2：用圖解法求解下面的線性規(guī)劃按小組分工完成：①畫約束條件1；③畫約束條件2；⑤畫約束條件3；⑦標(biāo)明可行域；⑨目標(biāo)函數(shù)等值線；⑾說明如何得到最優(yōu)解，算出相應(yīng)的目標(biāo)函數(shù)最優(yōu)值。

其他6個小組對應(yīng)講評。1第一步

模型標(biāo)準(zhǔn)化；第二步

按照基本解的定義①

找基（非退化3階方陣）——

多少個？不超過，為什麼？怎麼找？②

確定基變量和非基變量；③

令非基變量為0，解出基變量；④基變量和相應(yīng)非基變量搭配構(gòu)成基本解；2凸集——設(shè)K是n維歐氏空間的一個點(diǎn)集，若任意兩點(diǎn)X（1）∈K，X（2）∈K的連線上的一切點(diǎn)：

αX（1）+（1-α）X（2）∈

K

（0<α<1），則稱K為凸集。

3

頂點(diǎn)——設(shè)K是凸集，XK；若X不能用

X（1）

K，X（2）

K的線性組合表示，即

X≠αX（1）+（1-α）X（2）（0<α<1）則稱X為K的一個頂點(diǎn)（也稱為極點(diǎn)或角點(diǎn)）。

4圖解法—（練習(xí)）

18—16—14—12—10—8—6—4—2—0| | | | | | | | |2 4 6 8 10 12 14 16 18x1x24x1+6x2

482x1+2x2

182x1+x2

16可行域ABCDE1、定義“頂點(diǎn)”的方式有什麼特點(diǎn)？2、這種定義方式在什麼場合運(yùn)用最方便？

討論62、線性規(guī)劃問題解的性質(zhì)定理：

定理1-1

線性規(guī)劃問題的可行解集（即可行域）是凸集。

證明思路：根據(jù)凸集定義，采用直接法證明；具體步驟：①從D中任取兩個不同的點(diǎn)，應(yīng)滿足可行解定義中相應(yīng)的條件；②證明X=αX(1)+(1-α)X(2)∈D(利用①，證明X滿足凸集定義中相應(yīng)的條件)7

定理1-2

線性規(guī)劃幾何理論基本定理若，則X是D的一個頂點(diǎn)的充分必要條件是X為線性規(guī)劃的基本可行解。證明思路：定理1-2是X是D的一個頂點(diǎn)<=>X為LP的基本可行解;

引理是X為LP的基本可行解<=>X的正分量所對應(yīng)的系數(shù)列向量線性無關(guān);從而將問題轉(zhuǎn)化為X是D的一個頂點(diǎn)<=>

X的正分量所對應(yīng)的系數(shù)列向量線性無關(guān)8證明要點(diǎn)：（1）引理:X為LP的基本可行解<=>X的正分量所對應(yīng)的系數(shù)列向量線性無關(guān)必要性→由基本可行解定義直接證得充分性←正分量K個k=m→X=(x1,x2,…,xm,0,…0)T即為基本可行解k<m→補(bǔ)齊得基→退化的基本可行解（2）定理1-2

（反證法）

9必要性→第一步：將反證法假設(shè)和已知條件具體化；

第二步：尋找X附近的屬于D的兩個點(diǎn)X（1）和X（2）（技巧：將第一步得到的兩個式子相加減得到）；

第三步：選取適當(dāng)?shù)摩耍杀ＷC

X=1/2X（1）+1/2X（2），從而與“X是頂點(diǎn)”矛盾。10充分性←第一步：將反證法假設(shè)具體化，明確正分量；第二步：由大前提X是可行解,找出不全為0的一組數(shù)；第三步：得到P1,P2,…，Pm線性相關(guān)的結(jié)論，與已知條件矛盾；11定理1-3

若可行域非空有界，則線性規(guī)劃問題的目標(biāo)函數(shù)一定可以在可行域的頂點(diǎn)上達(dá)到最優(yōu)值。證明思路：首先可行域非空有界就肯定有最優(yōu)解本定理要證明的是設(shè)在非頂點(diǎn)X處取得最優(yōu)值，則存在頂點(diǎn)X（1）和X（2）也取得相同的最優(yōu)值。12定理1-4

若目標(biāo)函數(shù)在k個點(diǎn)處達(dá)到最優(yōu)值（k≥2）,則在這些頂點(diǎn)的凸組合上也達(dá)到最優(yōu)值.證明思路：根據(jù)凸組合的定義直接證得結(jié)論。13

課后小組討論2：（1）讀懂證明，理清思路，寫出從最羅嗦的證明過渡到最簡潔的證明過程（加上邊注——段落大意）

可以作為小實踐選題?。?）P70習(xí)題1-4（①檢查是否屬于可行域；②檢查相應(yīng)的Pj是否線性相關(guān)）14上述4個定理的一些有意義的啟示：

LP的可行域一定是凸集，但是凸集不一定成為LP的可行域，而非凸集一定不會是LP的可行域。（為什麼？能舉例說明嗎？）線性規(guī)劃的基本可行解和可行域的頂點(diǎn)是