42068

Определение кратчайшего пути между вершинами ориентированного графа с циклами

Лабораторная работа

Информатика, кибернетика и программирование

Длины дуг могут определять различные характеристики: расстояние стоимость время пропускную способность и т. Определить наикратчайший путь между вершиной 1 и вершиной 7 на графе с циклами представленном на рис. Рис. Матрица транспортных расходов соответствующая данному графу представлена на рис.

Русский

2013-10-27

2.43 MB

56 чел.

Лабораторная работа 3_2. Определение кратчайшего пути между вершинами ориентированного графа с циклами.

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

Пример. Определить наикратчайший путь между вершиной 1 и вершиной 7 на графе с циклами, представленном на рис.1.

Рис.1

Для решения задачи в процедуре EXCEL «Поиск решения», представим ее как транспортную задачу с промежуточными пунктами. Будем считать, что транспортные расходы при перевозке одной единицы груза равны (в условных единицах) расстояниям между вершинами. Одна единица груза отправляется из вершины 1 (исходный пункт) и должна прибыть в вершину 7 (пункт назначения). Вершины 2, 3, 4, 5, 6 рассматриваются как промежуточные пункты, которые являются одновременно и исходными пунктами и пунктами назначения.

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

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


Исходные

пункты

Пункты назначения

Количество груза

2

3

4

5

6

7

отправ. из пункта

1

2

4

4

3

М

М

1

2

0

М

3

М

2

М

0

3

М

0

5

9

М

М

0

4

5

4

0

5

14

М

0

5

М

4

3

0

4

25

0

6

6

М

13

6

0

4

0

Колич. груза прибыв.в пункт

0

0

0

0

0

1

Рис.2

Буквой М обозначается случай, когда между соответствующими вершинами нет пути. В качестве М берут число, значительно большее самого большего пути. В данной задаче наибольший путь между 5-й и 7-ой вершинами, поэтому можно взять, например, М=50. Для промежуточных пунктов 2, 3, 4, 5, 6 должны быть предусмотрены буферные емкости В. Буферная емкость должна быть не меньшей, чем количество груза, которое перемещается в сети, описываемой графом. В данной задаче В=1. После введения буферных емкостей в первый столбец и нижнюю строку таблицы и замены М=50, получим транспортную задачу, представляющую задачу о назначениях (Рис.3).

Исходные

Пункты назначения

Количество груза

пункты

2

3

4

5

6

7

отправ. из пункта

1

2

4

4

3

50

50

1

2

0

50

3

50

2

50

1

3

50

0

5

9

50

50

1

4

5

4

0

5

14

50

1

5

50

4

3

0

4

25

1

6

6

50

13

6

0

4

1

Колич. груза прибыв.в пункт

1

1

1

1

1

1

Рис.3

Последовательные преобразования матрицы транспортных расходов показаны на рис.4а, 4б, 4в.

2

3

4

5

6

7

2

3

4

5

6

7

1

2

4

4

3

50

50

0

2

2

1

48

48

2

0

50

3

50

2

50

0

50

3

50

2

50

3

50

0

5

9

50

50

50

0

5

9

50

50

4

5

4

0

5

14

50

5

4

0

5

14

50

5

50

4

3

0

4

25

50

4

3

0

4

25

6

6

50

13

6

0

4

6

50

13

6

0

4

Рис. 4а

Рис. 4б

2

3

4

5

6

7

2

3

4

5

6

7

1

0

2

2

1

48

44

0

1

1

0

47

43

2

0

50

3

50

2

46

0

49

2

49

1

45

3

50

0

5

9

50

46

51

0

5

9

50

46

4

5

4

0

5

14

46

6

4

0

5

14

46

5

50

4

3

0

4

21

51

4

3

0

4

21

6

6

50

13

6

0

0

6

50

13

6

0

0

Рис. 4в

Рис.5

На рис.4б показаны результаты вычитания минимального элемента первой строки (он равен 2) из первой строки, на рис.4с приведены результаты вычитания минимального элемента из шестого столбца (он равен 4) и результат вычеркивания строк и столбцов с нулями. На рис.5 показаны результаты вычитания минимального элемента (он равен 1) из невычеркнутых элементов, и результат вычеркивания строк и столбцов второй раз.

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

0

0

0

0

46

42

0

48

1

48

0

44

52

0

5

10

50

46

7

4

0

6

14

46

51

3

2

0

3

20

8

50

13

7

0

0

Рис.6

Перенеся эти результаты на исходную таблицу (рис.2), получим новую таблицу (рис.7).

Исход.

Пункты назначения

Количество груза

пункты

2

3

4

5

6

7

отправ. из пункта

1

2

4

4

3

М

М

1

2

0

М

3

М

2

М

0

3

М

0

5

9

М

М

0

4

5

4

0

5

14

М

0

5

М

4

3

0

4

25

0

6

6

М

13

6

0

4

0

Колич. груза прибыв.в пункт

0

0

0

0

0

1

Рис.7

Наикратчайший путь из вершины 1 в вершину 7 определяется следующей траекторией:

1 2 6 7

Длина наикратчайшего пути равна: 2+2+4=8.

II. Решение задачи в процедуре EXCEL  «Поиск решения»

1) Ввод данных. Переносим данные задачи в EXCEL. Результаты заполнения таблицы EXCEL можно увидеть на рис.8:

Рис.8

В ячейках B4:G9 введены длины путей из исходных пунктов в пункты назначения.

Ячейки B12:G17 являются изменяемыми ячейками для нашей процедуры.

В ячейках B18:G18 находятся суммы значений соответствующих столбцов изменяемых ячеек.

в ячейке B18 находится сумма ячеек B12:B17;

в С18 находится сумма ячеек С12:С17;

в D18 находится сумма ячеек D12:D17;

в E18 находится сумма ячеек E12:E17;

в F18 находится сумма ячеек F12:F17;

в G18 находится сумма ячеек G12:G17.

В ячейках H12:H17 находятся суммы значений соответствующих строк изменяемых ячеек.

в ячейке H12 находится сумма ячеек B12 : G12;

в H13 находится сумма ячеек B13:G13;

в H14 находится сумма ячеек B14:G14;

в H15 находится сумма ячеек B15:G15;

в H16 находится сумма ячеек B16:G16;

в H17 находится сумма ячеек B17:G17.

Целевая функция заносится в ячейку I3 и вычисляется по формуле «СУММПРОИЗВ (B4:G9 ; B12:G17)».

2) Заполнение окна процедуры «Поиск решения». 

целевая функция : I3;

значение целевой функции : min;

изменяемые ячейки: B12:G17;

ограничения задачи :

B18:G18 = 1 и H12:H17 = 1;

B12 : G17  0 (ячейки должны иметь положительные значения).

В окне «Параметры» установить «Линейная модель», что соответствует решению задачи симплекс-методом. Результаты заполнения окна показаны на рис.9:

Рис.9

  1.  Выполнив процедуру «Поиск решения» в первоначальной таблице (рис. 8) получим следующие результаты (рис.10):

Рис. 10

Путь минимальной длины:1 2 6 7, длина = 8. Эти результаты совпадают с решением данной задачи преобразованием матрицы транспортных расходов, приведенным выше.

Контрольные упражнения.  Задания.

  1.  Представить задачу об определении кратчайшего пути как транспортную с промежуточными пунктами.  Составить матрицу задачи и решить ее как транспортную, используя  процедуру поиска решения Excel/
  2.  Рассмотреть задачу из п.1 как задачу о назначениях и решить ее, используя преобразование матрицы стоимости.


Варианты

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15


 

А также другие работы, которые могут Вас заинтересовать

41447. Суть гідролізу, його види. Складання рівнянь гідролізу різних солей 476.5 KB
  Суть гідролізу його види.Складання рівнянь гідролізу різних солей.Суть гідролізуйого види. Як показано в прикладі розчин став лужним внаслідок гідролізу солі СНзСООNа.
41448. OKИCHO-BIДHOBHI PEAKЦIЇ 764.5 KB
  З змiнoю cтyпeня oкиcнeння eлeмeнтiв якi вxoдять дo cклдy виxiдниx peчoвин т пpoдyктiв peкцiї xiмiчнi peкцiї мoжн пoдiлити н двi гpyпи. Цe peкцiї: пoдвiйнoгo oбмiнy бo витicнeння кoмплeкcoyтвopeння дeякi peкцiї poзклдy peкцiї iзoмepизцiї пoлiмepизцiї coцiцiї тoщo: Дo дpyгoї гpyпи нлeжть peкцiї щo вiдбyвютьcя iз змiнoю cтyпeнiв oкиcнeння eлeмeнтiв peгyючиx peчoвин т пpoдyктiв peкцiї. Tкi peкцiї нзивютьcя oкucнoвiднoвнuмu нпpиклд: У пpoцeci цiєї peкцiї cтyпiнь oкиcнeння Цинкy змiнюєтьcя вiд 0 дo 2 Гiдpoгeнy вiд 1 дo 0....
41449. EЛEKTPOЛIЗ, ЙОГО СУТЬ ТА ЗНАЧЕННЯ 1012 KB
  Суть електролізу Особливості електролізу розплавів та розчинів. Практичне значення електролізу. Суть електролізу Особливості електролізу розплавів та розчинів. : Закони електролізу вперше були сформульовані видатним англійським фізиком М.
41450. ВЛАСТИВОСТІ ГАЛОГЕНІВ. ВОДНЕВІ СПОЛУКИ ГАЛОГЕНІВ 851.5 KB
  Добування і властивості хлору. На відміну від Хлору Брому Йоду й Астату Флуор в усіх своїх сполуках виявляє ступінь окиснення тільки З електронних структур видно що в атомах Хлору Брому Йоду й Астату в зовнішньому електронному шарі є вакантні dорбіталі. πЗв'язок помітно зміцнює молекулу і тому енергія дисоціації молекули хлору СІ2 239кДж моль значно більша ніж молекули фтору F2 1588 кДж моль.
41451. ОКСИГЕНОВМІСНІ СПОЛУКИ ГАЛОГЕНІВ 837 KB
  Оксигеновмiсні сполуки хлору їх особливості.Оксигеновмiсні сполуки хлору їх особливості. Непрямим способом добуто ряд сполук Хлору з Оксигеном але всі вони нестійкі. За температури 25С порівняно стійкими є такі оксигеновмісні сполуки Хлору: СІ2О СlO2 Сl2О6 Сl2O7.
41452. СІРКА. КИСНЕВІ ТА ВОДНЕВІ СПОЛУКИ СІРКИ 877.5 KB
  Оскільки атом Оксигену містить тільки два неспарені електрони він може лише двояко сполучатись у молекули: О О і О О О й утворювати тільки дві алотропні видозміни: кисень та озон.8 Полоній Po 6s26p46d0 0137 843 254 Оксиген та кисень. Кисень проста речовина утворена Оксигеном міститься в атмосферному повітрі у зв'язаному стані Оксиген входить до складу води кварцу силікатів алюмосилікатів сполук тваринного і рослинного походження. Вперше кисень у чистому вигляді добув шведський хімік К.
41453. СІРЧАНА КИСЛОТА, ЇЇ ВЛАСТИВОСТІ, ОДЕРЖАННЯ. СУЛЬФІТИ, СУЛЬФАТИ 764.5 KB
  Biдoмo кiльк cпoлyк Cyльфypy з Oкcигeнoм. Пpктичнe знчeння мють двi з ниx: oкcид cyльфypyIV т oкcид cyльфypyVI. Oкcид cyльфypyIV дoбyвють cплювнням npocтoї peчoвини cipки бo виплювнням пipитy. Oкcид cyльфypylV yтвopюєтьcя ткoж пiд чc пepeбiгy дeякиx мeтлypгiйниx пpoцeciв пiд чc cплювння км'янoro вyгiлля дo cклдy якoгo звжди вxoдить cipк.
41454. НЕМЕТАЛИ V ГРУПИ. АЗОТ. ВОДНЕВІ СПОЛУКИ АЗОТА 672 KB
  Hiтpиди 5eлeмeнтiв I т II гpyп пepioдичнoї cиcтeми кpиcтлiчнi peчoвини дocить ктивнi cпoлyки; вoни лeгкo poзклдютьcя вoдoю з yтвopeнням лyгy й мiкy: Hiтpиди seлeмeнтiв мeтлiчнi cпoлyки. Peгyючи з вoднeм y pзi пpoпycкння eлeктpичнoї icкpи зoт yтвopює дeякy кiлькicть мiкy: Цeй cпociб дoбyвння мiкy бyв зпpoпoнoвний нiмeцьким xiмiкoм Ф. Згiднo з пpинципoм лe Штeльє для yтвopeння мiкy нйcпpиятливiшими бyдyть виcoкий тиcк i низьк тeмпepтyp. Ocкiльки з низькиx тeмпepтyp peкцiя вiдбyвєтьcя пoвiльнo тo для пpиcкopeння пpoцecy cинтeз мiкy вeдyть...
41455. ОKCИГEHOBMICHI CПOЛУKИ HITPOГEHУ 1.08 MB
  Bci oкcиди нiтpoгeнy з виняткoм N2O дyжe oтpyйнi. Oкcид нiтpoгeнyI дoбyвють нгpiвнням нiтpтy мoнiю: Moлeкyл N2O мє лiнiйнy бyдoвy дoвжин зв'язкy dNH=0113 нм dNO= 0118 нм; N2O нecoлeтвopний oкcид тepмoдинмiчнo нecтiик cпoлyк Gf0 = 104 кДж мoль. Oкcид нiтpoгeнyI бeзбpвний гз coлoдкyвтий н cмк; мє cлбкий пpиeмний зпx тeмпepтypy плвлeння 91C тeмпepтypy кипiння 88 C Bдиxння вeликoї кiлькocтi N2O викликє cтн пoдiбний дo cпянiння звiдcи йoгo iнш нзв вeceлильний гз. N2О пoгнo poзчиняєтьcя y вoдi в 1 oб'ємi H2О з...