版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
運(yùn)籌帷幄之中決勝千里之外運(yùn)籌學(xué)課件整數(shù)線性規(guī)劃IntegerLinearProgramming1整數(shù)規(guī)劃整數(shù)規(guī)劃問題與模型整數(shù)規(guī)劃算法計(jì)算軟件應(yīng)用案例2整數(shù)規(guī)劃問題實(shí)例特點(diǎn)模型分類3應(yīng)用案例投資組合問題旅游售貨員問題背包問題4投資組合問題背景實(shí)例模型5背景證券投資:把一定的資金投入到合適的有價(jià)證券上以規(guī)避風(fēng)險(xiǎn)并獲得最大的利潤(rùn)。項(xiàng)目投資:財(cái)團(tuán)或銀行把資金投入到若干項(xiàng)目中以獲得中長(zhǎng)期的收益最大。6案例某財(cái)團(tuán)有萬元的資金,經(jīng)出其考察選中個(gè)投資項(xiàng)目,每個(gè)項(xiàng)目只能投資一個(gè)。其中第個(gè)項(xiàng)目需投資金額為萬元,預(yù)計(jì)5年后獲利()萬元,問應(yīng)如何選擇項(xiàng)目使得5年后總收益最大?7模型變量—每個(gè)項(xiàng)目是否投資約束—總金額不超過限制目標(biāo)—總收益最大89旅游售貨員問題背景案例模型10背景旅游線路安排預(yù)定景點(diǎn)走且只走一次路上時(shí)間最短配送線路—貨郎擔(dān)問題送貨地到達(dá)一次總路程最短11案例有一旅行團(tuán)從出發(fā)要遍游城市,已知從到的旅費(fèi)為,問應(yīng)如何安排行程使總費(fèi)用最小?12模型變量—是否從i第個(gè)城市到第j個(gè)城市約束每個(gè)城市只能到達(dá)一次、離開一次13避免出現(xiàn)斷裂每個(gè)點(diǎn)給個(gè)位勢(shì)除了初始點(diǎn)外要求前點(diǎn)比后點(diǎn)大14目標(biāo)—總費(fèi)用最小1516背包問題背景案例模型17背景郵遞包裹把形狀可變的包裹用盡量少的車輛運(yùn)走旅行背包容量一定的背包里裝盡可能的多的物品18實(shí)例某人出國留學(xué)打點(diǎn)行李,現(xiàn)有三個(gè)旅行包,容積大小分別為1000毫升、1500毫升和2000毫升,根據(jù)需要列出需帶物品清單,其中一些物品是必帶物品共有7件,其體積大小分別為400、300、150、250、450、760、190、(單位毫升)。尚有10件可帶可不帶物品,如果不帶將在目的地購買,通過網(wǎng)絡(luò)查詢可以得知其在目的地的價(jià)格(單位美元)。這些物品的容量及價(jià)格分別見下表,試給出一個(gè)合理的安排方案把物品放在三個(gè)旅行包里。
19物品12345678910體積200350500430320120700420250100價(jià)格154510070507520090203020問題分析變量—對(duì)每個(gè)物品要確定是否帶同時(shí)要確定放在哪個(gè)包裹里,如果增加一個(gè)虛擬的包裹把不帶的物品放在里面,則問題就轉(zhuǎn)化為確定每個(gè)物品放在哪個(gè)包裹里。如果直接設(shè)變量為每個(gè)物品放在包裹的編號(hào),則每個(gè)包裹所含物品的總?cè)萘烤秃茈y寫成變量的函數(shù)。為此我們?cè)O(shè)變量為第i個(gè)物品是否放在第j個(gè)包裹中21約束包裹容量限制必帶物品限制選帶物品限制22目標(biāo)函數(shù)—未帶物品購買費(fèi)用最小23模型24特征—變量整數(shù)性要求來源
問題本身的要求引入的邏輯變量的需要性質(zhì)—可行域是離散集合2526線性整數(shù)規(guī)劃模型一般整數(shù)規(guī)劃模型0-1整數(shù)規(guī)劃模型混合整數(shù)規(guī)劃模型27一般整數(shù)規(guī)劃模型280-1整數(shù)規(guī)劃模型29混合整數(shù)規(guī)劃模型30算法與線性規(guī)劃的關(guān)系分支定界算法割平面算法近似算法31與線性規(guī)劃的關(guān)系放松的線性規(guī)劃可行解是放松問題的可行解最優(yōu)值大于等于放松問題的最優(yōu)值整數(shù)規(guī)劃323334注釋最優(yōu)解不一定在頂點(diǎn)上達(dá)到最優(yōu)解不一定是放松問題最優(yōu)解的鄰近整數(shù)解整數(shù)可行解遠(yuǎn)多余于頂點(diǎn),枚舉法不可取35分支定界算法算法思想算法步驟算例注釋36算法思想隱枚舉法求解放松問題最優(yōu)值比界壞最優(yōu)解為整數(shù)最優(yōu)值比界好最優(yōu)解為非整數(shù)最優(yōu)值比界好分支邊界分支舍棄37分支的方法383940定界當(dāng)前得到的最好整數(shù)解的目標(biāo)函數(shù)值分支后計(jì)算放松的線性規(guī)劃的最優(yōu)解整數(shù)解且目標(biāo)值小于原有最好解的值則替代原有最好解整數(shù)解且目標(biāo)值大于原有最好解的值則刪除該分支其中無最優(yōu)解非整數(shù)解且目標(biāo)值小于原有最好解的值則繼續(xù)分支非整數(shù)解且目標(biāo)值大于等于原有最好解的值則刪除該分支其中無最優(yōu)解41選一分支寫出并求解放松問題,同時(shí)從分支集中刪除該分支判定是否為整數(shù)解初始分支為可行解集,初始界為無窮大判定是否分支集空是停止當(dāng)前最好解為最優(yōu)解是否42判定最優(yōu)值是否小于當(dāng)前界判定最優(yōu)值是否小于當(dāng)前界是否按非整數(shù)變量分支并加入分支集否是以最優(yōu)解替代當(dāng)前最好解最優(yōu)值替代當(dāng)前界43算例44454647注釋求解混合整數(shù)規(guī)劃問題,只對(duì)整數(shù)變量分支,對(duì)非整數(shù)變量不分支。48對(duì)0-1整數(shù)規(guī)劃分支時(shí)49分枝問題解可能出現(xiàn)的情況情況2,4,5
找到最優(yōu)解情況3
在縮減的域上繼續(xù)分枝定界法情況6
問題1的整數(shù)解作為界被保留,用于以后與問題2的后續(xù)分枝所得到的解進(jìn)行比較,結(jié)論如情況4或550分枝定界法舉例
例4解:松弛問題的最優(yōu)解為x1=2.5,x2=2,OBJ=23
由x1=2.5得到兩個(gè)分枝如下:51表4.2.3分枝問題的松弛解問題II的解即原整數(shù)問題的最優(yōu)解可能存在兩個(gè)分枝都是非整數(shù)解的情況,則需要兩邊同時(shí)繼續(xù)分枝,直到有整數(shù)解出現(xiàn),就可以進(jìn)行定界過程當(dāng)存在很多變量有整數(shù)約束時(shí),分枝即廣又深,在最壞情況下相當(dāng)于組合所有可能的整數(shù)解一般整數(shù)規(guī)劃問題屬于一類未解決的難題,NP-complete,只有少數(shù)特殊問題有好的算法,如任務(wù)分配問題、匹配問題52算法思想算法步驟算例割平面算法53算法思想由放松問題的可行域向整數(shù)規(guī)劃的可行域逼近方法—利用超平面切除要求整數(shù)解保留放松問題最優(yōu)值增加54割平面生成方法條件--保留整數(shù)解刪除最優(yōu)解55整數(shù)可行解最優(yōu)基可行解565758596061正則解62算法步驟求放松問題的最優(yōu)基可行解判斷是否為整數(shù)解是停止得到最優(yōu)解否在單純性表中加入一列利用對(duì)偶單純性算法求最優(yōu)解63算例(1,1.5)64656667686970計(jì)算軟件整數(shù)變量定義
LinDo
一般整數(shù)變量:GIN<Variable>0-1整數(shù)變量:INT<Variable>
LinGo
一般整數(shù)變量:@GIN(variable_name);0-1整數(shù)變量:@BIN(variable_name);算例71算例
max3x1+5x2+4x3subjectto2x1+3x2<=15002x2+4x3<=8003x1+2x2+5x3<=2000endginx1ginx3724.6任務(wù)分配問題例4.6.1有四個(gè)熟練工人,他們都是多面手,有四項(xiàng)任務(wù)要他們完成。若規(guī)定每人必須完成且只完成一項(xiàng)任務(wù),而每人完成每項(xiàng)任務(wù)的工時(shí)耗費(fèi)如表4.6.1,問如何分配任務(wù)使完成四項(xiàng)任務(wù)的總工時(shí)耗費(fèi)最少?73任務(wù)分配問題的數(shù)學(xué)模型模型中:xij
為第i個(gè)工人分配去做第j
項(xiàng)任務(wù);
aij
為第i
個(gè)工人為完成第j
項(xiàng)任務(wù)時(shí)的工時(shí)消耗;
{aij}m
m
稱為效率矩陣運(yùn)輸問題是任務(wù)分配問題的松弛問題任務(wù)分配問題不但是整數(shù)規(guī)劃,而且是0
1規(guī)劃任務(wù)分配問題有2m個(gè)約束條件,但有且只有m個(gè)非零解,是自然高度退化的任務(wù)分配是兩部圖的匹配問題,有著名的匈牙利算法下面介紹一種適合手算的算法(出自清華教科書)74
4.6.1清華算法定理1
如果從效率矩陣{aij}m
m中每行元素分別減去一個(gè)常數(shù)ui,從每列元素分別減去一個(gè)常數(shù)vj
,所得新的效率矩陣{bij}m
m的任務(wù)分配問題的最優(yōu)解等價(jià)于原問題的最優(yōu)解。證明:略定理2
若方陣中一部分元素為零,一部分元素非零,則覆蓋方陣內(nèi)所有零元素的最少直線數(shù)等于位于不同行、不同列的零元素的最多個(gè)數(shù)。證明:略清華算法的基本思路:根據(jù)定理1
變換效率矩陣,使矩陣中有足夠多的零。若矩陣中存在m
個(gè)不同行不同列的零,就找到了最優(yōu)解若覆蓋變換后的效率矩陣零元素的直線少于m條,就尚未找到最優(yōu)解,設(shè)法進(jìn)一步變換矩陣,增加新的零75清華算法的步驟:例4.6.1第一步:變換效率矩陣,使每行每列至少有一個(gè)零行變換:找出每行最小元素,從該行各元素中減去之列變換:找出每列最小元素,從該列各元素中減去之第二步:檢查覆蓋所有零元素的直線是否為m條劃線規(guī)則1、逐行檢查,若該行只有一個(gè)未標(biāo)記的零,對(duì)其加()標(biāo)記,將()標(biāo)記元素同行同列上其它的零打上*標(biāo)記。若該行有二個(gè)以上未標(biāo)記的零,暫不標(biāo)記,轉(zhuǎn)下一行檢查,直到所有行檢查完;76清華算法的步驟:例4.6.12、逐列檢查,若該列只有一個(gè)未標(biāo)記的零,對(duì)其加()標(biāo)記,將()標(biāo)記元素同行同列上其它的零打上*標(biāo)記。若該列有二個(gè)以上未標(biāo)記的零,暫不標(biāo)記,轉(zhuǎn)下一列檢查,直到所有列檢查完;3、重復(fù)1、2后,可能出現(xiàn)三種情況:a.
每行都有一個(gè)(0),顯然已找到最優(yōu)解,令對(duì)應(yīng)(0)位置的xij=1;b.
仍有零元素未標(biāo)記,此時(shí),一定存在某些行和列同時(shí)有多個(gè)零,稱為僵局狀態(tài),因?yàn)闊o法采用1、2
中的方法繼續(xù)標(biāo)記。4、打破僵局。令未標(biāo)記零對(duì)應(yīng)的同行同列上其它未標(biāo)記零的個(gè)數(shù)為該零的指數(shù),選指數(shù)最小的先標(biāo)記();采用這種方法直至所有零都被標(biāo)記,或出現(xiàn)情況a,或情況c
。77清華算法的步驟:例4.6.1c.
所有零都已標(biāo)記,但標(biāo)有()的零的個(gè)數(shù)少于m;
開始劃線過程:
對(duì)沒有標(biāo)記()的行打
對(duì)打
行上所有其它零元素對(duì)應(yīng)的列打
再對(duì)打
列上有()標(biāo)記的零元素對(duì)應(yīng)的行打
重復(fù)
,直至無法繼續(xù)
對(duì)沒有打
的行劃?rùn)M線,對(duì)所有打
的列劃垂線
劃線后會(huì)出現(xiàn)兩種情況:(1)
標(biāo)記()的零少于m個(gè),但劃有m條直線,說明矩陣中已存在m個(gè)不同行不同列的零,但打破僵局時(shí)選擇不合理,沒能找到?;氐絙
重新標(biāo)記;(2)
少于m條直線,到第三步;78清華算法的步驟:例4.6.1第三步:進(jìn)一步變換;
在未劃線的元素中找最小者,設(shè)為
對(duì)未被直線覆蓋的各元素減去
對(duì)兩條直線交叉點(diǎn)覆蓋的元素加上
只有一條直線覆蓋的元素保持不變以上步驟實(shí)際上仍是利用定理1第四步:抹除所有標(biāo)記,回到第二步,重新標(biāo)記;79清華算法的步驟:例4.6.1答:最優(yōu)分配方案為x13=x21=x34=x42=1,其余為0,即甲
C,乙
A,丙
D,丁
B,OBJ=2080
4.6.2關(guān)于清華算法的適用條件要求所有aij
0若某些aij
<0,則利用定理1進(jìn)行變換,使所有bij
0目標(biāo)函數(shù)為min型對(duì)于max型目標(biāo)函數(shù),將效率矩陣中所有aij
反號(hào),則等效于求min型問題;再利用定理1進(jìn)行變換,使所有bij
0,則可采用清華算法打破僵局時(shí)選擇不當(dāng)?shù)慕Y(jié)果:
結(jié)果僅出現(xiàn)3個(gè)標(biāo)記(),但卻劃出4條線,
說明什么?!81線性規(guī)劃有關(guān)的英文詞匯Operational/operationsresearch運(yùn)籌學(xué)Linearprogramming線性
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(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ì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 寶雞文理學(xué)院《薪酬管理》2022-2023學(xué)年第一學(xué)期期末試卷
- 寶雞文理學(xué)院《特種加工技術(shù)》2022-2023學(xué)年第一學(xué)期期末試卷
- 小電流接地選線系統(tǒng)數(shù)據(jù)采集卡的軟件設(shè)計(jì)
- 成套化妝品相關(guān)項(xiàng)目實(shí)施方案
- 護(hù)發(fā)液項(xiàng)目可行性實(shí)施報(bào)告
- 醫(yī)用細(xì)菌鑒定分析儀市場(chǎng)環(huán)境與對(duì)策分析
- 人教版高中數(shù)學(xué)必修4-32期末測(cè)試:高一期末模擬考試試卷2(必修3、必修4)
- 寶雞文理學(xué)院《復(fù)變函數(shù)與積分變換》2022-2023學(xué)年第一學(xué)期期末試卷
- 家用脫脂制劑相關(guān)項(xiàng)目建議書
- 手動(dòng)扭力倍增器市場(chǎng)環(huán)境與對(duì)策分析
- 中藥材及中藥飲片知識(shí)培訓(xùn)培訓(xùn)課件
- 管理學(xué)課件:11 領(lǐng)導(dǎo)概論
- GB/T 6728-2017結(jié)構(gòu)用冷彎空心型鋼
- GB/T 21010-2007土地利用現(xiàn)狀分類
- GB/T 19868.4-2005基于預(yù)生產(chǎn)焊接試驗(yàn)的工藝評(píng)定
- GB/T 10125-2021人造氣氛腐蝕試驗(yàn)鹽霧試驗(yàn)
- GA/T 1049.2-2013公安交通集成指揮平臺(tái)通信協(xié)議第2部分:交通信號(hào)控制系統(tǒng)
- 首次入院護(hù)理評(píng)估單相關(guān)的量表及存在問題講解學(xué)習(xí)
- 2023年上海市松江區(qū)城管協(xié)管員招聘筆試題庫及答案解析
- 中心靜脈導(dǎo)管(CVC)課件
- AFTN和SITA報(bào)文簡(jiǎn)介資料課件
評(píng)論
0/150
提交評(píng)論