- •1.Основные понятия и этапы са
- •2. Операция и ее составляющие. Этапы исо
- •Этапы операционного проекта
- •Виды математических моделей ио, примеры.
- •4. Состязательные задачи. Решение игры 2-х лиц
- •7. Примеры задач лп: игра 2-х лиц как задача лп, транспортная задача
- •В общем случае модель задачи лп имеет вид
- •Сбалансированная транспортная задача
- •8 Формы представления задач лп и способы приведения к ним
- •1. Каноническая форма задач лп
- •2. Стандартная форма задачи лп
- •9. Основные понятия лп. Свойства задач лп
- •10. Геометрия задач лп, базисные решения, вырожденность.
- •4.7. Выделение вершин допустимого множества
- •11. Понятие базиса. Переход от одного базисного решения к другому
- •12. Признак оптимальности. Определение начального базисного решения.
- •13. Алгоритм симплекс-метода
- •14. Двойственность задач лп
- •4.11.1. Запись двойственной задачи в симметричном случае
- •4.11.3. Запись двойственной задачи в общем случае
- •15.Экономическая интерпретация двойственной задачи
- •16. Теоремы двойственности
- •17. Двойственный и модифицированный симплекс-метод Модифицированный алгоритм
- •18. Параметрический анализ. Параметрирование вектора ограничениий
- •Параметрирование вектора ограничениий
- •19. Параметрирование коэффициентов линейной формы
- •20. Модели транспортных задач и их характеристика, условия разрешимости.
- •Простейшая транспортная задача (т-задача)
- •Транспортная задача с ограниченными пропускными способностями (Td - задача)
- •Транспортные задачи по критерию времени
- •21. Построение начального плана перевозок т-задачи
- •5.2.1. Построение начального плана перевозок
- •Правило северо-западного угла
- •Правило минимального элемента.
- •22.Обоснование метода потенциалов
- •5.2.3. Признак оптимальности
- •23. Алгоритм метода потенциалов.
- •24. Двойственная пара транспортных задач
- •25. Метод потенциалов для Td-задачи
- •5.5. Решение задачи по критерию времени
- •26. Приведение открытой транспортной задачи к закрытой
- •27. Транспортные задачи в сетевой постановке (транспортные сети)
- •28. Задача о максимальном потоке
- •29. Метод декомпозиции Данцига - Вулфа
- •30. Решение транспортной задачи методом Данцига-Вулфа (метод декомпозиции тз)
- •32. Целочисленное программирование
- •7.1. Проблема целочисленности
- •33. Метод отсечений
- •Пример 7.1. Выведем условие отсечения для задачи
- •34. Метод ветвей и границ
- •35. Аддитивный алгоритм
- •36. Нелинейное программирование
- •Теорема
- •37. Квадратичное программирование
- •38. Сепарабельное программирование (сп) и дробно-линейное программирование
- •8.5. Задачи дробно-линейного программирования
- •39. Метод покоординатного спуска и Хука-Дживса Метод первого порядка
- •8.8. Многомерный поиск безусловного минимума
- •8.8.1. Метод Гаусса-Зейделя (покоординатного спуска)
- •Метод Хука-Дживса (метод конфигураций) Метод первого порядка
- •Метод Хука-Дживса (метод конфигураций)
- •40. Симплексный метод поиска
- •41. Градиентные методы
- •Методы сопряженных направлений
- •43. Методы случайного поиска
- •Алгоритм с возвратом при неудачном шаге
- •Алгоритм с обратным шагом
- •Алгоритм наилучшей пробы
- •Алгоритм статистического градиента
- •44. Метод проектирования градиента
- •Метод проектирования градиента
- •45. Генетические алгоритмы
- •46. Метод штрафных функций и барьерных функций
- •Метод барьерных функций
- •47. Динамическое программирование
- •48. Распределение одного вида ресурса
- •49. Дп: задачи о кратчайшем пути и с мультипликативным критерием
- •Задача с мультипликативным критерием.
- •52. Многомерные задачи динамического программирования
- •53. Снижение размерности с помощью множителей Лагранжа
- •56. Многокритериальные задачи: постановка, проблемы, осн. Понятия, методы
- •Многокритериальная задача математического программирования
- •Где искать оптимальное решение
- •Определения
- •Условия оптимальности
- •57. Многокритериальные задачи: функция полезности, лексикографический анализ
- •Методы первой группы
- •Функция полезности
- •Решение на основе лексикографического упорядочения критериев
- •58. Методы главного критерия, свертки, идеальной точки, целевого прогр. Метод главного критерия
- •Линейная свертка
- •Максиминная свертка
- •Метод идеальной точки
- •Целевое программирование (цп)
- •59. Диалоговые методы решения задач по многим критериям
- •Метод уступок
- •Интерактивное компромиссное программирование
- •Построить таблицу
57. Многокритериальные задачи: функция полезности, лексикографический анализ
Как видно из предыдущих разделов, математические методы оптимизации позволяют находить эффективные решения. Однако из-за несравнимости эффективных решений не удаётся решить задачу со многими критериями до конца без привлечения ЛПР. Исходя из своих представлений об оптимальности решения ЛПР в конечном итоге отдаёт предпочтение одной из множества возможных альтернатив.
В специальной литературе предложены различные способы вовлечения ЛПР в процесс принятия решений. В зависимости от того, на какой стадии процесса выявляются и используются предпочтения ЛПР, можно выделить три группы многокритериальных методов принятия решений:
основаны на том, что ЛПР может выразить свои предпочтения до начала процесса многокритериальной оптимизации;
интерактивные (диалоговые) методы;
методы построения множества эффективных решений с последующим представлением его ЛПР.
В методах первой группы используются различные способы свёртки критериев, лексикографическое упорядочение критериев, установление желаемых уровней критериев и др. Вторая группа методов основана на непосредственном участии ЛПР в процессе оптимизации, когда на каждой итерации компьютер предлагает решения, а ЛПР их оценивает, и с учётом этих оценок компьютер ищет новые решения. Методы третьей группы отличаются друг от друга различными способами построения и представления множества эффективных решений.
Прежде чем перейти к рассмотрению конкретных методов, сделаем одно замечание. На практике далеко не всегда принимаемое решение должно быть эффективным, так как оно соответствует (по определению) предельным возможностям системы. Например, желание иметь некоторые резервы может привести к выбору решения, которое не будет принадлежать множеству Парето. Однако и такой выбор должен основываться на знании эффективных решений с тем, чтобы правильно оценить границы возможного, а значит и сами резервы.
Методы первой группы
ЛПР может выразить свои предпочтения в различной форме. Это зависит от особенностей самого ЛПР, новизны задачи, типа и числа критериев и других факторов. Поэтому методы данной группы отличаются тем, что используют разные представления предпочтений и способы их формализации. Однако все они в конечном итоге сводят многокритериальную задачу к одной или ряду задач с одним (иногда обобщенным) критерием.
Функция полезности
В XIX веке экономисты высказали предположение о существовании у каждого индивидуума определённого количественного измерителя счастья или полезности – “пользометра”. Единицы измерения этого прибора назвали “утилями” (от английского utility – полезность ). Согласно этой модели потребительского поведения каждый потребитель выбирает так товары и услуги, чтобы максимизировать свою полезность в пределах средств, которыми он располагает. Эта идея перенесена на многокритериальные задачи и интенсивно разрабатывается в теории полезности, ставшей самостоятельным направлением прикладной математики.
Применительно к многокритериальной задаче в качестве товаров и услуг выступают критерии, а в качестве потребителя – ЛПР. При этом предполагается существование на множестве значений критериев y1,y2,….,ym скалярной оценки предпочтений ЛПР, называемой полезностью.
Приведём строгое определение этого понятия. Функция U, которая каждой точке Y критериального пространства ставит в соответствие действительное число U(Y),называется функцией полезности (ценности) ЛПР, если
Y~Y"U(Y')=U(Y"),
Y'Y"U(Y')>U(Y").
Таким образом, функция полезности представляет собой математическую модель предпочтений ЛПР. Если функция полезности известна, то многокритериальная задача сводится к стандартной задаче оптимизации: найти вектор XD, максимизирующий U[Y(X)]. Множество точек критериального пространства, одинаковых по предпочтительности (для которых U(Y)=Const), образует гиперповерхность равного уровня функции полезности. Гиперповерхности равного уровня U(Y) называются кривыми безразличия, а семейство всех кривых безразличия – картой безразличия. Такая терминология связана с тем, что для любых двух альтернатив Y' и Y", лежащих на одной кривой безразличия, U(Y')=U(Y"), т.е. ЛПР всё равно, достигнет он Y' или Y". Пример карты безразличия некоторой функции полезности и нахождение по ней оптимального решения показаны на рис. 10.4.
Очевидно, что наибольшие затруднения при практическом применении рассматриваемого подхода вызывает построение функции полезности, адекватно отражающей предпочтения ЛПР.
Ч
G
В благоприятных случаях удается описывать предпочтения ЛПР функцией полезности, имеющей сравнительно простой вид:
U(y1,y2,...,ym)=F[U1(y1),U2(y2),...,Um(ym)], (10.7)
т.е. многомерная функция определяется через одномерные функции полезности значений одного отдельно взятого критерия. Типичные примеры таких функций для m=2:
U(Y)=C1y1+ С2у2, С1>0, С2>0,
, >0, >0.
Формализация структуры предпочтений основана на исследовании возможности взаимной компенсации значений различных критериев. Это проблема замещения по полезности. Возможные замещения на наборе критериев может дать только ЛПР, а выявить их у ЛПР и формально описать - задача аналитика. Далее будем предполагать, что критерии независимы по предпочтению (см. раздел 10.1.3), и рассмотрим простейшие случаи построения U(Y) для m=2.
Предельный коэффициент замещения критерия y1 на критерий у2 в точке ( , ) равен , если ЛПР согласен уступить единиц критерия y1 за единиц критерия у2, где - достаточно малая величина (строго говоря, при 0). В общем случае предельные коэффициенты замещения зависят от значений y1 и у2. Возвращаясь к рис.10.4 нетрудно понять, что предельный коэффициент есть тангенс угла наклона касательной к кривой безразличия в точке ( , ), взятый с обратным знаком. Отсюда ясно, что определение коэффициентов замещения дает представление о карте безразличия, а следовательно, и о виде функции полезности.
Если коэффициент замещения не зависит от значений y1 и у2, то это означает, что кривые безразличия – прямые, имеющие вид
y1+ y2=Const,
а предпочтения ЛПР могут быть представлены функцией
U(Y)=y1+ y2. (10.8)
Если предельный коэффициент замещения зависит от значения у2, но не зависит от y1, то подходящей составной функцией полезности может быть
U(Y)=y1+ U2(y2). (10.9)
В озможный путь получения U2(y2) состоит в следующем. Примем произвольно U2( )=0, что дает точку отсчета значений U2. Тогда U2( ) есть сумма в единицах y1, которую ЛПР согласен "заплатить" за переход от к . Выявив у ЛПР эти суммы для ряда значений у2, получим график функции U2(y2) как, например, на рис.10.5.
Карта безразличия, соответствующая структуре предпочтений (10.9), имеет вид семейства кривых, которые получаются простым сдвигом по горизонтали (по оси у1) одной из них. Аналогичный подход применяется и в случае, когда зависит от y1, но не зависит от у2.
Из ситуаций, когда коэффициент замещения зависит от значений обоих критериев, рассмотрим самую простую: структура предпочтений ЛПР аддитивна. Обратимся к рис 10.6. Если вместо знака вопроса (?) ЛПР поставит d, т.е. он согласен заплатить d единиц у1 за увеличение у2 на с в точке D и это остается в силе при любых значениях а, b, с и d и в любых точках А, В, С и D, образующих прямоугольник, то имеет место условие соответственных замещений.
Доказано, что структура предпочтений аддитивна и, следовательно, описывается функцией полезности вида
U(Y)=U1(y1)+ U2(y2) (10.10)
тогда и только тогда, когда выполняется условие соответственных замещений.
Одна из процедур построения функции (10.10), которую рассмотрим ниже, использует эквивалентность замещений в разных диапазонах одного из критериев. Приведем необходимые определения. Пара ( ) эквивалентна по разности полезности паре ( ), где < и < , если для любого исходного значения критерия у2 ЛПР согласен "заплатить" одно и то же количество единиц у2 за увеличение y1 как от до , так и от до . Средней по полезности точкой интервала [ ] значений критерия yi называется точка, которая образует эквивалентные по разности полезности пары [ ] и [ ]. Заметим, что из условия соответственных замещений следует независимость значения средней точки для данного интервала y1 от значений критерия у2, хотя "плата" за изменение уi (в единицах у2) будет зависеть от уровня у2.
Для построения функции полезности предварительно устанавливаем область возможных значений критериев: . Полагая, что структура предпочтений ЛПР аддитивна (на основе соответствующих предварительных исследований), функцию полезности представим в виде
U(y1,y2)= 1U1(y1)+ 2U2(y2), (10.11)
где
Ui( )=0, Ui( )=1, (10.12)
>0, 2>0 и 1+ 2=1. (10.13)
В процедуре отыскания U в виде (10.11), приводимой ниже, одинаковость пар и значения средних точек определяет ЛПР в диалоге с аналитиком.
I.Строим U1 в следующей последовательности:
-находим среднюю по полезности точку у интервала [ ] и полагаем U1(y )=0,5;
-находим среднюю по полезности точку у интервала [у , ] и полагаем U1(y )=0.75;
-находим среднюю по полезности точку у интервала [ ] и принимаем U1(y )=0,25;
-проверяем согласованность результатов: является ли у средней по полезности точкой интервала [у ,у ]? Если нет, то придется корректировать эти точки до достижения согласованности .
-по пяти определенным точкам (или большему числу, если продолжить дробление интервалов) строится график функции U1(y1).
2. Таким же образом находим U2(у2).
3. Определяем коэффициенты шкалирования и 2. Для этого выбираем любые две одинаковые по предпочтительности пары (y1,y2). Пусть, например, это пары ( ) и ( ). Тогда
U( )=U( )
или
. (10.14)
Значения U1 и U2 в точках и определяются по построенным графикам. Добавив к (10.14) равенство (10.13), находим значения и .
Соответствие полученной функции полезности структуре предпочтений ЛПР можно дополнительно проверить, предложив ему несколько пар значений критериев (отличных от и ) с одним значением U. Если ЛПР сочтет их примерно одинаковыми по предпочтительности, то построенная функция приемлема. В противном случае следует повторить 3-й этап процедуры с тем, чтобы уточнить значения и (их можно получить более надежно усреднением по нескольким парам с равной предпочтительностью).
С увеличением размерности критериального пространства трудоемкость построения функции полезности даже в аддитивном виде резко возрастает. А при более сложной структуре предпочтений ЛПР отыскание адекватной U(Y) становится весьма проблематичным.
Несмотря на то что имеется целый ряд хорошо разработанных процедур построения функции полезности (например, Р.Кини и Х.Райфа) рассмотренный подход к решению многокритериальных задач находит ограниченное применение. И прежде всего это связано с необходимостью длительной и напряженной работы с ЛПР. А как известно, руководители - народ занятой, да и далеко не все из них могут высказывать непротиворечивые суждения. Проблема многократно усложняется в ситуациях группового принятия решений. В то же время следует отметить главное достоинство метода: функция полезности наиболее полно и адекватно отражает систему ценностей ЛПР и позволяет относительно просто находить решение, наиболее предпочтительное (и в этом смысле оптимальное) для ЛПР с помощью одной стандартной задачи оптимизации.