1.1. Формальная постановка многокритериальной задачи линейного программирования.

1.2. Условие задачи

2. Решение многокритериальной задачи линейного программирования графическим методом

2.1. Формальное условие и сведение к ЗЛП

2.2. Графическое определение p-множества

3. Определение Парето-оптимального множества с-методом

3.1. Удаление пассивных ограничений

3.2. Определение p-множества с-методом

4. Определение альтернативных вариантов многокритериальной задачи

4.1. Метод гарантированного результата

4.2. Метод линейной свертки частных критериев

5. Составление сводной таблицы

Заключение

Список литературы

Введение

Лишь в редких случаях цели, которые лицо принимающее решение (ЛПР) стремится достичь в планируемой им операции, удается описать с помощью одного количественного показателя. Поэтому специалисты Системного анализа и Исследования операций считают целесообразным избегать термина «оптимизация», так как поиск оптимального решения х, доставляющего функции F(x) экстремальное значение, имеет вполне определенный смысл и давно входит в арсенал основных понятий математики. Многообразие целей ЛПР более адекватно может быть описано с помощью некоторой совокупности частных критериев (ч-критериев), характеризующих степень достижения частных целей. Противоречивый характер целей обуславливает, как правило, и противоречивость ч-критериев. С формальной точки зрения это приводит к тому, что свои экстремальные значения ч-критерии получают в различных точках ОДР D_x . Следовательно, ЛПР принимая решение х^, всегда должно идти на компромисс, в разумных пределах допуская ухудшение значений одних ч-критериев во имя улучшения значений других. Именно этот этап творческой деятельности ЛПР наименее формализуем и требует привлечения предыдущего опыта, интуиции и даже искусства ЛПР, обладающего практическим опытом в соответствующей предметной области. Решение, принимаемое ЛПР с привлечением совокупности ч-критериев, будем называть компромиссным , рациональным или просто решением ЛПР, избегая при этом термина «оптимальный», имеющего определенный и вполне точный смысл.

Основная идея обоснования и принятия решения ЛПР в условиях многокритериальности состоит в последовательном сужении ОДР D_x до минимальных размеров, что облегчает принятие окончательного решения ЛПР. Первым, наиболее существенным шагом в этом направлении будет являться сужение ОДР D_x до некоторого подмножества D_x ^p ÌD_x на основании принципа доминирования.

1.Общая постановка многокритериальной задачи линейного программирования.

1.1.Формальная постановка многокритериальной задачи линейного программирования.

Формальная схема многокритериальной ЗЛП (МЗЛП) от обычной ЗЛП отличается наличием нескольких целевых функций:

(1)

??? e_i ? ??????????????? ?????????? (???????, i = 1; m).

(3)

(2)

???? max ???????? ??? ????, ??? желательно увеличение каждой из линейных форм L^r (х), ?????????? ????????? r-? ???? ???.

Требование только максимизации не сужает общности задачи. Так, например, требование минимизации затрат некоторых ресурсов эквивалентно требованию максимизации остатка от изначально выделенных ресурсов. Наличие многих ч-критериев позволяет сделать модель (1) – (3) более адекватной изучаемой ситуации, однако выводит её из класса задач МП и требует разработки новых способов ее анализа. Начальный анализ МЗЛП состоит в удалении из области допустимых решений (ОДР) D_х явно худших, доминируемых решений х . Решение х^, доминирует решение х (х^, > х), если при х^, хотя бы один ч-критерий имеет больше значение при равенстве остальных. Поэтому решение х может быть исключено из дальнейшего рассмотрения, как явно худшее, чем х^, . Если решение х^, не доминируется ни одним из решений х ÎD_x , то его называют Паретто-оптимальным ( p - оптимальным) или эффективным решением ( p - решением) . Таким образом, p-решение - это неулучшаемое (недоминируемое) решение, и ясно, что решение ЛПР должно обладать этим свойством – другие решения нет смысла рассматривать.

Формальное определение p -оптимальности решения х^, записывается как требование об отсутствии такого решения х Î D_x , при котором бы были выполненыусловия

(4)

и хотя бы одно из них – строго (со знаком >).

Иными словами, условия (4) выражают требование невозможности улучшения решения х^, в пределах ОДР D_x ни по одному ч-критерию без ухудшения хотя бы по одному из других.

1.2.Условие задачи

Даны целевые функции:

L₁ = -x₁ + 2x₂ + 2,

L₂ = x₁ + x₂ + 4,

L₃ = x₁ - 4x₂ + 20,

и система ограничений:

x₁ + x₂ £ 15,

5x₁ + x₂ ³ 1,

-x₁ + x₂ £ 5,

--> ЧИТАТЬ ПОЛНОСТЬЮ <--