В информационно-вычислительной сети

В информационно-вычислительной сети (ИВС), состоящей из множества вычислительных систем - узлов, соединенных линиями связи, часто требуется решение различных задач маршрутизации. Например, каким образом (т.е. по каким из имеющихся каналов связи) в течение определенного промежутка времени осуществить передачу нескольких информационных сообщений разного объема из одного узла сети в ряд других узлов с минимальными затратами.

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

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

ИВС задается в виде графа, в котором вершины соответствуют узлам сети, обозначаемым латинскими буквами, а дуги - каналам связи, идентифицируемым номерами.

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

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

Определите оптимальные маршруты передачи данных в сети с конфигурацией и параметрами, заданными в следующих таблицах.

Сведения о вершинах (узлах ИВС)

Вершина (узел ИВС)	Примечание
A	Источник данных
B	Транзитный узел
C	Получатель данных объемом 10 и.е.
D	Транзитный узел
E	Транзитный узел
F	Получатель данных объемом 6 и.е.

Сведения о дугах (линиях связи)

№	Связываемые вершины	Пропускная способность (и.е.)	Стоимость передачи 1 и.е. (у.е.)	Стоимость аренды линии связи (у.е.)
1	A, B	25	6	10
2	A, E	15	1	6
3	B, C	8	3	7
4	B, D	17	1	6
5	C, D	7	5	7
6	C, F	11	4	10
7	D, F	9	2	6
8	E, D	12	2	7
9	E, F	5	5	7

Оптимальное решение задачи обеспечивает затраты на передачу данных, равные 157 у.е.

Список использованной литературы

1. Фратер Г. Excel 5.0: Пер. с нем. Киев: Торгово-издательское бюро BHV, 1995. 560 с.

2. Курицкий Б.Я. Поиск оптимальных решений средствами Excel 7.0. СПб.: BHV-Санкт-Петербург, 1997. 384 с.

3. Поляков В.В., Карпов А.В., Кузнецов В.А. Решение оптимизационных задач в среде табличного процессора Quattro Pro: Методические указания. Петрозаводск: Изд-во ПетрГУ, 1994. 37 с.

Владимир Витальевич Поляков

Сергей Тимофеевич Коржов

Александр Вениаминович Карпов

Решение задач математического программирования

в среде табличного процессора Excel

Методические указания

Редактор Л.П.Соколова

Подписано к печати 10.10.98. Формат 60x841/16.

Бумага типографская. Офсетная печать. 1,1 уч.-изд. л.

7 усл. кр.-отт. л. Тираж 150 экз. Изд. № 135 “С”.

Издательство Петрозаводского государственного

университета