Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

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 ) графически.

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

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

.

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

( 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Задача о коммивояжере.

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

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

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

Характеристики

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.

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

Список файлов книги