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

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

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

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

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

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

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

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

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

К математическому программированию относятся также методы решения экстремальных задач с бесконечным числом переменных – бесконечномерное программирование.

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