Другими словами, в множество Парето не включаются такие решения, которые могут быть улучшены одновременно по обоим критериям.

Укажем простое геометрическое правило, посредством которого можно выделять из заданного плоского множества его границу Парето.

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

3.2 Метод идеальной точки

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

Пусть на плоскости (х,y) задано множество щ и в каждой точке этого множества определены две непрерывные функции: U = Ц(x,y) и V = Ш(x,y).

На множестве щ найти точку (x₀,y₀), в которой Ц(x₀,y₀)=max и Ш(x₀,y₀)=max.

Сразу же отметим, что в общем случае поставленная задача решения не имеет. В самом деле, изобразим на плоскости (U,V) все точки, координаты которых вычисляются по формулам U = Ц(x,y) и V = Ш(x,y). Обозначим полученное множество через . Из рисунка видно, что U_max (наибольшее значение U) и V_max (наибольшее значение V) достигаются в разных точках, а точка P с координатами (U_max, V_max) лежит вне множества . Таким образом, в исходной постановке задача, вообще говоря, неразрешима - удовлетворить обоим требованиями одновременно невозможно. И, следовательно, нужно искать какое-то компромиссное решение.

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

Рассмотрим реализацию метода идеальной точки на конкретном примере.

Пример

Решить двухкритериальную задачу линейного программирования методом идеальной точки.

Решение

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

Рассмотрим первое неравенство 4y - x ? 20.

Границей полуплоскости является прямая 4y - x = 20. Построим эту прямую по двум точкам. Составим таблицу:

1)	x	0	4
	y	5	6

Определим, какую полуплоскость задает первое неравенство: выше построенной прямой или ниже ее. Для этого подставим в неравенство координаты любой «пробной» точки, не лежащей на построенной прямой. Возьмем в качестве «пробной точки» начало координат: (0; 0):

Получили верное числовое неравенство, значит рассматриваемое линейное неравенство определяет полуплоскость, которой принадлежит начало координат, т.е. расположенную ниже построенной прямой. Отметим выбранную полуплоскость.

Аналогично определим полуплоскости, задаваемые вторым и третьим неравенствами: 4x + y ? 22 и х - у ? 3.

2)	x	5	4		3)	x	5	1
	y	2	6			y	2	-2

Оставшиеся ограничения: х ? 0, у ? 0 задают первую координатную четверть. Область допустимых решений - многоугольник OABCD.

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

В нашем случае, очевидно, что O(0; 0), A(0; 5), B(4; 6), C(5; 2), D(3; 0), т.к. часть этих точек использовалась при построении прямых. В общем случае координаты точки пересечения двух прямых определяют совместным решением их уравнений, например, для точки С, которая является точкой пересечения (2) и (3) прямых необходимо решить систему:

Сложим уравнения, получим: . Откуда

Найдем координаты образов точек O, A, B, C, D в линейном преобразовании, определяемом целевыми функциями:

O(0; 0):

Таким образом, O(0; 0) > O(0; 0).

A(0; 5):

Таким образом, A(0; 5) > A(-10; -5).

B(4; 6):

Таким образом, B(4; 6) > B(-4; -14).

C(5; 2):

Таким образом, C(5; 2) > C(6; -12).

D(3; 0):

Таким образом, D(3; 0) > D(6; -6).

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

3. В критериальной плоскости найдем границу Парето - северо-восточную границу области OABCD.

Точкой утопии, в которой достигается максимум одновременно по двум критериям U и V, является точка P: через самую высокую (северную) точку области OABCD провели горизонтальную прямую (через точку O) и через самую правую (восточную) точку области OABCD провели вертикальную прямую (через точки C и D); точка - точка пересечения горизонтальной и вертикальной прямой.

4. На границе Парето найдем идеальную точку - точку, наиболее близко расположенную к точке утопии. В нашем случае это основание перпендикуляра, опущенного из точки утопии Р на отрезок OD - точка M

Найдем координаты точки M. Для этого найдем уравнение прямой OD. Воспользуемся уравнением прямой, проходящей через две точки: (0; 0), D(6; -6)

Найдем уравнение перпендикуляра, опущенного из точки утопии P на отрезок OD. Воспользуемся уравнением прямой с точкой и вектором нормали:

,

Координаты точки М:

Сложим уравнения: . Решение уравнения

Таким образом, М(3; -3), а значит, компромиссное решение позволит достигнуть значений целевых функций: U = 3, V = -3.

5. Найдем координаты точки в плоскости xOy, которой соответствует точка М критериальной плоскости. Для этого решим систему уравнений:

Получили, что компромиссным решением метода идеальной точки является M(1,5; 0), в которой критерии достигают значений U = 3, V = -3.

Эта точка принадлежит отрезку OD.

Ответ: M(1,5; 0), U_max (1,5; 0)= 3, V _max(1,5; 0)= -3.

Вопросы для самопроверки

1. Какая задача называется многоцелевой?

2. Каким своством обладают точки множества Парето?

3. Как найти множество Парето?

4. Что такое точка утопии?

5. В чем суть метода идеальной точки? Какая точка называется идеальной?



4. Нелинейное программирование

В общем случае задача нелинейного программирования (НП) состоит в нахождении экстремума (минимума или максимума) функции

Z = f (x₁,…, x_n) min (max),

на множестве, задаваемом ограничениями в виде равенств и (или) неравенств

g_i (x₁,…, x_n) = b_i, .

g_i (x₁,…, x_n) ? b_i,

Так же могут быть условия неотрицательности переменных.

Предполагается, что среди функций f и g_i () есть хоть одна нелинейная.

Любой n-мерный вектор x = (x₁,…,x_n), удовлетворяющий ограничениям задачи, называется допустимым решением, а множество X всех таких векторов -- областью допустимых решений (ОДР).

Перечислим свойства задач НП, которые существенно усложняют процесс их решения по сравнению с задачами линейного программирования:

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

2. Глобальный максимум (минимум) может достигаться как внутри области, так и на ее границах (где он, вообще говоря, будет не совпадать ни с одним из локальных экстремумов).

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

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

4.1 Графическое решение задачи нелинейного программирования

Графический метод можно использовать для решения задачи НП, которая содержит две переменных х₁ и х₂, например задачи следующего вида:

Z = f(x₁, x₂) > min (max);

g_i(x₁, x₂) ? b_i, .

Чтобы найти ее оптимальное решение, нужно выполнить следующие действия:

1. Найти ОДР, определяемую ограничениями задачи. Если окажется, что эта область пуста, то это означает, что задача не имеет решения.

2. Построить семейство линий уровня целевой функции f(х₁, х₂) = C при различных значениях числового параметра С.

3. При решении задачи на минимум определить направление убывания, а для задачи на максимум -- направление возрастания линий уровня целевой функции.

4. Найти точку ОДР, через которую проходит линия уровня с наименьшим в задаче на минимум (соответственно, наибольшим в задачи на максимум) значением параметра С. Эта точка будет оптимальным решением. Если целевая функция не ограничена снизу в задаче на минимум (сверху -- в задаче на максимум), то это означает, что задача не имеет оптимального решения.

5. Найти координаты точки оптимума и определить в ней значение целевой функции.

Отметим, что в отличие от задачи линейного программирования точка оптимума в задаче НП не обязательно находится на границе ОДР. Ею также может быть внутренняя точка этого множества.

Пример1

Найти максимальное и минимальное значение функции

При условиях

Это задача НП, т.к. целевая функция нелинейна.

Областью допустимых решений является треугольник АВС.

Строим линии уровня - концентрические окружности с центром в точке Е(3;4). Видно, что минимум целевой функции достигается в точке D -точке касания окружности и области, максимальное значение функция принимает в точке С - угловой точке множества.

Найдем координаты точке D, для этого воспользуемся равенством угловых коэффициентов прямой и касательной к окружности. Для прямой выразим x₂: , следовательно, k₁=10. Для касательной к окружности угловой коэффициент - это производная x₂ (находим производную неявной функции). Продифференцируем по x₁ обе части уравнения окружности:

Из условия получаем уравнение
или . Это одно из уравнений для нахождения координат точки D. Точка D лежит на прямой . Получаем систему:

Решая систему, находим

Следовательно, .

Координаты С найдем из системы: . Решив которую, находим С(2;12).

Ответ: ,

4.2 Метод множителей Лагранжа

Рассмотрим частный случай задачи НП, предполагая, что система ограничений содержит только уравнения, отсутствуют условия неотрицательности и функции f (x₁,…, x_n) и g_i (x₁,…, x_n) непрерывны вместе с частными производными.

Z = f (x₁,…, x_n) min (max);

g_i (x₁,…, x_n) = b_i, .

Чтобы найти решение этой задачи вводят переменные , называемые множителями Лагранжа и составляют функцию Лагранжа:

L(x, л) = L(x₁,…, x_n, л ₁,…, л _m) = f (x₁,…, x_n) + л_i (b_i - g_i (x₁,…, x_n)),

находят частные производные функции Лагранжа по всем переменным x_j и л_i и приравнивают их нулю для нахождения стационарных точек функции Лагранжа. Получается система n + m уравнений:

;

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

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



4.3 Решение задач выпуклого программирования

Рассмотрим задачу НП:

Z = f (x₁,…, x_n) min (max);

g_i (x₁,…, x_n) ? b_i, .

x_i ? 0,

Функция f называется выпуклой на выпуклом множестве Х, если для любой пары точек x, yХ и любого числа б(0, 1) справедливо соотношение

f(б x + (1 - б) y) ? б f(x) + (1 - б) f(y).

Функция f называется вогнутой на выпуклом множестве Х, если для любой пары точек x, yХ и любого числа б(0, 1) справедливо соотношение

f(б x + (1 - б) y) ? б f(x) + (1 - б) f(y)

Функция f называется строго выпуклой (строго вогнутой), если неравенства в соотношениях являются строгим для всех x ? y, т.е. знак неравенства "<" (соответственно, ">").

Очевидно, что если f -- выпуклая функция, то g = -f -- вогнутая функция. Сумма выпуклых (вогнутых) функций -- выпуклая (вогнутая) функция. Линейная функция является как выпуклой, так и вогнутой функцией.

Простейший пример выпуклой функции: z = х², а вогнутой: z = .

Множество допустимых решений задачи НП удовлетворяет условию регулярности, если существует, по крайней мере, одна точка X_i из ОДР такая, что g_i(X_i)<b_i.

Задача НП является задачей выпуклого программирования, если она удовлетворяет следующим условиям:

1) целевая функция f - выпукла (вогнута);

2) все функции g_i в ограничениях выпуклые.

Легко проверить, что если g -- выпуклая (вогнутая) функция, то для любого числа b множество {х | g(x) ? (?) b} -- выпуклое. Поэтому ОДР в задаче выпуклого программирования - выпуклое множество. Выпуклым будет и множество оптимальных решений. Если же ЦФ -- строго выпуклая (вогнутая) функция, то множество точек ее минимума (максимума) состоит из единственной точки.

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

Составим функцию Лагранжа для задачи выпуклого программирования:

L(x, л) = L(x₁,…, x_n, л ₁,…, л _m) = f (x₁,…, x_n) + л_i (b_i - g_i (x₁,…, x_n)).

Точка называется седловой точкой функции Лагранжа, если выполняется .

Теорема Куна-Таккера

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

Если предположить, что функции f и g_i непрерывно дифференцируемы, то можно записать условия Куна-Таккера, определяющие необходимые и достаточные условия того, чтобы точка была седловой точкой функции Лагранжа, т.е. являлась решением задачи выпуклого программирования. Эти условия имеют вид:

Предпоследнее условие означает, что если множитель Лагранжа положителен, то соответствующее ему ограничение в точке оптимума обязательно должно быть равенством. Если же ограничение не является равенством в точке оптимума, то его множитель Лагранжа равен нулю. Это условие аналогично условию дополняющей нежесткости в задачелинейного программирования.

В отличие от классической задачи условной оптимизации на множители Лагранжа накладывается условие неотрицательности.

Множители Лагранжа допускают интерпретацию, аналогичную интерпретации оптимальных оценок ограничений в задаче линейного программирования. Так множитель Лагранжа i-го ограничения характеризует величину изменения оптимального значения целевой функции при увеличении правой части этого ограничения на единицу и фиксированных значениях остальных ограничений.

Однако в отличие от задачи линейного программирования величина не равна в точности изменению оптимального значения целевой функции при увеличении правой части i-го ограничения на единицу, а дает лишь приближенную оценку этого изменения.

Пример 2

Решить задачу выпуклого программирования средствами MS Excel.

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

Решим задачу с использованием настройки Поиск решения. Для решения нашей задачи создадим в Excel книгу с именем «Решение задачи нелинейного программирования». Подготовим данные на листе.

Сначала определим ячейки, в которые будет помещен результат решения. Пусть это будут ячейки В2, С2, сделаем у них заголовки. В этих ячейках нет данных, их должен будет рассчитать Excel, они выделены цветом. Далее заполним коэффициенты при неизвестных и правые части системы ограничений (строки 5-7). Заведем строку 9 для целевой функции. Цветом выделена ячейка, в которой будет находиться значение целевой функции для найденного оптимального решения.

В ячейки D5, D6, D7 ведем формулы для зависимостей левых частей системы ограничений, а в ячейку E9 - формулу для зависимости целевой функции.

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

Далее нажимаем кнопку Параметры и в появившемся окне Параметры поиска решений устанавливаем флажок неотрицательные значения и нажимаем OK.

В окне Поиск решения после нажатия кнопки Выполнить появляется окно Результаты поиска решения, в котором выбираем сохранение найденных значений и нажимаем кнопку ОК.

Результаты поиска решений (для ячеек В2 и С2 установлены числовые форматы с 0 знаками после запятой):

Получили .

Покажем, что существует , при которой в точке минимума выполняются условия Куна-Таккера.

Перепишем задачу в виде:

Составим функцию Лагранжа . Для данной задачи она имеет вид:

Найдем частные производные:

Запишем условия Куна-Таккера:

Подставим в систему координаты оптимальной точки (4;3), найденной средствами Excel.

Произведение равно нулю, если один из множителей равен нулю. Из первого и второго уравнений следует, что выражения в скобках равны нулю. Из четвертого и пятого уравнений следует, что ₂=₃=0. Подставим их в остальные уравнения.

Откуда, находим решение: ₁=2, ₂=0, ₃=0. Следовательно, точка (4;3) является точкой экстремума.

Вопросы для самопроверки

1. В чем отличие НП от задачи ЗЛП?

2. В чем особенности нахождения решения задач НП?

3. Для каких задач НП разработаны методы решения?

4. В чем особенности графического решения задачи НП?

5. Какая функция называется функцией Лагранжа? Какой смысл множителей Лагранжа?

6. Сформулируйте условия Куна-Таккера.

7. Какие особенности имеет решение задачи выпуклого программирования?



Литература

1. Акулич И.Л. Математическое программирование в примерах и задачах. М.: Высшая школа, 1986.

2. Интрилигатор М. Математические методы оптимизации и экономическая теория. М.: Айрис-Пресс, 2002.

3. Исследование операций в экономике/ Под ред. Н.Ш. Кремера. М.:, ЮНИТИ, 2005.

4. Конюховский П. В. Математические методы исследования операций в экономике СПб: Питер, 2000.

5. Косоруков О.А,, Мищенко А.В. Исследование операций. М: Экзамен, 2003.

6. Кузнецов А.В., Сакович В.А., Холод Н.И. Высшая математика. Математическое программирование. Минск: Вышэйшая школа, 1994.

7. Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б. Математическое программирование. М.: Высшая школа, 1986.

8. Эддоус М., Стэжфилд Р. Методы принятия решений. М.: Аудит, ЮНИТИ, 1997.

9. Шикин Е. В., Шикина Г. Е. Исследование операций. М.: ТК Велби, Проспект, 2006.

Размещено на Allbest.ru