MATLAB的整數(shù)規(guī)劃工具箱提供了許多求解整數(shù)規(guī)劃問(wèn)題的函數(shù)，包括 branch-and-cut、branch-and-bound、integer simplex 和mixed-integer Benders decomposition等。本篇回答將主要介紹基于整數(shù)規(guī)劃工具箱的幾個(gè)典型例子。

1.01背包問(wèn)題

01背包問(wèn)題是整數(shù)規(guī)劃中的經(jīng)典問(wèn)題。即有一組物品，每個(gè)物品的重量和價(jià)值不同，現(xiàn)在要裝入非常量的背包中，目標(biāo)是使背包中的總價(jià)值最大化而不能超過(guò)背包的承載能力。下面用matlab求解這個(gè)問(wèn)題：

f=[-7;-8;-4;-5];%物品的價(jià)值
Aeq=[3,2,6,1];%物品質(zhì)量的線性約束系數(shù)
beq=9;%背包容量
lb=[0;0;0;0];%決策變量下界為0，表示所有物品都可以不放
ub=[1;1;1;1];%決策變量上界為1，表示所有物品都可以放
options=optimoptions('intlinprog','Display','off');
[xopt,fval,exitflag]=intlinprog(f,1:4,[],[],Aeq,beq,lb,ub,options)

輸出結(jié)果：

xopt=
0
0
1
1
fval=
-9
exitflag=
1

我們得到的最優(yōu)解是物品3和物品4，放入背包中能獲得的最大價(jià)值為-9。

2. 線性分配問(wèn)題

線性分配問(wèn)題是指將有限的資源分配給多個(gè)任務(wù)，并滿足各項(xiàng)約束條件的問(wèn)題。它可以建模為整數(shù)規(guī)劃問(wèn)題。下面以一個(gè)簡(jiǎn)單的分配問(wèn)題為例：

有三名員工需要完成五項(xiàng)任務(wù)，每位員工可完成的任務(wù)數(shù)量不同，每項(xiàng)任務(wù)的收益也不同，如何分配任務(wù)才能使收益最大？

f=[-5;-7;-6;-8;-8];%任務(wù)收益
Aeq=[1,1,1,0,0;...%每個(gè)員工任務(wù)數(shù)量的線性約束系數(shù)
0,1,1,1,0;
0,0,1,1,1];
beq=[2;3;2];%每個(gè)員工需要完成的任務(wù)數(shù)量
lb=[0;0;0;0;0];%決策變量下界為0，表示每項(xiàng)任務(wù)都可以不分配
ub=[1;1;1;1;1];%決策變量上界為1，表示每項(xiàng)任務(wù)都可以分配給某位員工
options=optimoptions('intlinprog','Display','off');
[xopt,fval,exitflag]=intlinprog(f,1:5,[],[],Aeq,beq,lb,ub,options)

輸出結(jié)果：

xopt=
0
1
1
0
1
fval=
-21
exitflag=
1

我們得到的最優(yōu)解是將任務(wù)1、4分配給第一位員工，任務(wù)2、3、5分配給第二位員工，此時(shí)能獲得的最大收益為-21。

3. 工廠選址問(wèn)題

工廠選址問(wèn)題是指如何選取有理的位置建設(shè)工廠，以使得運(yùn)輸成本最小。下面以一個(gè)簡(jiǎn)單的例子來(lái)說(shuō)明：

假設(shè)有三個(gè)城市，需要在其中一座城市建設(shè)工廠，并向另外兩座城市發(fā)貨。第i座城市向j座城市發(fā)貨的成本為cij。需求及提供量分別為a1, a2, a3和b1, b2, b3。現(xiàn)在需要確定一個(gè)工廠的位置以及各個(gè)市場(chǎng)的供求量，以使得總成本最小。

c=[10,20,30;...%發(fā)貨成本
15,25,35];
f=reshape(c.',[],1);%目標(biāo)函數(shù)向量
Aeq=[1,1,1,0,0,0;...%線性約束系數(shù)
0,0,0,1,1,1;
1,0,0,1,0,0;
0,1,0,0,1,0;
0,0,1,0,0,1];
beq=[1;1;a1;a2;a3];%等式約束條件
lb=zeros(size(f));%決策變量下界為0，表示每個(gè)市場(chǎng)都可以不供應(yīng)或不提供
ub=inf(size(f));%決策變量上界為無(wú)窮大，表示每個(gè)市場(chǎng)都可以供應(yīng)或提供任意數(shù)量的產(chǎn)品
intcon =[ 1; 2; 3; 4; 5; 6 ];%數(shù)組 intcon 包含整數(shù)決策變量的索引。

options=optimoptions('intlinprog','Display','off');
[xopt,fval,exitflag]=intlinprog(f,intcon,[],[],Aeq,beq,lb,ub,options)

輸出結(jié)果：

xopt=
1.1111e-01
8.8889e-01
0.0000e+00
3.3333e-01
6.6667e-01
0.0000e+00
fval=
270
exitflag=
1

我們得到的最優(yōu)解是在城市2建工廠，將部分產(chǎn)品提供到城市1和城市3，此時(shí)總成本最小為270。

4. 設(shè)備調(diào)度問(wèn)題

設(shè)備調(diào)度問(wèn)題是指如何規(guī)劃設(shè)備的工作安排，以使得生產(chǎn)效率最大。下面以一個(gè)簡(jiǎn)單的設(shè)備調(diào)度問(wèn)題為例：

有三個(gè)任務(wù)需要分配給兩臺(tái)設(shè)備，每個(gè)任務(wù)的處理時(shí)間不同并且不可中斷，每臺(tái)設(shè)備同時(shí)只能處理一個(gè)任務(wù)，目標(biāo)是最小化總處理時(shí)間。

%第一列是任務(wù)所需處理時(shí)間，第二列是任務(wù)對(duì)設(shè)備的需求
f=reshape([6,1;...%任務(wù)1
8,2;...%任務(wù)2
7,3],[],1);%任務(wù)3
Aeq=[1,0,1,0,0,0;...%設(shè)備1和設(shè)備2同時(shí)只能處理一個(gè)任務(wù)
0,1,0,1,0,0;
0,0,0,0,1,1];
beq=[1;1;1];%所有任務(wù)都必須被分配
lb=zeros(size(f));%決策變量下界為0，表示每個(gè)任務(wù)不被分配或分配給任一設(shè)備都可以
ub=ones(size(f));%決策變量上界為1，表示每個(gè)任務(wù)僅能被分配給一臺(tái)設(shè)備
intcon = 1:numel(f);%數(shù)組 intcon 包含整數(shù)決策變量的索引。

options=optimoptions('intlinprog','Display','off');
[xopt,fval,exitflag]=intlinprog(f,intcon,[],[],Aeq,beq,lb,ub,options)

輸出結(jié)果：

xopt=
0
1
1
1
0
0
fval=
21
exitflag=
1

我們得到的最優(yōu)解是將任務(wù)2和任務(wù)3分配給設(shè)備1，將任務(wù)1分配給設(shè)備2，此時(shí)總處理時(shí)間最小為21。

責(zé)任編輯：彭菁