В нескольких ранее рассмотренных примерах, сценарий решает серию связанных экземпляров модели, включая оператор solve внутри цикла. Результатом является простой алгоритм анализа чувствительности, запрограммированный на командном языке AMPL. Гораздо более мощные алгоритмические процедуры могут быть построены с использованием двух моделей и реализацией переключения между моделями. Оптимальное решение первой модели предоставляет данные для второй, и обе решаются поочередно таким образом, что в конечном итоге должно быть достигнуто некоторое условие завершения.
Классические методы генерации столбцов и разрезов, разложения и Лагранжевой релаксации основаны на схемах такого рода, которые подробно описаны в ссылках, приведенных в конце этой главы. Чтобы использовать две модели таким образом, скрипт должен иметь способ переключения между ними. Переключение может быть выполнено с помощью ранее определенных функций AMPL или более четко и эффективно путем определения отдельных именованных проблем и сред. Мы проиллюстрируем эти возможности с помощью сценария для основной формы задачи «обрезки рулона» или «резки», используя хорошо известную процедуру генерации элементарных столбцов. В целях краткости мы предоставим только схематическое описание процедуры, а ссылки в конце этой главы предоставят источники для подробного описания. На веб-сайте AMPL есть несколько других примеров схем генерации, декомпозиции и релаксации, и мы также будем использовать некоторые выдержки из них позже, не показывая полных моделей.
В задаче обрезки рулонов мы хотим разрезать длинные рулоны бумаги, на несколько меньших кусков, ширина которых соответствует заказам. Всю эту процедуру нам необходимо выполнить с минимальным количеством отходов. Эту проблему можно рассматривать в разрезе каждого рулона, для которого должны быть сделаны разрезы, чтобы получить необходимое количество рулонов меньшей ширины. Чтобы получить более управляемую модель, так называемая процедура Гилмора-Гомори определяет схему раскроя как любой возможный способ разрезания первоначального рулона. Таким образом, шаблон состоит из определенного количества рулонов каждой желаемой ширины, так что их общая ширина не превышает ширину исходного рулона. Если ширина рулона-донора равна 110'', и есть требования получить рулоны шириной 20'', 45'', 50'', 55'' и 75'', тогда шаблон, состоящий из двух рулонов 45'' и одного 20'' делает разрез рулона-донора - безотходным. Шаблон из рулона в 50'' и рулона в 55'' дает отходы 5''. Учитывая этот подход, можно составить две простые линейные программы:
# модель минимизации количества нарезаемых рулонов
param roll_width > 0; # ширина первоначальных рулонов
set WIDTHS; # набор длинн нарезаемых рулонов
param orders {WIDTHS} > 0; # количество кусочков каждой ширины
param nPAT integer >= 0; # количество шаблонов
set PATTERNS = 1..nPAT; # набор шаблонов
param nbr {WIDTHS,PATTERNS} integer >= 0; # объявление шаблонов
# Проверка: для каждого шаблона ширина его частей не должна превышать ширину рулона нарезки
check {j in PATTERNS}: sum {i in WIDTHS} i * nbr[i,j] <= roll_width;
var Cut {PATTERNS} integer >= 0; # количество рулонов нарезаных по каждому из шаблонов
minimize Number: sum {j in PATTERNS} Cut[j]; # минимизировать количество обрезаемых рулонов
subject to
Fill {i in WIDTHS}: sum {j in PATTERNS} nbr[i,j] * Cut[j] >= orders[i];
# для каждой ширины: количество нарезанных рулонов >= общее количество заказанных рулонов
# Модель генерации шаблона
param price {WIDTHS} default 0.0; # Стоимость резки
var Use {WIDTHS} integer >= 0; # Количество кусков каждой ширины в шаблоне
# Минимизировать стоимость нарезки шаблона
minimize Reduced_Cost: 1 - sum {i in WIDTHS} price[i] * Use[i];
subject to
# Ширина нарезанных из шаблона кусочков <= ширина рулона
Width_Limit: sum {i in WIDTHS} i * Use[i] <= roll_width;
которые могут работать вместе, чтобы найти эффективный план резки.
Модель оптимизации раскроя находит минимальное количество разрезаемых рулонов, которые необходимо нарезать, с учетом набора известных схем раскроя. (На самом деле эта модель - близкий родственник модели диеты: переменные, представляющие нарезанные образцы, а не купленные продукты питания, и ограничения, устанавливающие более низкий предел ширины нарезки, а не количество питательных веществ.)
Модель генерации шаблона стремится идентифицировать новый шаблон, который можно использовать при оптимизации раскроя, либо для уменьшения количества необходимых разрезаемых рулонов, либо для определения того, что такого нового шаблона не существует. Переменными этой модели являются количество каждой желаемой ширины в новом шаблоне. Ограничение гарантирует, что общая ширина шаблона не превышает ширину рулона. Отметим, что коэффициент переменной задается ее соответствующим «двойным значением» или «двойной ценой» из линейной релаксации модели оптимизации резки.
Мы можем искать хороший план резки, решая эти две проблемы поочередно. Сначала непрерывная переменная релаксация задачи оптимизации раскроя генерирует несколько двойных цен, затем задача генерации шаблона использует цены для генерации нового шаблона, а затем процедура повторяется со следующим набором шаблонов, увеличенным на единицу. Мы останавливаем итерации, когда проблема генерации шаблона указывает на то, что новый шаблон не может привести к улучшению. Тогда у нас будет наилучшее возможное решение с точки зрения (возможно) дробного числа нарезанных рулонов-доноров. Мы можем сделать последний прогон модели оптимизации раскроя с восстановленным ограничением целостности, чтобы получить наилучшее интегральное решение, используя сгенерированные шаблоны, или мы можем просто округлить дробные числа рулонов до следующих больших целых чисел, если это дает приемлемый результат. Это процедура Гилмора-Гомори. С точки зрения наших двух моделей AMPL, его шаги могут быть описаны следующим образом:
выбрать начальную схему резки, достаточную для удовлетворения спроса
repeat
решить проблему оптимизации дробной резки
let price[i] = Fill[i].dual для каждого шаблона i
решить проблему генерации схемы резки
если оптимальное значение <0, тогда
добавить новый шаблон резки, который режет Use[i] рулоны каждой ширины i
else
найти окончательное целочисленное решение и остановить
Простой способ инициализации - создать один шаблон для каждой ширины, содержащий столько копий этой ширины, сколько уместится в необработанном рулоне. Эти модели, безусловно, могут покрывать любые требования, но их решение не обязательно будет экономичным.
Реализация процедуры Гилмора-Гомори как сценария AMPL показана на рисунке ниже.
model cut.mod; # загрузка модели
data cut.dat; # загрузка данных
option solver cplex, solution_round 6; # округление решения до 6 значащих цифр
option display_1col 0, display_transpose -10; # скрыть столбцы со всеми 0 значениями
problem Cutting_Opt: Cut, Number, Fill; # Объявление именованной проблемы Cutting_Opt
option relax_integrality 1; # вкдючение режима игнорирования цнлочисленности переменных
problem Pattern_Gen: Use, Reduced_Cost, Width_Limit; # Объявление именованной проблемы Pattern_Gen
option relax_integrality 0; # откдючение режима игнорирования цнлочисленности переменных
let nPAT := 0; # количество шаблонов
for {i in WIDTHS} { # для каждой ширины кусков
let nPAT := nPAT + 1; # количество шаблонов + 1
let nbr[i,nPAT] := floor (roll_width/i); # шаблон = ширина рулона / количество кусков заданной ширины
let {i2 in WIDTHS: i2 <> i} nbr[i2,nPAT] := 0; # значения шаблонов с другой шириной кусков = 0
}
repeat {
solve Cutting_Opt; # Решить проблему Cutting_Opt
let {i in WIDTHS} price[i] := Fill[i].dual; # присвоить price[i] значения двойной цены Fill[i].dual
solve Pattern_Gen; # Решить проблему Pattern_Gen
if Reduced_Cost < -0.00001 then{# если значение Reduced_Cost < 0.00001 тогда
let nPAT := nPAT + 1; # количество шаблонов + 1
let {i in WIDTHS} nbr[i,nPAT] := Use[i]; # значение шаблона nbr[i,nPAT] = Use[i]
}
else break; # в противном случае остановить
}
display nbr, Cut;
option Cutting_Opt.relax_integrality 0;
solve Cutting_Opt;
display Cut;
Файл cut.mod содержит как модели оптимизации раскроя, так и модели генерации шаблонов. Поскольку эти модели не имеют общих переменных или ограничений, можно написать сценарий с простыми инструкциями решения, используя чередующиеся целевые функции:
repeat {
objective Number;
solve;
...
objective Reduced_Cost;
solve;
... }
Однако, при таком подходе, каждое решение отправляет решателю все переменные и ограничения, сгенерированные обеими моделями. Такие действия неэффективны и подвержены ошибкам, особенно для более крупных и сложных итерационных процедур.
Вместо этого мы могли бы гарантировать, что решателю будут отправляться только нужные переменные и ограничения. С использованием команд fix и drop для подавления ненужных переменных и ограничений, цикл будет выглядеть следующим образом:
repeat {
unfix Cut; restore Fill; objective Number;
fix Use; drop Width_Limit;
solve;
...
unfix Use; restore Width_Limit; objective Reduced_Cost;
fix Cut; drop Fill;
solve;
... }
Перед каждым solve должны быть возвращены ранее фиксированные переменные и исключенные ограничения с использованием функции unfix и restore. Этот подход эффективен, но он по-прежнему подвержен ошибкам и затрудняет чтение сценариев.
Поэтому в качестве альтернативы AMPL позволяет различать модели, используя формулировку проблемы, показанную на рисунке выше:
problem Cutting_Opt: Cut, Number, Fill; option relax_integrality 1; problem Pattern_Gen: Use, Reduced_Cost, Width_Limit; option relax_integrality 0;
Первый оператор определяет проблему с именем Cutting_Opt, которая состоит из переменных Cut, ограничений Fill и целевой функции Number. Это утверждение также делает Cutting_Opt текущей проблемой. Использование операторов var, minimize, maximize, subject to, и option теперь применимо только к этой проблеме. Таким образом, например, установив параметр relax_integrality в значение 1, мы гарантируем, что условие целостности переменных Cut будет ослаблено всякий раз, когда проблема Cutting_Opt будет являться текущей. Аналогичным образом мы определяем проблему Pattern_Gen, которая состоит из переменных Use, ограничения Width_Limit и цели Reduced_Cost. Она в свою очередь становится текущей проблемой, и на этот раз мы устанавливаем relax_integrality в "0", потому что для этой задачи имеет смысл только целочисленное решение.
Цикл for на рисунке выше создает начальные шаблоны резки, после чего основной цикл repeat выполняет процедуру Гилмора-Гомори, как описано ранее. Заявление solve Cutting_Opt; восстанавливает Cutting_Opt как текущую проблему вместе с ее окружением и решает связанную линейную программу. Тогда назначение let {i in WIDTHS} price[i]:= Fill[i].dual; переносит оптимальные двойные цены из Cutting_Opt в параметры price[i], которые будут использоваться Pattern_Gen. Все наборы и параметры являются глобальными в AMPL, поэтому на них можно ссылаться или изменять независимо от текущей проблемы.
Вторая половина основного цикла делает проблему Pattern_Gen и ее окружение текущей и отправляет связанную целочисленную программу решателю. Если полученный результат является отрицательным, шаблон, возвращаемый переменными Use[i], добавляется к данным, которые будут использоваться Cutting_Opt при следующем проходе цикла. В противном случае дальнейший прогресс невозможен, и цикл прерывается.
Скрипт завершается следующими утверждениями, чтобы найти лучшее целочисленное решение, используя все сгенерированные шаблоны:
option Cutting_Opt.relax_integrality 0; solve Cutting_Opt;
Выражение Cutting_Opt.relax_integrality обозначает значение параметра relax_integrality в среде Cutting_Opt. Мы обсудим эти виды имен и их использование более подробно в следующем разделе. В качестве примера того, как это работает, на рисунке ниже показаны данные для резки 110-дюймовых необработанных рулонов, чтобы удовлетворить требования 48, 35, 24, 10 и 8 для готовых рулонов шириной 20, 45, 50, 55 и 75 соответственно.
param roll_width := 110 ; param: WIDTHS: orders := 20 48 45 35 50 24 55 10 75 8 ;
commands cut.run; CPLEX 8.0.0: optimal solution; objective 52.1 0 dual simplex iterations (0 in phase I) CPLEX 8.0.0: optimal integer solution; objective -0.2 1 MIP simplex iterations 0 branch-and-bound nodes CPLEX 8.0.0: optimal solution; objective 48.6 2 dual simplex iterations (0 in phase I) CPLEX 8.0.0: optimal integer solution; objective -0.2 2 MIP simplex iterations 0 branch-and-bound nodes CPLEX 8.0.0: optimal solution; objective 47 1 dual simplex iterations (0 in phase I) CPLEX 8.0.0: optimal integer solution; objective -0.1 2 MIP simplex iterations 0 branch-and-bound nodes CPLEX 8.0.0: optimal solution; objective 46.25 2 dual simplex iterations (0 in phase I) CPLEX 8.0.0: optimal integer solution; objective -1e-06 8 MIP simplex iterations 0 branch-and-bound nodes nbr [*,*] : 1 2 3 4 5 6 7 8 := 20 5 0 0 0 0 1 1 3 45 0 2 0 0 0 2 0 0 50 0 0 2 0 0 0 0 1 55 0 0 0 2 0 0 0 0 75 0 0 0 0 1 0 1 0 ; Cut [*] := 1 0 2 0 3 8.25 4 5 5 0 6 17.5 7 8 8 7.5 ; CPLEX 8.0.0: optimal integer solution; objective 47 5 MIP simplex iterations 0 branch-and-bound nodes Cut [*] := 1 0 2 0 3 8 4 5 5 0 6 18 7 8 8 8 ;
которые появляются, когда сценарий выполняется с моделью и данными. Наилучшее дробное решение режет 46.25 рулонов-доноров по пяти различным схемам, используя 48 рулонов, если дробные значения округляются до следующего целого числа. Окончательное решение с использованием целочисленных переменных показывает, как можно применить набор из шести шаблонов для удовлетворения спроса, используя 47 необработанных рулонов.
Ниже представлен альтернативный пример переключения между моделями:
option solver conopt;
param S := 5;
set SCENARIOS := 1..S;
param UB{s in SCENARIOS};
let UB[1] := 20;
let UB[2] := 40;
let UB[3] := 60;
let UB[4] := 80;
let UB[5] := 100;
var x{s in SCENARIOS};
maximize OBJ: sum {s in SCENARIOS} x[s];
maximize OBJ_s{s in SCENARIOS}: x[s];
subject to CON{s in SCENARIOS}: 0 <= x[s] <= UB[s];
problem MASTER:
x,
OBJ,
CON ;
problem SUB{s in SCENARIOS}:
x[s],
OBJ_s[s],
CON[s] ;
print "Test Sub";
for {s in SCENARIOS} {
problem SUB[s];
solve;
display OBJ_s[s];
display CON[s].body;
display{j in 1.._ncons}(_conname[j],_con[j].body, _con[j].lb, _con[j].ub, _con[j].slack) > cons.txt;}
display {j in 1.._snvars} (_svarname[j],_svar[j],_svar[j].lb, _svar[j].ub, _svar[j].slack) > var.txt;
