实验10整数规划问题.docx

实验 10 整数规划问题 【实验目的】 1、练习建立实际问题的整数规划问题。
2、掌握用 LINGO 求解整数规划问题。 【实验内容】 第一题
某公司指派n个员工到n个城市工作（每个城市单独一人），希望使所花费的总电话费用尽 可能少。n4 6 0 6 4 8 8 6
8 5 4 6 6 0 3 8 3 2
8 6 7 9 4 3 0 6 7 8
6 8 2 3 8 8 6 0 8 8
6 3 6 2 8 3 7 8 0 9
6 7 6 6 2 8 8 9 0;
enddata
min=****@sum(link(i,j):***@sum(link2(k,h):c(i,j)*d(k,h)*x(i,k)*x(j,h))); ***@for(link3(i,k):***@bin(x));
***@for(person(i):***@sum(city(k):x(i,k))=1);
***@for(city(k):***@sum(person(i):x(i,k))=1);
结果如下：
表格 1 最优指派情况
人员编号
1
2
3
4
5
6
7
8
9
10
去往城市
9
8
1
3
6
7
2
5
4
10
最终话费:z=1178
三、小结
第一题为运筹学中的二次指派问题，之前的 LINGO 求解的均为简单线性规划问题，本次 LINGO 求解共有100 个变量，因此求解的过程很缓慢。
第二题 某钢管零售商从钢管厂进货，将钢管按照顾客的要求切割后售出。从钢管厂进货时得到的 ,28根315mm,21根350mm和30
根 455mm 的钢管。为了简化生产过程，规定所使用的切割模式的种类不能超过4 种，使用 频率最高的一种切割模式按照一根原料钢管价值的1/10增加费用，依次类推，且每种切割
模式下的切割次数不能太多(一根原料钢管最多生产5根产品)。此外，为了减少余料浪费
每种切割模式下的余料浪费不能超过100mm •为了使总费用最小，应如何下料？
一、模型建立
x
决策变量：用i (i=1,234)来表示第i种模式下切割的原料钢管数。
目标函数：
设总费用为乙则有
minz 二 + + +
1234
约束条件：
设第 i 种模式下，每根原钢管生产 290mm,315mm,350mm,455mm 规格的钢管数为
r ,r , r , r
1i 2i 3i 4i 。
为满足客户对不同规格的钢管数量要求，应有：
工 r * x > 15
1i i
i=1
工 r * x > 28
2i i
< i=1
工 r * x > 21
3i i
i=1
工 r * x > 30
4i i
i=1
每一种切割模式必须可行合理，所以每根原料钢管的成品量不能超过 1850，也不能少于 1750(余料不能大于 100)，即：
1850 > r * 290 + r * 315 + r * 350 + r * 455 > 1750,i = 1,2,3,4
1i 2i 3i 4i
每种切割模式下的切割次数不能太多，一根原料钢管最多可生产5 根产品，故有如下约 束：
r + r + r + r < 5