《数学建模算法与应用》-整数规划-指派问题-matlab求解

《数学建模算法与应用》——司守奎，整数规划相关的指派问题，主要叙述如何利用构建系数矩阵来满足matlab的求解函数参数（等式约束和不等式约束）

反方向的杰伦

2895人浏览 · 2023-07-12 11:55:55

反方向的杰伦 · 2023-07-12 11:55:55 发布

题目

现有8辆车，指派其中5辆到5个不同工地去运货，各车到不同工地所需费用如下表。
问：分别指派哪5辆车到哪5个地方，总费用最少？

调车费用表
车号→ 地点↓	1	2	3	4	5	6	7	8
1	30	25	18	32	27	19	22	26
2	29	31	19	18	21	20	30	19
3	28	29	30	19	19	22	23	26
4	29	30	19	24	25	19	18	21
5	21	20	18	17	16	14	16	18

$C{ij}$ 表示第 j 台车指派到第 i 号地点需要的费用，引入0-1变量：

$X{ij}\left\{\begin{matrix} 1& & \\ 0& & \end{matrix}\right.$

（1表示第 j 台车指派去第 i 号地点，0表示第 j 台车不指派去第 i 号地点）

数学模型为：

$min\sum_{i=1}^{5}\sum_{j=1}^{8}C{ij}X{ij}$

$s.t\left\{\begin{matrix} \sum_{i=1}^{5} X{ij} <=1, &j=1...8& \\ \sum_{j=1}^{8} X{ij} =1, &i=1...5& \\ X{ij} =1 or 0& i=1...5;& j=1...8 \end{matrix}\right.$

分析

不等式约束

1台车最多去1个地方（要么1个要么0个）：
x(1,j) + x(2,j) + x(3,j) + x(4,j) + x(5,j) <= 1, j=1...8

按matlab函数参数要求的 系数矩阵 为
11111 00000 00000 00000 00000 00000 00000 00000，第j=1台车：x1+x2+x3+x4+x5<=1；
00000 11111 00000 00000 00000 00000 00000 00000，第j=2台车：x1+x2+x3+x4+x5<=1；
00000 00000 11111 00000 00000 00000 00000 00000，第j=3台车：x1+x2+x3+x4+x5<=1；
00000 00000 00000 11111 00000 00000 00000 00000，第j=4台车：x1+x2+x3+x4+x5<=1；
00000 00000 00000 00000 11111 00000 00000 00000，第j=5台车：x1+x2+x3+x4+x5<=1；
00000 00000 00000 00000 00000 11111 00000 00000，第j=6台车：x1+x2+x3+x4+x5<=1；
00000 00000 00000 00000 00000 00000 11111 00000，第j=7台车：x1+x2+x3+x4+x5<=1；
00000 00000 00000 00000 00000 00000 00000 11111，第j=8台车：x1+x2+x3+x4+x5<=1；

等式约束：

1个地方只能被1台车去（必须有1台车去）：
x(i,1) + x(i,2) + x(i,3) + x(i,4) + x(i,5) + x(i,6) + x(i,7)+ x(i,8) = 1, i=1...5

按matlab函数参数要求的 系数矩阵 为
10000 10000 10000 10000 10000 10000 10000 10000，第i=1地点：x1+x2+x3+x4+x5+x6+x7+x8=1；
01000 01000 01000 01000 01000 01000 01000 01000，第i=2地点：x1+x2+x3+x4+x5+x6+x7+x8=1；
00100 00100 00100 00100 00100 00100 00100 00100，第i=3地点：x1+x2+x3+x4+x5+x6+x7+x8=1；
00010 00010 00010 00010 00010 00010 00010 00010，第i=4地点：x1+x2+x3+x4+x5+x6+x7+x8=1；
00001 00001 00001 00001 00001 00001 00001 00001，第i=5地点： x1+x2+x3+x4+x5+x6+x7+x8=1；

matlab代码

clc;clear;close all;
data=[
    30 25 18 32 27 19 22 26;
    29 31 19 18 21 20 30 19;
    28 29 30 19 19 22 23 26;
    29 30 19 24 25 19 18 21;
    21 20 18 17 16 14 16 18;
];

%指派矩阵从5×8转为40×1
c=data(:);

%不等式约束
a=zeros(8,40);
for j=1:8
   a(j,[(j-1)*5+1 : j*5])=1; 
end
b=ones(8,1);

%等式约束
Aeq=zeros(5,40);
for i=1:5
    Aeq(i,[i:5:40])=1;
end
Beq=ones(5,1);

intcon=1:40; %40个变量均为整数

lb=zeros(40,1);
ub=ones(40,1);

[x,y]=intlinprog(c,intcon,a,b,Aeq,Beq,lb,ub);
x=reshape(x,[5,8])