




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)
文檔簡介
1、第二章 線性規(guī)劃問題及單純形法,線性規(guī)劃問題及其數(shù)學(xué)模型 圖解法 單純形法原理 單純形法計算步驟 單純形法的進(jìn)一步討論,第三節(jié) 單純形法原理,本節(jié)重點: 基本概念 線性規(guī)劃基本定理 檢驗數(shù)的概念和計算 最優(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中的一個mm階的滿秩子系數(shù)矩陣,稱B是線性
2、規(guī)劃問題的一個基。,不失一般性,設(shè) :,B中的每一個列向量Pj ( j1,m )稱為基向量,與基向量Pj對應(yīng)的變量xj稱為基變量。線性規(guī)劃中除基變量以外的變量稱為非基變量。 基解: 在約束方程組(2.2)中,令所有非基變量 xm+1xm+2xn0,又因為有 ,根據(jù)克萊姆規(guī)則,由m個約束方程可解出m個基變量的唯一解 。將這個解加上非基變量取0的值有 ,稱X為線性規(guī)劃問題的基解。顯然在基解中變量取非零值的個數(shù)不大于方程數(shù)m,故基解的總數(shù)不超過 個。 基可行解: 滿足變量非負(fù)約束條件(2.3)的基解稱為基可行解。 可行基: 對應(yīng)于基可行解的基稱為可行基。 退化解: 基可行解的非零分量個數(shù) m 時,即
3、有的基可行解也為0,稱為退化解。,例:找出下述線性規(guī)劃問題的全部基解,指出其中的基可行解,并確定最優(yōu)解。,解:該線性規(guī)劃問題的全部基解見表中的 -,打者為基可行解,注*者為最優(yōu)解,z* l9。,線性規(guī)劃標(biāo)準(zhǔn)型問題解的關(guān)系,約束方程的 解空間,基解,可行解,非可行解,基 可行解,退化解,二、線性規(guī)劃問題的幾何意義,凸集的概念 頂點 線性規(guī)劃基本定理,1. 凸集,對簡單的幾何形體可以直觀地判斷其凹凸性,但在高維空間,只能給出點集的解析表達(dá)式,因此只能用數(shù)學(xué)解析式判斷。凸集的概念為:如果集合C中任意兩個點X1,X2,其連線上的所有點也都是集合C中的點,稱C為凸集。由于X1,X2的連線可表示為,因此凸
4、集定義用數(shù)學(xué)解析式可表為:對任何 ,有 則稱C為凸集.,圖中紅粗線和紅點是頂點。,2.頂點 凸集C中滿足下述條件的點X稱為頂點。 如果C中不存在任何兩個不同的點X1,X2,使X成為這兩個點連線上的一個點,或者:對任何 ,不存在 ,則稱X是凸集C的頂點。,3. 線性規(guī)劃基本定理,定理1 若線性規(guī)劃問題存在可行解,則問題的可行域是凸集。,證 (方法1) 若滿足線性規(guī)劃約束條件 的所有點組成的幾何圖形C是凸集,根據(jù)凸集定義,C內(nèi)任意兩點Xl,X2連線上的點也必然在C內(nèi),下面給予證明。,設(shè) 為C內(nèi)任意兩點, 即 ,將X1,X2代入約束條件有,(2.4),X1,X2連線上任意一點可以表示為:,(2.5)
5、,將式(2.4)代入式(2.5)得:,所以 。由于集合中任意兩點連線上的點均在集合內(nèi),所以C為凸集。,引理 線性規(guī)劃問題的可行解X=(x1,x2,xn)T為基可行解的充分必要條件是X 的正分量所對應(yīng)的系數(shù)列向量是線性無關(guān)的。,證明: (1)必要性 由基可行解的定義可知,X為基可行解 其正分量的系數(shù)列向量線性無關(guān)。 (2)充分性 若向量 線性獨立,則必有km;當(dāng)km時,它們恰好構(gòu)成一個基,從而 為相應(yīng)的基可行解。當(dāng)是km時,則一定可以從其余列向量中找出(m-k)個與 構(gòu)成一個基,其對應(yīng)的解恰為X,所以據(jù)定義它是基可行解。,定理2 線性規(guī)劃問題的基可行解 對應(yīng)線性規(guī)劃問題可行域(凸集)的頂點。,則
6、問題可以轉(zhuǎn)化為證明: 的正分量對應(yīng)的系數(shù)列向量線性相關(guān) 在可行域內(nèi)存在兩點 、 , 可以用 、 的凸組合表示。,不是基可行解 不是可行域的頂點。 不是基可行解 的正分量對應(yīng)的系數(shù)列向量線性相關(guān)。 不是可行域的頂點 在可行域內(nèi)存在兩點 、 , 可以用 、 的凸組合表示。,證明思路: 利用反證法證明。,定理3 若線性規(guī)劃問題有最優(yōu)解,一定存在一個基可行解是最優(yōu)解。,結(jié)論: 線性規(guī)劃問題的可行域是凸集(凸多面體),有有限多個頂點。頂點對應(yīng)基可行解。當(dāng)可行域有界時,必有頂點達(dá)到目標(biāo)函數(shù)最優(yōu)值。,三、單純型法的基本思路,由定理3可知,如果線性規(guī)劃問題存在最優(yōu)解,一定有一個基可行解是最優(yōu)解。 因此單純形法迭代的基本思路是:先找出一個基可行解,判斷其是否為最優(yōu)解,如果為否,則轉(zhuǎn)換到相鄰的基可行解,并使目標(biāo)函數(shù)值不斷增大,一直找到最優(yōu)解
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 培訓(xùn)安全保障措施方案
- 工廠安全管理方針
- 安全生產(chǎn)教育和培訓(xùn)范圍是
- 安全生產(chǎn)月啟動儀式策劃
- 黑龍江省哈爾濱市尚志中學(xué)2025年物理高二下期末綜合測試試題含解析
- 互聯(lián)網(wǎng)信息安全管理制度
- 生產(chǎn)安全事故隱患排查治理標(biāo)準(zhǔn)體系
- 企業(yè)安全生產(chǎn)的第一責(zé)任人
- 幼兒園安全隱患自查制度
- 各級人員安全生產(chǎn)責(zé)任制
- 保安培訓(xùn)課程表(完整版)咨詢培訓(xùn)
- 《飛機電子顯示器顯示符號》
- 贏利:未來10年的經(jīng)營能力
- 光伏支架風(fēng)荷載分析
- 頭等大事:脫發(fā)青年自救指南
- 馬拉色菌相關(guān)疾病診療指南(2022年版)
- 哈雷之約:基于指數(shù)成分股調(diào)整的選股策略
- 湖北省隨州市各縣區(qū)鄉(xiāng)鎮(zhèn)行政村村莊村名居民村民委員會明細(xì)及行政區(qū)劃代碼
- 磁流體密封課件
- T∕CCIA 001-2022 面向網(wǎng)絡(luò)安全保險的風(fēng)險評估指引
- 高處作業(yè)審批表
評論
0/150
提交評論