Реферат: Линейное программирование

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

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

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

X = {x En|gi(x) ≤ 0, i = 1:m}.

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

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

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

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

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