單純形法大M法求解線性規(guī)劃問(wèn)題.ppt

單純形法大M法求解線性規(guī)劃問(wèn)題.ppt

ID:51330289

大?。?.99 MB

頁(yè)數(shù):69頁(yè)

時(shí)間:2020-03-21

單純形法大M法求解線性規(guī)劃問(wèn)題.ppt_第1頁(yè)
單純形法大M法求解線性規(guī)劃問(wèn)題.ppt_第2頁(yè)
單純形法大M法求解線性規(guī)劃問(wèn)題.ppt_第3頁(yè)
單純形法大M法求解線性規(guī)劃問(wèn)題.ppt_第4頁(yè)
單純形法大M法求解線性規(guī)劃問(wèn)題.ppt_第5頁(yè)
資源描述:

《單純形法大M法求解線性規(guī)劃問(wèn)題.ppt》由會(huì)員上傳分享,免費(fèi)在線閱讀,更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、第二章單純形法單純形法的一般原理表格單純形法借助人工變量求初始的基本可行解單純形表與線性規(guī)劃問(wèn)題的討論改進(jìn)單純形法1考慮到如下線性規(guī)劃問(wèn)題其中A一個(gè)m×n矩陣,且秩為m,b總可以被調(diào)整為一個(gè)m維非負(fù)列向量,C為n維行向量,X為n維列向量。根據(jù)線性規(guī)劃基本定理:如果可行域D={X∈Rn/AX=b,X≥0}非空有界,則D上的最優(yōu)目標(biāo)函數(shù)值Z=CX一定可以在D的一個(gè)頂點(diǎn)上達(dá)到。這個(gè)重要的定理啟發(fā)了Dantzig的單純形法,即將尋優(yōu)的目標(biāo)集中在D的各個(gè)頂點(diǎn)上。單純形法的一般原理2Dantzig的單純形法把尋優(yōu)的目標(biāo)集中在所有基本可行解(即可行域頂點(diǎn))中。其基本思路是從一個(gè)初始的基本可行解

2、出發(fā),尋找一條達(dá)到最優(yōu)基本可行解的最佳途徑。單純形法的一般步驟如下:(1)尋找一個(gè)初始的基本可行解。(2)檢查現(xiàn)行的基本可行解是否最優(yōu),如果為最優(yōu),則停止迭代,已找到最優(yōu)解,否則轉(zhuǎn)一步。(3)移至目標(biāo)函數(shù)值有所改善的另一個(gè)基本可行解,然后轉(zhuǎn)會(huì)到步驟(2)。3確定初始的基本可行解確定初始的基本可行解等價(jià)于確定初始的可行基,一旦初始的可行基確定了,那么對(duì)應(yīng)的初始基本可行解也就唯一確定為了討論方便,不妨假設(shè)在標(biāo)準(zhǔn)型線性規(guī)劃中,系數(shù)矩陣A中前m個(gè)系數(shù)列向量恰好構(gòu)成一個(gè)可行基,即A=(BN),其中B=(P1,P2,…Pm)為基變量x1,x2,…xm的系數(shù)列向量構(gòu)成的可行基,N=(Pm+1,

3、Pm+2,…Pn)為非基變量xm+1,xm+2,…xn的系數(shù)列向量構(gòu)成的矩陣。4所以約束方程 就可以表示為用可行基B的逆陣B-1左乘等式兩端,再通過(guò)移項(xiàng)可推得:若令所有非基變量,則基變量由此可得初始的基本可行解5問(wèn)題:要判斷m個(gè)系數(shù)列向量是否恰好構(gòu)成一個(gè)基并不是一件容易的事?;上禂?shù)矩陣A中m個(gè)線性無(wú)關(guān)的系數(shù)列向量構(gòu)成。但是要判斷m個(gè)系數(shù)列向量是否線性無(wú)關(guān)并非易事。即使系數(shù)矩陣A中找到了一個(gè)基B,也不能保證該基恰好是可行基。因?yàn)椴荒鼙WC基變量XB=B-1b≥0。為了求得基本可行解,必須求基B的逆陣B-1。但是求逆陣B-1也是一件麻煩的事。結(jié)論:在線性規(guī)劃標(biāo)準(zhǔn)化過(guò)程中設(shè)法得到一個(gè)m

4、階單位矩陣I作為初始可行基B,6若在化標(biāo)準(zhǔn)形式前,約束方程中有“≥”不等式,那么在化標(biāo)準(zhǔn)形時(shí)除了在方程式左端減去剩余變量使不等式變成等式以外,還必須在左端再加上一個(gè)非負(fù)新變量,稱為人工變量.若在化標(biāo)準(zhǔn)形式前,約束方程中有等式方程,那么可以直接在等式左端添加人工變量。為了設(shè)法得到一個(gè)m階單位矩陣I作為初始可行基B,可在性規(guī)劃標(biāo)準(zhǔn)化過(guò)程中作如下處理:若在化標(biāo)準(zhǔn)形式前,m個(gè)約束方程都是“≤”的形式,那么在化標(biāo)準(zhǔn)形時(shí)只需在一個(gè)約束不等式左端都加上一個(gè)松弛變量xn+i(i=12…m)。7判斷現(xiàn)行的基本可行解是否最優(yōu)假如已求得一個(gè)基本可行解將這一基本可行解代入目標(biāo)函數(shù),可求得相應(yīng)的目標(biāo)函數(shù)值

5、其中分別表示基變量和非基變量所對(duì)應(yīng)的價(jià)值系數(shù)子向量。8要判定      是否已經(jīng)達(dá)到最大值,只需將代入目標(biāo)函數(shù),使目標(biāo)函數(shù)用非基變量表示,即:其中        稱為非基變量XN的檢驗(yàn)向量,它的各個(gè)分量稱為檢驗(yàn)數(shù)。若σN的每一個(gè)檢驗(yàn)數(shù)均小于等于0,即σN≤0,那么現(xiàn)在的基本可行解就是最優(yōu)解。9定理1:最優(yōu)解判別定理對(duì)于線性規(guī)劃問(wèn)題若某個(gè)基本可行解所對(duì)應(yīng)的檢驗(yàn)向量          ,則這個(gè)基本可行解就是最優(yōu)解。定理2:無(wú)窮多最優(yōu)解判別定理若     是一個(gè)基本可行解,所對(duì)應(yīng)的檢驗(yàn)向量,其中存在一個(gè)檢驗(yàn)數(shù)σm+k=0,則線性規(guī)劃問(wèn)題有無(wú)窮多最優(yōu)解。10基本可行解的改進(jìn)如果現(xiàn)行的基本

6、可行解X不是最優(yōu)解,即在檢驗(yàn)向量中存在正的檢驗(yàn)數(shù),則需在原基本可行解X的基礎(chǔ)上尋找一個(gè)新的基本可行解,并使目標(biāo)函數(shù)值有所改善。具體做法是:先從檢驗(yàn)數(shù)為正的非基變量中確定一個(gè)換入變量,使它從非基變量變成基變量(將它的值從零增至正值),再?gòu)脑瓉?lái)的基變量中確定一個(gè)換出變量,使它從基變量變成非基變量(將它的值從正值減至零)。由此可得一個(gè)新的基本可行解,由可知,這樣的變換一定能使目標(biāo)函數(shù)值有所增加。11換入變量和換出變量的確定:換入變量的確定—最大增加原則假設(shè)檢驗(yàn)向量                ,若其中有兩個(gè)以上的檢驗(yàn)數(shù)為正,那么為了使目標(biāo)函數(shù)值增加得快些,通常要用“最大增加原則”,即

7、選取最大正檢驗(yàn)數(shù)所對(duì)應(yīng)的非基變量為換入變量,即若則選取對(duì)應(yīng)的  為換入變量,由于    且為最大,因此當(dāng)   由零增至正值,可使目標(biāo)函數(shù)值最大限度的增加。12換出變量的確定—最小比值原則如果確定  為換入變量,方程其中  為A中與   對(duì)應(yīng)的系數(shù)列向量?,F(xiàn)在需在       中確定一個(gè)基變量為換出變量。當(dāng)  由零慢慢增加到某個(gè)值時(shí),的非負(fù)性可能被打破。為保持解的可行性,可以按最小比值原則確定換出變量:若則選取對(duì)應(yīng)的基變量 為換出變量。13定理3:無(wú)最優(yōu)解判別定理若是一個(gè)基本可行解

當(dāng)前文檔最多預(yù)覽五頁(yè),下載文檔查看全文

此文檔下載收益歸作者所有

當(dāng)前文檔最多預(yù)覽五頁(yè),下載文檔查看全文
溫馨提示:
1. 部分包含數(shù)學(xué)公式或PPT動(dòng)畫的文件,查看預(yù)覽時(shí)可能會(huì)顯示錯(cuò)亂或異常,文件下載后無(wú)此問(wèn)題,請(qǐng)放心下載。
2. 本文檔由用戶上傳,版權(quán)歸屬用戶,天天文庫(kù)負(fù)責(zé)整理代發(fā)布。如果您對(duì)本文檔版權(quán)有爭(zhēng)議請(qǐng)及時(shí)聯(lián)系客服。
3. 下載前請(qǐng)仔細(xì)閱讀文檔內(nèi)容,確認(rèn)文檔內(nèi)容符合您的需求后進(jìn)行下載,若出現(xiàn)內(nèi)容與標(biāo)題不符可向本站投訴處理。
4. 下載文檔時(shí)可能由于網(wǎng)絡(luò)波動(dòng)等原因無(wú)法下載或下載錯(cuò)誤,付費(fèi)完成后未能成功下載的用戶請(qǐng)聯(lián)系客服處理。