ВУЗ: Томский государственный университет систем управления и радиоэлектроники
Категория: Учебное пособие
Дисциплина: Дискретная математика
Добавлен: 28.11.2018
Просмотров: 5519
Скачиваний: 27
81
3.9
Методы
решения
экстремальных
задач
комбинаторного
программирования
К настоящему времени разработано большое число алгоритмов
решения экстремальных задач комбинаторного программирования.
Наиболее перспективные из них выделились в отдельную область
комбинаторного программирования. Общая идея этих методов со-
стоит в замене полного перебора всех вариантов частичными пере-
борами меньших объемов. При реализации этой идеи отыскивают
подмножества, заведомо не содержащие искомого экстремума и
сужают область перспективных вариантов.
Зачем это делается? Дело в том, что несмотря на конечное чис-
ло возможных решений, полный их перебор и др. более тонкие точ-
ные методы дают для задач реальной размерности (например, число
исходных объектов) такие объемы вычислений, что требуемые за-
траты делают эти методы практически нереальными. Это явление в
комбинаторном программировании называется «проклятием раз-
мерности» (современный американский математик Р.Беллман).
Первая группа – точные методы. Среди них можно выделить
две разновидности: переборные и непереборные методы. К первой
разновидности относятся методы, которые не гарантируют, что не
придется «просматривать» все возможные решения.
Переборные методы:
1) метод разбиения и анализа (обобщение широко известного
метода ветвей границ);
2) метод отсечений;
3) метод полного перебора.
Ко второй разновидности относятся методы, для которых су-
ществует гарантия того, что будет просмотрена только
часть воз-
можных решений. Выделение «просматриваемого» подмножества
возможных решений требует определенных, иногда достаточно
больших вычислительных затрат. Поэтому непереборные методы не
всегда более экономичны, чем переборные.
Непереборные методы:
1) метод динамического программирования;
2) перестановочный метод.
Охарактеризуем кратко упомянутые методы.
Метод разбиения и анализа. Состоит из двух процедур: про-
82
цедуры разбиения множества возможных решений
0
X
на подмно-
жества и процедуры анализа подмножетв возможных решений с це-
лью исключения некоторых из них. Метод является итерационным.
На каждой итерации выполняются обе процедуры. При этом раз-
биению подвергается одно из подмножеств возможных решений,
полученных и не исключенных на предыдуцих итерациях. Процеду-
ра анализа нацелена на то, чтобы проверить отсутствие в расссмат-
риваемомм подмножестве допустимого решения, лучшего по значе-
нию целевой функции. Если это удается сделать, то такое подмно-
жество отбрасывается (исключается из дальнейшего рассмотрения).
Пользуясь терминологией теории графов (в данном случае это
наиболее удобно), можно представить метод как итерационную про-
цедуру построения дерева, вершины которого соответствуют от-
дельным подмножествам озможных решений. Перед началом пер-
вой итерации имеем одну вершину –
0
X
(корневая). Процесс закан-
чивается, когда из дерева ветвлений исключается корневая вершина.
Каждый этап построения дерева имеет свои критерии (прави-
ла):
1)
при выборе вершины для очередного ветвления;
2)
при выборе способа разбиения очередной вершины;
3)
при анализе соответствующей вершины.
Метод разбиения и анализа является наиболее общим методом,
применимым для решения любой задачи комбинаторного програм-
мирования. При этом эффективность метода тем выше, чем более
учтена при его реализации специфика решаемой задачи.
Метод отсечений. Метод состоит в замене исходной задачи
последовательностью вспомогательных задач с той же целевой
функцией, но с более широкими множествами допустимых решений.
Последовательность задач строится до тех пор, пока на некотором
шаге построения не окажется, что решение построений на этом шаге
задачи является допустимым решением исходной. Это решение,
очевидно и будет искомым оптимальным решением. В методе пред-
полагается, что вспомогательные задачи являются существенно бо-
лее простыми, чем исходная.
На
k
-м шаге метода решается
k
-я задача: определить на мно-
жестве
k
X
1
подмножество
k
X
2
векторов
k
x
, доставляющих функ-
83
ции
)
(
0
x
f
(целевой функции исходной задачи) экстремальное
(максимальное) значение.
Таким образом метод отсечений определяется характером по-
следовательности множеств
{ }
.
1
k
X
Обязательно должны выпол-
няться условия (для всех
,...
2
,
1
=
k
), определяющие идею метода:
k
k
k
k
k
X
X
X
X
X
X
1
1
2
1
1
1
1
1
,
,
⊄
⊃
⊃
+
+
В “отсекаемую” часть множества
k
X
1
всегда попадает множе-
ство
k
X
2
оптимальных решений
k
-го шага
Основной способ построения
{ }
k
X
1
.
Формируется некоторое ограничение (свое на каждом
k
-м шаге) в виде неравенства
,
0
)
(
≤
x
k
ϕ
которому удовлетворяют
все
k
X
x
1
∈
, но не удовлетворяют
k
X
x
2
∈
. Такое ограничение на-
зывается правильным отсечением. С помощью него и формируют
множество
1
1
+
k
X
для
)
1
(
+
k
-го шага:
{
}
.
0
)
(
,
/
1
1
1
≤
∈
=
+
x
X
x
x
X
k
k
k
ϕ
Метод полного перебора. По сравнению с предыдущими
существенно прост и применим по крайней мере в двух областях
комбинаторного программирования:
1)
задачи сравнительно малой размерности;
2)
“изощренные задачи” со сложным заданием целевой
функции и (или) множества допустимых решений.
При реализации метода последовательно просматриваются
все возможные решения задачи. Просмотр состоит в проверке до-
пустимости данного решения и (при положительном ответе) – в под-
счете для этого решения значения целевой функции. Эффективность
метода зависит от объема промежуточной информации, подлежащей
запоминанию, и от близости “соседних” возможных решений.
Метод динамического программирования
Идея метода. Решение одной задачи с заданным числом ис-
ходных объектов заменяется при решением целого семейства вспо-
могательных задач, в которых число исходных объектов меняется от
84
минимально возможного до заданного в основной задаче. Вспомога-
тельные задачи имеют ту же целевую функцию и ту же (либо близ-
кую) структуру множеств возможных и допустимых решений, что у
основной задачи. Метод эффективен тогда, когда при решении од-
них вспомогательных задач удается существенно использовать оп-
тимальные решения других. Таким образом метод состоит в после-
довательном решении некоторой совокупности задач, близких по
структуре к основной, с использованием получаемых в ходе проце-
дуры оптимальных решений. Заканчивается процедура получением
оптимальных решений вспомогательных задач, по которым доста-
точно эффективно строится оптимальное решение исходной задачи.
Такая замена процесса решения одной задачи процессом последова-
тельного решения некоторой совокупности вспомогательных задач
и определила название метода. Основоположник – Р.Беллман.
Перестановочный метод. Выбирается некоторый оператор,
действующий на множества допустимых решений, который может
быть применим к одним допустимым решениям и неприменим к
другим. (Например, в перестановке меняет местами соседние эле-
менты, для которых соответствующие исходные данные связаны
определенным соотношением. Если в некоторой перестановке ока-
жется, что для всех соседних элементов указанное соотношение не
выполняется, то оператор к этой перестановке не применим). Опера-
тор должен удовлетворять условию: допустимое решение к которо-
му оператор применим, должно переводиться им в новое допусти-
мое решение, не уступающее по значению целевой функции старо-
му. Очевидно, когда такой оператор выбран, оптимальное решение
следует искать среди неподвижных для него допустимых решений
(тех к которым он неприменим). Метод эффективен, когда число
таких неподвижных решений невелико. В частности, если все не-
подвижные допустимые решения доставляют целевой функции оди-
наковые значения, то любое из них является оптимальным решени-
ем. Во всех случаях, используя выбранный оператор, можно из лю-
бого допустимого решения получить неподвижное допустимое
(многократным использованием оператора).
Рассмотрим применение метода к задаче о деталях (частный
случай обработки N деталей на
2
=
M
станках). Смысл задачи со-
стоит в следующем. Допустимые решения могут быть представлены
85
в виде перестановок
π
из
N
Π
, задающих порядок обработки де-
талей. Можно показать, что перестановка
π
′
, полученная из лю-
бой
перестановки
π
с
помощью
оператора
)
,...,
,
,
,...,
(
)
,...
,
,
,...,
)(
(
)
(
1
1
1
1
1
1
N
j
j
j
N
j
j
j
j
g
j
g
π
π
π
π
π
π
π
π
π
π
π
+
−
+
−
=
=
=
(18)
(перестановка
j
-го и
1
+
j
-го элементов) не уступает по
значению целевой функции перестановке
π
при следующем усло-
вии:
{
}
{
}
.
)
,
2
(
),
,
1
(
min
)
,
2
(
),
,
1
(
min
1
1
j
j
j
j
π
π
π
π
τ
τ
τ
τ
+
+
>
(19)
Выберем в качестве оператора перестановочного метода опе-
ратор
1
g
, который находит и меняет местами в перестановке
π
любую пару “соседних” элементов, для которых выполняется усло-
вие (19). Легко проверить, что при отсутствии в наборе
{
}
)
,
( j
i
τ
равных величин оператор
1
g
имеет единственную неподвижную
перестановку (т.е. такую, к которой оператор неприменим)
,
)
1
(
π
определяемую следующим образом.
Пусть
−
)
,
(
1
1
j
i
τ
минимальный по величине элемент набора
{
}
)
,
( j
i
τ
. Если
1
1
=
i
, то
,
1
)
1
(
1
j
=
π
в противном случае
.
)
2
(
1
)
1
(
2
j
i
N
=
=
π
Затем элемент
)
,
(
1
1
j
i
τ
удаляется из набора
{
}
,
)
,
( j
i
τ
а в ос-
тавшейся его части снова находится минимальный по величине эле-
мент
).
,
(
2
2
j
i
τ
Если оказывается, что
1
2
=
i
, то элемент
2
j
поме-
щается в незанятую на предыдущем шаге позицию перестановки
)
1
(
π
с минимальным номером. В противном случае
)
2
(
2
=
i
этот
элемент помещается в незанятой позиции
)
1
(
π
с максимальным
номером. Дальнейшеее заполнение перестановки
)
1
(
π
элементами
N
I
осуществляется аналогично. Можно проверить, что к получен-
ной перестановке
)
1
(
π
оператор
1
g
неприменим. Построим такую