实验十(整数规划).docx

大学数学实验实验报告
整数规划
化21
张腾
2012011864
2014-5-10
一、 实验目的
1、 练习建立实际问题的整数规划模型。
2、 掌握用LINGO软件求解整数规划问题。
二、 实验内
X(4,3)
X(5,6)
X(6,7)
X(7,2)
X(8,5)
X(9,4)-
X(10,10)-
未显示的X的值均为0。
以上数据是在历时7小时29分01秒后解出来的 解方案。
LINGO版本为LINGO11。使用了全局最优求
原始数据量较大，将有用的信息整理成表格直观的表示出来如下:
C0//1N^口报验实验实学数学大
城市 城 城 城市4 城市5 城市6 城市7 城市8 城市9
工1
涂红表示该员工在该城市。此方案即为最优解，话费总额最小为1142元。
事后我又在未使用全局求解的条件下进行了求解，LINGO选择的求解方法是分枝定法（B-B），可 以求得局部最优解，求解时间大大缩短，仅需数分钟至十几分钟，但求解结果和初值的选择有关，经过 多次实验，每次的求解过程和结果都不同，说明每次的迭代初值可能不同，求出的结果有1178， 1145，1142,说明所得结果只是局部最优解而非全局最优解，有一定机率所得的解就是全局最优解。
两种方法各有利弊，全局最优解费时，局部最优解效果不好，虽然结果与全局最优解比价接近了， 但并不准确，所以应根据具体情况选择合适的求解方法。
项目二：
（钢管下料）某钢管零售商从钢管厂进货，将钢管按照顾客的要求切割后售出。进货时得 到的原材料长度都是1850mm,现有一客户需要15根290mm、28根315mm、21根 350mm和30根455mm的钢管。为了简化生产过程，规定所使用的切割模式的种类不能超过 4种，使用频率最高的一种切割模式按照一根原料钢管价值的1/10增加费用。使用频次次之 的切割模式按照一根钢管价值的2/10增加费用，类推。且每种切割模式下的切割次数不能太 多（一根钢管最多生产5根产品）。此外，为了减少余料浪费，每种切割模式下的余料浪费不 能超过100mm。为了使总费用最少，应如何下料。
问题分析及模型建立：
这里我么参照书上226页对于钢管下料的普遍性分析方法。
首先我们用勺表示第i种模式（i=1,2,3,4）切割的原料钢管的的根数（由于切割方式的排 列顺序对于结果没有影响，我们不妨假设从1到4的切割频率依次下降），又设使用第i种切 割模式下每根原料钢管生产长290mm、315mm、350mm和455mm的钢管数量分别为 'll' 2i' 3i,l4i■
由题目条件我们可以得到目标函数为min = %1 + + +
为了满足客户要求我们有约束条件:
ri1%1+ri2%2+ri3%3+ri4%4^15 r21%1+r22%2+r23%3+r24%4^28 r31%1+r32%2+r33%3+r34%4^21 行1%1+行2%2+厂43也+行4%4二3° 且由于原料长度限制和余料的限制我们有限制条件：
1750 < 290r +315匚 + 350r + 455r < 1850
21 31 41
1750 < 290r + 315r + 350r + 455r < 1850
22 32 42
1750 < 290r + 315r + 350r + 455r < 1850
23 33 43
1750 < 290r +315匚 + 350r + 455r < 1850
24 34 44
且我们为了使得运算更加快速可以设立认为约束条件：
or1543Nh口报验实验实学数学大
首先我们不妨设
%1 > %2 > ^3 %4
其次所用的钢管至少为:
至多为:
15 X 290 + 28X 315 + 21X 350 + 30 X 455
1850
=19 （取整结果）
4
15 x 455 + 28 X 455 + 21 x 455 + 30 x 455
1850
=24 （取整结果）
所以我们有约束
1