第二章

第一题

　　只需要把$x_1x_2$换成y在利用0-1规划的性质对条件进行变形即可。

第二题

　　很明显决策变量是小区，要达到全部覆盖只需要满足每个小区能选的小学数量大于1即可。
　　这题连数据都不需要。

model:
sets:
col/1..6/:x;
endsets
min=@sum(col:x);
x(1)+x(2)+x(3)>1;
x(2)+x(4)>1;
x(3)+x(5)>1;
x(4)+x(6)>1;
x(5)+x(6)>1;
x(1)>1;
x(2)+x(4)+x(6)>1;
end

第三题

　　没啥好说的引入0-1的限制就行。

model:
sets:
she/1..6/;
com/1..4/;
link(she,com):c,x;
endsets
data:
c=4 2 3 4
6 4 5 5
7 6 7 6
7 8 8 6
7 9 8 6
7 10 8 6;
enddata
max=@sum(link:c*x);
@for(she(i):@sum(com(j):x(i,j))=1);
@for(com(j):@sum(she(i):x(i,j))>1);
@for(link:@bin(x));
end

第四题

　　待更新

第五题

　　首先考虑到比较小的数据范围，可以搜索出料头小于1米的切割方案（大于1米则可以切出一根1米的棍子）。
　　对于这七种切割方案进行规划，即可得到最小使用根数（注意材料根数要是整数）。

model:
sets:
row/1..3/;
col/1..7/:x;
link(row,col):a;
endsets
data:
a=1 2 0 0 0 0 1
0 0 3 2 1 0 1
4 1 0 2 4 6 1;
enddata
min=@sum(col:x);
@for(row(i):@sum(col(j):a(i,j)*x(j))>100);
@for(col:@gin(x));
end

第六题

　　和第三题很像

model:
sets:
car/1..8/;
pos/1..5/;
link(pos,car):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(link:c*x);
@for(pos(i):@sum(car(j):x(i,j))=1);
@for(car(j):@sum(pos(i):x(i,j))<1);
@for(link:@bin(x));
end

Donate