Page 143 - 数学建模算法与应用

第五章 整数规划的探讨

第四节 指派问题的计算机求解

整数规划问题的求解可以使用 Lingo 等专用软件。对于一般的整数规划问题，
无法直接利用 Malab 的函数。但对于指派问题等 0 － 1 整数规划问题，可以直接
利用 Matlab 的函数 bintprog 进行求解，但使用 Matlab 软件求解数学规划问题有
一个缺陷，即必须把所有的决策变量化成一维决策向量。实际上对于多维变量的

数学规划问题，需要做一个变量替换，变量替换后，约束条件是很难写的，而使
用 Lingo 软件求解数学规划问题是很方便的。

例 求解下列指派问题，已知指派矩阵为

j
解 这里需要把二维决策变量 x i （i，j=1，·，5) 变成一维决策变量 y k （k=1，，
25），编写的 Matlab 程序如下：
c =[3 8 2 10 3；8 7 2 9 7；6 ４2 7 5
8 4 2 3 5;9 10 6 9 10］；

c=c(：)；
a = zeros(10，25)；
for i=1：5

a(i，(i-1)*5+1：5*i)=1；
a(5 +i，i：5：25) =1；
end

b =ones(10，1)；
[x，fval] =bintprog(c，[]，[]，a，b)；
x=reshape(x，[5，5])， fval

求得最优指派方案为 x15=x 23 =x 32 =x 44 =x 51 =1，最优值为 21。
求解的 Lingo 程序如下：
model：

133