




已閱讀5頁(yè),還剩20頁(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)介
,整數(shù)規(guī)劃 制作:傅明睿,Mathematical modeling,整數(shù)規(guī)劃是什么?,規(guī)劃中的變量(部分或全部)限制為整數(shù)時(shí),稱為整數(shù)規(guī)劃。若在線性規(guī)劃模型中,變量限制為整數(shù),則稱為整數(shù)線性規(guī)劃。目前所流行的求解整數(shù)規(guī)劃的方法,往往只適用于整數(shù)線性規(guī)劃。目前還沒(méi)有一種方法能有效地求解一切整數(shù)規(guī)劃。,Mathematical modeling,整數(shù)規(guī)劃的分類,變量全限制為整數(shù)時(shí),稱純(完全)整數(shù)規(guī)劃。 變量部分限制為整數(shù)的,稱混合整數(shù)規(guī)劃。 變量只能取0或1時(shí),稱之為0-1整數(shù)規(guī)劃。,Mathematical modeling,整數(shù)規(guī)劃模型的建立 整數(shù)規(guī)劃模型的求解 完全枚舉法 分支定界法 割平面法 0-1數(shù)規(guī)劃模整型,Mathematical modeling,例1 集裝箱運(yùn)貨問(wèn)題: 已知甲乙兩種貨物的裝運(yùn)和獲利情況如下表所示,問(wèn):甲乙兩貨物各托運(yùn)多少箱,可使獲得利潤(rùn)最大?,Mathematical modeling,解:設(shè) 為甲乙兩貨物各托運(yùn)箱數(shù),Mathematical modeling,(1) 原線性規(guī)劃有最優(yōu)解,當(dāng)自變量限制為整數(shù)后,其整數(shù)規(guī)劃解出現(xiàn)下述情況: a原線性規(guī)劃最優(yōu)解全是整數(shù),則整數(shù)規(guī)劃最優(yōu)解與線性規(guī)劃最優(yōu)解一致。 b原線性規(guī)劃最優(yōu)解不全是整數(shù),則整數(shù)規(guī)劃最優(yōu)解小于原線性規(guī)劃最優(yōu)解(max)或整數(shù)規(guī)劃最優(yōu)解大于原線性規(guī)劃最優(yōu)解(min)。,Mathematical modeling,例2 今有一臺(tái)機(jī)器將一周生產(chǎn)的兩種型號(hào)的冷飲杯存儲(chǔ)在150立方米的儲(chǔ)藏室 里,并同時(shí)進(jìn)行出售.已知這臺(tái)機(jī)器能在6小時(shí)內(nèi)生產(chǎn)一百箱號(hào)杯,5小時(shí)內(nèi)生產(chǎn)一百箱號(hào)杯,生產(chǎn)以百箱為單位計(jì)算,預(yù)計(jì)每周生產(chǎn)60小時(shí).如果號(hào)杯每百箱占體積10立方米,每百箱可獲利潤(rùn)500元,每周售出數(shù)量不會(huì)超過(guò)800箱;號(hào)杯每百箱占體積20立方米, 每百箱可獲利潤(rùn)450元,每周售出數(shù)量不受限制.為保證總收益為最大,每周應(yīng)安排生產(chǎn)、號(hào)杯各多少百箱?,Mathematical modeling,解: 設(shè)每周生產(chǎn)、號(hào)杯各 百箱,則有如下數(shù)學(xué)模型,返回,Mathematical modeling,例3:設(shè)整數(shù)規(guī)劃問(wèn)題如下,完全枚舉法,Mathematical modeling,現(xiàn)求整數(shù)解(最優(yōu)解):如用“舍入取整法”可得到4個(gè)點(diǎn)即(1,3) (2,3)(1,4)(2,4)。顯然,它們都不可能是整數(shù)規(guī)劃的最優(yōu)解。 故按整數(shù)規(guī)劃約束條件,其可行解肯定在線性規(guī)劃問(wèn)題的可行域內(nèi)且為整數(shù)點(diǎn)。故整數(shù)規(guī)劃問(wèn)題的可行解集是一個(gè)有限集,如圖所示。,求得(2,2)(3,1)點(diǎn)為最大值,。 在求解整數(shù)規(guī)劃問(wèn)題時(shí),可將集合內(nèi)的整數(shù)點(diǎn)一一找出,其最大目標(biāo)函數(shù)的值為最優(yōu)解,此法為完全枚舉法。,返回,Mathematical modeling,對(duì)有約束條件的最優(yōu)化問(wèn)題(其可行解為有限數(shù))的所有可行解空間恰當(dāng)?shù)剡M(jìn)行系 統(tǒng)搜索,這就是分枝與定界內(nèi)容。通常,把全部可行解空間反復(fù)地分割為越來(lái)越小的子 集,稱為分枝;并且對(duì)每個(gè)子集內(nèi)的解集計(jì)算一個(gè)目標(biāo)下界(對(duì)于最小值問(wèn)題),這稱 為定界。在每次分枝后,凡是界限超出已知可行解集目標(biāo)值的那些子集不再進(jìn)一步分枝,這樣,許多子集可不予考慮,這稱剪枝。這就是分枝定界法的主要思路。,分支定界法,Mathematical modeling,例4 用分支定界法求以下整數(shù)規(guī)劃,Mathematical modeling,Mathematical modeling,開(kāi)始,V0 X1=2.25,X2=3.75;Z0=41.25,X23,X24,V1 X1=3,X2=3,Z2=39,V2 X1=1.8,X2=4,Z1=41,X12,X11,V3 X1=1,X2=4.44, Z4=40.56,V6 X1=0,X2=5,Z6=40,V5 X1=1,X2=4,Z5=37,V4 不可行,X24,X25,Mathematical modeling,0-1整數(shù)規(guī)劃,1.什么是0-1整數(shù)規(guī)劃? 2.什么時(shí)候采用0-1整數(shù)規(guī)劃法?,0-1 整數(shù)規(guī)劃是一種特殊形式的整數(shù)規(guī)劃,這時(shí)的決策變量xi 只取兩個(gè)值0或1,一般的解法為隱枚舉法。,正如計(jì)算機(jī)只懂得0,1兩個(gè)數(shù),1代表是,0代表否。同樣的,在0-1整數(shù)規(guī)劃中的0和1并不是真真意義上的數(shù),而是一個(gè)衡量事件是否發(fā)生的標(biāo)準(zhǔn)。一般來(lái)說(shuō),我們?cè)趶亩鄠€(gè)事物中選出其中一部分,在一定的條件下求解最優(yōu)情況時(shí)可以采用0-1整數(shù)規(guī)劃法。,Mathematical modeling,例5一個(gè)旅行者要到某地作兩周的帶包旅行,裝背包時(shí),他發(fā)現(xiàn)除了已裝的必需物件外,他還能再裝5公斤重的東西.他打算從下列4種東西中選取,使增加的重量不超過(guò)5公斤又能使使用價(jià)值最大.這4種東西的重量和使用價(jià)值(這里用打分?jǐn)?shù)的辦法表示價(jià)值)如下表所示,問(wèn)旅行者應(yīng)該選取哪些物件為好?,Mathematical modeling,解:建立模型為,Mathematical modeling,Mathematical modeling,由上表可知,問(wèn)題的最優(yōu)解為 X*=( x1 =1 x2=0 x3=1 ) 但此法太繁瑣,工作量相當(dāng)大。而隱枚舉法就是在此基礎(chǔ)上,通過(guò)加入一定的條件,就能較快的求得最優(yōu)解: 找到x1 =0 x2=0 x3=1 是一個(gè)可行解,為盡快找到最優(yōu)解,可將3 x12 x25 x3 5 作為一個(gè)約束,凡是目標(biāo)函數(shù)值小于5 的組合不必討論,如下表。,Mathematical modeling,例6 求解下列0-1規(guī)劃問(wèn)題,Mathematical modeling,解:對(duì)于0-1 規(guī)劃問(wèn)題,由于每個(gè)變量只取0,1兩個(gè)值,一般會(huì)用窮舉法來(lái)解,即將所有的0,1 組合找出,使目標(biāo)函數(shù)達(dá)到極值要求就可求得最優(yōu)解。,Mathematical modeling,例7(指派問(wèn)題) 有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ù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(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ì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 自我鼓勵(lì)的培訓(xùn)
- 2025年法律職業(yè)資格考試試題及答案示例
- 重癥哮喘護(hù)理指南解讀
- 牙周護(hù)理新手教程
- 室外氣象參數(shù)表
- 農(nóng)業(yè)科技應(yīng)用與農(nóng)業(yè)經(jīng)濟(jì)分析題
- 投資入股協(xié)議及合作經(jīng)營(yíng)合同
- 2025年貴州出租車資格證考試模擬試題
- 那場(chǎng)雨后的彩虹美麗的自然景觀寫(xiě)景6篇范文
- 讀小王子有感經(jīng)典讀物讀后感14篇
- 2024年貴州省黎平縣事業(yè)單位公開(kāi)招聘醫(yī)療衛(wèi)生崗筆試題帶答案
- 《關(guān)于智能家居系統(tǒng)》課件
- 公司財(cái)務(wù)培訓(xùn)試題及答案
- 煤礦重大災(zāi)害治理頂層設(shè)計(jì)方案
- 2024-2025學(xué)年江蘇省蘇州市張家港市梁豐高中春海創(chuàng)優(yōu)部八年級(jí)(下)期中檢測(cè)數(shù)學(xué)試卷(含答案)
- 2025年北京市高中學(xué)業(yè)水平合格考試歷史試卷真題(含答案詳解)
- 2025年春季高一年級(jí)入學(xué)考試英語(yǔ)試卷
- 剖宮產(chǎn)手術(shù)圍手術(shù)期預(yù)防用抗菌藥物管理實(shí)施細(xì)則
- 2025年心電圖機(jī)使用說(shuō)明標(biāo)準(zhǔn)課件
- 考官Simon雅思大作文范文
- 國(guó)內(nèi)外數(shù)智賦能課程教改的現(xiàn)狀與趨勢(shì)
評(píng)論
0/150
提交評(píng)論