Документация

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

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

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 1 logs with pattern
    3 cut(s) of length 12
    Waste of this pattern is 4
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 36 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.