Параметры commit[p,t] в модели выше, представляют минимальные объемы производства для каждого продукта в каждую неделю. Если мы изменим данные, чтобы поднять эти обязательства:
param commit: 1 2 3 4 := bands 3500 5900 3900 6400 coils 2500 2400 3400 4100 ;
тогда не хватает часов, чтобы произвести даже эти минимальные количества, и решатель сообщает, что проблема невыполнима:
ampl: model steelpl1.mod; ampl: data steelpl2.dat; ampl: solve; MINOS 5.5: infeasible problem. 13 iterations
В возвращаемом решении запас катушек (coils) за последний период отрицательный:
ampl: option display_1col 0; ampl: display Inv; Inv [*,*] (tr) : bands coils := 0 10 0 1 0 937 2 0 287 3 0 0 4 0 -2700 ;
а производство coils в нескольких периодах ниже требуемого минимума:
ampl: display commit,Make,market; : commit Make market := bands 1 3500 3490 6000 bands 2 5900 5900 6000 bands 3 3900 3900 4000 bands 4 6400 6400 6500 coils 1 2500 3437 4000 coils 2 2400 1750 2500 coils 3 3400 2870 3500 coils 4 4100 1400 4200 ;
Это типичные недопустимые результаты, которые возвращают решатели. Невозможности разбросаны по всему решению, поэтому трудно сказать, какие изменения могут потребоваться для достижения осуществимости. Расширяя понятие штрафов, мы можем лучше сконцентрировать неосуществимость там, где ее можно понять.
- Предположим, что мы хотим рассмотреть невозможность с точки зрения нехватки часов. Представьте, что мы расширяем кусочно-линейную штрафную функцию:
до функции:
Теперь Use[t] разрешено увеличивать значение avail_max[t], но только с очень большим штрафом за час - так что решение будет использовать часы выше avail_max[t] только в в случае крайней необходимости.
В AMPL новая функция штрафа вводится посредством следующих изменений:
var Use {t in 1..T} >= 0;
maximize Total_Profit:
sum {p in PROD, t in 1..T} (revenue[p,t]*Sell[p,t] -
prodcost[p]*Make[p,t] - invcost[p]*Inv[p,t])
- sum {t in 1..T} <<avail_min[t],avail_max[t]; 0,time_penalty[t],100000>> Use[t];
Прежняя граница avail_max[t] стала точкой останова, и справа от нее был введен очень большой наклон в 100000. Теперь мы получаем возможное решение, в котором часы используются следующим образом:
ampl: model steelpl2.mod; data steelpl2.dat; solve; MINOS 5.5: optimal solution found. 19 iterations, objective -1576814.857 ampl: display avail_max,Use; : avail_max Use := 1 42 42 2 42 42 3 40 41.7357 4 42 61.2857 ;
Эта таблица подразумевает, что обязательства могут быть выполнены, только добавив около 21 часа, в основном за последнюю неделю.
2. В качестве альтернативы мы можем рассматривать неосуществимость с точки зрения превышения обязательств.
Для этого мы вычитаем очень большой штраф из цели за каждую единицу, в которой Sell[p,t] падает ниже commit[p,t]. Штраф как функция Sell[p,t] показан на рисунке:
Так как эта функция имеет точку останова в commit[p,t], с наклоном "0" вправо и очень отрицательным значением слева, может показаться, что представление AMPL может быть:
<<commit[p,t]; -100000,0>> Sell[p,t]
Вспомните, однако, соглашение AMPL о том, что такая функция принимает нулевое значение в ноле.
Рисунок 3 ясно показывает, что мы хотим, чтобы наша штрафная функция принимала положительное значение в ноле, чтобы оно упало до нуля в commit[p,t] и далее, фактически мы хотим, чтобы функция принимала значение 100000 * commit[p,t] в ноле, и мы могли бы правильно выразить функцию, добавив эту константу в выражение штрафа:
<<commit[p,t]; -100000,0>> Sell[p,t] + 100000*commit[p,t]
То же самое можно сказать более кратко, используя второй аргумент, который явно указывает, где кусочно-линейная функция должна быть равна нулю:
<<commit[p,t]; -100000,0>> (Sell[p,t],commit[p,t])
Это говорит о том, что функция должна быть равна нулю в commit[p,t], как показано на Рисунке 3. В готовой модели мы имеем:
param T > 0; # number of weeks
param rate {PROD} > 0; # tons per hour produced
param inv0 {PROD} >= 0; # initial inventory
param commit {PROD,1..T} >= 0; # minimum tons sold in week
param market {PROD,1..T} >= 0; # limit on tons sold in week
param avail_min {1..T} >= 0; # unpenalized hours available
param avail_max {t in 1..T} >= avail_min[t]; # total hours avail
param time_penalty {1..T} > 0;
param prodcost {PROD} >= 0; # cost/ton produced
param invcost {PROD} >= 0; # carrying cost/ton of inventory
param revenue {PROD,1..T} >= 0; # revenue/ton sold
var Make {PROD,1..T} >= 0; # tons produced
var Inv {PROD,0..T} >= 0; # tons inventoried
var Sell {p in PROD, t in 1..T} >= 0, <= market[p,t];
maximize Total_Profit: sum {p in PROD, t in 1..T} (revenue[p,t]*Sell[p,t] - prodcost[p]*Make[p,t] - invcost[p]*Inv[p,t]) - sum {t in 1..T} <<avail_min[t]; 0,time_penalty[t]>> Use[t] - sum {p in PROD, t in 1..T} <<commit[p,t]; -100000,0>> (Sell[p,t],commit[p,t]);
# Objective: total revenue less costs in all weeks
subject to Time {t in 1..T}: sum {p in PROD} (1/rate[p]) * Make[p,t] = Use[t];
# Total of hours used by all products
# may not exceed hours available, in each week
subject to Init_Inv {p in PROD}: Inv[p,0] = inv0[p];
# Initial inventory must equal given value
subject to Balance {p in PROD, t in 1..T}: Make[p,t] + Inv[p,t-1] = Sell[p,t] + Inv[p,t];
# Tons produced and taken from inventory
# must equal tons sold and put into inventory
Обратите внимание, что Sell[p,t] появляется как в линейном, так и в кусочно-линейном элементе в целевой функции. AMPL автоматически распознает, что сумма этих элементов также кусочно-линейна.
Эта версия, использующая те же данные, дает следующее решение:
ampl: model steelpl3.mod; data steelpl2.dat; solve; MINOS 5.5: optimal solution found. 24 iterations, objective -293856347 ampl: display Sell,commit; : Sell commit := bands 1 3500 3500 bands 2 5900 5900 bands 3 3900 3900 bands 4 6400 6400 coils 1 0 2500 coils 2 2400 2400 coils 3 3400 3400 coils 4 3657 4100 ;
Чтобы справиться с заданным количеством часов, обязательства по доставке рулонов сокращаются на 2500 тонн в первую неделю и на 443 тонны в четвертую неделю.
