Конспект лекций по теории систем управления (994584), страница 5

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

Текст из файла (страница 5)

Действительно, какое решение ( или ) лучше, например, для двухкритериальной задачи:

1. , ;

2. , .

По-видимому, в данном случае, решения несравнимы.

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

Определение 1.

Из двух точек точка называется доминирующей по отношению к ( ), если для всех выполняется и, кроме того, по крайней мере, для одного j: .

Определение 2.

Точка называется улучшаемой, если существует хотя бы одна точка , такая, что , и хотя бы для одного j: , в противном случае точка неулучшаемая или эффективная.

Определение 3.

Множество S, состоящее из эффективных точек называется множеством решений, оптимальных по Парето.

(В. Парето /1848-1923/ - итальянский экономист, социолог, математик. Впервые ввел понятие "эффективная точка множества".)

Множество является решением задачи (1), с формальной точки зрения этим можно завершить рассмотрение задачи (0). Множество строится затем, чтобы из него, привлекая неформальные критерии можно было бы выбрать некоторое решение. Однако обычно выбор делается в пространстве критериев, а затем в силу взаимно-однозначного соответствия выбирается элемент из S. В задаче (0) задает отображение области в некоторую область . называется областью критериев.

Определение 4.

Доминирование остается в силе и для точек из . - элемент . Область называется областью согласия, если из любых двух точек этой области одна будет доминирующей по отношению к другой. Если совпадает с , тогда существует единственная точка , являющаяся доминирующей по отношению ко всем другим точкам из , то есть x - оптимальное решение задачи (0).

Определение 5.

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

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

(0)

Графически она представлена следующем рисунке

Рис. 17.

На этом рисунке видно, что для , а также для оба критерия возрастают, следовательно точки из полуинтервала [1;3) и (5;7] улучшаемы: для точка дает меньшее значение критериев, аналогично ведет себя x = 5 для .

Видно, что внутри отрезка [3;5] до точки пересечения графиков обеих функций, т.е. на отрезке , убывает, а возрастает. На отрезке [4;5] наоборот: возрастает, а убывает, следовательно, согласно введенным выше определениям - отрезок для данной задачи является множеством решений, оптимальных по Парето.

На следующем рисунке в пространстве , для этой же задачи представлены области согласия и компромиссов, являющиеся плоскими кривыми, полученными в результате отображения области (отрезок [1;7]) в области .

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

x	f1(x)	f2(x)
2	3	11
3	1	6
4	3	3
5	9	2

Рис. 18.

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

1. Методы решения при отсутствии дополнительной информации о важности частных критериев оптимальности.

2. Методы решения при наличии информации о важности частных критериев оптимальности.

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

1. Метод относительного разброса.

2. Метод отклонения частного критерия от его наименьшего значения.

3. Использование попарных приоритетов.

4. Использование интервальной информации.

5. Теоретико-игровая модель выбора весовых коэффициентов.

6. Определение весовых коэффициентов по разности максимального и минимального элемента матрицы С. Элементами матрицы С_ij являются значения i-ого частного критерия оптимальности в точке оптимальности j-ого критерия.

7. Определение весовых коэффициентов при одинаковом приоритете частных критериев.

Ко второй группе методов относятся:

1. Метод выделения главного критерия.

2. Метод последовательной оптимизации с учетом жесткого приоритета.

3. Метод последовательных уступок.

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

5. Метод квазиравенства частных критериев оптимальности.

6. Метод гарантированного результата или метод минимакса.

Задача многокритериального линейного программирования.

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

Определение доминирующего решения:

Из двух точек точка называется доминирующей по отношению к ( ), если для всех выполняется и, кроме того, по крайней мере, для одного j: .

Рис. 20. Пример области Парето.

Область Парето (рис.20) - область компромиссов (ломанная АВС).

Получилось, что:

• по первому критерию точка A лучше остальных

• по второму критерию точка B лучше остальных

• по третьему критерию точка C лучше остальных

• по четвёртому критерию точка C лучше остальных

Правило определения области решения:

Если все вектора, указывающие направления улучшения критериев (направление улучшения критерия совпадает с направлением градиента функции , если , и с направлением антиградиента функции , если ) принадлежат открытому полупространству проведённому через начало координат в системе координат (с₁,с₂), тогда решение решением многокритериальной задачи оптимизации является область Парето, представляющая часть границы допустимой области решений, в противном случае областью решений многокритериальной задачи будет вся допустимая область.

Пример:

Предположим, что градиенты функций (при , i=1,…,5) имеют направления показанные на рис.21.

Рис. 21.

В этом случае решением будет являться вся допустимая область S.

Пример:

f₁ = 2x₁ + 3x₂  max

f₂ = 2x₁ + 3x₂  min

x₁ + x₂  5

S x₁ + 4x₂  4

x₁  0; х₂  0

Рис. 22.

Решение: вся область (правило).

Задача:

Банк имеет возможность инвестировать финансовые ресурсы в размере 10 млн. долларов в два проекта. При инвестировании в первый проект прибыль составляет 30% годовых, при инвестировании во второй проект - 35% годовых. Потери от риска при вложении в первый проект составляют 60% годовых, во второй проект - 65% годовых. Какое количество финансовых средств банк должен вложить в первый и во второй проекты, чтобы получить максимальную прибыль и понести минимальные потери от риска.

f₁ = 0,3x₁ + 0,35x₂  max

f₂ = 0,6x₁ + 0,65 x₂  min

x₁ + x₂  10

x₁ > 0; х₂ > 0

Рис. 23.

Абсолютно гарантированный план.

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

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

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

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

,

,

Абсолютно гарантированный план получается при решении следующей задачи.

Удовлетворительные планы

Удовлетворительный план составляется путем проведения нескольких итераций просчета возможных путей реализации выпуска продукции (с увеличением объема реализации на 5% -10%). Во время каждой итерации просчитывается удовлетворения ограничения по ресурсам необходимым для выполнения намеченного плана. Если по каким-то видам ресурсов на определенные итерации не удовлетворяются (нельзя обеспечить поставку в таких количествах), то переходим к следующей итерации. Изменяем количество какого-то вида изделия, к планируемому к выпуску. И опять пересчитываем количество требуемых ресурсов и т.д. до того пока не будут выполнены ограничения по ресурсам.

Характеристики

Список файлов лекций