




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)
文檔簡介
第一章線性規(guī)劃及其擴(kuò)展第5節(jié)單純形法的進(jìn)一步討論
線性規(guī)劃的人工變量法目前有兩種方法:大M法和兩階段法。人工變量法在討論單純形法時,我們總是假定AX=b的系數(shù)矩陣A的秩r(A)=m<n,或者已有一個可行基。但是,在許多問題中,初始可行基是不容易找到的,或者A不滿秩。這樣單純形法就很難進(jìn)行。所以,我們要探討如何尋找第一個可行基?大M法(1)把原問題化為下列形式:其中M是任意大的正數(shù)大M法(2)關(guān)于大M法的幾點注釋:(1)在引入人工變量之前,約束條件已是等式,為了這些等式得到滿足,因此在最優(yōu)解中人工變量取值必須為零;為此在目標(biāo)函數(shù)中人工變量的取值為充分小的負(fù)數(shù),用“-M”代表;(2)若在單純形表中有λj≤0,且存在非零人工變量,則原問題無可行解;若基變量中不再含有非零的人工變量,這表示原問題有解;(3)引入的人工變量個數(shù)越少越好,只要出現(xiàn)單位矩陣作為基陣即可。大M法舉例(1)例解:將原問題化為標(biāo)準(zhǔn)形為:大M法舉例(2)引入的人工變量個數(shù)越少越好引入人工變量y2,y3≥0,由大M法得輔助問題為:其中M為任意大的正數(shù)得上述輔助問題的單純形初表為:大M法舉例(3)
T(B1)XBb
x1x2x3x4x5y2y3x4y2y3419-z’10M1111000-21-10-1100310001-2M-34M10-M00
T(B2)x4
x2
y3
-z’330211-101-21-10-110660403-31
6M6M-304M+1
03M-4M0人工變量優(yōu)先出基大M法舉例(4)
T(B3)XBb
x1x2x3x4x5y2y3x4x2x1031-z’30001-1/21/2-1/2011/30001/3102/301/2-1/21/600303/2-M-3/2-M+1/2
T(B4)x4
x2
x3
-z’00001-1/21/2-1/25/2-1/2100-1/41/41/43/23/20103/4-3/41/4
-3/2-9/200
0-3/4-M+3/4-M-1/4大M法舉例(5)原線性規(guī)劃問題的最優(yōu)解為因為在單純形表T(B4)中,非基變量檢驗數(shù)均小于等于零,且人工變量均為非基變量,取值為零,故原線性規(guī)劃問題達(dá)到最優(yōu)。線性規(guī)劃的兩階段法(1)原線性規(guī)劃問題為第一階段:y1,y2,…,ym稱為人工變量構(gòu)造原(LP)的輔助問題線性規(guī)劃的兩階段法(2)原(LP)的輔助問題的標(biāo)準(zhǔn)形式為:輔助問題必有最優(yōu)解線性規(guī)劃的兩階段法(初始單純形表1)輔助問題的標(biāo)準(zhǔn)形式的系數(shù)矩陣為:線性規(guī)劃的兩階段法(初始單純形表2)用單純形法求解,最終得到輔助問題的最優(yōu)單純形表T(B*)兩階段法的計算步驟:第二步若w*>0,則原線性規(guī)劃無可行解,停止求解,
否則轉(zhuǎn)第三步.第一步用單純形法求輔助問題的最優(yōu)單純形表T(B*)和最優(yōu)值w*.
第三步T(B*)中基變量中不含人工變量y,則把T(B*)中人工變量所在列劃去,把檢驗數(shù)行用原規(guī)劃的目標(biāo)函數(shù)的系數(shù)替代再把基變量的檢驗數(shù)化為0,即得原規(guī)劃的一個可行基的單純形表.再用單純形法迭代,直到終止.否則轉(zhuǎn)第四步.第四步w*=0,T(B*)中基變量中含有人工變量yr,若yr所在行的對應(yīng)的X系數(shù)全為0,則劃去T(B*)中yr所在行和所在的列,轉(zhuǎn)第三步。否則以某變量xS的系數(shù)brs0為軸心項進(jìn)行換基迭代后轉(zhuǎn)第三步。
線性規(guī)劃的兩階段法舉例(1)例1.用兩階段法求解下列(LP)問題
解:化原問題為標(biāo)準(zhǔn)形式則第一階段的輔助問題為線性規(guī)劃的兩階段法舉例(1-2)
輔助問題的標(biāo)準(zhǔn)形式為則第一階段的初始單純形表
為T(B1)線性規(guī)劃的兩階段法舉例(例1-3)
T(B1)XBb
x1x2x3x4x5x6y2y3x4y2y3643w71111000010-10-101001-100-10111-20-1-100
T(B2)x4
x1
y3
w2012110-10410-10-1010301-100-101301-100-1-10兩階段法舉例(例1-4)
T(B2)x4
XBb
x1x2x3x4x5x6y2y3x1
y3
w2012110-10410-10-1010301-100-101301-100-1-10x2
T(B3)x1y3w2012110-10410-10-1010100-3-1-1-111
100-3-1-1-100
因為輔助問題的最優(yōu)值w*=1>0,則原問題無可行解。線性規(guī)劃的兩階段法例2-1例2用兩階段法解線性規(guī)劃
解:引進(jìn)人工變量y2≥0,建立第一階段的輔助問題為
線性規(guī)劃的兩階段法舉例(例2-2)
輔助問題的標(biāo)準(zhǔn)形式為
則第一階段的初始單純形表
為T(B1)
XB
b
x1x2x3x4y2
x2y2
231/211/2-2/303/203/401
w
33/203/400例2-3
T(B1)x2x1w1011/4-2/3-1/32101/202/300000
T(B2)-1例2-4得w*=0,且基變量中不含有人工變量,則劃去T(B2)中y2所在列,把檢驗數(shù)行用原問題的目標(biāo)函數(shù)的系數(shù)替代再把基變量的檢驗數(shù)化為0,即得第二階段的初始單純形表.
T(B2)c-4-300
XB
b
x1x2x3x4y2
x2x1
12011/4-2/3-1/3101/202/3
w
00
000-1-z110011/4-2例2-5則原問題的一個初始單純形表如下x2
x1
12011/4-2/3101/20-z0011/4-2XBbx1x2x3x4
x2
x3
-z110-1/210-2/3420100-11/200-2原問題最優(yōu)解X*=(0,0,4,0)T原問題最優(yōu)值為z*=0例3-1例3用兩階段法解下列線性規(guī)劃
解:該問題的標(biāo)準(zhǔn)形式為:線性規(guī)劃的兩階段法舉例(例3-2)
輔助問題的標(biāo)準(zhǔn)形式為則第一階段的單純形初表為T(B1)引進(jìn)人工變量y1,y2,y3,建立第一階段的輔助問題為:例3-3
XB
bx1x2x3x4y1y2y3
y1y2y3
121-1110100110101020-11001
w
4
2
202000
T(B1)y1y2w3/2011/21/2101/23/2011/21/201-1/2302110
T(B2)0x11/210-1/21/2001/2-1例3-4
XB
bx1x2x3x4y1y2y3
y1y2x1
3/23/21/2011/21/2101/2011/21/201-1/210-1/21/2001/2
w
3
021100-1
T(B2)x2y2w3/2011/21/2101/200000-11-1000000
T(B3)0x11/210-1/21/2001/2-2例3-5x2y2w3/2011/21/2101/200000-11-1000000
T(B3)0x11/210-1/21/2001/2-2c2100得w*=0,T(B3)中基變量中含有人工變量y2,且y2所在行的對應(yīng)的X系數(shù)全為0,則劃去T(B3)中y2所在行,此時,基變量中不再含有人工變量,則劃去T(B3)中人工變量所在列,把檢驗數(shù)行用原問題的標(biāo)準(zhǔn)形式的目標(biāo)函數(shù)的系數(shù)替代再把
溫馨提示
- 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)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 【正版授權(quán)】 ISO/TR 41019:2024 EN Facility managements role in sustainability,resilience and adaptability
- 2025年度校園基礎(chǔ)設(shè)施裝修改造工程合同
- 2025年度房產(chǎn)居間合同:旅游地產(chǎn)項目開發(fā)合作協(xié)議
- 2025年度標(biāo)前協(xié)議模板:XX基礎(chǔ)設(shè)施建設(shè)合作前期協(xié)議
- 2025年度酒店客房預(yù)訂客戶投訴處理合同
- 2025年度博物館安防監(jiān)控設(shè)備采購與安裝合同
- 學(xué)期班級教學(xué)活動工作任務(wù)計劃
- 學(xué)期閱讀推廣活動計劃
- 社區(qū)文藝活動計劃
- 生物教育在新時代的挑戰(zhàn)與機(jī)遇計劃
- 2024全國各省高考詩歌鑒賞真題及解析
- 高考日語閱讀理解練習(xí)2篇-高考日語復(fù)習(xí)
- 印刷基礎(chǔ)知識培訓(xùn)資料
- NB/T 11536-2024煤礦帶壓開采底板井下注漿加固改造技術(shù)規(guī)范
- 2024-2025學(xué)年人教版五年級(上)英語寒假作業(yè)(一)
- 【課件】九年級化學(xué)下冊(人教版2024)-【新教材解讀】義務(wù)教育教材內(nèi)容解讀課件
- 醫(yī)院臨床科研大數(shù)據(jù)平臺方案
- 2024年北京市中考生物真題卷及答案解析
- GA/T 761-2024停車庫(場)安全管理系統(tǒng)技術(shù)要求
- (2024)湖南省公務(wù)員考試《行測》真題卷及答案解析
- 2025年部編教材的網(wǎng)絡(luò)培訓(xùn)心得體會
評論
0/150
提交評論