Почти все линейные программы в этом руководстве сформулированы в терминах неотрицательных переменных. Однако иногда переменная имеет смысл как при отрицательных, так и при положительных значениях, и во многих таких случаях связанные затраты являются кусочно-линейными с нулевой точкой останова.
Один из примеров - переменные инвентаризации модели:
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
Мы определили Inv[p,t], чтобы представить тонны продукта p, инвентаризованные в конце недели t. То есть в конце недели t есть Inv[p,t] тонн продукта p, которые были произведены, но не проданы. Отрицательное значение Inv[p,t], таким образом, можно интерпретировать как масса продукта p, который был продан, но не произведен - фактически, тонны отложенного заказа.
Ограничения материального баланса, остаются в силе при этой интерпретации:
subject to Balance {p in PROD, t in 1..T}:
Make[p,t] + Inv[p,t-1] = Sell[p,t] + Inv[p,t];
Этот анализ предполагает, что мы удалим >= 0 из объявления Inv в нашей модели. Тогда отложенный заказ может быть особенно привлекательным, если в последующие недели ожидается снижение продажной цены, например:
param revenue: 1 2 3 4 := bands 25 26 23 20 coils 30 35 31 25 ;
Однако, когда мы повторно решаем проблему с должным образом отредактированной моделью и файлами данных, результаты не соответствуют нашим ожиданиям:
ampl: model steelpl4.mod; data steelpl4.dat; solve; MINOS 5.5: optimal solution found. 15 iterations, objective 1194250 ampl: display Make,Inv,Sell; : Make Inv Sell := bands 0 . 10 . bands 1 0 -5990 6000 bands 2 0 -11990 6000 bands 3 0 -15990 4000 bands 4 0 -22490 6500 coils 0 . 0 . coils 1 0 -4000 4000 coils 2 0 -6500 2500 coils 3 0 -10000 3500 coils 4 0 -14200 4200 ;
Источник сложности заключается в целевой функции, где invcost[p] * Inv[p,t] вычитается из дохода от продаж. Когда Inv[p,t] отрицательное, отрицательная сумма вычитается, увеличивая видимую общую прибыль. Чем больше сумма отложенного заказа, тем больше увеличивается общая прибыль - отсюда и странное решение, при котором максимально возможные продажи задерживаются, а ничего не производится!
Правильная функция стоимости запасов для этой модели выглядит следующим образом:
Она увеличивается по мере того, как Inv[p,t] становится более положительным (большие запасы), так и по мере того, как Inv[p,t] становится более отрицательным (больше невыполненных заказов). Мы представляем эту кусочно-линейную функцию в AMPL, объявляя стоимость невыполненного заказа вместе со стоимостью запасов:
param invcost {PROD} >= 0;
param backcost {PROD} >= 0;
Тогда наклоны для Inv[p,t] в цели равны - backcost[p] и invcost[p], с точкой останова, равной нулю, и правильная целевая функция:
maximize Total_Profit:
sum {p in PROD, t in 1..T} (revenue[p,t]*Sell[p,t] - prodcost[p]*Make[p,t]
- <<0; -backcost[p],invcost[p]>> Inv[p,t]) - sum {t in 1..T}
<<avail_min[t]; 0,time_penalty[t]>> Use[t];
В отличие от нашего первого примера, кусочно-линейная функция скорее вычитается, чем складывается. Тем не менее, результат остается кусочно-линейным. Это то же самое, как если бы мы добавили выражение << 0; backcost [p], -invcost [p] >> Inv [p, t].
Когда мы вносим это изменение и добавляем к данным некоторые затраты на просроченный заказ, мы получаем более разумное решение. Тем не менее, сохраняется тенденция ничего не делать и все откладывать в более поздние периоды; это «конечный эффект», который возникает из-за того, что модель не учитывает конечную стоимость производства товаров, заказанных по истечении последнего периода. В качестве быстрого исправления мы можем исключить любые оставшиеся невыполненные заказы в конце. Добавив ограничение, согласно которому запасы на последней неделе должны быть неотрицательными:
subject to Final {p in PROD}: Inv[p,T] >= 0;
Решение с этим ограничением и со значениями обратных затрат 1,5 для bands и 2 для coils:
ampl: model steelpl5.mod; data steelpl5.dat; solve; MINOS 5.5: optimal solution found. 20 iterations, objective 370752.8571 ampl: display Make,Inv,Sell; : Make Inv Sell := bands 0 . 10 . bands 1 4142.86 0 4152.86 bands 2 6000 0 6000 bands 3 3000 0 3000 bands 4 3000 0 3000 coils 0 . 0 . ; coils 1 2000 0 2000 coils 2 1680 -820 2500 coils 3 2100 -800 2080 coils 4 2800 0 2000 ;
Согласно этому плану, около 800 тонн coils на 2 и 3 недели будут доставлены с опозданием на неделю.
