Тема 5. Лекция 6.

нелинейное программирование (НП)

1. Постановка задачи НП

2. Эколого-экономическая интерпретация задачи НП

3. Геометрическая интерпретация задачи НП

4. Метод множителей Лагранжа (ММЛ)

5. Обзор рассмотренных методов.

1. Постановка задачи нп

В общем виде задача НП состоит в определении max/min значения

f (x₁, x₂, … x_n) (1)

при условии, что ее переменные удовлетворяют соотношениям

g_i(x₁, x₂, …, x_n)  b_i (i = 1, k)

g_i(x₁, x₂, …, x_n) = b_i (i = k + 1, m),

где f и g_i некоторые известные функции n переменных, а b_i – заданные числа.

Имеется в виду, что в результате решения задачи будет определена точка Х* = (х₁*, х₂*, … х_n*), координаты которой удовлетворяют соотношению (2), причем для всякой другой точки, отвечающей условиям (2), выполняется

F* (x*₁, x*₂, … x*_n)  f (x₁, x₂, … x_n)

Если f и g_i – линейные функции, то это будет задача линейного программирования.

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

В евклидовом пространстве En система ограничений (2) определяет ОДР. В отличие от задачи ЛП она не всегда является выпуклой.

Если определена ОДР, то нахождение решения задачи НП сводится к определению такой точки этой области, через которую проходит гиперповерхность наивысшего (наинизшего) уровня: f (x₁, x₂, … x_n) = h, причем эта точка может находиться как на границе ОДР, так и внутри нее.

2. Эколого-экономическая интерпретация задач нп

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

Подраз-деления	Капитало-вложения, тыс.р.	Эффект, тыс. руб.	Капитало-вложения, тыс.р.	Эффект, тыс. руб.	Капитало-вложения, тыс.р.	Эффект, тыс. руб.
I	От 10 до 30	7,3	30…60	8,0	60	10
II	От 10 до 40	6,2	40…70	8,6	 70	9,1
III	От 10 до 50	9,1	50…60	9,8	 60	9,5

Математическая модель

Обозначим капиталовложения, распределенные между тремя подразделениями х₁, х₂, х₃.

Эффект по каждому подразделению: С₁(Х₁), С₂(Х₂), С₃(Х₃).

F = C₁(X₁) X₁ + C₂(X₂)X₂ + C₃(X₃)X₃ = f (X₁, X₂, X₃)  max

X₁ + X₂ + X₃ = 220

X₁, X₂, X₃  0.

Известно, что можно регулировать степень чистоты ОС путем нормирования, т.е. введения допустимого уровня загрязнителя в среде. Такое регулирование можно осуществлять путем выдачи производителю лицензий, условием для получения которых являлось бы соблюдение установленных норм качества ОС. Естественно, что каждое предприятие – источник загрязнения несет определенные затраты на устранение загрязнения.

Полные затраты (С) на устранение загрязнения складываются из суммы затрат С_i для каждого загрязняющего среду:

,

где Q_i – масса устраненного загрязняющего вещества i-м предприятиям.

Для обеспечения установленного уровня качества ОС полная масса загрязняющего вещества Q, подлежащего устранению, определяется как:

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

Таким образом целевая функция

.

Ограничения: .

В общем случае это задачи с размерностью  2. Их решение сводится к минимизации так называемой функции Лагранжа .