Линейные программы наиболее легко выражают «жесткие» ограничения: например, уровень производства должен быть не ниже(выше) определенной величины, или используемые ресурсы не должны превышать количество доступных ресурсов. Реальные ситуации часто не так однозначны. Производство и использование ресурсов могут иметь определенные предпочтительные уровни. Однако, можно нарушать эти уровни, принимая некоторые дополнительные расходы или уменьшая прибыль. Результирующие «мягкие» ограничения можно смоделировать, добавляя кусочно-линейные «штрафы» к целевой функции.
В качестве примера мы обратимся к модели многонедельного производства:
set PROD; # products
param T > 0; # number of weeks
param rate {PROD} > 0; # tons per hour produced
param inv0 {PROD} >= 0; # initial inventory
param avail {1..T} >= 0; # hours available in week
param market {PROD,1..T} >= 0; # limit on tons sold in week
param prodcost {PROD} >= 0; # cost per ton produced
param invcost {PROD} >= 0; # carrying cost/ton of inventory
param revenue {PROD,1..T} >= 0; # revenue per 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]; # tons sold
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]);
# Total revenue less costs in all weeks
subject to Time {t in 1..T}:
sum {p in PROD} (1/rate[p]) * Make[p,t] <= avail[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
Как видно из представленной модели: ограничения свидетельствуют, что в каждую из недель с 1 по T общее количество часов, затрачиваемых на производство всех продуктов, не может превышать определенной величины:
subject to Time {t in 1..T}:
sum {p in PROD} (1/rate[p]) * Make[p,t] <= avail[t];
Предположим, что на самом деле в каждую неделю можно использовать большее количество часов, но с некоторым штрафом в час к общей прибыли. В частности, мы заменяем параметр avail [t] двумя уровнями доступности и почасовой ставкой штрафа:
param avail_min {1..T} >= 0;
param avail_max {t in 1..T} >= avail_min[t];
param time_penalty {1..T} > 0;
До значения avail_min[t] часов деятельность осуществляется без штрафа. Деятельность между уровнями avail_min[t] и avail_max[t] происходит с потерей прибыли на величину time_penalty[t].
Чтобы смоделировать эту ситуацию, необходимо ввести новую переменную Use[t] для отражения часов, используемых производством. Очевидно, что Use[t] не может быть меньше нуля или больше avail_max[t]. Вместо нашего предыдущего ограничения мы говорим, что общее количество часов, затрачиваемое на производство всех продуктов, должно быть равно Use[t]:
var Use {t in 1..T} >= 0, <= avail_max[t];
subject to Time {t in 1..T}:
sum {p in PROD} (1/rate[p]) * Make[p,t] = Use[t];
Теперь мы можем описать почасовой штраф в терминах этой новой переменной. Если Use[t] находится между "0" и avail_min[t], штрафа нет. Если значение Use[t] находится между avail_min[t] и avail_max[t], штраф составляет time_penalty[t] в час. То есть штраф является кусочно-линейной функцией Use[t], как показано на рисунке ниже, с крутизной "0" и значением time_penalty[t] возле точки останова avail_min[t]. Используя ранее введенный синтаксис, мы можем переписать выражение целевой функции:
maximize Net_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];
Первое суммирование - это то же выражение для общей прибыли, что и раньше, а второе - сумма кусочно-линейных штрафных функций за все недели. Между << и >> находятся точка останова avail_min[t] и список окружающих наклонов,"0" и time_penalty[t]. За ним следует аргумент Use[t].
Окончательная пересмотренная модель показана ниже, а наш небольшой набор данных расширен новыми штрафами. В оптимальном решении мы находим, что используемые часы имеют следующие значения:
ampl: model steelpl1.mod; data steelpl1.dat; solve; MINOS 5.5: optimal solution found. 21 iterations, objective 457572.8571 ampl: display avail_min,Use,avail_max; : avail_min Use avail_max := 1 35 35 42 2 35 42 42 3 30 30 40 4 35 42 42 ;
На 1-й и 3-й неделях мы используем только доступные часы без штрафов, а на 2-й и 4-й неделях мы также используем штрафные часы. Решения для кусочно-линейных программ обычно отображают такого рода решения, в которых многие (хотя и не обязательно все) переменные «застревают» в одной из точек останова.
set PROD; # products
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} >= commit[p,t], <= market[p,t]; # tons sold var Use {t in 1..T} >= 0, <= avail_max[t]; # hours used
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];
# 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
param T := 4;
set PROD := bands coils;
param: rate inv0 prodcost invcost :=
bands 200 10 10 2.5
coils 140 0 11 3 ;
param: avail_min avail_max time_penalty :=
1 35 42 3100
2 35 42 3000
3 30 40 3700
4 35 42 3100 ;
param revenue: 1 2 3 4 :=
bands 25 26 27 27
coils 30 35 37 39 ;
param commit: 1 2 3 4 :=
bands 3000 3000 3000 3000
coils 2000 2000 2000 2000 ;
param market: 1 2 3 4 :=
bands 6000 6000 4000 6500
coils 4000 2500 3500 4200 ;
