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

Рассмотрим задачу нахождения кратчайших цепей между всеми парами узлов сети.

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

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

Пусть N = {1,2,..., n} – множество узлов, а c_{i j} – количественный параметр (длина, стоимость) дуги (i, j), направленной от узла i к узлу j. Обозначим через длину кратчайшей цепи из узла i в узел k.

Алгоритм Флойда. Первоначально за оценку длины d_{i k} кратчайшей цепи между двумя произвольными узлами i и k (между которыми могут быть и промежуточные узлы) принимают длину дуги (i, k), соединяющей эти узлы. Затем последовательно проверяют всевозможные промежуточные узлы, расположенные между i и k. Если длина цепи, проходящей через некоторый промежуточный узел, меньше текущего значения d_{i k}, то переменной d_{i k} присваивают новое значение; если d_{i k} > d_{i j} + d_{j k}, то значение d_{i k} заменяют значением (d_{i j} + d_{j k}). Такую процедуру повторяют для различных пар узлов, пока не будут получены все значения .

В алгоритме Флойда начальным значением переменной d_{i k} является c_{i k}. Затем оно последовательно улучшается до тех пор, пока не будет найдена кратчайшая цепь между узлами i и k. Алгоритм Флойда позволяет решать задачу о многополюсной кратчайшей цепи (пути) для сети из п узлов за п итераций. Обозначим символом оценку длины кратчайшей цепи из узла i в узел k, полученную на j-й итерации, и рассмотрим следующую задачу.

Задача. Необходимо соединить восемь объектов многополюсной цепью кратчайшей длины, причём один из объектов (№ 8) может только направлять информацию, а остальные – и направлять, и получать информацию без каких-либо ограничений (рис.2.3.1). На рисунке каждый объект представлен узлом, а каждая линия – дугой. Ориентированные дуги соответствуют распределительным звеньям, которые могут быть использованы для передачи информации только в указанном направлении. Числа, приписанные дугам, соответствуют расстоянию между объектами. Требуется найти для каждого объекта кратчайшие пути, связывающие его с другим объектами.

Рис.2.3.1

Решение. Воспользуемся алгоритмом Флойда. Поскольку п = 8, то число итераций в алгоритме будет 8. На каждой итерации строят матрицы длин кратчайших путей, которые содержат текущие оценки длин кратчайших цепей D ^j= ||||, где D⁰ = ||c_{i k}||, и матрицу маршрутов R ^j, служащую для нахождения промежуточных узлов (если таковые имеются) кратчайших цепей. На j-й итерации матрица маршрутов определяется как R ^j = ||||, где - первый промежуточный узел кратчайшей цепи из i в k, выбираемый среди множества

{1,2,..., j}, i ¹ j ¹ k, R ⁰ = ||||,

где = k.

Узел может быть получен из следующего соотношения:

Строим матрицу длин кратчайших цепей D⁰ и матрицу маршрутов R⁰. Отсутствие связи помечаем знаком ¥, нулём обозначаем связи внутри одного узла (из узла i в узел i):

;

.

Итерация 1. Выбираем базовый узел j = 1. В матрице D⁰ вычёркиваем j-ю (базовую) строку и j-й (базовый) столбец. Чтобы определить, приведёт ли использование узла 1 к более коротким цепям, необходимо исследовать элементы матрицы D⁰ с помощью трёхместной операции: ; i ¹ j ¹ k. Если = ¥, т.е. j-й элемент базового столбца равен ¥, то = . Если = ¥, т.е. j-й элемент базовой строки равен ¥, то = . Если ¹¥ и одно из двух значений или превосходит , то замену также производить не следует. Столбцы 3, 5, 7 и 8 содержат элементы, равные ¥ и принадлежащие базовой строке, а строки 3, 5-8 – элементы, равные ¥ и принадлежащие базовому столбцу, т.е. исследовать надо элементы (2,2); (2,4); (4,2); (4,4). Поскольку диагональные элементы можно не рассматривать, необходимо исследовать лишь оценки и :

;

.

Оценки и меньше оценок и : и должны быть внесены в матрицу D¹, а в матрице маршрутов надо положить , =1 и =1. Остальные элементы матриц D⁰ и R⁰ остаются без изменений.

Получим матрицы

;

.

Итерация 2. Определим узел 2 как базовый, т.е. проверим, приведёт ли его использование к более коротким цепям, и вычеркнем в матрице D¹ вторую строку и второй столбец. Здесь столбцы 6-8 содержат элементы, равные ¥ и принадлежащие базовой строке, а строки 6-8 – элементы, равные ¥ и принадлежащие базовому столбцу (столбцы и строки 6-8 не рассматриваем). Исключаем и диагональные элементы. Остаётся исследовать лишь элементы (1,3), (1,4), (1,5), (3,1), (3,4), (3,5), (4,1), (4,3), (4,5), (5,1), (5,23), (5,4). Нетрудно проверить, что здесь улучшены могут быть только оценки , , , , , , равные ¥:

;

;

;

;

;

.

Таким образом, ; остальные элементы остаются без изменения. Новые матрицы имеют вид

;

.

Итерация 3. Определяем, приведёт ли использование узла 3 к более коротким цепям. Берём узел 3 в качестве базового и вычеркиваем третью строку и третий столбец в матрице D². Исключаем диагональные элементы, элементы третьего столбца и третьей строки. Исследуем оставшиеся элементы матрицы D², получаем матрицы D³ и R³. Аналогично получаем матрицы D ^j и R ^j, j=. Матрицы D ^j, R ^j, j =остаются без изменений. Следовательно, оптимальное решение соответствует матрицам D⁵ и R⁵, определяющим как оптимальное расстояние для передачи между объектами, так и последовательность передачи информации:

;

.

Например, определим кратчайшую цепь из узла 1 в узел 5. По матрице D⁵ определяем, что длина этой цепи равна =9. Чтобы найти соответствующую последовательность узлов, обратимся к матрице R⁵. Значение равно 4, т.е. узел 4 является первым промежуточным узлом в кратчайшей цепи из узла 1 в узел 5. Теперь надо определить, какой узел следует за узлом 4 в кратчайшей цепи из узла 4 в узел 5. Рассмотрим данное значение равно 3. Значит, за узлом 4 следует узел 5. Аналогично, за узлом 3 следует узел 3, так как = 5. Следовательно, кратчайшая цепь из узла 1 в узел 5 определяется последовательностью узлов 1, 4, 3, 5.

3. Методические указания по выполнению лабораторной работы

Перед выполнением лабораторной работы необходимо ознакомиться с её целью, основными теоретическими положениями, особенностями использования пакета прикладных программ (ППП) QSB и табличного процессора (ТП) Excel 7.0 при решении транспортных задач.

Каждый студент получает у преподавателя индивидуальное задание на выполнение лабораторной работы.

В процессе лабораторной работы необходимо:

1) на основе содержательной постановки транспортной задачи разработать её математическую модель;

2) подготовить исходные данные для решения транспортной задачи методом потенциалов с использованием ППП QSB и симплекс-методом с использованием ТП Excel 7.0;

3) решить транспортную задачу при фиксированном варианте задания исходных данных;

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

На основе проведённых исследований определяются границы устойчивости полученных решений транспортной задачи.

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

4. форма отчётности по выполненной лабораторной работе

Отчёт должен содержать:

- титульный лист;

- содержательную и формальную постановку транспортной задачи;

- распечатки результатов решения и исследования транспортной задачи с использованием ППП QSB и ТП Excel 7.0;

- выводы по результатам решения и исследованию транспортной задачи.

Отчёт о лабораторной работе представляется к моменту её защиты.