




版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領
文檔簡介
1、§5.4 01型整數(shù)規(guī)劃模型1、 01型整數(shù)規(guī)劃模型概述整數(shù)規(guī)劃指的是決策變量為非負整數(shù)值的一類線性規(guī)劃,在實際問題的應用中,整數(shù)規(guī)劃模型對應著大量的生產(chǎn)計劃或活動安排等決策問題,整數(shù)規(guī)劃的解法主要有分枝定界解法及割平面解法(這里不作介紹,感興趣的讀者可參考相關書籍)。在整數(shù)規(guī)劃問題中,01型整數(shù)規(guī)劃則是其中較為特殊的一類情況,它要求決策變量的取值僅為0或1,在實際問題的討論中,01型整數(shù)規(guī)劃模型也對應著大量的最優(yōu)決策的活動與安排討論,我們將列舉一些模型范例,以說明這個事實。01型整數(shù)規(guī)劃的的數(shù)學模型為:目標函數(shù) 約束條件為:這里,0 | 1表示0或1。2、01型整數(shù)規(guī)劃模型的解法
2、01型整數(shù)規(guī)劃模型的解法一般為窮舉法或隱枚舉法,窮舉法指的是對決策變量的每一個0或1值,均比較其目標函數(shù)值的大小,以從中求出最優(yōu)解。這種方法一般適用于決策變量個數(shù)較小的情況,當較大時,由于個0、1的可能組合數(shù)為,故此時即便用計算機進行窮舉來求最優(yōu)解,也幾乎是不可能的。隱枚舉法是增加了過濾條件的一類窮舉法,該法雖能減少運算次數(shù),但有的問題并不使用。此時,就只能用窮舉法了。3. 應用實例例1 工程上馬的決策問題1)問題的提出 某部門三年內有四項工程可以考慮上馬,每項工程的期望收益和年度費用(千元)如下表所示:假定每一項已選定的工程要在三年內完成,是確定應該上馬哪些工程,方能使該部門可能的期望收益最
3、大。工 程費 用期望收益第1年第2年第3年15 1 84 7 103 9 28 6 1020402030234可用資金1822242)模型分析與變量的假設 這是工程上馬的決策問題,對任一給定的工程而言,它只有兩種可能,要么上馬,要么不上馬,這兩種情況分別對應二進制數(shù)中的1、0,大凡這樣的實際背景所對應的工程問題,大都可考慮用01型整數(shù)規(guī)劃模型建立其相應的模型。設因每一年的投資不超過所能提供的可用資金數(shù)25千元,故該01型整數(shù)規(guī)劃問題的約束條件為:由于期望收益盡可能大,故目標函數(shù)為:3)模型的建立與求解至此,我們得到該問題的01型整數(shù)規(guī)劃模型為:約束條件為:下面用隱枚舉法求其最優(yōu)解。易知,該01
4、型整數(shù)規(guī)劃模型有一可行解(0,0,0,1),它對應的目標函數(shù)值為:。自然,該模型的最優(yōu)解所對應的目標函數(shù)值應不小于30,于是,我們增加一過濾條件為: (4)在此過濾條件(過濾條件可不唯一)下,用隱枚舉法求01型整數(shù)規(guī)劃模型的最優(yōu)解的步驟為:(1)先判斷第一枚舉點所對應的目標函數(shù)值是否滿足過濾條件,若不滿足,則轉下一步;若滿足,再判斷該枚舉點是否滿足各約束條件,若有一個約束條件不滿足,則轉下一步,若均滿足,則將該枚舉點所對應的目標函數(shù)值z1(本例中,z1)作為新的目標值,并修改過濾條件為: ,再轉下一步;(2) 再判斷第二枚舉點所對應的目標函數(shù)值是
5、否滿足新的過濾條件,若不滿足,則轉下一步;若滿足,接著判斷該枚舉點是否滿足各約束條件,若有一個約束條件不滿足,則轉下一步,若均滿足,則將該枚舉點所對應的目標函數(shù)值z2(z2 ³z1)作為新的目標值,并修改過濾條件為: ,再轉下一步;(3) 重復步驟(2),直至所有的枚舉點均比較結束為止。由隱枚舉法的求解步驟,我們可給出該問題的求解過程如下表所示,并得到最優(yōu)解為:,相應的目標值為90(千元)。故應上馬的工程為2號、3號、4號工程。枚舉點當前目標值滿足約束條件(含過濾條件)?新目標值(4)(1)(2)(3)(0,0,0,0)(0,0,0,1)(0,0,1,0)(0
6、,0,1,1)(0,1,0,0)(0,1,0,1)(0,1,1,0)(0,1,1,1)(1,0,0,0)(1,0,0,1)(1,0,1,0)(1,0,1,1)(1,1,0,0)(1,1,0,1)(1,1,1,0)(1,1,1,1)30303030505070709090909090909090×3030×3050×5070×7090×90×90×90×90×90×90×90×90注:在該表中,表示滿足相應條件,×表示不滿足相應條件。例2 工序
7、的流程安排問題1)問題的提出 一條裝配線由一系列工作站組成,被裝配或制造的產(chǎn)品在裝配線上流動的過程中,每站都要完成一道或幾道工序,假定一共有六道工序,這些工序按先后次序在各工作站上完成,關于這些工序有如下的數(shù)據(jù):工序所需時間(分)前驅工序13無25無322461,3582634另外工藝流程特別要求,在任一給定的工作站上,不管完成哪些工序,可用的總時間不能超過10分鐘,如何將這些工序分配給各工作站,以使所需的工作站數(shù)為最少?2)模型分析與變量的假設下面,我們先討論工序與工作站的關系,并試圖建立起該問題的01型整數(shù)規(guī)劃模型。對任一工序而言,它要么屬于工作站,要么不屬于工作站,故決策變量可定義為:這
8、種定義,使我們能根據(jù)最優(yōu)解中的值來很快確定工序與工作站之間的隸屬關系。 又因工序1,2,3所需的工作時間不超過10分鐘,故工序1,2,3的工作可以在一個工作站上完成,此時,工序4,5,6只能分別在各自的工作站上工作,該可行解對應的工作站數(shù)為4個。也就是說,對最優(yōu)解而言,該裝配線上所需的工作站個數(shù)不會多于4個。因此,我們再定義變量如下:至此,我們得到所需的目標函數(shù)為:再考慮該模型的約束條件:(1) 每道工序均隸屬于一個工作站,且每一工序都必須完成,故有以下六個約束:(2)在任一工作站上完成隸屬工序所用的時間不能超過10分鐘,故有以下四個約束:(3)最后,我們再考慮各道工序所受的先后次序約束的條件。先考察工序2與工序3的關系,因工序2在工序3之前運行,故若工序3隸屬于工作站4,則工序2無論屬于那個工作站均可;若工序3隸屬于工作站3,則工序2可屬于工作站1或2或3;此時,變量應滿足的約束條件為:;同理,若工序3隸屬于工作站2或1,則變量應 滿足的約束條件為:同理,根據(jù)其它工序的優(yōu)先關系,可仿此法給出其相應的約束條件,由上圖知,六個工序之間有五個優(yōu)先關系,故這類約束條件共有15個。另外,在最優(yōu)解中,若有一個工作站不用(即=0),則隸屬于該工作站的全部必須為0,于是,有以下四個約束條件:3)模型的建立與求解 至此,我們得
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經(jīng)權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
- 6. 下載文件中如有侵權或不適當內容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 2025年揚州貨運上崗證模擬考試
- 自愿放棄工傷認定協(xié)議
- 個人股權0元轉讓協(xié)議
- 教育機構考試分數(shù)統(tǒng)計表
- 金融服務效率與質量對比表
- 市場細分區(qū)域分析圖表
- 保潔機械設備采購合同
- 競選大學班長發(fā)言稿
- 班長的發(fā)言稿
- 糧食巡視發(fā)言稿
- 幼兒園課件《神奇的帽子》
- (小升初真題)六年級數(shù)學簡便計算(易錯題、難題)一【含答案】
- 三菱變頻器d700使用手冊應用篇
- 學校安全隱患網(wǎng)格化管理平臺系統(tǒng)操作手冊
- 表面粗糙度等級對照表模板.doc
- GMP講課教案簡述
- 新冀人版小學科學三年級下冊全冊教案(2022年春修訂)
- 東莞虎門架空線路拆除施工方案
- 尿液結晶教學課件
- 繪本《你很特別》
- 茶葉揉捻機總體設計方案的擬定
評論
0/150
提交評論