Проблемный обзор

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

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

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