Наборы, параметры и переменные являются наиболее общими объектами модели, которые необходимо учитывать при интерпретации решения линейной программы. AMPL также предоставляет инструменты изучения целей, границ, разрывов, двойных цен и уменьшенной стоимости, связанных с оптимальным решением. Как уже было показано в многочисленных примерах, AMPL различает значения, связанные с компонентами модели, используя «квалифицированные» имена, которые состоят из идентификатора переменной или ограничения, точки (.) и предопределенного суффикса. Например, верхние границы для переменной Make называются Make.ub, а верхняя граница для Make ["coils", 2] - Make ["coils", 2].ub. Суффикс следует за индексом. Если объявить display Make, Make.ub будут отображены список оптимальных значений и верхние границы.
Целевые функции
Имя целевой функции (из объявления minimize или maximize) относится к значению цели, вычисленному из текущих значений переменных. Это имя может использоваться для представления оптимального значения целевой функции в display, print или printf:
print 100 * Total_Profit / sum {p in PROD, t in 1..T} revenue[p,t] * Sell[p,t];
65.37528084182735
Если текущая модель объявляет несколько целевых функций, можно ссылаться на любую из них, даже если только одна была оптимизирована. Можно написать несколько целевых функций в модели AMPL, но нельзя сказать, что бы одна была минимизирована, а другая максимизирована, - одновременно. Обычно, когда есть две цели, между ними возникает конфликт, так что решения, минимизирующие целевую функцию №1, не являются максимальными для функции №2. А решения, которые максимизируют цель №2, не являются минимальными для цели №1. Решение, которое минимизирует одну цель и максимизирует другую, будет иметь место только в редких ситуациях, поэтому не следует полагать, что можно оптимизировать обе цели одновременно для своей проблемы. Однако с использованием современных решателей можно произвести подобные вычисления. Вариант для получения хороших решений с несколькими целями указан в разделе multiobj в справочнике параметров AMPL-Gurobi и в опциях CPLEX для AMPL. Существует также более подробное описание этого параметра на странице https://groups.google.com/d/msg/ampl/cDKRsJFHJcQ/AhZsBmnqDQAJ (приводимые примеры из Gurobi, также работают с CPLEX).
Границы и разрывы: .lb, .ub, .slack
Суффиксы .lb и .ub в переменной обозначают ее нижнюю и верхнюю границы, в то время как .slack обозначает отличие значения переменной от ее ближайшей границы. Например:
display Buy.lb, Buy, Buy.ub, Buy.slack; : Buy.lb Buy Buy.ub Buy.slack := BEEF 2 2 10 0 CHK 2 10 10 0 FISH 2 2 10 0 HAM 2 2 10 0 MCH 2 2 10 0 MTL 2 6.23596 10 3.76404 SPG 2 5.25843 10 3.25843 TUR 2 2 10 0 ;
Сообщенные границы - это те границы, которые были отправлены решателю. Таким образом, они включают в себя не только границы, указанные в >= и <= фразах объявлений var, но также границы, которые были выведены из ограничений на этапе предварительного решения AMPL. Другие суффиксы позволяют увидеть исходные границы и дополнительные границы, выведенные с помощью presolve. Две одинаковые границы обозначают фиксированную переменную, которая обычно исключается с помощью предварительного вычисления. Таким образом, в модели планирования ограничение Inv[p, 0] = inv0[p] фиксирует начальные запасы:
display{p in PROD} (Inv[p,0].lb,inv0[p],Inv[p,0].ub);
Inv[p,0].lb inv0[p] Inv[p,0].ub :=
bands 10 10 10
coils 0 0 0 ;
В модели производства и транспортировки, ограничение:
sum{i in ORIG} Trans[i,j,p] = demand[j,p]
приводит к тому, что presolve фиксирует три переменные в нуле, потому что demand ["LAN", "plate"] равен нулю:
display {i in ORIG} Trans[i,"LAN","plate"].lb, Trans[i,"LAN","plate"].ub);
:Trans[i,’LAN’,’plate’].lb Trans[i,’LAN’,’plate’].ub :=
CLEV 0 0
GARY 0 0
PITT 0 0 ;
Как видно из этого примера, корректировки presolve для границ могут зависеть от данных, а также от структуры ограничений. Понятия границ и разрывов имеют аналогичную интерпретацию для ограничений модели.
body
Любое ограничение AMPL можно поместить в стандартную форму:
lower bound ≤ body ≤ upper bound
где body является суммой всех элементов, включающих переменные, тогда как lower bound и upper bound зависят только от данных. Суффиксы .lb, .body и .ub дают текущие значения этих трех частей ограничения. Например, в модели диеты имеются следующие ограничения:
subject to Diet_Min {i in MINREQ}: sum {j in FOOD} amt[i,j] * Buy[j] >= n_Min[i];
subject to Diet_Max {i in MAXREQ}: sum {j in FOOD} amt[i,j] * Buy[j] <= n_Max[i];
display Diet_Min.lb, Diet_Min.body, Diet_Min.ub; : Diet_Min.lb Diet_Min.body Diet_Min.ub := A 700 1013.98 Infinity B1 0 605 Infinity B2 0 492.416 Infinity C 700 700 Infinity CAL 16000 16000 Infinity ;
display Diet_Max.lb, Diet_Max.body, Diet_Max.ub; : Diet_Max.lb Diet_Max.body Diet_Max.ub := A -Infinity 1013.98 20000 CAL -Infinity 16000 24000 NA -Infinity 43855.9 50000 ;
Естественно, ограничения <= не имеют нижних границ, а ограничения >= не имеют верхних границ. AMPL использует -Infinity и Infinity вместо числа для обозначения этих случаев. Как нижняя, так и верхняя граница могут быть конечными, если ограничение задано двумя операторами <= или >=. Для ограничения = две границы являются тем же. Суффикс .slack относится к разнице между body и ближайшей границей:
display Diet_Min.slack; Diet_Min.slack [*] := A 313.978 B1 605 B2 492.416 C 0 CAL 0 ;
Для ограничений, которые имеют один оператор <= или >=, разрыв всегда является разницей между выражениями слева и справа от оператора, даже если с обеих сторон есть переменные. Ограничения с нулевым разрывом - это те, которые действительно ограничивают оптимальное решение.
Теневая цена и уменьшенная стоимость
С каждым ограничением в линейной программе связано значение, известное как двойная переменная, предельное значение или теневая цена. В командной среде AMPL двойные значения обозначаются именами ограничений без какого-либо суффикса. Например, коллекция ограничений с именем Demand:
subject to Demand {j in DEST, p in PROD}: sum {i in ORIG} Trans[i,j,p] = demand[j,p];
и таблица двойных значений, связанных с этими ограничениями, может быть просмотрена
display Demand; Demand [*,*] : bands coils plate := DET 201 190.714 199 FRA 209 204 211 FRE 266.2 273.714 285 LAF 201.2 198.714 205 LAN 202 193.714 0 STL 206.2 207.714 216 WIN 200 190.714 198 ;
Решатели возвращают в AMPL оптимальные двойные значения вместе с оптимальными значениями переменных. Здесь у нас есть место только для краткого изложения наиболее распространенной интерпретации двойственных значений. Обширная теория двойственности и применения двойственных переменных может быть прочитана в любом учебнике по линейному программированию.
Для начала рассмотрим ограничение Demand["DET", "band"] выше. Если мы изменим значение параметра demand ["DET", "band"] в этом ограничении, оптимальное значение целевой функции Total_Cost изменится соответственно. Если бы мы построили оптимальное значение Total_Cost по сравнению со всеми возможными значениями demand[“DET”, “bands”], результатом будет «кривая затрат», которая показывает, как общая стоимость меняется в зависимости от спроса на bands в Детройте.
Дополнительные вычисления потребуются для определения всей кривой затрат, но можно узнать что-то об этом из оптимальных двойных значений. После того, как вы решите линейную программу, используя определенное значение demand["DET", "bands"], двойная стоимость для ограничения покажет вам наклон кривой затрат при текущем значении спроса. Например, читая из таблицы выше, мы находим, что наклон кривой при текущем спросе равен 201. Это означает, что общая стоимость производства и доставки увеличивается со скоростью 201 долл. США за каждую дополнительную тонну bands, требуемых в DET, или составляет снижение на 201 доллар за каждое сокращение спроса на одну тонну. В качестве примера неравенства рассмотрим следующее ограничение из той же модели:
subject to Time {i in ORIG}:
sum {p in PROD} (1/rate[i,p]) * Make[i,p] <= avail[i];
Здесь показательно взглянуть на двойные значения вместе со разрывами:
display Time, Time.slack; : Time Time.slack := CLEV -1522.86 0 GARY -3040 0 PITT 0 10.5643 ;
Там, где значение Time положительно, - двойное значение равно нулю. Действительно, значение Time подразумевает, что оптимальное решение не использует все время, доступное в PITT. Следовательно, изменение avail["PITT"] нисколько не влияет на оптимум. С другой стороны, когда значение Time.slack (разрыв) равно нулю, двойная стоимость может иметь большое значение. В случае с GARY это значение составляет 3040, это означает, что общая стоимость увеличивается на 3040 долларов за каждый дополнительный час, доступный в GARY, или уменьшается на 3040 долларов за каждый потерянный час. В общем, если мы построим график оптимальных значений цели в сравнении с постоянным членом ограничения, кривая будет выпуклой кусочно-линейной для минимизации или вогнутой кусочно-линейной (то же самое, но вверх ногами) для максимизации:
В терминах стандартной формы lower bound ≤ body ≤ upper bound, введенной ранее, оптимальные двойственные значения можно рассматривать следующим образом:
- если значение разрыва ограничения положителен, двойное значение равно нулю.
- если значение разрыва равно нулю, тело ограничения должно равняться одной (или обеим) границам, а двойное значение относится к равным границам.
Двойные значения: .rc
В частности, двойное значение представляет собой наклон графика зависимости значения целевой функции от границы, оцениваемой по текущему значению границы. Это эквивалентно скорости изменения целевой функции относительно связанного значения.
Практически идентичный анализ применяется к границам переменной. Роль двойной цены здесь играет так называемая уменьшенная стоимость переменной, которую можно увидеть с помощью суффикса .rc. В качестве примера ниже приведены границы и сниженная стоимость для переменных:
display Buy.lb, Buy, Buy.ub, Buy.rc; : Buy.lb Buy Buy.ub Buy.rc := BEEF 2 2 10 1.73663 CHK 2 10 10 -0.853371 FISH 2 2 10 0.255281 HAM 2 2 10 0.698764 MCH 2 2 10 0.246573 MTL 2 6.23596 10 0 SPG 2 5.25843 10 0 TUR 2 2 10 0.343483 ;
Поскольку значение Buy["MTL"] не соприкасается с границами, его сниженная стоимость равна нулю. Значение Buy["HAM"] лежит на нижней границе, поэтому его уменьшенная стоимость указывает на то, что общая стоимость может увеличиваться примерно на 70 центов за каждую дополнительную единицу HAM. С другой стороны, Buy["CHK"] находится на своей верхней границе, и его отрицательная уменьшенная стоимость указывает на то, что общая стоимость будет уменьшаться примерно на 85 центов за единицу, в случае дальнейшего увеличения границ и роста объема выпуска CHK. Если текущее значение границы лежит прямо в точке, где круто меняется наклон кривой целевой функции (см. рисунок выше), тогда значение целевой функции будет изменяться с одной скоростью по мере увеличения границы, но с другой скоростью при ее уменьшении. В крайнем случае, любая из этих скоростей может быть бесконечной, указывая на то, что линейная программа становится невозможной, если граница увеличивается или уменьшается на любую дополнительную величину. Однако решатель сообщает AMPL только одну оптимальную двойную цену или уменьшенную стоимость, которая может быть скоростью в любом из направлений или некоторой величиной между ними.
Кроме того, в любом случае двойная цена или уменьшенная стоимость могут отражать только один наклон на кусочно-линейной кривой целевой функции. Следовательно, эти величины должны использоваться только в качестве исходного ориентира для чувствительности цели к определенным переменным или границам ограничений.
Если чувствительность очень важна для приложения, можно сделать серию прогонов с различными настройками границ, для быстрого изменения небольшой части данных. (Существуют алгоритмы для нахождения части или всей кусочно-линейной кривой с учетом линейного изменения одной или нескольких границ, но они не поддерживаются в текущей версии AMPL.)
