Многие простые кусочно-линейные функции можно моделировать несколькими эквивалентными способами в AMPL. Например, функцию:
![](https://i0.wp.com/www.solverytic.com/wp-content/uploads/2020/09/17-4.png?resize=759%2C221&ssl=1)
можно записать как:
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 <=... в ограничениях.