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

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

Оглавление

Введение

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

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

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

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

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.

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

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

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

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

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

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

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

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

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

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

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

. Отношение 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 = j (x). “Ценность" (“полезность”) исходов можно определить функционалом: F: Y → E, где y = j (x). Таким образом каждому x соответствует числовая оценка f (y) = f (j (x)).

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

Обозначим суперпозицию функций f и j через 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 = j (x), но в данном случае “качество" или “полезность" исхода y оценивается несколькими числами f (y) - по нескольким критериям, т.е. f_i: Y ® E, причем каждый из функционалов требуется максимизировать. Т.о. любому решению x соответствует исход y = j (x), а последнему соответствует вектор (f₁, f₂,., f_m).

С помощью суперпозиции f_i (x) = f_i (j (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.