第二章線性規劃§2.1凸集與凸函數凸集設V是實數域R上的線性空間（或稱為向量空間），若V上定義著正定對稱雙線性型g（g稱為內積），則V稱為（對于g的）內積空間或歐幾里德空間（有時僅當V是有限維時，才稱為歐幾里德空間）。具體來說，g是V上的二元實值函數，滿足如下關系：（1）g(x,y)=g(y,x)；（2）g(x+y,z)=g(x,z)+g(y,z)；（3）g(kx,y)=kg(x,y)；（4）g(x,x)>=0，而且g(x,x)=0當且僅當x=0時成立例2.1.2超球||x||≤r為凸集凸集的性質

X1X2X(1)X(2)X圖（1-7）X1X2X(1)X(2)-X(2)X(1)-X(2)圖（1-7）XX1X2X(1)X(2)XX(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)圖（1-7）X1X2X(1)X(2)X-X(2)X(1)-X(2)圖（1-7）X=X(2)+y=X(2)+(X(1)-X(2))=X(1)+(1-)X(2)y=(X(1)-X(2))(0<<1)極點極點凸函數凸函數的例子凸函數的幾何性質凸函數的幾何性質上圖對于一元凸函數f(x),可以發現,位于函數曲線上方的圖形是凸集.事實上這一結論對于多元函數也是成立的,而且是充要條件,即有下面的定理.定理:設f(x)是定義在凸集

上的函數,則f(x)是凸函數的充要條件是其上圖epi(f)為凸集,其中epi(f)=證明:作業凸函數的性質凸函數的判斷凸函數的判斷一階條件二階條件凸規劃定理2.1.5證明(思路)§2.2線性規劃的標準型

與基本概念線性規劃的一般形式線性規劃的標準型矩陣-向量形式的標準型矩陣-向量形式的標準型可行域為凸集一般形式轉化為標準型基本概念基本概念基本概念§2.3線性規劃的基本定理有可行解→有基可行解有最優解→有最優的基可行解單純形方法的思路找出一基可行解(極點)若其不是最優,找到一個相鄰極點新的目標函數值不大于原目標函數值經過有限次迭代給出最優解或判斷無最優解。§2.4單純形方法規范式2.4.1基可行解是最優解的判斷準則判別數最優性條件例2.4.1考慮線性規劃判斷無最優解基可行解的轉換基可行解的轉換單純形方法如果線性規劃是非退化的,則按照上面的方法

(進基,離基)迭代一次后,目標函數值有所下降.

經過有限次迭代之后,一定可以得到一個基可行解,使得其所有判別數非負(得到最優解),或者其有一個判別數是負的,但對應列向量的所有分量非正(線性規劃無最優解).這種求解線性規劃的方法稱為單純形方法.單純形法的迭代步驟單純形法的迭代的主要工作是將原來的規范式寫為新的規范式.通過初等行變換將主元變為1通過初等行變換將主元所在列其它元素變為0得到新的規范式§2.5單純形表§2.6初始基可行解的求法2.6.1大M單純形法大M方法算例2.6.2兩階段單純形法兩階段法算例求解原線性規劃的單純形表§2.8線性規劃的對偶理論原始問題對偶問題對偶規劃(定義2.8.1)對合性定理2.8.1對偶線性規劃的對偶問題是原始線性規劃問題對偶規劃的寫法寫出對偶規劃非對稱形式的對偶線性規劃弱對偶性定理推論若x0是原始線性規劃的可行解,y0是對偶線性規劃的可行解,且cTx0=bTy0,則x0與y0分別是原始線性規劃問題與對偶線性規劃問題的最優解.推論2(補充)對偶的線性規劃都有最優解的充要條件是兩者都有可行解.定理2.8.6若原始線性規劃問題與對偶線性規劃問題之一具有無界的目標函數值,則另一個無可行解.對偶性定理定理2.8.5若原始線性規劃問題與對偶線性規劃問題之一有最優解,則另一個也有最優解,并且它們目標函數的最優值相等.對偶的線性規劃問題的解兩個互為對偶的線性規劃的解的情況(1)兩個都有可行解¨兩個都有最優解,最優值相等¨一個有最優解(2)兩個都無可行解(書中有錯)(3)一個有可行解,無最優解(目標函數無界),則另一個無可行解互補松弛性§2.9對偶單純形法單純形方法與對偶單純形方法1.最優性的判別2.確定離基變量3.確定進基變量3.確定進基變量算例§2.10靈敏度分析靈敏度分析非基變量價格系數的變化基變量價格系數的變化基變量價格系數的變化例2.10.1B仍然是最優基?影子價格約束矩陣中系數的變化例2.10.2§2.11整數線性規劃整數線性規劃如果線性規劃的全部或部分變量要求取為整數,就稱為整數線性規劃,有時簡稱為整數規劃.所有的變量都要求是整數時,稱為純整數線性規劃;部分變量要求取整數時,稱為混合型整數線性規劃.求解的簡單思路:先不考慮整數要求,求解一般的線性規劃.若求得的最優解不滿足整數要求時,用”舍入取整”的方法處理.該方法有時會帶來很大的誤差,甚至得到的解不可行.2.11.1割平面法割平面方程割平面方程增加割平面方程的規劃割平面法示例割平面法的