Первый этап. 0-шаг. W(t):=0; вершину t считаем временной помеченной вершиной, для всех iÎE\{t} W(i):=M , вершины iÎE\{t} не помечены..

0 - шаг. W(t): =0; вершину t считаем временной помеченной вершиной, для всех iÎ E\{t} W(i): =M, вершины iÎ E\{t} не помечены..

k- ый шаг. Среди всех временно помеченных вершин i ищем вершину j с наименьшим значением W. Вершину j помечаем постоянной пометкой. Если j=s, то переходим к выполнению второго этапа, в противном случае просматриваем вершину j. Для этого для всех vÎ V ^-(j) выполнить:

1.определяем i=h2(v),

2.если вершина i непомечена постоянной пометкой, то

W(i): =min(W(i), c(v)+W(j)),

эта вершина помечается временной пометкой. Переходим к выполнению (k+1) шага.

 

Второй этап. (восстановление кратчайшего пути)

0 - шаг. i (0): =s;

k - ый шаг. Среди vÎ V ⁺(i (k-1)) ищем v (k-1), для которой

W(h1(v (k)))=c(v (k))+W(i (k-1)),

i (k): =h1(v (k)).

Если i (k)=t, то алгоритм заканчивает работу, в противном случае переходим к выполнению (k+1) -го шага.

 

В результате выполнения второго этапа получим

t= i (k), v (k-1), i (k-1), v (k-2),..., v (0), i (0)=s,

являющееся решением задачи.

Задание 15.3

 

Решить предыдущую задачу алгоритмом Дейкстры. Результаты представить в виде таблицы 2 и выписать кратчайший путь.

Литература.

 

1. Моисеев Н.Н. Математические задачи системного анализа.-М., Наука, 1981, 487 с.

2. Гермейер Ю.Б. Введение в теорию исследования операций. - М., Наука, 1971.

3. Зайченко Ю.П. Исследование операций. - Киев, Вiща школа, 1975.

4. Коваленко А.Г. Элементы выпуклого векторного программирования. Учебное пособие. - Самара, 1990, 83 стр.

5. Коваленко А.Г., Власова И.А. Цветков Ю.Д. - Лабораторный практикум по методам оптимизации. - Куйбышев, СамГУ, 1991, 59 стр.

6. Подиновский В.В., Ногин В.Д. Парето - оптимальные решения. М., Наука, 1971.

7. Дубов Ю.А. и др. Многокритериальные модели формирования и выбора вариантов систем. М., Наука, 1986.

8. Романовский И.В. Алгоритмы решения экстремальных задач. М. Наука, 1977.

9. Коваленко А.Г. Алгоритмы решения некоторых задач оптимизации многошаговых процессов. Куйбышев, 1985, 72 стр.

10.Тетерев А.Г. Динамическое программирование в курсе исследования операций. - Куйбышев, 1983.

11.Исследование операций под ред. Дж.Моудера, С.Элмаграби. М., " Мир", 1981, т.1, 2.

12. Корбут А.А., Финкельштейн Ю.Ю. Дискретное программирование. М. Наука М., Наука, 1971.

13. Райфа Г. Анализ решений. - М., Мир, 1977.

14. Хедли Дж. Нелинейное и динамическое программирование. - М., Мир, 1967.

15. Ху Т. Целочисленное программирование и потоки в сетях. М., Мир, 1971.

16. Танаев В.С., Шкурба В.В. Введение в теорию расписаний. М., Наука, 1975.

17.Беллман Р., Дрейфус С. Прикладные задачи динамического программирования. М., Мир, 1965.

18. Акоф Р., Сасиени М. Основы исследования операций. М. Мир. 1971.

19. Нейман Дж., Моргенштерн О. Теория игр и экономическое поведение. М., «Наука», 1970.

20.Подиновский В.В., Ногин В.Д. Парето-оптимальные решения многокритериальных задач. М. Наука, 1982, 256 с.

21.Ларичев О. И. Объективные модели и субъективные решения. М., Наука, 1987, 142 с.

22.Голиков А.И., Коткин Г.Г., Характеристика множества оптимальных оценок задач многокритериальной оптимизации. Журнал вычислительной математики и математической физики. 1988. № 10. т.28. с.1461 – 1474.

23. Машунини Ю.К. Методы и модели векторной оптимизации.М., Наука, 1986, 141 с.

24.Коваленко А.Г., Власова И.А., Федечев А.Ф. Лабораторный практикум по методам оптимизации. Изд. «Самарский университет», Самара, 1998 г.

25.Коваленко А.Г., Власова И.А., Шведова И.А. Лабораторный практикум по методам исследования операций. Изд. «Самарский университет», Самара, 1997г.

26.Юдин Д.Б., Гольштейн Е.Г. Задачи линейного программирования транспортного типа. М. «Наука» 1969.

27. Морз Ф.М., Кимбел Д.Е. Методы исследования операций. М., «Советское радио», 1956г.

 

 

[1] В настоящей главе приведены основные теоремы векторного выпуклого программирования и многокритериальной задачи без доказательств и авторы предлагают читателю самостоятельно доказать предложенные теоремы. Доказательства этих теорем можно найти в работах Коваленко А.Г. Элементы выпуклого векторного программирования [4] и Карманова В.Г. Математическое программирование [26].