Многие простые кусочно-линейные функции можно моделировать несколькими эквивалентными способами в AMPL. Например, функцию:
можно записать как:
if Use[t] > avail_min[t] then time_penalty[t] * (Use[t] - avail_min[t]) else 0
или более кратко, как
max(0, time_penalty[t] * (Use[t] - avail_min[t]))
Текущая версия AMPL не определяет, являются ли эти выражения кусочно-линейными. Поэтому мы вряд ли получим удовлетворительные результаты, если попытаемся решить эту модель. Которая имеет подобные выражения в своей целевой функции. Чтобы воспользоваться преимуществами методов линейного программирования, которые могут применяться для кусочно-линейных сегментов, необходимо использовать кусочно-линейную терминологию:
<<avail_min[t]; 0,time_penalty[t]>> Use[t]
так, структура может быть отмечена и передана решателю.
Тот же совет относится к функции ABS. Представьте, что мы хотим чтобы количество часов было близко к avail_min[t]. Тогда, мы бы хотели, чтобы штраф равнялся time_penalty[t], умноженному на сумму, на которую Use[t] отклоняется (выше или ниже) от avail_min[t]. Такую формулировку можно записать следующим образом:
time_penalty[t] * abs(Use[t] - avail_min[t])
Однако, чтобы выразить его явно кусочно-линейным образом, необходимо записать его так:
time_penalty[t] * <<avail_min[t]; -1,1>> Use[t]
или эквивалентно
<<avail_min[t]; -time_penalty[t],time_penalty[t]>> Use[t]
Как показывает этот пример: умножение кусочно-линейной функции на константу равносильно умножению каждого из ее угловых коэффициентов по отдельности.
В качестве последнего примера распространенной кусочно-линейной задачи мы обратимся к модели назначения:
set PEOPLE;
set PROJECTS;
set ABILITIES within (PEOPLE cross PROJECTS);
param supply {PEOPLE} >= 0; # hours each person is available
param demand {PROJECTS} >= 0; # hours each project requires
check: sum {i in PEOPLE} supply[i] = sum {j in PROJECTS} demand[j];
param cost {ABILITIES} >= 0; # cost per hour of work
param limit {ABILITIES} >= 0; # maximum contributions to projects
var Assign {(i,j) in ABILITIES} >= 0, <= limit[i,j];
minimize Total_Cost:
sum {(i,j) in ABILITIES} cost[i,j] * Assign[i,j];
subject to Supply {i in PEOPLE}:
sum {(i,j) in ABILITIES} Assign[i,j] = supply[i];
subject to Demand {j in PROJECTS}:
sum {(i,j) in ABILITIES} Assign[i,j] = demand[j];
Напомним, что для i в наборе PEOPLE и j в наборе PROJECTS cost[i,j] - это стоимость часа работы человека i над проектом j, а переменная решения Assign [i,j] - это количество часов, которое человеку i назначено для работы над проектом j:
set PEOPLE;
set PROJECTS;
param cost {PEOPLE,PROJECTS} >= 0;
var Assign {PEOPLE,PROJECTS} >= 0;
Изначально мы сформулировали целевую функцию как общую стоимость всех заданий,
sum {i in PEOPLE, j in PROJECTS} cost[i,j] * Assign[i,j]
Что, если мы хотим получить самое справедливое задание вместо самого дешевого? Тогда мы можем минимизировать максимальную стоимость заданий любого человека:
minimize Max_Cost: max {i in PEOPLE}
sum {j in PROJECTS} cost[i,j] * Assign[i,j];
Эта функция в некотором смысле также кусочно-линейна. Она складывается из линейных функций sum {j in PROJECTS} cost[i,j] * Assign[i,j]для разных людей i. Однако она не является кусочно-линейной по отдельным переменным. На математическом языке она не разделима - и, следовательно, ее нельзя записать с использованием обозначения <<. . . >>.
Это тот случай, когда кусочная линейность может быть обработана только путем переписывания модели в виде линейной программы. Мы вводим новую переменную M для представления максимума. Затем мы пишем ограничения, чтобы гарантировать, что M больше или равно каждой стоимости, из которой она является максимальной:
var M;
minimize Max_Cost: M;
subject to M_def {i in PEOPLE}:
M >= sum {j in PROJECTS} cost[i,j] * Assign[i,j];
Поскольку M минимизируется, при оптимальном решении оно фактически будет равно максимуму sum {j in PROJECTS} cost[i,j] * Assign[i,j]для всех i в PEOPLE. Остальные ограничения такие же, как и в любой задаче назначения:
set PEOPLE;
set PROJECTS;
param supply {PEOPLE} >= 0; # hours each person is available
param demand {PROJECTS} >= 0; # hours each project requires
check: sum {i in PEOPLE} supply[i] = sum {j in PROJECTS} demand[j];
param cost {PEOPLE,PROJECTS} >= 0; # cost per hour of work
param limit {PEOPLE,PROJECTS} >= 0; # maximum contributions
# to projects
var M;
var Assign {i in PEOPLE, j in PROJECTS} >= 0, <= limit[i,j]; minimize Max_Cost: M; subject to M_def {i in PEOPLE}: M >= sum {j in PROJECTS}
cost[i,j] * Assign[i,j];
subject to Supply {i in PEOPLE}:
sum {j in PROJECTS} Assign[i,j] = supply[i];
subject to Demand {j in PROJECTS}:
sum {i in PEOPLE} Assign[i,j] = demand[j];
Такой вид переформулировки может быть применен к любой задаче, имеющей цель «минимум-максимум». Та же идея работает для аналогичной цели «max-min», с maximize вместо minimize и с M <=... в ограничениях.
