合理下料问题的线性规划模型.pdf

39 合理下料问题的线性规划模型合理下料问题的线性规划模型合理下料问题的线性规划模型合理下料问题的线性规划模型代西武( 北京建筑工程学院基础部, 100044) 摘要总结出了合理下料问题的两种一般表述形式提出了线材合理下料问题的三个整数线性规划模型 II III IV 这些模型是严谨的没有漏洞和缺陷并且很容易在此基础上修改或添加一些其他约束条件便于在实际工程中进行应用指出了 1 中断言的不准确性建立了比 8 中模型简洁许多的模型指出了 5 中所建模型的缺陷和错误关键词线性规划合理下料数学模型 1 引言在建筑施工过程中一般需要应用大量多种规格的原材料( 如: 钢材木材塑钢铝合金等) 而生产厂家只能生产一定规格的原材料不能完全满足施工需要实际施工时还要经过裁截得到所需要的规格这样就不可避免的要产生一些残料这会造成损失和浪费因此合理下料尽量减少残料的发生减少损失和浪费对降低工程成本提高经济效益有着重大意义关于这方面的研究可参阅[ 1 0] [ 11 ] 合理下料问题是运筹学规划模型中一类极具代表性的应用问题这类问题在建立整数线性规划模型时需要思维的严谨性得到的整数线性规划模型则极具典型性这方面的研究较多可参阅[ 1 ] [9] 并且几乎所有的线性规划书中都有论述遗憾的是一些书中所建立的数学模型是错误的我们查阅了大量的书籍和文献总结出了合理下料问题的两种一般表述形式提出了线材合理下料问题的三个整数线性规划模型 II III IV 这些模型是严谨的没有漏洞和缺陷并且很容易在此基础上修改或添加一些其他约束条件便于在实际工程中进行应用指出了 1 中断言的不准确性建立了比 8 中模型简洁许多的模型指出了 5 中所建模型的缺陷和错误 2 合理下料问题的一般表述形式 第一种形式 合理下料问题合理下料问题合理下料问题合理下料问题设用同种规格的原材料下零件 mAAA,,, 21 ! 的毛坯已知在一件原材料上有 nBBB,,, 21 ! 种不同的下料方式每种下料方式可得各种毛坯的个数及每种零件的需要量见下表 1 问应怎样安排下料才能在满足需要量的条件下使得所用的原材料数量最少表1 各种下料方式及相应得到的毛坯数 各种下料方式各种零件 B 1 B 2 ! B n 各种零件的需求量 A 1 C 11 C 1 2 ! C 1 n b 1 A 2 C 2 1 C 22 ! C 2n B 2 " " " " " A m C m 1 C m2 ! C mn b m 40 其中 ji c 表示第 j 种下料方式得到第 i 种零件 i A 的毛坯数量对此下料问题我们设决策变量采取第 j种下料方式的原材料数量为 j x nj,,2, 1 ! = 从而可得到下面的整数线性规划模型 I ∑= = n j jxz 1 min (1) ?????=≥=≥∑= .,, 2 , 1,, 0 .,, 2 , 1, .. 1 njx mib x c ts j i n j jji ! ! 且为整数 (2) 在建立此模型时应注意不可将≥改为将约束条件写成没有松弛变量的等式是容易出现的错误 第二种形式 线材合理下料问题线材合理下料问题线材合理下料问题线材合理下料问题有一批原料线材如管材棒材钢筋角钢钢梁等每根长 l 米现需要截取 n种不同长度的毛坯长度为 j a 的