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

第1頁(yè)運(yùn)籌帷幄之中決勝千里之外運(yùn)籌學(xué)課件整數(shù)線性規(guī)劃IntegerLinearProgramming第2頁(yè)整數(shù)規(guī)劃整數(shù)規(guī)劃問(wèn)題與模型整數(shù)規(guī)劃算法計(jì)算軟件應(yīng)用案例第3頁(yè)整數(shù)規(guī)劃問(wèn)題實(shí)例特點(diǎn)模型分類第4頁(yè)應(yīng)用案例投資組合問(wèn)題旅游售貨員問(wèn)題背包問(wèn)題第5頁(yè)投資組合問(wèn)題背景實(shí)例模型第6頁(yè)背景證券投資：把一定的資金投入到合適的有價(jià)證券上以規(guī)避風(fēng)險(xiǎn)并獲得最大的利潤(rùn)。項(xiàng)目投資：財(cái)團(tuán)或銀行把資金投入到若干項(xiàng)目中以獲得中長(zhǎng)期的收益最大。第7頁(yè)案例某財(cái)團(tuán)有萬(wàn)元的資金，經(jīng)出其考察選中個(gè)投資項(xiàng)目，每個(gè)項(xiàng)目只能投資一個(gè)。其中第個(gè)項(xiàng)目需投資金額為萬(wàn)元，預(yù)計(jì)5年后獲利（）萬(wàn)元，問(wèn)應(yīng)如何選擇項(xiàng)目使得5年后總收益最大？第8頁(yè)模型變量—每個(gè)項(xiàng)目是否投資約束—總金額不超過(guò)限制目標(biāo)—總收益最大第9頁(yè)第10頁(yè)旅游售貨員問(wèn)題背景案例模型第11頁(yè)背景旅游線路安排預(yù)定景點(diǎn)走且只走一次路上時(shí)間最短配送線路—貨郎擔(dān)問(wèn)題送貨地到達(dá)一次總路程最短第12頁(yè)案例有一旅行團(tuán)從出發(fā)要遍游城市，已知從到的旅費(fèi)為，問(wèn)應(yīng)如何安排行程使總費(fèi)用最小？第13頁(yè)模型變量—是否從i第個(gè)城市到第j個(gè)城市約束每個(gè)城市只能到達(dá)一次、離開(kāi)一次第14頁(yè)避免出現(xiàn)斷裂每個(gè)點(diǎn)給個(gè)位勢(shì)除了初始點(diǎn)外要求前點(diǎn)比后點(diǎn)大第15頁(yè)目標(biāo)—總費(fèi)用最小第16頁(yè)第17頁(yè)背包問(wèn)題背景案例模型第18頁(yè)背景郵遞包裹把形狀可變的包裹用盡量少的車輛運(yùn)走旅行背包容量一定的背包里裝盡可能的多的物品第19頁(yè)實(shí)例某人出國(guó)留學(xué)打點(diǎn)行李，現(xiàn)有三個(gè)旅行包，容積大小分別為1000毫升、1500毫升和2000毫升，根據(jù)需要列出需帶物品清單，其中一些物品是必帶物品共有7件，其體積大小分別為400、300、150、250、450、760、190、（單位毫升）。尚有10件可帶可不帶物品，如果不帶將在目的地購(gòu)買，通過(guò)網(wǎng)絡(luò)查詢可以得知其在目的地的價(jià)格（單位美元）。這些物品的容量及價(jià)格分別見(jiàn)下表，試給出一個(gè)合理的安排方案把物品放在三個(gè)旅行包里。

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

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

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

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

LinDo

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

LinGo

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

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

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

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

第74頁(yè)

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

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

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

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