В простых моделях производства с максимальной прибылью, произведенные товары отличаются от потребляемых ресурсов, так что общее производство очевидным образом ограничено доступными ресурсами. Однако в более реалистичной модели сложной операции, такой как сталелитейный завод или нефтеперерабатывающий завод, производство осуществляется на нескольких единицах оборудования, в результате некоторые материалы подаваемые на вход одного оборудования могут быть выходными материалами другого оборудования в технологической цепочке.
Для описания этой ситуации нам нужна модель, которая в более общем виде может описывать материалы, которые могут быть входными или выходными продуктами, а также с производственным оборудованием, которое может включать несколько входных и выходных требований.
Мы начинаем с разработки формулировки AMPL обычным построчным (или ограниченным) способом.
Формулировка ограничений по строкам
Определение нашей модели начинается с набора материалов и набора активностей:
set MAT; set ACT;
Ключевыми значениями данных являются коэффициенты ввода-вывода для всех комбинаций материал-деятельность:
param io {MAT,ACT};
Если io[i,j]>0, это интерпретируется как количество материала i, произведенного (как выход) единицей деятельности j. С другой стороны, если io[i,j] <0, это представляет количество материала i, израсходованного (как вход) единицей деятельности j. Например, значение 10 представляет 10 единиц i, произведенных на единицу j, а значение –10 представляет 10 единиц, потребленных на единицу j. Конечно, мы можем ожидать, что для многих комбинаций i и j будет io[i,j]=0, что означает, что материал i вообще не фигурирует в деятельности j. Чтобы понять, почему мы хотим интерпретировать io[i,j] таким образом, предположим, что мы определили Run[j] как уровень, на котором мы работаем (выполняем) активность j:
param act_min {ACT} >= 0;
param act_max {j in ACT} >= act_min[j];
var Run {j in ACT} >= act_min[j], <= act_max[j]; Тогда io[i,j]*Run[j]
это общее количество произведенного материала i (io[i,j]>0) или количество потребленного материала i (io[i,j]<0) по виду деятельности j. Суммируя все активности, мы находим количество материала, которое i произвел в операции, за вычетом потребленного количества. Эти суммы должны быть сбалансированы, что выражается следующим ограничением:
subject to Balance {i in MAT}: sum{j in ACT}io[i,j]*Run[j] = 0;
А как насчет доступности ресурсов или требований к готовой продукции? Они легко моделируются с помощью дополнительных действий, которые представляют собой покупку или продажу материалов. Закупочная деятельность для материала у меня не имеет входных данных, и только i является выходом. Верхний предел Run[i] представляет количество доступного ресурса. Аналогично, операция продажи для материала i не имеет выходных данных, и в качестве входных данных используется только i, а нижний предел для Run[i] представляет количество этого товара, которое должно быть произведено для продажи. Мы завершаем модель, связывая доходы с деятельностью. Торговые операции обязательно приносят положительные доходы, в то время как закупочные и производственные операции приносят отрицательные доходы, то есть затраты. Сумма удельных доходов и уровней активности дает общую чистую прибыль от операции. Итоговая формулировка модели (по строкам) имеет следующий вид:
set MAT; # materials
set ACT; # activities
param io {MAT,ACT}; # input-output coefficients
param revenue {ACT}; param act_min {ACT} >= 0;
param act_max {j in ACT} >= act_min[j];
var Run {j in ACT} >= act_min[j], <= act_max[j];
maximize Net_Profit: sum {j in ACT} revenue[j] * Run[j];
subject to Balance {i in MAT}: sum {j in ACT} io[i,j] * Run[j] = 0;
Файл iorow.mod на сайте AMPL.
Столбчатая формулировка
Как показывает наше обсуждение деятельности по купле-продаже, все в этой модели может быть организовано по видам деятельности: В частности, для каждого действия j у нас есть переменная решения Run[j], стоимость или доход, представленный revenue[j], ограничения act_min[j] и act_max[j], а также набор коэффициентов вход-выход io[i,j]. Такие изменения, как повышение доходности единицы или приобретение нового источника снабжения, учитываются путем добавления операции или путем изменения данных для операции. В формулировке по строкам важность видов деятельности для этой модели несколько скрыта. В то время как act_min[j] и act_max[j] появляются в объявлении переменных, revenue[j] указано в объявлении целевой функции, а значения io[i,j] находятся в объявлении ограничения.
Альтернатива по столбцам объединяет всю эту информацию, добавляя фразы obj и coeff в объявление var:
var Run {j in ACT} >= act_min[j], <= act_max[j],
obj Net_Profit revenue[j],
coeff {i in MAT} Balance[i] io[i,j];
Фраза obj говорит, что в целевой функции Net_Profit переменная Run[j] имеет коэффициент revenue[j]; То есть заменяет фразу revenue[j]*Run[j]. Фраза coeff немного сложнее, потому что она индексируется по набору. В ней говорится, что для каждого материала i в ограничении Balance[i] переменная Run[j] должна иметь коэффициент io[i,j], так что добавляется элемент io[i, j]*Run[j]. Вместе эти фразы описывают все коэффициенты всех переменных в линейной программе. Поскольку мы поместили все коэффициенты в объявление var, мы должны удалить их из других объявлений:
maximize Net_Profit;
subject to Balance {i in MAT}: to_come = 0;
Ключевое слово to_come указывает, где должно быть добавлено выражение io[i,j]*Run[j], сгенерированное объявлением var. to_come = 0 можно представить как шаблон для ограничения, которое будет заполнено когда будут объявлены коэффициенты. Однако для цели в этом примере шаблон не требуется, поскольку он представляет собой исключительно сумму условий revenue[j]*Run[j]. Шаблоны могут быть написаны ограниченным количеством способов. Поскольку фразы obj и coeff ссылаются на Net_Profit и Balance, объявление var должно следовать после maximize и подчиняться объявлениям в формулировке по столбцам. Полная модель:
set MAT; # materials
set ACT; # activities
param io {MAT,ACT}; # input-output coefficients
param revenue {ACT}; param act_min {ACT} >= 0;
param act_max {j in ACT} >= act_min[j];
maximize Net_Profit;
subject to Balance {i in MAT}: to_come = 0;
var Run {j in ACT} >= act_min[j], <= act_max[j], obj Net_Profit revenue[j], coeff {i in MAT} Balance[i] io[i,j];
Столбчатая формулировка (iocol1.mod).
Уточнение столбчатой формулировки
Преимущества столбчатого подхода становятся более очевидными, когда модель становится более сложной. В качестве примера рассмотрим, что произойдет, если мы захотим иметь отдельные переменные для представления продаж готовых материалов. Мы объявляем подмножество материалов, которые можно продать, и используем его для индексации новых коллекций границ, доходов и переменных:
set MATF within MAT; # finished materials
param revenue {MATF} >= 0;
param sell_min {MATF} >= 0;
param sell_max {i in MATF} >= sell_min[i];
var Sell {i in MATF} >= sell_min[i], <= sell_max[i];
Теперь мы можем отказаться от специальных операций по продаже, описанных ранее. Поскольку остальные элементы ACT представляют закупочную или производственную деятельность, мы можем ввести неотрицательную стоимость параметра, связанную с ними:
param cost {ACT} >= 0;
В построчном подходе новая цель записывается как
maximize Net_Profit: sum {i in MATF} revenue[i] * Sell[i] - sum {j in ACT} cost[j] * Run[j];
общая выручка от продаж за вычетом общих затрат на сырье и производство. Пока что мы, кажется, улучшили модель: Структура чистой прибыли более четко сформулирована, и продажи ограничиваются явно обозначенными готовыми материалами. Кроме того, оптимальные объямы продаж легче анализируются, помимо других переменных, с помощью такой команды display Sell. Осталось исправить ограничения. Мы хотели бы сказать, что чистый объем производства материала i от всех видов деятельности, представлен в виде:
sum {j in ACT} io[i,j] * Run[j]
должно равняться проданному количеству - Sell[i], если i - готовый материал, либо нулю. Таким образом, объявление ограничения должно быть написано:
subject to Balance {i in MAT}: sum {j in ACT} io[i,j] * Run[j] = if i in MATF then Sell[i] else 0;
К сожалению, это ограничение кажется менее ясным, чем наше первоначальное, из-за усложнения, вызванного выражением if-then-else.
В столбчатой альтернативе цель и ограничения такие же, как модели выше, а все изменения отражены в объявлениях переменных:
var Run {j in ACT} >= act_min[j], <= act_max[j], obj Net_Profit - cost[j], coeff {i in MAT} Balance[i] io[i,j];
var Sell {i in MATF} >= sell_min[i], <= sell_max[i], obj Net_Profit revenue[i], coeff Balance[i]-1;
В этом представлении переменная Sell[i] представляет вид продаж, который мы ранее описали, только с материалом i в качестве входных данных и без материалов в качестве выходных данных - отсюда и единственный коэффициент –1 в ограничении Balance[i]. Нам не нужно указывать все нулевые коэффициенты для Sell[i]. Ноль предполагается для любого ограничения, не указанного явно во фразе coeff в объявлении. Полная модель имеет следующий вид:
set MAT; # materials
set ACT; # activities
param io {MAT,ACT}; # input-output coefficients
set MATF within MAT; # finished materials
param revenue {MATF} >= 0;
param sell_min {MATF} >= 0;
param sell_max {i in MATF} >= sell_min[i];
param cost {ACT} >= 0;
param act_min {ACT} >= 0;
param act_max {j in ACT} >= act_min[j];
maximize Net_Profit;
subject to Balance {i in MAT}: to_come = 0;
var Run {j in ACT} >= act_min[j], <= act_max[j], obj Net_Profit -cost[j], coeff {i in MAT} Balance[i] io[i,j]; var Sell {i in MATF} >= sell_min[i], <= sell_max[i], obj Net_Profit revenue[i], coeff Balance[i] -1;
Файл iocol2.mod на сайте AMPL.
Этот пример предполагает, что подход по столбцам особенно подходит для уточнения модели "черный ящик", которая позволяет различать различные виды деятельности. Например, легко добавить еще одну группу переменных, которые представляют закупку сырья. С другой стороны, версии модели "черный ящик", которые включают в себя многочисленные специализированные ограничения, в большей степени подходят для формулировки по строкам.
