0-1規(guī)劃的應(yīng)用案例

0-1規(guī)劃的應(yīng)用

一、投資場(chǎng)所的選擇例1、京成畜產(chǎn)品公司計(jì)劃在市區(qū)的東、西、南、北四區(qū)建立銷售門市部，擬議中有10個(gè)位置Aj

(j＝1，2，3，…，10)可供選擇，考慮到各地區(qū)居民的消費(fèi)水平及居民居住密集度，規(guī)定：在東區(qū)由A1

，A2

，A3三個(gè)點(diǎn)至多選擇兩個(gè)；在西區(qū)由A4

，A5兩個(gè)點(diǎn)中至少選一個(gè)；在南區(qū)由A6

，A7兩個(gè)點(diǎn)中至少選一個(gè)；在北區(qū)由A8

，A9

，A10

三個(gè)點(diǎn)中至少選兩個(gè)。

Aj

各點(diǎn)的設(shè)備投資及每年可獲利潤由于地點(diǎn)不同都是不一樣的，預(yù)測(cè)情況見右表所示

(單位：萬元)。但投資總額不能超過720萬元，問應(yīng)選擇哪幾個(gè)銷售點(diǎn)，可使年利潤為最大?解：設(shè)：0--1變量xi=1(Ai點(diǎn)被選用）或0(Ai點(diǎn)沒被選用）。這樣我們可建立如下的數(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,……,10二、固定成本問題例2．高壓容器公司制造小、中、大三種尺寸的金屬容器，所用資源為金屬板、勞動(dòng)力和機(jī)器設(shè)備，制造一個(gè)容器所需的各種資源的數(shù)量如下表所示。不考慮固定費(fèi)用，每種容器售出一只所得的利潤分別為4萬元、5萬元、6萬元，可使用的金屬板有500噸，勞動(dòng)力有300人月，機(jī)器有100臺(tái)月，此外不管每種容器制造的數(shù)量是多少，都要支付一筆固定的費(fèi)用：小號(hào)是l00萬元，中號(hào)為150萬元，大號(hào)為200萬元?，F(xiàn)在要制定一個(gè)生產(chǎn)計(jì)劃，使獲得的利潤為最大。

0-1規(guī)劃的應(yīng)用(2)解：這是一個(gè)整數(shù)規(guī)劃的問題。設(shè)x1，x2，x3分別為小號(hào)容器、中號(hào)容器和大號(hào)容器的生產(chǎn)數(shù)量。各種容器的固定費(fèi)用只有在生產(chǎn)該種容器時(shí)才投入，為了說明固定費(fèi)用的這種性質(zhì)，設(shè)

yi=1(當(dāng)生產(chǎn)第i種容器,即xi＞0時(shí))或0（當(dāng)不生產(chǎn)第i種容器即xi=0時(shí)）引入約束xi≤Myi

，i=1，2，3，M充分大，以保證當(dāng)yi

=0時(shí)，xi=0。這樣我們可建立如下的數(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≥0

yj

為0--1變量，i=1,2,3例3．有四個(gè)工人，要分別指派他們完成四項(xiàng)不同的工作，每人做各項(xiàng)工作所消耗的時(shí)間如下表所示，問應(yīng)如何指派工作，才能使總的消耗時(shí)間為最少。

0-1規(guī)劃的應(yīng)用(3)三、指派問題

有n項(xiàng)不同的任務(wù)，恰好n個(gè)人可分別承擔(dān)這些任務(wù)，但由于每人特長不同，完成各項(xiàng)任務(wù)的效率等情況也不同。現(xiàn)假設(shè)必須指派每個(gè)人去完成一項(xiàng)任務(wù)，怎樣把n項(xiàng)任務(wù)指派給n個(gè)人，使得完成n項(xiàng)任務(wù)的總的效率最高，這就是指派問題。解：引入0—1變量xij，并令

xij

=1(當(dāng)指派第i人去完成第j項(xiàng)工作時(shí))或0（當(dāng)不指派第i人去完成第j項(xiàng)工作時(shí))．

這可以表示為一個(gè)0--1整數(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(甲只能干一項(xiàng)工作)

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

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

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

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四、分布系統(tǒng)設(shè)計(jì)例6．某企業(yè)在A1地已有一個(gè)工廠，其產(chǎn)品的生產(chǎn)能力為30千箱，為了擴(kuò)大生產(chǎn)，打算在A2，A3，A4，A5地中再選擇幾個(gè)地方建廠。已知在A2，A3，A4，A5地建廠的固定成本分別為175千元、300千元、375千元、500千元，另外，A1產(chǎn)量及A2，A3，A4，A5建成廠的產(chǎn)量，那時(shí)銷地的銷量以及產(chǎn)地到銷地的單位運(yùn)價(jià)(每千箱運(yùn)費(fèi))如下表所示。

a)問應(yīng)該在哪幾個(gè)地方建廠，在滿足銷量的前提下，使得其總的固定成本和總的運(yùn)輸費(fèi)用之和最小?

b)如果由于政策要求必須在A2，A3地建一個(gè)廠，應(yīng)在哪幾個(gè)地方建廠?0-1規(guī)劃的應(yīng)用(4)解：a)設(shè)xij為從Ai運(yùn)往Bj

的運(yùn)輸量(單位千箱)，

yi

=1(當(dāng)Ai被選中時(shí))或0（當(dāng)Ai沒被選中時(shí))．

這可以表示為一個(gè)整數(shù)規(guī)劃問題：Minz=175y2+300y3+375y4+500y5+8x11+4x12+3x13+5x21+2x22+3x23+4x31+3x32+4x33+9x41+7x42+5x43+10x51+4x52+2x53其中前4項(xiàng)為固定投資額，后面的項(xiàng)為運(yùn)輸費(fèi)用。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≥0yi為0--1變量，i=1,2,3,4,5；j=1,2,3

0-1規(guī)劃的應(yīng)用(5)五、投資問題

例5．某公司在今后五年內(nèi)考慮給以下的項(xiàng)目投資。已知：項(xiàng)目A：從第一年到第四年每年年初需要投資，并于次年末回收本利115%，但要求第一年投資最低金額為4萬元，第二、三、四年不限；項(xiàng)目B：第三年初需要投資，到第五年未能回收本利128％，但規(guī)定最低投資金額為3萬元，最高金額為5萬元；項(xiàng)目C：第二年初需要投資，到第五年未能回收本利140%，但規(guī)定其投資額或?yàn)?萬元或?yàn)?萬元或?yàn)?萬元或?yàn)?萬元。項(xiàng)目D：五年內(nèi)每年初可購買公債，于當(dāng)年末歸還，并加利息6%，此項(xiàng)投資金額不限。該部門現(xiàn)有資金10萬元，問它應(yīng)如何確定給這些項(xiàng)目的每年投資額，使到第五年末擁有的資金本利總額為最大?

解：1)設(shè)xiA、xiB、xiC、xiD

(i＝1，2，3，4，5)分別表示第i年年初給項(xiàng)目A，B，C，D的投資額；設(shè)yiA，yiB，是0—1變量，并規(guī)定取1時(shí)分別表示第i年給A、B投資，否則取0（i=1,2,3,4,5）。

設(shè)yiC

是非負(fù)整數(shù)變量，并規(guī)定：2年投資C項(xiàng)目8萬元時(shí)，取值為4；

2年投資C項(xiàng)目6萬元時(shí)，取值為3；

2年投資C項(xiàng)目4萬元時(shí)，取值為2；

2年投資C項(xiàng)目2萬元時(shí)，取值為1；

2年不投資C項(xiàng)目時(shí)，取值為0；

這樣我們建立如下的決策變量：

第1年第2年第3年第4年第5年

Ax1A

x2A

x3A

x4A

B

x3B

C

x2C(=20000y2C)

D

x1D

x2D

x3D

x4D

x5D

0-1規(guī)劃的應(yīng)用(6)2）約束條件：第一年：年初有100000元，D項(xiàng)目在年末可收回投資，故第一年年初應(yīng)把全部資金投出去，于是x1A+x1D=100000；第二年：A次年末才可收回投資故第二年年初的資金為1.06x1D，于是x2A+x2C+x2D=1.06x1D；第三年：年初的資金為1.15x1A+1.06x2D，于是x3A+x3B+x3D=1.15x1A+1.06x2D；第四年：年初的資金為1.15x2A+1.06x3D，于是x4A+x4D=1.15x2A+1.06x3D；第五年：年初的資金為1.15x3A+1.06x4D，于是x5D=1.15x3A+1.06x4D；關(guān)于項(xiàng)目A的投資額規(guī)定:x1A≥40000y1A

，x1A≤200000y1A

，200000是足夠大的數(shù)；保證當(dāng)

y1A=0時(shí)，x1A=0；當(dāng)y1A=1時(shí)，x1A≥40000。關(guān)于項(xiàng)目B的投資額規(guī)定:x3B≥30000y3B

，x3B≤50000y3B

；

保證當(dāng)

y3B=0時(shí)，x3B=0；當(dāng)y3B=1時(shí)，50000≥

x3B≥30000。