Обзор проблемы

Лесозавод начинается с деревьев, которые были обрезаны до бревен фиксированной длины. Укажите фиксированную длину журнала.

logLength = 40;

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

Укажите эти фиксированные длины и количества заказов для этих длин.

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

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

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

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

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

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

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

Формулировка на основе решателя MATLAB

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

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

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

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

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

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',lpopts);

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

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:size(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 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] Форд, Л. Р., младший и Д. Р. Фулкерсон. Предлагаемые вычисления для максимальных потоков многоторовых сетей. Наука об управлении 5, 1958, стр. 97-101.

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