




版權(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ì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 2025屆湖北省襄陽市東風(fēng)中學(xué)物理高一下期末聯(lián)考試題含解析
- 甘肅省天水市清水縣第四中學(xué)2025屆物理高一下期末學(xué)業(yè)水平測(cè)試試題含解析
- 2025年北京市西城區(qū)月壇中學(xué)高一物理第二學(xué)期期末質(zhì)量跟蹤監(jiān)視模擬試題含解析
- 全國(guó)大學(xué)生職業(yè)規(guī)劃大賽《能源經(jīng)濟(jì)》專業(yè)生涯發(fā)展展示
- 2025屆湖南省道縣第二中學(xué)物理高一第二學(xué)期期末學(xué)業(yè)質(zhì)量監(jiān)測(cè)模擬試題含解析
- 信用社柜員年度考核個(gè)人工作總結(jié)
- 保姆雇傭的簡(jiǎn)單合同
- 企業(yè)培訓(xùn)計(jì)劃書怎么寫
- 智本論視角下的企業(yè)轉(zhuǎn)型升級(jí)策略
- 親子閱讀講話稿
- 保安培訓(xùn)課程表(完整版)咨詢培訓(xùn)
- 《飛機(jī)電子顯示器顯示符號(hào)》
- 贏利:未來10年的經(jīng)營(yíng)能力
- 光伏支架風(fēng)荷載分析
- 頭等大事:脫發(fā)青年自救指南
- 馬拉色菌相關(guān)疾病診療指南(2022年版)
- 哈雷之約:基于指數(shù)成分股調(diào)整的選股策略
- 湖北省隨州市各縣區(qū)鄉(xiāng)鎮(zhèn)行政村村莊村名居民村民委員會(huì)明細(xì)及行政區(qū)劃代碼
- 磁流體密封課件
- T∕CCIA 001-2022 面向網(wǎng)絡(luò)安全保險(xiǎn)的風(fēng)險(xiǎn)評(píng)估指引
- 高處作業(yè)審批表
評(píng)論
0/150
提交評(píng)論