【正文】 0x0,xx6xx3xxxm a x z21212121????????2421552。這些頂點的凸組合也是最優(yōu)值。若有最優(yōu)解，也必在頂點上達到。 證明反證法：若 X*不為頂點且是 LP的最優(yōu)解，由推論 2， 因此，令 則 由此得到 即目標函數(shù)在頂點處也達到最優(yōu)值。 推論 2：若可行解集 D是有界的凸集，則 D中任意一點 x，都可表示成 D的頂點的凸組合。 線性規(guī)劃的基本定理 定理 13 線性規(guī)劃問題的可行解集 D中的點 x是頂點的充分必要條件是： x是基礎(chǔ)可行解。 頂點與基可行解相對應(yīng) 線性規(guī)劃的基本定理 定理 13 線性規(guī)劃問題的可行解集 D中的點 x是頂點的充分必要條件是： x是基礎(chǔ)可行解。當(dāng) k=m時，恰構(gòu)成一個基，從而X為基可行解，當(dāng) k＜ m時，則一定可以從其余的列向量中取出 mk個與 P1, P2,…, P k 構(gòu)成極大無關(guān)組，對應(yīng)的解恰為 X，有定義它是基礎(chǔ)可行解。 證明： 必要性 由基礎(chǔ)解的定義可知：非零分量所對應(yīng)的系數(shù)列向量為基向量，故系數(shù)矩陣 A的列向量是線性無關(guān)。令 X*=α X1 +(1 α )X2 ,則 AX*=A[α X1 +(1 α )X2 ]= α A X1 +(1 α ) AX2 =αb +(1 α )b=b, 且 α X1 +(1 α )X2 ≥0。任意 X1 ,X2 ∈ D,有 A X1=b, X1 ≥0。（即連接線性規(guī)劃問題任意兩個可行解的線段上的點仍然是可行解。 即： 若 D中的任意兩點 x(1),x(2) ，不存在數(shù) ? （ 0 ? 1） 使得 x= ? x(1)+(1 ?)x(2) 成立，則稱 x為凸集 D的一個頂點。 即： 若 D中的任意兩點 x(1),x(2) ∈ D，存在0?1 使得 x= ? x(1)+(1 ?)x(2) ∈ D,則稱 D為凸集 例 1. 6（凸集） 例（非凸集） 例 :X= ? X(1) +(1 ?)X(2),為什么？ X1 X2 X(1) X(2) X 圖（ 17） 例 X1 X2 X(1) X(2) X(2) X(1) X(2) 圖（ 17） X 例 X1 X2 X(1) X(2) X X(1) X(2) y= ?(X(1) X(2) ) (0 ? 1) X=X(2)+y = X(2)+ ?(X(1) X(2) ) = ? X(1) +(1 ?)X(2) 圖（ 17） 例 X1 X2 X(1) X(2) X X(2) X(1) X(2) 圖（ 17） X=X(2)+y = X(2)+ ?(X(1) X(2) ) = ? X(1) +(1 ?)X(2) y= ?(X(1) X(2) ) (0 ? 1) 兩個基本概念： 凸組合 (Convex bination)： 設(shè) x(1),x(2) …..x (k)是 n維歐氏空間中的 k個點，若 存在數(shù) u1,u2,….u k 且0≤ui ≤1 (i=1,2,…k), ? ui =1, 使得 x= u1 x(1)+ u2 x(2) +…..+ uk x(k) 成立，則稱 x為 x(1),x(2) …..x (k)的凸組合 。 為了理解基礎(chǔ)解 .基礎(chǔ)可行解 .最優(yōu)解的概念， 用下列例子說明： 標準型為： x1 + 2x2 ≤ 8 4x1 ≤ 16 4x2 ≤ 12 x1， x2≥0 max z = 2 x1 + 3 x2 +0x3 + 0x4 + 0 x5 x1 + 2x2 +x3 = 8 4x1 x4 = 16 4x2 + x 5 = 12 x1, x2 , x3 ,x4 ,x5 ≥0 ???????????????????????????????????????????????????????100,010,001,402,04154321 PPPPP例 max z = 2 x1 + 3 x2 ),(100010001543 PPPB ????????????基 基為： 基變量為： x3 ， x4 ， x5 ， 非基變量為 x1 ， x2 。 mnCmnC a11 a12 …. a 1m b1 B= a21 a22 …. a 2m b = b2 …………………………… ………… am1 am2 …. a mm bn a11 a12 a1m b1 a1m+1 a1n a21 x1+ a22 x2 + ….+ a 2m xm= b2 a2m+1 xm+1 …. a2n xn …………………………… ………… am1 am2 amm bn amm+1 amn 或 ???????nmjjjmjjj xPbxP11021 ???? ?? nmm xxx ?令 XB 是對應(yīng)這個基的基變量 XB= Tmxxx ),( 21 ?TmxxxX )0,0,( 21 ??? 為 基解 。 ⊙ 與基礎(chǔ)可行解對應(yīng)的基，稱為 可 行基 。 ?基礎(chǔ)解 .基礎(chǔ)可行解 .可行基 ⊙ 對于某一特定的基 B，非基變量取 0值的解，稱為基礎(chǔ)解。 ?基礎(chǔ)解 .基礎(chǔ)可行解 .可行基 ⊙ 對于某一特定的基 B，非基變量取 0值的解，稱為基礎(chǔ)解。 ⊙ 與基向量 Pj 相對應(yīng)的變量 xj就稱為 基變量，其余的就稱為非基變量。 ?基、基向量、基變量 ⊙ 設(shè) r(A)=m,并且 B是 A的 m 階非奇異 的子矩陣（ det(B)0),則稱矩陣 B為線性規(guī)劃問題的一個基。 ?基、基向量、基變量 ⊙ 設(shè) r(A)=m,并且 B是 A的 m 階非奇異 的子矩陣（ det(B)0),則稱矩陣 B為線性規(guī)劃問題的一個基。 ⊙ 滿足目標函數(shù)（ 19）的可行解 X， 稱為線性規(guī)劃的問題最優(yōu)解。 ?解、可行解、最優(yōu)解 ⊙ 滿足約束條件（ 110）的 X，稱為 線性規(guī)劃問題的解。 Max S = CX （ 19） . AX=b （ 110） X ? 0 （ 111） ?解、可行解、最優(yōu)解 ⊙ 滿足約束條件（ 110）的 X，稱為 線性規(guī)劃問題的解。 解的情況： ?有可行解 ⊙ 有唯一最優(yōu)解 ⊙ 有無窮最優(yōu)解 ⊙ 無界解 (無 最 優(yōu)解） ?無可行解 線性規(guī)劃問題解的概念 線性規(guī)劃標準型的矩陣形式： Max S = CX （ 19