【正文】 ???????????????????????????100,010,001,402,04154321 PPPPP例 max z = 2 x1 + 3 x2 ),(100010001543 PPPB ????????????基 基為： 基變量為： x3 ， x4 ， x5 ， 非基變量為 x1 ， x2 。 251421341241628xxxxxxx???????令 非基變量 x1 =0， x2 =0 ， 基變量 x3 =8， x4 = 16， x5 =12 X=(0,0,8,16,12)T為基解 ， 且為基可行解 解的集合： 非可行解 可行解 解的集合： 基礎解 解的集合： 可行解 基礎解 基礎可行解 解的集合： 可行解 基礎解 基礎最優(yōu)解 基礎可行解 第二節(jié)：線性規(guī)劃解的性質（幾何意義） 凸集 （ Convex set） 概念： 設 D是 n維歐氏空間 的一個點集，若 D中的任意兩點 x(1),x(2)的連 線上的一切點 x仍在 D中，則稱 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)： 設 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)的凸組合 。 兩個基本概念： 頂點 (Extreme opint)： 設 D是凸集 , 若 D中的點 x 不能成為 D中任何線段上的內點，則稱 x為凸集 D的頂點。 即： 若 D中的任意兩點 x(1),x(2) ，不存在數(shù) ? （ 0 ? 1） 使得 x= ? x(1)+(1 ?)x(2) 成立，則稱 x為凸集 D的一個頂點。 例： 多邊形上的點是頂點 圓周上的點都是頂點 線性規(guī)劃的基本定理 定理 11 線性規(guī)劃問題的可行解集是凸集。（即連接線性規(guī)劃問題任意兩個可行解的線段上的點仍然是可行解。 ) 證明 線性規(guī)劃問題的可行解的集合為 D={X|AX=b,X≥0}。任意 X1 ,X2 ∈ D,有 A X1=b, X1 ≥0。 A X2=b, X2 ≥0。令 X*=α X1 +(1 α )X2 ,則 AX*=A[α X1 +(1 α )X2 ]= α A X1 +(1 α ) AX2 =αb +(1 α )b=b, 且 α X1 +(1 α )X2 ≥0。 故 X* ∈ D 線性規(guī)劃的基本定理 定理 12 線性規(guī)劃問題的可行解 x=（ x1, x2,…, x n )T為基礎可行解的充分必要條件是： x的非零分量所對應的系數(shù)矩陣 A的列向量是線性無關。 證明： 必要性 由基礎解的定義可知：非零分量所對應的系數(shù)列向量為基向量，故系數(shù)矩陣 A的列向量是線性無關。 （ 86） 充分性 若向量 P1, P2,…, P k 線性無關，則必有 k≤m。當 k=m時，恰構成一個基，從而X為基可行解，當 k＜ m時，則一定可以從其余的列向量中取出 mk個與 P1, P2,…, P k 構成極大無關組，對應的解恰為 X，有定義它是基礎可行解。 線性規(guī)劃的基本定理 定理 13 線性規(guī)劃問題的可行解集 D中的點 x是頂點的充分必要條件是： x是基礎可行解。 頂點與基可行解相對應 線性規(guī)劃的基本定理 定理 13 線性規(guī)劃問題的可行解集 D中的點 x是頂點的充分必要條件是： x是基礎可行解。 推論 1：可行解集 D中的頂點個數(shù)是有限的。 線性規(guī)劃的基本定理 定理 13 線性規(guī)劃問題的可行解集 D中的點 x是頂點的充分必要條件是： x是基礎可行解。 推論：可行解集 D中的頂點個數(shù)是有限的。 推論 2：若可行解集 D是有界的凸集，則 D中任意一點 x，都可表示成 D的頂點的凸組合。 例： x1 x2 X(1) X(2) X(3) x x1 x2 X(1) X(2) X(3) x X’ X’= ? X(1) +(1 ?)X(3) (0 ? 1) x1 x2 X(1) X(2) X(3) X X’ X = ?X’ +(1 ?)X(2) (0 ? 1) 因為 x’是 X(1) ， X(3)連線上的一點，故 x’ = ? X(1) +(1 ?)X(3) (0 ? 1) 又因為 x是 X ’ ， X(2)連線上的一點，故 X = ? X’ +(1 ?)X(2) (0 ? 1) X = ? （ ? X(1) +(1 ?)X(3)） +(1 ?)X(2) = ? ? X(1) +(1 ?)X(2) +(1 ?) ? X(3) =u1X(1) +u2X(2) +u3X(3) 其中 (0ui1) 且 u1 +u2 +u3 = ? ? +(1 ?)+(1 ?) ? =1 x1 x2 X(1) X(2) X(3) X’ X =u1X(1) +u2X(2) +u3X(3) 線性規(guī)劃的基本定理 定理 14 若可行域 D有界，則線性規(guī)劃問題的最優(yōu)解，必定在 D的頂點上達到。 證明反證法：若 X*不為頂點且是 LP的最優(yōu)解，由推論 2， 因此，令 則 由此得到 即目標函數(shù)在頂點處也達到最優(yōu)值。 ??????? kiiikiii xX11)( 1,0,* ???},2,1|m a x { )()( kicxcx im ???)(1)(1)(1)(* mkimikiiikiii CxCxCxxCCX ?????????? ???)()()( **,* mmm CxCXCxCXCxCX ??? ，故又說明 1：若可行解集 D無界，則線性規(guī)劃問題可能有最優(yōu)解，也可能無最優(yōu)解。若有最優(yōu)解，也必在頂點上達到。 說明 2：有時目標函數(shù)也可能在多個頂點上達到最優(yōu)值。這些頂點的凸組合也是最優(yōu)值。（有無窮多最優(yōu)解） 事實上，若 是目標函數(shù)達到最大值的頂點， ， ， 于是， )()2()1( , kXXX ???????? ki iiiki iXX1)(1* 1,0, ???.*1*1)(1)(* ZZCXXCCX ki ikiiikiii ???? ??? ??? ???kiCXZ i ,2,1,)(* ??? 練習題 已知線性規(guī)劃問題： 求其所有基解，基可行解及最優(yōu)解。 0x0,xx6xx3xxxm a x z21212121????????242155