lingo模型实例及求解.ppt

LINGO模型实例与求解
下料问题
背包问题
选址问题
指派问题
1
整理课件
问题1. 如何下料最节省 ?
下料问题
问题2. 客户增加需求：
原料钢管:每根19米
4米50根
6米20根
8米15根
客户需求
节省的标准是什么？
由于采用不同切割模式太多，会增加生产和管理成本，规定切割模式不能超过3种。如何下料最节省？
5米10根
2
整理课件
按照客户需要在一根原料钢管上安排切割的一种组合。
切割模式
余料1米
4米1根
6米1根
8米1根
余料3米
4米1根
6米1根
6米1根
合理切割模式的余料应小于客户需要钢管的最小尺寸
余料3米
8米1根
8米1根
钢管下料
3
整理课件
为满足客户需要，按照哪些种合理模式，每种模式切割多少根原料钢管，最为节省？
合理切割模式
2. 所用原料钢管总根数最少
模式
4米钢管根数
6米钢管根数
8米钢管根数
余料(米)
1
4
0
0
3
2
3
1
0
1
3
2
0
1
3
4
1
2
0
3
5
1
1
1
1
6
0
3
0
1
7
0
0
2
3
钢管下料问题1
两种标准
1. 原料钢管剩余总余量最小
4
整理课件
xi ~按第i 种模式切割的原料钢管根数(i=1,2,…7)
约束
满足需求
决策变量
目标1（总余量）
按模式2切割12根,按模式5切割15根，余料27米
模
式
4米
根数
6米
根数
8米
根数
余
料
1
4
0
0
3
2
3
1
0
1
3
2
0
1
3
4
1
2
0
3
5
1
1
1
1
6
0
3
0
1
7
0
0
2
3
需
求
50
20
15
最优解：x2=12, x5=15,
其余为0；
最优值：27
整数约束： xi 为整数
5
整理课件
当余料没有用处时，通常以总根数最少为目标
目标2（总根数）
约束条件不变
最优解：x2=15, x5=5, x7=5,
其余为0；
最优值：25。
xi 为整数
按模式2切割15根，按模式5切割5根，按模式7切割5根，共25根，余料35米
虽余料增加8米，但减少了2根
与目标1的结果“共切割27根，余料27米” 相比
6
整理课件
钢管下料问题2
对大规模问题，用模型的约束条件界定合理模式
增加一种需求：5米10根；切割模式不超过3种。
现有4种需求：4米50根，5米10根，6米20根，8米15根，用枚举法确定合理切割模式，过于复杂。
决策变量 (15维)
xi ~按第i 种模式切割的原料钢管根数(i=1,2,3)
r1i, r2i, r3i, r4i ~ 第i 种切割模式下，每根原料钢管生产4米、5米、6米和8米长的钢管的数量
7
整理课件
满足需求
模式合理：每根余料不超过3米
整数非线性规划模型
钢管下料问题2
目标函数（总根数）
约束条件
整数约束： xi ,r1i, r2i, r3i, r4i (i=1,2,3)为整数
8
整理课件
增加约束，缩小可行域，便于求解
原料钢管总根数下界：
(最佳切割方式)
特殊生产计划(简单切割方式)：对每根原料钢管
模式1：切割成4根4米钢管，需13根；
模式2：切割成1根5米和2根6米钢管，需10根；
模式3：切割成2根8米钢管，需8根。
原料钢管总根数上界：31
模式排列顺序可任定
需求：4米50根，5米10根，6米20根，8米15根
每根原料钢管长19米
9
整理课件
LINGO求解整数非线性规划模型
Local optimal solution found at iteration: 12211
Objective value:
Variable Value Reduced Cost
X1
X2