2.5.1. Условная оптимизация методом Лагранжа и условия Куна-Таккера
Проектирование технических объектов всегда включает в себя элементы оптимизации – стремление получить наилучший вариант среди возможных вариантов при варьировании значений параметров объекта при заданной структуре -- параметрическая оптимизация. Внутренние параметры объекта проектирования n-мерный вектор х=(x1, x2,.. xn), выходные параметры – m-мерный вектор у=(y1, y2,.. ym), а внешние параметры (параметры окружающей среды) – l-мерный вектор q=(q1, q2,..ql).
Модель объекта проектирования имеет вид f(x,q), где f –вектор-функция. Если внешние параметры q известны и фиксированы, то y=f(x), и такая
модель – детерминированная модель объекта. Общий подход к решению
задачи поиска минимума или максимума функции f(x) при наличии
ограничений gj(x) = bj на ее переменные x = (x1,x2…xn), задача условной
оптимизации решается методом Лагранжа. Метод базируется на составлении лагранжиана L(x) = f(x) +∑λjgj(x), где λj, j =1,2…m, m ≤ n – неопределённые множители Лагранжа, которые представляют собой оценку изменений оптимального значения целевой функции f(x) при малых изменениях правых частей bj ограничений gj(x) = bj. Суть предложенного Лагранжем метода -- перенос ограничений в целевую функцию. Практическое применение метода Лагранжа сводится к вычислению частных производных лагранжиана по х и приравниванию их нулю.
Обобщением метода множителей Лагранжа являются условия Куна-Таккера. В отличие от него, ограничения, накладываемые на переменные, представляют собой не уравнения, а неравенства:
В задаче нелинейной оптимизации требуется найти значение многомерной переменной х, минимизирующее целевую функцию f(x) при условиях, когда на переменную 
наложены ограничения типа неравенств 
, а компоненты вектора неотрицательны.
Необходимые условия минимума функции f(x), реализующегося при х = х*:
● стационарность min L(x) = L(x*),
x
● дополняющая нежёсткость λjgj(x*) = 0, j = 1,,,m,
● неотрицательность λj≥ 0, j =1,2…m.
Достаточные условия: кроме условий стационарности, дополняющей нежёсткости и неотрицатености выполняется условие положительности λj.. Максимум функции f(x) достигается при минимизации -- f(x).
2.5.2. Пример из экономики
Оптимальное распределение имеющихся ресурсов для достижения цели (наибольшего дохода или наименьших затрат) подбор наиболее выгодной производственной программы выпуска продукции при использовании ограниченных источников сырья. Пусть планируется выпуск четырёх видов продукции Р1, Р2, Р3,Р4, ожидаемый доход от реализации единицы продукции
каждого вида оценивается в 14,19, 14, 11; по каждому виду требуется сырьё S1, S2, S3, располагаемые запасы которого оцениваются соответственно в 35, 30, 40. Расход сырья на единицу продукции задаётся матрицей 3х4
| Р1 | Р2 | Р3 | Р4 | |
| S1 | ||||
| S2 | ||||
| S3 |
Выпуск продукции в объёмах х1, х2, х3,х4 обеспечит максимальный доход, когда f(x) =14х1+ 10 х2 + 14х3 + 11х4→max при выдерживании ограничений на располагаемые ресурсы сырья
х1+ 2х2 + 2х3 + 3х4 ≤35,
х1+ х2+ 2х3 + 3х4 ≤ 30,
2х1+ х2 + 2х3 + х4 ≤ 40.
Прямая задача f(x)→max. Двойственная задача – минимизация общих затрат на ресурсы при ценах у1, у2, у3 за единицу каждого вида f(у) = 35у1 + 30у2+ 40у3 →min. Расходы репсурсов по видам продукции не должны превышать доходов от реализации, поэтому при оптимизации их f(у)→min необходимо учесть ограничения
4у1 + 4у2+ 2у3 ≤ 14,
2у1 + 4у2+ у3 ≤ 10,
2у1 + 2у2+ 2у3 ≤ 14,
3у1 + 3у2+ 4у3 ≤ 11.
Решение прямой и двойственной задач сводится к составлению лагранжианов со своими неопределенными множителями λ и μ, которые
определяются из уравнений – приравниваемых нулю частных производных
лагранжианов по своим переменным х и y. Выполнение условий дополнительной нежёсткости даёт совместное решение прямой и двойственной задач. Решение пары двойственных задач f(x) →max, f(y) →min x*= (0; 5; 12,5; 0), y*= (3; 4; 0).
Пара векторов x*, y*называется седловой точкой функции Лагранжа L(x,y), ; в седловой точке выполняется условие L(x*, y*)= max min L(x, y) = min maxL(x, y). Седловая точка функции Лагранжа – аналог седловой точки в теории антагонистиических игр (раздел 2.6)