下料问题：基于求解器

此示例说明如何使用带有整数线性规划子例程的线性规划来求解下料问题。该示例使用基于求解器的优化问题设置方法。有关基于问题的方法，请参阅下料问题：基于问题。

问题概述

木材厂首先会将树木修剪成固定长度的原木。指定固定原木长度。

logLength = 40;

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

指定这些固定长度以及这些长度木材的订单数量。

lengthlist = [8; 12; 16; 20];
quantity = [90; 111; 55; 30];
nLengths = length(lengthlist);

假设切割时没有材料损失，并且切割也没有成本。

线性规划表示

包括 Ford 和 Fulkerson [1] 以及 Gilmore 和 Gomory [2] 在内的几位作者建议采用以下步骤，您可以在下一节中实施。切割模式是单根原木可以切割成的一组长度。

与生成所有可能的切割模式相比，将切割模式作为子问题的解来生成更加有效。从一组基本切割模式开始，求解线性规划问题，目标是最小化所用原木的数量，但要使用现有模式的切割来满足需求。

求解该问题后，通过求解整数线性规划子问题来生成新模式。子问题是找到最佳的新模式，即从 lengthlist 中每个长度切出的木材，加起来不超过可能的总长度 logLength。要优化的数量是新模式的缩减成本，即一减去当前解的拉格朗日乘数之和乘以新的切割模式。如果这个量是负的，那么将该模式纳入线性规划将会改善其目标。如果不是，那么就不存在更好的切割模式，并且迄今为止使用的模式给出了最优的线性规划解。得出这个结论的原因与何时停止原始单纯形法的原因完全一致：当不存在具有负缩减成本的变量时，该方法终止。当不存在具有负缩减成本的模式时，本例中的问题终止。有关详细信息和示例，请参阅列生成算法及其参考。

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

MATLAB 基于求解器的表示

在这个表示中，模式是一个整数向量，包含 lengthlist 中每个长度的切割数量。使用一个名为 patterns 的矩阵来存储模式，其中矩阵中的每一列都给出一个模式。例如，

$patterns = [\begin{matrix} 2 & 0 \\ 0 & 2 \\ 0 & 1 \\ 1 & 0 \end{matrix}] .$

第一个模式（列）代表两个长度为 8 的切段和一个长度为 20 的切段。第二种模式代表两条长度为 12 的切段和一条长度为 16 的切段。每个都是可行的模式，因为切段总数不超过 logLength = 40。

在这个表示中，如果 x 是一个包含每个模式使用次数的整数列向量，那么 patterns*x 就是一个给出每种类型的切割次数的列向量。满足需求的约束是 patterns*x >= quantity。例如，使用前面的 patterns 矩阵，假设 $x = [\begin{matrix} 45 \\ 56 \end{matrix}]$ 。（这个 x 使用了 101 根原木。）然后，

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

这代表一个可行解，因为结果超出了需求

$quantity = [\begin{matrix} 90 \\ 111 \\ 55 \\ 30 \end{matrix}] .$

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

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

要根据当前拉格朗日乘数从现有模式中生成新模式，请求解子问题。循环调用子问题来生成模式，直到无法找到进一步的改进。子问题的目标仅取决于当前的拉格朗日乘数。变量是非负整数，表示每种长度的切割次数。唯一的约束是，模式中切段的长度总和不能超过原木长度。创建一个下界向量 lb2 以及表示这些边界和线性约束的矩阵 A2 和 b2。

lb2 = zeros(nLengths,1);
A2 = lengthlist';
b2 = logLength;

为了避免求解器产生不必要的反馈，请将外循环和内部子问题解的 Display 选项设置为 'off'。

lpopts = optimoptions("linprog",Display="off");
ipopts = optimoptions("intlinprog",Display="off");

初始化循环的变量。

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

调用循环。

while reducedCost < reducedCostTolerance && exitflag > 0
    lb = zeros(nPatterns,1);
    f = lb + 1;
    A = -patterns;
    b = -quantity;
    
    [values,nLogs,exitflag,~,lambda] = linprog(f,A,b,[],[],lb,[],lpopts); 
    if exitflag > 0
        fprintf('Using %g logs\n',nLogs);
        % Now generate a new pattern, if possible
        f2 = -lambda.ineqlin;
        [values,reducedCost,pexitflag] = intlinprog(f2,1:nLengths,A2,b2,[],[],lb2,[],ipopts);
        reducedCost = 1 + reducedCost; % continue if this reducedCost is negative
        newpattern = round(values);
        if pexitflag > 0 && reducedCost < reducedCostTolerance
            patterns = [patterns newpattern];
            nPatterns = nPatterns + 1;
        end
    end
end

Using 97.5 logs
Using 92 logs
Using 89.9167 logs
Using 88.3 logs

现在您已经得到了线性规划问题的解。为了完成解，请使用最终模式再次求解问题，使用 intlinprog，其中所有变量都是整数。另外，计算浪费，即每个模式和整个问题未使用的原木的量（以英尺为单位）。

if exitflag <= 0 
    disp('Error in column generation phase')
else
    [values,logsUsed,exitflag] = intlinprog(f,1:length(lb),A,b,[],[],lb,[],[],ipopts);
    if exitflag > 0
        values = round(values);
        logsUsed = round(logsUsed);
        fprintf('Optimal solution uses %g logs\n', logsUsed);
        totalwaste = sum((patterns*values - quantity).*lengthlist); % waste due to overproduction
        for j = 1:numel(values)
            if values(j) > 0
                fprintf('Cut %g logs with pattern\n',values(j));
                for w = 1:size(patterns,1)
                    if patterns(w,j) > 0
                        fprintf('    %d cut(s) of length %d\n', patterns(w,j),lengthlist(w));
                    end
                end
                wastej = logLength - dot(patterns(:,j),lengthlist); % waste due to pattern inefficiency
                totalwaste = totalwaste + wastej;
            fprintf('    Waste of this pattern is %g\n', wastej);
            end
        end
        fprintf('Total waste in this problem is %g.\n',totalwaste);
    else 
        disp('Error in final optimization')
    end
end

Optimal solution uses 89 logs

Cut 18 logs with pattern

    5 cut(s) of length 8

    Waste of this pattern is 0

Cut 15 logs with pattern

    2 cut(s) of length 20

    Waste of this pattern is 0

Cut 1 logs with pattern

    2 cut(s) of length 8
    2 cut(s) of length 12

    Waste of this pattern is 0

Cut 55 logs with pattern

    2 cut(s) of length 12
    1 cut(s) of length 16

    Waste of this pattern is 0

Total waste in this problem is 28.

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

table(lengthlist,quantity,patterns*values,'VariableNames',["Length" "Number Required" "Number Produced"])

ans=4×3 table
    Length    Number Required    Number Produced
    ______    _______________    _______________

       8             90                 92      
      12            111                112      
      16             55                 55      
      20             30                 30

该解额外生产了两块长度为 8 的板材和一块长度为 12 的板材，总共超额生产了 28 英尺。

参考资料

[1] Ford, L. R., Jr. and D. R. Fulkerson.A Suggested Computation for Maximal Multi-Commodity Network Flows.Management Science 5, 1958, pp. 97-101.

[2] Gilmore, P. C., and R. E. Gomory.A Linear Programming Approach to the Cutting Stock Problem--Part II. Operations Research 11, No. 6, 1963, pp. 863-888.

另请参阅

主题

下料问题：基于问题