库存削减问题:基于问题的

打开实时脚本

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

问题概述

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

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);

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

Subproblem = optimproblem();削减= optimvar(“削减”， n长度，1，“类型”，“整数”，下界的0 (nLengths 1));子问题。约束= dot(lengthlist,cuts) <= logLength;

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

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

初始化循环的变量。

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

调用循环。

而reducedCost < reducedCost tolerance && exitflag > 0 logprob =优化问题(“描述”，“减少日志”);创建变量表示所使用的每个模式的数量X = optimvar(“x”， nPatterns, 1，下界的, 0);目标是使用的日志数量logprov . objective . logsused = sum(x);限制条件是削减能满足需求。logprobo . constraints . demand = patterns*x >= quantity;[values,nLogs,exitflag，~，lambda] = solve(logprob，“选项”, lpopts);如果退出> 0 fprintf('使用%g logs\n', nLogs);如果可能的话，现在生成一个新的模式子问题。目标= 1.0 -点(lambda.约束。需求，削减);[values,reducedCost,pexitflag] = solve(子问题，“选项”, ipopts);Newpattern = round(values.cuts);如果double(pexitflag) > 0 && reducedCost < reducedCost tolerance patterns = [patterns newpattern];nPatterns = nPatterns + 1;结束结束结束

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

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

如果Exitflag <= 0“列生成阶段错误”）其他的x.Type =“整数”；[values,logsUsed,exitflag] = solve(logprob，“选项”, ipopts);如果Double (exitflag) > 0个值。X = round(values.x);%，以防某些值不完全是整数logsUsed = sum(values.x);流('最佳解决方案使用%g logs\n', logsUsed);总浪费= sum((模式*值。X -数量).*长度列表);由于生产过剩造成的浪费为J = 1:size(values.x)如果Values.x (j) > 0 fprintf(用模式\n切割%g条日志values.x (j));为W = 1:大小(图案，1)如果pattern (w,j) > 0 fprintf(长度%d\n的' %g 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。

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

参考文献

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

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

库存削减问题:基于问题的

问题概述

线性规划公式

MATLAB基于问题的公式

参考文献

相关的话题