Logo GenDocs.ru

Поиск по сайту:  

Загрузка...

Лекции по ТПР - файл Лекция№06-тпр.doc


Загрузка...
Лекции по ТПР
скачать (681.7 kb.)

Доступные файлы (18):

Лекция№01-тпр.doc38kb.12.11.2008 13:15скачать
Лекция№02-тпр.doc97kb.12.11.2008 13:25скачать
Лекция№03-тпр.doc179kb.12.09.2004 22:30скачать
Лекция№04-тпр.doc146kb.12.09.2004 22:31скачать
Лекция№05-тпр.doc131kb.12.09.2004 22:32скачать
Лекция№06-тпр.doc248kb.12.09.2004 22:33скачать
Лекция№09.doc177kb.03.10.2006 21:09скачать
Лекция№10-тпр.doc179kb.12.09.2004 22:49скачать
Лекция№11-тпр.doc353kb.25.11.2005 11:46скачать
Лекция№12-тпр.doc205kb.12.09.2004 22:53скачать
Лекция№13-тпр.doc191kb.12.09.2004 22:54скачать
Лекция№14-тпр.doc83kb.14.12.2004 14:25скачать
Лекция№15-тпр.doc301kb.12.09.2004 23:02скачать
Лекция№16-тпр.doc131kb.12.09.2004 23:04скачать
Лекция№17-тпр.doc542kb.12.09.2004 23:03скачать
Лекция№7-тпр.doc142kb.12.09.2004 22:38скачать
Лекция№8-тпр.doc93kb.12.09.2004 22:44скачать
Лекция№9-тпр.doc142kb.12.09.2004 22:47скачать

Лекция№06-тпр.doc

Реклама MarketGid:
Загрузка...
Лекция №6

Алгоритм поиска кратчайших путей.

Запишем двойственную задачу по отношению к исходной (1)-(5). При этом в двойственной задаче столько же переменных, сколько ограничений в исходной, и столько же ограничений, сколько в исходной задаче переменных. Ограничения (2)-(4) записаны для каждого узла сети, поэтому в двойственной задаче будет содержаться n переменных, т.е. вектор двойственных переменных запишется:

.

Тогда двойственная ЗЛП будет иметь вид:

(6)

Здесь - вектор ограничений (2)-(4), в котором на r-том месте стоит 1, а на s-том стоит –1. - вектор коэффициентов в ограничениях (2)-(4), в котором на i-том месте стоит 1, а на j-том стоит -1. Двойственные переменные не ограничены по знаку. В скалярной форме (6) запишется:

(7)

Также как и в методе потенциалов, одну из двойственных переменных можно назначить произвольно. Пусть . Для удобства записи сделаем замену: . Тогда задача (7) примет вид:

(8)

(9)

(10)

Таким образом, вместо исходной задачи (1)-(5) необходимо решить двойственную задачу (8)-(10). Для этого исходные данные записываются в следующую таблицу:

























i j

1



r



s



n




1








































r













































n

















Клетки строк и столбцов заполняются величинами по мере решения задачи (8)-(10). Остальные клетки соответствуют дугам и заполняются значениями длин дуг . Оставшиеся клетки не заполняются и в расчетах не участвуют.

Вначале в строке и столбце с номерами r записываются нулевые значения . Далее последовательно заполняются элементы столбцов начиная с №1. Для определения элемента просматривается столбец №j и если в этом столбце существует хотя бы одна клетка с известным элементом и известным значением , то вычисляется :



Минимум берется среди всех клеток , для которых известны и . Найденные значения записываются в строке и столбце с номером j. Этот процесс продолжается до тех пор, пока не определится для конечного узла s искомого пути.

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

Если при просмотре столбцов с неизвестными значениями невозможно их определить, то это значит, что до этих узлов j не существует пути из узла r. Строки и столбцы, соответствующие узлу j, из таблицы вычеркиваются.

Пусть найдены все для конечных узлов . Далее поверяются условия оптимальности (9). При этом возможны 2 случая:

  1. Для любых дуг справедливо неравенство . Это означает, что кратчайшие пути найдены.

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

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

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

Сам кратчайший путь, т.е. узлы, через которые он проходит, восстанавливается следующим образом: в столбце s находится клетка , для которой . Такая клетка обязательно существует. Дуга будет последним звеном искомого пути. Далее в столбце с номером находится клетка , для которой . Дуга будет предпоследним звеном цепи. Далее просматривается столбец и т.д. до тех пор, пока не найдется первое звено пути , для которого .

Таким образом, найден путь . Длина этого пути

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

Так как предполагается, что для дуг пути выполняются неравенства (9), то можно записать:









Если сложить левые и правые части этих неравенств, то можно записать . Таким образом . Что и требовалось доказать.

Пример.

Найти кратчайший путь на заданной транспортной сети из узла №3 в узлы №5 и №7.




r=3, s=5,7.






2

6

0

3

8

10

11



i j

1

2

3

4

5

6

7

6

1




4

3

1










6

2













2







0

3

2



















3

4







1







7




8

5







5

1







4

10

6




4













1

11

7























Полагаем сначала . Далее:

  1. j=1, v=3, =2. .

  2. j=2, v=1, =4. =2=6.

  3. j=4, v=1, =1. =2=3.

  4. j=5, v=6, =2. =6=8.

  5. j=6, v=4, =7. =3=10.

  6. j=7, v1=5, =4. =8=12

v2=6, =1. =10=11

=11.

Проверка на оптимальность:

  1. (1,2): =4= 7. (4,6): =7=

  2. (1,3): =-2< 8. (5,3): =-8<

  3. (1,4): =1= 9. (5,4): =-5<

  4. (2,5): =2= 10. (5,7): =3<

  5. (3,1): =2= 11. (6,2): =-8<

  6. (4,3): =-3< 12. (6,7): =1=

Условие оптимальности выполняется для всех . Длина пути ==11, ==8.

Восстановление пути:

  1. Путь : (3,1,4,6,7)

  2. Путь (3,1,2,5).



Скачать файл (681.7 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации
Рейтинг@Mail.ru