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 = чертежу максимальное значение Z достигается в точке (0;0) Zmax = = 2 • 25 + 49 = 99; Zmin достигается в точке Z), в которой эллипс касается области ОАВС. Для нахождения координат точки D приравняем угловые коэффициенты первой прямой и целевой

фу™:, - - ,/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