Оп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 следующим образом.

 

j = 1:

 

 

j = 1  2  3   4  5  6  7 v_j – u₁  *  2  5  11  7  *  * d_1j *  2  8  11 9  *  *

 

Поскольку v_j-u_i £ d_ij для всех j, величины v_j пересчитывать не следует. Заметим, что для j=1, 6 и 7 расстояния d_ij не определены, поэтому эти вели- чины при сравнении не берутся. В процессе реализации алгоритма обнару- живается, что условие оптимальности первый раз нарушается при i=6.

При i = 6 условие оптимальности нарушается для j = 4 и 5. Величины v₄

 

и v₅ изменяются следующим образом:

 

v ^/₄ = u₆ + d₆₄ = 3+5=8 (v₄=u₄=8),

 

v ^/₅ =u₆ + d₆₅ =3+1= 4 (v₅ =u₅=4).

 

В последующих вычислениях, т.е. для i=7, используются изменённые значения v₄ , v₅ и u₄ , u₅.

_{j = 2:}

 

 

 

 

 

 

 

 

j = 3: j = 4: j=5: 

j = 1 2 3 4 5 6 7

 

v_j – u₂ -2 * 3 * 5 1 *

d_2j 4 * 3 * 5 1 *

 

 

j = 1 2 3 4 5 6 7

 

v_j – u₃ -5 -3 * 6 * -2 *

^d_3j ^1 4 * ¥ ^* 2 *

 

 

j = 1 2 3 4 5 6 7

 

v_j – u₄ -11 * -6 * * -8 2

d_4j 5 * 9 * * 2 23

 

 

j = 1 2 3 4 5 6 7

 

v_j – u₅ -7 -5 * * * -4 6

^d_5j ² ¥ ^{* * * 7 9}

 

j = 6:

 

 

 

 

 

 

 

j =7: 

 

 

 

j = 1 2 3 4 5 6 7

 

v_j – u₆ * -1 2 8 4 * 10

d_6j * 8 3 5 1 * 10

 

 

j = 1 2 3 4 5 6 7

 

v_j – u₇ * * * -5 -9 -10 *

^d_7j ^{* * * 10 4 2 *}

 

 

После этого повторяется шаг 2 с изменёнными значениями v_j  и u_i. В таблице 3 приведены результаты сравнений, проведённых для i =1, 2, … ,7. Из этой таблицы видно, что в новых изменениях уже нет необходимости, и по- этому последние изменённые величины v_j дают длину кратчайшего пути от 1 _{до j.}

 

Покажем, каким образом используется u_i и v_j в таблице 2 для определения кратчайших расстояний между узлом 1 и каждым из узлов j=2, 3, … , 7. Проиллюстрируем процедуру на примере нахождения участков кратчайшего п ути между узлами 1 и 7.

Как уже известно, кратчайшее расстояние между узлами 1 и 7 равно v₇ =

 

13. Определение участков сети должно начинаться с узла 7. Требуется найти узел, непосредственно предшествующий узлу 7. Из столбца 7 таблицы 2 видно, что равенство v₇ =u₁ + d₁₇ , выполняется при i=5 и i=6, т. е. либо узел 5, либо узел 6 соединён с 7 (альтернативные решения).

Рассмотрим сначала узел 5. Из столбца 5 видно, что равенство v₅=u₁+d₁₅ выполняется при i=6. Далее из столбца 6 следует, что равенство v₆=u₁+d₁₆ вы- полняется при i=2. Наконец, как следует из столбца 2, равенство v₂=u₁+d₁₂ выполняется при i=1. Получившиеся участки дают путь 1®2®6®5®7 с v₇

_=13.

 

Аналогичная процедура позволяет получить другой кратчайший путь между узлами 1 и 7, а также все пути между узлами 1 и j = 2, 3, 4, 5 и 6.

 

 

 

 

^{j =1 2 3 4 5 6 7 u}_i 

Таблица 3

 

i =1 _* 2

_* 2

i =2 -2 _*

⁴ _* 

5 8 4

8 11 9

3 _* 2

³ _* ⁵ 

* * ⁰

* *

1 _* 2

¹ _*

 

i =3 -5 -3 _*

^1 4 _* 

3 _* -2 _* 5

_* ² _*

 

i =4 -8

5 

_* -3 _*

_* ⁹ _* 

_* -5 5 8

_* ^2 23

 

i =5 -4

2 

-2 _* *

_* * 

_* -1 9 4

_* ^7 9

 

i = 6 _*

*

i = 7 _*

_* 

-1 2

8 3

 

* *

_* * 

5 1

5 1

5 -9

10 4 

*

*

-10

2 

10 3

10

_* 13

_*

 

ЛИСТИНГ ПРОГРАММЫ

 

Алгоритм Форда-Беллмана

 

var a:array[1..20,1..20] of word; {матрица смежности}

c,pred,fl,d:array[1..20] of word;{c - массив кратчайших расстояний; pred - массив предыдущих вершин; fl - массив флагов; d - массив для записи пути}

i,j,k,n,first,last:byte;

f:text;{переменная для  открытия in.txt}

 

{процедура обхода  графа вглубь для поиска всех  путей}

 

Procedure Dfs(x:word); {в качестве  параметра передаём текущую вершину}

var i:byte; {локальная переменная}

begin

if x=last then {если конечная  вершина, то вводим путь}

  begin

   write(first,' ');

   for i:=1 to j do {выводим путь}

    write(d[i],' ');

    writeln;

    exit;{выходим из процедуры}

  end;

fl[x]:=1; {помечаем что  были в вершине}

for i:=1 to n do {если не  были в вершине и существует  дуга в неё}

  if (fl[i]=0)and(a[x,i]<>32767) then

   begin

    inc(j);

    d[j]:=i; {записываем  в путь вершину}

    dfs(i);

    dec(j);

   end;

 fl[x]:=0; {помечаем что вершина свободна}

end;

 

{основная программа}

 

begin

     assign(f,'in.txt'); {открываем файл для чтения}

     reset(f);

     readln(f, n); {считываем  количество вершин}

     for i:=1 to n do

          for j:=1 to n do

          read(f,a[i,j]); {считываем матрицу смежности}

     writeln('Mатрица:');

     for i:=1 to n do  {выводим матрицу на экран}

          for j:=1 to n do

           if j=n then writeln(a[i,j])

           else write(a[i,j],' ');

     for i:=1 to n do {заменяем нули бесконечностью}

          for j:=1 to n do

          if a[i,j]=0 then a[i,j]:=32767;

     writeln('Введите 1 вершину: ');

     readln(first);

     writeln('Введите 2 вершину');

     readln(last);

     close(f); {закрываем файл in.txt}

     for j:=1 to n do

     begin

           c[j]:=a[first,j]; {записываем начальные значения}

           if a[first,j]<32767 then

           pred[j]:=first; {если существует дуга  то записываем предыдущую вершину}

     end;

     for i:=3 to n do

         for j:=1 to n do

             if j<>first then

             for k:=1 to n do  {если не бесконечность и путь более выгодный}

                 if (c[k]<32767) and (c[k]+a[k,j]<c[j]) then

                  begin

                   c[j]:=c[k]+a[k,j]; {записываем новое значение}

                   pred[j]:=k; {записываем pred вершину}

                  end;

     if c[last]=32767 then writeln('Нет путей')

     else {если бесконечность то нет пути}

      begin

          writeln;

          writeln('Кратчайший путь:');

          write(first,' ');

          i:=last;

          k:=1;

          while i<>first do {в обратном порядке  обходим путь}

           begin

               d[k]:=i; {записываем путь в массив}

               k:=k+1;

               i:=pred[i];

           end;

          for i:=k-1 downto 1 do {выводим кратчайший путь}

          write(d[i],' ');

          writeln;

          writeln('Все пути:');

          j:=0;

          Dfs(first); {вызываем процедуру поиска  всех путей}

      end;

     readln;

     readln;

end.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ЗАКЛЮЧЕНИЕ

 

В данной курсовой работе мною была раскрыта тема «Определение кратчайшего пути на сети с циклами». Эта тема является достаточно важной в рассмотрении вопросов системного анализа.

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

• минимизация сети;

• кратчайший путь:

• сеть без циклов;
• сеть с циклами;

• определение максимального потока;

Метод «Определение кратчайшего пути на сети с циклами» теоретически рассмотрен более подробно и к этому методу предложена программа, написанная на языке программирования Pascal.

Эта программа облегчает  понимание данного метода и дает яркую картину принципа его работы.

 При написании курсовой работы была использована различного рода литература.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ЛИТЕРАТУРА

 

1. Дегтярев Ю.И. Методы оптимизации: Учеб. пособие для ВУЗов.-М.: Сов.радио, 1980.-272с.

 

2. Дегтярев Ю.И. Исследование операций: Учеб. пособие для ВУЗов по спец.АСУ. -М.: Высш. шк., 1986.-320с.: ил.