Особенности задач дискретной оптимизации. Общие сведения о методах решения задач: методы отсечения, комбинаторные методы, приближенные методы

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

· методы отсечения для задач (частично) целочисленного линейного программирования;

· комбинаторные методы;

· приближенные методы.

Остановимся подробнее на этих методах.

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

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

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

· полученное нецелочисленное решение ему не удовлетворяет;

· любое целочисленное решение ему удовлетворяет.

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

· нахождение универсального правила формирования отсечений;

· доказательство конечности процесса отсечения;

· борьба с чрезмерным ростом размерности задач при добавлении ограничений.

Р. Гомори удалось решить эти проблемы, что позволило ему создать универсальный и реализуемый в вычислительном отношении алгоритм.

Трудности вычислительной реализации. В дальнейшем выявилась большая непредсказуемость в поведении различных алгоритмов отсечения. Вычислительный эксперимент показал, что существуют задачи сравнительно небольшой размерности, решение которых не удается получить при больших затратах машинного времени. В дальнейшем было найдено объяснение этого явления: было показано[4], что для некоторых вариантов алгоритма Гомори существуют задачи, в которых число отсечений быстро растет с ростом размерности задачи и ростом коэффициентов, а в текущих симплекс-таблицах появляются весьма большие числа.

Методы отсечения не нашли широкого применения при решении прикладных задач ЦЛП по следующим причинам:

· сложно определить, какое отсечение (из большого их числа) является сильнейшим;

· методы отсечения приспособлены в основном для решения чисто целочисленных задач, которые составляют лишь малую часть задач ДО, встречающихся в приложениях;

· методы отсечения не приспособлены для решения разреженных задач ЦЛП.

Алгоритмы этого типа рассматриваются подробнее ниже, в разделе 7.1.

Комбинаторные методы. Основная идея комбинаторных методов состоит в использовании конечности множества допустимых решений и замене полного их перебора сокращенным (направленным или неявным перебором). Если каким-либо образом удается показать, что подмножество не содержит оптимальных решений, то в дальнейшем задача (1.1) решается на множестве . Таким образом, главную роль в сокращении перебора играют оценка и отбрасывание неперспективных подмножеств, заведомо не содержащих оптимальных решений. Эта идея реализуется путем последовательного разбиения множества всех допустимых решений на подмножества. При этом среди подмножеств, последовательно порождаемых на каждом шаге процесса, могут обнаружиться как подмножества, не содержащие допустимых решений, так и подмножества, не содержащие оптимальных решений. Отбрасывание таких подмножеств позволяет заменить полный перебор частичным и тем самым уменьшает затраты вычислительных ресурсов.

Таким образом, комбинаторные методы основаны на двух элементах:

· последовательное разбиение множества решений на подмножества;

· оценивание получаемых подмножеств и отбрасывание неперспективных.

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

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

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

· метод последовательного анализа вариантов[5];

· метод ветвей и границ [10];

· локальные алгоритмы Ю.И. Журавлева [7];

· методы, основанные на последовательностных схемах[6];

· метод динамического программирования [20];

· аппроксимационно-комбинаторный метод[7];

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

Приближенные методы. Эти методы широко применяются при решении задач ДО вида (1.1), так как нахождение точного решения может потребовать значительных вычислительных ресурсов. Современные приближенные методы обычно являются комбинированными, т.е. содержат в себе элементы различных методов. В приближенных методах решение задачи производится обычно в два этапа: построение начального решения и улучшение начального решения.

При этом на первом этапе широко используются эвристические алгоритмы ‑ алгоритмы, основанные на правдоподобных, но не обоснованных строго предположениях о свойствах оптимального решения задачи. Примером эвристического алгоритма может быть алгоритм решения задачи коммивояжера, в котором на каждом шаге реализуется переход в ближайшую из оставшихся точку. Алгоритмы такого типа носят название «greedy» («жадные» или пожирающие алгоритмы).

Эти алгоритмы на каждом шаге решают «локальную» задачу оптимизации; полученное решение может быть сколь угодно далеким от оптимума. На втором этапе используются алгоритмы локальной оптимизации, связанные с введенным понятием окрестности; при этом можно использовать несколько алгоритмов этого типа, изменяя правила выбора окрестности. Приближенным методам посвящен раздел 7.2 главы 7.