В этом примере показано, как решить сокращающую задачу запаса с помощью линейного программирования с целочисленной линейной стандартной подпрограммой программирования. Пример использует Основанный на проблеме подход Setup Оптимизации. Для основанного на решателе подхода смотрите Сокращающую проблему Запаса: основанный на решателе.
Фреза пиломатериалов запускается с деревьев, которые были обрезаны к журналам фиксированной длины. Задайте фиксированную продолжительность журнала.
logLength = 40;
Фреза затем сокращает журналы в фиксированные длины, подходящие для последующей обработки. Проблема состоит в том, как сделать сокращения так, чтобы фреза удовлетворила набору порядков с наименьшим количеством журналов.
Задайте эти фиксированные длины и количества порядка для длин.
lengthlist = [8; 12; 16; 20]; quantity = [90; 111; 55; 30]; nLengths = length(lengthlist);
Примите, что нет никакой материальной потери в создании сокращений и никакой стоимости для сокращения.
Несколько авторов, включая Форд и Фалкерсона [1] и Гилмор и Гомори [2], предлагают следующую процедуру, которую вы реализуете в следующем разделе. Сокращающий шаблон является набором длин, к которым может быть сокращен один журнал.
Вместо того, чтобы генерировать каждый возможный сокращающий шаблон, более эффективно сгенерировать сокращающие шаблоны как решение подпроблемы. При запуске с основного набора сокращения шаблонов решите задачу линейного программирования минимизации количества журналов, используемых удовлетворяющий ограничению, что сокращения, с помощью существующих шаблонов, удовлетворяют требованиям.
После решения той задачи сгенерируйте новый шаблон путем решения целочисленной линейной подпроблемы программирования. Подпроблема состоит в том, чтобы найти лучший новый шаблон, означая количество сокращений от каждой длины в lengthlist
это составляет в целом не больше, чем общую возможную длину logLength
. Количество, чтобы оптимизировать является уменьшаемой стоимостью нового шаблона, который является один минус сумма множителей Лагранжа в течение текущих времен решения новый сокращающий шаблон. Если это количество будет отрицательно, то обеспечение того шаблона в линейную программу улучшит свою цель. В противном случае затем никакой лучший сокращающий шаблон не существует, и шаблоны, используемые до сих пор, дают оптимальное линейное решение для программирования. Причина этого заключения точно параллельна причине того, когда остановить основной симплекс-метод: метод завершает работу, когда нет никакой переменной с отрицательной уменьшаемой стоимостью. Проблема в этом примере завершает работу, когда нет никакого шаблона с отрицательной уменьшаемой стоимостью. Для получения дополнительной информации и пример, см. алгоритмы генерации Столбца и ее ссылки.
После решения задачи линейного программирования таким образом, у вас могут быть решения для нецелого числа. Поэтому решите задачу еще раз, с помощью сгенерированных шаблонов и ограничив переменные иметь целочисленные значения.
Шаблон, в этой формулировке, является вектором целых чисел, содержащих количество сокращений каждой длины в lengthlist
. Расположите матрицу под названием patterns
сохранить шаблоны, где каждый столбец в матрице дает шаблон. Например,
Первый шаблон (столбец) представляет два сокращения длины 8 и одно сокращение длины 20. Второй шаблон представляет два сокращения длины 12 и одно сокращение длины 16. Каждый - выполнимый шаблон, потому что общим количеством сокращений является не больше, чем logLength
= 40.
В этой формулировке, если x
вектор-столбец целых чисел, содержащих число раз, каждый шаблон используется, затем patterns*x
вектор-столбец, дающий количество сокращений каждого типа. Ограничением удовлетворения требованию является patterns*x >= quantity
. Например, с помощью предыдущего patterns
матрица, предположите это . (Этот 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.