![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
|
![]() |
![]() |
||||||
![]() |
Eng | Rus | Ukr | ![]() |
![]() |
||||
![]() |
|||||||
![]() |
![]() |
||||||
![]() |
![]() |
![]() |
|||||
![]() |
Компьютерные сети
|
16.01.2005
|
![]() |
![]() |
|||
3.6. Задача распределения потоков. 3.6.1.Постановка задачи. Задана структура сети G=(X,E), пропускные способности всех каналов
при условии Выше было доказано, что функция которая тоже вогнута, а потом к эквивалентной задаче минимизации Учитывая, что вероятности 3.6.2.Алгоритм решения задачи РП Алгоритм А2 состоит из начального этапа и конечного числа однотипных итераций. На начальном этапе строим начальный допустимый поток, совместимый с матрицей H и удовлетворяющий условию k-тая итерация: Пусть есть поток 1. Найдём условные длины всех дуг: 2. Находим кратчайшие пути в метрике 3. Распределяем все потоки по кратчайшим путям и находим общий поток по кратчайшим путям 4. Рассчитываем стоимостной показатель для потока V(k): и для потока 5. Если 6. Построим выпуклую комбинацию потоков 7. Находим значение критерия и находим такое
8. Находим Начальный этап. Допустим, что задан суммарный внешний поток 1. Приравниваем 2. Пускай Если Если 3. Приравниваем 4. Находим условные длины путей: 5. Находим кратчайшие пути Дальше находим оптимальное значение 6. Если 7. Приравниваем n=n+1 и переходим к шагу 2. |
![]() |
||||||
![]() |
|||||||
Copyright © 2002-2004 | ![]() |
||||||
![]() |
![]() |