




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡介
1、 Mathematical modeling2整數(shù)規(guī)劃是什么整數(shù)規(guī)劃是什么?規(guī)劃中的變量(部分或全部)限制為整數(shù)時(shí),稱為整數(shù)規(guī)規(guī)劃中的變量(部分或全部)限制為整數(shù)時(shí),稱為整數(shù)規(guī)劃。若在線性規(guī)劃模型中,變量限制為整數(shù),則稱為整數(shù)劃。若在線性規(guī)劃模型中,變量限制為整數(shù),則稱為整數(shù)線性規(guī)劃。目前所流行的求解整數(shù)規(guī)劃的方法,往往只適線性規(guī)劃。目前所流行的求解整數(shù)規(guī)劃的方法,往往只適用于整數(shù)線性規(guī)劃。目前還沒有一種方法能有效地求解一用于整數(shù)線性規(guī)劃。目前還沒有一種方法能有效地求解一切整數(shù)規(guī)劃。切整數(shù)規(guī)劃。Mathematical modeling3整數(shù)規(guī)劃的分類整數(shù)規(guī)劃的分類變量全限制為整數(shù)時(shí),稱純(完
2、全)整數(shù)規(guī)劃。變量全限制為整數(shù)時(shí),稱純(完全)整數(shù)規(guī)劃。變量部分限制為整數(shù)的,稱混合整數(shù)規(guī)劃。變量部分限制為整數(shù)的,稱混合整數(shù)規(guī)劃。變量只能取變量只能取0或或1時(shí),稱之為時(shí),稱之為0-1整數(shù)規(guī)劃。整數(shù)規(guī)劃。Mathematical modeling4整數(shù)規(guī)劃模型的建立整數(shù)規(guī)劃模型的建立整數(shù)規(guī)劃模型的求解整數(shù)規(guī)劃模型的求解 完全枚舉法完全枚舉法 分支定界法分支定界法 割平面法割平面法0-1數(shù)規(guī)劃模整型數(shù)規(guī)劃模整型Mathematical modeling5例1 集裝箱運(yùn)貨問題:已知甲乙兩種貨物的裝運(yùn)和獲利情況如下表所示,問:甲乙兩貨物各托運(yùn)多少箱,可使獲得利潤最大?Mathematical mo
3、deling6且為整數(shù)0,135224451020max21212121xxxxxxxxz解:設(shè)解:設(shè) 為甲乙兩貨物各托運(yùn)箱數(shù)為甲乙兩貨物各托運(yùn)箱數(shù)12,x xMathematical modeling7(1) 原線性規(guī)劃有最優(yōu)解,當(dāng)自變量限制為原線性規(guī)劃有最優(yōu)解,當(dāng)自變量限制為整數(shù)后,其整數(shù)規(guī)劃解出現(xiàn)下述情況:整數(shù)后,其整數(shù)規(guī)劃解出現(xiàn)下述情況: a原線性規(guī)劃最優(yōu)解全是整數(shù),則整數(shù)規(guī)原線性規(guī)劃最優(yōu)解全是整數(shù),則整數(shù)規(guī)劃最優(yōu)解與線性規(guī)劃最優(yōu)解一致。劃最優(yōu)解與線性規(guī)劃最優(yōu)解一致。 b原線性規(guī)劃最優(yōu)解不全是整數(shù),則整數(shù)原線性規(guī)劃最優(yōu)解不全是整數(shù),則整數(shù)規(guī)劃最優(yōu)解小于原線性規(guī)劃最優(yōu)解(規(guī)劃最優(yōu)解小于原
4、線性規(guī)劃最優(yōu)解(max)或整數(shù)規(guī)劃最優(yōu)解大于原線性規(guī)劃最優(yōu)解或整數(shù)規(guī)劃最優(yōu)解大于原線性規(guī)劃最優(yōu)解(min)。)。Mathematical modeling8例例2 今有一臺機(jī)器將一周生產(chǎn)的兩種型號的冷飲杯今有一臺機(jī)器將一周生產(chǎn)的兩種型號的冷飲杯存儲在存儲在150立方米的儲藏室立方米的儲藏室 里里,并同時(shí)進(jìn)行出售并同時(shí)進(jìn)行出售.已已知這臺機(jī)器能在知這臺機(jī)器能在6小時(shí)內(nèi)生產(chǎn)一百箱小時(shí)內(nèi)生產(chǎn)一百箱號杯號杯,5小時(shí)內(nèi)小時(shí)內(nèi)生產(chǎn)一百箱生產(chǎn)一百箱號杯號杯,生產(chǎn)以百箱為單位計(jì)算生產(chǎn)以百箱為單位計(jì)算,預(yù)計(jì)每預(yù)計(jì)每周生產(chǎn)周生產(chǎn)60小時(shí)小時(shí).如果如果號杯每百箱占體積號杯每百箱占體積10立方米立方米,每百箱可獲利潤
5、每百箱可獲利潤500元元,每周售出數(shù)量不會超過每周售出數(shù)量不會超過800箱箱;號杯每百箱占體積號杯每百箱占體積20立方米立方米, 每百箱可獲利潤每百箱可獲利潤450元元,每周售出數(shù)量不受限制每周售出數(shù)量不受限制.為保證總收益為最大為保證總收益為最大,每周應(yīng)安排生產(chǎn)每周應(yīng)安排生產(chǎn)、號杯各多少百箱?號杯各多少百箱?Mathematical modeling912,x x解解: 設(shè)每周生產(chǎn)設(shè)每周生產(chǎn)、號杯各號杯各 百箱百箱,則有如下則有如下數(shù)學(xué)模型數(shù)學(xué)模型且為整數(shù)0,815020106056450500max211212121xxxxxxxxxz返回返回Mathematical modeling10
6、例例3:設(shè)整數(shù)規(guī)劃問題如下:設(shè)整數(shù)規(guī)劃問題如下 且為整數(shù)0,13651914max21212121xxxxxxxxz完全枚舉法完全枚舉法Mathematical modeling11 現(xiàn)求整數(shù)解(最優(yōu)解):現(xiàn)求整數(shù)解(最優(yōu)解):如用如用“舍入取整法舍入取整法”可得到可得到4個(gè)點(diǎn)即個(gè)點(diǎn)即(1,3) (2,3)(1,4)(2,4)。顯然,它們都不。顯然,它們都不可能是整數(shù)規(guī)劃的最優(yōu)解。可能是整數(shù)規(guī)劃的最優(yōu)解。 故故按整數(shù)規(guī)劃約束條件,按整數(shù)規(guī)劃約束條件,其可行解肯定在線性規(guī)劃其可行解肯定在線性規(guī)劃問題的可行域內(nèi)且為整數(shù)問題的可行域內(nèi)且為整數(shù)點(diǎn)。故整數(shù)規(guī)劃問題的可點(diǎn)。故整數(shù)規(guī)劃問題的可行解集是一個(gè)有
7、限集,如行解集是一個(gè)有限集,如圖所示。圖所示。 求得求得(2,2)()(3,1)點(diǎn)為最大值,。點(diǎn)為最大值,。 在求解整數(shù)規(guī)劃問題時(shí),可將集合內(nèi)的整數(shù)點(diǎn)一一找出,在求解整數(shù)規(guī)劃問題時(shí),可將集合內(nèi)的整數(shù)點(diǎn)一一找出,其最大目標(biāo)函數(shù)的值為最優(yōu)解,此法為其最大目標(biāo)函數(shù)的值為最優(yōu)解,此法為完全枚舉法完全枚舉法。返回返回Mathematical modeling12對有約束條件的最優(yōu)化問題(其可行解為有限數(shù))對有約束條件的最優(yōu)化問題(其可行解為有限數(shù))的所有可行解空間恰當(dāng)?shù)剡M(jìn)行系的所有可行解空間恰當(dāng)?shù)剡M(jìn)行系統(tǒng)搜索,這就是分枝與定界內(nèi)容。通常,把全部可統(tǒng)搜索,這就是分枝與定界內(nèi)容。通常,把全部可行解空間反復(fù)地
8、分割為越來越小的子行解空間反復(fù)地分割為越來越小的子集,稱為分枝;并且對每個(gè)子集內(nèi)的解集計(jì)算一個(gè)集,稱為分枝;并且對每個(gè)子集內(nèi)的解集計(jì)算一個(gè)目標(biāo)下界(對于最小值問題),這稱目標(biāo)下界(對于最小值問題),這稱為定界。在每次分枝后,凡是界限超出已知可行解為定界。在每次分枝后,凡是界限超出已知可行解集目標(biāo)值的那些子集不再進(jìn)一步分枝集目標(biāo)值的那些子集不再進(jìn)一步分枝,這樣,許多這樣,許多子集可不予考慮,這稱剪枝。這就是分枝定界法的子集可不予考慮,這稱剪枝。這就是分枝定界法的主要思路。主要思路。分支定界法分支定界法Mathematical modeling13 例例4 用分支定界法求以下整數(shù)規(guī)劃用分支定界法求
9、以下整數(shù)規(guī)劃1212122max5865945,0 xzxxxxxxxx且為整數(shù)Mathematical modeling141x2xMathematical modeling15開始開始V0 X1=2.25,X2=3.75;Z0=41.25X23X24V1 X1=3,X2=3,Z2=39V2 X1=1.8,X2=4,Z1=41X12X11V3 X1=1,X2=4.44, Z4=40.56V6 X1=0,X2=5,Z6=40V5 X1=1,X2=4,Z5=37V4 不可行不可行X24X25Mathematical modeling16 0-1整數(shù)規(guī)劃整數(shù)規(guī)劃1.什么是什么是0-1整數(shù)規(guī)劃?整數(shù)
10、規(guī)劃?2.什么時(shí)候采用什么時(shí)候采用0-1整數(shù)規(guī)劃法?整數(shù)規(guī)劃法?0-1 整數(shù)規(guī)劃是一種特殊形式的整數(shù)規(guī)劃,整數(shù)規(guī)劃是一種特殊形式的整數(shù)規(guī)劃,這時(shí)的決策變量這時(shí)的決策變量xi 只取兩個(gè)值只取兩個(gè)值0或或1,一般的解,一般的解法為隱枚舉法。法為隱枚舉法。正如計(jì)算機(jī)只懂得正如計(jì)算機(jī)只懂得0,1兩個(gè)數(shù),兩個(gè)數(shù),1代表是,代表是,0代代表否。同樣的,在表否。同樣的,在0-1整數(shù)規(guī)劃中的整數(shù)規(guī)劃中的0和和1并不是并不是真真意義上的數(shù),而是一個(gè)衡量事件是否發(fā)生真真意義上的數(shù),而是一個(gè)衡量事件是否發(fā)生的標(biāo)準(zhǔn)。一般來說,我們在從多個(gè)事物中選出的標(biāo)準(zhǔn)。一般來說,我們在從多個(gè)事物中選出其中一部分,在一定的條件下求解
11、最優(yōu)情況時(shí)其中一部分,在一定的條件下求解最優(yōu)情況時(shí)可以采用可以采用0-1整數(shù)規(guī)劃法。整數(shù)規(guī)劃法。Mathematical modeling17例例5一個(gè)旅行者要到某地作兩周的帶包旅行一個(gè)旅行者要到某地作兩周的帶包旅行,裝背包時(shí)裝背包時(shí),他發(fā)他發(fā)現(xiàn)除了已裝的必需物件外現(xiàn)除了已裝的必需物件外,他還能再裝他還能再裝5公斤重的東西公斤重的東西.他打他打算從下列算從下列4種東西中選取種東西中選取,使增加的重量不超過使增加的重量不超過5公斤又能使公斤又能使使用價(jià)值最大使用價(jià)值最大.這這4種東西的重量和使用價(jià)值種東西的重量和使用價(jià)值(這里用打分?jǐn)?shù)這里用打分?jǐn)?shù)的辦法表示價(jià)值的辦法表示價(jià)值)如下表所示如下表所示
12、,問旅行者應(yīng)該選取哪些物件為問旅行者應(yīng)該選取哪些物件為好?好?Mathematical modeling18解:建立模型為解:建立模型為12341234max Z=6x7392345s.t. 0,11,2,3,4ixxxxxxxxiMathematical modeling19Mathematical modeling20由上表可知,問題的最優(yōu)解為由上表可知,問題的最優(yōu)解為 X*=( x1=1x2=0 x3=1 ) 但此法但此法太繁瑣,工作量相當(dāng)大。而隱枚舉法就是在此基礎(chǔ)上,通過加太繁瑣,工作量相當(dāng)大。而隱枚舉法就是在此基礎(chǔ)上,通過加入一定的條件,就能較快的求得最優(yōu)解:入一定的條件,就能較快的
13、求得最優(yōu)解: 找到找到x1=0 x2=0 x3=1 是一個(gè)可行解,為盡快找到最優(yōu)解,可將是一個(gè)可行解,為盡快找到最優(yōu)解,可將3 x12x25 x3 5 作為一個(gè)約束,凡是目標(biāo)函數(shù)值小于作為一個(gè)約束,凡是目標(biāo)函數(shù)值小于5 的組合不必討論,的組合不必討論,如下表。如下表。Mathematical modeling21例例6 求解下列求解下列0-1規(guī)劃問題規(guī)劃問題1231231231223123max32522 (1)44 (2). . 3 (3) 46 (4),01Zxxxxxxxxxstxxxxx x x或Mathematical modeling22解:對于解:對于0- -1 規(guī)劃問題,由于每個(gè)變量只取規(guī)劃問題,由于每個(gè)變量只取0,1兩個(gè)值,一兩個(gè)值,一般會用窮舉法來解,即將所有的般會用窮舉法來解,即將所有的0,1 組合找出,使目標(biāo)函數(shù)組合找出,使目標(biāo)函數(shù)達(dá)到極值要求就可求得最優(yōu)解。達(dá)到極值要求就可求得最優(yōu)解。Mathematical modeling23例例7(指派問題指派問題) 有有5個(gè)工人,要分派他們分別完個(gè)工人,要分派他們分別完成成5項(xiàng)工作,每人做各項(xiàng)工作所消耗的時(shí)間如下項(xiàng)工作,每人做各項(xiàng)工作所消耗的時(shí)間如下表,問應(yīng)如何安排工作,可使總的消耗時(shí)間最表,問應(yīng)如何安排工作,可使總的消耗時(shí)間最??????Mathematical modeling2410,1,2,5ijijxi j
溫馨提示
- 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)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 2025至2030中國電動(dòng)潔面儀行業(yè)產(chǎn)業(yè)運(yùn)行態(tài)勢及投資規(guī)劃深度研究報(bào)告
- 2025至2030中國甲基異丁基甲酮行業(yè)產(chǎn)業(yè)運(yùn)行態(tài)勢及投資規(guī)劃深度研究報(bào)告
- 2025至2030中國生日蠟燭行業(yè)產(chǎn)業(yè)運(yùn)行態(tài)勢及投資規(guī)劃深度研究報(bào)告
- 2025至2030中國甘草霜行業(yè)產(chǎn)業(yè)運(yùn)行態(tài)勢及投資規(guī)劃深度研究報(bào)告
- 2025至2030中國特殊群體教育行業(yè)市場深度研究及發(fā)展前景投資可行性分析報(bào)告
- 《護(hù)理值班與交接班制度》考試試題
- 商業(yè)培訓(xùn)的未來之路AR技術(shù)的應(yīng)用與推廣研究
- 培養(yǎng)情緒智力提升學(xué)生綜合能力的關(guān)鍵
- 商業(yè)環(huán)境中技術(shù)風(fēng)險(xiǎn)管理的策略與方法
- 教育數(shù)字化轉(zhuǎn)型的實(shí)踐與探索
- 2023-2024學(xué)年四川省成都市高新區(qū)八年級(下)期末數(shù)學(xué)試卷
- 2025高考全國一卷語文真題
- (高清版)DB13(J)∕T 8556-2023 建設(shè)工程消耗量標(biāo)準(zhǔn)及計(jì)算規(guī)則(園林綠化工程)
- GB/T 1094.1-2013電力變壓器第1部分:總則
- DB33T 1199-2020 農(nóng)村生活污水處理設(shè)施建設(shè)和改造技術(shù)規(guī)程
- IPQC培訓(xùn)教材
- SAE-J400-2002-中文版
- 高中物理知識點(diǎn)(力學(xué)部分)
- 啤酒生產(chǎn)線控制系統(tǒng)設(shè)計(jì)——灌裝部分
- 地埋管道更換施工組織方案
- 兒科常用藥物劑量換算速查表
評論
0/150
提交評論