32 Метод ветвей и границ, решение линейных целочисленных задач.(Метод Ленд и Дойг)

33. Метод ветвей и границ, задача о коммивояжере.

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

Формализуем задачу.

Пусть известна матрица расстояний между пунктами i и j . В качестве неизвестной величины введем переменную

Модель задачи о коммивояжере будет иметь вид

(4.9)

при ограничениях:

; (4.10)

; (4.11)

. (4.12)

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

Ограничение (4.10) говорит о том, что коммивояжер должен в каждый пункт заехать только один раз, а ограничение (4.11) — из каждого пункта выехать только один раз. Ограничения (4.10)—(4.12) и дополнительное ограничение на маршруте коммивояжера создают так называемый гамильтоновый контур (по имени ирландского математика У. Гамильтона).

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

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

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

34. Динамическое программирование, принцип Беллмана, схема метода.

ДП – математический метод оптимизации многошаговых процессов принятия решений.

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

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

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

Задачи ДП:

• распределение ресурсов;

• календарное планирование;

• управление запасами;

• оптимизация маршрутов на сетях;

• замена оборудования.

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

Постановка задачи:

Имеется система S, которая переходит из начального состояния S₀ в конечное состояние S­_m под воздействием вектора управлений U. В развернутом виде это выглядит:

Или сокращенно:

Где – вектор управлений.

Все эти переходы можно представиться как траекторию в фазовом пространстве:

(Рисунок рассмотрен для случая, когда состояния системы описываются двумерным вектором).

Управление тоже может описываться вектором.

Через – будем обозначать доход на переходе , - функция перехода состояний. Интересующий нас выигрыш –

Также кроме аддитивного критерия может применяться мультипликативный, где .

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

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

Рассмотрим последовательность переходов состояний в виде следующей схемы:

Доход на i – м шаге: . – наилучшая эффективность при движении из S_i в S_m – называется Условно Оптимальным Выигрышем (УОВ). УОВ зависит только от состояния, это непосредственно вытекает из формулы для УОВ. Управление, при котором достигается УОВ называется Условно Оптимальным Управлением (УОУ) и обозначается .

Назовем конструкцию – полуоптимальным выигрышем (ПОВ). В таком случае УОВ на i-м шаге будет иметь вид (Уравнение Беллмана):

где u_i – все возможные управления на i-м шаге, S_i – получается из функции перехода состояний .

Реализация вышеописанных идей предполагает 2 этапа:

1. Обратная прогонка.

m-й шаг:

, где – множество возможных «предпоследних» состояний. - УОУ.

m-1-й шаг:

, где . – УОУ. УОВ – получен на предыдущем шаге.

…………………………………………………………………………..

i-й шаг:

, где . – УОУ.

…………………………………………………………………………..

1-й шаг:

, где . – УОУ.

2. Прямая прогонка.

В результате обратной прогонки получили УОВ на 1-м шаге. Нулевое состояние системы, при котором УОВ на 1-м шаге максимален и есть оптимальный выигрыш данной задачи. На каждом шаге было сформировано условно оптимальное управление. Определив начальное состояние, приводящее к оптимальному выигрышу (зачастую мощность множества начальных состояний равна единице, т.е. начальное состояние заранее известно), по УОУ на 1-м шаге определим соответствующее управление, которое уже будет безусловным. Имея управление на 1-м шаге и начальное состояние, по функции перехода состояний получим 1-е состояние, по которому определим безусловное оптимальное управление на 2-м шаге. И так далее восстановим всю цепочку оптимальных управлений. Сказанное можно записать следующим образом: