О децентрализованной транспортной задаче

Введение Классическая транспортная задача заключается в максимизации функции n m So = J2 СИ(1) i=1 j=1 при ограничениях mn ^xij = (ii,^2,xij = bj, xij ^ 0; i = 1,2, …,n; j = 1,2, …,m. (2) Она моделирует централизованное распределение m видов производимой продукции в количествах bj, j = 1, 2,… , m, среди n потребителей с объемами спроса (ц, i = 1, 2,…, n. Здесь и далее предполагается, что nm ai = S bj. Через Cij ^ 0 обозначается прибыль, получаемая про- i=i j=i изводителем при продаже одной единицы j-го вида продукции i-му потребителю. Классическая транспортная задача является полиномиально разрешимой . *) Исследование выполнено при финансовой поддержке Российского фонда фундаментальных исследований (проекты 08-01-00516 и 08-01-00370). © 2008 , В статье рассматривается децентрализованная транспортная задача, в которой предполагается, что каждый потребитель действует индивидуально, максимизируя свою собственною выгоду. Производитель может контролировать лишь очередность обслуживания (доступа) потребителей. В настоящей работе предполагается, что потребители имеют ту же матрицу доходов (cj), что и производитель. Ясно, что выгода каждого потребителя зависит от очередности, в которой он будет допущен к производителю. При заданной очередности обслуживания п, которую можно интерпретировать как перестановку строк матрицы (Cij), доходы потребителей легко находятся из последовательного решения следующих задач Si(n) = Шах cn(i)jxn(i)jxn(i)j = aп(i), 0 Xn(i)j bj X*n(i)j \ (3) где через X*j обозначен оптимальный выбор i-го потребителя. Тогда доход производителя равен суммарному доходу потребителей, т. е. nm i=i sd (п) = *52 si(n) = cn(i)j Xi(i)j i=i j=i (4) Требуется найти SD = max Sd (п). Поскольку каждое допустимое решение задачи (3)-(4) является допустимым решением задачи (1)-(2), имеем SD ^ SO, где через SO обозначен оптимум классической транспортной задачи (1)-(2). В следующем разделе показано, что децентрализованная транспортная задача в отличие от классической является NP-трудной даже в том случае, когда ( i = 2, i = 1, 2, . . . , n, и bj = 1, j = 1, 2, . . . , m. В разд. 3 приводится приближенный алгоритм решения задачи (3)-(4) в случае, когда ai = k, i = 1, 2,…, n, и bj = 1, j = 1, 2,… , m. Алгоритм имеет трудоемкость O(kn3) и гарантирует получение решения, не более чем в k раз худшего оптимального. Построены два класса матриц. Для матриц одного класса выполняется соотношение SD = SO, но алгоритм находит решение, в k раз худшее оптимального. Для матриц другого класса алгоритм находит оптимальное решение, но имеет место соотношение SD ~ SO/k. Тем самым показано, что константа в оценке точности алгоритма неулучшаема, а рассматриваемая дисциплина обслуживания потребителей может оказаться в наихудшем случае во много раз невыгоднее централизованной системы закупок (поставок). 1. Доказательство NP-полноты В этом разделе доказывается NP-полнота следующей задачи распознавания. Задача 1. Даны матрица C размера n х 2n и целое число K. Обозначим через Cii и C\j два наибольших элемента первой строки и назовем весом матрицы C величину f (C) = Cii + Cij + /(С), где матрица C получается из С удалением первой строки, а также i-го и j-го столбцов. Существует ли такая перестановка строк матрицы С, что получившаяся матрица имеет вес не меньше K? Нетрудно заметить, что задача 1 эквивалентна частному случаю задачи (3)-(4) при ai = 2, i = 1,2, …,n, и bj = 1, j = 1,2,…, 2n. Заметим, что в случае, когда ( i = bj = 1, i, j = 1, 2, . . . , n, задача (3)-(4) эквивалентна задаче о назначениях. Это следует из того факта, что в оптимальном решении задачи о назначениях всегда найдется элемент, являющийся максимальным в своей строке. Отметим, что задача о назначениях разрешима за полиномиальное время . Принадлежность задачи 1 классу NP очевидна. Для доказательства ее NP-полноты воспользуемся следующей известной NP-полной задачей Выполнимость . Задача Выполнимость. Дано q дизъюнкций над множеством из p переменных. Можно ли назначить этим переменным такие значения истинности, чтобы каждая дизъюнкция содержала по крайней мере один истинный литерал (под литералом понимается переменная или ее отрицание)? Нам потребуется сбалансированная версия этой задачи, где каждый литерал входит ровно в t дизъюнкций. Покажем, что при таком дополнительном условии задача Выполнимость остается NP-полной. Утверждение 1. Сбалансированная версия задачи Выполнимость NP-полна. Доказательство. Рассмотрим произвольный пример задачи Выполнимость и обозначим через t максимальное число вхождений литерала в дизъюнкции. Пусть X — произвольный литерал, входящий в s t дизъюнкций (если таких литералов нет, то пример уже сбалансирован). Добавим новую переменную у, а также t — s копий дизъюнкции хУ у У у и s копий дизъюнкции у У у. Ясно, что полученный набор дизъюнкций эквивалентен исходному, но литералы х,у и у встречаются ровно по t раз. Проведя эту процедуру для каждого литерала, встречающегося менее чем t раз, получим сбалансированный пример задачи Выполнимость. Утверждение 1 доказано. Теперь можно доказать основной результат данного раздела. Теорема 1. Задача 1 NP-полна. Доказательство. Построим сведение сбалансированной задачи Выполнимость к задаче 1. Рассмотрим некоторый сбалансированный набор из q дизъюнкций над множеством из p переменных, где каждый литерал встречается ровно t раз. Положим b — 4tp + 2 и a — 2tpb + b + 2. Каждой переменной Xi поставим в соответствие 2t строк (по t строк для каждого из литералов Xi и Xi) и 5? столбцов. Столбец матрицы будем называть большим, средним или малым, если максимальный элемент этого столбца равен a, b или 1 соответственно. Каждой переменной Xi соответствуют 2t больших, t средних и 2t малых столбцов (по t из которых соответствуют литералам Xi и ~x~i). Строки и столбцы, соответствующие литералам Xi HXi, имеют соответственно вид (элементы всех остальных столбцов в этих строках будут равны 0): {Ax.,B,It,0t) и (Af.,B,0t,It), где (a a 2a a 2a 2 aa 2 aa 2 a 2« \ 2 } a 2, B -Ib 00 … b …0 0 \a 2a 2a 2a 2aa\0b ia 2 a 2a a 2a aa 2 aa 2 a 2« \ 2 ) a 2, It -I1 00 … 1 …0 \ 0 \aa 2a 2a 2a 2a\0.1.. 0t — квадратная нулевая матрица порядка t. Для каждой дизъюнкции назначим по одному малому столбцу, соответствующему каждому входящему в эту дизъюнкцию литералу. Столбцы назначаются произвольным образом, но так, чтобы разным дизъюнкциям были назначены разные столбцы. Каждой дизъюнкции поставим в соответствие одну строку. Ее элементы во всех больших и средних столбцах, соответствующих переменным, положим равными a/2 и b/2 соответственно. Элементы строки в назначенных для данной дизъюнкции малых столбцах положим равными 1. Добавим также для каждой дизъюнкции один большой столбец с элементом a в соответствующей строке. Все остальные элементы строк, соответствующих дизъюнкциям, положим равными 0. В результате получим матрицу с 2tp + q строками, 2tp + q большими столбцами (из которых 2tp соответствуют переменным и q дизъюнкциям), tp средними столбцами и 2tp малыми столбцами. Добавим в случае необходимости полностью нулевые строки и/или столбцы, чтобы число столбцов матрицы стало ровно вдвое больше числа строк. Положим K — (2tp + q)a + tpb + tp + q. Покажем, что набор дизъюнкций выполним тогда и только тогда, когда приведенная выше матрица при некоторой перестановке строк имеет вес не меньше K. Предположим, что набор дизъюнкций выполним. Тогда переставим строки матрицы в таком порядке: сначала поставим строки, соответствующие истинным литералам, затем — ложным литералам, затем — дизъюнкциям, и наконец, полностью нулевые строки, если таковые имеются. Тогда в каждой строке, соответствующей истинному литералу, дважды выбирается элемент a, после чего все большие столбцы, соответствующие переменным, будут удалены. Поэтому во всех строках, соответствующих ложным литералам, выбираются элементы b и 1, что приводит к удалению всех средних столбцов, а также всех малых столбцов, соответствующих ложным литералам. Заметим, что ни один малый столбец, соответствующий истинному литералу, удален не был. Поскольку каждая дизъюнкция содержит хотя бы один истинный литерал, во всех строках, соответствующих дизъюнкциям, можно выбрать элементы a и 1. Таким образом, вес матрицы равен 2atp + tp(b + 1) + q(a + 1) — K. Допустим теперь, что при некоторой перестановке строк получается матрица веса f * ^ K. Сначала покажем, что строки, соответствующие дизъюнкциям, идут после строк, соответствующих переменным. Оценим величину f* сверху как сумму максимальных элементов всех столбцов. По выбору a и b имеем f * ^ (2tp + q)a + tpb + 2tp (2tp + q)a + tpb + b/2 (2tp + q)a + a/2. Следовательно, для выполнения неравенства f * ^ K необходимо, чтобы в каждом большом столбце был выбран элемент a, а в каждом среднем столбце — элемент b. В частности, отсюда следует, что выбор максимальных элементов в строке, соответствующей дизъюнкции, дол жен производиться после того, как будут удалены все большие и средние столбцы, соответствующие переменным. Рассмотрим произвольную переменную x. Ей соответствуют 2t строк. В первых t строках выбираются два элемента из больших столбцов (в результате все большие столбцы, соответствующие x, удаляются). В следующих t строках выбираются по одному элементу из среднего и малого столбцов. Таким образом, все большие и средние столбцы, соответствующие x, будут удалены лишь после выбора двух максимальных элементов в последней из строк, соответствующих x. Следовательно, ни одна строка, соответствующая дизъюнкции, не может встречаться раньше строки, соответствующей переменной. Поскольку в каждом большом столбце, соответствующем переменной x, должен быть выбран элемент a, то либо все строки, соответствующие литералу x, должны идти перед строками, соответствующими литералу х, либо наоборот, все строки, соответствующие х, должны идти перед строками, соответствующими x. Положим значение переменной x равным «истина», если имеет место первая альтернатива, и «ложь» в противном случае. Заметим, что все малые столбцы, соответствующие ложным литералам, были удалены. Сумма элементов, выбранных в строках, соответствующих переменным, равна 2tpa + tpb + tp. Ясно, что в строке, соответствующей дизъюнкции, выбирается элемент a из соответствующего ей большого столбца и элемент 1 из одного из назначенных ей малых столбцов, если хотя бы один из этих столбцов не был удален. Таким образом, сумма элементов, выбранных в этих строках, не превосходит q(a + 1). Поскольку f * ^ K — 2tpa + tpb + tp + q(a + 1), в каждой строке, соответствующей дизъюнкции, должен быть элемент 1. А это значит, что каждая дизъюнкция содержит истинный литерал. Теорема 1 доказана. 2. Приближенный алгоритм Рассмотрим следующий приближенный алгоритм решения задачи (3)-(4) в случае, когда ai — k, i — 1,2,k ^ 2, и bj — 1, j — 1,2,…,m. Описание алгоритма Шаг 0. Решается классическая транспортная задача (1)-(2) с матрицей (cij) при ai — k, i — 1, 2,…, n, и bj — 1, j — 1, 2,… , m. Пусть Ui — множество элементов матрицы, соответствующих ненулевым значениям переменных в оптимальном решении задачи (1)-(2). Тогда Ui содержит по k элементов каждой строки и по одному элементу каждого столбца матрицы (cij). Шаг i (для i = 1, 2,… ,n). Обозначим через Xi максимальный элемент в Ui и положим равным номеру строки, содержащей Xi. Пусть Vi = Xi ^ y2 ^ … ^ yj — элементы строки лежащие в Ui (очевидно, j * k). Выберем k максимальных элементов в строкеОбозначим их через z\ ^ z2 ^ … ^ zk. Ясно, что zii ^ yi Для всех I = 1, 2,… , j. Удалим из Ui элементы y\, V2, …,Vj, а также элементы тех столбцов, которые содержат zi, z2,…, zk. Обозначим полученное множество через Ui+i. Если Ui+i = 0, то переходим на шаг i + 1. В противном случае, значения n(i + 1), n(i + 2),…, назначаются произвольно из числа тех, которые не были выбраны ранее, и алгоритм заканчивает свою работу. Оценку качества работы алгоритма дает следующая Теорема 2. Алгоритм за время O(kn3) находит приближенное решение децентрализованной транспортной задачи с матрицей (cij) при Cij ^ 0, ец = k и bj = 1, i = 1, 2,…, n, j = 1, 2,…, m, отличающееся от оптимального не более чем в k раз. Доказательство. Трудоемкость алгоритма определяется решением классической транспортной задачи на шаге 0, поскольку остальные шаги алгоритма выполняются за линейное время. Шаг 0 требует O(kn3) элементарных операций . Оценим погрешность алгоритма. Через Si обозначим сумму удаленных на i-м шаге элементов из Ui. Достаточно показать, что для каждого ( k \ i выполняется соотношение Si * k I z\ ]. В этом случае Vi=i / n k/ n \ Sd (n) = Y,Y, zi [Y, Si) /k = ( ? u)/k = SC/k SD/k. i=l 1=1\i=l /«ЂUi Чтобы оценить Si, рассмотрим два случая. 1.Если Xi € {zl, z2,…, zk}, то из Ui помимо y1, y2,…, Vj удаляется не более чем k — 1 элементов, каждый из которых не превосходит Xi. Следовательно, jk/ k \ Si * (k — 1)Xi + ? vi * (k — 1)z1 + ? zi * k ГГ zH . i=ii=i\i=i J 2.Если Xi € {zi, z2, …,zk}, то zii ^ Xi для каждого l = 1, 2, …,k. Поскольку всего из Ui удалено не более чем 2k элементов, имеем Si * 2kXi * 2( V zA * k так как k ^ 2. Теорема 2 доказана. Покажем неулучшаемость доказанной в теореме 2 константы. В первом примере показано, что существуют матрицы, для которых оптимальные решения классической и децентрализованной транспортных задач отличаются почти в k раз. Во втором примере показывается, что решение, найденное описанным выше алгоритмом, может быть почти в k раз хуже оптимального. Чтобы избежать громоздкости, оба примера приведены для случая k = 2, но их нетрудно обобщить и для произвольного k. Пример 1. Рассмотрим матрицу (cij) с четным числом строк n: 2 е2 2е 2 а 210 201 00 0 0 .1.. Нетрудно проверить, что при а 2 имеем SC = п(а + 1), SD = (а + 2)n/2 + n/2. Ясно, что при достаточно большом значении а, выполняется соотношение SC/SD ~ 2. Пример 2. Пусть матрица C = (Ca, In) имеет четное число строк n, где /а + n 0 0 0 0 0 0 а + n — 2 0 0 0 0 0 0 а+2 0 0 0 0 а + n 0 0 0 2 0 10 а + n — 3 0 0 0 2 0 0 а+1 In — квадратная единичная матрица порядка n. Оптимальным решением децентрализованной транспортной задачи с указанной матрицей является перестановка ni = n(n — 1)… 1, так что n2 2 S*D = ЗЪ(тп) = J^((a + г) + 1) = па + у + 3^. i=i Алгоритм же находит перестановку П2 = 12 … n, для которой имеет место соотношение 2 2 4 5d(tt2) = j](a + 2i + 2) + ^ = + ^- + 2n. i=i Таким образом, Sd(ti»i)/Sd(П2) ~ 2 при достаточно большом значении а, т. е. решение, найденное алгоритмом, отличается от оптимального почти в два раза. В заключение отметим, что приведенный в статье алгоритм можно легко модифицировать на случай произвольных Тогда алгоритм найдет решение, которое не более чем в k раз хуже оптимального, где k = max^ | i = 1, 2,… ,n}. В случае же произвольных bj необходимо сначала для каждого j скопировать j-й столбец bj раз. Получится эквивалентная задача с единичными требованиями потребителей, однако для нее приведенный выше алгоритм будет псевдополиномиальным.