第二章線性規(guī)劃

第二章線性規(guī)劃§2.1凸集與凸函數(shù)凸集設(shè)V是實(shí)數(shù)域R上的線性空間（或稱為向量空間），若V上定義著正定對(duì)稱雙線性型g（g稱為內(nèi)積），則V稱為（對(duì)于g的）內(nèi)積空間或歐幾里德空間（有時(shí)僅當(dāng)V是有限維時(shí)，才稱為歐幾里德空間）。具體來說，g是V上的二元實(shí)值函數(shù)，滿足如下關(guān)系：（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當(dāng)且僅當(dāng)x=0時(shí)成立例2.1.2超球||x||≤r為凸集凸集的性質(zhì)

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)極點(diǎn)極點(diǎn)凸函數(shù)凸函數(shù)的例子凸函數(shù)的幾何性質(zhì)凸函數(shù)的幾何性質(zhì)上圖對(duì)于一元凸函數(shù)f(x),可以發(fā)現(xiàn),位于函數(shù)曲線上方的圖形是凸集.事實(shí)上這一結(jié)論對(duì)于多元函數(shù)也是成立的,而且是充要條件,即有下面的定理.定理:設(shè)f(x)是定義在凸集

上的函數(shù),則f(x)是凸函數(shù)的充要條件是其上圖epi(f)為凸集,其中epi(f)=證明:作業(yè)凸函數(shù)的性質(zhì)凸函數(shù)的判斷凸函數(shù)的判斷一階條件二階條件凸規(guī)劃定理2.1.5證明(思路)§2.2線性規(guī)劃的標(biāo)準(zhǔn)型

與基本概念線性規(guī)劃的一般形式線性規(guī)劃的標(biāo)準(zhǔn)型矩陣-向量形式的標(biāo)準(zhǔn)型矩陣-向量形式的標(biāo)準(zhǔn)型可行域?yàn)橥辜话阈问睫D(zhuǎn)化為標(biāo)準(zhǔn)型基本概念基本概念基本概念§2.3線性規(guī)劃的基本定理有可行解→有基可行解有最優(yōu)解→有最優(yōu)的基可行解單純形方法的思路找出一基可行解(極點(diǎn))若其不是最優(yōu),找到一個(gè)相鄰極點(diǎn)新的目標(biāo)函數(shù)值不大于原目標(biāo)函數(shù)值經(jīng)過有限次迭代給出最優(yōu)解或判斷無最優(yōu)解?！?.4單純形方法規(guī)范式2.4.1基可行解是最優(yōu)解的判斷準(zhǔn)則判別數(shù)最優(yōu)性條件例2.4.1考慮線性規(guī)劃判斷無最優(yōu)解基可行解的轉(zhuǎn)換基可行解的轉(zhuǎn)換單純形方法如果線性規(guī)劃是非退化的,則按照上面的方法

(進(jìn)基,離基)迭代一次后,目標(biāo)函數(shù)值有所下降.

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