Линейное программирование. Многомерная минимизация при наличии ограничений

Многомерная минимизация при наличии ограничений

Линейное программирование

Задача минимизации функции n переменных ¦(x) = (x ₁,…, x _n) на некотором множестве Х Еⁿ не совпадающая со всем пространством Еⁿ и заданном с помощью ограничений (равенств и неравенств) на координаты х_j (j = 1: n) точки х Î Eⁿ называется задачей математического программирования и в общем виде записывается:

X = { x Eⁿ | g_i (x) ≤ 0, i = 1: m }.

Математическое программирование − это область математики, разрабатывающая теорию и численные методы решения многомерных задач с ограничениями, т.е. задач на экстремум функции многих переменных с ограничениями на область изменения этих переменных.

Частным случаем этих задач, в которых отыскивается минимум или максимум некоторой линейной функции и ограничения представляются в виде равенств и неравенств, все переменные х_j удовлетворяют условию не отрицательности х_j ³ 0 (j = 1: n) являются задачи линейного программирования (ЛП).

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

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

Линейное программирование представляет собой наиболее часто используемый метод оптимизации (74% от общего числа применяемых оптимизационных методов).