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

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

Одной из основных задач оптимизации является так называемая задача математического программирования, которая в общем случае состоит в нахождении такого вектора х = (х₁, х₂, …, х_n), при котором достигается наибольшее или наименьшее значение непрерывной функции f(x), при условии, что x ∈ M, где M – допустимая область, представляющая собой некоторое подмножество всего пространства.

Математическая форма записи этой задачи (для определённости сформулируем её как задачу максимизации, хотя она ничем не отличается от задачи минимизации) такова:

max{f(x) | x ∈ M}.

Функцию f(x) называют целевой, а условия, описывающие множество М, – системой ограничений. В зависимости от вида этой функции и свойств допустимой области M задача математического программирования относится к тому или иному классу.

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

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

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

• отсечения;
• комбинаторные (переборные);
• приближённые.

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

1. Методы отсечения. Исторически исследованиям задач дискретной оптимизации предшествовало развитие теории и методов линейного программирования, в частности, создание Джорджем Данцигом симплекс-метода как универсального метода решения задач линейного программирования.

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

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

Методы отсечения сводят решение задачи целочисленного линейного программирования к решению последовательности специальным образом построенных задач линейного программирования. Впервые эта идея для задач целочисленного линейного программирования была высказана тем же Дж. Данцигом.

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

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

Далее снова решается задача линейного программирования с дополнительно введенным ограничением (отсечением), процесс повторяется до получения целочисленного решения.

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

Реализация метода отсечения предполагает решение следующих трёх проблем:

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

Эти проблемы впервые были решены с помощью алгоритмов Р. Гомори, который сформулировал универсальное правило формирования отсечений и доказал конечность процесса отсечений.

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

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

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

2. Комбинаторные (переборные) методы. Здесь необходимо вначале определить понятие оптимизационно-комбинаторной задачи. Это можно сделать следующим образом.

Пусть имеется множество из n элементов. На этом множестве задаётся множество комбинаций P = {p₁, p₂, …, p_n}, где под комбинациями понимаются сочетания, подстановки, перестановки, свойственные каждой конкретной задаче. На множестве Р задаётся некоторая функция f. В оптимизационно-комбинаторной задаче ищется экстремум функции f (максимум или минимум) и отыскиваются те элементы множества P, на которых функция f экстремальна.

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

В общем виде задачу можно сформулировать так: из заданного множества предметов со свойствами «стоимость» и «вес» требуется отобрать подмножество с максимальной полной стоимостью, соблюдая при этом ограничение на суммарный вес.

При решении оптимизационно-комбинаторных задач необходимо следующее:

• нужно уметь перебирать множество значений функции f;
• вычислять эти значения и сравнивать.

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

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

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

В настоящее время наиболее широко применяемыми являются три группы методов:

• локальная оптимизация;
• случайный поиск;
• методы ветвления.

Рассмотрим кратко суть этих методов.

При локальной оптимизации для каждой комбинации p_i ∈ P определяется множество Q_i – множество комбинаций, соседних с p_i. Исходной операцией является случайный выбор начальной комбинации. Затем на множестве Q_i находят локальный экстремум. Этот процесс повторяется многократно, и среди полученных локальных экстремумов выбирается наименьший и именно он принимается за приближённое значение.

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

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

• признаки выбираются заранее путём анализа условий задачи;
• признаки получают из анализа уже полученных решений.

3. Методы ветвления. Впервые метод ветвей и границ был предложен для решения задач целочисленного линейного программирования.

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

1. Алгоритмы, строящие дерево подзадач исходной задачи (например, алгоритм Лэнд и Дойга, предложенный для решения задач целочисленного программирования. В этом методе строится дерево задач линейного программирования, добиваясь постепенного удовлетворения условий целочисленности – вариант метода отсечений);
2. Алгоритмы, строящие дерево недопустимых решений (например, аддитивный алгоритм Балаша и его модификации). Этот метод применяется для решения задач линейного программирования с булевыми переменными;
3. Алгоритмы, строящие дерево допустимых решений (например, метод решения задач о коммивояжере).

Для примера ввиду большой популярности и распространённости задачи о коммивояжере, опишем последовательность действий (алгоритм) в методе ветвей и границ для этой задачи:

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

Процесс продолжается до получения полной последовательности.

Если длина маршрута, соответствующая эталонной последовательности, меньше длины эталонной ветви, то её принимают за эталонную.

Последняя эталонная последовательность будет оптимальной.

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

• задача о ранце;
• задача о коммивояжере;
• задача минимизации среднего времени обработки партии деталей;
• задача о назначениях;
• задача о покрытии;
• задача компоновки;

и другие.

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

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

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

На основе этих методов иногда разрабатываются гибридные методы.

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

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

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

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

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

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

Например, вместо поиска x ∈ M, для которого f(x) минимальна, ставится задача поиска такого x* ∈ M, что f(x₀) – f(x*) < ε или (f(x₀) – f(x*))/f(x*) < ε, ε > 0. То есть фактически условия подобного рода требуют поиска лишь точек, в которых функция существенно убывает, но минимума может и не достигать.

Основанием для перехода к приближённым методам являются такие признаки задачи:

• экспоненциальный (очень быстрый) рост объёма вычислений с ростом размерности задач; это явление получило название «проклятие размерности»;
• для точного решения задач большой размерности нужны мощные компьютеры, а приближённые решения можно получить на имеющихся;
• в прикладных задачах, как уже отмечалось, часто исходную задачу удаётся сформулировать лишь приближённо, тогда точное решение не имеет смысла и может представлять скорее теоретический интерес;
• исходные данные в прикладной задаче известны, как правило, приближённо, соответственно приближёнными являются и параметры модели, и поиск точного решения не оправдан.

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

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

А.А. Антонюк, кандидат физико-математических наук