一、线性规划问题 题目1：
评分：
一车队有8辆车，这8辆车存放在不同地点，队长要派其中5辆到个不同的工地去运货。
各车从存放处调到装货地点所需费用列于表2.5.问应选用哪五辆车调到何处去运货，才能
使各车从所在地点调到装货地点所需的费用最少（要求分别用matlab和Lingo编程求解）？
表2.5 调车费用表- 装货地点 1 2 3 4 5 6 7 8 车号 1 2 3 4 5 （1）
解：记cij表示第j号车调到装货地点i所需的费用。引进0-1变量，
30 29 28 29 21 25 31 29 30 20 18 19 30 19 18 32 18 19 24 17 27 21 19 25 16 19 20 22 19 14 22 30 23 18 16 26 19 26 21 18 ?1,第j号车调到装货地点ixij??
0，第j号车厢没有调到装货地点?建立如下的0-1整数规划模型：
58min??cijxij
i?1j?1?5??xij?1,j?1...8?i?1?8s.t??xij?1,i?1...5 ?j?1?x?0或1,i?1,2...5;j?1,2....8?ij?（1）编写的matlab程序如下 clc,clear
c=[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]; c=c(:);
a=zeros(8,40); for j=1:8
a(j,[(j-1)*5+1:5*j])=1; end
b=ones(8,1); d=zeros(5,40); for i=1:5
d(i,[i:5:40])=1; end
e=ones(5,1);
[x,fval]=bintprog(c,a,b,d,e); x=reshape(x,[5,8]) fval 运行结果如下： x =
(1,3) 1 (2,4) 1 (3,5) 1 (5,6) 1 (4,7) 1
fval =
87
所以最优方案为x13?x24?x35?x56?x47?1,最优值为 87。
Lingo程序如下
model: sets:
col/1..5/:i; var/1..8/:j;
links(col,var):c,x; endsets data:
c=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; enddata
min=@sum(links:c*x);
@for(col(i):@sum(var(j):x(i,j))=1); @for(var(j):@sum(col(i):x(i,j))<=1); @for(links:@bin(x)); end
运行结果为
Objective value: 87.00000
X( 1, 1) 0.000000 30.00000 X( 1, 2) 0.000000 25.00000 X( 1, 3) 1.000000 18.00000 X( 1, 4) 0.000000 32.00000 X( 1, 5) 0.000000 27.00000 X( 1, 6) 0.000000 19.00000 X( 1, 7) 0.000000 22.00000 X( 1, 8) 0.000000 26.00000 X( 2, 1) 0.000000 29.00000 X( 2, 2) 0.000000 31.00000 X( 2, 3) 0.000000 19.00000 X( 2, 4) 1.000000 18.00000 X( 2, 5) 0.000000 21.00000 X( 2, 6) 0.000000 20.00000 X( 2, 7) 0.000000 30.00000 X( 2, 8) 0.000000 19.00000 X( 3, 1) 0.000000 28.00000 X( 3, 2) 0.000000 29.00000 X( 3, 3) 0.000000 30.00000 X( 3, 4) 0.000000 19.00000 X( 3, 5) 1.000000 19.00000 X( 3, 6) 0.000000 22.00000 X( 3, 7) 0.000000 23.00000 X( 3, 8) 0.000000 26.00000 X( 4, 1) 0.000000 29.00000 X( 4, 2) 0.000000 30.00000 X( 4, 3) 0.000000 19.00000 X( 4, 4) 0.000000 24.00000 X( 4, 5) 0.000000 25.00000 X( 4, 6) 0.000000 19.00000 X( 4, 7) 1.000000 18.00000 X( 4, 8) 0.000000 21.00000 X( 5, 1) 0.000000 21.00000