Задача о стоимости информационных сетей

Размещено на http://www.allbest.ru/

1

Задача о стоимости информационных сетей

1. Математическая модель информационной сети

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

1.1 Некоторые сведения из теории графов

граф задача сеть затраты

Дадим определения основным понятиям теории графов, которые потом будут использоваться в работе.

Граф - это совокупность множества вершин X, множества ребер Y и отображение инцидентности f, которое ставит в соответствие каждому ребру пару вершин.

Смежные вершины- это вершины, соединенные ребром, смежные рёбра- это рёбра, у которых общая вершина. Вершина и ребро инцидентны друг другу, если точка - конец ребра .

Связный граф- это граф, в котором каждая пара различных вершин соединяется, по крайней мере, одной цепью.

Петля - это ребро (или дуга), инцидентное только одной вершине.

Путь - незамкнутый ориентированный маршрут без повторяющихся дуг.

Сечение - это множество ребер Y_s относительно которого множество вершин разбивается на два непересекающихся множества (стороны сечения), которые ребра из Ys и соединяют.

Параллельные рёбра - это рёбра, инцидентные одной паре вершин.

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

Цикл - это замкнутая цепь (простой цикл, если цепь простая).

Граф называется связным, если всякая пара его вершин соединяется цепью.

Подграф - любая часть графа, которая сама является графом.

1.2 Постановка задачи

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.4 Теорема о максимальном потоке и минимальном разрезе

(Форд, Фалкерсон, 1955 г.). Максимальный поток между вершинами t и s равен величине минимального сечения между этими вершинами:

maxv()=min c(L).

ЄФ LЄМ

Рассмотрим данную теорему на конкретном примере.

Пусть задан граф состоящий из 5 узлов и 7 дуг. Каждой дуге присвоена определенная пропускная способность (SJ-13, JP-8, PT-15, PS-9, SR-6, RP-10, RT-5). Также каждой дуге присвоен определенный поток не превышающий пропускную способность дуги: (SJ)=7, (JP)=7, (PT)=7, (PS)=8, (SR)=4, (TR)=4.

Размещено на http://www.allbest.ru/

1

Найдем величины потоков для каждой из вершин:

Q(S)=7+4-8=3

Q(R)=4+4-8=0

Q(J) =7-7=0

Q(P)=7+8-7-8=0

Q(T)=4-7=-3

Тогда ясно, что величина потока из Sв Tравна 3.

Всего возможно 5 разрезов, которые отделяют S от T. Выпишем эти разрезы, указав соответствующие множества вершинA,B образующие сечения:

1) A={S},B={J,P,R,T}

2) A={S,J},B={P,R,T}

3) A={S,J,R}, B={P,T}

4) A={S,J,P},B={R,T}

5) A={S,J,P,R },B={T}

Найдем пропускные способности этих сечений:

C(L₁)=6+13=19

C(L₂)=8+6=14

C(L₃)=8+10=18

C(L₄)=15+6=21

C(L₅)=15

Сечение с минимальной пропускной способностью это сечение L₂. Таким образом, данное сечение может передать поток до 14 единиц. Заданный поток имеет величину 3. Следственно мы можем увеличить величину потока в сети. Покажем, как работает алгоритм Форда-Фалкерсона для данного примера.

Шаг 1.

Добавим поток величиной 1 по цепи SJPT.

По данной цепи поток максимальный так как по дуге JP он является максимальным. Теперь поток в данной сети равен 4. Но его можно еще увеличить.

Шаг 2.

Добавим поток величиной 2 по цепи SRPT.

По данной цепи поток максимальный так как по дуге SR и RP он является максимальным. Теперь поток в данной сети равен 6. Еще увеличим поток в данной цепи.

Шаг 3.

Добавим поток величиной 4 путем уменьшения потока по цепи TRPS.

Теперь поток данной сети равен 10, но мы можем его еще увеличить так как минимальное сечение равно 14.

Шаг 4.

Увеличим поток еще на 4 путем уменьшения потока по дуге PS и увеличения потока по дуге PT.

Теперь поток в данной сети равен 14. Этот поток является максимальным по теореме Форда-Фалкерсона о максимальном потоке. То есть максимальный поток равен минимальному сечению.



2.

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

2.1 Модель сети с устройствами памяти в узлах

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

Рассмотрим взвешенный, ориентированный граф G = (X, Y, f), где X - множество вершин, Y- множество ветвей графа, f -отображение инциденции.

Пусть -- объем запоминающего устройства вершины ( i=1,…,n ),

-- пропускная способность ветви ( j=1,…,m ).

Из графа G построим ориентированный граф G* путём разбиения каждой вершины на две: и . Все ветви, входящие в вершину графа G, являются входящими в графа G*, а все ветви, исходящие из вершины графа G, становятся исходящими из графа G* для каждой В графе G* для всех i существует ветвь, направленная от к .

Структура такого графа показана на рис. 3.1

Приведем пример графа с памятью:

Размещено на http://www.allbest.ru/

1

На данном примере мы видим, что входной поток больше выходного. Значит данная вершина имеет систему памяти.

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

Размещено на http://www.allbest.ru/

1

На данном примере мы видим, что узлы R и P принимают больший поток чем отдают. Узел P принимает поток 3, а отдает 2. Значит узел P запоминает поток равный 1. А узел R принимает поток 5, отдает 3, а запоминает 2.

2.2 Задача о минимальных затратах на построение сети

Чтобы минимизировать данную функцию нам нужно выписать некоторые ограничения. Для начала выпишем ограничения для потока в сети для каждой дуги. Поток в дуге должен быть больше 0 и в то же время меньше пропускной способности данной дуги:

* * *

,

Где - величина потока в сети;

t - промежуток времени от t₀ до t;

с - пропускная способность ветви.

И при этом величина потока больше какой то заданной величины E.

Далее выпишем ограничение для каждого узла:

* * *

,

где - это память которая была заполнена на момент времени ;

- количество информации, которая поступила в узел за время от до t.

- количество информации, которая ушла из узла за время от до t.

- обьем памяти узла.

Также необходимо задать функцию максимального потока:

max,

Где с - пропускные способности ветвей.

d - память узлов сети.

h - стоимость пропускных способностей.

k - стоимость памяти узлов данной сети.

Решение нашей задачи сводится к решению уравнения линейного программирования.

2.3 Решение уравнений линейного программирования

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

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

Функция называется целевой функцией (или линейной формой) задачи, а условия - ограничениями данной задачи.

Пример 4.

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

Решение. В данной задаче требуется найти максимум функции, а система ограничений содержит четыре неравенства. Следовательно, чтобы записать ее в форме основной задачи, нужно перейти от ограничений-неравенств к ограничениям-равенствам. Так как число неравенств, входящих в систему ограничений задачи, равно четырем, то этот переход может быть осуществлен введением четырех дополнительных неотрицательных переменных. При этом к левым частям каждого из неравенств вида“?“ соответствующая дополнительная переменная прибавляется, а из левых частей каждого из неравенств вида “? ” вычитается. В результате ограничения принимают вид уравнений:

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



3.1 Модельный пример решения задачи о стоимости информационной сети с заданными пропускными способностями ветвей и узлов

Имеется информационная сеть, которая задана с помощью взвешенного, ориентированного графа G = (X, Y), где X = { } -совокупность узлов сети (вершин графа) и Y = { } - множество ветвей (рёбер графа), соединяющих узлы сети, соответствующих всем линиям или каналам связи между этими узлами. Время работы данной сети рассматривается на промежутке [0,T].

Пусть - пропускные способности ветвей сети, а - пропускные способности (память) узлов данной сети соответственно.

Также для данной сети задана функция максимального потока

и заданы значение линейных коэффициентов и :

Тогда необходимо найти такие оптимальные значения

и ,

при которых линейный функционал

достигает минимума при следующих ограничениях:

Далее выпишем еще одно ограничение:

Заметим, что неравенство и неравенство можно заменить одним

}=.

Теперь выпишем ограничения на объёмы накопителей памяти в сети.

Допустим, что в начальный момент времени = 0 все векторы :

.

И при каждом t входящий поток в источник сети равен константе , то есть в каждый момент времени сервер получает одинаковый объём информации.

В результате получаем такие ограничения на объёмы накопителей памяти:

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

при ограничениях:

Вычислим значение данного линейного функционала F с помощью вычислительных средств ЭВМ, указав численные значения для Т и . Например,

Т = 10 и .

Получаем такой результат:

F = 4267,

Размещено на Allbest.ru

...