<<
>>

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

<< | >>
Источник: Бережная Е.В., Бережной В.И.. Математические методы моделирования экономических систем: Учеб. пособие. — 2-е изд., перераб. и доп. — М.: Финансы и статистика,2006. - 432 е.. 2006

Еще по теме 10.1. Геометрическая интерпретация задач нелинейного программирования: