86

9.Задачи дискретной оптимизации.

9.1Методы решения задач дискретной оптимизации.

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

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

1. методы отсечения;

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

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

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

Интенсивное развитие получили комбинаторные методы. Это вызвано тем, что на практике необходимо решать большое количество оптимизационных, комбинаторных задач. Такими задачами, к примеру, являются:

1. задача о ранце;

2. задача о коммивояжере;

3. задача минимизации среднего времени обработки партии деталей;

4. задача о назначениях;

5. задача о покрытии;

6. задача компоновки;

и так далее.

Определить понятие оптимизационно-комбинаторной задачи можно следующим образом:

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

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

1. нужно уметь перебирать множество значений функции ;

2. вычислять эти значения и сравнивать.

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

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

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

1. локальная оптимизация;

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

3. метод ветвления.

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

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

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

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

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

2. признаки получают из анализа уже полученных решений.

Методы ветвления.

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

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

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

2. алгоритмы, строящие дерево недопустимых решений(например, аддитивный алгоритм Балаша и его модификации). Этот метод применяется для решения задач линейного программирования с булевыми переменными;

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

Общая схема метода ветвей и границ для задачи дискретной оптимизации

( 9.1.0 )

, - допустимое, конечное множество ( 9.1.0 )

включает следующие основные моменты:

1. подсчет оценок (ищется нижняя граница целевой функции на множестве ). Нижней оценкой будет такое число , что ;

1. многошаговый процесс разбиения множества на подмножества(ветвление по определенным правилам);

1. пересчет оценок. Если множество , то . Если множество состоит из объединения , то есть , то оценка для любого подмножества будет не меньше, чем оценка для множества , то есть:

.

Часто для некоторых удается получить строгое неравенство:

1. признак оптимальности(в том случае когда решаем задачу на минимум)

в случае, если и (x - решение, принадлежит некоторому ) и ,

то x - оптимальное решение задачи ( 9.1 .0 ) - ( 9.1 .0 ).

Процесс решения исходной задачи ( 9.1 .0 ) - ( 9.1 .0 ) может быть описан так:

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

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

9.1.1 Алгоритм Лэнд и Дойга.

Задача целочисленного линейного программирования представляет собой:

( 9.1.0 )

( 9.1.0 )

( 9.1.0 )

( 9.1.0 )

Допустимое множество задачи целочисленного линейного программирования формулами ( 9.1 .0 ) - ( 9.1 .0 ) предполагается ограниченным.

Оценки снизу вычисляются с помощью релаксации, состоящей в отбрасывании условия ( 9.1 .0 ) целочисленности переменных.

Полученная задача решается симплекс методом.

Решается задача ( 9.1 .0 ) - ( 9.1 .0 ), если полученное решение удовлетворяет условию ( 9.1 .0 ), то исходная задача целочисленного линейного программирования считается решенной.

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

выбирается и исходная задача ветвится на две подзадачи:

1. с дополнительным ограничением ;

2. с дополнительным ограничением .

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

На шаге выбранная на шаге подзадача разветвляется на две новые с дополнительными ограничениями

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

Пример.

( 9.1.0 )

( 9.1.0 )

( 9.1.0 )

Умножим ( 9.1 .0 ) на ( -1 ), тогда получим:

( 9.1 .0 )

( 9.1.0 )

( 9.1 .0 )

Отбрасываем условие ( 9.1 .0 ) и решаем задачу ( 9.1 .0 ) - ( 9.1 .0 ) графически.

	3	0
	0	8.25

	-8	0
	0	4

имеет координаты

Решением данной задачи является точка:

.

Поскольку условие целочисленности переменных не выполняется, то исходная задача разбивается на две подзадачи:

( I ):

( I I ):

Решением ( I ) задачи является:

Решением ( I I ) задачи является:

Графическое представление задачи 1.

Графическое представление задачи 2.

Поскольку , то ветвим далее задачу ( I I ). Выбираем координату . Получаем задачи:

( I I I ):

( I V ):

Решением ( I I I ) задачи является:

( I V ) задача решений не имеет.

Графическое представление задачи 3.

Графическое представление задачи 4.

Продолжаем ветвление. Ветвим далее задачу ( I I I ). Выбираем координату . Получаем задачи:

( V ):

( V I ):

Решением ( V ) задачи является:

Решением ( V I ) задачи является:

,

Графическое представление задачи 5.

Графическое представление задачи 6.

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

9.2Задача о коммивояжере.

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

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

- это просто индекс, но путевые расходы по данному маршруту должны быть минимальны.