材料最佳切割问题的算法解决方案
导言
最佳切割问题是一个经典的操作研究问题，当需要将标准尺寸的材料分离成指定参数的空白时就会出现。 目标是以最少的原材料消耗满足生产计划。
本文研究了该问题的数学公式以及基于线性和整数规划组合的算法解决方案。
此示例演示如何使用线性规划和整数线性规划例程求解切割问题。
我们将连接必要的库。
# import Pkg
# Pkg.add(["LinearAlgebra", "JuMP", "GLPK", "MathOptInterface", "HiGHS"])
using LinearAlgebra, JuMP, GLPK, MathOptInterface, HiGHS
const MOI = MathOptInterface
任务说明
该公司以标准长度的管道形式接收坯料。 让我们定义这个长度。
引导长度=40
然后将这些管道切割成适合进一步使用的标准尺寸的坯料。 优化任务是确定一个切割方案，该方案将允许您使用最少数量的源管道来完成一组给定的订单。
有必要为每种尺寸指定所需的钢坯尺寸和订单量。
list_长度= [8, 12, 16, 20]
所需数量= [90, 111, 55, 30]
类型数=长度（长度列表）
假设在切割过程中没有材料损失，并且没有考虑切割操作的成本。
解算法
切割模式被定义为一组钢坯长度，当它被切割时，可以从一个单一的管道获得。
.png)
而不是完全搜索可接受的切割模式，使用迭代列生成过程。 该算法实现了两级优化方案:
-
主要任务（线性松弛）：最大限度地减少原始空白的数量，同时满足当前模式组合的需求。
-
辅助任务（列生成）：搜索通过主任务的双变量计算的具有负现值的新模板。 否定性准则提供了目标函数的改进。
迭代过程继续进行，直到改进模式被用尽，这对应于单纯形方法中的最优性条件。 所得线性松弛溶液作为下界。
最后阶段：为了获得整数解，问题在生成的一组模板上反复求解，并要求整数个变量。 这种方法将线性规划的效率与整数方法的精度相结合。
设置任务
在这个问题陈述中，样本是一个整数的向量，其中的元素表示长度列表中每个标准尺寸的空白数。 要存储模板，将使用名称组织矩阵 образцы，其中每列对应一个图案。
第一个模板（第一列）对应于两个长度为8的空白和一个长度为20的空白。 第二模板为两个长度为12的坯料和一个长度为16的坯料。 这两个模板都是可以接受的，因为每个模板中所有空白的总长度不超过 длина_заготовки = 40.
在这个公式中，如果 x —这是一个整数的列向量，指示每个样本使用多少次，然后是产品 给出一个列向量，其中包含每种类型的空白总数。 需求满足条件写成 образцы*x >= требуемое_количество.
为了形成初始的可接受切割模式集，使用最简单的选项，仅包含一个标准尺寸的空白。 每个这样的样本包括给定大小的最大可能数量的空白。
样本=对角线（地板。（Int，准备的长度。/list_line))
number_images=大小（样本，2）
子问题的目标是最小化仅依赖于拉格朗日乘数的函数。 变量是非负整数（每种类型的空白数）。 唯一的限制是模板中坯料的总长度不得超过原始坯料（管道）的长度。
子任务=模型（GLPK。优化器）
@variable(子任务,sections[1:number of types]>=0,Int)
@constraint（子任务，点（长度列表，部分）<=准备的长度）
初始化循环的变量。
降低成本=-Inf
降低成本的公差=-0.0001
退出status_=MOI。最佳
让我们开始循环。
而降低成本<公差降低成本&&退出状态==MOI。最佳
main_problem=模型（）。优化器）
set_silent（main_problem）
@variable(main_problem,x[1:样本数]>=0)
@objective(main_problem,Min,sum(x))
@constraint(main_problem,Demand,samples*x.>=所需数量)
优化！（main_problem）
退出status_status=termination_status（main_stask）
订单数=round(objective_value(main_problem),digits=2)
如果退出status_==MOI。最佳
println("被使用 ", количество_заготовок, " 空白")
对偶变量=对偶。(main_problem[:需求])
@objective（子任务，分钟，1.0点（双变量，节））
set_silent（子任务）
优化！(子任务)
减少值=objective_value（子任务）
子任务status_=termination_status（子任务）
new_image=圆形。（Int，值。(部分))
如果任务status_==MOI。最佳&&降低成本<降低成本的公差
样本=[new_image样本]
number_images=number_images+1
end
else
break
end
end
在这个阶段，已经获得了线性规划问题的解决方案。 要完成计算，有必要使用最终的一组模板再次解决问题，更改解决方案变量的类型。 到整数。 还需要计算废物量-每个样品和整个任务的未使用材料量。
如果退出状态_！=莫伊。最佳
println("列生成阶段的错误")
else
整数任务=模型（）。优化器）
set_silent（integer_problem）
@variable（整数问题，x_integer[1：number_images]>=0，Int）
@objective（整数问题，Min，sum（x_整数））
@constraint(integer task,Demand,samples*x_integer.>=所需数量)
优化！（集成）
status_integer=termination_status（整数任务）
如果status_integer==MOI。最佳
value_x=值。(x_整数)
used_references=sum(values of_x)
println("\最优解使用 ", использовано_заготовок, " 空白")
总废物=总和（样本*x值为所需数量）。*list_长度)
对于j in1：长度（x的值）
如果_x[j]的值>0
println("[医]普拉斯克罗特 ", значения_x[j], " 根据样品空白 ", j)
对于w in1：尺寸（样本，1）
如果样本[w,j]>0
println(" ", образцы[w, j], " 长度详情 ", список_длин[w])
end
end
样本废物=样本长度-点(样本[:,j],长度列表)
一般废物+=样本废物
println(" 这个样品的浪费: ", отходы_образца)
end
end
println("一般废物: ", общие_отходы, ".")
else
println("最终优化中的错误")
end
end
println("\结果表:")
println("长度不需要生产")
println("------\t---------\t-----------")
生产=圆形。(Int,样本*value_x)
对于i in1：长度（list_length）
println(список_длин[i], "\t", требуемое_количество[i], "\t\t", произведено[i])
end
结论
此示例显示了用于求解最优切割问题的完整算法循环。 演示了使用线性松弛来查找改进模式和随后的整数规划以获得最终计划的迭代方法的有效性。
由此产生的解决方案允许您确定所需材料的最小量并分析生产废料的结构。 所提出的方法对优化各行业的工艺流程具有实用价值。