3.12. Устойчивость оптимизационного решения

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

Рассмотрим простейшую задачу линейного программирования:

Ее оптимальное решение включает и .

Двойственные оценки соответствуют решению системы уравнений:

Пусть коэффициент 1,4 в целевой функции заменяется на случайный параметр С. Двойственные оценки у₁ и y₂ в этом случае равны:

Для оптимального решения задачи необходимы поло­жительные у₁ и у₂: 42 - 25С ≥ 0; 40С - 30 ≥ 0. Отсюда сле­дует, что решение и остается опти­мальным для следующего интервала значений: 0,75 ≤ С ≤ 1,68. Если параметр С выходит за пределы допустимого интервала значений, то необходимо получить новое реше­ние задачи.

Аналогичное исследование можно выполнить для вы­явления интервалов изменения ресурсов в ограничениях. Пусть система ограничений имеет вид:

где d₁, d₂, d₃ - свободные переменные; - случайный параметр. В оптимальном решении , и, следова­тельно, решение этой системы уравнений будет иметь вид

Данное решение имеет только структурную устойчи­вость для интервала значений от -142⁶/₇ до 19¹⁸⁷/₂₀₂.

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

4.1. Классификация и общая постановка задач нелинейного программирования

Задачи нелинейного программирования - большой класс разнообразных задач, из которых будем рассматривать только сводящиеся к задачам линейного программирования.

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

Задачи, в которых зависимости между переменными в целевой функции и/или в ограничениях нелинейны, назы­вают задачами нелинейного программирования.

Если обозначить целевую функцию и ограничения че­рез обобщенную функцию h(х_j), то все многообразие задач нелинейного программирования можно свести к классифи­кации (см. табл. 16).

В общем виде задача НЛП состоит в определении мак­симума (минимума) функции

(1)

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

(2)

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

Таблица 16

Отрезок, соединяющий две точки		Вид функции	Число оптимумов	График
Совпадает	0	Линейная	2
Выше вершины	>0	Выпуклая вниз	3
Ниже вершины	<0	Выпуклая вверх (вогнутая вниз)	3
По обе стороны от вершины	Меняет знак	Смешанная	Несколько

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

при max целевой функции или

при min целевой функции.

Если f и g_i - линейные функции, то задача (1), (2) - задача линейного программирования.

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

Нелинейные задачи решаются с помощью метода кусочно-линейной аппроксимации или метода множителей Лагранжа, В задачах квадратичного программирования применяется ме­тод Била, Баранкина-Дорфмана, градиентные методы (метод Франка-Вулфа, штрафных функций, метод возможных на­правлений). В градиентных методах итерационный процесс осуществляется до того момента, пока градиент функции f(x) в очередной точке x_k+1 не станет равным нулю или пока (достаточно малое положительное число, ха­рактеризующее точность полученного решения).