Пример 2.

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

Рис. 5 – Пример сети для алгоритма Дейкстры

Шаг 0. Назначаем узлу постоянную метку .

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

Узел	Метка	Статус метки
		Постоянная
		Временная
		Временная

Среди узлов и узел имеет наименьшее значение расстояния . Поэтому статус метки этого узла изменяется на " постоянная ".

Шаг 2. Из узла 3 (последнего узла с постоянной меткой) можно попасть в узлы 4 и 5. Получаем следующий список узлов.

Узел	Метка	Статус метки
		Постоянная
		Временная
		Постоянная
		Временная
		Временная

Временный статус метки узла заменяется на постоянный .

Шаг 3. Из узла можно достичь узлов и . После вычисления меток получим следующий их список.

Узел	Метка	Статус метки
		Постоянная
		Временная
		Постоянная
		Постоянная
		Временная

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

Шаг 4 Из узла можно перейти только в узел , но он уже имеет постоянную метку, которую нельзя изменить. Поэтому на данном шаге получаем такой же список меток, как и на предыдущем шаге, но с единственным изменением: метка узла получает статус постоянной, т.е. . С временной меткой остается только узел , но так как из этого узла нельзя попасть ни в какой другой, процесс вычислений заканчивается.

Узел	Метка	Статус метки
		Постоянная
		Постоянная
		Постоянная
		Постоянная
		Временная
Рис. 6 – Применение алгоритма Дейсктры (ошибка в дуге (2, 4), стрелка должна быть направлена от 4 к 2)

Алгоритм позволяет проводить вычисления непосредственно на схеме сети, как показано на рис. 6.

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

Таким образом, получаем путь общей длиной .

40. Алгоритмы нахождения кратчайшего пути. Алгоритм Флойда.

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

Покажем сначала основную идею метода Флойда. Пусть есть три узла , и , и заданы расстояния между ними (рис. 7). Если выполняется неравенство , то целесообразно заменить путь путем . Такая замена (далее ее будем условно называть треугольным оператором) выполняется систематически в процессе выполнения алгоритма Флойда.

Рис. 7 – Треугольный оператор Флойда

Алгоритм Флойда требует выполнения следующих действий.

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

Рис. 8 – Исходные матрицы и

Шаг k (основной). Задаем строку и столбец как ведущую строку и ведущий столбец. Рассматриваем возможность применения треугольного оператора ко всем элементам матрицы . Если выполняется неравенство

,

тогда выполняем следующие действия:

a) создаем матрицу путем замены в матрице элемента на сумму ,

b) создаем матрицу путем замены в матрице элемента на . Полагаем и повторяем шаг .

Поясним действия, выполняемые на -омшаге алгоритма, представив матрицу так, как она показана на рис. 9. На этом рисунке строка и столбец являются ведущими. Строка –любая строка с номером от до , а строка –произвольная строка с номером от до . Аналогично столбец представляет любой столбец с номером от до , а столбец – произвольный столбец с номером от до . Треугольный оператор выполняется следующим образом.

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

Рис. 9 – Реализация треугольного оператора

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

1. Расстояние между узлами и равно элементу вматрице .

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

41. Транспортные модели. Определение транспортной модели.

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

На рис. 1 показано представление транспортной задачи в виде сети с пунктами отправления и пунктами назначения, которые показаны в виде узлов сети. Дуги, соединяющие узлы сети, соответствуют маршрутам, связывающим пункты отправления и назначения. С дугой , соединяющей пункт отправления с пунктом назначения , соотносятся два вида данных: первый – стоимость перевозки единицы груза из пункта в пункт , и второй – количество перевозимого груза . Объем грузов в пункте отправления равен a объем грузов в пункте назначения — . Задача состоит в определении неизвестных величин , минимизирующих суммарные транспортные расходы и удовлетворяющих ограничениям, накладываемым на объемы грузов в пунктах отправления (предложения) и пунктах назначения (спрос).

Рис. 1 – Представление транспортной задачи

42. Решение транспортной задачи. Определение начального решения. Метод северо-западного угла.

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

Таблица 2.1

Шаг 1. Определяем начальное базисное допустимое решение, затем переходим к выполнению второго шага.

Шаг 2. На основании условия оптимальности симплекс-метода среди всех небазисных переменных определяем вводимую в базис переменную. Если все небазисные переменные удовлетворяют условию оптимальности, вычисление заканчиваются; в противном случае переходим к третьему шагу.

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

Рассмотрим каждый описанный шаг в отдельности.