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

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

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

К ним относятся задачи: нелинейного программирования, линейного программирования, целочисленного программирования, дробно-линейного программирования, параметрического программирования, сепарабельного программирования, квадратичного программирования, динамического программирования, стохастического программирования, геометрического программирования и другие.

Существуют различные признаки классификации этих задач.

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

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

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

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

Для решения выпуклых задач разработаны многочисленные численные методы, приспособленные для решения на ЭВМ, связанные с понятием градиента целевой функции и основной идеей о том, что функция наиболее быстро убывает, если двигаться в направлении, противоположном градиенту. К ним относятся метод градиентного спуска, метод сопряженных градиентов и т.д. Но есть и методы, основанные на других идеях: метод штрафных функций, многочисленные варианты метода случайного поиска и т.д.

Другой классификационный признак – способ задания области ограничений задачи (1), т.е. множества G. Возможны варианты:

1) ограничений нет вообще,

2) ограничения заданы системой уравнений,

3) ограничения заданы системой неравенств.

Для 1-го случая, если ограничения на переменные не накладываются (т.е. G = Rⁿ), а целевая функция является непрерывной дифференцируемой функцией, то задача (1) называется классической задачей на экстремум (безусловный экстремум). В основе ее решения лежит теория дифференциального исчисления, в частности, теория экстремумов и опирающиеся на нее методы.

Для 2-го случая, если является непрерывной дифференцируемой функцией, а множествоG задано системой уравнений , где– непрерывно дифференцируемые скалярные функции,b_i – действительные числа, то задача (1) называется классической задачей на условный (относительный) экстремум. Обычно эти задачи сводятся к задачам безусловной оптимизации с помощью метода множителей Лагранжа.

В 3-м случае задачи с ограничениями-неравенствами разделяют на два класса – нелинейные и линейные.

Задача вида

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

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

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

где D – симметричная матрица размерности n x n, – вектор коэффициентов целевой функции,А – матрица коэффициентов в системе линейных неравенств, – вектор действительных чисел.

Способы решения таких задач во многом определяются видом матрицы D: если D – положительно определённая матрица, то целевая функция будет выпуклой и любой её локальный минимум будет глобальным. Если D – отрицательно определённая матрица, то может быть несколько локальных минимумов, но глобальный минимум, если он существует, достигается обязательно на вершине допустимой области. В общем случае, когда собственные числа матрицы D имеют разные знаки, задача сильно усложняется, так как глобальный минимум может достигаться где угодно – и внутри области и на её границе.

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

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

Если целевая функция и ограничения (уравнения и неравенства) – линейные, то получим задачу линейного программирования (ЗЛП).

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

- геометрический метод;

- простой симплекс-метод и его модификации:

- симплексные таблицы;

- метод искусственного базиса;

- симплекс-метод с обратной матрицей;

- двойственный симплекс-метод;

- метод последовательного сокращения невязок и другие.

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

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

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

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

Частным случаем задачи целочисленного программирования относятся задачи булевского программирования, где переменные x_j принимают всего два значения – 0 и 1. Наиболее известные из этих задач – это задача о назначениях (какого работника на какую работу поставить), задача выбора маршрута (задача коммивояжера, задача почтальона), задача о максимальном паросочетании и т.д.

Методы и модели линейного программирования используются при решении следующих задач:

- планирование товарооборота;

- построение торговой сети;

- распределение сотрудников по операциям;

- распределение ресурсов;

- организация рациональных перевозок (транспортная задача);

- организация рациональных закупок продуктов (задача о диете);

- оптимальное производство продукции;

- задача о раскрое материала и др.

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

Найти при условиях

,

где D – конечное или счетное множество. Тогда условие – условие дискретности. Чаще всего условие дискретности разделяют по отдельным переменным следующим образом:.

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

Задачи геометрического программирования – задачи наиболее плотного расположения некоторых объектов в заданной двумерной или трехмерной области. Такие задачи встречаются в задачах раскроя материала для производства каких-то изделий и т.п. Имеющиеся здесь алгоритмы в основном ориентированы на сокращение перебора вариантов с поиском локальных минимумов.

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

Динамическое программирование – это вычислительный метод для решения экстремальных задач определенной структуры, который возник и сформировался в 1950-1953г.г. благодаря работам Р. Беллмана над динамическими задачами управления запасами. Динамическое программирование представляет собой направленный последовательный перебор вариантов, который обязательно приводит к глобальному максимуму.

Основные свойства задач, к которым возможно применить принцип динамического программирования:

- Задача должна допускать интерпретацию как n-шаговый процесс принятия решений.

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

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

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

Задача о выборе траектории, задача последовательного принятия решения, задача об использовании рабочей силы, задача управления запасами – классические задачи динамического программирования.