问题描述
此问题源于道路养护决策，采用数学的0-1规划，决策需要养护的路段。其数学描述如下：
problem.png-401kB
目标函数：
obj = 1486 X3 + 495 X5 + 260 X6 + 2760 X8 + 120 X9 + 120 X10 + 2070 X11 + 2070 X12 + 90 X15 + 750
约束s.t.:
X3 + X5 + X6 + X8 + X11 + X12 >= 3
X3 + X8 + X11 + X12 >= 3
X8 + X9 + X10 + X11 >= 3
数据规范化
为了便于程序求解，将以上表达式的系数规范化为矩阵：
750 3 3 3
0 0 0 0
0 0 0 0
1486 1 1 0
0 0 0 0
495 1 0 0
2760 1 0 0
0 0 0 0
2760 1 1 1
120 0 0 1
120 1 0 1
2070 1 1 1
2070 1 1 0
0 0 0 0
0 0 0 0
90 0 0 0
MATLAB求解
采用整数线性规划函数intlinprog。
程序代码：
% 道路养护决策，0-1规划
%% 数据输入
clc,clear
% 标准化输入数据，由Excel导入
data = [
750 3 3 3
0 0 0 0
0 0 0 0
1486 1 1 0
0 0 0 0
495 1 0 0
2760 1 0 0
0 0 0 0
2760 1 1 1
120 0 0 1
120 1 0 1
2070 1 1 1
2070 1 1 0
0 0 0 0
0 0 0 0
90 0 0 0
];
const = data(1,:);
data(1,:) = [];
%% 优化参数定义
n = size(data,1); % 规划变量个数
f = data(:,1)'; % 目标函数系数
f_const = const(1); % 目标函数常数项
intcon = 1:n; % 所有系数均为整数
lb = zeros(1,n); % lower bound 为0
ub = ones(1,n); % upper bound 为1，即构造0-1 规划
A = -data(:,2:end)'; % 不等式约束方程系数
b = -const(:,2:end)'; % y约束方程右端b
Aeq = []; % 等式约束系数,为空
beq = [];
%% 优化求解
x = intlinprog(f,intcon,A,b,Aeq,beq,lb,ub); % 求解，注意优化问题定义最小值，-f
obj = sum(x.*f') + f_const; % 计算目标函数
clc
disp('x = ') % 结果显示
disp(x)
disp('obj =')
disp(obj)
y运算结果：
x =
0
0
1
0
0
0
0
0
1
1
1
1
0
0
0
obj =
6616
