Некоторые прикладные задачи

Задачи об источниках и потребителях

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

Пусть в некоторую единицу времени источники x_j (j=1,2,..,k) вырабатывают a_j единиц продукции, а потребность потребителя y_i (I=1,2,..,m) в этой продукции равна b_i. Пропускные способности линий считаются также отнесенными к выбранной единице времени. Таким образом, в задачах этого типа идет речь о неизменном и однородном по времени стационарном потоке.

С каждой такой задачей свяжем транспортную сеть D. Вершинами сети D служат источники, потребители, промежуточные пункты и еще две вспомогательные вершины: вход x₀ и выход z. Вершину x₀ свяжем дугами (x₀,x_j) (j=1,..,k) с источниками и припишем им пропускные способности a_j. Потребителей y_i свяжем с выходом z дугами (y_i,z) с пропускными способностями b_i. Остальные вершины соединим между собой дугами с соответствующими пропускными способностями в соответствии с реальным наличием связей между ними.

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

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

ЗАДАНИЕ 23. Решить задачу об источниках и потребителях, сведя ее к задаче построения максимального потока в транспортной сети и используя второй алгоритм – алгоритм меток для построения максимального потока.