下料问题:基于问题的

这个例子展示了如何解决一个问题下料问题用线性规划与整数线性规划的子程序。示例使用具体问题具体分析的优化设置方法。有关基于解算器的方法，请参见基于求解器的下料问题．

问题概述

伐木场开始时，树木被修剪成固定长度的原木。指定固定的日志长度。

对数长度=40；

然后轧机将原木切割成适合进一步加工的固定长度。问题是如何进行切割，使工厂用最少的原木满足一组订单。

指定这些固定长度和长度的订购数量。

长度列表=[8；12；16；20]；数量=[90；111；55；30]；NLENGHTS=长度（长度列表）；

假设在进行切割时没有材料损失，也没有切割成本。

线性规划公式

一些作者，包括Ford和Fulkerson[1]以及Gilmore和Gomory[2]，建议在下一节中实现以下过程。切割模式是一组可以切割一根原木的长度。

代替生成每一个可能的切割模式，生成切割模式作为子问题的解决方案更有效。从一组基本的切割模式开始，在现有模式的切割满足需求的约束下，解决使使用的原木数量最小化的线性规划问题。

求解该问题后，通过求解一个整数线性规划子问题生成一个新的模式。子问题是找到最佳的新模式，即从每个长度切入的切数lengthlist这些加起来不超过可能的总长度对数长度。要优化的数量是新模式的降低成本，即1减去当前解决方案的拉格朗日乘数乘以新切割模式的总和。如果该数量为负，则将该模式引入线性规划将改善其目标。如果不是，则不存在更好的切割模式，且该模式到目前为止使用的s给出了最优线性规划解。得出此结论的原因与停止原始单纯形法的原因完全平行：当没有负降低成本的变量时，该方法终止。本例中的问题在没有负降低成本的模式时终止。有关详细信息，请参阅s和一个示例，请参见列生成算法及其参考资料。

用这种方法解线性规划问题后，你可以得到非整数解。金宝搏官方网站因此，再次解决这个问题，使用生成的模式并约束变量为整数值。

基于MATLAB问题的公式

在这个公式中，模式是一个整数向量，其中包含每个长度的切割数lengthlist．排列一个名为模式以存储模式，其中矩阵中的每一列给出一个模式。例如,

$模式 = [\begin{matrix} 2. & 0 \\ 0 & 2. \\ 0 & 1. \\ 1. & 0 \end{matrix}] ．$

第一个模式(列)表示长度为8的两段和长度为20的一段。第二个图案代表了长度为12的两段和长度为16的一段。每一个都是可行的模式，因为削减的总数不超过对数长度= 40。

在这个公式中，如果x是包含每个模式使用次数的整数列向量，然后图案*x是一个列向量，给出每种类型的切割数。满足需求的约束为图案*x>=数量．例如，使用前面的模式矩阵,假设 $x = [\begin{matrix} 45 \\ 56 \end{matrix}]$ . （本x使用101个日志。）然后

$模式 * x = [\begin{matrix} 90 \\ 112 \\ 56 \\ 45 \end{matrix}],$

这是一个可行的解决方案，因为结果超出了需求

$数量 = [\begin{matrix} 90 \\ 111 \\ 55 \\ 30 \end{matrix}] ．$

要获得初始可行的切割模式，请使用最简单的模式，该模式只有一个切割长度。对原木使用尽可能多的该长度的切割。

模式=diag（地板（对数长度/长度列表））；nPatterns=大小（模式，2）；

要根据现有的拉格朗日乘数生成新的模式，需要求解一个子问题。在循环中调用子问题以生成模式，直到没有发现进一步的改进。子问题的目标只取决于当前的拉格朗日乘数。变量是非负整数，表示每个长度的切数。唯一的限制是图案中各切线的长度之和不超过对数长度。

子问题= optimproblem ();削减= optimvar (“切”，n长度，1，“类型”,“整数”,“LowerBound”0 (nLengths 1));子问题。Constraints = dot(lengthlist,cuts) <= logLength;

为了避免来自求解器的不必要反馈，设置展示选项“关闭”对于外部循环和内部子问题解决方案。

lpopts = optimoptions (“linprog”,“显示”,“关闭”）;ipopts = optimoptions (“intlinprog”, lpopts);

初始化循环的变量。

reducedCost =无穷;reducedCostTolerance = -0.0001;exitflag = 1;

所谓的循环。

而降低成本0 logprob=optimproblem(“说明”,“伐木”）;%创建代表所使用的每种模式数量的变量x=optimvar(“x”，n模式，1，“LowerBound”, 0);%目标是已使用的日志数量logprob.Objective.logsUsed=总和（x）；%限制条件是削减满足需求logprob.Constraints.Demand=模式*x>=数量；[值，nLogs，exitflag，~，lambda]=solve（logprob，“选项”, lpopts);如果exitflag>0 fprintf('正在使用%g日志\n'（非直瞄发射系统）；%现在生成一个新的模式，如果可能的话子问题。Objective = 1.0 - dot(lambda.Constraints.Demand,cuts);(价值观、reducedCost pexitflag) =解决(子问题,“选项”, ipopts);newpattern =圆(values.cuts);如果double(pexitflag) > 0 && reducedCost < reducedCostTolerance patterns = [pattern newpattern]; / /最小化成本nPatterns = nPatterns + 1;结束结束结束

使用97.5日志使用92日志使用89.9167日志使用88.3日志

现在，您有了线性规划问题的解决方案。要完成解决方案，请使用最终模式再次解决问题，更改解决方案变量x另外，计算浪费，即每个模式和整个问题的未使用日志的数量（英尺）。

如果exitflag<=0显示(“列生成阶段出错”)其他的x、 类型=“整数”；(价值观、logsUsed exitflag) =解决(logprob,“选项”, ipopts);如果Double (exitflag) > 0值。x =圆(values.x);%，以防某些值不是精确的整数logsUsed =总和(values.x);fprintf('最佳解决方案使用%g log \n', logsUsed);totalwaste =((模式*值之和。x -数量)。* lengthlist);生产过剩造成浪费对于j = 1:大小(values.x)如果> 0 fprintf(使用模式\n'切割%g日志x（j））；对于w=1：尺寸（图案，1）如果图案（w，j）>0 fprintf(“%g长度为%d的切口\n”、模式(w, j), lengthlist (w));结束结束wastej=对数长度-点（图案（：，j），长度列表）；%由于模式效率低下造成的浪费总废物=总废物+废物j；fprintf('此模式的浪费为%g\n'，j）；结束结束fprintf('此问题中的总浪费量为%g。\n', totalwaste);其他的disp (“最终优化中的错误”)结束结束

最优方案使用89条日志

切15根有图案的原木

2个长度为20的切口

此模式的浪费为0

切18根有图案的原木

1段8段2段16段

此模式的浪费为0

切割37根有花纹的原木

2个长度为8的切口2个长度为12的切口

此模式的浪费为0

切19根有图案的原木

2个长度为12的切口1个长度为16的切口

此模式的浪费为0

这个问题的总浪费是28。

部分浪费是由于生产过剩，因为工厂将一根原木切割成三根12英尺长的木块，但只使用一根。部分浪费是由于图案效率低下，因为三根12英尺长的木块比40英尺的总长度少4英尺。

参考文献

福特，Jr. R.， Jr. Fulkerson。最大多商品网络流的建议计算。管理科学5,1958，第97-101页。

[2] 吉尔摩，P.C.和R.E.戈莫里。下料问题的线性规划方法——第二部分。运筹学研究11，第6期，1963年，第863-888页。

下料问题:基于问题的

问题概述

线性规划公式

基于MATLAB问题的公式

参考文献

相关的话题

优化工具箱的文档

金宝app

8 MATLAB数据科学备忘单