Исследование операций (стр. 8 )

U2 = 0 + 2 =2

U3 = min(U1+d13, U2+d23) = min(0+8,2+3) = 5; i = 1,2

U4 = min(U1+d14) = min(0+11)=11

U5 = min(U1+d15, U2+d25) = min(0+9,2+5) = 7

U6 = min(U2+d26,U3+d36,U4+d46 ,U5+d56) = min(2+1,5+2,11+2,7+7) = 3

U6 = min(U4+d47,U5+d57,U6+d67) = min(11+23,7+9,3+10) = 13

3) Проверка обратных ходов.

Формально такая проверка получается сравнением dij с Uj-Ui :

Если dij <Uj -Ui , (*) то значения Uj меняется на Uj = Ui + dij,

Такая замена означает, что «обратный» ход стал более выгоден чем прямой.

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

	1	2	3	4	5	6	7	Ui
1		2	5	11(8)	7(4)			0
2	-2		3		5(2)	1		2
3	-5	-3				-2		5
4	-11(-8)		-6(-3)			-8(-5)	2(5)	11(8)
5	-7(-4)					-4(-1)	6(9)	7(4)
6		-1	2	8(5)	4(1)		10	3
7				-2(-5)	-6(-9)	-10		13

В таблице только те значения, для которых есть dij. Условия dij < Uj - Ui- выполнилось для d64: 8 > 5 и d65 : 4 > 1, новые значения Uj=Ui+dij :

U4= U6 + d64 = 3+5 =8;

U5= U6 + d65 = 3+1 =4.

Данные таблицы после пересчета показаны в скобках.

Теперь осталось только разобраться в том, каким образом по данным таблицы определить оптимальный путь.

4. Нахождение оптимального пути.

Для нахождения оптимального пути пользуются формулой: Uj=Ui+dij, например: U7=Ui+di7, di7 находятся в 7 столбце таблицы коэффициентов. U7=13.

Формуле удовлетворяют 3 варианта:

U7=U6+d67 13=3+10 далее: U6=U2+d26;3=2+1 U2=U1+d12;2=0+2 Оптимальный путь: 1®2®6®7

U7=U5+d57 13=4+9 далее: U5=U6+d65;4=3+1 U6=U2+d26;3=2+1 U2=U1+d12;2=0+2 Оптимальный путь: 1®2®6®5®7

Как видно существуют два равноценных пути.

Вопросы:

1.   Найдите по таблице кратчайший путь из 1 в 4 (1®2®6®4,U4=8)

2.   Из 1 в 5 (1®2®6®5, U5=4)

В заключение заметим, что существует много задач далеких от «транспортных», которые сводятся к задачам о кратчайшем пути.

3.3 Задача о максимальном потоке.

Пусть есть сеть (трубопровод, ЛЭП, информационная система) между двумя узлами s и t. Цифрами обозначены пропускные способности дуг цепи Cij, i и j - номера соответствующих узлов цепи.

В задаче требуется определить максимальный поток (нефти, информации и т. д.), который способна передать система из S в t за единицу времени.

Алгоритм решения задачи:

1. Выбирается любая цепь, соединяющая s с t .

2. Обозначим (Cij)- - пропускные способности дуг, составляющих эту цепь, (Cij)+ - сиоответствующих им дуг обратного направления.

3. Определим q = min (Cij) > 0

4. Вычтем q из всех (Cij)- и прибавим q к (Cij)+

5. Выбирается любая другая цепь, соединяющая s и t и т. д.

6. Когда не останется ни одного пути от s к t, полученные значения Cij используются для расчета потока в дугах:

(А)

Где cij- пропускные способности исходной сети,

(Cij)*- пропускные способности модифицированной сети.

ЛЕКЦИЯ 10

Максимальный поток из S в t равен:

т. е. определяется как сумма потоков, вытекающих из узла S или как сума потоков, втекающих в узел t.

Пример:

Рассмотрим сеть на рис. (*)

1) Составим матрицу пропускных способностей:

	S	1	2	3	4	t
S		10 –	3	14	4
1	5+		5	9	5 –
2	5	6		15		10
3	12	7	10		7	2
4	3	9+		8		13 –
t			3	4	5+

Столбцы таблицы показывают пропускные способности входящих в узлы дуг, строки – вытекающих из узла дуг.

2) Выберем произвольную цель. Проще всего ее выбрать прямо по матрице. Положительные значения коэффициентов в столбцах каждой из строк показывают, что в узлы можно попасть из данного узла.

Например: СS1 = 10 показывает возможность S _ 1

C14 = 5 показывает возможность 1 _ 4

C4t = 13 показывает возможность 4 _ t

Т. о. мы выбрали цепь (S > 1> 4 > t), одну из возможных. Обозначим ее дуги СS1,C14, C4t знаком “–“, а противоположные им С1S, C41, Ct4 знаком “+“

3) Найдем q = min {Cij} = min {10, 5, 13} = 5

1) Новые значения Cij заносим в таблицу

	S	1	2	3	4	t
S		5	3	14 –	4
1	10		5	9	0
2	5	6		15+		10 –
3	12+	7	10 –		7	2
4	3	14		8		8
t			3+	4	10

5) Выбираем произвольную цепь: (S > 3> 2 > t), обозначаем С+ij и С–ij