削减库存问题:具体问题具体分析
这个例子展示了如何解决削减库存的问题使用线性规划和整数线性规划子例程。这个例子使用了具体问题具体分析的优化设置的方法。solver-based方法,请参阅削减库存问题:Solver-Based。
问题概述
一个木材厂始于树已经削减到固定长度的记录。指定日志长度固定。
logLength = 40;
机然后削减登录固定长度适合进一步处理。问题是如何让削减,使磨机满足一组订单最少的日志。
指定这些固定长度和长度的订单数量。
lengthlist = [8;12;16;20);数量= (90;111;55;30);nLengths =长度(lengthlist);
假设没有物质损失进行削减,削减成本。
线性规划公式
几个作者,包括福特和Fulkerson[1]和吉尔摩Gomory[2],显示下列程序,实现在接下来的部分。切割模式是一组,一个日志可以被削减。
而不是生成所有可能的切割模式,更有效的生成切割模式作为子问题的解决方案。从一组基础的切割模式,解决线性规划问题的减少使用的日志数量削减受到约束,使用现有的模式,满足要求。
解决这个问题后,生成一个新的模式通过求解整数线性规划子问题。子问题是找到最好的新模式,意味着削减的数量从每个长度lengthlist,加起来可能不超过总长度logLength。量优化是降低成本的新模式,这是一个负的和拉格朗日乘数法对当前解决方案*新模式。如果这个数量是负数,然后将这种模式引入线性规划将提高其目标。如果不是,然后更好的切割模式不存在,到目前为止使用的模式给最优线性规划解决方案。这个结论的原因是完全平行的原因当停止原始单纯形法:该方法终止当没有变量-降低成本。这个问题在这个例子中终止当没有模式-降低成本。和一个示例的详细信息,请参见列生成算法和它的引用。
在这种方式解决线性规划问题之后,你可以有noninteger解决方案。金宝搏官方网站因此,解决这一问题,使用生成的模式和约束变量整数值。
MATLAB具体问题具体分析公式
一个模式,在这个配方,是一个整数向量包含每个长度的削减的数量lengthlist。安排一个矩阵命名模式存储模式,每个列的矩阵给出了模式。例如,
第一个模式(列)表示两个削减长度8和一个切长度20。第二种模式代表了两个削减长度12和一个切长度16。每个是一个可行的模式,因为减税总额不超过logLength= 40。
在这个公式中,如果x是一个列向量的整数包含每个模式的次数,然后呢* x模式是一个列向量的数量给每个类型的削减。会议需求的约束模式* x > =数量。例如,使用前面的模式矩阵,假设
。(这x使用101日志)。然后
代表一个可行的解决方案,因为结果超过需求吗
有一个初始可行的切割模式,使用最简单的模式,它只有一个切割的长度。使用尽可能多的削减长度可行的日志。
模式=诊断接头(地板(logLength. / lengthlist));nPatterns =大小(模式2);
产生新模式从现有的基于当前的拉格朗日乘数法,解决部分问题。在一个循环中调用子问题来生成模式,直到没有进一步改善。子问题的目标只取决于当前的拉格朗日乘数法。变量非负整数表示的数量削减的长度。唯一的限制是,削减的长度之和不超过日志模式长度。
子问题= optimproblem ();削减= optimvar (“削减”nLengths 1“类型”,“整数”,下界的0 (nLengths 1));子问题。约束=点(lengthlist削减)< = logLength;
为了避免不必要的反馈解决,设置显示选项“关闭”外循环和内子问题的解决方案。
lpopts = optimoptions (“linprog”,“显示”,“关闭”);ipopts = optimoptions (“intlinprog”,lpopts);
初始化变量的循环。
reducedCost =无穷;reducedCostTolerance = -0.0001;exitflag = 1;
所谓的循环。
而reducedCost < reducedCostTolerance & & exitflag > 0 logprob = optimproblem (“描述”,“减少日志”);%创建变量代表的数量每个模式使用x = optimvar (“x”nPatterns 1下界的,0);%的目标是使用的日志数量logprob.Objective。logsUsed = (x)之和;%的约束条件是满足需求logprob.Constraints。需求=模式* x > =数量;(价值观、nLogs exitflag ~,λ)=解决(logprob,“选项”,lpopts);如果exitflag > 0流(“使用% g日志\ n”,nLogs);%现在生成一个新的模式,如果可能的话子问题。目标= 1.0点(lambda.Constraints.Demand削减);(价值观、reducedCost pexitflag) =解决(子问题,“选项”,ipopts);newpattern =圆(values.cuts);如果双(pexitflag) > 0 & & reducedCost < reducedCostTolerance模式= (newpattern模式);nPatterns = nPatterns + 1;结束结束结束
使用97.5日志使用92日志使用89.9167日志使用88.3日志
你现在有线性规划问题的解决方案。完成解决方案,解决这个问题的最终模式,改变变量的解决方案x整数类型。同时,计算浪费,这是未使用的日志(英尺)的数量为每个模式和问题作为一个整体。
如果exitflag < = 0 disp (的错误在列生成阶段)其他的x。类型=“整数”;(价值观、logsUsed exitflag) =解决(logprob,“选项”,ipopts);如果双(exitflag) > 0值。x =圆(values.x);%,以防一些值不是整数logsUsed =总和(values.x);流(“最佳解决方案使用% g日志\ n”,logsUsed);totalwaste =((模式*值之和。x -数量)。* lengthlist);由于生产过剩%浪费为j = 1:大小(values.x)如果values.x (j) > 0流(“减少% \ n g日志模式”values.x (j));为w = 1:尺寸(模式1)如果模式(w, j) > 0流(' % g削减长度(s) % d \ n '、模式(w, j), lengthlist (w));结束结束wastej = logLength -点(模式(:,j), lengthlist);%浪费由于模式效率低下totalwaste = totalwaste + wastej;流(这种模式的“浪费是% g \ n ',wastej);结束结束流(总浪费在这个问题上是% g。\ n”,totalwaste);其他的disp (“最终优化错误”)结束结束
最优解使用89日志
减少15日志模式
2减少20 (s)的长度
这种模式的浪费是0
减少18日志模式
1切的长度8 2把(s) 16
这种模式的浪费是0
削减37日志模式
2减少长度(s) 8 2减少长度(s) 12
这种模式的浪费是0
减少19日志模式
2减少(s)的长度12 1切长度(s) 16
这种模式的浪费是0
浪费在这个问题上是28。
浪费是由于生产过剩的一部分,因为工厂削减一登录三12英尺,但只使用一个。浪费是由于模式低效的一部分,因为这三个12英尺4英尺短片段的40英尺的总长度。
引用
[1]福特,l·R。,Jr. and D. R. Fulkerson.建议计算最大多种商品网络流。管理科学,1958年,页97 - 101。
[2]吉尔摩,p . C。,and R. E. Gomory.线性规划方法削减股票问题——第二部分。6号运筹学11日,1963年,页863 - 888。
