切割问题【数学规划的应用(含代码)】阿里达摩院MindOpt

简介: 本文主要讲述了使用MindOpt工具对切割问题进行优化的过程与实践。切割问题是指从一维原材料(如木材、钢材等)中切割出特定长度的零件以满足不同需求,同时尽可能减少浪费的成本。文章通过实例详细介绍了如何使用MindOpt云上建模求解平台及其配套的MindOpt APL建模语言来解决此类问题,包括数学建模、代码实现、求解过程及结果分析等内容。此外,还讨论了一维切割问题的应用场景,并对其进行了扩展,探讨了更复杂的二维和三维切割问题。通过本文的学习,读者能够掌握利用MindOpt工具解决实际切割问题的方法和技术。

本文主要讲述使用MindOpt工具优化切割问题

视频讲解👈👈👈👈👈👈👈👈👈

案例场景

image.png

切割问题涉及从一维的原材料如木材、钢材、布匹卷等切割出特定长度的零件以满足不同需求。同时最小化浪费成本。这个问题可以形式化为在满足需求的同时减少原材料的使用量。对于一维切割的思路,可以进行扩展。实际中有很多的应用。

扩展的思路例如钢筋切割将统一长钢筋原材料根据需求切割成不同长度小尺寸,例如切割能最小化原材料数量。

木材加工从长度不一的原材料中切割出多种长度的小段。如何切割能最大化成品总数长度数、提高原材料利用率。

一维切割的应用场景包括但不限于以下几点:制造业中切割问题应用于各种物料和材料的切割例如金属塑料木材等,通过优化切割方案可以提高原材料的利用率,减少成本的浪费。

在建筑业中切割问题应用于各种材料的切割例如钢筋管道石材等,通过优化切割方案可以满足建筑结构的需求,减少材料浪费,提高施工效率。

在木工行业中,切割问题可以应用于各种木材的切割例如板材木块等,通过优化切割方案可以提高木材的利用率,减少浪费,提高生产效率。

在服装、纺织和皮革业中,切割问题用于面料皮革等的切割例如服装鞋子等的剪裁。通过优化切割方案,可以提高面料和皮革的利用率,减少浪费,提高生产效率。

数学规划

image.png

切割问题可以使用数学规划的方法解决。数学规划是一种数学优化方法,主要寻找变量取值在特定的约束情况下,使得我们的决策目标得到一个最大或最小值的决策。常见的数学优化方法有线性规划、混合优化、整数规划和非线性规划。在实际应用中,需要确定问题的目标约束变量的取值范围,对其建立一个数学模型,对数学模型进行求解,得出的结果就是问题的最优决策。在求解时往往将数学模型转换为一个代码,通过代码调用优化求解器工具。优化求解器可以帮助我们计算大规模数据的数学规划问题。

问题描述

image.png

假设有一批长度统一的水管原材料,要切出不同长度。如何安排切割使得使用的原材料数量最少?考虑八点因素:第一是原材料长度,每个原材料长度统一是100单位,第二是需求量,需要不同规格的材料数量。第三是如何将不同长度的小段组合以最大限度的利用原材料,减少浪费。第四是每根原材料切割的结果必须是完整的小段,不能有分数或小数。第五每种切割方案的数量必须大于等于0。第六目标是使用最少的原材料数量来满足所有的需求。第七是切割过程中会有一定的损耗,该问题忽略不计。第八结合以上因素,寻找最少使用原材料的优化方案。

代码解析

image.png

在案例中,我们对这个问题进行数学建模和代码转化,用到MindOpt云上建模求解平台(一个页面版的线上开发环境,可在线的开发调试代码)、以及达摩院研发的建模语言MindOpt APL,与学公式非常贴近。

工具:

声明集合、参数

image.png

首先定义了原材料的长度,也就是标准水管的长度。下面是使用map语法,从CSV文件中读取数据的一个方法,并且将其用作模型的一个参数。第一句表示CSV文件在data目录下。下面定义了一个名为demand 的集合,通过读取下面file d2目录下的demand.CSV文件来获取数据。依然表示读取该文件中的第一列数据。Ln表示数字,gap1表示读取操作跳过第一行。因为第一行通常是表头。最终这个集合demand将包含需求序号的列表123。

下面是读取需求长度。创建了一个名为demand size的参数,以demand集合为索引的映射,数据同样来自CSV文件。通过1n 2n读取第一列作为索引,也就是需求序号,并且读取第二列作为需求长度的值,即54 50 70,所以demand size将包含demand的集合每个序号对应的需求长度。DemandNum读取了需求个数,从demand集合为索引的映射,数据来源与前述相同,但是1n 3n表示使用第三列数据作为个数的值。所以demandNum将包含于demand集合中每个序号对应的需求个数。

image.png

下面是定义原材料的总数,pipe_num=15,创建了一个rawpipe的集合。只包含从1到pipe_num,表示15根原材料编号。

声明变量

image.png

然后来看定义的变量,第一个变量定义了一个变量x_pipeused,表示在满足所有需求后总共被使用的管道数量,也就是FUS。第二个变量定义了一个索引rawpipe的二元变量数组x_cuts,每个元素x_cuts[i]表示编号为i的原材料是否被切割使用。1表示原材料被切割,0表示原材料未被切割。该变量是二进制变量bi。第三个变量定义了一个证书变量数组x_cutnum,索引为rawpipe,原材料水管编号的集合,和demand需求序列集合的笛卡尔积,每个元素x_cutnum[i,j]表示编号为i的原材料水管中编号为j的需求长度被切割出的数量。整数变量意味着这些变量的值必须为非负整数。再来看定义的优化目标。

声明目标

image.png

我们的目标是最小化使用原材料的数量,最小化切割的总次数,最小化定义的第一个变量x_pipeused,最小化总共被使用的管道数量。

声明约束

image.png

第一个约束条件是每个需求j的尺寸需求应该得到满足,对于每个需求的需求量demandnum[j]必须小于或者等于所有原材料管道i中切割出该需求尺寸的数量x_cutnum[ij]的一个总和,这样确保了每个尺寸的需求都至少得到满足。

image.png

下面的需求是每个原材料i的切割方式不能超过其总长度。Demandsize是需求j的尺寸,typelength是原材料管道的长度,x_cutnum[ij]是从原材料管道i切割出满足需求j的数量,对所有需求尺寸的切割长度求和,得到的总长度不应该超过原材料管道长度乘该管道是否被使用的标志x_cuts。如果管道未被使用,x_cuts为0,因此等式右侧为零,满足约束。

image.png

确保变量typeused=实际被切割的原材料数量之和,对于集合rawpipe中的每个原材料管道,如果被切割,x_cuts i等于1就会在x_pipeused中累加计数。然后使用求解指令进行求解。一般遇到规模大的问题,变量取值会比较多,复杂程度高,解出的结果变量的取值可读性不高,所以使用map语法中打印CSV表格的方法,提高角色变量的可读性。这段代码是打印切割方案到一个切割方案CSV的文件中。

将结果打印为表格

image.png

这段代码是命令在切割方案点CSV文件中写入表头,表头包含了材料长度、需求数量以及对应的切割数量。然后使用close命令去关闭CSV文件。将数据写入到表格中。这段代码遍历了所有原材料,也就是rawpipe中的每一项,并且只考虑至少有一次被切割的。由于x_cuts[i]是一个二元变量,所以这里用0.5作为阈值来检测是否为1。对于每一根原材料,将长度以及每个需求的尺寸以及该原材料为每个需求切割出的数量打印到CSV文件中,格式化字符串括号用于插入变量值,百分号操作符用于将变量值传递给格式化字符串。然后使用追加符号表示向切割方案点CSV文件追加内容,而不是覆盖原有内容。最后使用close命令关闭文件。

结果解析

image.png

首先可以看到使用了七个原材料,使用七个水管。对第一根水管进行切割,得到了两个长度为14的水管,以及一个长度为70的水管。对第二根水管进行切割,得到了一个长度为14的水管以及一个长度为70的水管。剩下的变量的取值与上述类似,不详细介绍。

对本期内容进行回顾:

本期讲述切割问题,对水管原材料进行切割,需要最小化水管原材料的使用数量。使用工具是MIndopt云上建模求解平台,网址是opt.aliyun.com。

获取源代码

image.png

切割问题优化:一维长度或容量切割-MindOpt Studio

最后对这个问题进行扩展。

这个问题讲述的是一维切割,通常还有更为复杂的二维和三维切割,对应需要考虑的因素会指数升级,对应的解决方案可能会不一致。例如一维的控制量只有长度,二维有坐标xy和转角。三维对应xyz和roll、pitch、yaw三种选择角度。切割形状不能重叠表达。

相关文章
|
达摩院 供应链 安全
光储荷经济性调度问题【数学规划的应用(含代码)】阿里达摩院MindOpt
本文介绍使用MindOpt工具优化光储荷经济性调度的数学规划问题。光储荷经济性调度技术旨在最大化能源利用率和经济效益,应用场景包括分布式光伏微网、家庭能源管理系统、商业及工业用电、电力市场参与者等。文章详细阐述了如何通过数学规划方法解决虚拟电厂中的不确定性与多目标优化难题,并借助MindOpt云建模平台、MindOpt APL建模语言及MindOpt优化求解器实现问题建模与求解。最终案例展示了如何通过合理充放电策略减少37%的电费支出,实现经济与环保双重效益。读者可通过提供的链接获取完整源代码。
|
达摩院 算法 安全
智慧楼宇多目标调度问题【数学规划的应用(含代码)】阿里达摩院MindOpt
本文探讨了使用MindOpt工具优化智慧楼宇的多目标调度问题,特别是在虚拟电厂场景下的应用。智慧楼宇通过智能化技术综合考虑能耗、舒适度等多目标,实现楼宇设备的有效管理和调度。虚拟电厂作为多能源聚合体,能够参与电力市场,提供调峰、调频等辅助服务。文章介绍了如何使用MindOpt云上建模求解平台及MindOpt APL建模语言对楼宇多目标调度问题进行数学建模和求解,旨在通过优化储能设备的充放电操作来最小化用电成本、碳排放成本和功率变化成本,从而实现经济、环保和电网稳定的综合目标。最终结果显示,在使用储能设备的情况下,相比不使用储能设备的情形,成本节约达到了约48%。
|
达摩院 供应链 JavaScript
网络流问题--仓储物流调度【数学规划的应用(含代码)】阿里达摩院MindOpt
本文通过使用MindOpt工具优化仓储物流调度问题,旨在提高物流效率并降低成本。首先,通过考虑供需匹配、运输时间与距离、车辆容量、仓库储存能力等因素构建案例场景。接着,利用数学规划方法,包括线性规划和网络流问题,来建立模型。在网络流问题中,通过定义节点(资源)和边(资源间的关系),确保流量守恒和容量限制条件下找到最优解。文中还详细介绍了MindOpt Studio云建模平台和MindOpt APL建模语言的应用,并通过实例展示了如何声明集合、参数、变量、目标函数及约束条件,并最终解析了求解结果。通过这些步骤,实现了在满足各仓库需求的同时最小化运输成本的目标。
|
达摩院 安全 调度
网络流问题--交通调度【数学规划的应用(含代码)】阿里达摩院MindOpt
本文探讨了如何利用数学规划工具MindOpt解决交通调度问题。交通调度涉及网络流分析,考虑道路容量、车辆限制、路径选择等因素,以实现高效运行。通过建立数学模型,利用MindOpt云平台和建模语言MAPL,设定流量最大化目标并确保流量守恒,解决实际的调度问题。案例展示了如何分配车辆从起点到终点,同时满足道路容量约束。MindOpt Studio提供在线开发环境,支持模型构建和求解,帮助优化大规模交通调度。
|
达摩院 Linux API
阿里达摩院MindOpt求解器V1.1新增C#接口
阿里达摩院MindOpt求解器发布最新版本V1.1,增加了C#相关API和文档。优化求解器产品是求解优化问题的专业计算软件,可广泛各个行业。阿里达摩院从2019年投入自研MindOpt优化求解器,截止目前经历27个版本的迭代,取得了多项国内和国际第一的成绩。就在上个月,2023年12月,在工信部产业发展促进中心等单位主办的首届能源电子产业创新大赛上,MindOpt获得电力用国产求解器第一名。本文将为C#开发者讲述如何下载安装MindOpt和C#案例源代码。
470 3
阿里达摩院MindOpt求解器V1.1新增C#接口
|
达摩院 Linux 决策智能
阿里达摩院MindOpt优化求解器-月刊(2024年3月)
### MindOpt 优化求解器月刊(2024年3月) - 发布亮点:MAPL建模语言升级至V2.4,支持云上无安装使用和向量化建模语法。 - 新增功能:Linux用户可本地安装`maplpy`,并支持Python与MAPL混编。 - 实例分享:介绍背包问题的组合优化,展示如何在限定容量下最大化收益。 - 用户投稿:探讨机票超售时的最优调派策略,以最小化赔付成本。 - 加入互动:官方钉钉群32451444,更多资源及。 [查看详细内容](https://opt.aliyun.com/)
213 0
阿里达摩院MindOpt优化求解器-月刊(2024年3月)
|
达摩院 开发者 容器
「达摩院MindOpt」优化形状切割问题(MILP)
在制造业,高效地利用材料不仅是节约成本的重要环节,也是可持续发展的关键因素。无论是在金属加工、家具制造还是纺织品生产中,原材料的有效利用都直接影响了整体效率和环境影响。
「达摩院MindOpt」优化形状切割问题(MILP)
|
机器学习/深度学习 达摩院
阿里达摩院MindOpt优化求解器-月刊(2024年4月)
【摘要】2024.04.30,阿里云发布了MindOpt优化求解器的新商品和功能。MindOpt现在已上架,提供超低价零售求解器,支持按需购买,可在阿里云平台上直接购买联网或不联网License。新版本V1.2发布,提升MILP性能,并增加PostScaling参数。此外,MindOpt Studio推出租户定制版,正处于邀测阶段。同时分享了使用MindOpt解决二分类SVM问题的案例。更多内容,可访问相关链接。
393 0
|
达摩院 IDE 开发工具
阿里达摩院MindOpt优化求解器-月刊(2024年5月)
阿里达摩院MindOpt优化求解器-月刊(2024年5月版),新增了两个案例,如何使用LLM和MindOpt更准确地回答数学问题、如何使用MindOpt优化云计算集群虚拟机资源配置提高机器利用率,和如何利用IIS冲突分析指导不可解的问题解决方案。MindOpt的求解器已经可以在阿里云线上购买不联网版本。租户版也正式上线,可体验更多功能。新增QQ交流群。
284 4
人员排班【数学规划的应用(含代码)】阿里达摩院MindOpt
本文介绍了使用阿里巴巴达摩院的MindOpt工具解决人员排班的数学规划问题。人员排班在多个行业中至关重要,如制造业、医疗、餐饮和零售等。问题涉及多种约束,包括工作需求、员工能力、工作时间限制、连续工作天数及公平性。通过MindOpt云建模平台和建模语言MindOpt APL,建立数学模型并编写代码来解决最小化总上班班次的问题。案例中展示了如何声明集合、参数、变量和约束,并给出了部分代码示例。最后,通过MindOpt求解器得到最优解,并将结果输出到CSV文件中。

热门文章

最新文章