logo
Шепеленко О

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

Условно задачи математического программирования, которые заключаются в исследовании функции на экстремум, на переменные которой наложены определенные ограничения, можно разделить на задачи:

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

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

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

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

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

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

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

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

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

Рассматривают так же отдельные классы задачи дробно-линейного программирования, когда система ограничений являются линейной, а целевая функция – дробно-линейная; задачи параметрического программирования, когда система ограничений являются линейной, а целевая функция содержит параметр.

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