10.1. Геометрическая интерпретация задач нелинейного программирования
^max,min = х2> •••> хп) (Ю.1)
при ограничениях
fi(xb х2, хп) > О, Xj > О, / = 1, mj = 1, л.
Если все неравенства преобразовать в уравнения, то получим классическую задачу на условный экстремум, которая может быть решена методом множителей Лагранжа.
Практически системы получаются трудно разрешимыми, поэтому ограничения преобразуют в неравенства, и задачу решают методами математического программирования. Существующие методы позволяют решать узкий класс задач.С помощью большинства вычислительных методов можно найти точку локального оптимума, но нельзя установить, является ли она точкой глобального (абсолютного) оптимума или нет.
Если в задачах линейного программирования точка экстремума является вершиной многогранника, то в задачах нелинейного программирования она может лежать в вершине многогранника, на ребре (грани) или внутри области. Если задача содержит нелинейные ограничения, то область допустимых решений не является выпуклой и кроме глобального оптимума могут существовать точки локального оптимума.
Рассмотрим несколько примеров решения задач графическим методом.
.2
Z
= 2(х - 5)2 + (у - 7)
х + 2у< 12; х + у< 9; х > 0; у > 0.
Решение
Построим область допустимых решений (рис. 10.1): У
Пример 10.1.
На этом же графике построим одну из семейства целевых функций, для этого преобразуем Z в каноническую форму
(х-5)2 (у-1)2 л ¦
±—+ ^ — = 1. Получим уравнение эллипса с полуосями
Z / Z Z
a = фу™:, - - ,/2 , - 6; 0 - «г - 5, ¦ * - 7,У; у' - -1/2 = -^* р; упрощая, получим: 4(х - 5) = у - 7. у-1 Решая совместно систему 4(х-5) = д>-7 х + 2д> = 12, находим координаты точки D (38/9; 35/9). ^min = 2(38/9 - 5)2 + (35/9 - 7)2 - 11. Пример 10.2. ^max, min ~ х\ х2 Xj + х2 < 4; Xj + х2 > 5; хх > 0; <7; х2 >6; х2 > 0. Решение В этом случае область допустимых решений не является выпуклой и состоит из двух отдельных частей (рис. 10.2). Минимальное значение функции Z = 11 достигается в точках А (1; 4) и L (4; 1). Функция Z имеет два локальных максимума: в точках D (2/3; 6); Z = 328/9 и в точке М (7; 4/7); Z = Точка М является точкой глобального максимума. ^9