Обзор задачи

Мельница пиломатериалов начинается с деревьев, которые были обрезаны до журналов фиксированной длины. Задайте фиксированную длину журнала.

logLength = 40;

Затем мельница разрезает журналы на фиксированные длины, подходящие для дальнейшей обработки. Проблема заключается в том, как сделать вырезы так, чтобы мельница удовлетворяла набору порядков с наименьшим количеством журналов.

Задайте эти фиксированные длины и количества порядка для длин.

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

Предположим, что нет потерь материала при выполнении разрезов и нет затрат на разрезание.

Формулировка линейного программирования

Несколько авторов, включая Форда и Фулкерсона [1] и Гилмора и Гомори [2], предлагают следующую процедуру, которую вы реализуете в следующем разделе. Шаблон резания представляет собой набор длин, на которые можно нарезать один журнал.

Вместо того, чтобы генерировать каждый возможный рисунок резания, более эффективно генерировать шаблоны резания как решение подпрограммы. Начиная с базового набора шаблонов резания, решите задачу линейного программирования минимизации количества журналов при условии ограничения, что вырезы, используя существующие шаблоны, удовлетворяют требованиям.

После решения этой задачи сгенерируйте новый шаблон путем решения целочисленной подпрограммы линейного программирования. Подпрограмма состоит в том, чтобы найти лучший новый шаблон, означающий количество вырезов от каждой длины в lengthlist которые складываются не более, чем общая возможная длина logLength. Количество для оптимизации является сниженной стоимостью нового шаблона, что на один минус сумма множителей Лагранжа для текущего решения умножает на новый шаблон резания. Если эта величина отрицательная, то включение этого шаблона в линейную программу улучшит его цель. Если нет, то лучшего шаблона резания не существует, и используемые до сих пор шаблоны дают оптимальное решение линейного программирования. Причина такого вывода в точности параллельна причине, когда остановить основной метод симплекса: метод заканчивается, когда нет переменной с отрицательной сниженной стоимостью. Задача в этом примере прекращается, когда нет шаблона с отрицательной сниженной стоимостью. Для получения дополнительной информации и примера смотрите Алгоритмы генерации столбцов и их ссылки.

После решения задачи линейного программирования таким образом, можно иметь нецелочисленные решения. Поэтому решите задачу еще раз, используя сгенерированные шаблоны и ограничивая переменные целые числа значениями.

MATLAB Формулировка, основанная на проблеме

Шаблон, в этой формулировке, является вектором целых чисел, содержащих количество разрезов каждой длины в lengthlist. Расположите матрицу с именем patterns для хранения шаблонов, где каждый столбец в матрице дает шаблон. Для примера,

Первый шаблон ( столбец) представляет собой два разреза длины 8 и один разрез длины 20. Второй шаблон представляет собой два разреза длины 12 и один разрез длины 16. Каждый из них является допустимым шаблоном, поскольку общая сумма разрезов составляет не более logLength = 40.

В этой формулировке, если x - вектор-столбец из целых чисел, содержащий количество раз, когда используется каждый шаблон, затем patterns*x является вектор-столбец, в которой указывается количество разрезов каждого типа. Ограничение удовлетворения потребности в patterns*x >= quantity. Для примера использование предыдущих patterns матрица, предположим, что $\mathit{x}=\left[\begin{array}{c}45\\ 56\end{array}\right]$. (Этот x использует 101 журнал.) Тогда

который представляет собой возможное решение, поскольку результат превышает спрос

Чтобы иметь начальный допустимый шаблон резания, используйте простейшие шаблоны, которые имеют всего одну длину реза. Используйте столько вырезов этой длины, сколько возможно для журнала.

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

Чтобы сгенерировать новые шаблоны из существующих таковых на основе текущих множителей Лагранжа, решите подпрограмму. Вызовите подпрограмму в цикле, чтобы сгенерировать шаблоны, пока не будет найдено дальнейшее улучшение. Цель подпроблемы зависит только от текущих множителей Лагранжа. Переменные являются неотрицательными целыми числами, представляющими количество разрезов каждой длины. Единственным ограничением является то, что сумма длин вырезов в шаблоне не превышает длину журнала.

subproblem = optimproblem();
cuts = optimvar('cuts', nLengths, 1, 'Type','integer','LowerBound',zeros(nLengths,1));
subproblem.Constraints = dot(lengthlist,cuts) <= logLength;

Чтобы избежать ненужной обратной связи от решателей, установите Display опция для 'off' как для внешнего контура, так и для решения внутренней подпрограммы.

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

Инициализируйте переменные для цикла.

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

Вызовите цикл.

while reducedCost < reducedCostTolerance && exitflag > 0
    logprob = optimproblem('Description','Cut Logs');     
    % Create variables representing the number of each pattern used
    x = optimvar('x', nPatterns, 1, 'LowerBound', 0);
    % The objective is the number of logs used
    logprob.Objective.logsUsed = sum(x);
    % The constraint is that the cuts satisfy the demand
    logprob.Constraints.Demand = patterns*x >= quantity;
    
    [values,nLogs,exitflag,~,lambda] = solve(logprob,'options',lpopts);
    
    if exitflag > 0
        fprintf('Using %g logs\n',nLogs);
        % Now generate a new pattern, if possible
        subproblem.Objective = 1.0 - dot(lambda.Constraints.Demand,cuts);
        [values,reducedCost,pexitflag] = solve(subproblem,'options',ipopts);
        newpattern = round(values.cuts);
        if double(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

Теперь у вас есть решение задачи линейного программирования. Чтобы завершить решение, решите задачу снова с помощью конечных шаблонов, меняя переменную решения x на целый тип. Кроме того, вычислите отходы, которые являются количеством неиспользованных журналов (в футах) для каждого шаблона и для задачи в целом.

if exitflag <= 0 
    disp('Error in column generation phase')
else
    x.Type = 'integer';
    [values,logsUsed,exitflag] = solve(logprob,'options',ipopts);
    if double(exitflag) > 0
        values.x = round(values.x); % in case some values were not exactly integers
        logsUsed = sum(values.x);
        fprintf('Optimal solution uses %g logs\n', logsUsed);
        totalwaste = sum((patterns*values.x - quantity).*lengthlist); % waste due to overproduction
        for j = 1:size(values.x)
            if values.x(j) > 0
                fprintf('Cut %g logs with pattern\n',values.x(j));
                for w = 1:size(patterns,1)
                    if patterns(w,j) > 0
                        fprintf('    %g 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 15 logs with pattern

    2 cut(s) of length 20

    Waste of this pattern is 0

Cut 18 logs with pattern

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

    Waste of this pattern is 0

Cut 37 logs with pattern

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

    Waste of this pattern is 0

Cut 19 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.

Часть отходов происходит из-за перепроизводства, потому что мельница разрезает один журнал на три 12-футовых куска, но использует только один. Часть отходов происходит из-за неэффективности шаблона, поскольку три 12-футовых куска на 4 фута меньше общей длины 40 футов.

Ссылки

[1] Ford, L. R., Jr. and D. R. Fulkerson. Предлагаемые расчеты для максимальных потоков многомерных сетей. Наука менеджмента 5, 1958, с. 97-101.

[2] Гилмор, П. К. и Р. Е. Гомори. Подход к линейному программированию проблемы резания запаса - часть II. Исследования операций 11, № 6, 1963, стр. 863-888.