Содержание:

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

2 Описание метода и алгоритма решения.

2.1 Составление исходной таблицы расстояний.

2.2 Определение li и lj

2.3 Определение длинны кратчайших путей.

2.4 Нахождение кратчайшего пути.

3 Описание программы. 7

4 Описание подпрограмм и процедур.

4.1 Подпрограммы и функции.

4.2 Таблица идентификаторов.

5 Пример решения контрольной задачи.

6 Выводы.

7 Список литературы.

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

На практике часто встречается задача определения кратчайшего маршрута по заданной сети из начального пункта до конечного пункта маршрута. Транспортная сеть может быть представлена в виде графа (рис.1), дуги которого - транспортные магистрали, а узлы - пункты отправления и назначения. Графически транспортная сеть изображается в виде совокупности n пунктов P1,P2, .,Pn, причем некоторые упорядоченные пары (Pi,Pj) пунктов назначения соединены дугами заданной длинны r(Pi,Pj)=lij. Некоторые или все дуги могут быть ориентированы, т.е. по ним возможно движение только в одном направлении, указанном стрелками.

На рис.1 построена ориентированная транспортная сеть, содержащая шесть пунктов P1,P2, .,P6, которые связаны между собой восьмью транспортными путями.

Необходимо определить кратчайший маршрут из пункта P1 в P6. Определение кратчайшего маршрута состоит в указании последовательности прохождения маршрута через промежуточные пункты и суммарной длинны маршрута.

Например маршрут из пункта P1 в пункт P6: P1P2P4P6; L=l12+l24+l46=10.

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

2. Описание метода и алгоритма решения.

Метод Форда бал разработан специально для решения сетевых транспортных задач и основан, по существу, на принципе оптимальности.

Алгоритм метода Форда содержит четыре этапа (схема 1). На первом этапе производится заполнение исходной таблицы расстояний от любого i-го пункта в любой другой j-й пункт назначения. На втором этапе определяются для каждого пункта некоторые параметры li и lj по соответствующим формулам. Далее на третьем этапе определяются кратчайшие расстояния. Наконец, на четвертом этапе определяются кратчайшие маршруты из пункта отправления Р1 в любой другой пункт назначения Рj, j=1,2, .,n.

Рассмотрим подробнее каждый из этих четырех этапов.

2.1 Первый этап: Составление исходной таблицы расстояний.

Данная таблица содержит n+1 строк и такое же количество столбцов; Pi - пункты отправления; Pj - пункты назначения. Во второй строке и втором столбце проставляется значения параметров li иlj, определение значений которых производятся на втором этапе решения задачи. В остальных клетках таблицы проставляются значения расстояний lij из i-го пункта в j-й пункт. Причем заполняем клетки таблицы, лежащие выше главной диагонали. Если пункт Pi не соединен отрезком пути с пунктом Pj, то соответствующая клетка таблицы не заполняется.

2.2 Второй этап: Определение li и lj.

Определяется значение параметров в соответствии с формулой:

lj=min(li+lij); i=1,2, .,n; j=1,2, .,n, (1)

где l1=0.

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

2.3 Третий этап: Определение длинны кратчайших путей.

Возможны два случая определения длинны кратчайших путей из пунктов Pi в пункты Pj, i=1,2, .,n; j=1,2, .,n.

В первом случае, если выполняются неравенство:

lj - li£ lij; lij¹0; j=1,2, .,n; j=1,2, .,n, (2)

то значения параметров [IE1] l1, .,ln удовлетворяют условиям оптимальности. Каждое значение lj есть не что иное, как кратчайшее расстояние от пункта Pi до пункта Pj, j=2,3, .,n.

Во втором случае, если для некоторых клеток (i,j) таблицы имеет место неравенство:

lj - li > lij; i=1, .,n; j=1, .,n, (3)

то значения lj и li могут быть уменьшены.

Если справедливо (3), тогда исправим значение lj0, пересчитав его по формуле:

l¢j0=li0+li0j0. (4)

2.4 Четвертый этап: Нахождение кратчайшего пути.

Определения последовательности пунктов кратчайшего маршрута. С этой целью для каждого столбца определяют величину:

lr1,j= lj - lr1, (5)

где lr1,j берется из таблицы, причем lr1 выбирается так, чтобы выполнилось равенство (5). Таким образом определим r1. Далее продолжим ту же операцию, но будем считать, последней не Pn, а Pr1. Будем продолжать до тех пор, пока rn=1.

Таким образом кратчайший маршрут проходит через Pr1,Pr2, .,Prn, а длинна маршрута Lmin=lr2,r1+lr3,r2+ .+lrn-1,rn.

3. Описание программы.

Программа «FORD» написана на языке высокого уровня - Pascal, в интегрированной среде разработки «Turbo Pascal 7.0» фирмы Borland Inc.

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

В программе предусмотрена возможность повторного решения задачи с другими исходными данными.

4. Описание подпрограмм и процедур.

4.1 Подпрограммы и функции.