Объявление целевой функции
Объявление целевой функции включает в себя одно из ключевых слов minimize или maximize. За которым следует имя цели, двоеточие и линейные выражения в ранее определенных наборах, параметрах и переменных. Например:
minimize Total_Cost: sum {j in FOOD} cost[j] * Buy[j];
maximize Total_Profit: sum {p in PROD, t in 1..T}
(sum {a in AREA[p]} revenue[p,a,t] * Sell[p,a,t] -
prodcost[p] * Make[p,t] - invcost[p] * Inv[p,t]);
Наименование целевой функции не играет никакой дальнейшей роли в модели. В командах AMPL имя целевой функции относится к ее значению. После решения экземпляра модели, имя целевой функции можно использовать в арифметических выражениях для расчета дополнительных значений:
display {j in FOOD} 100 * cost[j] * Buy[j] / Total_Cost;
100*cost[j]*Buy[j]/Total_Cost [*] :=
BEEF 14.4845
CHK 4.38762
FISH 3.8794
HAM 24.4792
MCH 16.0089
MTL 16.8559
SPG 15.6862
TUR 4.21822 ;
В данном примере производится расчет удельного веса затрат для каждого продукта в общей стоимости.
Объявление нескольких целевых функций
По умолчанию, каждая линейная программа имеет одну целевую функцию. Однако, модель может содержать более одной декларации целевой функции. Кроме этого, используя индексное выражение после имени целевой функции, можно определить индексированный набор для множества целевых функций. В этих случаях, с помощью команды objective (применяется перед командой solve) можно указать целевую функцию, которая должна быть оптимизирована. Если модель содержит несколько целевых функций, по умолчанию AMPL выбирает для оптимизации первую.
В качестве примера рассмотрим модель диеты:
set NUTR;
set FOOD;
param cost {FOOD} > 0;
param f_min {FOOD} >= 0;
param f_max {j in FOOD} >= f_min[j];
param n_min {NUTR} >= 0;
param n_max {i in NUTR} >= n_min[i];
param amt {NUTR,FOOD} >= 0;
var Buy {j in FOOD} >= f_min[j], <= f_max[j];
minimize Total_Cost: sum {j in FOOD} cost[j] * Buy[j];
subject to Diet {i in NUTR}:
n_min[i] <= sum {j in FOOD} amt[i,j] * Buy[j] <= n_max[i];
data;
set NUTR := A B1 B2 C NA CAL ;
set FOOD := BEEF CHK FISH HAM MCH MTL SPG TUR ;
param: cost f_min f_max :=
BEEF 3.19 2 10
CHK 2.59 2 10
FISH 2.29 2 10
HAM 2.89 2 10
MCH 1.89 2 10
MTL 1.99 2 10
SPG 1.99 2 10
TUR 2.49 2 10 ;
param: n_min n_max := A 700 20000 C 700 20000 B1 700 20000 B2 700 20000 NA 0 40000 CAL 16000 24000 ; |
param amt (tr): A C B1 B2 NA CAL := BEEF 60 20 10 15 938 295 CHK 8 0 20 20 2180 770 FISH 8 10 15 10 945 440 HAM 40 40 35 10 278 430 MCH 15 35 15 15 1182 315 MTL 70 30 15 15 896 400 SPG 25 50 25 15 1329 370 TUR 60 20 15 10 1397 450 ; |
Необходимо найти минимальное значение для натрия, чтобы можно было удовлетворить все ограничения. Для этого можно ввести новую цель, равную общему количеству натрия в рационе:
minimize Total_NA: sum{j in FOOD} amt["NA",j] * Buy[j];
Мы создаем эту задачу только для натрия, потому что по условиям задачи нет оснований минимизировать другие питательные вещества. Можно решить линейную программу для общих затрат, используя правила AMPL для выбора целевой функции (выбирается первая):
model diet.mod;
data diet2a.dat;
display n_max["NA"];
n_max[’NA’] = 50000
minimize Total_NA: sum {j in FOOD} amt["NA",j] * Buy[j];
solve;
MINOS 5.5: optimal solution found.
13 iterations, objective 118.0594032
Решатель сообщает значение минимальной стоимости. Мы можем использовать оператор display, чтобы отобразить значения общего содержания натрия в представленном решении:
display Total_NA; Total_NA = 50000
Далее используя команду objective, можно выбрать в качестве цели минимизацию содержания натрия. Повторная команда solve оптимизирует новую цель. Полученный результат для Total_Cost:
objective Total_Cost; solve; MINOS 5.5: optimal solution found. 1 iterations, objective 48186 display Total_Cost; Total_Cost = 123.627
свидетельствует о том, что содержание натрия можно снизить примерно до 1800 ед. При этом, общая стоимость возрастает примерно на 5,50 долларов. (Здоровые диеты, как правило, дороже, потому что их целью является прежде всего сбалансированность рациона, а не минимизация затрат.)
В качестве другого примера, поэкспериментируем с результатами решения следующей задачи:
model transp.mod; data assign.dat; solve;
CPLEX 8.0.0: optimal solution; objective 28
24 dual simplex iterations (0 in phase I)
option display_1col 1000, omit_zero_rows 1;
option display_eps .000001;
display Total_Cost,{i in ORIG, j in DEST} cost[i,j] * Trans[i,j];
Total_Cost = 28
cost[i,j]*Trans[i,j] :=
Coullard C118 6 Daskin D241 4 Hazen C246 1 Hopp D237 1 Iravani C138 2 Linetsky C250 3 |
Mehrotra D239 2 Nelson C140 4 Smilowitz M233 1 Tamhane C251 3 White M239 1 ;
|
Чтобы сохранить значение целевой функции (28) во время эксперимента, добавим ограничение, которое зафиксирует значение целевой функции:
subject to Stay_Optimal: sum {i in ORIG, j in DEST} cost[i,j] * Trans[i,j] = 28;
cost[i,j] - это рейтинг офиса j, определенный лицом i. Trans[i,j] имеет значение 1, если решатель назначает сотрудника i в офис j, или 0 в противном случае. Таким образом, выражение:
sum{j in DEST} cost[i,j] * Trans[i,j]
Мы используем для объявления новой целевой функции:
minimize Pref_of{i in ORIG}: sum{j in DEST} cost[i,j] * Trans[i,j];
Это утверждение создает для каждого сотрудника i цель Pref_of[i], которая оптимизирует значение его предпочтений i для комнаты, которой i назначен. Затем мы можем выбрать любого человека и оптимизировать рейтинг его предпочтений:
objective Pref_of["Coullard"]; solve; CPLEX 8.0.0: optimal solution; objective 3 3 simplex iterations (0 in phase I)
Для новой формулировки задачи, первоначальное значение цели не изменилась, а значение предпочтения выбранного лица улучшилось. Это произошло, за счет ухудшения результата для других сотрудников:
display Total_Cost, {i in ORIG, j in DEST} cost[i,j] * Trans[i,j];
Total_Cost = 28
cost[i,j]*Trans[i,j] :=
Coullard D241 3 Daskin D237 1 Hazen C246 1 Hopp C251 5 Iravani C138 2 Linetsky C250 3 |
Mehrotra D239 2 Nelson C140 4 Smilowitz M233 1 Tamhane C118 5 White M239 1 ; |
Возможность внесения указанных изменений продиктована наличием нескольких оптимальных решений первоначальной цели общего ранжирования. Решатель произвольно возвращает одно из этих решений. Используя дополнительную целевую функцию в задаче с множеством оптимальных решений, мы можем навязать дополнительные условия всем элементам решения.
Многоцелевое моделирование
В общем, не существует никакого возможного решения, которое минимизирует две целевые функции одновременно. Проблема множественной целевой функции может быть решена в следующих вариантах:
- Оптимизировать взвешенную сумму целей: для двух целей w1 и Например: найти минимум общей целевой функции: w1*(первая целевое выражение) + w2*(второе целевое выражение).
- Оптимизировать первую цель, затем добавить ограничение вида:
(выражение первой цели) <= (оптимальное значение) + (некоторое небольшое отклонение), и оптимизировать вторую цель.
- Определить две разные задачи оптимизации, каждая из которых имеет свою целевую функцию. Решить первую задачу, затем присвоить некоторые оптимальные значения первой задачи соответствующим параметрам второй задачи, а затем решить вторую. При необходимости назначить некоторые оптимальные значения второй задачи соответствующим параметрам первой задачи и повторить оптимизацию.
Мультицелевое моделирование
AMPL не принимает файлы модели (или операторы модели, такие как minimize) внутри цикла for. Вместо этого необходимо создать один файл *.mod, который будет содержат все целевые функции, каждая из которых имеет свое отдельное имя. Затем используя выражение objective, можно изменять цель перед каждым solve. Прикрепленные файлы раскрывают пример. Файл модели определяет следующие цели:
minimize total_number: sum {j in FOOD} Buy[j];
minimize total_cost {s in STORE}: sum {j in FOOD} cost[s,j] * Buy[j];
Следующий сценарий позволяет изменять целевую функцию для эти задачи:
model dietobj.mod;
data dietobj.dat;
objective total_number;
solve;
print "TOTAL NUMBER"; display Buy;
for {s in STORE} {
objective total_cost[s];
solve;
print "STORE " & s; display Buy;
}
Там, где имеется индексированная коллекция целей, подобно minimal total_cost {s in STORE}, можно использовать цикл for для прохода по ним, как показано в примере выше.
Однако нельзя использовать цикл for для итерации по целям, которые определены в отдельных утверждениях minimize или maximize. Вот почему целевая функция, заданная параметром minimal total_cost, должна обрабатываться отдельно.
Действия с целевыми функциями
Запись наилучшего решения в результате серии проходов
Следующий код запоминает наилучшее значение целевой функции в результате серии проходов:
param best_obj default -1000000;
param best_c;
param best_w;
if obj > best_obj then {let best_obj := obj;
let best_c := c;
let best_w := w;
print " new best obj:", obj, c, w;}
Вычисление целевой функции на основании комбинаций входных параметров
model Counter.mod;
data Counter.dat;
param value {1..C_Max, 0..w_Max};
for {cval in 1..C_Max, wval in 0..w_Max} {
let c:= cval;
let w:= wval;
solve;
let value[cval,wval] := obj;
}
display value;
