Основные принципы реализации методов оптимизации

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

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

Задачи математического программирования классифицируются в зависимости от вида целевой функции и свойств допустимой области ограничений 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 -м шаге не должен оказывать влияния на предыдущие решения, кроме необходимого пересчета переменных.

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

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

- последовательное приближение;

- последовательный анализ вариантов;

- случайный поиск.

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

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

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

Дата добавления: 2014-01-15