2023年全國(guó)碩士研究生考試考研英語(yǔ)一試題真題(含答案詳解+作文范文)_第1頁(yè)
已閱讀1頁(yè),還剩23頁(yè)未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

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

文檔簡(jiǎn)介

1、單純形法進(jìn)一步討論,竇志武,云南財(cái)經(jīng)大學(xué) 物流學(xué)院,單純形法的進(jìn)一步討論-人工變量法,人工變量法:前面討論了在標(biāo)準(zhǔn)型中系數(shù)矩陣有單位矩陣,很容易確定一組基可行解。在實(shí)際問題中有些模型并不含有單位矩陣,為了得到一組基向量和初基可行解,在約束條件的等式左端加一組虛擬變量,得到一組基變量。這種人為加的變量稱為人工變量,構(gòu)成的可行基稱為人工基,用大M法或兩階段法求解,這種用人工變量作橋梁的求解方法稱為人工變量法。,例: min z=2x1+

2、3x2 max z=-2x1-3x2+0x3 s.t x1+x2? 3 標(biāo)準(zhǔn)化 s.t x1+x2 -x3=3 x1+2x2 = 4 ? x1+2x2=4 x1?0, x2?0 xj?0, (j=1,2,3,4),,,m

3、ax z=-2x1-3x2+0x3 -M x4-M x5 s.t x1+x2 -x3+ x4 =3 x1+2x2 +x5 =4 xj?0, (j=1,2,3,4,5),,引進(jìn)人工變量,及M——非常大正系數(shù),模型轉(zhuǎn)變?yōu)?這種處理方法稱為大M法,以下則

4、可完全按單純形法求解。,1.大M法,單純形法的進(jìn)一步討論-人工變量法,單純形法的進(jìn)一步討論-人工變量法,例1.10 用大M法解下列線性規(guī)劃,解:首先將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式,系數(shù)矩陣中不存在單位矩陣,無(wú)法建立初始單純形表。,單純形法的進(jìn)一步討論-人工變量法,故人為添加兩個(gè)單位向量,得到人工變量單純形法數(shù)學(xué)模型:,其中:M是一個(gè)很大的抽象的數(shù),不需要給出具體的數(shù)值,可以理解為它能大于給定的任何一個(gè)確定數(shù)值;再用前面介紹的單純形法求解該模型

5、,計(jì)算結(jié)果見下表。,單純形法的進(jìn)一步討論-人工變量法,,,→,→,,→,單純形法的進(jìn)一步討論-人工變量法,例1.11 用大M法解下列線性規(guī)劃,解:首先將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式,系數(shù)矩陣中不存在單位矩陣,無(wú)法建立初始單純形表。,單純形法的進(jìn)一步討論-人工變量法,故人為添加兩個(gè)單位向量,得到人工變量單純形法數(shù)學(xué)模型:,其中:M是一個(gè)很大的抽象的數(shù),不需要給出具體的數(shù)值,可以理解為它能大于給定的任何一個(gè)確定數(shù)值;再用前面介紹的單純形法求解該模

6、型,計(jì)算結(jié)果見下表。,單純形法的進(jìn)一步討論-人工變量法,,,→,,→,,單純形法的進(jìn)一步討論-人工變量法,,→,,單純形法的進(jìn)一步討論-兩階段法,用計(jì)算機(jī)處理數(shù)據(jù)時(shí),只能用很大的數(shù)代替M,可能造成計(jì)算機(jī)上的錯(cuò)誤,故多采用兩階段法。,第一階段: 在原線性規(guī)劃問題中加入人工變量,構(gòu)造如下模型:,對(duì)上述模型求解(單純形法),若ω=0,說(shuō)明問題存在基可行解,可以進(jìn)行第二個(gè)階段;否則,原問題無(wú)可行解,停止運(yùn)算。,單純形法的進(jìn)一步討論-兩階段

7、法,第一階段的線性規(guī)劃問題可寫為:,第一階段單純形法迭代的過(guò)程見下表,單純形法的進(jìn)一步討論-兩階段法,,,→,,→,,單純形法的進(jìn)一步討論-兩階段法,第二階段: 在第一階段的最終表中,去掉人工變量,將目標(biāo)函數(shù)的系數(shù)換成原問題的目標(biāo)函數(shù)系數(shù),作為第二階段計(jì)算的初始表(用單純形法計(jì)算)。,例:,單純形法的進(jìn)一步討論-兩階段法,,,→,第二階段:,∴最優(yōu)解為(4 1 9 0 0),目標(biāo)函數(shù) Z = 2,單純形法的進(jìn)一步

8、討論,通過(guò)大M法或兩階段法求初始的基本可行解。但是如果在大M法的最優(yōu)單純形表的基變量中仍含有人工變量,或者兩階段法的輔助線性規(guī)劃的目標(biāo)函數(shù)的極小值大于零,那么該線性規(guī)劃就不存在可行解。,無(wú)可行解,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,C,,,,,,,,,,,,,,,,,,-3 -2 -1 0 0 0 -M -M,CB,XB,b,x1

9、x2 x3 x4 x5 x6 x7 x8,θ,0-M-M,x4x7x8,643,1 1 1 1 0 0 0 01 0 -1 0 -1 0 1 00 1 -1 0

10、 0 -1 0 1,6/1-3/1,Z,-7M,-6-4M,-15-M,-3+M -2+M -1-2M 0 -M -M 0 0,0-M-2,x4x7x2,343,1 0 2 1 0 1 0 -11 0 -1 0 -1

11、 0 1 00 1 -1 0 0 -1 0 1,3/14/1-,Z,Z,-3+M 0 -3-M 0 -M -2 0 2-M,-3-M-2,x1x7x2,313,1 0 2 1 0 1

12、0 -10 0 -3 -1 -1 -1 1 10 1 -1 0 0 -1 0 1,0 0 3-3M 3-M -M 1-M 0 -1,,,例,單純形法的進(jìn)一步討論,運(yùn)算到檢驗(yàn)數(shù)全負(fù)為止,仍含有人工變量,無(wú)可行解。,單純形法的進(jìn)一步

13、討論,無(wú)最優(yōu)解與無(wú)可行解時(shí)兩個(gè)不同的概念。 無(wú)可行解是指原規(guī)劃不存在可行解,從幾何的角度解釋是指 線性規(guī)劃問題的可行域?yàn)榭占?無(wú)最優(yōu)解則是指線性規(guī)劃問題存在可行解,但是可行解的目 標(biāo)函數(shù)達(dá)不到最優(yōu)值,即目標(biāo)函數(shù)在可行域內(nèi)可以趨于無(wú)窮大(或者無(wú)窮?。o(wú)最優(yōu)解也稱為有限最優(yōu)解,或無(wú)界解。 判別方法:無(wú)最優(yōu)解判別定理  在求解極大化的線性規(guī)劃問題過(guò)程中,若某單純形表的檢驗(yàn) 行存在某個(gè)大于零的檢驗(yàn)數(shù),但是該檢驗(yàn)數(shù)所

14、對(duì)應(yīng)的非基變量 的系數(shù)列向量的全部系數(shù)都為負(fù)數(shù)或零,則該線性規(guī)劃問題 無(wú)最優(yōu)解,無(wú)最優(yōu)解,因 但 所以原問題無(wú)最優(yōu)解,單純形法的進(jìn)一步討論,退化,即計(jì)算出的 θ(用于確定換出變量)存在有兩個(gè)以上相同的最小比值,會(huì)造成下一次迭代中由一個(gè)或幾個(gè)基變量等于零,這就是退化(會(huì)產(chǎn)生退化解)。 為避免出現(xiàn)計(jì)算的循環(huán),勃蘭特(Bland)提出一個(gè)簡(jiǎn)便有效的規(guī)則(攝動(dòng)法原理

15、): ⑴ 當(dāng)存在多個(gè) 時(shí),選下標(biāo)最小的非基變量為換入變量;(2) 當(dāng)θ值出現(xiàn)兩個(gè)以上相同的最小值時(shí),選下標(biāo)最小的基變量為換出變量。,單純形法的進(jìn)一步討論,無(wú)窮多最優(yōu)解,若線性規(guī)劃問題某個(gè)基本可行解所有的非基變量檢驗(yàn)數(shù)都小于等于零,但其中存在一個(gè)檢驗(yàn)數(shù)等于零,那么該線性規(guī)劃問題有無(wú)窮多最優(yōu)解。例3:最優(yōu)表:非基變量檢驗(yàn)數(shù)   ,所以有無(wú)窮多最優(yōu)解。,單純形法的進(jìn)一步討論,單純形法的進(jìn)一

16、步討論,解的判別:1)唯一最優(yōu)解判別:最優(yōu)表中所有非基變量的檢驗(yàn)數(shù)非零,則線性規(guī)劃具有唯一最優(yōu)解。2)多重最優(yōu)解判別:最優(yōu)表中存在非基變量的檢驗(yàn)數(shù)為零,則線性規(guī)劃具有多重最優(yōu)解(或無(wú)窮多最優(yōu)解)。3)無(wú)界解判別:某個(gè) k>0且aik≤0(i=1,2,…,m)則線性規(guī)劃具有無(wú)界解。4)無(wú)可行解的判斷:當(dāng)用大M單純形法計(jì)算得到最優(yōu)解并且存在Ri>0時(shí),則表明原線性規(guī)劃無(wú)可行解。5)退化解的判別:存在某個(gè)基變量為零的

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 眾賞文庫(kù)僅提供信息存儲(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)論