86



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

    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 не обнаружили, то для дальнейшего разбиения выбираем множество с минимальной оценкой. Разбиваем это множество на несколько подмножеств и повторяем процесс до тех пор, пока не получим оптимальное решение.

      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.


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

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

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

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

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


Множество допустимых маршрутов состоит из элементов . Количество элементов равно


Математическая интерпретация задачи:


- это целевая функция ( 9.2.0 )

В качестве ограничений возьмем:

( 9.2.0 )

( 9.2.0 )



- это элементы матрицы путевых расстояний(издержек).


Ограничение ( 9.2 .0 ) говорит о том, что въезд в город осуществляется один раз.

Ограничение ( 9.2 .0 ) говорит о том, что выезд из города осуществляется один раз.


Эта задача может быть также сформулирована как задача о назначениях.


Чтобы была записана задача о коммивояжере, необходимо ввести дополнительные ограничения:

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


Пример.

Пусть имеется матрица вида:


полному перебору всех возможных вариантов можно поставить дерево вариантов.


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

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

Обозначим - некоторая ветка дерева, включающая вершин вместе с исходной, - это номер(индекс) ветки.

может изменяться от до , где - мощность множества .

, то есть количество ветвей нашего дерева, отличающегося элементами, начиная с первого.

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


Пример.

Возьмем , где (из предыдущего примера).

.................................


Обозначим через - множество всех начальных участков ветвей, содержащих элементов.

- множество ветвей, имеющих общий начальный участок и включающий все городов.


Пример.




Вводится понятие нижней границы для совокупности веток .

где - длина участка от исходной вершины по ветви .


Оптимистическая оценка:

Обозначим ее

Выбор такой оптимистической оценки ничем не обусловлен. Она может выбираться по-разному.

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


Предлагается следующий способ ее получения:

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