Информационная система поддержки принятия решений в условиях многокритериальной оптимизации

• Введение
• Основные понятия теории принятия решений
• Формализация задач принятия решений
• Однокритериальные задачи в условиях определенности
• Многокритериальные задачи в условиях определенности
• 1.Методы оценки многокритериальных альтернатив
• Прямые методы
• Аксиоматические методы
• Методы компенсации
• Человеко-машинные процедуры принятия решений
• 2. Постановка задачи об упаковке
• 3. Функция полезности.
• Методы построения аддитивной функции полезности
• 4. Слои Парето
• 5. Программа
• Структура
• Пример решения задачи
• Заключение
• Список использованных источников
• Приложения

Основные понятия теории принятия решений

Термин " Системный анализ" будем понимать как совокупность методов, ориентированных на исследование сложных систем - технических, экономических, экологических. программных и т.д.

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

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

Под принятием решения будем понимать выбор одного или нескольких вариантов решения задачи из некоторого исходного множества вариантов (альтернатив). Последствием принятия решения назовем событие (исход), на возможность появления которого влияет данное решение. Чем является этот исход — зависит от ситуации, в которой это решение принимается. В большинстве случаев это будет максимальный выход продукта при минимальных затратах на его производство, но это всё же далеко не общий случай, и от него тоже можно (и нужно) абстрагироваться: это могут быть как прямые энергозатраты, так и затраты денег, времени и вообще всего, что является ресурсом с точки зрения конкретной предметной области. То же самое касается и продукта: это может быть как материальная ценность, так и нематериальная. Например, принятие определённого решения, результатом которого станет повышение процента сгорания топлива в двигателе разрабатываемой конструкции.

Система предпочтений — совокупность правил, устанавливающих приоритеты при выборе из множества альтернатив.

принятие решение аддитивная функция

Решение — подмножество множества альтернатив, образованное на основе системы предпочтений.

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

На принятие решений в той или иной степени влияют активные группы людей, имеющих общие интересы по отношению к проблеме, требующей решение — эксперты в предметной области. К ним обычно обращаются за оценками, за прогнозами исходов тех или иных решений. Эксперты высказывают свое субъективное мнение. Если эксперт беспристрастен и является профессионалом, его оценки близки к объективным.

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

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

построение формальных моделей ситуации выбора;

анализ неопределенностей;

формирование целей принятия решений.

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

Формализация задач принятия решений

Под принятием решения будем понимать выбор подмножества альтернатив из исходного их множества. При этом не стоит забывать, что множество может быть пустым, содержать один или больше одного элемента. Выбор той или иной альтернативы из исходного множества должен быть так или иначе обусловлен. Значимые критерии альтернатив устанавливаются лицом, принимающим решения (в дальнейшем ЛПР) и, при отображении альтернативы в вектор, будут представлять из себя скаляры, входящие в его состав. При недостатке информации о критериях выбора, который ему предстоит сделать, ЛПР может обратиться к экспертам в текущей предметной области. Для возможности выбора той или иной альтернативы из исходного множества у ЛПР должна быть, во-первых, возможность сравнивать их между собой, и, во-вторых, возможность оценивать эти альтернативы. В общем случае задача принятия решения представима кортежем следующего вида: X, I, S, F, где X — исходное множество альтернатив; I — уровень информации; S — метод поиска (метод) решения; F — множество критериев оценки альтернатив.

Для любых двух множеств X и Y (различных или нет) существует единственное множество, состоящее из всех упорядоченных пар (x, y), x X, y Y. Обозначается X Y и называется декартовым произведением (или просто произведением) X и Y. Поскольку ЛПР попарно сравнивает элементы одного и того же множества, нас интересует произведение множества X на само себя — X X, и его мы будем обозначать как X². Бинарным отношением на множестве X будем называть произвольное подмножество R множества X², т. е. R А^{2 (}R X X).

Если задано отношение R X² и (x_i, x_j) R ((x_i, x_j) R x_i R x_j), x_i X, x_j X, то графически:

Получившиеся фигуры называют ориентированным графом, или графом, узлы — вершинами графа. Задание бинарного отношения интерпретируется как введение некоторой системы предпочтений, т. е. если (x_i, x_j) R, x_i X, x_j X, то подразумевается, что в определенном смысле элемент x_i «лучше» или не «хуже» элемента x_j.

Рассмотрим некоторые свойства бинарного отношения.

1. Отношение называется рефлексивным, если (x_i, x_i) R x_i X.

2. Отношение называется антирефлексивным, если из x_i R x_j x_i x_j.

3. Отношение называется связным, если x_i, x_j X (x_i, x_j) R или (x_j, x_i) R.

4. Отношение называется симметричным, если x_i, x_j X из x_i R x_j x_j R x_i.

5. Отношение называется асимметричным, если из двух соотношений x_i R x_j и x_j R x_i, по меньшей мере одно не выполняется. Если отношение ассиметрично, то оно и антирефлексивно.

6. Отношение называется антисимметричным, если x_i, x_j X из x_i R x_j и x_j R x_i x_i = x_j.

7. Отношение называется транзитивным, если x_i, x_j, x_k X таких, что (x_i, x_j) R и (x_j, x_k) R (x_i, x_k) R.

8. Отношение R называется квазипорядком, если R рефлексивно и транзитивно.

9. Отношение R называется линейным квазипорядком, если R рефлексивно, транзитивно и связно.

10. Отношение P называется отношением строгого предпочтения, если оно антисимметрично и связно.

11. Отношение I называется отношением безразличия, если оно симметрично и транзитивно.

Граф рефлексивного отношения содержит петли у всех вершин, антирефлексивного — не содержит ни одной петли. Граф связного отношения содержит дуги между любыми двумя вершинами графа. Для симметричного отношения вершины графа связаны парами противоположно направленных дуг. В графе асимметричного отношения петли отсутствуют, а вершины могут быть связаны только одной направленной дугой. Граф антисимметричного отношения может иметь петли, но связь между вершинами отображается только одной направленной дугой.

На практике не всегда требуется максимизация или минимизация того или иного критерия. Может оказаться, что требуется удержать его определённое значение. Для удобства в этом случае используют так называемую функцию полезности (далее ФП). Под этим абстрактным понятием подразумевается некая функция, значение которой отражает приближение её аргументов (в качестве аргумента выступает некое решение, выраженное в виде вектора критериев) к оптимальному значению. В случае оптимизации по одному критерию, ФП может принимать в качестве аргумента скалярное значение вместо одномерного вектора. В ФП локализована логика, численно выражающая разницу между текущим и требуемым значением. Наиболее распространенным подходом к решению задач ПР является построение ФП U (x) со следующими свойствами: U (x_i) > U (x_j), если (x_i, x_j) P; U (x_i) = U (x_j), если (x_i, x_j) I. Если ФП существует, то она определяет линейный квазипорядок на множестве X. Верно и обратное, если на множестве X построен линейный квазипорядок, то возможно построение ФП (например, путем сопоставления альтернативам множества X, расположенных в порядке убывания их предпочтительности натуральных чисел в возрастающем порядке; одинаково предпочтительным альтернативам будут присвоены одинаковые числа).

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

Если найдено решение, для которого не существует лучшей альтернативы, то такое решение называется парето-оптимальным. Заметим, что парето-оптимальных решений может быть больше одного. Они образуют множество Парето, являющееся, соответственно, подмножеством исходного множества. Для определения нахождения выбранной альтернативы в множестве Парето достаточно сравнить её с остальными альтернативами исходного множества, используя бинарное отношение, определённое на исходном множестве. Если ни одна из них не оказалась лучше, значит, выбранная альтернатива принадлежит множеству Парето. В таком случае говорят, что данная альтернатива недоминируема на исходном множестве. Элементы множества Парето — это решения, недоминируемые на исходном множестве. Также невозможно сравнить между собой элементы множества Парето, используя определённое на исходном множестве бинарное отношение. В таком случае говорят, что элементы несравнимы между собой.

Связь между любой парой альтернатив определяется последовательностью бинарных отношений. «Сильным» бинарным отношениям соответствуют большие требования к превосходству одной альтернативы над другой и, следовательно, большее число несравнимых альтернатив. Самым сильным является полное доминирование одной альтернативы над другой. Более «слабые» бинарные отношения определяют условия, при которых, несмотря на противоречивые оценки, одна альтернатива объявляется лучшей, чем другая.

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

Однокритериальные задачи в условиях определенности

Простейшая ситуация выбора возникает, когда принятие конкретного решения x приводит к однозначному исходу y, оцениваемому с помощью единственного критерия. Предполагается однозначная зависимость y = (x). «Ценность» («полезность») исходов можно определить функционалом: F: Y > E, где y = (x). Таким образом каждому x соответствует числовая оценка f (y) = f ((x)).

Функционал F позволяет в явном виде отразить систему предпочтений ЛПР. Будем считать, чем больше значение F, тем более предпочтительна данная альтернатива.

Обозначим суперпозицию функций f и через F, приходим к оптимизационной задаче:

(1)

Функционал F (x) называют целевым функционалом или целевой функцией. Требуется построить множество:

= (2)

Соответствующее бинарное отношение R может быть задано следующим образом: (x, x) R тогда и только тогда, когда F (x) > F (x). Если F (x) = F (x), то точки x, x несравнимы по R и (x, x) R. Такое отношение обладает антирефлексивностью, ассиметричностью, транзитивностью и поэтому является отношением строгого порядка на X.

Многокритериальные задачи в условиях определенности

Положим, что любому решению x X соответствует единственный элемент y Y, где y = (x), но в данном случае «качество» или «полезность» исхода y оценивается несколькими числами f (y) — по нескольким критериям, т. е. f_i: Y E, причем каждый из функционалов требуется максимизировать. Т.о. любому решению x соответствует исход y = (x), а последнему соответствует вектор (f₁, f₂,., f_m).

С помощью суперпозиции f_i (x) = f_i ((x)) i = 1,., m можно непосредственно оценивать качество самого решения x, используя векторное отображение F: X E^m, F = (f₁,., f_m).

Рассмотрим точки x₁, x₂ X. Если f_i (x₂) f_i (x₁) i = 1,., m, причем по крайней мере одно из неравенств строгое, то будем говорить, что x₁ предпочтительнее x_2. Если для некоторого x⁰ X не существует более предпочтительных точек, то x⁰ будем называть эффективным или Парето — оптимальным решением многокритериальной задачи:

f_i (x), i = 1,., X (3)

Множество, включающее в себя все эффективные решения обозначим P_F (X) или P (X) (для известного векторного отображения) и будем называть множеством Парето для векторного отображения F: X E^m, F = (f₁,., f_m), P_F (X) X.

Множество P (F) = F (P (X)) будем называть множеством эффективных оценок.

Согласно принципу Парето оптимальное решение необходимо искать среди элементов множества P (X). В противном случае всегда найдется точка x X, оказывающаяся более предпочтительной с учетом всех частных целевых функций f_i (x).

Точку x₁ X будем называть слабо эффективным решением задачи (3), если не существует x₂ X, для которой выполняются строгие неравенства f_i (x₂) f_i (x₁), i = 1,., m. Т. е. решение называется слабо эффективным, если оно не может быть сразу по всем критериям «полезности», задаваемых с помощью f_i (x), i = 1,., m.

Множество слабо эффективных решений обозначим S_F (X) или S (X), P (X) S (X) (S (F) = F (S (X)).

Такая система предпочтений на множестве альтернатив X, заданная с помощью векторного отображения F может быть представлена на языке бинарных отношений: x₁, x₂ X

x₁ R₁ x₂ f_i (x₁) f_i (x₂), i = 1,., m. (4)

x₁ R₂ x₂ f_i (x₁) f_i (x₂), i = 1,., m, f_i (x₁) f_i (x₂).

Бинарное отношение R_{1 -} называют отношением строгого доминирования или Слейтера, а R₂ — отношением Парето. Ядра этих отношений совпадают с множествами S_F (X), P_F (X).

1.Методы оценки многокритериальных альтернатив

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

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

Прямые методы

Здесь зависимость общей полезности альтернативы от оценок по отдельным критериям известна заранее. Чаще всего используется вид зависимости, при котором определяются численные показатели важности критериев (веса), умножаемые на оценки по критериям (метод взвешенной суммы критериев). Другой метод — это дерево решений. Путем последовательного просмотра всех вариантов выбора определяются альтернативные варианты решений. Для каждого альтернативного варианта подсчитываются вероятности осуществления, которые умножаются на его ценность.

Прямые методы можно разделить на пять групп:

Постулируется сама формула зависимости полезности для многокритериальной альтернативы и все ее параметры.

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

Обоснованием выбора считается привлекательность того или иного способа для ЛПР.

Постулируется основная формула зависимости, но ее параметры непосредственно назначаются ЛПР. Например, метод взвешенных сумм оценок критериев.

Основная форма зависимости задается, а ее параметры определяются путем вычислений, проводимых на основе прямой оценки ЛПР полезностей многокритериальных альтернатив.

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

Обоснованием является представление о принципе максимизации ожидаемой полезности как о «единственном рациональном» принципе в принятии решений.

Аксиоматические методы

В литературе эта группа методов рассматривается как единственный «научно обоснованный» подход к анализу многокритериальных альтернатив, известный под названием MAUT (многокритериальная теория полезности). Аксиоматические методы разделяют на две подгруппы:

Оценки альтернатив по многим критериям считаются известными (принятие решений при определенности).

Заданы функции распределения вероятностей оценок альтернатив (принятие решений при риске).

Система аксиом:

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

Пусть u, v, w U — полезности альтернатив, тогда для любых u и v имеет место одно из следующих отношений:

u=v, u>v, uv, v>w следует u>w.

Аксиомы, исключающие ненормальности в предпочтениях. Т. е. можно использовать любые части полезности двух альтернатив (объектов) для выражения эквивалентной полезности третьей:

Рис. 1. Схема основных этапов простого метода многокритериальной оценки (SMART).

Из u>v>w следует существование такой, что u+ (1+) v=w. Обычно эту аксиому называют аксиомой растворимости.

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

А) Слабая условная независимость по полезности: предпочтения для двух альтернатив, отличающихся лишь оценками по шкале одного критерия, не зависят от оценок этих альтернатив по шкалам других критериев.

Б) Совместная независимость: предпочтения между альтернативами, отличающимися оценками по определенному подмножеству критериев, не зависят от одинаковых оценок по критериям оставшегося подмножества.

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

где xi — оценка по i — му критерию, fi — функция полезности по i — му критерию.

Методы компенсации

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

Точки и кривые безразличия

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

Построение кривой k_i:

Выбирается исходная точка P1 (x1, y1), где x1, y1 — значение критериев X, Y в данной точке;

Выбирается приращение по критерию X (положительное или отрицательное) и определяется x2 = x1 + ;

Определяется значение y2 по критерию Y такое, что точка P₁¹ (x2, y2) эквивалентна по полезности точке P1 (x1, y1);

По найденным точкам проводится кривая безразличия.

Например, кривые безразличия для двух критериев оценки альтернатив (Рис.2).

Рис. 2. Кривые безразличия для двух критериев оценки альтернатив

Методы сравнения разностей оценок альтернатив

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

Пусть (x1, x2, …, xN), (y1, y2, …, yN) — оценки альтернатив и по N критериям. Тогда альтернатива предпочтительней, чем альтернатива, если

где Ui — функция полезности для i — го критерия, i — функция, определяющая влияние разностей оценок по i — му критерию на результат сравнения двух альтернатив.

Методы порогов несравнимости

Связь между любой парой альтернатив определяется последовательностью бинарных отношений. «Сильным» бинарным отношениям соответствуют большие требования к превосходству одной альтернативы над другой и, следовательно, большее число несравнимых альтернатив. Самым сильным является полное доминирование одной альтернативы над другой. Более «слабые» бинарные отношения определяют условия, при которых, несмотря на противоречивые оценки, одна альтернатива объявляется лучшей, чем другая.

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

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

Бинарные отношения. Каждому из N критериев, имеющих числовые шкалы, ставится в соответствие целое число p, характеризующее важность критерия. Выдвигается гипотеза о превосходстве альтернативы a над альтернативой b. Множество I, состоящее из N критериев, разбивается на три подмножества:

I⁺ (a, b) — подмножество критериев, по которым a предпочтительнее b;

I⁼ (a, b) — подмножество критериев, по которым a равноценно b;

I^- (a, b) — подмножество критериев, по которым b предпочтительнее a.

Далее формируется индекс согласия с гипотезой о превосходстве a над b:

(11)

Также формируется индекс несогласия: для критериев подмножества I- (a, b) определяются d_ab — разности оценок альтернатив b и a.

Альтернатива a объявляется превосходящей альтернативу b, если c_abc1 и d_abd1 (где c1, d1 — заданные уровни).

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

Рекомендуется использовать вложенные бинарные отношения S1S2S3.

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

Человеко-машинные процедуры принятия решений

Эти процедуры применимы, когда модель проблемы известна частично. Человек взаимодействует с ЭВМ, определяя желаемое соотношение между критериями.

Существующие человеко-машинные методы принятия решений отличаются следующими чертами.

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

xi0, 1in

Задано N критериев качества C1, C2, …, CN, где

Рис. 3. Схема основных этапов метода порогов несравнимости.

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

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

2. Постановка задачи об упаковке

Рассмотрим следующую задачу: имеется множество из М объектов, которое желательно упаковать в К емкостей для последующей перевозки, причем М существенно больше К. Каждый объект характеризуется количественными физическими параметрами (например весом и объемом); каждая емкость характеризуется этими же предельными физическими параметрами (например, общим объемом и грузоподъемностью. Кроме того, каждый из упаковываемых объектов имеет оценки по нескольким критериям (с порядковыми шкалами), которые характеризуют его качество, его привлекательность для лица, ответственного за перевозку. Емкость контейнеров недостаточна для упаковки всех имеющихся объектов. Желательно осуществить упаковку наилучшим образом, т. е. так чтобы:

Среди упакованных объектов было бы наибольшее количество таких, качество которых превосходило бы качество неупакованных — критерий О₂.

Число упакованных объектов было бы максимально возможным, так как все они в той или иной степени заслуживают упаковки в емкости (т.е. предварительный отбор, исключающий абсолютно плохие объекты, уже сделан) — критерий О₁.

При К = 1 и многих критериях оценки качества упаковываемых предметов мы придем к многокритериальной задаче о многомерном рюкзаке. Задача об упаковке в контейнеры менее известна. Эта задача ставится следующим образом: Имеется конечное множество объектов, причем размер каждого из них задан рациональным числом. Требуется упаковать предметы в минимально возможное количество контейнеров так, чтобы суммарный размер объектов в каждом контейнере не превышал его размер (также рациональное число).

Упаковываемые объекты имеют оценки качества по многим критериям. Требуется упаковать максимальное число объектов, а не получить минимальное число контейнеров. Введем следующие обозначения:

v_ij — j-й физический параметр i-го объекта;

V_ij — j-й физический параметр l-го контейнера;

U_i — общая ценность i-го объекта.

Обозначим через I=1, 2, …, М множество номеров объектов, а через

множество тех упакованных объектов, для которых не найдется более ценных среди не упакованных.

Формальная постановка задачи имеет следующий вид:

,

j = 1, …, P, l = 1, …, K,

3. Функция полезности

Пусть заданы критерии K₁,…, K_n; X = x — множество векторых оценок вариантов по этим критериям. Пусть на X задано R — отношение предпочтения. Числовая функция f: X > R, называется функцией полезности (ценности, предпочтительности), если она обладает следующим свойством: f (x)? f (y) ЃМ x R y.

Если известна функция полезности, то поиск оптимального варианта сводится к задаче нахождения x* = arg max f (x), xЃёX — аргумента максимума функции полезности на множестве X.

Как найти функцию полезности? Методы построения функции полезности делятся на эвристические и аксиоматические.

К эвристическим методам можно отнести метод главного критерия и метод обобщенного критерия.

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

Метод обобщенного критерия заключается в свёртке набора критериев в числовую функцию, которая и будет являться функцией полезности.

Виды свёрток:

1) аддитивная свёртка: f = б₁K₁+…+б_nK_n;

2) мультипликативная свёртка: f = exp (б₁ln (K₁) +…+б_nln (K_n)) = =11. nnKKбб;

3) приведенная свёртка: f = min (K_i/б_i) по всем i=1…n (или f = max (K_i/б_i) по всем i=1…n).

Аксиоматические методы построения функции полезности — это формальные методы, основанные на том, что формулируются специальные предположения (аксиомы) о свойствах предпочтения, выполнение которых гарантирует существование функции полезности конкретного вида.

Обычно, при использовании таких методов функцию полезности строят в аддитивном виде:

f = л₁f₁+…+л_nf_{n (}*)

как сумму функций полезности по каждому критерию с некоторыми весовыми коэффициентами л₁,…, л_n.

Пусть K_I Ѓј K = {K₁,…, K_n} - подмножество множества критериев, т. е. группа критериев с номерами из множества I = {i₁,…, i_m}. О = {1,…, n}I. Тогда K_{О -} все остальные критерии, а векторная оценка x представляется в виде (x_I, x_О).

Говорят, что критерии K_I не зависят по предпочтению от критериев K_О, если предпочтения для любых двух оценок x = (x_I, x_О) и x' = (x_I', x_О), содержащих одинаковые компоненты с номерами из О, не зависят от самих значений этих компонент.

Критерии K₁,…, K_n такие, что любой набор K_I из них не зависит по предпочтению от остальных критериев K_О, называются взаимно независимыми по предпочтению.

Теорема Дебре (критерий существования аддитивной функции полезности): функция полезности может быть задана в аддитивном виде (*) тогда и только тогда, когда критерии K₁,…, K_n взаимно независимы по предпочтению (при n?3).

При n=2, кроме взаимной независимости критериев, требуется выполнение условия соответственных замещений (при n?3 оно выполняется автоматически):

ЃНx₁, x₂, y₁, y₂, a, b, c, d если (x₁, x₂)? (x₁-a, x₂+b) и (x₁, y₂)? (x₁-a, y₂+c), то (y₁, x₂)? (y₁-d, x₂+b) и (y₁, y₂)? (y₁-d, y₂+c).

Т.е., если увеличение на b и c разных значений x₂ и y₂ критерия K₂ при некотором опорном значении x₁ критерия K₁ компенсируется одним и тем же уменьшением этого значения x₁ критерия K₁, то такие же увеличения b и c тех же значений x₂ и y₂ критерия K₂ сохраняются и при любом другом опорном значении y₁ критерия K₁.

Как осуществляется проверка взаимной независимости критериев по предпочтению?

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

Утверждение (Леонтьева-Гормана): если любая пара критериев { K_i, K_j } не зависит по предпочтению от остальных (n-2) критериев, то все критерии K₁,…, K_n взаимно независимы по предпочтению.

Таким образом, проверка сводится к установлению независимости только всех пар критериев от всех остальных критериев.

Пусть необходимо проверить на независимость по предпочтению наборы K_I и K_О. Берём набор x_О⁺ наилучших (явно хороших) значений K_О и подбираем (запрашиваем у ЛПР) два разных набора x_I' и x_I'' таких, что (x_I', x_О⁺) ~ (x_I'', x_О⁺). Затем берём набор x_О ^- самых плохих оценок и спрашиваем у ЛПР, сохранилось ли безразличие (x_I', x_О^-) ~ (x_I'', x_О^-)? Если нет, то критерии K_I зависят от критериев K_О. Если да, повторяем процедуру еще для некоторых других x_I' и x_I''. Если всё время безразличие остаётся, задаём вопрос в общем виде (сохранится ли безразличие при любых наборах). Если да, то наборы критериев K_I и K_О независимы.

Методы построения аддитивной функции полезности

Шаговый метод совместного шкалирования.

Пусть n=2 и условие соответственных замещений выполнено.

f (x₁, x₂) = f₁ (x₁) + f₂ (x₂) ЃН (x₁, x₂) ЃёX.

Обозначим диапазоны изменения оценок x₁ и x₂: x_1*? x₁? x₁^*, x_2*? x₂? x₂^*.

Полагаем f (x_1*, x_2*) = f₁ (x_1*) = f₂ (x_2*) = 0 (начало отсчета).

Берем любое значение x₁¹ > x_1* достаточно близкое к нему. Устанавливаем f₁ (x₁¹) = 1 (единица измерения).

От ЛПР требуем указать x₂¹ такое, что (x₁¹, x_2*) ~ (x_1*, x₂¹), для этого значения также f₁ (x₂¹) = 1.

Затем у ЛПР запрашиваем x₁² и x₂² такие, что:

(x₁², x_2*) ~ (x₁¹, x₂¹) ~ ~ (x_1*, x₂²). f (x₁¹, x₂¹) = 1+1 = 2 ЃЛ f₁ (x₁²) = f₂ (x₂²) = 2.

Далее у ЛПР запрашиваем x₁³ и x₂³ такие, что:

(x₁³, x_2*) ~ (x₁², x₂¹) ~ ~ (x₁¹, x₂²) ~ (x_1*, x₂³) ЃЛ f₁ (x₁³) = f₂ (x₂³) = 3.

И т.д. Таким образом, получаем наборы значений f₁ (x_1*), f₁ (x₁¹), f₁ (x₁²), f₁ (x₁³) … и f₂ (x_2*), f₂ (x₂¹), f₂ (x₂²), f₁ (x₂³) … по которым с помощью интерполяции строятся функции f₁ (x) и f₂ (x).

Метод половинного деления.

Метод находит функцию полезности в виде

f (x₁, x₂) = л₁f₁ (x₁) +л₂f₂ (x₂), где f₁ (x_1*) = f₂ (x_2*) = 0, f₁ (x₁^*) = f₂ (x₂^*) = 1, л₁>0, л₂>0, л₁+л₂=1.

Построим функцию f₁.

ЛПР просим указать среднюю по полезности оценку x₁^0.5 Ѓё [x_1*; x₁^*], т. е. такую, изменение полезности на [x_1*; x₁^0.5] равно изменению полезности на [x₁^0.5; x₁^*]. Устанавливаем f₁ (x₁^0.5) = 0.5.

Далее аналогично получаем

x₁^0.25 Ѓё [x_1*; x₁^0.5] ЃЛ f₁ (x₁^0.25) = 0.25 и x₁^0.75 Ѓё [x₁^0.5; x₁^*] ЃЛ f₁ (x₁^0.75) = 0.75 и т. д.

С помощью интерполяции, восстанавливаем функцию f₁ по её значениям в точках x₁^0.5, x₁^0.25, x₁^0.75…

Функция f₂ строится аналогично.

Для нахождения весового коэффициента л₁ достаточно запросить у ЛПР пару одинаковых по предпочтительности оценок (x₁', x₂')? (x₁'', x₂'') ЃЛ ЃЛ f (x₁', x₂') = f (x₁'', x₂'') ЃЛ л₁f₁ (x₁') + (1-л₁) f₂ (x₂') = л₁f₁ (x₁'') + (1-л₁) f₂ (x₂''), а из этого равенства уже можно выразить л_{1 (}а л₂ = 1 — л₁).

4. Слои Парето

Поскольку вероятность того, что исходное множество будет одновременно являться и множеством Парето (состоять из несравнимых объектов) крайне мала, то будем выделять т. н. слои Парето. Один слой формируется следующим образом:

из исходного множества выделяется недоминируемый элемент

затем выделяются все несравнимые с ним объекты

Выделенные объекты заносятся в новое множество, называемое слоем Парето. Затем исходное множество, из которого теперь удалены «лучшие» объекты, обрабатывается по тому же принципу до тех пор, пока обработке и занесению в свой слой не подвергнется каждый его элемент. Каждый слой Парето является элементом множества подмножеств исходного множества. На рис. 4.1 показан граф, иллюстрирующий пример отношения доминирования на множестве. Исходящая стрелка обозначает доминирование объекта, из которого она исходит, над объектом, на который она указывает. Двунаправленная стрелка говорит о том, что объекты несравнимы (4 14, 8 13). Узел 5 является доминирующим на исходном множестве, поэтому на рисунке он не имеет ни одной входящей стрелки, в т. ч. двунаправленной, а только исходящие. Поэтому его можно выделить во множество (слой) Парето, которое будет состоять только из одного элемента. На рисунках 4.2 — 4.8 показан процесс изменения исходного множества по мере выделения из него слоёв Парето.

Рис.4.1 В центре расположен недоминируемый объект (узел графа).

Рис.4.2.

Рис.4.3.

Рис.4.4.

Рис.4.5.

Рис.4.6.

Рис.4.7 Рис.4.8

В результате осуществлённых операций объекты исходного множества распределились по слоям Парето следующим образом:

[5]

[7]

[17]

[16]

[12]

[4] [13] [14]

[10] [20]

[1] [3] [9] [18] [19]

Сравнение упаковки объектов для сортировки по полезности и для распределения по слоям Парето.

В таблице 4.1 представлены объекты, отсортированные по полезности:

Таблица 4.1 Сортировка по полезности.

Упакуем объекты в контейнеры, отсортировав их по полезности (Таб.4.2)

Таблица 4.2 Распределение объектов по контейнерам после сортировки по полезности.

Величина суммарной полезности: 144.

А теперь упакуем их после распределения по слоям Парето (Таб.4.3)

Таблица 4.3 Распределение объектов по контейнерам после распределения по слоям Парето.

Величина суммарной полезности: 120.

На рис. 4.9 представлен график, отображающий результаты упаковки для обоих случаев распределения объектов. Вывод.

Рис. 4.9 Представление результатов упаковки.

Вывод.

Была выполнена упаковка 20 объектов, каждый из которых имеет свои характеристики массы и объёма. Упаковка производилась в 5 контейнеров двумя способами: по полезности и по слоям Парето. В обоих случаях количество упакованных объектов одинаково. Оценка результатов упаковки для варианта по слоям Парето в данной задаче оказалась хуже, чем для упаковки по полезности.

5. Программа

Структура

Программа, решающая эту задачу, написана на языке Java. Java является объектно-ориентированным языком, поэтому в нём доступны классы — структуры данных, описывающие объекты. С математической точки зрения класс можно отождествить с вектором, а поля класса — со скалярами в составе этого вектора. При этом поля класса могут сами являться объектами (экземплярами) других классов (или этого же класса, в случае со связными списками). Помимо этого, класс содержит методы, позволяющие оперировать данными. Другими словами, поля описывают объект класса, а методы — поведение этого объекта. Java также поддерживает спецификаторы доступа к полям и методам, что позволяет обезопасить данные внутри класса от нежелательного доступа и модификации («повреждения информации»). Также в Java существует наследование классов — объект класса-наследника наследует поля и методы родительского класса, за исключением приватных. Этот механизм используется в случае, когда существующий класс недостаточно подробно описывает какой-либо объект, и требуется расширить его описание и/или переопределить методы родительского класса, доступные классу-наследнику. Класс в Java может наследоваться только от одного родительского класса — создатели языка пришли к выводу, что во всех случаях, когда в программе используется множественное наследование, можно перестроить архитектуру программы так, чтобы обойтись одиночным. Это намного упрощает разработку и исключает проблему т. н. «ромбовидного наследования» .

Помимо обычного наследования, в Java есть механизм интерфейсов. Интерфейс можно описать как класс, все поля которого являются константами, а все методы — абстрактными. Интерфейс не содержит реализаций методов, аналогично прототипам функций в С/С++. Интерфейсы, как и классы, могут наследоваться друг от друга, причём для них возможно множественное наследование (поскольку методы в интерфейсах не реализованы, проблем с «ромбовидным наследованием» не возникает). Для задействования механизма интерфейсов в объявлении класса нужно указать, что он реализует интерфейс с таким-то именем. После этого в этом классе необходимо реализовать все методы, объявленные в интерфейсе. Если реализация всех методов невозможна, а «пустые» реализации по тем или иным причинам недопустимы, можно объявить этот класс абстрактным. Но в этом случае объект этого класса, как и объект интерфейса, создать будет нельзя. Класс может реализовать любое количество интерфейсов, и интерфейс может быть реализован любым количеством классов. В дальнейшем, создав интерфейсную ссылку, её можно будет инициализировать объектом любого класса, реализующего этот интерфейс. При этом классы, реализующие интерфейс, могут не состоять друг с другом в каком-либо отношении наследования. (Благодаря этому можно, например, создать массив интерфейсных ссылок на такие классы). Через интерфейсную ссылку недоступны никакие поля объекта, которым инициализирована эта ссылка, кроме констант интерфейса, и недоступны никакие методы, не объявленные в этом интерфейсе либо в родительских интерфейсах. Механизм интерфейсов удобен в тех случаях, когда необходимо определить, что будет делать объект, и неважно, как именно он это будет делать, что очень помогает на стадии проектирования программы.

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

1. Количество элементов коллекции можно изменять, в то время как размер массива постоянен.

2. Следовательно, на момент создания коллекции необязательно знать, сколько элементов должно быть в её составе. Тем более что это и не всегда возможно.

Вдобавок, элементы некоторых видов коллекций могут индексироваться любым объектом, т. е. их индекс, в отличие от индекса элемента массива, может не быть целым числом (карта — список пар «ключ — значение», где ключ — объект). В других случаях коллекции позволяют абстрагироваться от индекса вообще (множество, стек, очередь, кольцевой буфер, кольцевой связный список).

В данной программе определены классы, описывающие следующие сущности:

1. Упаковываемый объект. Этот класс содержит параметры упаковываемых объектов — объём, вес и оценки по полезности.

2. Контейнер. Описывает одномерный контейнер.

3. Упаковщик. Осуществляет операции по созданию парных объектов, формированию слоёв Парето, упаковке объектов в контейнеры.

4. ЛПР. Содержит алгоритм вычисления ценности (функция ценности), умеет сравнивать объекты по полезности, отображать парные объекты в один объект.

5. Склад. То место, откуда получают объекты для упаковки и куда возвращаются объекты, не поместившиеся в контейнеры.

6. Бинарное отношение (интерфейс). Содержит один метод — compare («сравнить»). Реализован вложенным классом в классе, описывающем ЛПР.

Также имеется один класс, содержащий метод main, в котором реализована последовательность действий описываемых сущностей от момента создания всех объектов и до момента упаковки объектов.

Пример решения задачи

Рассмотрим следующую задачу:

Имеем 40 объектов. Объекты имеют два физических параметра — вес и объем, ценность объекта оценивается по пяти критериям. Причём оценки по двум критериям (критерий 1 и 2) более важны, чем оценки по другим критериям. Вычислим полезность каждого объекта. Воспользуемся прямым методом оценки многомерных альтернатив, тогда функция полезности каждого объекта будет иметь следующий вид:

где wi — вес i-го критерия, назначаемый ЛПР:

xi — оценка альтернативы по i — му критерию.

N — число номеров критериев.

Назначим веса критериев, в соответствии с условием нормировки:

Так как критерий 1 и 2 имеют большую важность, то им будет соответствовать большой вес.

Вес критериев приведён в таблице 5.3.1.

Таблица 5.3.1 Веса критериев

На рис. 5.3.1 приведены характеристики объектов и контейнеров. На этом этапе есть возможность создавать и разбивать пары объектов, а также менять их характеристики и характеристики контейнеров.