24. Потоки в сетях и принцип их сохранения. Теорема Форда-Фалкерсона.

В этой теории в качестве основы рассматриваются движения в сетях потоков любой природы от источника s к стоку t.

Потоком в сети S = (N,U) от входа sN к выходу tN называется неотрицательная функция , определённая на множестве дуг сети U, со следующими свойствами:

1.Величина потока по каждой дуге не должна превосходить её пропускной способности 0, (I,j)U.

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

, где -множество вершин, инцидентных дугам, направленных от вершины i; – множество вершин, инцидентных дугам, направленных к вершине i.

Из определения следует, что величина потока не исчезает и не накапливается в вершинах сети, и, следовательно, количество потока из входа s равно количеству потока, заходящего в вход t. Это значение называется величиной потока V.

Пусть в ориентированной сети S = (N,U) от источника к стоку протекает поток, величина которого равна V. Множество вершин S = (N,U) можно разбить на 2 непересекающихся подмножества Np и , которые соединяются между собой дугами, образующими множество Uр. Причём исток s принадлежит множеству узлов Np, а сток t принадлежит множеству узлов .

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

Барьер для потока, отделяющий множество узлов Np от множества узлов , называется разрезом и обозначается (Np, ).

Разрез представляет такое множество дуг Uр, исключение которых отделяет вход от выхода сети, и, следовательно, отделяет множество Np от множества сети S = (N,U) таким образом, что существование потока в таком случае невозможно, и тогда V=0. Причём начало дуги разреза принадлежит Np , а конец - .

Величина максимального потока от источника s к стоку t ограничена сверху величиной разреза С(Np, ) и, следовательно, V С(Np, ).

Минимальный размер сети называется разрез, имеющий минимальную величину.

Теорема Форда-Фалкерсона. Величина максимального потока V_max от входа s к выходу t равна величине минимального разреза, отделяющего вход и выход сети, т.е.

25. Построение максимального потока

Пусть задана сеть S = (N,U) с множеством вершин N и множеством дуг U. Дуга u U, соединяющая вершины i и j, i,j N, сети S, называется допустимой дугой, если она обладает одним из следующих свойств:

1.Направление дуги совпадает с направлением потока, и значение потока по этой дуге меньше её пропускной споособности: u=(i,j), (u) c(u).

2.Направление дуги противоположно направлению потока и величина потока отлична от нуля: u=(i,j), (u)

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

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

Пусть дана сеть, над каждой дугой которой указана её пропускная способность, а в скобках – поток по этой дуге.

Определение максимального потока основано на увеличении потока вдоль увеличивающей цепи на величину Δ. Алгоритм построения максимального потока включает следующую последовательность:

1.Задание начального значения потока. Удобно задавать нулевое значение.

2. Построение увеличивающей цепи от входа к выходу сети. Если такой цепи нет, то максимальный поток построен, его величина

в противном случае переходят к пункту 3 алгоритма.

3.Увеличение вдоль построенной цепи значения потока на максимально возможную величину Δ, при этом по каждой увеличивающей дуге поток увеличивается на Δ, а по каждой уменьшающей дуге уменьшается на ΔПосле этого следует возврат к пункту 2.

29. Принципиальные системы регулирования товарных запасов. Система с двумя фиксированными уровнями запасов и с фиксированной периодичностью заказа. Система с двумя фиксированными уровнями запасов без постоянной периодичности заказа.

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

1.Максимальный уровень запаса;

2.Нижний ур-нь запаса (точка запаса);

3.Длительность периода м\у заказами.

Первые 2 параметра постоянны, а третий – частично переменный. Рассматриваемая система сложнее предыдущей, однако, она позволяет исключить возможность нехватки товарного запаса. Недостатком системы является то, что пополнение запасов до максимального уровня не может производиться независимо от фактического расходования запасов.

Система с двумя фиксированными уровнями запасов без постоянной периодичности заказа, или (s, S) – стратегия управления запасами. Эту систему называют также (s, S) – системой, или системой «максимум-минимум». Рассмотрим (s, S)- стратегию управления запасами. Она устраняет недостаток предыдущей системы и является её модификацией. В этой системе – два регулирующих параметра:

1.Нижний (критич.) уровень запаса s;

2.Верхний уровень запаса S.

Если через x обозначить величину запасов до принятия решения о их пополнении, через p – величину пополнения, а через y=x+p – величину запасов после пополнения, то (s, S) – стратегия управления запасами задаётся функцией

Т.е. пополнения не происходит, если имеющийся уровень запасов больше критического уровня s. Если имеющийся уровень меньше или равен s, то принимается решение о пополнении запаса обязательно до верхнего уровня S, так что величина пополнения равна p=S-x.