版權(quán)說(shuō)明:本文檔由用戶(hù)提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
運(yùn)籌學(xué)課件單純形法的計(jì)算步驟第一頁(yè),共二十五頁(yè),2022年,8月28日4.1 單純形表
用表格法求解LP,規(guī)范的表格——單純形表如下:第二頁(yè),共二十五頁(yè),2022年,8月28日計(jì)算步驟(1).找出初始可行基,確定初始基可行解,建立初始單純形表。(2).檢驗(yàn)各非基變量xj的檢驗(yàn)數(shù),若j
0,j=m+1,…,n;則已得到最優(yōu)解,可停止計(jì)算,否則轉(zhuǎn)入下一步。(3).在j
>0,j=m+1,…,n中,若有某個(gè)k對(duì)應(yīng)xk的系數(shù)列向量Pk0,則此問(wèn)題是無(wú)界解,停止計(jì)算。否則,轉(zhuǎn)入下一步。(4).根據(jù)max(j>0)=k,確定xk為換入變量,按
規(guī)則計(jì)算=min{bi/aik\aik>0}可確定第l行的基變量為換出變量。轉(zhuǎn)入下一步。第三頁(yè),共二十五頁(yè),2022年,8月28日
23000
12
10040
01004
001
02300000081612x3x4x54-3
23000
2
1
0
10-1/2
-92000-3/4003x3x4x224-()
3
0
1001/4
16
4
0010X(0)=(0,0,8,16,12)T,z0=0第四頁(yè),共二十五頁(yè),2022年,8月28日
23000
2
1
010-1/2-1300-201/4203x1x4x2-412
3
0
100
1/4
8
0
0-41
2
23000
2
1
0
10-1/2
-92000-3/4003x3x4x224-
3
0
1001/4
16
4
0010()
X(1)=(0,3,2,16,0)T,z1=9第五頁(yè),共二十五頁(yè),2022年,8月28日
23000
2
1
010-1/2-1300-201/4203x1x4x2-412
3
0
100
1/4
8
0
0-41
2()
23000
4
1
00
1/40-1400-1.5-1/8
0203x1x5x2
2
0
11/2
-1/8
0
4
0
0-2
1/21
X(2)=(2,3,0,8,0)T,z2=13
X(3)=(4,2,0,4,0)T,z3=14第六頁(yè),共二十五頁(yè),2022年,8月28日§5單純形法的進(jìn)一步討論5.1 人工變量法
解決初始基可行解的問(wèn)題。當(dāng)某個(gè)約束方程中沒(méi)有明顯的基變量時(shí),在該方程中加上人工變量。第七頁(yè),共二十五頁(yè),2022年,8月28日其中第2、3個(gè)約束方程中無(wú)明顯基變量,分別加上人工變x6,x7第八頁(yè),共二十五頁(yè),2022年,8月28日這時(shí),初始基和初始基可行解很明顯。X(0)=(0,0,0,11,0,3,1)T不滿(mǎn)足原來(lái)的約束條件。如何使得可從X(0)開(kāi)始,經(jīng)迭代逐步得到x6=0,x7=0的基可行解,從而求得問(wèn)題的最優(yōu)解,有兩種方法:第九頁(yè),共二十五頁(yè),2022年,8月28日反之,若加了人工變量的問(wèn)題解后最優(yōu)解中仍含人工變量為基變量,便說(shuō)明原問(wèn)題無(wú)可行解。例3的單純形表格為:只要原問(wèn)題有可行解,隨著目標(biāo)函數(shù)向最大化方向的改善,人工變量一定會(huì)逐步換出基,從而得到原問(wèn)題的基可行解,進(jìn)而得到基最優(yōu)解。3.大M法在目標(biāo)函數(shù)中加上懲罰項(xiàng)
max=3x1-x2-x3-Mx6-Mx7其中M為充分大的正數(shù)。第十頁(yè),共二十五頁(yè),2022年,8月28日3-6M M-1 3M-1 0
-M 0 0
0x4
103-20100-1-Mx610[1]00-11-21-1x31-2010001
1 -1+M 0 0
-M 0-3M+1
0x4
12[3]001-2-1x210100-14-1x31-20100
1 0 0 0
-1
3x1
41001/3-2/3-1x210100-1-1x390012/3-4/3
000-1/3-1/3
X*=(4,1,9,0,0),z*=2第十一頁(yè),共二十五頁(yè),2022年,8月28日2.兩階段法第一階段:以人工變量之和最小化為目標(biāo)函數(shù) min=x6+x7
第二階段:以第一階段的最優(yōu)解(不含人工變量)為初始解,以原目標(biāo)函數(shù)為目標(biāo)函數(shù)。第十二頁(yè),共二十五頁(yè),2022年,8月28日第十三頁(yè),共二十五頁(yè),2022年,8月28日第十四頁(yè),共二十五頁(yè),2022年,8月28日第十五頁(yè),共二十五頁(yè),2022年,8月28日5.2線性規(guī)劃問(wèn)題解的討論一、無(wú)可行解
maxz=2x1+4x2
x1+x210
2x1+x2
40
x1,x20人工變量不能從基底換出,此時(shí)原線性規(guī)劃無(wú)可行解x1x2CBXBbX3
x5
0-1
0000-1
x1x2x3x4x540210-1110[1]1100cj1040/2x1
x5
0-1
200-1-2-111011100
cj-zj0-1-2-10cj-zj210-10Z0=-40Z1=-20第十六頁(yè),共二十五頁(yè),2022年,8月28日第十七頁(yè),共二十五頁(yè),2022年,8月28日
例:maxz=3x1+4x2
x1+x240
2x1+x260
x1-x2=0
x1,x20
此題初始解是退化的。最優(yōu)解也是退化解。退化解迭代中,當(dāng)換入變量取零值時(shí)目標(biāo)函數(shù)值沒(méi)有改進(jìn),x1x20x340111000x4602101-1-Mx50[1]-10010x3400[2]100x46003013x101-1003+M4-M000zj-cj
000-7/3
zj-cj
0x30001-1/3
4x2200101/33x1201001/3cj→3400-M
CB
XBbx5
θx1x2x3
x4
0700zj-cj00-3.50zj-cj4x220011/200x4000-3/213x120101/20第十八頁(yè),共二十五頁(yè),2022年,8月28日第十九頁(yè),共二十五頁(yè),2022年,8月28日
例maxz=3x1+5x2
3x1+5x215
2x1+x25
2x1+2x211
x1,x20
如果將x1換入基底,得另一解,由可行域凸性易知,有兩個(gè)最優(yōu)解必有無(wú)窮多組最優(yōu)解當(dāng)非基底變量的檢驗(yàn)數(shù)中有取零值,或檢驗(yàn)數(shù)中零的個(gè)數(shù)大于基變量個(gè)數(shù)時(shí),有無(wú)窮多解。CBXBbx3
x4x5
00035000
x1x2x3x4x5521010153[5]1003511/5x2
x4x5
50033/511/50027/50-1/51054/50-2/501
cj-zj00-100cj-zj35000Z0=01122001Z1=15x1x2第二十頁(yè),共二十五頁(yè),2022年,8月28日四、無(wú)(有)界解
maxz=x1+x2
-2x1+x24
x1-x22
-3x1+x23
x1,x20
若檢驗(yàn)數(shù)有大于0,而對(duì)應(yīng)系數(shù)列中
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶(hù)所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶(hù)上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶(hù)上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶(hù)因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 2024年硬泡聚醚項(xiàng)目建議書(shū)
- 2024年磷酸鐵鋰電池合作協(xié)議書(shū)
- 2024年納豆激酶合作協(xié)議書(shū)
- 2024年地?zé)釤岜每照{(diào)系統(tǒng)項(xiàng)目發(fā)展計(jì)劃
- 2024年紫外固化材料合作協(xié)議書(shū)
- 2024年高強(qiáng)空心玻璃纖維項(xiàng)目建議書(shū)
- 2023年復(fù)相硼化物陶瓷項(xiàng)目調(diào)研分析報(bào)告
- 幼兒園《如果不吃青菜》課件
- 城市軌道交通概論學(xué)習(xí)通超星期末考試答案章節(jié)答案2024年
- 冬季傳染病預(yù)防-(課件)-小學(xué)主題班會(huì)課件
- 家長(zhǎng)寫(xiě)數(shù)學(xué)卷面分析總結(jié)與反思
- 新時(shí)代大學(xué)生勞動(dòng)教育智慧樹(shù)知到期末考試答案章節(jié)答案2024年江西中醫(yī)藥大學(xué)
- 醫(yī)院食堂餐飲服務(wù)方案(2篇)
- 《SketchUp三維輔助設(shè)計(jì)》課件-05 SketchUp基本編輯工具
- 人教版 年六年級(jí)數(shù)學(xué)上冊(cè)教案(全冊(cè))
- 六年級(jí)數(shù)學(xué)上冊(cè)知識(shí)目標(biāo)雙向細(xì)目表
- 《墻繪表現(xiàn)》課件-1-2《墻繪藝術(shù)介紹》
- 瓶裝液化石油氣充裝規(guī)范
- 項(xiàng)目部交通安全管理實(shí)施細(xì)則
- 中國(guó)浸漬紙行業(yè)發(fā)展分析及投資前景預(yù)測(cè)研究報(bào)告
- 2024川渝高竹新區(qū)管理委員招聘筆試參考題庫(kù)附帶答案詳解
評(píng)論
0/150
提交評(píng)論