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

Формально алгоритм метода ветвей и границ выглядит следующим образом.

В начале любой итерации t известна верхняя оценка оптимального значения целевой функции. Имеется список задач (маршрутов), в котором некоторое подмножество значений c_ij изменено и принято равным ∞, а также подмножество { x_ij }={ x_ij | x_ij =1}.

На итерации 1 основной список включает две задачи: в одной из них c_ij изменено на ∞, а в другой – соответствующая переменная x_ij=1,
а c_ij = ∞.

На итерации t выполняются следующие шаги.

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

Шаг 2. Определить нижнюю оценку целевой функции для любого цикла, порождаемого выбранной задачей. Если нижняя оценка больше или равна F _t (x), то принять F _t+1 (x) = F _t (x) и вернуться к шагу 1. В противном случае перейти к шагу 3.

Шаг 3. Если текущее решение определяет цикл, то зафиксировать его, принять равным соответствующему значению целевой функции и вернуться к шагу 1. В противном случае – перейти к шагу 4.

Шаг 4. Выбрать переменную х_hk, не входящую в текущее решение, такую, что c_hk < ∞ при условии, что х_hk=1 не приводит к образованию подцикла на переменных, уже вошедших в решение. При таком выборе внести в основной список две задачи. Каждую из этих задач принять идентичной задаче, выбранной на шаге 1, за исключением лишь того, что в одну из них ввести изменение c_hk =∞, а в другую – условие х_hk =1 и
c_hk = ∞. Принять F _t+1 (x) = F _t (x) и вернуться к шагу 1.

 

Математическая постановка транспортной задачи.

В пунктах P₁, P₂ … P_n имеется груз в количествах a₁, a₂ … a_n. Его необходимо перевезти в пункты Q₁, Q₂ … Q_n в количествах b₁, b₂, … b_n. Требуется составить такой план перевозок, при котором суммарные транспортные расходы минимальны.

 

Обозначим через x_ij – количество груза перевозимого из пункта P_i в пункт Q_j.

c_ij – стоимость перевозки единицы этого груза.

 

Количество груза отправляемого из пункта P_i должно быть равно имеющимся запасам a_n.

Количество груза поставляемого в Q_j должно быть равно имеющимся потребностям b_n.

Целевая функция определяет стоимость перевозки всего груза.

 

Модифицированный распределительный метод транспортной задачи

∑a_i ≠ ∑b_j

Транспортные задачи, у которых возможности и потребности не совпадают называются открытыми. Для их решения, в случае если ∑a_i > ∑b_j, вводят условного потребителя, для которого c_i,усл =0.

Если ∑a_i < ∑b_j, то вводят условного поставщика, для которого c_усл,j=0.

Таблица в таком случае будет иметь вид:

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

 

Распределительный метод.

1) Поиск исходного решения

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

А1B1->АnBn

2) Проанализируем пустые(=0) клетки

Исследуем перспективность клетки А1В3 полагая, что Х13=1.Для оценки переспективности пустой клетки строится прямоугольник принятия решиений, в котором все углы кроме исследуемого должны быть заняты т.у в них величины Хij<>0

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

3) Перераспределение полученного решения

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

В клетках с «-» индексом из значений переменных вычитается минимальное значения переменной, стоящих в этих клетках и это же значение прибавляется к значению переменных, стоящих в клетках с «+» индексами.
В оставшихся клетках значения переменных остаются прежними.

После перераспределения делается очередная итерация заключающаяся в поиске перспективной клетки и очередном перераспределении.

Цикломатическое число графа

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

Цикломатическая матрица:

Цикломатическим числом графа ν(G) – называется число базисных циклов, через которые можно выразить любой другой цикл.

ν(G)=m-n+1, где m – сигнатура; n – множество вершин.

Для приведенного выше графа ν(G)=5-4+1=2, т.е. имеется 2 независимых цикла и что можно убрать 2 ребра так, чтобы получился связанный граф без циклов.

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

 

(11) Деревья. Остовное дерево минимального веса Дерево - это связный ациклический граф. Связность означает наличие путей между любой парой вершин, ацикличность - отсутствие циклов и то, что между парами вершин имеется только по одному пути. Ориентированное (направленное) дерево - ацикличный орграф (ориентированный граф, не содержащий циклов), в котором только одна вершина имеет нулевую степень захода (в неё не ведут дуги), а все остальные вершины имеют степень захода 1 (в них ведёт ровно по одной дуге). Вершина с нулевой степенью захода называется корнем дерева, вершины с нулевой степенью исхода (из которых не исходит ни одна дуга) называются концевыми вершинами или листьями Теорема. В связном графе (M, N, T) найдется частичный связный граф (M, N, T) В котором |M| - 1= |N'| = k и можно перенумеровать вершины из M числами от О до k, a дуги из N' числами от l до k таким образом, что для любой дуги u? N' выполн. Задача о кратчайшем остовном дереве. Пусть каждой дуге J графа (M, N, T) сопоставлено неотрицательное число l[j] именуемое длиной этой дуги Требуется построить такое остовное дерево (M, N, T) У которого сумма Длин дуг была бы минимальна.

 

 

(12) Топологическая сортировка графа. Алгоритм Демукрона Топологическая сортировка - один из основных алгоритмов на графах, который примен. для реш. множества более сложных задач. Задача тополог. сортировки графа сост. в следующем: указать такой линейный порядок на его вершинах, чтобы любое ребро вело от вершины с меньшим номером к вершине с большим номером. Очевидно, что если в графе есть циклы, то такого порядка не существует. Ориентир. сетью назыв. бесконтурный ориентир. граф. В задачах подобного плана рассматриваются только конечные сети. Алгоритм Демукрона — алгоритм решения задачи тополог. сортировки, то есть упорядочения вершин графа по их уровням для бесконтурного ориентир. графа. Уровни вершин графа можно рассматривать как длины max путей от входов до этих вершин. Основная идея алгоритма Демукрона состоит в послед. удалении из сети, начиная со входов, вершин и исходящих из них дуг. Алгоритм исп. матрицу смежности вершин В типа n x n в качестве средства представления сети и основан непосредственно на определении уровня вершины и свойствах матрицы В.

 

 

Операции над графами.

1) Дополнение графа G = (x, U).

Это граф , у которого носитель совпадает с исходным графом и множество дуг есть дополнение для множества дуг U.

2) Объединение графов

При условии, что не пересекаются

G = (x, U) у которого множество вершин объединены с и дуги образованы с .

3) Сумма графов

Граф G = (x, U) образован путем объединения графов и построения полного двудольного графа, у которого одна доля представляет собой множество , а 2 доля

4) Удаление вершины x из графа G = (x, U)

5) Удаление ребра из графа