Приложения задачи о максимальном потоке

Транспортная задача по критерию времени. Проблемы, возникающие при рациональной организации перевозок различных грузов, имеют исключительное народнохозяйственное значение. Математические задачи, к которым можно свести указанные проблемы, называют транспортными. Изучение методов решения транспортных задач важно ещё и потому, что большое количество других прикладных задач можно описать математической моделью, сходной с моделью задачи о перевозках, а следовательно, и решать по аналогичным алгоритмам. Качество плана транспортной задачи можно оценивать по различным критериям. Здесь мы ограничимся лишь критерием времени. Поставим задачу.

Пусть известны запасы груза a_i у поставщиков A_i, спрос b_j потребителей B_j и время t_ij доставки груза (независимо от объёма поставки) по маршруту A_i - B_j. Составить реализуемый за минимальное время план перевозок, при котором спрос удовлетворяется полностью.

Если суммарный запас груза совпадает с суммарным спросом, т. е. , то задачу называют закрытой, в противном случае — открытой.

Составим математическую модель задачи. Обозначим через x_ij количество груза, планируемое к перевозке из i -го пункта поставки в j -й пункт потребления, через t — время наиболее продолжительной перевозки. Оптимальным будем считать план , самая продолжительная перевозка которого минимизируется. Модель закрытой задачи имеет вид:

; (5.11)

; (5.12)

; (5.13)

. (5.14)

Как видно, целевая функция (5.11) является нелинейной. Уравнения (5.12) — ограничения по запасам — выражают требование, чтобы сумма всех поставок, идущих из i -го пункта, равнялась запасу а_i груза в нем; уравнения (5.13) — ограничения по потребностям — чтобы сумма всех поставок, направляемых в j -й пункт, равнялась его спросу b_j. Условие (5.14) означает, что обратные перевозки (возврат груза) не предполагаются.

Решение задачи (5.11)–(5.14) сведением её к задаче о максимальном потоке является одним из известных методов. Суть метода в следующем. Строится сеть с m + n + 2 вершинами, m из которых соответствуют поставщикам А_i, а n — потребителям B_j; две оставшиеся соответствуют истоку I и стоку S (рис. 5.15). Пропускные способности рёбер полагают равными:

, , , , .

У рёбер (А_i, B_j) проставляются времена t_ij доставки груза.

B ₁

b ₁

Рис. 5.15

Время доставки по рёбрам (I, A_i) и (B_j, S) считают равным нулю, т. е. . После построения сети по рассмотренной в § 5.5 методике отыскивается поток заданной мощности

,

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

Задача об оптимальном назначении.

Мы ограничимся рассмотрением упрощённого варианта задачи, сохраняющем, однако, все основные особенности общей задачи.

Пусть некоторая комплексная работа P связана с производством совокупности m более мелких работ P ₁, P ₂, …, P_m, которые могут выполнятся независимо одна от другой. В распоряжении планирующего органа находится n организаций-исполнителей И ₁, И ₂, …, И_n, каждая из которых может выполнять только некоторые определенные работы. При этом каждый исполнитель одновременно может выполнять только какую-либо одну работу и каждая работа одновременно может выполняться только одним исполнителем. Задача состоит в распределении работ между исполнителями таким образом, чтобы одновременно выполнялось возможно большее их число.

Составим математическую модель задачи в предположении, что задана матрица , элементы которой характеризуют возможности исполнителей, а именно: a_ij = 1, если
i -я работа может выполняться j -м исполнителем, и a_ij = 0
в противном случае.

Обозначим через x_ij переменные, характеризующие распределение работ между исполнителями,
и согласимся приписывать переменной x_ij значение, равное 1, если i -я работа поручена j -му исполнителю, и значение, равное 0, в противном случае. Итак,

x_ij = 1 или 0 .

Поскольку каждому исполнителю можно поручить не больше одной работы, должно выполняться условие

. (5.16)

По условию задачи каждую работу можно поручить только такому исполнителю, который способен её выполнить. Это можно выразить записью

. (5.17)

Поскольку каждая работа поручается не более как одному исполнителю, то должно выполняться условие

. (5.18)

Очевидно, что общее число m работ, одновременно выполняемых всеми n исполнителями, можно представить в виде

. (5.19)

Из математической модели (5.15)–(5.19) видно, что задача об оптимальных назначениях является задачей целочисленного линейного программирования, а потому может быть решена известными аналитическими методами [см. глава 4].

Здесь мы рассмотрим решение задачи сведением её к задаче о максимальном потоке. С этой целью строится сеть с m + n + 2 вершинами, m из которых соответствуют работам P_i, а n — исполнителям И_j, одна — истоку I и одна — стоку S (рис. 5.16). Исток I соединяют с вершинами P_i и считают пропускные способности рёбер (I, P_i) равными 1, а рёбер (P_i, I) равными 0. Вершины И_j соединяют со стоком S, и пропускные способности получившихся рёбер (И_j, S) считают равными 1, а рёбер (S, И_j) равными 0. Вершину P_i соединяют ребром с вершиной И_j тогда и только тогда, когда a_ij = 1, т. е. когда работа P_i может быть выполнена исполнителем И_j. При этом пропускную способность такого ребра (P_i, И_j) считают равной 1, а ребра (И_j, P_i) равной 0.

Рис. 5.16

Каждому распределению работ можно поставить в соответствие поток на сети. В самом деле, если работа P_i поручается исполнителю И_j, то по цепочке рёбер (I, P_i), (P_i, И_j), (И_j, S) пропускается поток единичной мощности. Можно показать и обратное: любому потоку с целочисленными компонентами соответствует некоторое распределение работ. При таком соответствии число распределённых работ равно мощности суммарного потока из истока I в сток S. Поэтому, чтобы решить задачу об оптимальных назначениях, достаточно найти в соответствующей сети максимальный поток с целочисленными потоками по рёбрам сети.

Дата добавления: 2015-07-26