




已閱讀5頁,還剩20頁未讀, 繼續(xù)免費(fèi)閱讀
版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)
文檔簡介
,整數(shù)規(guī)劃 制作:傅明睿,Mathematical modeling,整數(shù)規(guī)劃是什么?,規(guī)劃中的變量(部分或全部)限制為整數(shù)時,稱為整數(shù)規(guī)劃。若在線性規(guī)劃模型中,變量限制為整數(shù),則稱為整數(shù)線性規(guī)劃。目前所流行的求解整數(shù)規(guī)劃的方法,往往只適用于整數(shù)線性規(guī)劃。目前還沒有一種方法能有效地求解一切整數(shù)規(guī)劃。,Mathematical modeling,整數(shù)規(guī)劃的分類,變量全限制為整數(shù)時,稱純(完全)整數(shù)規(guī)劃。 變量部分限制為整數(shù)的,稱混合整數(shù)規(guī)劃。 變量只能取0或1時,稱之為0-1整數(shù)規(guī)劃。,Mathematical modeling,整數(shù)規(guī)劃模型的建立 整數(shù)規(guī)劃模型的求解 完全枚舉法 分支定界法 割平面法 0-1數(shù)規(guī)劃模整型,Mathematical modeling,例1 集裝箱運(yùn)貨問題: 已知甲乙兩種貨物的裝運(yùn)和獲利情況如下表所示,問:甲乙兩貨物各托運(yù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 今有一臺機(jī)器將一周生產(chǎn)的兩種型號的冷飲杯存儲在150立方米的儲藏室 里,并同時進(jìn)行出售.已知這臺機(jī)器能在6小時內(nèi)生產(chǎn)一百箱號杯,5小時內(nèi)生產(chǎn)一百箱號杯,生產(chǎn)以百箱為單位計(jì)算,預(yù)計(jì)每周生產(chǎn)60小時.如果號杯每百箱占體積10立方米,每百箱可獲利潤500元,每周售出數(shù)量不會超過800箱;號杯每百箱占體積20立方米, 每百箱可獲利潤450元,每周售出數(shù)量不受限制.為保證總收益為最大,每周應(yīng)安排生產(chǎn)、號杯各多少百箱?,Mathematical modeling,解: 設(shè)每周生產(chǎn)、號杯各 百箱,則有如下數(shù)學(xué)模型,返回,Mathematical modeling,例3:設(shè)整數(shù)規(guī)劃問題如下,完全枚舉法,Mathematical modeling,現(xiàn)求整數(shù)解(最優(yōu)解):如用“舍入取整法”可得到4個點(diǎn)即(1,3) (2,3)(1,4)(2,4)。顯然,它們都不可能是整數(shù)規(guī)劃的最優(yōu)解。 故按整數(shù)規(guī)劃約束條件,其可行解肯定在線性規(guī)劃問題的可行域內(nèi)且為整數(shù)點(diǎn)。故整數(shù)規(guī)劃問題的可行解集是一個有限集,如圖所示。,求得(2,2)(3,1)點(diǎn)為最大值,。 在求解整數(shù)規(guī)劃問題時,可將集合內(nèi)的整數(shù)點(diǎn)一一找出,其最大目標(biāo)函數(shù)的值為最優(yōu)解,此法為完全枚舉法。,返回,Mathematical modeling,對有約束條件的最優(yōu)化問題(其可行解為有限數(shù))的所有可行解空間恰當(dāng)?shù)剡M(jìn)行系 統(tǒng)搜索,這就是分枝與定界內(nèi)容。通常,把全部可行解空間反復(fù)地分割為越來越小的子 集,稱為分枝;并且對每個子集內(nèi)的解集計(jì)算一個目標(biāo)下界(對于最小值問題),這稱 為定界。在每次分枝后,凡是界限超出已知可行解集目標(biāo)值的那些子集不再進(jìn)一步分枝,這樣,許多子集可不予考慮,這稱剪枝。這就是分枝定界法的主要思路。,分支定界法,Mathematical modeling,例4 用分支定界法求以下整數(shù)規(guī)劃,Mathematical modeling,Mathematical modeling,開始,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.什么時候采用0-1整數(shù)規(guī)劃法?,0-1 整數(shù)規(guī)劃是一種特殊形式的整數(shù)規(guī)劃,這時的決策變量xi 只取兩個值0或1,一般的解法為隱枚舉法。,正如計(jì)算機(jī)只懂得0,1兩個數(shù),1代表是,0代表否。同樣的,在0-1整數(shù)規(guī)劃中的0和1并不是真真意義上的數(shù),而是一個衡量事件是否發(fā)生的標(biāo)準(zhǔn)。一般來說,我們在從多個事物中選出其中一部分,在一定的條件下求解最優(yōu)情況時可以采用0-1整數(shù)規(guī)劃法。,Mathematical modeling,例5一個旅行者要到某地作兩周的帶包旅行,裝背包時,他發(fā)現(xiàn)除了已裝的必需物件外,他還能再裝5公斤重的東西.他打算從下列4種東西中選取,使增加的重量不超過5公斤又能使使用價值最大.這4種東西的重量和使用價值(這里用打分?jǐn)?shù)的辦法表示價值)如下表所示,問旅行者應(yīng)該選取哪些物件為好?,Mathematical modeling,解:建立模型為,Mathematical modeling,Mathematical modeling,由上表可知,問題的最優(yōu)解為 X*=( x1 =1 x2=0 x3=1 ) 但此法太繁瑣,工作量相當(dāng)大。而隱枚舉法就是在此基礎(chǔ)上,通過加入一定的條件,就能較快的求得最優(yōu)解: 找到x1 =0 x2=0 x3=1 是一個可行解,為盡快找到最優(yōu)解,可將3 x12 x25 x3 5 作為一個約束,凡是目標(biāo)函數(shù)值小于5 的組合不必討論,如下表。,Mathematical modeling,例6 求解下列0-1規(guī)劃問題,Mathematical modeling,解:對于0-1 規(guī)劃問題,由于每個變量只取0,1兩個值,一般會用窮舉法來解,即將所有的0,1 組合找出,使目標(biāo)函數(shù)達(dá)到極值要求就可求得最優(yōu)解。,Mathematical modeling,例7(指派問題) 有5個工人,要分派他們分別
溫馨提示
- 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)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 公司職場內(nèi)活動方案
- 公司組織健身走活動方案
- 公司自制檸檬茶活動方案
- 公司晨會團(tuán)體活動方案
- 2025年統(tǒng)計(jì)學(xué)專業(yè)期末考試試卷及答案
- 2025年經(jīng)濟(jì)法相關(guān)知識考試試題及答案
- 北師大版(2024)七年級下冊英語期末復(fù)習(xí):Unit1~6各單元書面表達(dá)練習(xí)題(含答案+范文)
- 2025年中國冷凍面包產(chǎn)品行業(yè)市場全景分析及前景機(jī)遇研判報告
- 2024年度浙江省二級造價工程師之建設(shè)工程造價管理基礎(chǔ)知識練習(xí)題及答案
- 2024年度浙江省二級注冊建筑師之法律法規(guī)經(jīng)濟(jì)與施工題庫綜合試卷B卷附答案
- 美洲文化課件教學(xué)
- 2025屆重慶市巴川中學(xué)生物七下期末統(tǒng)考試題含解析
- 期末總動員暨誠信教育主題班會
- 醫(yī)學(xué)檢驗(yàn)進(jìn)修匯報
- 2024年貴州省黎平縣事業(yè)單位公開招聘醫(yī)療衛(wèi)生崗筆試題帶答案
- 《關(guān)于智能家居系統(tǒng)》課件
- 公司財(cái)務(wù)培訓(xùn)試題及答案
- 煤礦重大災(zāi)害治理頂層設(shè)計(jì)方案
- 2024-2025學(xué)年江蘇省蘇州市張家港市梁豐高中春海創(chuàng)優(yōu)部八年級(下)期中檢測數(shù)學(xué)試卷(含答案)
- 2025年北京市高中學(xué)業(yè)水平合格考試歷史試卷真題(含答案詳解)
- 2025年春季高一年級入學(xué)考試英語試卷
評論
0/150
提交評論