15. Определение потока сети. Величина потока. Определение максимально возможной величины потока в сети. Пример определения.

Сетью называется связный орграф без петель.

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

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

Результат расчета пропускных способностей всех разрезов сети, показанной на рис. 46, приведен в таблице 2.

Таблица 2
Разрез	Множество узлов Х*	Множество дуг разреза А*	Пропускная способность разреза С(А*)
А*1	0	(0,1); (0,2)	3+2=5
А*2	0, 1	(0,2); (1,2); (1,3)	2+3+1=6
А*3	0, 2	(0,1); (2,3)	3+4=7
А*4	0, 1, 2	(1,3); (2,3)	1+4=5

Таким образом, максимально возможная величина потока в сети, приведенной на рис. 46, определяется двумя минимальными разрезами – А*₁ и А*₄ – и равна М_max(f)=5. Это подтверждает выдвинутое выше предположение о возможности увеличения на единицу значений дуговых потоков на пути (0, 1, 2, 3).

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

• задачи управления ресурсами;

• задачи транспортного типа;

• задачи календарного планирования;

• задачи массового обслуживания,

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

Задачи управления ресурсами. К основным задачам этого класса относятся задачи: а) организации поставок и управления запасами ресурсов; б) распределения ресурсов.

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

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

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

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

a_ij – количество i-того ресурса, необходимого для выполнения единичного объема j-того вида работ: a_ij0; i=1, 2,…, m; j=1, 2,…, n;

b_i – доступный объем (запас) i-того ресурса: b_i>0;

c_j – цена выполнения единичного объема j-того вида работ: с_j>0.

Пусть x_j – планируемый объем выполнения j-того вида работ. Тогда допустимым является такое планирование объемов выполняемых работ x=(x₁, x₂, …, x_n), при котором суммарные затраты каждого i-того ресурса не превосходят его доступного объема (запаса):

(6)

Кроме того, имеем следующее естественное ограничение:

xj0; i=1,…,n

(7)

Стоимость общего объема запланированных работ x выражается величиной:

(8)

Задача планирования (распределения) ресурсов ставится следующим образом: среди всех векторов x, удовлетворяющих ограничениям (6) и (7) найти такой, при котором величина (8) принимает наибольшее значение:

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

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

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

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

Пусть для осуществления работ в n пунктах необходим ресурс, поставляемый из m источников. Необходимо организовать доставку ресурса из источников в пункты потребления так, чтобы при полном удовлетворении потребностей минимизировать суммарные потери транспортировки, причем известно:

a_i – доступный объем (запас) ресурса в i-том источнике: a_i>0;

b_j – потребность в ресурсе на j-том пункте: b_j>0;

c_ij – цена доставки единичного объема ресурса из i-го источника в j-й пункт выполнения работ: с_ij>0; i=1, 2,…, m; j=1, 2,…, n.

При ограничивающем условии – предположении о том, что суммарные запасы равны суммарным потребностям ресурса – транспортная задача сводится к задаче линейного программирования. При условии:

(9)

постановка задачи имеет следующий вид:

при условиях: = ,

(10)

где x_ij – количество ресурса, доставляемого из i-го источника в j-й пункт. Условие (9) является необходимым и достаточным для существования по крайней мере одной матрицы перевозок [x_ij], удовлетворяющей ограничениям задачи (10).

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

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

1. потребности абонентов сети в получении объемов информации (ресурса);

2. возможности сети в предоставлении каналов той или иной мощности между различными узлами связи;

3. критерии эффективности распределения каналов относительно их пропускной способности.

18