版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡介
第二次和第三次課合訂單純形法第1頁,共42頁,2023年,2月20日,星期一一、基本思想從標(biāo)準(zhǔn)型的LP模型的一個(gè)基可行解出發(fā),判斷是否是最優(yōu)。如果是最優(yōu)解,結(jié)束運(yùn)算;否則,設(shè)法找到一個(gè)更優(yōu)(目標(biāo)函數(shù)值減?。┑幕究尚薪狻H绱死^續(xù),經(jīng)過有限次迭代代,就可以找到LP的最優(yōu)解或判別LP問題有沒有最優(yōu)解。第三節(jié)單純形法(Simplexmethod)(1947)G.B.Dantzig第2頁,共42頁,2023年,2月20日,星期一找出一個(gè)初始基本可行解是否最優(yōu)轉(zhuǎn)移到另一個(gè)基本可行解(找出更小的目標(biāo)函數(shù)值)最優(yōu)解是否循環(huán)結(jié)束基本思想框圖如何找初始基本可行解?如何判斷是否最優(yōu)解?如何轉(zhuǎn)換基本可行解?第3頁,共42頁,2023年,2月20日,星期一
求回顧上一節(jié)例1:的一個(gè)基本解和一個(gè)基本可行解.第4頁,共42頁,2023年,2月20日,星期一解:約束方程的增廣矩陣為:x2
x4注意到A是2×4矩陣,r(A)=2.由于第2列和第4列線性無關(guān),構(gòu)成一個(gè)2階單位子塊,因此可構(gòu)成一個(gè)基矩陣.取為基變量,為自由變量,用自由變量表表示基變量得如下同解方程組:第5頁,共42頁,2023年,2月20日,星期一又因5>0,6>0,該解顯然非負(fù),因此這個(gè)解也是一個(gè)基本可行解。x2
x4第6頁,共42頁,2023年,2月20日,星期一基變量取為其他變量的情況若取為基變量,為自由變量,由于基本解中自由變量全取零,所以只需對第一列,第二列以及常數(shù)項(xiàng)列組成的矩陣初等行變換至行最簡形:由此可得基本解:又因3>0,8>0,該解顯然非負(fù),因此這個(gè)解也是一個(gè)基本可行解。第7頁,共42頁,2023年,2月20日,星期一結(jié)論:
若系數(shù)矩陣A中存在m階單位子塊,得到基本可行解之后,如何判斷它是否是最優(yōu)解呢?
設(shè)約束線性方程組AX=b的系數(shù)矩陣A的秩R(A)=m,則有如下結(jié)論成立:記增廣矩陣為(A,b),其中,基變量的取值為單位子塊中1所對應(yīng)的右邊常數(shù)項(xiàng)非負(fù),且對應(yīng)的常數(shù)那么從增廣矩陣中便可讀出一個(gè)基本可行解.項(xiàng)的值,自由變量取值全為零.第8頁,共42頁,2023年,2月20日,星期一該解是否最優(yōu)呢?將代入目標(biāo)函數(shù)表達(dá)式中消去得注意到的系數(shù)為-10<0,而可行域中可見,當(dāng)時(shí),目標(biāo)函數(shù)值減小,所以不是最優(yōu)解.思考:若此時(shí)目標(biāo)函數(shù)中自由變量的系數(shù)均大于零,那么這個(gè)解是否是最優(yōu)解?第9頁,共42頁,2023年,2月20日,星期一1.單純形表中心部位
A
右列
b
底行(檢驗(yàn)行)
0
右下端目標(biāo)函數(shù)中常數(shù)項(xiàng)的相反數(shù)目標(biāo)函數(shù)中變量的系數(shù)底線二、單純形表及容許的運(yùn)算r(A)=m第10頁,共42頁,2023年,2月20日,星期一2.容許運(yùn)算中心部位Ab右列底行
0右下端1)底線以上的行可進(jìn)行初等行變換(三種);2)底線以上的行乘常數(shù)后加至底行(包括右下端).底線使表具備下面四個(gè)特點(diǎn):①
②
③④第11頁,共42頁,2023年,2月20日,星期一3.終止條件(最優(yōu)性條件)當(dāng)表格具備如下特點(diǎn):②右列元素非負(fù)①
中心部位具有m階單位子塊③底行中相應(yīng)于單位子塊位置的元素為0(基變量對應(yīng)的底行元素為零)④底行其他元素非負(fù)(自由變量對應(yīng)的元素非負(fù))則從表格中即可讀得LP問題的最優(yōu)解和最優(yōu)值.滿足①②時(shí),可讀出基本可行解滿足①②③時(shí),判斷該解是否最優(yōu).滿足①②③④時(shí),可斷定該基本可行解是最優(yōu)解.第12頁,共42頁,2023年,2月20日,星期一最優(yōu)解(值)的讀法:
單位子塊中1所在列對應(yīng)的變量(基變量)取相應(yīng)右列的值,其余變量(自由變量)取值為零,將它們寫在一起即是一個(gè)最優(yōu)解.而此時(shí)右下端元素的相反數(shù)即為相應(yīng)的最優(yōu)值.第13頁,共42頁,2023年,2月20日,星期一20-41
6-1130
5
1
-3
24
0
20-41
6-1130
5
-10
0
270
-9
的系數(shù)為-10<0滿足①②滿足①②③但④不滿足4.舉例第14頁,共42頁,2023年,2月20日,星期一
以上講述了利用單純形表以及容許運(yùn)算求得一個(gè)基本可行解,并判斷其是否最優(yōu)的方法.
若該基本可行解不是最優(yōu)的,那么如何由當(dāng)前表得到一個(gè)更優(yōu)(對應(yīng)的目標(biāo)函數(shù)值下降)的基本可行解呢?
由上面例題知,取值大于零時(shí),目標(biāo)函數(shù)值下降.這就意味著將成為基變量,不再是自由變量;那么中至少一個(gè)將由基變量變?yōu)樽杂勺兞?單純形法的后半部分討論的主要內(nèi)容.當(dāng)前基本可行解不是最優(yōu)怎么辦?第15頁,共42頁,2023年,2月20日,星期一設(shè)當(dāng)前表格已具備①②③三個(gè)特點(diǎn),但④不滿足:三、基可行解的轉(zhuǎn)換1)進(jìn)基變量的確定對應(yīng)的取為進(jìn)基變量;從底行中任選一個(gè)負(fù)元素,比如第16頁,共42頁,2023年,2月20日,星期一2)離基變量的確定“最小比例原則”也稱
原則選取一個(gè),記為
從所選元素所在的列(第j列)底線以上的正元素中按其中:3)進(jìn)行旋轉(zhuǎn)運(yùn)算利用容許的運(yùn)算將變?yōu)?,該列其它元素(包括底行相應(yīng)的元素)變?yōu)?,從而實(shí)現(xiàn)將變?yōu)榛兞康哪康?第17頁,共42頁,2023年,2月20日,星期一1.單純形法的迭代步驟1)將問題化為標(biāo)準(zhǔn)型,寫出相應(yīng)的表格;2)建立滿足①②③三個(gè)特點(diǎn)的初始單純形表:若1)對應(yīng)的表格滿足①②③,直接進(jìn)入第3)步;若1)對應(yīng)的表格滿足①②,但③不滿足,則利用將底行以上行的若干倍數(shù)加到底行,使③滿足;若1)對應(yīng)的表格不滿足①②,則借助大M法(下一節(jié)的內(nèi)容)使①②滿足,然后再使③滿足.四、單純形算法及應(yīng)用第18頁,共42頁,2023年,2月20日,星期一3)若底行元素全非負(fù),則得到最優(yōu)解,結(jié)束運(yùn)算;否則轉(zhuǎn)4).4)確定進(jìn)基變量對應(yīng)的取為進(jìn)基變量;從底行中任選一個(gè)負(fù)元素,比如令5)確定離基變量從所選元素所在的列(第j列)底線以上的正元素中按第19頁,共42頁,2023年,2月20日,星期一“最小比例原則”選取一個(gè),記為其中:6)進(jìn)行旋轉(zhuǎn)運(yùn)算利用容許的運(yùn)算將變?yōu)?,該列其它元素變?yōu)?,從而實(shí)現(xiàn)將變?yōu)榛兞康哪康?7)觀察得到的新表(滿足①②③).若底行所有元素均非負(fù),則已得最優(yōu)解,結(jié)束運(yùn)算;否則,返回第4)步.第20頁,共42頁,2023年,2月20日,星期一2.例題解析例1.求解LP20-41
6-1130
5
1
-3
24
0
解:該LP已是標(biāo)準(zhǔn)形,故直接列出如下表格:滿足①②為判斷該解是否最優(yōu),利用容許的運(yùn)算使③滿足,得:第21頁,共42頁,2023年,2月20日,星期一
2
0
-4
1
6
-1
1
3
0
5
-10
0
270-9
1
0
-21/23
0
1
11/2800
75
21
滿足①②③但④不滿足滿足①②③④可見此LP有最優(yōu)解最優(yōu)值為第22頁,共42頁,2023年,2月20日,星期一例2.
求解LP解:先化LP為標(biāo)準(zhǔn)形,列出如下表格:第23頁,共42頁,2023年,2月20日,星期一方法一:
-1
1
1
00
2
1
2
0
10
1031001
15
-2
-3
000
0
-1
1
1
00
2
3
0
-2
10
640-101
13
-5
0
300
6
第24頁,共42頁,2023年,2月20日,星期一
0
1
1/31/30
4
1
0
-2/31/3
0
2
0
05/3-4/31
50
0-1/35/3016
010
3/5-1/53
1
0
0
-1/52/54
001-4/53/53
0
0
0
7/5
1/5
17
滿足①②③④第25頁,共42頁,2023年,2月20日,星期一
010
3/5-1/53
1
0
0
-1/52/54
001-4/53/53
0
0
0
7/5
1/5
17
滿足①②③④是化為標(biāo)準(zhǔn)形的LP的最優(yōu)解.
略去松弛變量,故原LP問題的最優(yōu)解為最優(yōu)值為第26頁,共42頁,2023年,2月20日,星期一方法二:取底行中左邊第一個(gè)負(fù)元素對應(yīng)的變量為進(jìn)基變量
-1
1
1
00
2
1
2
0
10
1031001
15
-2
-3
000
0
04/3
1
01/3
7
05/3
01-1/3
5
1
1/3
001/3
5
0-7/3
002/310
第27頁,共42頁,2023年,2月20日,星期一
0
01-4/5
3/5
3
0
103/5
-1/5
3
1
0
0-1/5
1/5
4
0007/51/5
17
滿足①②③④是化為標(biāo)準(zhǔn)形的LP的最優(yōu)解.
略去松弛變量,故原LP問題的最優(yōu)解為最優(yōu)值為第28頁,共42頁,2023年,2月20日,星期一3.注意事項(xiàng)(可能出現(xiàn)的情況)1)若迭代過程中右列元素中出現(xiàn)‘‘0’’元素(此時(shí)對應(yīng)的基本可行解中某基變量的取值為0),那么稱該基本可行解是退化的,接下來的迭代可能出現(xiàn)循環(huán).解決辦法:在每次選進(jìn)基變量時(shí),每次選底行中左邊第一個(gè)負(fù)元素對應(yīng)的變量為進(jìn)基變量,這就是改進(jìn)的單純形法.2)若最終表格中底行元素均非負(fù),且所有自由變量(非基變量)對應(yīng)的底行元素(檢驗(yàn)數(shù))均大于‘‘0’’
,則此時(shí)LP有唯一最優(yōu)解.第29頁,共42頁,2023年,2月20日,星期一3)若最終表格中底行元素均非負(fù),且存在某自由變量(非基變量)對應(yīng)的底行元素(檢驗(yàn)數(shù))等于‘‘0’’
,則此時(shí)LP有無窮多最優(yōu)解.4)若最終表格中底行存在負(fù)元素,且有一個(gè)進(jìn)基變量所在的列中底線以上沒有正元素(無法迭代下去),則此LP問題無最優(yōu)解.以上結(jié)論的證明參見<<運(yùn)籌學(xué)>>清華大學(xué)出版社.第30頁,共42頁,2023年,2月20日,星期一例3.用單純形法求解解:將上述線性規(guī)劃化為標(biāo)準(zhǔn)形:第31頁,共42頁,2023年,2月20日,星期一方法一:
1
1
1
1
00
12
2
1
-1
010
6-130001
9
-1
2
-1000
0
01/2
3/2
1
-1/20
9
1
1/2
-1/201/20
3
07/2
-1/201/21
12
05/2
-3/2
01/20
3
滿足①②③但④不滿足滿足①②③但④不滿足第32頁,共42頁,2023年,2月20日,星期一
0
1/3
1
2/3
-1/30
6
1
2/3
0
1/3
1/30
6
0
11/3
01/3
1/31
15
0
3
0100
12
滿足①②③④略去松弛變量,得原LP最優(yōu)解為
最優(yōu)解:注:由于最終表底行中自由變量
對應(yīng)的系數(shù)為0,
故有無窮多最優(yōu)解,即該最優(yōu)解不是唯一最優(yōu)解。第33頁,共42頁,2023年,2月20日,星期一方法二:
1
1
1
1
00
12
2
1
-1
010
6-130001
9
-1
2
-1000
0
1
1
1
1
00
12
3
2
011
0
18
-13
00
0
1
9
03
0100
12
滿足①②③但④不滿足滿足①②③④第34頁,共42頁,2023年,2月20日,星期一1
1
1
1
00
12
3
2
011
0
18
-13
0
溫馨提示
- 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)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 幼兒園教案說課稿
- 感恩母校演講稿(15篇)
- 紡織品檢測課程設(shè)計(jì)教案
- 親子閱讀活動(dòng)總結(jié)
- XTCLl促銷活動(dòng)的方案
- 初中生防性侵安全教育
- 大班語言游戲教案及教學(xué)反思《手影游戲》
- 庫房出租合同范本
- 基站場地出租合同范文
- 固定資產(chǎn)租賃業(yè)務(wù)合同
- 穿越河流工程定向鉆專項(xiàng)施工方案
- 地球物理學(xué)進(jìn)展投稿須知
- 機(jī)床精度檢驗(yàn)標(biāo)準(zhǔn) VDI3441 a ISO230-2
- 社會主義新農(nóng)村建設(shè)建筑廢料利用探究
- 解析電力施工項(xiàng)目的信息化管理
- 火炬介紹 音速火炬等
- 制劑申請書(共16頁)
- 《質(zhì)量守恒定律》評課稿
- 人教版七年級上冊地理《第4章居民與聚落 第3節(jié)人類的聚居地——聚落》課件
- 對縣委常委班子及成員批評意見范文
- 數(shù)據(jù)中心IDC項(xiàng)目建議書
評論
0/150
提交評論