生产工艺或管理中的优化问题
生产工艺或管理中的优化问题
某钢管零售商从钢管厂进货,将钢管按照顾客的要求切割后售出. 从钢管厂进货时得到的原料钢管都是19m 长.
⑴现有一客户需要50根4m 长、20根6m 长和15根8m 长的钢管,应如何下料最节省?
(2)零售商如果釆用不同切割模式太多,将会导致生产过程的复杂化,从而增加生产和管理成本,所以该零售商规定采用的切割模式不能超过3种. 此外,该客户除需要(1) 中的三种钢管外,还需要10根5m 长的钢管,应如何下料最节省?
1. 问题(1)的分析和建模
首先,应当确定哪些切割模式是可行且合理的,即按照客户需要在原料钢管上安排切割的一种组合,同时保证切割的余料不应该大于或等于客户需要钢管的
钢管下料的合理切割模式
问题化为在满足客户需要的条件下,按照哪些合理的模式,切割多少根原料钢管,最为节省. 而所谓节省,可以有两种标准,一是切割后剩余的总余料量最小,二是切割原料钢管的总根数最少. 下面将对这两个目标分别讨论.
决策变量:用x i 表示按照第i 种模式(i= 1,2,…,7) 切割的原料钢管的根数, 显然它们应当是非负整数.
决策目标:以切割后剩余的总余料量最小为目标,则由表可得
min Z1 = 3x1+ x2+ 3x3 + 3x4 +X 5+X 6 +3X 7
以切割原料钢管的总根数最少为目标,则有
minZ 2= x 1+x2+ x3+X 4+ X5+X 6+ X7
约束条件:为满足客户的需求, 按照表应有
4x 1+ 3x2 + 2x3+ x4+x5≧ 50 x 2+2x4+x5+3x6≧20 x 3 + x5+2x7≧ 15 X i ∈N, i = 1,…,7
这样,可以分别得到满足上面两个目标函数建立的整数规划模型. 2. 问题(2) 的分析和建模
由于钢管规格增加到4种,如果按照解问题⑴的思路,枚举法的工作量较大. 下面介绍整数非线性规划模型,可以同时确定切割模式和切割计划,这是带有普遍性的方法.
同问题(1) 类似,一个合理的切割模式的余料不应该大于或等于客户需要的钢管的最小尺寸,切割计划中只使用合理的切割模式,而由于本题中参数都是整数,所以合理切割模式的余量不能大于3m. 此外,这里我们仅选择总根数最少为目标进行求解.
决策变量:由于不同切割模式不能超过三种,可以用x i 表示按照第i 种模式 (i= 1,2,3)切割的原料钢管的根数,显然它们应当是非负整数. 设所使用的第i 种切割模式下每根原料钢管生产4m 长、5m 长、6m 长和8m 长的钢管数量分别为
r 1i ,r 2i ,r 3i ,r 4i (非负整数). 决策目标:以切割原料钢管的总根数最少为目
标,即目标为
min X 1+X2+X3
约束条件:为满足客户的需求,应有
r 11x 1+ r12x 2+r 13x 3≧ 50 r 21x 1+r22x 2 +r23x 3≧10 r 31x 1 + r32x 2 + r33x 3≧20 r 41x 1 + r42x 2 +r43x 3≧15
每一种切割模式必须可行合理,所以每根原料钢管的成品量不能超过19m, 也不能少于16m(余料不能大于3m) ,于是
16
这个问题中x j , rij 是变量.
于是,可以得到该问题的一个整数非线性规划模型. 但在实际用软件求解时, 为了减少运行时间,可以增加一些显然的约束条件,从而缩小可行解的搜索范围. 例如,由于3种切割模式的排列顺序是无关紧要的,所有不妨增加以下约束:
x 1>=x2>=x3