Постановка задачи. 
Задача о стоимости информационных сетей

Для начала дадим определение понятию информационная сеть.

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

Моделью нашей информационной сети будет простой ориентированный связный граф с памятью. Пропускная способность ветви довольно часто является моделью максимально возможного объема потока, который может передаваться через данную ветвь. Если в некоторую вершину входит поток, больший того, который может быть передан одновременно через исходящие направленные ветви, то избыточный поток должен запоминаться в данной вершине, в противном случае он будет утерян. Следовательно вершина должна иметь систему памяти.

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

Решением линейных оптимизационных задач в экономике занимались Л. Канторович и Дж. Данциг, С. Гасс и Т. Саати («транспортная» задача) и другие. В данной работе задача сводится к решению задачи линейного программирования.

Потоки в сетях с заданными пропускными способностями ветвей

Сеть — ориентированный простой связный граф без петель и параллельных дуг.

Поток — целые числа, назначенные дугам сети, которые интерпретируются как скорости потока вещества в дугах.

Источник — вершина сети, в которой выходной поток больше входного.

Сток — вершина сети, в которой входной поток больше выходного.

Сеть с ограниченной пропускной способностью — сеть, в которой поток по каждой дуге заключен между нулем и верхней границей, называемой пропускной способностью дуги.

Будем предполагать, что пропускные способности заданы. Дополнительно предполагаем, что они неотрицательны и целочисленны: с_i — пропускная способность i-ой ветви. В сети задан поток: _i — величина потока в i-ой ветви. Поток называется допустимым, если 0? ф_i? с_i. Величина потока в вершине x равна разности между выходящим потоком из вершины х и входящим потоком в вершину х. Пусть:

— множество дуг, выходящих из х.

— множество дуг, входящих в х.

Если Q (x)=0, то вершина называется промежуточной;

Если Q (x)>0, то это источник;

Если Q (x)<0, то это сток.