下料问题:基于问题的
这个例子展示了如何解a削减库存的问题使用具有整数线性编程子程序的线性编程。该示例使用基于问题的优化设置的方法。关于基于求解器的方法，请参见切削库存问题:基于求解器．
问题概述
木材轧机从已被修剪到固定长度的树木的树木开始。指定固定日志长度。
logLength = 40;
然后轧机将原木切割成适合进一步加工的固定长度。问题是如何进行切割，使工厂用最少的原木满足一组订单。
指定这些固定长度和长度的订购数量。
lengthlist = [8;12;16;20);数量= (90;111;55;30);nLengths =长度(lengthlist);
假设在切割过程中没有物质损失，也没有切割成本。
线性规划公式
一些作者，包括Ford和Fulkerson[1]以及Gilmore和Gomory[2]，建议在下一节中实现以下过程。切割模式是一组可以切割一根原木的长度。
代替生成每一个可能的切割模式，生成切割模式作为子问题的解决方案更有效。从一组基本的切割模式开始，在现有模式的切割满足需求的约束下，解决使使用的原木数量最小化的线性规划问题。
求解该问题后，通过求解一个整数线性规划子问题生成一个新的模式。子问题是找到最佳的新模式，即从每个长度切入的切数lengthlist这加起来不超过总长度logLength．优化的数量是新图案的成本降低，即1减去当前解决方案的拉格朗日乘数乘以新的切割图案。如果这个量是负的，那么将这个模式带入线性规划将提高它的目标。如果没有，那么就不存在更好的切割模式，并且到目前为止使用的模式给出了最优线性规划的解决方案。这个结论的原因与何时停止原始单纯形方法的原因完全相同:当没有变量时，方法终止，降低成本为负。当没有负降低成本的模式时，此示例中的问题将终止。详细信息和示例请参见列生成算法和它的引用。
用这种方法解线性规划问题后，你可以得到非整数解。万博 尤文图斯因此，再次解决这个问题，使用生成的模式并约束变量为整数值。
MATLAB具体问题具体分析公式
在这个公式中，模式是一个整数向量，其中包含每个长度的切点数lengthlist．排列一个名为模式要存储模式，其中矩阵中的每个列给出图案。例如，
第一个模式(列)表示长度为8的两段和长度为20的一段。第二个图案代表了长度为12的两段和长度为16的一段。每一个都是可行的模式，因为削减的总数不超过logLength= 40。
在这个公式中，如果x一个整数列向量是否包含每个模式使用的次数* x模式是列向量，给出每种类型切割的数量。满足需求的约束条件是模式* x > =数量．例如，使用前一个模式矩阵,假设
．(这x使用101日志)。然后
哪个代表一个可行的解决方案，因为结果超过了需求
要有一个初始可行的切割模式，使用最简单的模式，只有一个长度的切割。使用尽可能多的长度切割原木。
模式=诊断接头(地板(logLength. / lengthlist));nPatterns =大小(模式2);
要根据现有的拉格朗日乘数生成新的模式，需要求解一个子问题。在循环中调用子问题以生成模式，直到没有发现进一步的改进。子问题的目标只取决于当前的拉格朗日乘数。变量是非负整数，表示每个长度的切数。唯一的限制是图案中各切线的长度之和不超过对数长度。
子问题= optimproblem ();削减= optimvar (“削减”nLengths 1“类型”，“整数”，下界的0 (nLengths 1));子问题。Constraints = dot(lengthlist,cuts) <= logLength;
为了避免来自求解器的不必要反馈，设置显示选择“关闭”对于外循环和内子问题的解。
lpopts = optimoptions (“linprog”，“显示”，“关闭”）;ipopts = optimoptions (“intlinprog”, lpopts);
初始化循环的变量。
reducedCost =无穷;reducedCostTolerance = -0.0001;exitflag = 1;
所谓的循环。
而logprob =最优问题(“描述”，“减少日志”）;%创建代表所使用的每种模式数量的变量x = optimvar (“x”nPatterns 1下界的, 0);%目标是已使用的日志数量logprob.Objective.logsUsed = (x)之和;约束条件是削减满足需求logpro . constraints . demand = patterns*x >= quantity;(价值观、nLogs exitflag ~,λ)=解决(logprob,“选项”, lpopts);如果Exitflag > 0 fprintf(“使用% g日志\ n”, nLogs);%现在生成一个新的模式，如果可能的话子问题。Objective = 1.0 - dot(lambda.Constraints.Demand,cuts);(价值观、reducedCost pexitflag) =解决(子问题,“选项”, ipopts);newpattern = round（值.Cuts）;如果double(pexitflag) > 0 && reducedCost < reducedCostTolerance patterns = [pattern newpattern]; / /最小化成本nPatterns = nPatterns + 1;结束结束结束
使用97.5日志使用92日志使用89.9167日志使用88.3日志
现在你有线性规划问题的解了。为了完成这个解决方案，再用最终的模式来解决这个问题，改变解决方案变量x为整数类型。另外，计算浪费，即每个模式和整个问题的未使用日志的数量(英尺)。
如果Exitflag <= 0'列生成阶段出错'）其他的x.Type =“整数”；(价值观、logsUsed exitflag) =解决(logprob,“选项”, ipopts);如果Double (exitflag) > 0值。x =圆(values.x);%，以防某些值不是精确的整数logsUsed =总和(values.x);流('最佳解决方案使用%g log \n', logsUsed);totalwaste =((模式*值之和。x -数量)。* lengthlist);生产过剩造成浪费为j = 1：大小（值.x）如果> 0 fprintf(使用模式\n'切割%g日志values.x (j));为w = 1:尺寸(模式1)如果if (w,j) > 0 fprintf(' %g cut(s) of length %d\n'、模式(w, j), lengthlist (w));结束结束wastj = logLength - dot(patterns(:，j)，lengthlist);%由于模式效率低下造成的浪费总废物=总废物+废物j;流('浪费这个模式是%g\n', wastej);结束结束流(这个问题的总浪费是%g.\n, totalwaste);其他的disp (“最终优化中的错误”）结束结束
最优方案使用89条日志
切15根有图案的原木
长度为20
这种模式的浪费是0
切18根有图案的原木
1段8段2段16段
这种模式的浪费是0
切37根有图案的原木
2段长度为8段长度为12段
这种模式的浪费是0
用图案切割19个日志
2段长度为12段1段长度为16段
这种模式的浪费是0
这个问题的总浪费是28。
部分浪费是由于生产过剩，因为工厂将一根原木切割成3块12英尺的碎片，但只使用了一根。部分浪费是由于模式效率低，因为这3个12英尺的部件比40英尺的总长度少了4英尺。
参考
福特，Jr. R.， Jr. Fulkerson。一种关于最大多商品网络流量的建议计算方法。管理科学5,1958，第97-101页。
p.c. Gilmore和r.e. Gomory。下料问题的线性规划方法——第二部分。运筹学研究11，第6期，1963年，第863-888页。
相关话题
你也可以从以下列表中选择一个网站:
