運籌學整數(shù)線性規(guī)劃

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

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

問題本身的要求引入的邏輯變量的需要性質—可行域是離散集合第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ī)劃的關系分支定界算法割平面算法近似算法第32頁與線性規(guī)劃的關系整數(shù)規(guī)劃放松的線性規(guī)劃可行解是放松問題的可行解最優(yōu)值大于等于放松問題的最優(yōu)值第33頁第34頁第35頁注釋最優(yōu)解不一定在頂點上達到最優(yōu)解不一定是放松問題最優(yōu)解的鄰近整數(shù)解整數(shù)可行解遠多余于頂點，枚舉法不可取第36頁分支定界算法算法思想算法步驟算例注釋第37頁算法思想隱枚舉法求解放松問題最優(yōu)值比界壞

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

最優(yōu)解為非整數(shù)最優(yōu)值比界好分支邊界分支舍棄第38頁分支的方法第39頁第40頁第41頁定界當前得到的最好整數(shù)解的目標函數(shù)值分支后計算放松的線性規(guī)劃的最優(yōu)解整數(shù)解且目標值小于原有最好解的值則替代原有最好解整數(shù)解且目標值大于原有最好解的值則刪除該分支其中無最優(yōu)解非整數(shù)解且目標值小于原有最好解的值則繼續(xù)分支非整數(shù)解且目標值大于等于原有最好解的值則刪除該分支其中無最優(yōu)解第42頁選一分支寫出并求解放松問題，同時從分支集中刪除該分支判定是否為整數(shù)解初始分支為可行解集，初始界為無窮大判定是否分支集空是停止當前最好解為最優(yōu)解是否第43頁判定最優(yōu)值是否小于當前界判定最優(yōu)值是否小于當前界是否按非整數(shù)變量分支并加入分支集否是以最優(yōu)解替代當前最好解最優(yōu)值替代當前界第44頁算例第45頁第46頁第47頁第48頁注釋求解混合整數(shù)規(guī)劃問題，只對整數(shù)變量分支，對非整數(shù)變量不分支。第49頁對0-1整數(shù)規(guī)劃分支時第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)解否在單純性表中加入一列利用對偶單純性算法求最優(yōu)解第61頁算例(1,1.5)第62頁第63頁第64頁第65頁第66頁第67頁第68頁計算軟件整數(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頁應用案例分析人力資源分配問題應急設施選址問題第71頁人力資源分配問題某個中型百貨商場對售貨人員（周工資200元）的需求經(jīng)統(tǒng)計如下表

為了保證銷售人員充分休息，銷售人員每周工作5天，休息2天。問應如何安排銷售人員的工作時間，使得所配售貨人員的總費用最?。啃瞧谝欢奈辶呷藬?shù)12151214161819第72頁模型假設每天工作8小時，不考慮夜班的情況；每個人的休息時間為連續(xù)的兩天時間；每天安排的人員數(shù)不得低于需求量，但可以超過需求量第73頁問題分析因素不可變因素：需求量、休息時間、單位費用；可變因素：安排的人數(shù)、每人工作的時間、總費用；方案確定每天工作的人數(shù)，由于連續(xù)休息2天，當確定每個人開始休息的時間就等于知道工作的時間，因而確定每天開始休息的人數(shù)就知道每天開始工作的人數(shù)，從而求出每天工作的人數(shù)。變量每天開始休息的人數(shù)約束條件

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

第74頁

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

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

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

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