Question

高分悬赏：运筹学搬迁问题

如题：某厂计划将它的一部分在市区的生产车间搬至该市的卫 星城镇 , 好处是土地、房租费及排污处理费用等都较便宜 , 但这样做会增加车 间之间的交通运输费用 。
设该厂原在市区车间有 A,B,C,D,E 五个 , 计划搬迁去的卫星城镇有甲、
乙两处 。规定无论留在市区或甲、乙两卫星城镇均不多于 3 个车间 。
从市区搬至卫星城带来的年费用节约见表 1所示 。

A B C D E
搬至甲 100 150 100 200 50
搬至乙 100 200 150 150 150

但搬迁后带来运输费用增加由 Cik 和 djl 值决定 , Cik为 i和 k 车间之间的年运量 ,djl 为市区同卫星城镇间单位运量的运费 , 具体数据分别见表 2 和表3。

表2 Cik 值 （单位：吨/年）

B C D E
A 0 1000 1500 0
B 1400 1200 0
C 0 2000
D 700

表3 djl 值 （单位：元/吨）

甲 乙 市区
甲 50 140 130
乙 50 90
市区 100
试为该厂确定一个最优的车间搬迁方案。
小弟拿到这道题目，想破脑壳，理不出一条思路来，有哪位高手给出一条正确的解答，小弟愿意出100两银子（100分）酬谢！
由于原问题的表格无法复制,而且也无法控制在网页上显示的格式,故现在原文件一并附上,小弟诚心求教,希望高手不吝赐教,小弟一定勤上百度,多弄得分奉上.http://blog.szu.edu.cn/attach/8DA6D9A5-CDAF-46C2-B6B0-CA33BE56C03D
非常感谢楼下的大哥，不过你能不能把你的约束条件用数学式子表达一下，我想用EXCEL做，我对灵狗不熟悉……

Answer 1

可以考虑0－1整数规划；ABCDE 各从三个地方选一个！

只是不知道后面那些在讲什么？都不知道什么是目标！

如果是费用：搬可节约费用，多了城市间的运费，即题中djl。
好像Cik都用不到。因为在一个城市里也要相互运输嘛！！

如果不考虑Cik，只考虑节约费用和城市间运输费用。
就又碰到一个问题：多了城市间运输费用怎么算。
是不是各个车间的运输情况（即，连同情况），是不是，每年A要运输到每个车间，B要运输到每个车间，C要运输到每个车间，D要运输到每个车间，E要运输到每个车间.如果是，那么解决思路如下：

由第一步0－1变量可以得到一种方案：并可算数节约了多少，几个在市，在甲，在乙。

通过几个在市，在甲，在乙联合djl值，可得到增加的运输费。

最后就是选出一个方案使得费用最小了。

可能用程序方便点。手算的话0－1好像只能是穷举法（印象中），
由于规定无论留在市区或甲、乙两卫星城镇均不多于 3 个车间
则方案有150种，手算不太可能！！！

补充：
哦，是我搞错了。本来把Cik看成运费了。
Cik为 i和 k 车间之间的年运量
djl 为市区同卫星城镇间单位运量的运费
如果知道了一个方案，那i运到j的dij值知道×Cij就是i到j的运费了
即确定一种方案后，就通过两个联立可知i车间到j车间的年运费。

而第一张表是年运费节约：方案确定，节约费用也已知。

这样目标就很明确，就是事年运费最少！

写了个LINGO程序，希望对你有帮助！
sets:
a/1..3/:;!三个地方;
b/1..5/:;!五个车间;
link(a,b):x,jie;!x为0－1变量，jie为节约费用;
aa(a,a):dij;!dig就是两车间的运量;
bb(b,b):cik,y;!cik就是两地之间的运费单价;!y为求每个方案下i车间到j车间的运费;
bbaa(b,b,a,a):yy; !为计算y做辅助作用;
endsets
data:
jie=100 150 100 200 50
100 200 150 150 150
0 0 0 0 0;
cik=0 0 1000 1500 0
0 0 1400 1200 0
0 0 0 0 2000
0 0 0 0 700
0 0 0 0 0;
dij=50 140 130
140 50 90
130 90 100;
enddata
!搬迁约束;
@for(a(i): @sum(b(j): x(i,j))<=3);
@for(b(j): @sum(a(i): x(i,j)) =1);
@for(link(i,j): @bin(x));!0－1约束;
!计算y;
@for(bb(m,n)|m#lt#n:
@for(aa(i,j):
yy(m,n,i,j)=@if(x(i,m)#eq#1#and#x(j,n)#eq#1,cik(m,n)*dij(i,j),0)));
@for(bb(m,n): @sum(aa(i,j): yy(m,n,i,j))=y(m,n));
!目标函数;
min=-@sum(link: x*jie)+@sum(bb: y);

结果:
总费用580500.0
方案A－市 B－乙 C－乙 D－市 E－乙

说明由于题中好像说明部分搬出，所以可能要加一个约束条件使有一个车间留在市区。

表达式我也不知道怎么表示:尽力!
设X为0－1变量阵:1为选择，0为不选择，则X为3×5的矩阵

约束条件1：各地不多于 3 个车间
xi1+xi2+...+xi5<=3 i=1,2,3;

约束条件2：每个车间只能安排在一个地方
x1i+x2i+x3i=1; i=1,2,3,4,5;

目标使费用最小
节约费用＝X.*节约费用矩阵再求和。
（“.*”为矩阵中相应位置相乘。 节约费用矩阵，只要将搬到市区设为0，就也是3×5的矩阵了）

接下来就是算运费，这个比较麻烦！
以A到B的运费举例：
思想就是找到X第1列1是在哪行，记为m，X的第2列1是在哪行，记为n，通过m，n对应dij表就可以知道A到B的年运费单价。和运量相乘就可得到运费。
其他一次这么确定。

感觉这个东西太难搞了！及时用了程序也是最笨的办法。希望有更好方法！

Answer 2

表一中的数值没有单位。每年节约100元？100万元？若是100元，实在可以忽略不计。

若可以使用计算机，那么写个程序可以解决问题。将5个车间安排在3个地方的所有可能列出来，计算每种安排的费用（运费-节约），费用最低的即是最优。

5个车间安排在3个地方，要求某地不超过3个车间，总共有210种安排方案。