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

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

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

Математическое программирование возникло в 30-е годы ХХ века. Венгерский математик Б. Эгервари в 1931 году решил задачу, называемую проблемой выбора. Американский ученый Г.У. Кун обобщил этот метод, после чего он стал называться «венгерским методом». В 1947 году американский ученый Дж. Данциг описал один из основных методов решения задач линейного программирования, получивший название «симплексный».

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

В зависимости от вида целевой функции и структуры ограничений в математическом программировании выделяют следующие основные разделы (рис.6.4):

Если целевая функция (6.1) и система ограничений (6.2)-(6.3) линейны относительно проектных параметров, то задача математического программирования называется задачей линейного программирования (ЛП). Если нелинейны – нелинейного программирования. Если ставится дополнительное условие, чтобы переменные были целочисленны – задача целочисленного программми-рования и т.п.

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

При этом в практических задачах число переменных и ограничений обычно столь велико, что если просто перебирать все точки, " подозреваемые" на экстремум, то вряд ли даже ЭВМ справится с такой задачей.