1. Постановка задачи

математическая модель парето оптимальность

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

1) многокритериальная задача

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

выходные данные: решения, входящие в множество Парето; номера парето-оптимальных решений из множества исходных решений

2) двухкритериальная задача

выходные данные: решения, входящие в множество Парето; номера парето-оптимальных решений из множества исходных решений; графическое представление парето-оптимальных решений.

2. Краткие теоретические сведения

Пусть задан набор числовых функций

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

Указанные выше числовые функции образуют векторный критерий

, который принимает значения в пространстве m-мерных векторов

. Это пространство называют критериальным пространством или пространством оценок, а всякое значение

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

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

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

Необходимо отметить, что формирование математической модели принятия решений (т.е. построение множества X и векторного критерия f ) нередко представляет собой сложный процесс, в котором тесно взаимодействуют специалисты двух сторон. А именно, представители конкретной области знаний, к которой относится исследуемая проблема, и специалисты по принятию решений (математики). С одной стороны, следует учесть все важнейшие черты и детали реальной задачи, а с другой, – построенная модель не должна оказаться чрезмерно сложной с тем, чтобы для ее исследования и решения можно было успешно применить разработанный к настоящему времени соответствующий математический аппарат. Именно поэтому этап построения математической модели в значительной степени зависит от опыта, интуиции и искусства исследователей обеих сторон. Его невозможно отождествить с простым формальным применением уже известных, хорошо описанных алгоритмов.

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

Рассмотрим два произвольных возможных решения

. Для них имеет место один и только один из следующих трех случаев:

1) справедливо соотношение

(ЛПР первое решение предпочитает второму),

2) справедливо соотношение

(ЛПР второе решение предпочитает первому),

3) не выполняется ни соотношение

, ни соотношение

(ЛПР не может отдать предпочтение ни одному из указанных двух решений).

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

выполняются, невозможен благодаря асимметричности отношения предпочтения

В первом из указанных выше случаев, т.е. при выполнении соотношения

, говорят, что решение

доминирует решение

Если же реализуется третий случай, то говорят, что решения

не сравнимы по отношению предпочтения.

Аксиома Парето.

Для всех пар допустимых решений

, для которых имеет место неравенство

, выполняется соотношение

Решение

называется оптимальным по Парето (парето-оптимальным), если не существует такого возможного решения

, для которого имеет место неравенство

. Все парето-оптимальные решения образуют множество Парето, обозначаемое

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

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

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

3. Реализация программного средства.

Среда разработки: VisualStudio 2010

Язык программирования: C#

3.1 Проектирование

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

Список классов с кратким описанием:

1) MainView.cs – это главное окно, служит для ввода данных и запуска работы алгоритма поиска парето-оптимальных решений.

2) SolutionsView.cs – это окно, которое содержит найденные парето-оптимальные решения, представленные в табличной форме

3) GraphView.cs– окно, на котором будет отображаться графическое представление множества Парето для двухкритериальных задач

4) Pareto.cs – это основной класс. Содержит 2 алгоритма поиска множества Парето.

5) Graph.cs – класс, содержащий методы для построения графиков (в данном случае будем использовать стороннюю библиотеку ZedGgraph.dll)

6) File.cs –методы для сохранения и загрузки данных в/из файл(а).

3.2 Алгоритм поиска парето-оптимальных решений

Шаг 1. Положить P(Y) =Y , i =1, j = 2 . Тем самым образуется так называемое текущее множество парето-оптимальных векторов, которое в начале работы алгоритма совпадает с множеством Y , а в конце составит искомое множество парето-оптимальных векторов. Алгоритм устроен таким образом, что искомое множество парето-оптимальных векторов получается из Y последовательным удалением заведомо неоптимальных векторов.

Многокритериальные задачи. Паретовские решения (стр. 1 из 2)

Оглавление

1. Постановка задачи

2. Краткие теоретические сведения

3. Реализация программного средства.

3.1 Проектирование

3.2 Алгоритм поиска парето-оптимальных решений