ВведениеДля решения транспортных задач в классической постановке существует довольно много эффективных алгоритмов и программ [1−5]. Однако зачастую при решении практических проблем недостаточно один раз решить транспортную задачу. Часто транспортная задача используется как элемент итеративного процесса, например, при решении задач размещения с дополнительными ограничениями нетранспортного типа или задач с нелинейными ценами [6−11]. В таких случаях полученный в результате решения оптимальный план является лишь этапом работы [12–15, 31]. В зависимости от результатов изменяются исходные задачи, и транспортная задача решается заново. Однако такой способ нельзя признать экономным с точки зрения вычислительной эффективности [16−20]. Для этого необходимо при внесении изменений в исходные данные корректировать полученный ранее оптимальный план при помощи специальных процедур. В настоящей работе приводятся алгоритмы формирования связей поставщиков и потребителей.Типовая исходная задача Пусть задана ориентированная сеть G=N,U,β, где N  – множество вершин сети, U  – множество ориентированных дуг, β  – величина потоков на дугах. Предположим, что β(u)>0  для всех uϵU .Для каждой вершины i  определим два множества дуг: A(i)  – множество входящих дуг, Bi  – множество входящих.Величину Qi=A(i)βu-B(i)βu  будем называть мощностью вершины. Если Qi>0 , то вершина является поставщиком, если Qi<0  – потребителем, а если Qi=0  – промежуточной вершиной.Целью мы называем последовательность ориентированных дуг заданным на ней положительным потоком:С=i0,i1, i1,i2,…,(iK-1,iK)ε .Началом цепи всегда будет поставщик, а концом – потребитель. Цепи служат для описания связей между поставщиками и потребителями. Задание цепи С  означает, что поставщик i0  отправляет потребителю iK  ε  единиц продукта через пункты i1,i2,…,iK-1 . Через n(C)  будем обозначать начальную вершину цепи, через K(C)  – конечную, а через ε(С)  – поток цепи.В данной задаче требуется найти такое множество цепей С1,…,Cl,  чтобы выполнялись следующие условия.Для любой цепиQnCj>0, QKCj<0.                                                                                (1)Для каждой вершины при Qi>0 СjnСj=iεСj=Q(i)                                                                                           (2)при Qi<0 СjnСj=iεСj=-Q(i). Для каждой дугиСjuϵСjεСj≤βu.                                                                                               (3)Первое условие означает, что цепи начинаются в поставщиках и заканчиваются в потребителях. Второе условие означает, что сумма потоков по цепям, начинающимся в поставщике, равна мощности этого поставщика, а сумма потоков по цепям, заканчивающимся в потребителе, равна абсолютной величине его мощности. Из третьего условия следует, что сумма потоков по цепям, проходящим через данную дугу, не превосходит потока по этой дуге. Легко заметить, что эти три условия формализуют интуитивные представления о правилах привязки поставщиков к потребителям [21−25]. Формализованное представление алгоритмаПредставим алгоритм построения искомого множества цепей сначала в случае ациклической сети – сети без ориентированных циклов. На самом деле, в результате решения транспортной задачи в абсолютном большинстве случаев будет получена именно ациклическая сеть. Действительно, для транспортной задачи без ограничений пропускной способности решение будет деревом, а для транспортной задачи с ограничениями ориентированный цикл в оптимальном плане может появиться только тогда, когда в исходной сети существует ориентированный цикл, состоящий из дуг нулевой стоимости [26, 27].Прежде чем перейти к описанию алгоритма, необходимо сформулировать определение и доказать одно свойство ациклических сетей.Вершина, в которую не входит ни одна дуга, называется исходной, а вершина, из которой не выходит ни одной дуги, называется тупиковой [ 28−30].Лемма 1. В ациклической сети найдется одна исходная вершина.Доказательство. Пусть это не так и в любую вершину входит хотя бы одна дуга. Рассмотрим произвольную вершину сети i0 . Возьмем (i0,i1) , входящую в вершину сети i0 . Далее возьмем дугу i1,i2  и т.д. Прерваться этот процесс не может, по предположению. Рассмотрим полученную последовательность вершин i0,i1,i2,…,iK,…  . Среди них найдутся одинаковые: il=im . Но тогда дуги (im,im-1),  (im-1,im-2),…,(il+1,il)  образуют ориентированный цикл, что противоречит ацикличности сети.Коротко опишем структуру информации, необходимую для работы алгоритма. В каждой вершине нам нужен список выходящих из нее дуг. Обозначим этот список через A(i) . Кроме того, для каждой вершины будем помнить degi  – количество входящих в нее дуг.Алгоритм привязки выглядит следующим образом.Выбираем вершину i0  такую, что deg(i0)=0.  Если такой вершины нет, то заканчиваем работу. Иначе переходим к шагу 2.Если вершина i0  тупиковая, т.е. А(i0)  пуст, то удаляем i0  из сети и переходим к шагу 1. Если А(i0)  не пуст, то объявляем i0  последней вершиной построенной цепи. Полагаем ε=∞ . Переходим к шагу 3.Пусть iK  последняя вершина цепи. Если А(iK)  пуст, заканчиваем построение цепи и переходим к шагу 4. Если А(iK)  не пуст, то обозначим через iK+1 конечную вершину 1-й дуги списка А(iK):(iK, iK+1) . Полагаем, ε=minε,βiK, iK+1.  Объявляем iK+1 последней вершиной цепи и повторяем шаг 3.Добавляем цепь С= (i0,i1, i1,i2,…,(iK-1,iK)ε)  в список построенных цепей. На всех дугах цепи производим пересчет потоков: βil,il+1=βil,il+1-ε. Если после пересчет βil,il+1=0 , то выбрасываем дугу il,il+1  из списка A(il)  и уменьшаем deg(il+1)  на единицу. Переходим к шагу 2.Из леммы 1 следует, что алгоритм закончит работу, когда все вершины будут удалены из сети. Рассмотрим теперь сеть, содержащую циклы. В этом случае описанный алгоритм не применим. Для того, чтобы получить возможность им пользоваться, необходимо предварительно «разорвать» в сети все ориентированные циклы, что и делает приведенный ниже алгоритм удаления циклов. Информация, используемая этим алгоритмом, такая же, как и у предыдущего.Алгоритм удаления циклов выглядит следующим образом.Берем произвольную непросмотренную вершину сети i0 . Если все вершины просмотрены, то заканчиваем работу. Объявляем i0  последней вершиной построенной последовательности вершин.Пусть iK  последняя вершина построенной последовательности. Пусть A(iK)  пуст. Объявляем iK просмотренной.Если K≠0 , то объявляем iK-1  последней вершиной последовательности; дугу (iK-1,iK)  удаляем из списка A(iK-1)  и повторяем шаг 2.Если К=0 ,  то переходим к шагу 1.Пусть A(iK)  не пуст. Обозначим через iK+1  конечную вершину 1-й дуги списка А(iK):(iK, iK+1) .Если вершина iK+1  ранее не принадлежала построенной последовательности, то объявляем iK+1  последней вершиной последовательности и повторяем шаг 2.Если iK+1=il,   l≤K , то построен ориентированный цикл. Переходим к шагу 3.Вычисляем ε=minβ(ij, ij+1)  – минимум величин потоков на цикле. На всех дугах цикла производим пересчет потоков:βij, ij+1=βij, ij+1-ε. Если на дуге (ij, ij+1)  поток стал равен нулю, то удаляем ее из списка A(ij)  и исключаем эту дугу из сети. Объявляем il  последней вершиной построенной последовательности и переходим к шагу 2.В следующем пункте будет доказано, что после окончания работы этого алгоритма получается ациклическая сеть и для привязки поставщиков и потребителей можно пользоваться ранее описанным алгоритмом.Прежде всего заметим, что при построении в первом алгоритме цепи, благодаря ацикличности сети, мы всегда достигнем тупиковой вершины за конечное число шагов. Ясно, что отсюда легко следут конечность описанного алгоритма. Докажем теперь, что множество построенных цепей удовлетворяет требованиям, сформулированным в п. 2. Лемма 2. В описанном алгоритме началом построенной цепи может быть только поставщик, а концом – только потребитель.Доказательство. Пусть Q+i=Aiβu, а Q-i=Biβu.  `Если i0  – исходная вершина цепи, то deg⁡(i0)=0  и, следовательно, множество входящих в i0  дуг B(i0)  пуст. Отсюда следует, что Q+i0>0, Q-i0=0  и Q(i0)>0 , а также Q-iK>0, Q+iK=0  и Q(iK)<0 , т.е. мощность исходной вершины положительна, а конечной – отрицательна. Заметим, что после пересчета потоков на цепи мощности внутренних вершин не меняеются, мощность i0  уменьшается на ε , а мощность iK увеличивается на ε . Но Q(i0)= Q+i0  остается неотрицательной, а Q(iK)= -Q-iK  yе положительной, так как ε≤min(β(i0,i1),β(iK,iK-1)) , а β(i0,i1)≤ Q+i0 . Следовательно, знаки Q после пересчета сохраняются. Так как началом цепи всегда является вершина с положительной, а концом – вершина с отрицательной мощностью, то из того, что мощность сохраняет знак при преобразовании потоков, непосредственно следует утверждение леммы.Лемма 3. Сумма потоков по всем цепям, выходящим из поставщика, равна мощности этого поставщика.Доказательство. Пусть веришна i0  – поставщик. Из леммы 2 следует, что i0  не может быть конечной вершиной цепи. Значит прежде чем i0  станет начальной вершиной, она может быть только промежуточной. Следовательно, в момент, когда i0  стала начальной вершиной, мощность i0  по сравнению с началом работы алгоритма не изменилась и равна сейчас Q+i0 . Пусть Cl,Cl+1,…,Cm  – цепи, началом которых является i0.  Если i0  стала начальной вершиной цепи, то другая вершина может стать началом цепи только когда A(i0)  будет исчерпан. Однако, если A(i0)  исчерпан, то Q+i0 =0. Следовательно, d=lmε(Cd)=Q(i0) , что и требовалось доказать.Лемма 4. Сумма потоков по всем цепям, заканчивающимся в потребителе, равна по абсолютной величине мощности.Доказательство. Во-первых, сумма потоков на заканчивающихся в потребителе цепях не может по абсолютной величине превышать мощность потребителя, так как, по лемме 2, потребитель может быть только концом цепи, а знаки мощности не меняются. Из определения следует, что сумма мощностей всех вершин сети равна нулю, значит Q(i)>0Qi=Q(i)<0Q(i). Но, по лемме 3 Q(i)>0Qi=ε(Cj).  Так как сумма потоков на цепях, заканчивающихся в потребителе, не превосходит по абсолютной величине его мощности, то из равенства Q(i)<0Q(i)=ε(Cj) следует, что для каждого потребителя Q(i)=KCj=iε(Cj). Лемма доказана.Приведем теперь полное обоснование первого алгоритма. Из лемм 2-4 непосредственно следует справедливость условий (1) и (2) для построенного множетсва цепей. Условие (3) выполняется потому, что каждый раз, назначая поток по цепи, мы соотвественно уменьшаем потоки на дугах. Таким образом, для построенного множества цепей выполняются все три условия привязки.Далее необходимо доказать, что после выполнения второго алгоритма будет получена ациклическая сеть. Докажем, что через пространственную вершину не может проходить ориентированный цикл. У просмотренной вершины список А пуст, поэтому достаточно доказать, что через дугу, выбрасываемую из списка А, цикл не проходит. Докажем это утверждение индукцией по порядку выбрасывания дуг. Дуга выбрасывается из списка, если поток на ней стал равен нулю или если она входит в вершину с пустым списком А. В первом случае очевидно, что никакой цикл по этой дуге пройти не может, так как дуга с нулевым потоком исключается из сети. Во втором случае, если это первая выбрасываемая дуга, то она входит в вершину, из которой вообще нет выходящих дуг, т.е. никакой цикл через эту дугу не пройдет. Если же это не первая выбрасываемая дуга, то она входит в вершину с пустым списком А, но через дуги, ранее выброшенные из списков, циклы не проходят по предположению индукции. Следовательно, циклы не проходят и через нашу дугу. Таким образом, доказано, что через просмотренную вершину циклы не проходят. Так как в конце работы алгоритма все вершины просмотрены, то результатом работы является ациклическая сеть.Также необходимо остановиться на оценке трудоемкости алгоритмов. Из описания первого алгоритма следует, что при построении одной цепи мы работаем только с принадлежащими этой цепи дугами. На обработку дуги требуется конечное число операций. Следовательно, общую трудоемкость алгоритма можно оценить величиной порядка On+O(C1) , где n – число вершин сети, а C1  – сумма длин всех построенных цепей. Слагаемое On  появляется из-за того, что мы тратим некоторое количество действий на обработку первой вершины цепи; при этом цепь может и не быть построена. Трудоемкость второго алгоритма оценивается величиной порядка Oр+O(C2) , где р – число дуг сети, а C2  – сумма длин всех уничтожаемых циклов. Слагаемое Oр  появляется потому, что мы расходуем некоторое количество действий на удаление дуг из списков А, а слагаемое O(C2)  – потому что на каждой дуге построенного цикла (и только на них) мы выполняем некоторые действия. Из самого вида этих оценок ясно, что они близки к оптимальным. Отметим, что после пересчета потоков на цепи в первом алгоритме и на цикле во втором, хотя бы на одной дуге поток становится равным нулю. Таким образом, число цепей, получаемых в первом алгоритме, и циклов, уничтожаемых во втором, можно оценить сверху величиной р. Отсюда следует, что С1≤n,p  и С2≤n,p  и оба алгоритма имеют полиноминальную оценку трудоемкости относительно числа вершин и дуг сети.Приведем теперь более точную оценку количества цепей, получившихся при работе первого алгоритма.Пусть в сети n  вершин, p  дуг, S  поставщиков и t  потребителей.Теорема. Число цепей не превосходит p-n+s+t.  Доказательство. Заметим, что после окончания работы алгоритма потоки на всех дугах сети равны нулю. Каждой внутренней вершине i  сопоставим цепь Сj(i)  после пересчета потоков, на которой Q+i  становится равной нулю. Но, так как вершина Q-i  становится равной нулю. Но, так как вершина i  внутренняя, то Qi=0 , а значит и Q-i=0. Следовательно, после пересчета потоков цепи Сj(i)  для любой внутренней вершины i  поток станет равен нулю по крайней мере на двух дугах. После пересчета потоков на других цепях поток становится равным нулю, хотя бы одной дуге. Следовательно, общее количество цепей можно оценить величиной p-nBH,  где nBH  – число внутренних вершин. Теперь из равенства nBH=n-s-t  следует справедливость утверждения теоремы.Следствие. Если исходная сеть является деревом, то число цепей не превосходит s+t-1.  4. ЗаключениеПри использовании приведенных алгоритмов для привязки поставщиков к потребителям на рынке БРИКС алгоритмов после решения сетевых транспортных задач следует преобразовать полученный оптимальный план к виду, необходимому для работы алгоритмов привязки. Здесь мы отходим от принятых способов хранения оптимального плана в целях единообразия обработки решений транспортных задач с ограничениями пропускной способности и без ограничений. Отметим, что алгоритм удаления циклов следует применять только к решению задачи с ограничениями и только в том случае, когда в исходной сети есть ориентированные циклы из дуг нулевой стоимости.Отметим, что для задачи без ограничений достаточно запомнить лишь начало цепи, конец цепи и поток по ней, так как маршрут перевозки однозначно восстанавливается по этим данным и по дереву оптимального плана, тогда как для задачи с ограничениями необходимо запоминать весь маршрут перевозки; здесь может быть, например, несколько различных цепей с одинаковыми началами и концами.Описанный алгоритм привязки осуществляет закрепление поставщиков за потребителями на рынке БРИКС без учета каких-либо требований к этому закреплению. В некоторых случаях такое закрепление не является удовлетворительным.