基于整数规划工具箱的几个典型例子

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。现在需要确定一个工厂的位置以及各个市场的供求量，以使得总成本最小。

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。

责任编辑：彭菁