運(yùn)籌學(xué)13課件_第1頁
運(yùn)籌學(xué)13課件_第2頁
運(yùn)籌學(xué)13課件_第3頁
運(yùn)籌學(xué)13課件_第4頁
運(yùn)籌學(xué)13課件_第5頁
已閱讀5頁,還剩25頁未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

1、第二章 線性規(guī)劃問題及單純形法,線性規(guī)劃問題及其數(shù)學(xué)模型 圖解法 單純形法原理 單純形法計(jì)算步驟 單純形法的進(jìn)一步討論,第三節(jié) 單純形法原理,本節(jié)重點(diǎn): 基本概念 線性規(guī)劃基本定理 檢驗(yàn)數(shù)的概念和計(jì)算 最優(yōu)性判別 基變換(換入變量和換出變量的確定),一、關(guān)于標(biāo)準(zhǔn)型解的若干基本概念,線性規(guī)劃問題 :,可行解:滿足上述約束條件(2.2),(2.3)的解 ,稱為線性規(guī)劃問題的可行解。全部可行解的集合稱為可行域。 最優(yōu)解:使目標(biāo)函數(shù)(2.1)達(dá)到最大值的可行解稱為最優(yōu)解。 基:設(shè) A 為約束方程組(2.2)的 mn 階系數(shù)矩陣,(設(shè)nm),其秩為m,B是矩陣A中的一個(gè)mm階的滿秩子系數(shù)矩陣,稱B是線性

2、規(guī)劃問題的一個(gè)基。,不失一般性,設(shè) :,B中的每一個(gè)列向量Pj ( j1,m )稱為基向量,與基向量Pj對(duì)應(yīng)的變量xj稱為基變量。線性規(guī)劃中除基變量以外的變量稱為非基變量。 基解: 在約束方程組(2.2)中,令所有非基變量 xm+1xm+2xn0,又因?yàn)橛?,根據(jù)克萊姆規(guī)則,由m個(gè)約束方程可解出m個(gè)基變量的唯一解 。將這個(gè)解加上非基變量取0的值有 ,稱X為線性規(guī)劃問題的基解。顯然在基解中變量取非零值的個(gè)數(shù)不大于方程數(shù)m,故基解的總數(shù)不超過 個(gè)。 基可行解: 滿足變量非負(fù)約束條件(2.3)的基解稱為基可行解。 可行基: 對(duì)應(yīng)于基可行解的基稱為可行基。 退化解: 基可行解的非零分量個(gè)數(shù) m 時(shí),即

3、有的基可行解也為0,稱為退化解。,例:找出下述線性規(guī)劃問題的全部基解,指出其中的基可行解,并確定最優(yōu)解。,解:該線性規(guī)劃問題的全部基解見表中的 -,打者為基可行解,注*者為最優(yōu)解,z* l9。,線性規(guī)劃標(biāo)準(zhǔn)型問題解的關(guān)系,約束方程的 解空間,基解,可行解,非可行解,基 可行解,退化解,二、線性規(guī)劃問題的幾何意義,凸集的概念 頂點(diǎn) 線性規(guī)劃基本定理,1. 凸集,對(duì)簡(jiǎn)單的幾何形體可以直觀地判斷其凹凸性,但在高維空間,只能給出點(diǎn)集的解析表達(dá)式,因此只能用數(shù)學(xué)解析式判斷。凸集的概念為:如果集合C中任意兩個(gè)點(diǎn)X1,X2,其連線上的所有點(diǎn)也都是集合C中的點(diǎn),稱C為凸集。由于X1,X2的連線可表示為,因此凸

4、集定義用數(shù)學(xué)解析式可表為:對(duì)任何 ,有 則稱C為凸集.,圖中紅粗線和紅點(diǎn)是頂點(diǎn)。,2.頂點(diǎn) 凸集C中滿足下述條件的點(diǎn)X稱為頂點(diǎn)。 如果C中不存在任何兩個(gè)不同的點(diǎn)X1,X2,使X成為這兩個(gè)點(diǎn)連線上的一個(gè)點(diǎn),或者:對(duì)任何 ,不存在 ,則稱X是凸集C的頂點(diǎn)。,3. 線性規(guī)劃基本定理,定理1 若線性規(guī)劃問題存在可行解,則問題的可行域是凸集。,證 (方法1) 若滿足線性規(guī)劃約束條件 的所有點(diǎn)組成的幾何圖形C是凸集,根據(jù)凸集定義,C內(nèi)任意兩點(diǎn)Xl,X2連線上的點(diǎn)也必然在C內(nèi),下面給予證明。,設(shè) 為C內(nèi)任意兩點(diǎn), 即 ,將X1,X2代入約束條件有,(2.4),X1,X2連線上任意一點(diǎn)可以表示為:,(2.5)

5、,將式(2.4)代入式(2.5)得:,所以 。由于集合中任意兩點(diǎn)連線上的點(diǎn)均在集合內(nèi),所以C為凸集。,引理 線性規(guī)劃問題的可行解X=(x1,x2,xn)T為基可行解的充分必要條件是X 的正分量所對(duì)應(yīng)的系數(shù)列向量是線性無關(guān)的。,證明: (1)必要性 由基可行解的定義可知,X為基可行解 其正分量的系數(shù)列向量線性無關(guān)。 (2)充分性 若向量 線性獨(dú)立,則必有km;當(dāng)km時(shí),它們恰好構(gòu)成一個(gè)基,從而 為相應(yīng)的基可行解。當(dāng)是km時(shí),則一定可以從其余列向量中找出(m-k)個(gè)與 構(gòu)成一個(gè)基,其對(duì)應(yīng)的解恰為X,所以據(jù)定義它是基可行解。,定理2 線性規(guī)劃問題的基可行解 對(duì)應(yīng)線性規(guī)劃問題可行域(凸集)的頂點(diǎn)。,則

6、問題可以轉(zhuǎn)化為證明: 的正分量對(duì)應(yīng)的系數(shù)列向量線性相關(guān) 在可行域內(nèi)存在兩點(diǎn) 、 , 可以用 、 的凸組合表示。,不是基可行解 不是可行域的頂點(diǎn)。 不是基可行解 的正分量對(duì)應(yīng)的系數(shù)列向量線性相關(guān)。 不是可行域的頂點(diǎn) 在可行域內(nèi)存在兩點(diǎn) 、 , 可以用 、 的凸組合表示。,證明思路: 利用反證法證明。,定理3 若線性規(guī)劃問題有最優(yōu)解,一定存在一個(gè)基可行解是最優(yōu)解。,結(jié)論: 線性規(guī)劃問題的可行域是凸集(凸多面體),有有限多個(gè)頂點(diǎn)。頂點(diǎn)對(duì)應(yīng)基可行解。當(dāng)可行域有界時(shí),必有頂點(diǎn)達(dá)到目標(biāo)函數(shù)最優(yōu)值。,三、單純型法的基本思路,由定理3可知,如果線性規(guī)劃問題存在最優(yōu)解,一定有一個(gè)基可行解是最優(yōu)解。 因此單純形法迭代的基本思路是:先找出一個(gè)基可行解,判斷其是否為最優(yōu)解,如果為否,則轉(zhuǎn)換到相鄰的基可行解,并使目標(biāo)函數(shù)值不斷增大,一直找到最優(yōu)解

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

最新文檔

評(píng)論

0/150

提交評(píng)論