库存削减问题:基于求解器

打开实时脚本

这个例子展示了如何解决一个库存削减问题利用线性规划与整数线性规划子程序。该示例使用基于求解器的优化问题设置的方法。有关基于问题的方法，请参见库存削减问题:基于问题的．

问题概述

木材厂首先将树木修剪成固定长度的圆木。指定固定的日志长度。

logLength = 40;

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

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

Lengthlist = [8;12;16;20);数量= [90;111;55;30);nlength_length = length(长度列表);

假设在切割过程中没有物质损失，也没有切割成本。

线性规划公式

包括Ford和Fulkerson[1]和Gilmore和Gomory[2]在内的几位作者建议使用以下过程，您将在下一节中实现该过程。切割图案是一组长度，单个原木可以切割到的长度。

与其生成每一种可能的切割模式，不如将切割模式作为子问题的解来生成更有效。从一组基本的切割模式开始，在现有模式的切割满足需求的约束下，求解最小化使用的日志数的线性规划问题。

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

用这种方法求解线性规划问题后，就可以得到非整数解。因此，再一次解决这个问题，使用生成的模式并将变量约束为整数值。

基于MATLAB求解的公式

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

$模式＝［ \begin{matrix} 2 & 0 \\ 0 & 2 \\ 0 & 1 \\ 1 & 0 \end{matrix} ］．$

第一个图案(列)表示两个长度为8的切口和一个长度为20的切口。第二个图案表示两个长度为12的切口和一个长度为16的切口。每一个都是可行的模式，因为削减的总数不会超过logLength= 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} ］．$

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

pattern = diag(floor(loglengh ./lengthlist));nPatterns = size(patterns,2);

要从现有的基于当前拉格朗日乘子的模式中生成新的模式，需要解决一个子问题。在循环中调用子问题以生成模式，直到没有发现进一步的改进。子问题的目标只依赖于当前的拉格朗日乘子。变量是非负整数，表示每个长度的切割数。唯一的限制是图案中切割的长度之和不能超过对数长度。创建一个下界向量lb2和矩阵A2而且b2表示这些界限和线性约束。

lb2 = 0 (nlength,1);A2 = lengthlist';b2 = logLength;

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

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

初始化循环的变量。

reducedCost = -Inf;reducedCostTolerance = -0.0001;Exitflag = 1;

调用循环。

而reducedCost < reducedCostTolerance && exitflag > 0 lb = 0 (nPatterns,1);F = lb + 1;A = -patterns;B = -quantity;(价值观、nLogs exitflag ~,λ)= linprog (f, A, b,[],[],磅,[],lpopts);如果退出> 0 fprintf('使用%g logs\n', nLogs);如果可能的话，现在生成一个新的模式F2 = -lambda.ineqlin;[values,reducedCost,pexitflag] = intlinprog(f2,1: nlength,A2,b2，[]，[]，lb2，[]，ipopts);reducedCost = 1 + reducedCost;%继续，如果此reducedCost为负Newpattern = round(值);如果pexitflag > 0 && reducedCost < reducedCost tolerance patterns = [patterns newpattern];nPatterns = nPatterns + 1;结束结束结束

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

现在你有了线性规划问题的解。要完成解决方案，请使用最终的模式再次解决问题intlinprog所有变量都是整数。此外，计算浪费，这是每个模式和整个问题的未使用日志的数量(单位为英尺)。

如果Exitflag <= 0“列生成阶段错误”）其他的(价值观、logsUsed exitflag) = intlinprog (f, 1:长度(磅),A, b,[],[],磅,[],[],ipopts);如果Exitflag > 0 values = round(values);logsUsed = round(logsUsed);流('最佳解决方案使用%g logs\n', logsUsed);Totalwaste = sum((模式*值-数量).*lengthlist);由于生产过剩造成的浪费为J = 1:大小(值)如果值(j) > 0 fprintf用模式\n切割%g条日志值(j));为W = 1:大小(图案，1)如果pattern (w,j) > 0 fprintf(长度为%d\n的cut(s)、模式(w, j), lengthlist (w));结束结束wastej = logLength - dot(patterns(:，j)，lengthlist);%由于模式效率低下造成的浪费总废物=总废物+废物j;流('浪费这个模式是%g\n', wastej);结束结束流(“这个问题的总浪费是%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。

创建一个表，显示长度，每个长度所需的数量，以及每个长度生产的数量。

表(lengthlist、数量、模式*值,“VariableNames”, (“长度”“所需数量”“数量”])

ans =4×3表长度数量需要生产的数量  ______ _______________ _______________ 8 90 92 12 111 112 16 55 55 20 30 30

该解决方案额外生产了两个长度为8的零件和一个长度为12的零件，总共生产了28英尺。

参考文献

小福特、l.r.和d.r.富尔克森。多商品网络最大流量的建议计算。《管理科学》第5期，1958年，第97-101页。

吉尔摩，P. C.和R. E.戈莫里。切削库存问题的线性规划方法——第二部分。《运筹学》第11期，第6期，1963年，第863-888页。

库存削减问题:基于求解器

问题概述

线性规划公式

基于MATLAB求解的公式

参考文献

相关的话题