Опpеделение кpатчайшего пути на сети с циклами

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ

 

 

УЧРЕЖДЕНИЕ ОБРАЗОВАНИЯ

«ГОМЕЛЬСКИЙ ГОСУДАРСТВЕННЫЙ  УНИВЕРСИТЕТ  
ИМЕНИ ФРАНЦИСКА СКОРИНЫ»

 

 

Заочный факультет

Кафедра автоматизированных систем обработки  информации

 

 

 

 

 

Опpеделение кpатчайшего  пути на

сети с циклами

Курсовая  работа

 

по дисциплине «Системный анализ и исследование операций»

 

 

 

 

 

Исполнитель

студент группы АС-32    Шелкунов А.А.

 

 

Руководитель

ассистент       Давыдов В.С.

 

 

 

 

Гомель, 2010

 

 

 

 

Содержание

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

 

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

 

1. Проектирование газопровода, соединяющие буровые скважины в Мексиканском заливе с находящейся на берегу приемной станцией. Следует выбрать проект, в котором строительство газопровода имеет минимальную стоимость.
2. Определение кратчайшего пути между двумя городами, проходящего по существующей сети шоссейных дорог.
3. Определение максимальной пропускной способности (в тоннах/год) трубопровода для транспортировки угольной пульпы с шахт Вайоминга на тепловые электростанции в Хьюстоне. (Уголь под напором воды поступает специально спроектированный трубопровод и перегоняется с шахт в пункты назначения).

 

Анализ указанных  примеров показывает, что оптимизационные  задачи на сети можно описать следующими тремя типами моделей:

1. минимизация сети;
2. нахождение кратчайшего маршрута;
3. определение максимального потока;

 

Рассмотренные выше примеры  связаны с определением расстояний и материальных потоков. Перечисленные выше задачи можно сформулировать и в принципе решить как задачи линейного программирования. Однако из-за огромного числа переменных и ограничений сетевых задач непосредственное применение симплекс- метода не целесообразно.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2 СЕТЕВАЯ МОДЕЛЬ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

 

ОСНОВНЫЕ  ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ

 

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

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

Математический  аппарат сетевых моделей базируется на теории графов.

Графом называется совокупность двух конечных множеств:

- множества  точек, которые называются вершинами, и множества пар вершин, которые называются ребрами. Если рассматриваемые пары вершин являются упорядоченными, т. е. на каждом ребре задается направление, то граф называется ориентированным; в противном случае — неориентированным. Последовательность неповторяющихся ребер, ведущая от некоторой вершины к другой, образует путь.

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

В экономике  чаще всего используются два вида графов: дерево и сеть.

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

Сеть — это ориентированный конечный связный граф, имеющий начальную вершину (источник) и конечную вершину (сток). Таким образом, сетевая модель представляет собой граф вида «сеть».

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

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

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

Сетевые модели могут строиться:

• в терминах событий: вершины- события, дуги- взаимосвязь событий;
• в терминах работ: вершины- работы, дуги- взаимосвязь работ;
• в терминах работ и событий: вершины- события результата работ (начало либо завершение), дуги- сами работы.

2 АЛГОРИТМ ОПPЕДЕЛЕНИЯ КPАТЧАЙШЕГО ПУТИ НА

СЕТИ С ЦИКЛАМИ

 

 

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

_{проиллюстрируем её на числовом примере.}

 

 

 

 

 

 

 

1 2 … n –1 n u_i

 

^1 d11 ^d12 ^… d1, n-1 ^d1n ^u1

 

^2 d21 ^d22 ^… d2, n-1 ^d2n ^u2

_M …

^n dn1 ^dn2 ^… dn, n-1 ^dnn ^un

^v₁ ^v₂ ^… v_n-1 ^v_n 

Таблица 1

 

 

 

 

 

 

Пусть требуется определить кратчайший маршрут между узлом 1 и лю- бым другим узлом сети j, j = 2,…, n. Алгоритм удобно представить, записав расстояния d_ij между узлами  i и j в виде таблице 1 (заметим, что d_ij могут от- личаться от d_ji). Таким образом, строка i (столбец j) представляет узел i (узел j). Шаги алгоритма можно представить следующим образом.

Шаг 1 Пусть v_j – сумма длин дуг, образующих цепь, ведущую из узла 1 в узел j. Положим v₁= 0 и u_i равным v_j, если i = j. При условии, что i и j и со- единены дугой, величина v_j определяется как v_j = min{u_i + d_{i j}}.

Процесс начинается с i = 1 и v₁ =u₁ = 0.

 

Заметим, что u_i включает расстояния до узла i, которое заметим исполь- зуется для определения ближайшего узла j. При этом требуется, чтобы обра- щение к значению u_i (= v_j) для i= j происходило сразу после появления v_j   и

 

прежде чем вычислено какое-либо новое значение v_j.

 

Шаг 2 Положить i =1.

 

1) Вычислить v_j-u_i для всех j.

 

2) Если d_ij³ v_j-u_i для всех j, то между узлами i и j не существует более короткого пути. Если i = n, перейти к п. 4. Иначе положить i=i+1 и перейти к

_{п. 1.}

 

3) Если d_{i j}< v_j - u_i, вычислить новые значения v_j , v ^/_j используя формулу

 

v ^/_j = u_i + d_{i j} .

 

Заменить v_j и u_i и для i = j на v ^/_j. Если i = n, перейти к п. 4, в противном случае положить i=i+1 и перейти к п. 1.

4) Если значение v_j изменялось в п. 3, повторить пункт 2, используя из- менённое значение. В противном случае перейти к шагу 3.

Шаг 3 Полученные значения v_j определяют кратчайшее расстояние ме-

 

_{жду узлами 1 и j =2, 3, …, n. Для получения соответствующих цепей послед-}

 

 

_{няя дуга (i, j) в цепи (i, j) должна удовлетворять условию} 

_{u  = v - d  .}

 

ⁱ₁ ^{j i j}

 

^{После определения i}₁ ^{предпоследняя вершина i}₂ ^{должна удовлетворять}

 

 

_{равенству} 

 

_{u = v - d .}

 

ⁱ₂ ⁱ ₁ 

ⁱ ₂ⁱ ₁

 

 

Процесс продолжается, пока не будет достигнут узел 1.

 

Пример:

 

Рассмотрим сеть на рисунке 1. Сеть содержит циклы, возникающие из-за возможности двустороннего движения. Если дуга ориентирована (т.е. движение одностороннее), расстояние в другом направлении полагается равным ¥ .

Соответствующие величины d_ij вместе с предварительными значениями u_i и v_j и приведены в таблице 2. Исходные величины v_j и u_i определяются сле- дующим образом. Пусть u₁ = v₁ = 0 . При использовании формулы

v_j = min{u_i +d_{i j}}

 

Осуществляется последовательное обращение к величинами v_j  и u_i  по мере того как они становятся доступными. v₂ = 0+2= 2, u₂ =2,

 

_{v3 =} 

_{min {u1 + d13 , u2 + d23}= min {0+8, 2+3}= 5, u3 = 5,}

 

i =1, 2 

i =1, 2

 

 

 

_{v4 =} 

_{min {u1+d14 , u2+d34}= min {0+11, 5+ ¥ }=11, u4 = 11,}

 

 

 

v₅ = 

i =1,3

 

_{min {u1+d15, u2+d25}=}

i =1, 2 

i =1,3

 

_{min {0+9, 2+5}=7, u5 =7,}

i =1, 2

 

 

 

v₆ = 

_min

i =2,3, 4,5 

{u₂+d₂₆,u₃+d₃₆,u₄+d₄₆ ,u₅ +d₅₆}= 

_min

i =2,3, 4,5 

{2+1,5+2,11+2,7+7}= 3, u₆= 3,

 

 

 

_{v7 = min}

i =4,5,6 

{u₄ + d₄₇ , u₅ + d₅₇, u₆ + d₆₇,}= 

_min

i =4,5,6 

{11+23,7+9,3+10}=13, u₇=13.

 

 

 

5

 

 

 

8 ⁷

 

 

⁵ ₁

₂

^9 2 8

3

 

² ₄

⁴

 

8

₁

¹ 

9

 

4 ₇

₁

¹⁰ 2

6

10

3

 

₂

₂₃

_5 2

³

 

 

₅ ⁹

⁴

 

11

 

Рисунок 1 − Пример сети с циклами

 

 

 

i/j 1 2 3 4 6 6 7 u_i

 

1 2 8 11 9 0

2 4 3 5 1 2

^3 1 4 ¥ ^2 2 5

4 5 9 2 23 11

^5 2 ¥ ^7 9 7

6 8 3 5 1 10 3

7 10 4 2 13

 

^v_j ^{0 2 5 11 7 3 13} 

 

 

 

 

Таблица 2

 

 

 

При переходе к шагу 2 проводится проверка условия оптимальности п у- тём сравнения (v_j-u_i) с d_ij следующим образом.