Некоторые виды задач линейного программирования используют функции, которые на самом деле не являются линейными, а состоят из нескольких связанных линейных сегментов:
Кусочно-линейные характеристики часто используются для того, чтобы дать более реалистичное описание затрат, чем это может быть достигнуто одними только линейными терминами. В такого рода приложениях кусочно-линейные термины служат практически той же цели, что и нелинейные, но без некоторых трудностей, которые присущи нелинейному моделированию.
Чтобы сделать сравнение явным, мы будем использовать тот же пример транспортировки, что и в главе "Нелинейные модели".
Фиксированное количество кусочков
В линейной транспортной модели:
set ORIG; # origins
set DEST; # destinations
param supply {ORIG} >= 0; # amounts available at origins
param demand {DEST} >= 0; # amounts required at destinations
check: sum {i in ORIG} supply[i] = sum {j in DEST} demand[j];
param cost {ORIG,DEST} >= 0; # shipment costs per unit
var Trans {ORIG,DEST} >= 0; # units to be shipped
minimize Total_Cost:
sum {i in ORIG, j in DEST} cost[i,j] * Trans[i,j];
subject to Supply {i in ORIG}:
sum {j in DEST} Trans[i,j] = supply[i];
subject to Demand {j in DEST}:
sum {i in ORIG} Trans[i,j] = demand[j];
любое количество единиц может быть отправлено из заданного пункта отправления в заданный пункт назначения с одинаковой стоимостью за единицу. Однако более реалистичный случай, когда наиболее выгодная ставка может быть доступна только для ограниченного числа единиц. Поставки сверх этого лимита оплачиваются по более высоким тарифам. Для каждой пары исходный пункт - пункт назначения, указаны три уровня стоимости. Общая стоимость доставки по заданному направлению повышается с увеличением количества отправлений по кусочно-линейной схеме, состоящей из трех частей:
Чтобы смоделировать трехкомпонентные затраты, мы заменяем параметр cost на 3 параметра rate и 2 параметра limit:
param rate1 {i in ORIG, j in DEST} >= 0;
param rate2 {i in ORIG, j in DEST} >= rate1[i,j];
param rate3 {i in ORIG, j in DEST} >= rate2[i,j];
param limit1 {i in ORIG, j in DEST} > 0;
param limit2 {i in ORIG, j in DEST} > limit1[i,j];
Доставка от i до j оплачивается по ставке rate1[i,j] за единицу до значения limit1 [i,j] единиц. Затем по ставке rate2[i,j] за единицу до limit2 [i,j], а затем по ставке rate3[i,j].
Обычно rate2 [i,j] больше, чем rate1 [i,j], а rate3 [i,j] больше, чем rate2 [i,j], но они могут быть и равны, если ссылка от i до j не имеет различия в ставках.
В линейной транспортной модели цель выражается через переменные и параметр cost следующим образом:
var Trans {ORIG,DEST} >= 0;
minimize Total_Cost: sum {i in ORIG, j in DEST} cost[i,j] * Trans[i,j];
Мы могли бы аналогичным образом выразить кусочно-линейную задачу, введя три набора переменных, одна из которых представляет количество, отгруженное по каждой ставке:
var Trans1 {i in ORIG, j in DEST} >= 0, <= limit1[i,j];
var Trans2 {i in ORIG, j in DEST} >= 0, <= limit2[i,j]
- limit1[i,j];
var Trans3 {i in ORIG, j in DEST} >= 0;
minimize Total_Cost: sum {i in ORIG, j in DEST} (rate1[i,j]
* Trans1[i,j] + rate2[i,j] * Trans2[i,j] + rate3[i,j] * Trans3[i,j]);
Однако, тогда новые переменные должны быть введены во все ограничения и придется иметь дело с этими переменными всякий раз, когда нужно отобразить оптимальные результаты. Вместо того, чтобы возиться со всеми этими проблемами, можно явно описать кусочно-линейную функцию стоимости в терминах исходных переменных. Поскольку стандартного способа описания кусочно-линейных функций в алгебраической нотации не существует, AMPL предоставляет для этой цели свой собственный синтаксис.
з-х кусочная линейная функция, изображенная выше, формулируется в AMPL следующим образом:
<<limit1[i,j], limit2[i,j]; rate1[i,j], rate2[i,j], rate3[i,j]>> Trans[i,j]
Выражение между << ... >> описывает кусочно-линейную функцию, за которой следует имя переменной, к которой оно применяется. (Это как "умножениие" Trans [i,j] на серию коэффициентов. Выражение состоит из двух частей: списка точек останова, в которых изменяется наклон функции, и списка наклонов - в данном случае это limit[i,j]. Списки разделяются точкой с запятой, а элементы каждого списка разделяются запятыми. Поскольку первый наклон применяется к значениям до первой точки останова, а последний наклон - к значениям после последней точки останова, количество наклонов должно быть на единицу больше, чем количество точек останова.
Несмотря на то, что списков точек останова и наклонов достаточно для описания кусочно-линейной функции затрат для оптимизации, они не совсем точно и однозначно определяют функцию. Если добавить, скажем, значение 10 к стоимости в каждой точке, тогда получится другая функция стоимости, даже если все точки останова и наклоны остались прежними. Чтобы устранить эту двусмысленность, AMPL предполагает, что кусочно-линейная функция принимает нулевое значение, как показано на рисунке выше.
Суммируя стоимость по всем направлениям, получим кусочно-линейную целевую функцию:
minimize Total_Cost: sum {i in ORIG, j in DEST}
<<limit1[i,j], limit2[i,j];
rate1[i,j], rate2[i,j], rate3[i,j]>> Trans[i,j];
Объявления переменных и ограничений остаются такими же, как и раньше. Окончательная модель имеет следующий вид:
set ORIG; # origins
set DEST; # destinations
param supply {ORIG} >= 0; # amounts available at origins
param demand {DEST} >= 0; # amounts required at destinations
check: sum {i in ORIG} supply[i] = sum {j in DEST} demand[j];
param rate1 {i in ORIG, j in DEST} >= 0;
param rate2 {i in ORIG, j in DEST} >= rate1[i,j];
param rate3 {i in ORIG, j in DEST} >= rate2[i,j];
param limit1 {i in ORIG, j in DEST} > 0;
param limit2 {i in ORIG, j in DEST} > limit1[i,j];
var Trans {ORIG,DEST} >= 0; # units to be shipped
minimize Total_Cost: sum {i in ORIG, j in DEST}
<<limit1[i,j], limit2[i,j];
rate1[i,j], rate2[i,j], rate3[i,j]>> Trans[i,j];
subject to Supply {i in ORIG}: sum {j in DEST} Trans[i,j] = supply[i];
subject to Demand {j in DEST}: sum {i in ORIG} Trans[i,j] = demand[j];
Динамическое количество кусочков
Подход, использованный в предыдущем примере, наиболее полезен, когда для каждого элемента имеется всего несколько линейных частей. Однако если имеется например 12 кусочков вместо трех, модель, становится громоздкой. Более того, в реальности для каждого термина более вероятно, что будет около 12 кусочков, а не точно 12. Случай, содержащий менее 12 штук, можно было бы обработать, уравняв некоторые тарифы, но для большого количества частей это было бы громоздкой конструкцией, которая потребует много ненужных значений данных и скроет фактическое количество частей в каждом элементе.
Гораздо лучший подход - позволить самому количеству кусочков (то есть количеству тарифов доставки) быть параметром модели, индексируемым по направлениям:
param npiece {ORIG,DEST} integer >= 1;
Затем мы можем проиндексировать ставки и лимиты для всех комбинаций направлений и частей:
param rate {i in ORIG, j in DEST, p in 1..npiece[i,j]}
>= if p = 1 then 0 else rate[i,j,p-1];
param limit {i in ORIG, j in DEST, p in 1..npiece[i,j]-1}
> if p = 1 then 0 else limit[i,j,p-1];
Для любого конкретного пункта отправления i и пункта назначения j количество линейных частей в термине стоимости определяется как npiece [i, j]. Наклоны - это rate[i,j,p] для p от 1 до npiece [i,j], а промежуточные точки останова - limit [i,j,p] для p от 1 до npiece [i,j] -1. Как и раньше, количество наклонов больше, чем точек останова.
Чтобы использовать кусочно-линейную нотацию функций AMPL с этими значениями данных, мы должны предоставить индексированные списки точек останова и наклонов, а не явные списки из предыдущего примера. Это делается путем помещения выражений индексации перед значениями наклона и точки останова:
minimize Total_Cost: sum {i in ORIG, j in DEST}
<<{p in 1..npiece[i,j]-1} limit[i,j,p];
{p in 1..npiece[i,j]} rate[i,j,p]>> Trans[i,j];
В остальном модель та же. Ниже показана итоговая модель и данные. Обратите внимание, что поскольку npiece ["PITT", "STL"] равно 1, Trans ["PITT", "STL"] имеет только один наклон и не имеет точек останова. Это подразумевает линейный элемент для Trans ["PITT", "STL"] в целевой функции.
set ORIG; # origins
set DEST; # destinations
param supply {ORIG} >= 0; # amounts available at origins
param demand {DEST} >= 0; # amounts required at destinations
check: sum {i in ORIG} supply[i] = sum {j in DEST} demand[j];
param npiece {ORIG,DEST} integer >= 1;
param rate {i in ORIG, j in DEST, p in 1..npiece[i,j]}
>= if p = 1 then 0 else rate[i,j,p-1];
param limit {i in ORIG, j in DEST, p in 1..npiece[i,j]-1}>
if p = 1 then 0 else limit[i,j,p-1];
var Trans {ORIG,DEST} >= 0; # units to be shipped
minimize Total_Cost: sum {i in ORIG, j in DEST}
<<{p in 1..npiece[i,j]-1} limit[i,j,p];
{p in 1..npiece[i,j]} rate[i,j,p]>> Trans[i,j];
subject to Supply {i in ORIG}: sum {j in DEST} Trans[i,j] = supply[i];
subject to Demand {j in DEST}: sum {i in ORIG} Trans[i,j] = demand[j];
param: ORIG: supply := GARY 1400 CLEV 2600 PITT 2900 ; param: DEST: demand := FRA 900 DET 1200 LAN 600 WIN 400 STL 1700 FRE 1100 LAF 1000 ; param npiece: FRA DET LAN WIN STL FRE LAF := GARY 3 3 3 2 3 2 3 CLEV 3 3 3 3 3 3 3 PITT 2 2 2 2 1 2 1 ; param rate := [GARY,FRA,*] 1 39 2 50 3 70 [GARY,DET,*] 1 14 2 17 3 33 [GARY,LAN,*] 1 11 2 12 3 23 [GARY,WIN,*] 1 14 2 17 [GARY,STL,*] 1 16 2 23 3 40 [GARY,FRE,*] 1 82 2 98 [GARY,LAF,*] 1 8 2 16 3 24 [CLEV,FRA,*] 1 27 2 37 3 47 [CLEV,DET,*] 1 9 2 19 3 24 [CLEV,LAN,*] 1 12 2 32 3 39 [CLEV,WIN,*] 1 9 2 14 3 21 [CLEV,STL,*] 1 26 2 36 3 47 [CLEV,FRE,*] 1 95 2 105 3 129 [CLEV,LAF,*] 1 8 2 16 3 24 [PITT,FRA,*] 1 24 2 34 [PITT,DET,*] 1 14 2 24 [PITT,LAN,*] 1 17 2 27 [PITT,WIN,*] 1 13 2 23 [PITT,STL,*] 1 28 [PITT,FRE,*] 1 99 2 140 [PITT,LAF,*] 1 20 ; param limit := [GARY,*,*] FRA 1 500 FRA 2 1000 DET 1 500 DET 2 1000 LAN 1 500 LAN 2 1000 WIN 1 1000 STL 1 500 STL 2 1000 FRE 1 1000 LAF 1 500 LAF 2 1000 [CLEV,*,*] FRA 1 500 FRA 2 1000 DET 1 500 DET 2 1000 LAN 1 500 LAN 2 1000 WIN 1 500 WIN 2 1000 STL 1 500 STL 2 1000 FRE 1 500 FRE 2 1000 LAF 1 500 LAF 2 1000 [PITT,*,*] FRA 1 1000 DET 1 1000 LAN 1 1000 WIN 1 1000 FRE 1 1000 ;
Простые кусочно-линейные элементы имеют множество применений в линейных моделях.
Мы рассмотрим три случая использования кусочно-линейной формулировки:
- допущение нарушений "мягкие ограничения";
- анализ неосуществимости;
- представление затрат для переменных, которые значимы как на отрицательном, так и на положительном отрезке.
