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

1.01背包問題

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

f=[-7;-8;-4;-5];%物品的價值
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，放入背包中能獲得的最大價值為-9。

2. 線性分配問題

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

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

f=[-5;-7;-6;-8;-8];%任務(wù)收益
Aeq=[1,1,1,0,0;...%每個員工任務(wù)數(shù)量的線性約束系數(shù)
0,1,1,1,0;
0,0,1,1,1];
beq=[2;3;2];%每個員工需要完成的任務(wù)數(shù)量
lb=[0;0;0;0;0];%決策變量下界為0，表示每項任務(wù)都可以不分配
ub=[1;1;1;1;1];%決策變量上界為1，表示每項任務(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分配給第二位員工，此時能獲得的最大收益為-21。

3. 工廠選址問題

工廠選址問題是指如何選取有理的位置建設(shè)工廠，以使得運輸成本最小。下面以一個簡單的例子來說明：

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

c=[10,20,30;...%發(fā)貨成本
15,25,35];
f=reshape(c.',[],1);%目標函數(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，表示每個市場都可以不供應或不提供
ub=inf(size(f));%決策變量上界為無窮大，表示每個市場都可以供應或提供任意數(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，此時總成本最小為270。

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

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

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

%第一列是任務(wù)所需處理時間，第二列是任務(wù)對設(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同時只能處理一個任務(wù)
0,1,0,1,0,0;
0,0,0,0,1,1];
beq=[1;1;1];%所有任務(wù)都必須被分配
lb=zeros(size(f));%決策變量下界為0，表示每個任務(wù)不被分配或分配給任一設(shè)備都可以
ub=ones(size(f));%決策變量上界為1，表示每個任務(wù)僅能被分配給一臺設(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，此時總處理時間最小為21。

責任編輯：彭菁