183814 (629937), страница 4

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 4)

При разработке методов решения векторных задач приходится решать ряд специфических проблем.

Проблема нормализации возникает в связи с тем, что локальные критерии имеют, как правило, различные единицы и масштабы измерения, и это делает невозможным их непосредственное сравнение. Операция приведения критериев к единому масштабу и безразмерному виду носит название нормирования. Наиболее распространенными способами нормирования является замена абсолютных значений критериев их безразмерными относительными величинами

fr(X) = fr(X) ,

f*r

или относительными значениями отклонений от оптимальных значений критериев f*r

fr(X) = f*r - fr(X) ,

f*r

Проблема выбора принципа оптимальности связана с определением свойств оптимального решения и решением вопроса - в каком смысле оптимальное решение превосходит все остальные.

Проблема учета приоритета критериев встает, если локальные критерии имеют различную значимость. Необходимо найти математическое определение приоритета и степень его влияния на решение задачи.

Проблема вычисления оптимума возникает, если традиционные вычислительные схемы и алгоритмы непригодны для решения задач векторной оптимизации.

Решение перечисленных проблем идет в нескольких направлениях. Основные направления:

Методы, основанные на свертывании критериев в единый;

Методы, использующие ограничения на критерии;

Методы целевого программирования;

Методы, основанные на отыскании компромиссного решения;

Методы, в основе которых лежат человеко-машинные процедуры принятия решений (интерактивное программирование).

В методах, основанных на свертывании критериев, из локальных критериев формируется один. Наиболее распространенным является метода линейной комбинации частных критериев. Пусть задан вектор весовых коэффициентов критериев = 1,…,r, характеризующих важность соответствующего критерия, r = 1, r 0 (r = 1,K). Линейная скаляризованная функция представляет собой сумму частных критериев, умноженных на весовые коэффициенты. Задача математического программирования становится однокритериальной и имеет вид

F = rfr(X) (max),

qi(X) bi (I = 1,M),

X 0.

Критерии в свертке могут быть нормированы. Решение, полученное в результате оптимизации скаляризованного критерия эффективно.

К недостаткам метода можно отнести то, что малым приращениям коэффициентов соответствуют большие приращения функции, т.е. решение задачи неустойчиво, а также необходимость определения весовых коэффициентов.

Направление методов, использующих ограничения на критерии включает два подхода:

1. метод ведущего критерия;

2. методы последовательного применения критериев (метод последовательных уступок, метод ограничений).

В методе ведущего критерия все целевые функции кроме одной переводятся в разряд ограничений. Пусть = (2, 3,…, к-1) – вектор, компоненты которого представляют собой нижние границы соответствующих критериев. Задача будет иметь вид

F = f1 (max)

fr r (r = 2,K),

qi (X) bi (I = 1,M),

X 0.

Полученное этим методом решение может не быть эффективным, поэтому необходимо проверить его принадлежность области компромиссов.

Метод ведущего критерия применяется в таких задачах, как минимизация полных затрат при условии выполнения плана по производству различных видов продукции, максимизация выпуска комплектных наборов при ограничении на потребляемые ресурсы.

Алгоритм метода последовательных уступок:

1. Критерии нумеруются в порядке убывания важности.

2. Определяется значение f*1. Лицом, принимающим решение, устанавливается величина уступки 1 по этому критерию.

3. Решается задача по критерию f2 с дополнительным ограничением f1(X) f*1 - 1.

Далее пункты 2 и 3 повторяются для критерия f2,…, fk.

Полученное решение не всегда принадлежит области компромиссов.

При решении задач методами целевого программирования предполагается приближение значения каждого критерия к определенной величине fr, т.е. достижение определенной цели. В самом общем виде задача целевого программирования формулируется как задача минимизации сумм отклонений целевых функций от целевых значений с нормированными весами.

d(F(X), F) = ( w_R f_R (X) - f _R ^p) (min),

где F = f₁,...., f_R - вектор целевых значений,

W = w₁,..., w_R - вектор весов, обычно w_R = 1_, w_R 0

(r = 1, K), значения p находятся в пределах 1 p ,

d(.) – расстояние (мера отклонения) между F(X) и F.

Во многих случаях применения целевого программирования полагают p = 1. Например, в линейном целевом программировании функции f_R (X) (r=1, K) и q_i (X) (i = 1,M) линейны и нет целочисленных переменных.

В задачах лексикографического программирования критерии строго упорядочены по важности, так что при сравнении пары решений в первую очередь используется критерий f₁ и лучшим считается то решение, для которого значение этого критерия больше, если значения первого критерия для обоих решений оказываются равными, то применяется критерий f₂ и предпочтение отдается тому решению, для которого значение f₂ больше, ели и второй критерий не позволяет определить лучшее решение, то привлекается f₃ и т.д. Учет информации о важности критериев осуществляется путем поэтапного решения задачи минимизации отклонений критериев от целевых значений. Часто в лексикографическом программировании F = F, p = 1 .

Точка F обычно не принадлежит области допустимых значений и поэтому ее иногда называют идеальной или утопической точкой. В некоторых методах целевого программирования допускается задание утопического множества, как пример при построении архимедовой задачи.

Характеристики

Список файлов курсовой работы