薄膜切割的数学建模

薄膜切割问题 摘要 本文解决的是在不同的要求下如何确定薄膜切割任务的问题 属于优化问 题中的一维下料问题 为解决该问题 本文建立了两个整数规划模型 采用整 数规划近似算法和贪心算法对模型进行求解 对于问题一 本文以余料最少为第一优化目标 最大余料宽度最大和切割 方式数最少为第二优化目标 各规格小卷的订单数为约束条件 建立整数规划 模型 由于该问题属于 NP 完全问题 只能考虑用近似算法 对该模型本文用整 数规划近似算法和贪心算法进行求解 对这两种算法结果的优劣进行分析比较 可供选择 整数规划近似解法的结果为 利用率 99 94 切割的大卷总卷数 262 切割方式 16 余料最大宽 180 具体切割方案见表 5 1 贪心算法的结果 为 利用率 99 26 切割的大卷总卷数 264 切割方式 16 余料最大宽度 900 具体切割方案见表 5 2 两种算法结果的比较见表 5 3 对于问题二 本文采用与问题一相同的优化目标 约束条件为订单数量约 束和加急订单在规定期限内完成约束 以此建立整数规划模型 根据问题一的 分析比较得出整数规划近似解法更适合解决此问题 问题二采用整数规划近似 解法求解 结果为 利用率 99 94 切割的大卷总卷数 262 切割方式 41 余 料最大宽 50 完成任务需要 11 天 完成加急订单需要 7 天 具体切割方案见表 6 1 按表所示的顺序进行切割生产 关键词 一维下料 整数规划 整数规划近似解法 贪心算法 一 问题重述 1 1 问题背景 随着高分子合成技术的不断进步 具有独特物理机械性能的新型聚合物可 广泛用来满足市场的需要 各式各样的薄膜功能及结构将具有更大的灵活性和 经济性 科学地运用原料 设计合理的产品结构以及与加工工艺的紧密配合 则是摆在每一个薄膜生产商面前永无止境的挑战性课题 只有当加工设备 加 工原料 结构设计 加工艺 三者的技术资源得到充分利用 并达到最佳状态 时 才能使包装基材在其最终产品上以最经济 最合理 最充分 最廉价的形 式出现 并满足市场的需求 1 2 问题相关信息 直接从薄膜厂制膜车间生产出来的的薄膜 在薄膜行业称为半成品 简称 大卷或母卷 宽度一般为 8100mm 厚度有若干种规格 如 19 微米 21 微米等 长度则根据厚度不同而有所不同 薄膜厂销售部门首先接到客户订单或直接 提货单 客户订单或提货单中有所需要的薄膜类型 如 BOPP 膜 消光膜 CPP 膜 珠光膜等 薄膜厚度 如 19 微米 21 微米等 薄膜宽度 如 330mm 620mm 等 件数 其次销售部门根据当前市场行情同客户商谈价格 谈好价格后 客户会发过来一个清单 然后销售部会根据情况把相同薄膜类型 相同厚度的需求合在一起 进行组合优化 形成一个切割任务单 最后在切割 车间通过机器将大卷切割成客户需要的规格 切割好后送达客户的薄膜称为小 卷 假设一般小卷的最小宽度为 330mm 某薄膜厂接到如下订货 来自不同客户的订货的汇总 订货单汇总 薄膜类型相同 厚度相同 订单号规格 宽度 单位 mm 件数 1330206 2620456 3820156 4920318 5100053 61250157 71360263 81470139 91800182 10225094 1 3 需要解决的问题 问题一 请你为该厂设计一个满意的切割方案送交切割车间 该切割方案 须指出切割大卷的总卷数 切割的方式数 材料的利用率等数据 问题二 若该厂的薄膜切割机每天最多只能处理 24 大卷的切割任务 3 7 9 号订单属于加急订单 必须在一周内完成切割 然后发货 问该怎样调整切割 方案 在这种方案下完成整个切割任务单需要多少天 二 问题分析 2 1 问题一的分析 最优的切割方案应该是材料利用率最高并且是最方便的方案 材料的利用 率体现在两个方面 一 余料的宽度之和最小 二 所有余料中宽度最大的余 料最大 即让余料尽可能集中 供再生产利用 方案最方便体现在切割的方式 数最少 所以优化的目标一共有三个 通过对实际情况的调查 生产时往往最 先考虑的是材料的利用率 然后才是考虑余料的大小和切割的方式数 所以本 文将利用率作为第一优化目标 余料的大小和切割的方式数作为次优化目标 得出的切割方案为一个集合 车间可以根据实际情况选择合适的切割方案进行 生产 由于本问题的大卷宽度 d0与小卷宽度 di的比值较大 一个大卷的切割方式 数 m 很大 这类问题属于 NP 完全问题 在多项式时间内没有最优解 只能用 近似解法求解 为得出较优的结果 本文采用两种算法求解 从中找出较好的 算法 首先用整数规划的近似解法 找到材料利用率高的切割方式作为选择 对需求量设置松弛变量 用整数规划的方法求解 然后 贪心算法是在每一当 前状态下找到切割的局部最优解 即在每一当前状态下尽量多的使用材料利用 率最高的切割方式 直到把所有的小卷切割完 2 2 问题二的分析 问题二的优化目标与问题一相同 问题二在问题一的基础上加了一个时间 限制 通过对问题一的结果分析可以确定整数规划是较好的解法 包含 3 7 9 号订单的大卷的数目不能超过七天切割机所能加工的大卷总数 生产时则优先 生产 3 7 9 号订单 根据问题一的求解思想对问题二进行求解 找出最优的切 割方案 三 数据的分析 在工业上 下料问题包括材料的切割问题 排样问题和装箱问题 把条形 的原材料加工成若干不同长度就属于材料的切割问题 如型材 棒材的下料 建筑业中钢筋 铝合金的下料 家具制造业中板材的下料 把形状为矩形大小 不一的材料排放在一个卷材平面上就属于排样问题 如印刷业中各种书刊 报 纸的排版 微电子工业中集成电路的排布 而把体积不同的立方体装在一个体 积确定的箱子里就属于装箱问题 如物流业中的集装箱装货 即如何将货物优 化的装入有限空间的集装箱中则属于装箱问题 本文中需要根据情况把相同薄 膜类型 相同厚度的需求合在一起 进行组合优化 形成一个切割任务单 最 后在切割车间通过机器将大卷切割成客户需要的规格 也就是小卷 很明显 属于材料的切割问题 就材料的切割问题而言 根据原材料和配料维数的数目 又可以把下料问 题进一步分为一维下料问题 二维下料问题 三维下料问题等 一维下料问题 指的是型材 棒材的下料 二维下料问题则主要指板材的下料 三维下料问题 是指原材料和所下皮料的长 宽 高均有特定要求的情况 本文所讨论的属于 一维下料问题 一维下料问题的原则是原材料的余料最少或是原材料的总长最 短 同时切割方式也尽可能少 单个大卷全部用来切割不同规格的小卷时对应的情况如下表3 1 表3 1 订单号小卷个数剩余材料 124180 21340 39720 48740 58100 66600 751300 85750 94900 1031350 从表中我们可以得到单个大卷全部用来切割一个小卷对应的最大个数和大卷余 料 因而在实际切割时 在不同的下料方式中 单次切割时小卷的范围都已经 限定 四 模型的假设和符号说明 4 1 模型的假设 1 假设一般小卷的最小宽度为 330mm 2 假设该厂的薄膜切割机每天最多只能处理 24 大卷的切割任务 3 假设薄膜切割不会产生切割损耗 4 假设切割机都正常工作 4 2 符号的说明 Fi第 i 种可行的切割方案 i 1 2 S Fi 第 i 种可行的切割方案的余料宽度总和 i 1 2 bm Fi 第 i 种可行切割方案的所有余料中宽度最大值 i 1 2 N Fi 第 i 种可行的切割方案的切割方式数 i 1 2 bj第 j 种切割方式的余料宽度 j 1 2 m di第 i 种规格小卷的宽度 i 1 2 n d0大卷薄膜的宽度 aij第 j 种切割方式产生的第 i 种规格小卷的数量 i 1 2 n j 1 2 m m一个大卷的切割方式数 n小卷的规格数量 xj第 j 种切割方式的应用次数 j 1 2 m si第 i 种规格小卷的需求量 i 1 2 n A第 j 种切割方式产生的第 i 种规格小卷的数量构成的 n 行 m 列矩 阵 X第 j 种切割方式的应用次数构成的 m 行 1 列矩阵 D第 i 种规格小卷的需求量构成的 n 行 1 列矩阵 T加急订单的期限 C0一天内切割大卷数的最大值 CJ包含加急订单的大卷数总和 CS实际使用的大卷数 w0实际的利用率 0订单数松弛量的最大值 i第 i 种规格小卷的订单数松弛量 m0利用率最高的前 m0种切割方式 B第 i 种规格小卷的订单数松弛量构成的 n 行 1 列矩阵 五 问题一的解答 针对问题一本文建立了模型一 5 1 模型一的建立 5 1 1 确定目标函数 最优的切割方案应该是材料利用率最高并且是最方便的方案 材料的利用 率体现在两个方面 一 余料的宽度之和最小 二 所有余料中宽度最大的余 料最大 即让余料尽可能集中 供再生产利用 方案最方便体现在切割的方式 数最少 所以模型一的目标函数一共有三个 min max min i mi i S F bF N F 5 1 2 确定约束条件 1 每一个大卷的切割方式中 产生小卷的宽度总和不能超过该大卷的宽度 01 2 j bjm 其中 0 1 1 2 n jiji i bda djm 2 切割的每一种小卷总数与订单数量相等 AXD 其中 切割方式系数矩阵 11121 21222 12 m ijn mm nnnm aaa Aaaaa aaa 切割方式的应用次数矩阵 123 1 2 T mj Xx x xxxN jm 各种规格小卷需求量矩阵 123 T n Ds s ss 5 1 3 相关量的计算 1 余料的宽度值和 1 m ijj j S Fb x 2 所有余料中宽度最大的余料 max 1 2 mij bFbjm 3 切割的方式数 其中 1 m ij j N Fg x 1 0 0 0 x g x x 5 1 4 综上所述得到问题一的多目标优化模型 1 1 min max max 1 2 min m ijj j mij m ij j S Fb x bFbjm N Fg x 123 123 0 1 01 2 1 2 1 2 j T mj T n n jiji i bjm AXD stXx x xxxN jm Ds s ss bda djm 5 2 问题一模型的求解 由于本问题的大卷宽度 d0与小卷宽度 di的比值较大 一个大卷的切割方式 数 m 很大 这类问题属于 NP 完全问题 在多项式时间内没有最优解 所以本 文考虑使用多种近似方法求解 通过比较 从中找出最优的求解方法 通过对实际情况的调查 生产时往往最先考虑的是材料的利用率 然后才 是考虑余料的大小和切割的方式数 所以本文将利用率作为第一优化目标 余 料的大小和切割的方式数作为次优化目标 得出的切割方案为一个集合 车间 可以根据实际情况选择合适的切割方案进行生产 5 2 1 整数规划的近似解法 本问题的大卷宽度 d0与小卷宽度 di的比值较大 一个大卷的切割方式数 m 很大 但是要保证材料有较高的利用率 所选择的切割方式必定是在单个大卷 利用率较高的切割方式中选择的 基于这一思想 本文设计出该问题的近似算 法 算法流程 1 找出单个大卷利用率最高的前 m0种切割方式 作为可选择的切割方式 2 切割方案生产的每一种规格的小卷数量与对应的小卷订单数之间有一 个松弛量 0 0 1 2 ii N in 松弛变量构成的矩阵 12 T n B 3 将模型一的约束条件改为如下约束条件 订单数加了松弛变量 0 01 2 0 1 2 j ii bjm stAXBD N in 4 在上述约束条件下 用整数规划的方法进行求解 由于切割方式数 m0较 小 可以在较短的时间内求得最优解 若无解则增大松弛变量 5 改变 m0的值及松弛变量 0的值 按 4 的求解方法 得出切割方案最优解 Fi的集合 6 在这些解当中找到切割方式数 N 最少 最大宽度的余料宽度 bm最大的解 组成解的集合 车间根据实际情况选择合适的方案 算法流程图 编程求解 考虑到小卷规格的最小宽度为 330mm 而大卷若产生 5 的余料 则宽度 为 8100 0 05 405mm 所以可以初步判定实际使用的切割方式的材料利用率几 乎全在 95 以上 所以 本文通过编程 程序见附录一 查找材料利用率在 95 以 上的所有切割方式 一共有 9974 种 作为为整数规划可供选择的切割方式数 通过编程求解 程序见附录二 得出最优的切割方案 如表 5 1 表 5 1 整数规划近似解法的最优切割方案表 5 2 2 贪心算法求解 考虑到本问题的数据量庞大 难以找到最优解 本文考虑另外一种求解方 法 通过不断的在当前状态下求局部最优解 最后得出问题的近似最优解 算法流程 1 在当前需求的小卷规格种类的条件下 初始状态是所有需求规格 通过 规划求解得出材料利用率最高的一种切割方式 2 在当前的各规格小卷的需求量 总需求与当前总产量之差 条件下 尽 量多的采用 1 中得出的利用率最高的切割方式生产 直到在不超过当前需求量 条件下 不能再切割为止 切割次数为 ni a s i i 2 1min 第 i 种规格小卷的当前需求量 当前最优切割方式产生的第 i 种 i s i a 规格小卷的数量 3 更新需求的小卷规格种类及需求量 4 转第 1 步执行 直到所有规格的小卷的当前需求量为零结束 算法流程图 规格12345678910余料宽大卷数 订单2064561563185315726313918294bjCsj 方式10000000022042 方式20000012011801 方式300000402001601 方式400003010201401 方式500022030001801 方式60012004000035 方式70012020200016 方式80013010110037 方式9010310010109 方式1005010111001059 方式110632000000801 方式122130301000011 方式132400001020029 方式14300023100003 方式157121011000015 方式1612420000000201 利用率99 94 切割的大卷总卷数262 切割方式16 余料最大宽180 编程求解 本文用 lingo 软件求解当前状态下的最优切割方式 用 matlab 软件求解该 切割方式的应用次数 并更新状态 两个程序交替运行 程序见附录三 得出 总的切割方案 切割方案如表 5 2 表 5 2 贪心算法求解的最优切割方案表 规格12345678910余料宽大卷数 订单2064561563185315726313918294bjCsj 方式121200000000038 方式21402200000009 方式3200710000002 方式40050400000012 方式5000512000003 方式60011041000037 方式70012004000041 方式8000501000103 方式90000000022045 方式1000040003001034 方式110001002300501 方式120000001301801 方式1300000003209010 方式1400000021203101 方式15000000302042019 方式1600000000409008 利用率99 26 切割的大卷总卷数264 切割方式16 余料最大宽度900 5 3 问题一结果的分析 本文用两种算法对问题一进行求解 贪心算法是不断的在当前状态下找到 局部最优解 最终得出问题的近似解 结果的好坏与具体问题有很大关系 且 对切割方式数和最大宽度余料无法进行具体优化 但是其算法简单 能够很快 得出较优的解 整数规划近似解法是在对订单数设置松弛变量 只列出最优的 一些切割方式作为选择的切割方式 可以得出该问题的相当好的解 对于本问 题可以得出最优解 两种解法的优劣比较如下表 5 3 表 5 3 两种算法的比较表 解法实际使用大卷数材料利用率切割方式余料最大宽度 整数规划法26299 94 16180 贪心算法26499 26 16900 从表中比较可以明显看出整数规划法的结果明显好于贪婪算法 这也为问 题二的解法提供了依据 六 问题二的解答 针对问题二本文建立了模型二 6 1 模型二的建立 6 1 1 确定目标函数 问题二是在假设该厂的薄膜切割机每天最多只能处理 24 大卷的切割任务的 情况下 在一周内完成切割 3 7 9 号订单 求最优切割方案 最优的切割方案应该是材料利用率最高并且是最方便的方案 材料的利用 率体现在两个方面 一 余料的宽度之和最小 二 所有余料中宽度最大的余 料最大 即让余料尽可能集中 可供下次再生产利用 方案最方便体现在切割 的方式数最少 所以模型二有如下目标函数 min max min i mi i S F bF N F 6 1 2 确定约束条件 1 每一个大卷的切割方式中 小卷的宽度总和不能超过大卷的宽度 01 2 j bjm 其中 0 1 1 2 n jiji i bda djm 2 切割的每一种小卷总数与订单数量相等 AXD 其中 切割方式系数矩阵 11121 21222 12 m ijn mm nnnm aaa Aaaaa aaa 切割方式的应用次数矩阵 123 1 2 T mj Xx x xxxN jm 各种规格小卷需求量矩阵 123 T n Ds s ss 3 加急订单必须在规定的期限内完成 0J CTC 其中 其中 13 7 9 m Jijj ji Cgax 1 0 0 0 x g x x 6 1 3 相关量的计算 1 余料的宽度值和 1 m ijj j S Fb x 2 所有余料中宽度最大的余料 max 1 2 mij bFbjm 3 切割的方式数 1 m ij j N Fg x 6 1 4 综上所述得到问题二的多目标优化模型 1 1 min max max 1 2 min m ijj j mij m ij j S Fb x bFbjm N Fg x 0 13 7 9 123 123 0 1 01 2 1 2 1 2 j J m Jijj ji T mj T n n jiji i bjm CTC AXD stCgax Xx x xxxN jm Ds s ss bda djm 6 2 问题二模型的求解 由于本问题的大卷宽度 d0与小卷宽度 di的比值较大 一个大卷的切割方式 数 m 很大 这类问题属于 NP 完全问题 在多项式时间内没有最优解 考虑到 问题一中用整数规划的近似解法得出的结果相当好 而问题二只是在问题一的 基础上多了一个时间限制 所以问题二采用整数规划的近似解法求解 三个目 标的优化顺序与问题一相同 算法流程 1 找出单个大卷利用率最高的前 m0种切割方式 作为可选择的切割方式 2 切割方案生产的每一种规格的小卷数量与对应的小卷订单数之间有一 个松弛量 0 0 1 2 ii N in 松弛变量构成的矩阵 12 T n B 3 将模型一的约束条件改为如下约束条件 订单数加了松弛变量 0 01 2 0 1 2 j ii bjm stAXBD N in 4 在上述约束条件下 用整数规划的方法进行求解 由于切割方式数 m0较 小 可以在较短的时间内求得最优解 若无解则增大松弛变量 5 改变 m0的值及松弛变量 0的值 按 4 的求解方法 得出切割方案最优解 Fi的集合 6 在这些解当中找到切割方式数 N 最少 最大宽度的余料宽度 bm最大的解 组成解的集合 车间根据实际情况选择合适的方案 算法流程图见问题一的整数规划法算法流程图 编程求解 考虑到小卷规格的最小宽度为 330mm 而大卷若产生 5 的余料 则宽度 为 8100 0 05 405mm 所以可以初步判定实际使用的切割方式的材料利用率几 乎全在 95 以上 所以 本文通过编程 程序见附录一 查找材料利用率在 95 以 上的所有切割方式 一共有 9974 种 作为为整数规划可供选择的切割方式数 通过编程求解 程序见附录四 得出最优的切割方案 如表 6 1 表 6 1 见附录 五 6 3 问题二的结果分析 利用率 99 94 切割的大卷总卷数 262 切割方式 41 余料最大宽 50 完 成任务需要 11 天 完成加急订单需要 7 天 按表所示的顺序进行切割 该结果的材料利用率很高 切割的方式数为 41 在可接受的范围之内 八 模型的评价和改进 8 1 模型的优点 1 大量运用图表对答案进行表示 直观 对比性强 2 运用图论只是求解 便于理解 编程简单 易于解题 3 考虑方面较细 考虑到多种可能 能够应付各种情况 8 2 模型的缺点 对于切割方式数和余料最大宽度难以进行具体优化 8 3 模型的改进 人们对下料问题进行了大量的理论研究 取得一些成果 但是由于下料问 题是一个 NP 问题且应用复杂 一直没有标准的方法来解决下料问题 本文所 建立的模型由于对如何下料事先缺乏周密考虑 所以也很难大幅度降低余料 材料利用率也不高 我们因此要从各方面进行改进并利用算法尽量是的材料的 利用率达到最佳状态 从多个角度对下料算法进行研究 在应用领域方面 对下料问题的研究是 在合理时间内寻早最优解法 在算法分析方面 对下料问题的研究是分析算法 的复杂度 空间的复杂性 对算法性能表现方面 在一般情况下和最坏情况下 对下料问题的质量以及适用的问题类型进行研究 针对不同的问题特点测试和 分析算法的性能 多目标 多约束条件 不仅仅限于材料利用率最高这一主要目标 结合具 体工艺和应用要求考虑多种约束条件 算法也不仅局限于一种方法 可以综合 多种单一下料算法 在对应的阶段选择与之对应的最合适的算法 从而求得最 优解 最终获得满意的求解结果 九 参考文献 1 刘蓉 一维下料方法的一种启发式算法及其运用 D 合肥工业大学 2006 5 2 雷功炎 数学建模讲义 北京 北京大学出版社 2009 6 十 附录 附录一 寻找利用率在 95 以上的切割方式的 matlab 程序 找出最优的切割方式 clear clc b0 330 620 820 920 1000 1250 1360 1470 1800 2250 宽度 y0 load qiongjujieguo txt 切割方式的数量 y1 load qiongju txt a b size y0 m 1 for i 1 a if y0 i 0 FS m 1 y1 i FS m 2 y0 i m m 1 end end sy zeros 1 10 计算剩余量 a1 b1 size FS for i 1 a1 temp 0 t FS i 1 for j 1 10 temp temp t j b0 j end sy i 8100 temp end for j 1 a1 fprintf 第 d 中切割方式为 j FS j 1 fprintf 消耗大卷数 FS j 2 fprintf 余料为 sy j fprintf n end 附录二 整数规划的 lingo 程序 model sets dajuan 1 9974 num 找出 95 以上的组合 xinghao 1 10 d m limit links dajuan xinghao x endsets data d 330 620 820 920 1000 1250 1360 1470 1800 2250 m 206 456 156 318 53 157 263 139 182 94 需求数量 limit 24 13 9 8 8 6 5 5 4 3 单个切割时的上限 x file qiongju txt text qiongjujieguo txt num enddata min sum dajuan i num i for xinghao j sum dajuan i x i j num i m j for dajuan i num i 60 for dajuan i gin num i end 附录三 若要运行程序 请先运行 lingo 程序 再运行 matlab 程序 这样交替运行 得出所有切割方式 贪心算法 lingo 程序 model sets xinghao 1 10 d x p endsets data d 330 620 820 920 1000 1250 1360 1470 1800 2250 p file data1 txt 范围限制 text data txt x 下料方式 enddata min 8100 x 1 d 1 x 2 d 2 x 3 d 3 2 x 4 d 4 x 5 d 5 x 6 d 6 x 7 d 7 2 x 8 d 8 x 9 d 9 2 x 10 d 10 x 1 d 1 x 2 d 2 x 3 d 3 x 4 d 4 x 5 d 5 x 6 d 6 x 7 d 7 x 8 d 8 x 9 d 9 x 10 d 10 8100 x 1 p 1 x 2 p 2 x 3 p 3 x 4 p 4 x 5 p 5 x 6 p 6 x 7 p 7 x 8 p 8 x 9 p 9 x 10 q i 1 确定最小的切割次数 n q i 1 end end end disp 切割次数 n x1 n x1 for i 1 L0 q i 2 shuliang i x1 i 找出切割后剩余的产品需求 end q t q 2 save shuliang txt t ascii 附录四 第二问穷举法 lingo 程序 model sets dajuan 1 9974 num 找出 95 以上的组合 xinghao 1 10 d m limit links dajuan xinghao x