運籌學(xué)整數(shù)規(guī)劃案例

1、整數(shù)規(guī)劃建模 應(yīng)用最廣泛的整數(shù)規(guī)劃問題是各種類型的決策問題，決策者希望模型能回答諸如：是否要執(zhí)行某些項目（或某些活動），在什么時候或什么地點執(zhí)行等決策問題，回答這類“是否”或“有無”問題可借助整數(shù)規(guī)劃中的0-1整數(shù)變量。 0-1整數(shù)變量只有兩個選擇，0由于它在數(shù)學(xué)上的特性可以很好的代表“無”或“否”，而1則可以很好地代表“有”或“是”。0-1變量由于它的特殊性也被稱為二進制變量、決策變量或邏輯變量。10-1變量的作用1. xj1方案j被選中0方案j未被選中2. 從n個方案中必須選中一個：3. 從n個方案中最多選中m個：4. 方案i只有在方案j選中時，才可能被選中：5. 方案i與方案j是否選中是

2、同時的：2與01變量相關(guān)的幾個實際問題1. 投資問題 現(xiàn)有總額為b的資金可用于投資，共有n個項目可供投資者選擇，已知項目j所需投資額為aj，投資后可得利潤cj（j 1，2，n），不妨設(shè)b，aj，cj 均是整數(shù)，試問為使所得利潤最大，應(yīng)選取那些項目進行投資？先引入01變量xj，令 xj1對項目j投資0否則則可得到如下整數(shù)規(guī)劃問題：3例1：華美公司有5個項目被列入投資計劃，各項目的投資額和期望的投資收益見下表：項目投資額（萬元）投資收益（萬元）121015023002103100604130805260180 該公司只有600萬元資金可用于投資，由于技術(shù)上的原因，投資受到以下約束：在項目1、2和3

3、中必須有一項被選中；項目3和4只能選一項；項目5被選中的前提是項目1必須被選中。問如何在上述條件下選擇一個最好的投資方案，使投資收益最大。4 令0-1變量為決策變量，即xi1表示選中項目i，否則xi0表示項目i未被選中。則模型可以表示為：解：52. 背包問題 背包問題由來以久，它是從旅行者如何選擇放在背包中的用品引出的。 旅行者可背負的重量有限，但旅行者需要攜帶的物品很多，如：食品、水、衣物、帳篷、急救用品等等，旅行者不可能將所有想攜帶的物品都統(tǒng)統(tǒng)背上，他只能選擇那些最重要的物品隨身攜帶，又不超過他可能負擔(dān)的最大重量，為解決這個問題，旅行者可給每種物品指定一個重要性系數(shù)，他的目標(biāo)是在小于一定重

4、量的前提下，使所攜帶的物品的重要性系數(shù)之和最大。6例2 ：一登山隊員做登山準(zhǔn)備，他需要攜帶的物品有：食品、氧氣、冰鎬、繩索、帳篷、照相機和通訊設(shè)備每種物品的重要系數(shù)和重量如下表所示，假定登山隊員可攜帶的最大重量為25千克。問他如何抉擇？序號1234567物品食品氧氣冰鎬繩索帳篷照相器材通訊設(shè)備重量（千克）55261224重要系數(shù)2015181484107 令xi1表示登山隊員攜帶物品i，xi0表示不帶物品i。則問題可寫為：Max z =20 x1+15x2+18x3 +14x4+8x5+4x6+10 x7s.t. 5x1+ 5x2 + 2x3 +6x4+12x5+2x6+4x725 xi=1或

5、0，i=1,2,7解：8背包問題應(yīng)用（作業(yè)） 要把7種規(guī)格的包裝箱裝到兩輛鐵路平板車上去，包裝箱的寬和高相同，但厚度和重量不同，見下表： 每輛車有10.2m長的地方可以用來裝箱（類似面包片），載重為40噸。C5， C6 ， C7 ，三類包箱所占總空間（厚度）不超過302.7cm，試建立數(shù)學(xué)模型，盡量將這些包裝箱裝到平板車上去，使浪費的空間最小。9例3.一公司考慮在四個城市：北京、上海、廣州和武漢設(shè)立庫房。這些庫房負責(zé)向三個地區(qū)：華北、華中和華南地區(qū)發(fā)運貨物，每個庫房每月可處理貨物1000件。在北京設(shè)庫房每月的成本為4.5萬元。上海為5萬元，廣州為7萬元，武漢為4萬元。每個地區(qū)的月平均需求量為：

6、華北每月600件，華中每月700件，華南每月800件。發(fā)運貨物的費用（元/件）見下表： 公司希望在滿足地區(qū)需要的前提下使平均月成本最小，且還要滿足以下條件：如果在上海設(shè)立庫房，則必須也在武漢設(shè)庫房；最多設(shè)立三個庫房；武漢和廣州不能同時設(shè)立庫房。 請建立一個滿足上述要求的整數(shù)規(guī)劃模型。3. 工廠選址運輸問題10 設(shè)每個月從倉庫i運往地區(qū)j的產(chǎn)品的貨物數(shù)量為xij，引入01變量yi= 1表示在Ai設(shè)立倉庫，否則不設(shè)。 設(shè)每個月的總花費為z，則上述問題的數(shù)學(xué)模型為Min z200 x11+400 x12+500 x13+300 x21+250 x22+450 x23 +600 x31+400 x32

7、+250 x33+300 x41+150 x42+350 x43+45000y1+50000y2+70000y3+40000y4s.t. x11+x12+x131000y1 x21+x22+x231000y2 x31+x32+x331000y3 x41+x42+x431000y4 x11+x21+x31+x41600 x12+x22+x32+x42700 x13+x23+x33+x43800 y2-y40 y1+y2+y3+y43 y3+y4 1 xij0；yi0或1；i=1,2,3,4；j=1,2,311工廠選址運輸問題 設(shè)有n個需求點，有m個可供選擇的廠址，每個廠址只能建一個工廠，在i處建

8、廠，生產(chǎn)能力為Di，單位時間的固定成本為ai，需求點j的需求量為bj，從廠址i到需求點j的單位運費為Cij，問應(yīng)如何選擇廠址才能獲得經(jīng)濟上的總花費最小的方案。12 設(shè)在單位時間內(nèi)，從廠址i運往需求點j的產(chǎn)品數(shù)量為xij， 引入01變量yi=1在i地建廠0否則設(shè)在單位時間內(nèi)的總花費為z，則上述問題的數(shù)學(xué)模型為134.集合覆蓋和布點問題 集合覆蓋問題也是典型的整數(shù)規(guī)劃問題，在集合覆蓋問題中，一個給定集合（集合一）的每一個元素必須被另一個集合（集合二）的元素所覆蓋。在滿足覆蓋集合一所有元素的前提下，集合覆蓋問題的目標(biāo)是求需要的集合二的元素最少，該問題之所以又稱為布點問題，是因為它常被用于一些公共設(shè)施

9、，如：學(xué)校、醫(yī)院、商業(yè)區(qū)、消防隊等設(shè)施的布點問題，解決如何既滿足公共要求，又使布的點最少，以節(jié)約投資費用。14例4：解決某市消防站的布點問題：某城市共有6個區(qū)，每個都可以建消防站。市政府希望建設(shè)的消防站最少，但必須滿足在城市任何地區(qū)發(fā)生火警時，消防車要在15分鐘內(nèi)趕到現(xiàn)場。據(jù)實地測定，各區(qū)之間消防車行駛的時間見下表：請幫助該市制定一個最節(jié)省的計劃。 表3.5消防車在各區(qū)行駛距離表 地區(qū)1 地區(qū)2 地區(qū)3 地區(qū)4 地區(qū)5 地區(qū)6地區(qū)1 0 10 16 28 27 20地區(qū)2 10 0 24 32 17 10地區(qū)3 16 24 0 12 27 21地區(qū)4 28 32 12 0 15 25地區(qū)5 2

10、7 17 27 15 0 14地區(qū)6 20 10 21 25 14 015 解：Xj=1表地區(qū)設(shè)消防站， Xj=0表地區(qū)不設(shè)消防站。Z消防站總數(shù)，則模型如下： MinZ=X1+X2+X3+X4+X5+X6 s.t： X1+X21 X1+X2+X61 X3+X41 X3+X4+X51 X4+X5+X61 X2+X5+X61 Xj=0，1；j=1，2，3，4，5，6。16作業(yè)某市有8個區(qū)，救護車從一個區(qū)開往另一個區(qū)所需時間：區(qū)號12345678人口（萬人）10246898104022054861293034502235735464203254205882302241569632203250781255230245810974422060該市只有兩輛救護車，且希望救護車，所在的位置能使盡可能多的人口位于救護車在兩分鐘內(nèi)可達到的范圍內(nèi)，請幫助該市構(gòu)造一個整數(shù)規(guī)劃模型來解決這個問題。175. 指派問題 在生活中經(jīng)常遇到這樣的問題，某單位需要完成n項任務(wù)，恰好有n個人可以承擔(dān)這些任務(wù)，由于