Интерактивное компромиссное программирование

Так называется метод, использующий для поиска удовлетворящего ЛПР компромиссного решения линейную свертку. При этом от ЛПР не требуется назначать веса, ему лишь нужно на каждой итерации выбрать одно решение из (m +1)-го предлагаемых, после чего веса вычисляются программно.

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

, (10.24)

где - максимальное и минимальное значения -го критерия на допустимом множестве D. Как следует из (10.24), может изменяться от 0 до 1. Очевидно, что если - линейная функция, то и тоже линейная.

Теперь паретовские (эффективные) решения можно находить, максимизируя свертку

(10.25)

при условии Х D.

Одним из существенных недостатков ряда интерактивных методов является использование параметров, численные значения которых должен указывать ЛПР. В рассматриваемом методе эта проблема исключается, так как веса в (10.25) определяются не ЛПР, а специальной процедурой, обеспечивающей вычисление на каждой итерации значений весов, оптимальных в максиминном смысле. Процедура основана на игровом подходе, а именно, на формализации и решении игры двух лиц с нулевой суммой. В качестве стратегий первого игрока рассматриваются целевые функции, второго - решения многокритериальной задачи, полученные к данному шагу и не забракованные ЛПР. Платежом на каждой паре стратегий является степень близости -й целевой функции на -м решении к своему максимальному значению . Тогда вероятности применения стратегий первым игроком и будут иметь смысл весов целевых функций, входящих в свертку (10.25).

В целом процесс поиска компромиссного решения рассмат­риваемым методом можно представить следующим образом. Процедура начинается с решения 2 m обычных задач математического программирования для нахождения максимальных и минимальных значений m целевых функций. По ним вычисляют степень близости каждого решения к максимально возможному значению каждой целевой функции. Приняв их за платежи игры 2-х лиц размерности m_* m и решив игровую задачу, получают текущие веса целевых функций. Последние используют для нахождения (m +1)-го решения. Для полученного решения также вычисляются степени близости по всем критериям. Теперь вместе с предыдущими m решениями новое решение предъявляют ЛПР. Его спрашивают, предпочитает ли он одно из этих решений всем другим. Если да, то это решение принимается за окончательное и процесс заканчивается. В противном случае ЛПР просят выделить из предъявленных ему решений наименее предпочитаемое. Это решение исключается, а из оставшихся m решений формируется и решается очередная игровая задача. Далее таким же способом, как описано выше, находят новое альтернативное компромиссное решение и предъявляют его вместе с m уже имеющимися. Итеративный процесс продолжается до тех пор, пока ЛПР не выявит предпочитаемое им решение.

Рассмотренная процедура реализуется следующим алгоритмом.

Шаг 0. Определить и , для чего решить задачи

а)

при условии Х D. Очевидно, что получаемые решения () не что иное, как идеальные решения.

б)

при условии X D. В противоположность предыдущим решения () называют антиидеальными.

Шаг 1. Взять решения в качестве первоначальных решений и вычислить степени близости по формуле (10.24).

Построить таблицу

	X^1	X^2	…	X^m
f 1			…
f 2			…
…	…	…	…	…
fm			…

где - степень близости j -ro решения к максимальному значению i -й целевой функции.

Шаг 2. Решить следующую игровую задачу одним из методов линейного программирования.

при условиях

...

Шаг 3. Образовать новую функции свертки, используя оптимальные веса, найденные на шаге 2, и решить следующую задачу максимизации этой функции для получения нового альтернативного компромиссного решения .

при условии X D.

Шаг 4. Вычислить значения степеней близости нового решения к максимально возможным значениям целевых функций, . Добавить колонку с этими значениями к таблице, построенной на шаге 1.

Шаг 5. Представить ЛПР новую таблицу и спросить, предпочитает ли он строго одно решение всем другим m-решениям. Если да, то идти на шаг 6. Иначе просить ЛПР отметить наименее предпочитаемое решение. Заменить его новым решением, найденным на шаге 4, и вернуться на шаг 2.

Шаг 6. Останов.

Пример 10.7. Применим этот алгоритм к задаче из примера 10.5.

Шаг 0. a)

при условии X D,

где D определяется системой

x ₁+ x ₂ 8,

- x ₁+ x ₂ 2,

0 x ₁ 6, 0 x 2 4.

Решение: =(0,2), =2.

f ₂(X) = 4 x ₁- x ₂

при условии X D.

Решение: =(6,0), =24.

б) f ₁(X ) =-2 x ₁+ x ₂

при условии X D.

Решение: =(6,0), =-12.

= 4 x ₁- x ₂ min

при условии X D.

Решение: =(0.2). =-2.

Шаг 1. Решения и принимаем за первоначальные эффективные решения X¹ и X². Составляем таблицу степеней близости

	X ^1	X ^2
f 1
f 2

 

Шаг 2. Решаем задачу линейного программирования:

при условиях

,

,

.

Решение: =0.5, =0.5.

Шаг 3. Составляем новую функцию свертки

Решаем следующую задачу линейного программирования для нахождения нового компромиссного решения:

при условии X D.

Решение: Х³=(4,4), f ₁(Х³)=-4, f ₂(X³)=l2. На рис.10.17 это точка С.

Шаг 4. Вычисляем степени близости полученного решения

,

и показываем ЛПР три эффективных решения:

	X^1	X^2	X^3
f 1			0.571
f 2			0.538

 

Шаг 5. Предположим, что ЛПР не устраивает ни одно из этих решений, а наименее предпочтительным он считает решение X¹. Тогда это решение заменяем решением X³ и возвращаемся на шаг 2.

Вторая итерация

Шаг 2. Решаем следующую задачу для определения новых весов:

d ⁴(X) => max

при условиях

0.571 + 0.538 d ⁴,

₂ d ⁴,

Оптимальные значения: =0.447, =0.553.

Шаг 3. Решаем задачу с этими весами:

d ⁴(X) = 0.447 d ₁(X) + 0.553 d ₂(Х)=

= ( 2 х ₁ + x ₂ + 40 )=> max

при условии X D.

Решение: Х⁴=(6.2), f ₁(X⁴)=-10, f ₂(X⁴)=22. На рис.10.17 это вершина E множества достижимости.

Шаг 4. Вычисляем степени близости нового решения

=0.143, =0.923

и предъявляем его ЛПР вместе с оставшимися:

	X^3	X^2	X^4
f 1	0.571		0.143
f 2	0.538		0.923

 

Шаг 5. Предположим, что ЛПР предпочитает новое решение всем другим. Идем на шаг 6.

Шаг 6. Останов. Наилучшее компромиссное решение нашей задачи:

Х =(6.2), f = (-10,22), d = (0.143,0.923).

Отметим некоторые особенности рассмотренного метода.

При его применении необходимо иметь в виду, что в соответствии с теоремой 5 максимизация линейной свертки (10.25) гарантирует получение эффективного решения только в случае положительности всех . Наличие нулевых значений весов может приводить к слабо эффективным решениям.

Из анализа процедуры поиска компромиссного решения следует, что область принятия решений сужается после каждой итерации алгоритма. При этом можно ожидать хорошей сходимости, так как каждое новое решение, предъявляемое ЛПР, является наиболее вероятным среди уже имеющихся, что обусловлено максиминным выбором весов.

Очевидным достоинством метода является использование естественного для ЛПР способа выражения своих предпочтений. Здесь отсутствуют какие-либо эвристические параметры (к ним относят параметры, значения которых должен назначать ЛПР).

Если модель исходной многокритериальной задачи линейна, то вся вычислительная часть интерактивного метода может быть реализована с помощью стандартных пакетов линейного программирования, что означает возможность решения задач большой размерности. Подзадача определения оптимальных весов (шаг 2) остается линейной при любом виде исходной модели.

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