韓伯棠管理運籌學(xué)(第三版)-第八章-整數(shù)規(guī)劃

第八章

整數(shù)規(guī)劃運籌學(xué)1第六章整數(shù)規(guī)劃

§1整數(shù)規(guī)劃的圖解法

§2整數(shù)規(guī)劃的計算機求解

§3整數(shù)規(guī)劃的應(yīng)用*§4整數(shù)規(guī)劃的分枝定界法2整數(shù)規(guī)劃是一類要求變量取整數(shù)值的數(shù)學(xué)規(guī)劃，可分成線性和非線性兩類。整數(shù)線性規(guī)劃(IntegerLinearProgramming，簡記為ILP)問題研究的是要求變量取整數(shù)值時，在一組線性約束條件下一個線性函數(shù)最優(yōu)問題，是應(yīng)用非常廣泛的運籌學(xué)的一個重要分支。應(yīng)用實例：●工程投資問題●工作分配問題●選址問題●背包問題第六章整數(shù)規(guī)劃3根據(jù)變量的取值情況，整數(shù)線性規(guī)劃又可以分為純整數(shù)規(guī)劃〔所有變量取整數(shù)〕，混合整數(shù)規(guī)劃〔局部變量取整數(shù)〕，0-1整數(shù)規(guī)劃〔變量只取0或1〕等。求整數(shù)解的線性規(guī)劃問題，不是用四舍五入法或去尾法對線性規(guī)劃的非整數(shù)解加以處理就能解決的。整數(shù)線性規(guī)劃一些根本算法的設(shè)計是以相應(yīng)線性規(guī)劃的最優(yōu)解為出發(fā)點而開展出來的。整數(shù)規(guī)劃是數(shù)學(xué)規(guī)劃中一個較弱的分支，目前有成熟的方法解線性整數(shù)規(guī)劃問題，而非線性整數(shù)規(guī)劃問題，還沒有好的方法。第六章整數(shù)規(guī)劃4§1整數(shù)規(guī)劃的圖解法例1.某公司擬用集裝箱托運甲、乙兩種貨物，這兩種貨物每件的體積、重量、可獲利潤以及托運所受限制如表所示。甲種貨物至多托運4件，問兩種貨物各托運多少件，可使獲得利潤最大。貨物每件體積(立方米)每件重量(百千克)每件利潤（百元）甲乙19527344023托運限制1365140

5貨物每件體積(立方米)每件重量(百千克)每件利潤（百元）甲乙19527344023托運限制1365140

解：設(shè)x1、

x2分別為甲、乙兩種貨物托運的件數(shù)，建立模型。目標函數(shù)：Maxz=2x1+3x2約束條件：s.t.195

x1+273x2≤13654

x1+40x2≤140

x1≤4

x1，x2≥0,為整數(shù)。如果去掉最后一個約束，就是一個線性規(guī)劃問題.§1整數(shù)規(guī)劃的圖解法6利用圖解法，得到線性規(guī)劃的最優(yōu)解為x1=2.44,x2=3.26,目標函數(shù)值為14.66。由圖表可看出,整數(shù)規(guī)劃的最優(yōu)解為x1=4,x2=2,目標函數(shù)值為14。Maxz=2x1+3x2195x1+273x2=13654x1+40x2=1404231123x2x1§1整數(shù)規(guī)劃的圖解法7對于整數(shù)規(guī)劃，易知有以下性質(zhì)：性質(zhì)1：任何求最大目標函數(shù)值的純整數(shù)規(guī)劃或混合整數(shù)規(guī)劃的最大目標函數(shù)值小于或等于相應(yīng)的線性規(guī)劃的最大目標函數(shù)值；任何求最小目標函數(shù)值的純整數(shù)規(guī)劃或混合整數(shù)規(guī)劃的最小目標函數(shù)值大于或等于相應(yīng)的線性規(guī)劃的最小目標函數(shù)值?！?整數(shù)規(guī)劃的圖解法8§2分支定界法以及計算機求解分枝定界法步驟：求解與IP相應(yīng)的LP問題，可能會出現(xiàn)下面幾種情況：假設(shè)所得的最優(yōu)解的各變量恰好取整數(shù)，那么這個解也是原整數(shù)規(guī)劃的最優(yōu)解，計算結(jié)束。假設(shè)無可行解，那么原整數(shù)規(guī)劃問題也無可行解，計算結(jié)束。假設(shè)有最優(yōu)解，但其各分量不全是整數(shù)，那么這個解不是原整數(shù)規(guī)劃的最優(yōu)解，轉(zhuǎn)下一步。9分枝定界法步驟〔續(xù)〕：從不滿足整數(shù)條件的基變量中任選一個xl進行分枝，它必須滿足xl[xl]或xl[xl]+1中的一個，把這兩個約束條件加進原問題中，形成兩個互不相容的子問題〔分枝〕。定界：把滿足整數(shù)條件各分枝的最優(yōu)目標函數(shù)值作為上〔下〕界，用它來判斷分枝是保存還是剪枝。剪枝：把那些子問題的最優(yōu)值與界值比較，凡不優(yōu)或不能更優(yōu)的分枝全剪掉，直到每個分枝都查清為止。10例：分支定界法的求解思路圖線性規(guī)劃1Z1=14.66X1=2.44X2=3.26z=13,

=14.66線性規(guī)劃2Z2=13.90X1=2X2=3.30X1≤2X1≥3X2≤2X2≥3z=13,

=14.58z=14,

=14線性規(guī)劃4Z4=14.00X1=4X2=2線性規(guī)劃5無可行解線性規(guī)劃3Z3=14.58X1=3X2=2.8611例2：

Maxz=3x1+x2+3x3

s.t.-x1+2x2+x3≤44x2-3x3≤2

x1-3x2+2x3≤3x1,x2,x3≥0,為整數(shù)例3：

Maxz=3x1+x2+3x3

s.t.-x1+2x2+x3≤44x2-3x3≤2

x1-3x2+2x3≤3

x3≤1

x1,x2,x3≥0

x1，x3

為整數(shù)，x3

為0-1變量用《管理運籌學(xué)》軟件求解得：

x1=5x2=2x3=2用《管理運籌學(xué)》軟件求解得:z=16.25x1=4x2=1.25x3=1§2整數(shù)規(guī)劃的計算機求解12§3整數(shù)規(guī)劃的應(yīng)用一、投資場所的選擇例4、京成畜產(chǎn)品公司方案在市區(qū)的東、西、南、北四區(qū)建立銷售門市部，擬議中有10個位置Aj(j=1,2,3,…,10)可供選擇，考慮到各地區(qū)居民的消費水平及居民居住密集度，規(guī)定:在東區(qū)由A1，A2，A3三個點至多項選擇擇兩個；在西區(qū)由A4，A5兩個點中至少選一個；在南區(qū)由A6，A7兩個點中至少選一個；在北區(qū)由A8，A9，A10三個點中至少選兩個。

Aj各點的設(shè)備投資及每年可獲利潤由于地點不同都是不一樣的，預(yù)測情況見表所示(單位：萬元)。但投資總額不能超過720萬元，問應(yīng)選擇哪幾個銷售點，可使年利潤為最大?13解：設(shè)：0--1變量xi

=1(Ai點被選用)或0(Ai點沒被選用)。這樣我們可建立如下的數(shù)學(xué)模型：Maxz=36x1+40x2+50x3+22x4+20x5+30x6+25x7+48x8+58x9+61x10s.t.100x1+120x2+150x3+80x4+70x5+90x6+80x7+140x8+160x9+180x10≤720

x1+x2+x3≤2

x4+x5≥1

x6+x7≥1

x8+x9+x10≥2

xj≥0

且xj為0--1變量，i=1,2,3,…,1014例5、解決某市消防站的布點問題，該城市有6個區(qū)，每個區(qū)都可以建消防站。市政府希望設(shè)置的消防站最少，但必須滿足在城市的任何地區(qū)發(fā)生火警時，消防車要在15分鐘內(nèi)趕到現(xiàn)場。據(jù)實地測定，各區(qū)之間消防車行駛的時間如下表所示，請幫助該市制定一個最省的方案。12345610101628272021002432171031624012272142832120152552717271501462010212514015設(shè)xi=1,0;1－i區(qū)建消防站，0－i區(qū)不建消防站，i=1,…6minz=x1+x2+x3+x4+x5+x6s.t.x1+x2≥1,x3+x4

≥1,x3+x4+x5

≥1x4+x5+x6

≥1,x2+x6

≥1

xi=0,1;i=1,…6123456101016282720210024321710316240122721428321201525527172715014620102125140161718練習(xí)、背包問題背包可裝入8單位重量，10單位體積物品。假設(shè)背包中每件物品至多只能裝一個，怎樣才能使背包裝的物品價值最高。物品名稱重量體積價值1書52202攝像機31303枕頭14104休閑食品23185衣服451519解：xi為是否帶第i種物品MaxZ=20x1+

30x2+10x3+18x4+15x55x1+3x2+x3+2x4+4x5

82x1+x2+4x3+3x4+5x510xi為0,1物品名稱重量體積價值1書52202攝像機31303枕頭14104休閑食品23185衣服451520一般形式：,整數(shù)

xi為i物品攜帶數(shù)量ai為i物品單位重量ci為i物品重要性估價b為最大負重21§3整數(shù)規(guī)劃的應(yīng)用二、固定本錢問題例6．高壓容器公司制造小、中、大三種尺寸的金屬容器，所用資源為金屬板、勞動力和機器設(shè)備，制造一個容器所需的各種資源的數(shù)量如表所示。不考慮固定費用，每種容器售出一只所得的利潤分別為4萬元、5萬元、6萬元，可使用的金屬板有500噸，勞動力有300人/月，機器有100臺/月，此外不管每種容器制造的數(shù)量是多少，都要支付一筆固定的費用：小號是l00萬元，中號為150萬元，大號為200萬元?，F(xiàn)在要制定一個生產(chǎn)方案，使獲得的利潤為最大。22解：這是一個整數(shù)規(guī)劃的問題。設(shè)x1，x2，x3分別為小號容器、中號容器和大號容器的生產(chǎn)數(shù)量。各種容器的固定費用只有在生產(chǎn)該種容器時才投入，為了說明固定費用的這種性質(zhì)，設(shè)yi=1(當生產(chǎn)第i種容器,即xi＞0時)或0〔當不生產(chǎn)第i種容器即xi=0時〕。引入約束xi≤Myi，i=1，2，3，M充分大，以保證當yi=0時，xi=0?！?整數(shù)規(guī)劃的應(yīng)用23這樣我們可建立如下的數(shù)學(xué)模型：Maxz=4x1+5x2+6x3-100y1-150y2-200y3s.t.2x1+4x2+8x3≤5002x1+3x2+4x3≤300

x1+2x2+3x3≤100xi≤Myi，i=1，2，3，M充分大

xj≥0yj為0--1變量，i=1,2,3§3整數(shù)規(guī)劃的應(yīng)用24三、指派問題有n項不同的任務(wù)，恰好n個人可分別承擔這些任務(wù)，但由于每人特長不同，完成各項任務(wù)的效率等情況也不同?，F(xiàn)假設(shè)必須指派每個人去完成一項任務(wù)，怎樣把n項任務(wù)指派給n個人，使得完成n項任務(wù)的總的效率最高，這就是指派問題?！?整數(shù)規(guī)劃的應(yīng)用25例7．有四個工人，要分別指派他們完成四項不同的工作，每人做各項工作所消耗的時間如下表所示，問應(yīng)如何指派工作，才能使總的消耗時間為最少?！?整數(shù)規(guī)劃的應(yīng)用26解：引入0—1變量xij，并令

xij=1(當指派第i人去完成第j項工作時)或0(當不指派第i人去完成第j項工作時)．這可以表示為一個0--1整數(shù)規(guī)劃問題：Minz=15x11+18x12+21x13+24x14+19x21+23x22+22x23+18x24+26x31+17x32+16x33+19x34+19x41+21x42+23x43+17x44§3整數(shù)規(guī)劃的應(yīng)用27整數(shù)規(guī)劃模型為：Minz=15x11+18x12+21x13+24x14+19x21+23x22+22x23+18x24+26x31+17x32+16x33+19x34+19x41+21x42+23x43+17x44s.t.x11+x12+x13+x14=1(甲只能干一項工作)

x21+x22+x23+x24=1(乙只能干一項工作)

x31+x32+x33+x34=1(丙只能干一項工作)

x41+x42+x43+x44=1(丁只能干一項工作)

x11+x21+x31+x41=1(A工作只能一人干)

x12+x22+x32+x42=1(B工作只能一人干)

x13+x23+x33+x43=1(C工作只能一人干)

x14+x24+x34+x44=1(D工作只能一人干)

xij為0--1變量，i,j=1,2,3,4§3整數(shù)規(guī)劃的應(yīng)用28四、分布系統(tǒng)設(shè)計例8．某企業(yè)在A1地已有一個工廠，其產(chǎn)品的生產(chǎn)能力為30千箱，為了擴大生產(chǎn)，打算在A2，A3，A4，A5地中再選擇幾個地方建廠。在A2，A3，A4，A5地建廠的固定本錢分別為175千元、300千元、375千元、500千元，另外，A1產(chǎn)量及A2，A3，A4，A5建成廠的產(chǎn)量，那時銷地的銷量以及產(chǎn)地到銷地的單位運價(每千箱運費)如下表所示。a)問應(yīng)該在哪幾個地方建廠，在滿足銷量的前提下，使得其總的固定本錢和總的運輸費用之和最小?b)如果由于政策要求必須在A2，A3地建一個廠，應(yīng)在哪幾個地方建廠?§3整數(shù)規(guī)劃的應(yīng)用29§3整數(shù)規(guī)劃的應(yīng)用30解：a)設(shè)xij為從Ai運往Bj的運輸量(單位千箱)，yk=1(當Ak被選中時)或0〔當Ak沒被選中時),k=2,3,4,5．這可以表示為一個整數(shù)規(guī)劃問題：Minz=175y2+300y3+375y4+500y5+8x11+4x12+3x13+5x21+2x22+3x23+4x31+3x32+4x33+9x41+7x42+5x43+10x51+4x52+2x53其中前4項為固定投資額，后面的項為運輸費用?！?整數(shù)規(guī)劃的應(yīng)用31s.t.x11+x12+x13≤30(A1廠的產(chǎn)量限制)

x21+x22+x23≤10y2(A2廠的產(chǎn)量限制)

x31+x32+x33≤20y3(A3廠的產(chǎn)量限制)

x41+x42+x43≤30y4(A4廠的產(chǎn)量限制)

x51+x52+x53≤40y5(A5廠的產(chǎn)量限制)

x11+x21+x31+x41+x51=30(B1銷地的限制)

x12+x22+x32+x42+x52=20(B2銷地的限制)

x13+x23+x33+x43+x53=20(B3銷地的限制)

xij≥0,i=1,2,3,4,5;j=1,2,3,yk為0-1變量,k=2,3,4,5.32整數(shù)規(guī)劃模型為：Minz=175y2+300y3+375y4+500y5+8x11+4x12+3x13+5x21+2x22+3x23+4x31+3x32+4x33+9x41+7x42+5x43+10x51+4x52+2x53其中前4項為固定投資額，后面的項為運輸費用。s.t.x11+x12+x13≤30(A1廠的產(chǎn)量限制)

x21+x22+x23≤10y2(A2廠的產(chǎn)量限制)

x31+x32+x33≤20y3(A3廠的產(chǎn)量限制)

x41+x42+x43≤30y4(A4廠的產(chǎn)量限制)

x51+x52+x53≤40y5(A5廠的產(chǎn)量限制

x11+x21+x31+x41+x51=30(B1銷地的限制)

x12+x22+x32+x42+x52=20(B2銷地的限制)

x13+x23+x33+x43+x53=20(B3銷地的限制)xij≥0,i=1,2,3,4,5;j=1,2,3,yk為0-1變量,k=2,3,4,5.33五、投資問題例9.某公司在今后五年內(nèi)考慮給以下的工程投資.：工程A：從第一年到第四年每年年初需要投資，并于次年末回收本利115%，但要求第一年投資最低金額為4萬元，第二、三、四年不限；工程B：第三年初需要投資，到第五年末能回收本利128％，但規(guī)定最低投資金額為3萬元，最高金額為5萬元；工程C：第二年初需要投資，到第五年末能回收本利140%，但規(guī)定其投資額或為2萬元或為4萬元或為6萬元或為8萬元。工程D：五年內(nèi)每年初可購置公債，于當年末歸還，并加利息6%，此項投資金額不限。該部門現(xiàn)有資金10萬元，問它應(yīng)如何確定給這些工程的每年投資額，使到第五年末擁有的資金本利總額為最大?§3整數(shù)規(guī)劃的應(yīng)用34解：1)設(shè)xiA、xiB、xiC、xiD(i＝1，2，3，4，5)分別表示第i年年初給工程A，B，C，D的投資額；設(shè)yiA，yiB，是0-1變量，并規(guī)定取1時分別表示第i年給A、B投資，否那么取0〔i=1,2,3,4,5〕。設(shè)yiC是非負整數(shù)變量,并規(guī)定:第2年投資C工程8萬元時,取值為4；第2年投資C工程6萬元時,取值3;第2年投資C工程4萬元時,取值2；第2年投資C工程2萬元時,取值1;第2年不投資C時,取值0;這樣我們建立如下的決策變量：第1年第2年第3年第4年第5年Ax1Ax2Ax3Ax4ABx3BCx2C=20000y2CDx1Dx2D