運(yùn)籌學(xué)-整數(shù)規(guī)劃案例策劃推廣方案

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

現(xiàn)有總額為b的資金可用于投資，共有n個項目可供投資者選擇，已知項目j所需投資額為aj，投資后可得利潤cj（j＝1，2，…，n），不妨設(shè)b，aj，cj均是整數(shù)，試問為使所得利潤最大，應(yīng)選取那些項目進(jìn)行投資？先引入0－1變量xj，令

xj＝1…對項目j投資0…否則則可得到如下整數(shù)規(guī)劃問題：3與0－1變量相關(guān)的幾個實際問題1.投資問題例1：華美公司有5個項目被列入投資計劃，各項目的投資額和期望的投資收益見下表：項目投資額（萬元）投資收益（萬元）121015023002103100604130805260180該公司只有600萬元資金可用于投資，由于技術(shù)上的原因，投資受到以下約束：①在項目1、2和3中必須有一項被選中；②項目3和4只能選一項；③項目5被選中的前提是項目1必須被選中。問如何在上述條件下選擇一個最好的投資方案，使投資收益最大。4例1：華美公司有5個項目被列入投資計劃，各項目的投項目投資額令0-1變量為決策變量，即xi＝1表示選中項目i，否則xi＝0表示項目i未被選中。則模型可以表示為：解：5令0-1變量為決策變量，即xi＝1表示選中項2.背包問題背包問題由來以久，它是從旅行者如何選擇放在背包中的用品引出的。旅行者可背負(fù)的重量有限，但旅行者需要攜帶的物品很多，如：食品、水、衣物、帳篷、急救用品等等，旅行者不可能將所有想攜帶的物品都統(tǒng)統(tǒng)背上，他只能選擇那些最重要的物品隨身攜帶，又不超過他可能負(fù)擔(dān)的最大重量，為解決這個問題，旅行者可給每種物品指定一個重要性系數(shù)，他的目標(biāo)是在小于一定重量的前提下，使所攜帶的物品的重要性系數(shù)之和最大。62.背包問題背包問題由來以久，它是從旅行者例2：一登山隊員做登山準(zhǔn)備，他需要攜帶的物品有：食品、氧氣、冰鎬、繩索、帳篷、照相機(jī)和通訊設(shè)備每種物品的重要系數(shù)和重量如下表所示，假定登山隊員可攜帶的最大重量為25千克。問他如何抉擇？序號1234567物品食品氧氣冰鎬繩索帳篷照相器材通訊設(shè)備重量（千克）55261224重要系數(shù)2015181484107例2：一登山隊員做登山準(zhǔn)備，他需要攜帶的物品有：序號123

令xi＝1表示登山隊員攜帶物品i，xi＝0表示不帶物品i。則問題可寫為：Maxz=20x1+15x2+18x3

+14x4+8x5+4x6+10x7s.t.5x1+5x2+2x3+6x4+12x5+2x6+4x7≤25

xi=1或0，i=1,2,…,7解：8令xi＝1表示登山隊員攜帶物品i，xi＝0表背包問題應(yīng)用（作業(yè)）

要把7種規(guī)格的包裝箱裝到兩輛鐵路平板車上去，包裝箱的寬和高相同，但厚度和重量不同，見下表：

每輛車有10.2m長的地方可以用來裝箱（類似面包片），載重為40噸。C5，C6，

C7，三類包箱所占總空間（厚度）不超過302.7cm，試建立數(shù)學(xué)模型，盡量將這些包裝箱裝到平板車上去，使浪費(fèi)的空間最小。9背包問題應(yīng)用（作業(yè)）要把7種規(guī)格的包裝箱裝到兩輛鐵例3.一公司考慮在四個城市：北京、上海、廣州和武漢設(shè)立庫房。這些庫房負(fù)責(zé)向三個地區(qū)：華北、華中和華南地區(qū)發(fā)運(yùn)貨物，每個庫房每月可處理貨物1000件。在北京設(shè)庫房每月的成本為4.5萬元。上海為5萬元，廣州為7萬元，武漢為4萬元。每個地區(qū)的月平均需求量為：華北每月600件，華中每月700件，華南每月800件。發(fā)運(yùn)貨物的費(fèi)用（元/件）見下表：華北華中華南北京200400500上海300250450廣州600400250武漢300150350公司希望在滿足地區(qū)需要的前提下使平均月成本最小，且還要滿足以下條件：①如果在上海設(shè)立庫房，則必須也在武漢設(shè)庫房；②最多設(shè)立三個庫房；③武漢和廣州不能同時設(shè)立庫房。請建立一個滿足上述要求的整數(shù)規(guī)劃模型。3.工廠選址運(yùn)輸問題10例3.一公司考慮在四個城市：北京、上海、廣州和武漢設(shè)立庫房。

設(shè)每個月從倉庫i運(yùn)往地區(qū)j的產(chǎn)品的貨物數(shù)量為xij，引入0－1變量yi=1表示在Ai設(shè)立倉庫，否則不設(shè)。

設(shè)每個月的總花費(fèi)為z，則上述問題的數(shù)學(xué)模型為Minz＝200x11+400x12+500x13+300x21+250x22+450x23+600x31+400x32+250x33+300x41+150x42+350x43+45000y1+50000y2+70000y3+40000y4s.t.x11+x12+x13≤1000y1x21+x22+x23≤1000y2x31+x32+x33≤1000y3x41+x42+x43≤1000y4x11+x21+x31+x41≥600x12+x22+x32+x42≥700x13+x23+x33+x43≥800y2-y4≤0y1+y2+y3+y4≤3y3+y4≤

1xij≥0；yi＝0或1；i=1,2,3,4；j=1,2,311設(shè)每個月從倉庫i運(yùn)往地區(qū)j的產(chǎn)品的貨物數(shù)量為xij工廠選址運(yùn)輸問題

設(shè)有n個需求點，有m個可供選擇的廠址，每個廠址只能建一個工廠，在i處建廠，生產(chǎn)能力為Di，單位時間的固定成本為ai，需求點j的需求量為bj，從廠址i到需求點j的單位運(yùn)費(fèi)為Cij，問應(yīng)如何選擇廠址才能獲得經(jīng)濟(jì)上的總花費(fèi)最小的方案。12工廠選址運(yùn)輸問題設(shè)有n個需求點，有m個可供選

設(shè)在單位時間內(nèi)，從廠址i運(yùn)往需求點j的產(chǎn)品數(shù)量為xij，

引入0－1變量yi=1…在i地建廠0…否則設(shè)在單位時間內(nèi)的總花費(fèi)為z，則上述問題的數(shù)學(xué)模型為13設(shè)在單位時間內(nèi)，從廠址i運(yùn)往需1…在i地建廠4.集合覆蓋和布點問題集合覆蓋問題也是典型的整數(shù)規(guī)劃問題，在集合覆蓋問題中，一個給定集合（集合一）的每一個元素必須被另一個集合（集合二）的元素所覆蓋。在滿足覆蓋集合一所有元素的前提下，集合覆蓋問題的目標(biāo)是求需要的集合二的元素最少，該問題之所以又稱為布點問題，是因為它常被用于一些公共設(shè)施，如：學(xué)校、醫(yī)院、商業(yè)區(qū)、消防隊等設(shè)施的布點問題，解決如何既滿足公共要求，又使布的點最少，以節(jié)約投資費(fèi)用。144.集合覆蓋和布點問題集合覆蓋問題也是典型的例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ū)101016282720地區(qū)210024321710地區(qū)316240122721地區(qū)428321201525地區(qū)527172715014地區(qū)62010212514015例4：解決某市消防站的布點問題：某城市共有6個區(qū)，每個都可以解：Xj=1表地區(qū)設(shè)消防站，Xj=0表地區(qū)不設(shè)消防站。Z＝消防站總數(shù)，則模型如下：

MinZ=X1+X2+X3+X4+X5+X6s.t：X1+X2≥1

X1+X2+X6≥1X3+X4≥1X3+X4+X5≥1X4+X5+X6≥1X2+X5+X6≥1Xj=0，1；j=1，2，3，4，5，6。16解：Xj=1表地區(qū)設(shè)消防站，Xj=0表地區(qū)作業(yè)某市有8個區(qū)，救護(hù)車從一個區(qū)開往另一個區(qū)所需時間：區(qū)號12345678人口（萬人）10246898104022054861293034502235735464203254205882302241569632203250781255230245810974422060該市只有兩輛救護(hù)車，且希望救護(hù)車，所在的位置能使盡可能多的人口位于救護(hù)車在兩分鐘內(nèi)可達(dá)到的范圍內(nèi)，請幫助該市構(gòu)造一個整數(shù)規(guī)劃模型來解決這個問題。17作業(yè)某市有8個區(qū)，救護(hù)車從一個區(qū)開往另一個區(qū)所需時間：區(qū)號15.指派問題

在生活中經(jīng)常遇到這樣的問題，某單位需要完成n項任務(wù)，恰好有n個人可以承擔(dān)這些任務(wù)，由于每個人的專長不同，個人完成不同任務(wù)的效率（時間、費(fèi)用等）也不同。于是產(chǎn)生了指派哪個人去完成哪項任務(wù)，使總效率最高，稱為指派問題（AssignmentProblem）。185.指派問題18

已知上面5名運(yùn)動員各種姿勢游泳成績（50m），試問如何從中選拔一個200m混合泳的接力隊，使預(yù)期比賽成績最好。（列出整數(shù)規(guī)劃模型）ABCDE仰泳37.732.933.837.035.4蛙泳43.333.142.234.941.8蝶泳33.328.538.930.433.6自由泳29.226.429.628.531.15.指派問題（作業(yè)）19已知上面5名運(yùn)動員各種姿勢游泳成績（50m），20202121222223232424整數(shù)規(guī)劃建模應(yīng)用最廣泛的整數(shù)規(guī)劃問題是各種類型的決策問題，決策者希望模型能回答諸如：是否要執(zhí)行某些項目（或某些活動），在什么時候或什么地點執(zhí)行等決策問題，回答這類“是—否”或“有—無”問題可借助整數(shù)規(guī)劃中的0-1整數(shù)變量。0-1整數(shù)變量只有兩個選擇，0由于它在數(shù)學(xué)上的特性可以很好的代表“無”或“否”，而1則可以很好地代表“有”或“是”。0-1變量由于它的特殊性也被稱為二進(jìn)制變量、決策變量或邏輯變量。25整數(shù)規(guī)劃建模應(yīng)用最廣泛的整數(shù)規(guī)劃問題是各種類0-1變量的作用1.xj＝1…方案j被選中0…方案j未被選中2.從n個方案中必須選中一個：3.從n個方案中最多選中m個：4.方案i只有在方案j選中時，才可能被選中：5.方案i與方案j是否選中是同時的：260-1變量的作用1.xj＝1…方案j被選中2.從n個方案與0－1變量相關(guān)的幾個實際問題1.投資問題

現(xiàn)有總額為b的資金可用于投資，共有n個項目可供投資者選擇，已知項目j所需投資額為aj，投資后可得利潤cj（j＝1，2，…，n），不妨設(shè)b，aj，cj均是整數(shù)，試問為使所得利潤最大，應(yīng)選取那些項目進(jìn)行投資？先引入0－1變量xj，令

xj＝1…對項目j投資0…否則則可得到如下整數(shù)規(guī)劃問題：27與0－1變量相關(guān)的幾個實際問題1.投資問題例1：華美公司有5個項目被列入投資計劃，各項目的投資額和期望的投資收益見下表：項目投資額（萬元）投資收益（萬元）121015023002103100604130805260180該公司只有600萬元資金可用于投資，由于技術(shù)上的原因，投資受到以下約束：①在項目1、2和3中必須有一項被選中；②項目3和4只能選一項；③項目5被選中的前提是項目1必須被選中。問如何在上述條件下選擇一個最好的投資方案，使投資收益最大。28例1：華美公司有5個項目被列入投資計劃，各項目的投項目投資額令0-1變量為決策變量，即xi＝1表示選中項目i，否則xi＝0表示項目i未被選中。則模型可以表示為：解：29令0-1變量為決策變量，即xi＝1表示選中項2.背包問題背包問題由來以久，它是從旅行者如何選擇放在背包中的用品引出的。旅行者可背負(fù)的重量有限，但旅行者需要攜帶的物品很多，如：食品、水、衣物、帳篷、急救用品等等，旅行者不可能將所有想攜帶的物品都統(tǒng)統(tǒng)背上，他只能選擇那些最重要的物品隨身攜帶，又不超過他可能負(fù)擔(dān)的最大重量，為解決這個問題，旅行者可給每種物品指定一個重要性系數(shù)，他的目標(biāo)是在小于一定重量的前提下，使所攜帶的物品的重要性系數(shù)之和最大。302.背包問題背包問題由來以久，它是從旅行者例2：一登山隊員做登山準(zhǔn)備，他需要攜帶的物品有：食品、氧氣、冰鎬、繩索、帳篷、照相機(jī)和通訊設(shè)備每種物品的重要系數(shù)和重量如下表所示，假定登山隊員可攜帶的最大重量為25千克。問他如何抉擇？序號1234567物品食品氧氣冰鎬繩索帳篷照相器材通訊設(shè)備重量（千克）55261224重要系數(shù)20151814841031例2：一登山隊員做登山準(zhǔn)備，他需要攜帶的物品有：序號123

令xi＝1表示登山隊員攜帶物品i，xi＝0表示不帶物品i。則問題可寫為：Maxz=20x1+15x2+18x3

+14x4+8x5+4x6+10x7s.t.5x1+5x2+2x3+6x4+12x5+2x6+4x7≤25

xi=1或0，i=1,2,…,7解：32令xi＝1表示登山隊員攜帶物品i，xi＝0表背包問題應(yīng)用（作業(yè)）

要把7種規(guī)格的包裝箱裝到兩輛鐵路平板車上去，包裝箱的寬和高相同，但厚度和重量不同，見下表：

每輛車有10.2m長的地方可以用來裝箱（類似面包片），載重為40噸。C5，C6，

C7，三類包箱所占總空間（厚度）不超過302.7cm，試建立數(shù)學(xué)模型，盡量將這些包裝箱裝到平板車上去，使浪費(fèi)的空間最小。33背包問題應(yīng)用（作業(yè)）要把7種規(guī)格的包裝箱裝到兩輛鐵例3.一公司考慮在四個城市：北京、上海、廣州和武漢設(shè)立庫房。這些庫房負(fù)責(zé)向三個地區(qū)：華北、華中和華南地區(qū)發(fā)運(yùn)貨物，每個庫房每月可處理貨物1000件。在北京設(shè)庫房每月的成本為4.5萬元。上海為5萬元，廣州為7萬元，武漢為4萬元。每個地區(qū)的月平均需求量為：華北每月600件，華中每月700件，華南每月800件。發(fā)運(yùn)貨物的費(fèi)用（元/件）見下表：華北華中華南北京200400500上海300250450廣州600400250武漢300150350公司希望在滿足地區(qū)需要的前提下使平均月成本最小，且還要滿足以下條件：①如果在上海設(shè)立庫房，則必須也在武漢設(shè)庫房；②最多設(shè)立三個庫房；③武漢和廣州不能同時設(shè)立庫房。請建立一個滿足上述要求的整數(shù)規(guī)劃模型。3.工廠選址運(yùn)輸問題34例3.一公司考慮在四個城市：北京、上海、廣州和武漢設(shè)立庫房。

設(shè)每個月從倉庫i運(yùn)往地區(qū)j的產(chǎn)品的貨物數(shù)量為xij，引入0－1變量yi=1表示在Ai設(shè)立倉庫，否則不設(shè)。

設(shè)每個月的總花費(fèi)為z，則上述問題的數(shù)學(xué)模型為Minz＝200x11+400x12+500x13+300x21+250x22+450x23+600x31+400x32+250x33+300x41+150x42+350x43+45000y1+50000y2+70000y3+40000y4s.t.x11+x12+x13≤1000y1x21+x22+x23≤1000y2x31+x32+x33≤1000y3x41+x42+x43≤1000y4x11+x21+x31+x41≥600x12+x22+x32+x42≥700x13+x23+x33+x43≥800y2-y4≤0y1+y2+y3+y4≤3y3+y4≤

1xij≥0；yi＝0或1；i=1,2,3,4；j=1,2,335設(shè)每個月從倉庫i運(yùn)往地區(qū)j的產(chǎn)品的貨物數(shù)量為xij工廠選址運(yùn)輸問題

設(shè)有n個需求點，有m個可供選擇的廠址，每個廠址只能建一個工廠，在i處建廠，生產(chǎn)能力為Di，單位時間的固定成本為ai，需求點j的需求量為bj，從廠址i到需求點j的單位運(yùn)費(fèi)為Cij，問應(yīng)如何選擇廠址才能獲得經(jīng)濟(jì)上的總花費(fèi)最小的方案。36工廠選址運(yùn)輸問題設(shè)有n個需求點，有m個可供選

設(shè)在單位時間內(nèi)，從廠址i運(yùn)往需求點j的產(chǎn)品數(shù)量為xij，

引入0－1變量yi=1…在i地建廠0…否則設(shè)在單位時間內(nèi)的總花費(fèi)為z，則上述問題的數(shù)學(xué)模型為37設(shè)在單位時間內(nèi)，從廠址i運(yùn)往需1…在i地建廠4.集合覆蓋和布點問題集合覆蓋問題也是典型的整數(shù)規(guī)劃問題，在集合覆蓋問題中，一個給定集合（集合一）的每一個元素必須被另一個集合（集合二）的元素所覆蓋。在滿足覆蓋集合一所有元素的前提下，集合覆蓋問題的目標(biāo)是求需要的集合二的元素最少，該問題之所以又稱為布點問題，是因為它常被用于一些公共設(shè)施，如：學(xué)校、醫(yī)院、商業(yè)區(qū)、消防隊等設(shè)施的布點問題，解決如何既滿足公共要求，又使布的點最少，以節(jié)約投資費(fèi)用。384.集合覆蓋和布點問題集合覆蓋問題也是典型的例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ū)101016282720地區(qū)210024321710地區(qū)316240122721地區(qū)428321201525地區(qū)527172715014地區(qū)62010212514039例4：解決某市消防站的布點問題：某城市共有6個區(qū)，每個都可以解：Xj=1表地區(qū)設(shè)消防站，Xj=0表地區(qū)不設(shè)消防站。Z＝消防站總數(shù)，則模型如下：

MinZ=