第一節(jié) 整數(shù)線性規(guī)劃問題

1、精品課程運(yùn)籌學(xué) 1.1 整數(shù)線性規(guī)劃問題舉例整數(shù)線性規(guī)劃問題舉例 1.2 解整數(shù)線性規(guī)劃問題的困難性解整數(shù)線性規(guī)劃問題的困難性 精品課程運(yùn)籌學(xué) 1.1 整數(shù)線性規(guī)劃問題舉例整數(shù)線性規(guī)劃問題舉例 整數(shù)線性規(guī)劃整數(shù)線性規(guī)劃(integer linear programming，ilp) 矩矩陣陣nma : n rc m rb t n xxx),( 1 , 2 , 1 , 0 i 1 , 0 i若若, 1nj 01規(guī)劃問題規(guī)劃問題 j是是,2 , 1n的非空真子集的非空真子集 混合整數(shù)線性規(guī)劃問題混合整數(shù)線性規(guī)劃問題 , 1nj 純整數(shù)線性規(guī)劃問題純整數(shù)線性規(guī)劃問題 , 2 , 1, 0 . min

2、 njiix x baxts xc i t 精品課程運(yùn)籌學(xué) 例例 3.1.13.1.1 投資決策問題投資決策問題 某某部部門門在在今今后后五五年年中中可可用用于于投投資資的的資資金金總總額額為為 b萬(wàn)萬(wàn)元元，有有)2( nn個(gè)個(gè)可可以以考考慮慮的的投投資資項(xiàng)項(xiàng)目目，假假 定定每每個(gè)個(gè)項(xiàng)項(xiàng)目目最最多多投投資資一一次次， 第第), 1(njj 個(gè)個(gè)項(xiàng)項(xiàng) 目目所所需需的的資資金金為為 j b萬(wàn)萬(wàn)元元，將將會(huì)會(huì)獲獲得得的的利利潤(rùn)潤(rùn)為為 j c 萬(wàn)萬(wàn)元元.問問應(yīng)應(yīng)如如何何選選擇擇投投資資項(xiàng)項(xiàng)目目，才才能能使使獲獲得得的的總總 利利潤(rùn)潤(rùn)最最大大. 精品課程運(yùn)籌學(xué) b 解 2 1 n 1 b 2 b n b

3、 1 c 2 c n c 個(gè)項(xiàng)目個(gè)項(xiàng)目決定投資第決定投資第j jj bb1 jj cc1 個(gè)項(xiàng)目個(gè)項(xiàng)目決定不投資第決定不投資第j j b00 j c00 個(gè)個(gè)項(xiàng)項(xiàng)目目；，決決定定不不投投資資第第 個(gè)個(gè)項(xiàng)項(xiàng)目目；，決決定定投投資資第第 j j x j 0 1 投資決策變量投資決策變量 精品課程運(yùn)籌學(xué) 設(shè)獲得的總利潤(rùn)為設(shè)獲得的總利潤(rùn)為z z，則上述問題的數(shù)學(xué)模型為，則上述問題的數(shù)學(xué)模型為 njx bxb ts xcz j n j jj n j jj , 110 0 . max 1 1 ，或或 0)1( jj xx 變量限制為整數(shù)本質(zhì)上是一個(gè)非線性約束，它不可變量限制為整數(shù)本質(zhì)上是一個(gè)非線性約束，它

4、不可 能用線性約束來代替它能用線性約束來代替它. 精品課程運(yùn)籌學(xué) 例例3.1.23.1.2 某某建建筑筑公公司司承承包包建建兩兩種種類類型型宿宿舍舍.甲甲種種宿宿舍舍每每幢幢 占占地地面面積積為為)(1025. 0 23 m ；乙乙種種宿宿舍舍每每幢幢占占地地面面 積積為為)(104 . 0 23 m .該該公公司司已已購(gòu)購(gòu)進(jìn)進(jìn))(103 23 m 的的建建 筑筑用用地地.計(jì)計(jì)劃劃要要求求建建甲甲種種宿宿舍舍不不超超過過 8 幢幢， 乙乙種種宿宿 舍舍不不超超過過 4 幢幢.建建甲甲種種宿宿舍舍一一幢幢可可獲獲利利 10 萬(wàn)萬(wàn)元元， 建建乙乙種種宿宿舍舍一一幢幢可可獲獲利利 20 萬(wàn)萬(wàn)元元.問

5、問應(yīng)應(yīng)建建甲甲、乙乙種種 宿宿舍舍各各幾幾幢幢，公公司司獲獲利利最最大大？ 精品課程運(yùn)籌學(xué) 解 設(shè)建設(shè)甲種宿舍設(shè)建設(shè)甲種宿舍 1 x幢， 乙種宿舍幢， 乙種宿舍 2 x幢， 則該問題幢， 則該問題 的的數(shù)學(xué)模型為數(shù)學(xué)模型為 這是一個(gè)純整數(shù)線性規(guī)劃問題這是一個(gè)純整數(shù)線性規(guī)劃問題. 且為整數(shù)且為整數(shù)0, 4 8 34 . 025. 0. 2010max 21 2 1 21 21 xx x x xxts xxz 精品課程運(yùn)籌學(xué) 例例 3.1.33.1.3 旅行售貨員問題旅行售貨員問題 （貨郎擔(dān)問題）（貨郎擔(dān)問題）(tsp問題）問題） 有有一一推推銷銷員員，從從城城市市 0 v出出發(fā)發(fā)，要要遍遍訪訪城

6、城市市 n vvv, 21 各各一一次次，最最后后返返回回 0 v.已已知知從從 i v到到 j v的的 旅旅費(fèi)費(fèi)為為 ij c.問問他他應(yīng)應(yīng)該該按按怎怎樣樣的的次次序序訪訪問問這這些些城城 市市，使使得得總總旅旅費(fèi)費(fèi)最最少少？（設(shè)設(shè)mcii ，m為為充充分分 大大的的正正數(shù)數(shù)，ni, 1 , 0 ） 精品課程運(yùn)籌學(xué) 解 對(duì)每一對(duì)城市對(duì)每一對(duì)城市 i v和和 j v，我們指定一個(gè)變量，我們指定一個(gè)變量 ij x，令，令 ，其它情況，其它情況 ；直接進(jìn)入直接進(jìn)入，如果推銷員決定從，如果推銷員決定從 0 1 ji ij vv x 首先，每個(gè)城市恰好進(jìn)入一次，即首先，每個(gè)城市恰好進(jìn)入一次，即 njx

7、 n i ij , 0, 1 0 nix n j ij , 0, 1 0 其次，每個(gè)城市恰好離開一次，即其次，每個(gè)城市恰好離開一次，即 精品課程運(yùn)籌學(xué) 第三，不能第三，不能出現(xiàn)多于一個(gè)互不連通的旅行路線圈，出現(xiàn)多于一個(gè)互不連通的旅行路線圈， 且不排除任何可能的旅行路線且不排除任何可能的旅行路線 niu njinnxuu i ijji , 1, 1 , 1 為實(shí)數(shù)為實(shí)數(shù) 如：六個(gè)城市的貨郎擔(dān)問題如：六個(gè)城市的貨郎擔(dān)問題 )5( n 令令 1 201201 xxx 1 534534 xxx 0 ij x其其它它 0 v 1 v 2 v 5 v 4 v 3 v 可歸結(jié)為可歸結(jié)為ilp的問題的問題 精

8、品課程運(yùn)籌學(xué) njinnxuu ijji 1 , 1 如：六個(gè)城市的貨郎擔(dān)問題如：六個(gè)城市的貨郎擔(dān)問題 5 n 令令 1 201201 xxx 1 534534 xxx 0 ij x其其它它 0 v 1 v 2 v 5 v 4 v 3 v 45 43 uu 45 54 uu 45 35 uu 45 精品課程運(yùn)籌學(xué) 1.2 解整數(shù)線性規(guī)劃問題的困難性解整數(shù)線性規(guī)劃問題的困難性 第一個(gè)問題：為什么不解對(duì)應(yīng)的第一個(gè)問題：為什么不解對(duì)應(yīng)的lp，然后將其解，然后將其解 舍入到最靠近的整數(shù)解呢？舍入到最靠近的整數(shù)解呢？ x 的的最最優(yōu)優(yōu)解解lp 的的最最優(yōu)優(yōu)解解ilp 的的可可行行區(qū)區(qū)域域lp 費(fèi)費(fèi)用用下下降降方方向向 0 1 x 2 x 精品課程運(yùn)籌學(xué) 第二個(gè)問題是：可否用枚舉法來解第二個(gè)問題是：可否用枚舉法來解ilp問題呢？問題呢？ 當(dāng)問題變量個(gè)數(shù)很少，且可行集合內(nèi)的格點(diǎn)個(gè)當(dāng)問題變量個(gè)數(shù)很少，且可行集合內(nèi)的格點(diǎn)個(gè) 數(shù)也很少時(shí)，枚舉法是可行的數(shù)也很少時(shí)，枚舉法是可行的.但對(duì)一般但對(duì)一般 ilp 問問 題， 枚舉法是無能為力的題， 枚舉法是無能為力的.如如 50 個(gè)城市的貨