Методы оптимальных решений

Запишем условия Куна – Таккера и проверим, выполняются ли они в точке (1, 0). Условия принимают следующий вид:

При Х* = (1, 0) из уравнения следует, что U2 = -4, тогда как уравнение дает U2 = 0. Следовательно, точка оптимума не является точкой Куна – Таккера.

Замечание. Нарушение условия линейной независимости не обязательно означает, что точка Куна – Таккера не существует.

Теорему Куна – Таккера можно использовать для доказательства того, что заданная допустимая точка, удовлетворяющая условию линейной независимости, не является оптимальной, если она не удовлетворяет условиям Куна – Таккера. С другой стороны, если в этой точке условия Куна – Таккера выполняются, то нет гарантии, что найдено оптимальное решение нелинейной задачи.

 

Задача 4.

 

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

Необходимо:

1. Найти и изобразить  множество достижимых критериальных векторов Z, его паретову границу P(Z) и идеальную точку z*.

2. Изобразить линии уровня  функции  .

3. Графически решить задачу  нахождения достижимой точки (z’1, z’2), дающей минимум отклонения от идеальной точки.

4. Аналитически записать  задачу минимизации отклонения  от идеальной точки в виде  задачи линейного программирования.

Решение

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

Будем строить графики ограничений по одному, начиная с имеющего высший приоритет. У нас это - ограничение по прибыли. Минимизируем

d1-, следовательно, помечаем область  над прямой, для которой

d1- = 0, а d1+ >0 (см. рис. 1).

Рис. 1. Анализ 1 и II целей

Аналогично и для 2-го ограничения. Следовательно, если решение удовлетворяет первым двум целям, то решение будет находиться в области, заштрихованной на рис. 4.1. Третья цель - избежать перерасход ресурса 2-го вида. Для нее d3+ должно быть равно нулю, следовательно, область удовлетворения цели должна находиться под прямой, заданной этим ограничением, а область, удовлетворяющая всем трем первым ограничениям - это заштрихованная полоска на рис .2.

 

 

Рис. 2. Анализ всех целей

Четвертая цель (произвести по крайней мере 7 изделий 2-го вида) минимизирует d4- , следовательно, область, удовлетворяющая этой цели,

находится выше прямой х2 = 7. Но эта область не имеет общих точек с заштрихованной, а поскольку заштрихованная область имеет больший приоритет, то в ней и будем определять решение задачи. Как видим, 4-я цель не может быть выполнена. Наименьшее значение переменной сЬГ будет в точке А с координатами (0;6). Это и будет решение задачи: продукцию 1-го вида не выпускать(х1 = 0), а 2-го вида выпустить в объеме 6 ед. (х2 = 6).

Подставив эти величины в целевые ограничения, получим другие переменные:

Таким образом, цель по прибыли удовлетворена и превышена на 6 ед. (прибыль = 36), цель по 1-му ресурсу выполнена и превышена на 6 ед. (израсходовано 18 ед. - 6 ед. пришлось привлечь дополнительно, что разрешено по условию задачи). Цель по 2-му ресурсу выполнена в точности ( израсходовано 30 ед), а 4-я цель недовыполнена на одну единицу ( вместо 7 ед. по контракту придется поставить 6 ед.).

 

 

Задача 5.

Рассмотреть задачу двухкритериальной максимизации

→ max,

→ max

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

,

x1≥0,

x2≥ 0,

x3≥ 0.

Необходимо:

1. Найти Парето-эффективное решение, максимизирующее линейную свертку критериев 

2. Проверить, выполняется  ли для возникающей задачи  нелинейного программирования условия  теоремы Вейерштрасса и является  ли эта задача задачей выпуклого  программирования.

3. Проверить возможность  использования условий Куна-Таккера в данной задаче.

4. Выписать и проверить  выполнение условий Куна-Таккера в градиентной форме для различных наборов активных ограничений.

5. Найти решение рассматриваемой  задачи нелинейного программирования.

6. Выписать функцию Лагранжа  и условия Куна-Таккера через функцию Лагранжа.

7. Проверить выполнение  условий Куна-Таккера в найденном решении.

Решение:

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

1. Способ оценки коэффициентов в линейной свертке

Рассмотрим многокритериальную задачу оптимизации: пусть функции fi(x), i = 1, 2, ..., m, определены на множестве X, X ⊂ Rn, Rn - n-мерное вещественное пространство, и отображают X соответственно в Yi ⊂ R = (-∞, ∞); требуется найти

 (1)

Основные способы решения этой задачи основаны на свертке критериев fi(x) из (1) [2]. Из различных способов свертки критериев на практике наиболее часто используется способ линейной свертки. Он предполагает объединение критериев из (1) путем построения линейной комбинации fi(x), i = 1, 2, ..., m (построению взвешенной суммы частных критериев) и переходу к однокритериальной задаче:

 (2)

 (3)

где αi определяются экспертами. Однако такой подход определения α i, основанный на субъективном мнении экспертов, приводит в конечном итоге к тому, что решение задачи (2), (3) будет в значительной степени субъективным. В данном пункте предлагается другой способ определения α i, i = 1, 2, ..., m. Вначале будем допускать, что все критерии из (1) не ранжированы. В этом случае предлагается следующий способ свертки критериев f i(x) из (1).

Пусть заданы точки x (1) , x (2) , ..., x (r) ∈ X. Вычислим значения

,

и построим линейную комбинацию

в которой α i, i = 1, 2, ..., m, предлагается выбирать (приближенно) путем решения задачи нелинейного программирования:

 (4)

 (5)

 (6)

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

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

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

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

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

Задача (4)-(6) может быть решена методами, описанными в [2]. Для ее численного решения можно использовать различные инструментальные средства, например, офисным приложением электронных таблиц Excel.

Пусть теперь критерии f1(x), i = 1, 2, ..., m, ранжированы следующим образом:

 (7)

где соотношение

,

означает что критерий fp(x) не менее предпочтителен, чем критерий f p+1(x). Однако степень предпочтительности fp(x) по отношению к f p+1(x) неизвестна (не указана). В этом случае, очевидно α i, i = 1, ..., m, должны удовлетворять дополнительному условию

. (8)

Тогда задача приближенного вычисления α i, i = 1, 2, ..., m, в случае их ранжирования согласно (7) сводится к решению оптимизационной задачи (4)-(6),(8).

Пример 1. Пусть в модели (4)-(6), i = 1, 2; r = 1, 2, ..., 5, x (1) = 0,5; x (2) = 3; x (3) = 4,5; x (4) = 7; x (5) = 8,5. Тогда, воспользовавшись офисным приложением электронных таблиц Excel, найдем α1 = 0,5; α2 = 0,5.

Если критерии f 1(x), f 2(x), ранжированы , то решая эту же задачу при дополнительном условии (8) (т.е. α1 ≥ α2), получим тот же результат: α1 = 0,5; α2 = 0,5.

Явные формулы для вычисления коэффициентов в линейной свертке критериев

В задачах (4)-(6), (4)-(7) коэффициенты α i, i = 1, ..., m, как отмечалось в п.1, определяются методами нелинейного программирования. Покажем, что при некоторых дополнительных ограничениях на функции f i(x), i = 1, 2, ..., m, из (1) можно указать явные формулы для вычисления α i, i = 1, ..., m.

Продифференцируем левую часть выражения (4) последовательно по α1, α2, ..., αn. Из необходимого условия экстремума следует, что α1, α2, ..., αn определяются из системы алгебраических уравнений

 (9)

которая, после преобразований, принимает вид:

 (10)

Согласно правилу Крамера система (10) будет иметь единственное решение, если ее главный определитель

 (11)

отличен от нуля: Δ ≠ 0.

Введем вспомогательные определители:

.........................................................................................................

.

Тогда, по теореме Крамера,

 (12)

Следовательно, если f i(x), i = 1, 2, ..., n, из (1) непрерывны на X и удовлетворяют в заранее заданных точках x(1) , x (2) , ..., x (r) ∈ X условию Δ ≠ 0, то α1, α2, ..., αn определяются соотношениями (12).