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

1.01背包問題

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

f=[-7;-8;-4;-5];%物品的價值
Aeq=[3,2,6,1];%物品質量的線性約束系數
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)

輸出結果：

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

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

2. 線性分配問題

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

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

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

輸出結果：

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

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

3. 工廠選址問題

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

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

c=[10,20,30;...%發貨成本
15,25,35];
f=reshape(c.',[],1);%目標函數向量
Aeq=[1,1,1,0,0,0;...%線性約束系數
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));%決策變量上界為無窮大，表示每個市場都可以供應或提供任意數量的產品
intcon =[ 1; 2; 3; 4; 5; 6 ];%數組 intcon 包含整數決策變量的索引。

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

輸出結果：

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

我們得到的最優解是在城市2建工廠，將部分產品提供到城市1和城市3，此時總成本最小為270。

4. 設備調度問題

設備調度問題是指如何規劃設備的工作安排，以使得生產效率最大。下面以一個簡單的設備調度問題為例：

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

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

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

輸出結果：

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

我們得到的最優解是將任務2和任務3分配給設備1，將任務1分配給設備2，此時總處理時間最小為21。

責任編輯：彭菁