運(yùn)籌學(xué)整數(shù)線性規(guī)劃

第1頁運(yùn)籌帷幄之中決勝千里之外運(yùn)籌學(xué)課件整數(shù)線性規(guī)劃IntegerLinearProgramming第2頁整數(shù)規(guī)劃整數(shù)規(guī)劃問題與模型整數(shù)規(guī)劃算法計(jì)算軟件應(yīng)用案例第3頁整數(shù)規(guī)劃問題實(shí)例特點(diǎn)模型分類第4頁應(yīng)用案例投資組合問題旅游售貨員問題背包問題第5頁投資組合問題背景實(shí)例模型第6頁背景證券投資：把一定的資金投入到合適的有價(jià)證券上以規(guī)避風(fēng)險(xiǎn)并獲得最大的利潤。項(xiàng)目投資：財(cái)團(tuán)或銀行把資金投入到若干項(xiàng)目中以獲得中長期的收益最大。第7頁案例某財(cái)團(tuán)有萬元的資金，經(jīng)出其考察選中個(gè)投資項(xiàng)目，每個(gè)項(xiàng)目只能投資一個(gè)。其中第個(gè)項(xiàng)目需投資金額為萬元，預(yù)計(jì)5年后獲利（）萬元，問應(yīng)如何選擇項(xiàng)目使得5年后總收益最大？第8頁模型變量—每個(gè)項(xiàng)目是否投資約束—總金額不超過限制目標(biāo)—總收益最大第9頁第10頁旅游售貨員問題背景案例模型第11頁背景旅游線路安排預(yù)定景點(diǎn)走且只走一次路上時(shí)間最短配送線路—貨郎擔(dān)問題送貨地到達(dá)一次總路程最短第12頁案例有一旅行團(tuán)從出發(fā)要遍游城市，已知從到的旅費(fèi)為，問應(yīng)如何安排行程使總費(fèi)用最??？第13頁模型變量—是否從i第個(gè)城市到第j個(gè)城市約束每個(gè)城市只能到達(dá)一次、離開一次第14頁避免出現(xiàn)斷裂每個(gè)點(diǎn)給個(gè)位勢除了初始點(diǎn)外要求前點(diǎn)比后點(diǎn)大第15頁目標(biāo)—總費(fèi)用最小第16頁第17頁背包問題背景案例模型第18頁背景郵遞包裹把形狀可變的包裹用盡量少的車輛運(yùn)走旅行背包容量一定的背包里裝盡可能的多的物品第19頁實(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è)旅行包里。

第20頁物品12345678910體積200350500430320120700420250100價(jià)格1545100705075200902030第21頁問題分析變量—對(duì)每個(gè)物品要確定是否帶同時(shí)要確定放在哪個(gè)包裹里，如果增加一個(gè)虛擬的包裹把不帶的物品放在里面，則問題就轉(zhuǎn)化為確定每個(gè)物品放在哪個(gè)包裹里。如果直接設(shè)變量為每個(gè)物品放在包裹的編號(hào)，則每個(gè)包裹所含物品的總?cè)萘烤秃茈y寫成變量的函數(shù)。為此我們設(shè)變量為第i個(gè)物品是否放在第j個(gè)包裹中第22頁約束包裹容量限制必帶物品限制選帶物品限制第23頁目標(biāo)函數(shù)—未帶物品購買費(fèi)用最小第24頁模型第25頁特征—變量整數(shù)性要求來源

問題本身的要求引入的邏輯變量的需要性質(zhì)—可行域是離散集合第26頁第27頁線性整數(shù)規(guī)劃模型一般整數(shù)規(guī)劃模型0-1整數(shù)規(guī)劃模型混合整數(shù)規(guī)劃模型第28頁一般整數(shù)規(guī)劃模型第29頁0-1整數(shù)規(guī)劃模型第30頁混合整數(shù)規(guī)劃模型第31頁算法與線性規(guī)劃的關(guān)系分支定界算法割平面算法近似算法第32頁與線性規(guī)劃的關(guān)系整數(shù)規(guī)劃放松的線性規(guī)劃可行解是放松問題的可行解最優(yōu)值大于等于放松問題的最優(yōu)值第33頁第34頁第35頁注釋最優(yōu)解不一定在頂點(diǎn)上達(dá)到最優(yōu)解不一定是放松問題最優(yōu)解的鄰近整數(shù)解整數(shù)可行解遠(yuǎn)多余于頂點(diǎn)，枚舉法不可取第36頁分支定界算法算法思想算法步驟算例注釋第37頁算法思想隱枚舉法求解放松問題最優(yōu)值比界壞

最優(yōu)解為整數(shù)最優(yōu)值比界好

最優(yōu)解為非整數(shù)最優(yōu)值比界好分支邊界分支舍棄第38頁分支的方法第39頁第40頁第41頁定界當(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)解第42頁選一分支寫出并求解放松問題，同時(shí)從分支集中刪除該分支判定是否為整數(shù)解初始分支為可行解集，初始界為無窮大判定是否分支集空是停止當(dāng)前最好解為最優(yōu)解是否第43頁判定最優(yōu)值是否小于當(dāng)前界判定最優(yōu)值是否小于當(dāng)前界是否按非整數(shù)變量分支并加入分支集否是以最優(yōu)解替代當(dāng)前最好解最優(yōu)值替代當(dāng)前界第44頁算例第45頁第46頁第47頁第48頁注釋求解混合整數(shù)規(guī)劃問題，只對(duì)整數(shù)變量分支，對(duì)非整數(shù)變量不分支。第49頁對(duì)0-1整數(shù)規(guī)劃分支時(shí)第50頁算法思想算法步驟算例割平面算法第51頁算法思想由放松問題的可行域向整數(shù)規(guī)劃的可行域逼近方法—利用超平面切除要求整數(shù)解保留放松問題最優(yōu)值增加第52頁割平面生成方法條件--保留整數(shù)解刪除最優(yōu)解第53頁整數(shù)可行解最優(yōu)基可行解第54頁第55頁第56頁第57頁第58頁第59頁正則解第60頁算法步驟求放松問題的最優(yōu)基可行解判斷是否為整數(shù)解是停止得到最優(yōu)解否在單純性表中加入一列利用對(duì)偶單純性算法求最優(yōu)解第61頁算例(1,1.5)第62頁第63頁第64頁第65頁第66頁第67頁第68頁計(jì)算軟件整數(shù)變量定義

LinDo

一般整數(shù)變量:GIN<Variable>0-1整數(shù)變量:INT<Variable>

LinGo

一般整數(shù)變量:@GIN(variable_name);0-1整數(shù)變量：@BIN(variable_name);算例第69頁算例

max3x1+5x2+4x3subjectto2x1+3x2<=15002x2+4x3<=8003x1+2x2+5x3<=2000endginx1ginx3第70頁應(yīng)用案例分析人力資源分配問題應(yīng)急設(shè)施選址問題第71頁人力資源分配問題某個(gè)中型百貨商場對(duì)售貨人員（周工資200元）的需求經(jīng)統(tǒng)計(jì)如下表

為了保證銷售人員充分休息，銷售人員每周工作5天，休息2天。問應(yīng)如何安排銷售人員的工作時(shí)間，使得所配售貨人員的總費(fèi)用最??？星期一二三四五六七人數(shù)12151214161819第72頁模型假設(shè)每天工作8小時(shí)，不考慮夜班的情況；每個(gè)人的休息時(shí)間為連續(xù)的兩天時(shí)間；每天安排的人員數(shù)不得低于需求量，但可以超過需求量第73頁問題分析因素不可變因素：需求量、休息時(shí)間、單位費(fèi)用；可變因素：安排的人數(shù)、每人工作的時(shí)間、總費(fèi)用；方案確定每天工作的人數(shù)，由于連續(xù)休息2天，當(dāng)確定每個(gè)人開始休息的時(shí)間就等于知道工作的時(shí)間，因而確定每天開始休息的人數(shù)就知道每天開始工作的人數(shù)，從而求出每天工作的人數(shù)。變量每天開始休息的人數(shù)約束條件

1.每人休息時(shí)間2天，自然滿足。

第74頁

3.變量非負(fù)約束：第75頁目標(biāo)函數(shù)：總費(fèi)用最小，總費(fèi)用與使用的總?cè)藬?shù)成正比。由于每個(gè)人必然在且僅在某一天開始休息，所以總?cè)藬?shù)等于第76頁模型第77頁注解該問題本質(zhì)上是個(gè)整數(shù)規(guī)劃問題，放松的線性規(guī)劃的最優(yōu)解是個(gè)整數(shù)解，所以兩規(guī)劃等價(jià)。定義整數(shù)變量用函數(shù)@gin(x1)……@gin(x7);

0-1整數(shù)變量為@bin(x1)第78頁應(yīng)急選址問題

某城市要在市區(qū)設(shè)置k個(gè)應(yīng)急服務(wù)中心,經(jīng)過初步篩選確定了m個(gè)備選地，現(xiàn)已知共有n個(gè)居民小區(qū)，各小區(qū)到個(gè)備選地的距離為為了使得各小區(qū)能及時(shí)得到應(yīng)急服務(wù)，要求各小區(qū)到最近的服務(wù)中心的距離盡可能的短，試給出中心選址方案。第79頁問題分析

該問題與傳統(tǒng)的選址問題的主要區(qū)別在于其目標(biāo)不再是要求費(fèi)用最小，而是要求最長距離最短。也就是離服務(wù)中心距離最遠(yuǎn)的小區(qū)離最近的服務(wù)中心距離最