Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 12)

Следовательно, выделив x_n-1 и повторив все предыдущие рассуждения приходим к выводу:

(4)

Систематизируя изложенное, получим рекуррентные зависимости: (5), (4), (3):

(5)

т.к. .

В некоторых задачах целевая функция носит мультипликативный характер:

(6)

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

Пример:

Пусть n = 3, b_n = 4, a_i = 1, m = 4.

Ф₂(x) – наилучшая эффективность, когда x ресурсов выделяют первой и второй задаче (0 ≤ x ≤ b_n).

(j, i) – способ распределения ресурсов соответствующий Ф₂(х),

i ресурсов выделяют задаче 1,

j ресурсов выделяют задаче 2.

i + j = x.

Ф₃(х) – наивысшая эффективность, когда x ресурсов выделяют трем задачам.

(k, j, i) – способ распределения ресурсов, соответствующий Ф₃(х),
k + j + i = x, k ресурсов выделяют задаче 3.

X	f1(x)	f2(x)	f3(x)	Ф2(х)	Ф3(х)	(j, i)	(k, j, i)
0	0	0	0	0	0	0,0	0,0,0
1	0,1	0,2	0,3	0,2	0,3	1,0	1,0,0
2	0,3	0,2	0,3	0,3	0,5	1,1 0,2	1,1,0
3	0,4	0,3	0,4	0,5	0,6	1,2	1,1,1 1,0,2
4	0,4	0,6	0,5	0,6	0,8	1,3 4,0	1,1,2

На первой итерации будем распределять ресурсы только первой и второй задаче:

Далее исследования можно продолжать согласно:

,

т.е. необходимо рассматривать не все возможные комбинации, а только те, которые на первом шаге были выделены как перспективные:

Лабораторная работа № 7 (4 часа)

Задача о кратчайшем маршруте в ациклической сети

Предположим, что известна топология сети (N):

Каждый узел сети обозначает некоторое состояние исследуемой системы.

Узел 1 – исток, начальное состояние;

Узел 10 – сток, конечное состояние;

С_ij – стоимость перехода из i состояния в j.

Будем искать кратчайший маршрут из состояния 1 в 10.

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

y_j – стоимость, отвечающая стратегии минимальных затрат для пути от узла j до стока;

S_j – решение, позволяющее достичь y_j.

Поскольку из состояния 10 число оставшихся шагов равно 0, то

.

Очень легко можно вычислить y₉ и y₈:

,

.

Вычислим y₇:

, .

Теперь можно обнаружить известную методичность и алгоритм поиска оптимальной стратегии представить в виде рекуррентного состояния:

, .

Упорядоченная запись остальных вычислений выглядит так:

;

, ;

, ;

, ;

, ;

, ;

Искомый маршрут имеет длину 17 и представляет собой последовательность событий: 1 – 3 – 7 – 9 – 10.

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

Таблица 5

j	Состояние	1	2	3	4	5	6	7	8	9	10
yj	Расстояние до стока	17	16	12	18	8	4	5	1	4	0
Sj	Ближайший адрес	3	6	7	7	8	8	9	10	10	*

Например, маршрут 2 – 10 имеет длину 16 и представляет собой последовательность событий 2 – 6 – 8 – 10.

Пример: Пусть задана топология сети.

В результате использования алгоритма определения кратчайшего маршрута получим:

, ;

, _;

, ;

, ;

, ;

, ;

, ;

, .

Кратчайшие маршруты из любого узла в узел-сток можно определить по таблице:

j	1	2	3	4	5	6	7	8
yj	0	1	2	3	5	6	7	8
Sj	*	1	2	3	4	4	6	7

Кратчайший маршрут в сети общего вида

В ациклической сети можно было пронумеровать узлы сети от 1 до р таким образом, что если сеть содержит дугу (i,j), то i<j. Чтобы добиться этого условия присвоим стоку номер р. Зачеркнем этот узел и все входящие в него дуги и не будем их рассматривать в дальнейшем при присвоении номеров.

Возьмем любой другой узел, имеющий теперь только входящие в него дуги, и припишем ему номер р-1. Будем продолжать этот процесс, пока все узлы не будут пронумерованы. В этом случае y_k – длину маршрута k-р можно определить рекуррентно.

В сети общего вида, которая имеет петли, такую нумерацию установить не удается.

Алгоритм отыскания кратчайшего маршрута в сети общего вида может быть записан:

1. Вычислить y_p=0, а все остальные y_k=¥.

2. Если в сети остается хотя бы одна дуга (i,j), такая, что , вычислить . В противном случае останов.

Краткая математическая запись условий, которым должны удовлетворять все y_i, имеет вид:

Вычисления можно проводить в различном порядке.

На самом узле с помощью этого алгоритма отыскиваются кратчайшие маршруты из всех узлов в конечном узле.

П

j

i

ример 1:

C:

Уточнение длины (yi) кратчайшего маршрута				4	2
				5	3	1
				¥	¥	¥	0
			i \ j	1	2	3	4
4	5	¥	1		2	3	5
2	3	¥	2			1	3
	1	¥	3		1		1
		0	4
Уточнение ближайших адресов (ai) кратчайшего маршрута				4	4	4	Ост
				3	3
				2

Характеристики

Список файлов книги