В общем случае переменные задачи линейного программирования должны быть

Задача присвоения — это фундаментальная задача комбинаторной оптимизации. В самом общем виде проблема заключается в следующем:

Экземпляр задачи имеет несколько агентов и несколько задач. Любой агент может быть назначен для выполнения любой задачи. Неся некоторые затраты, которые могут варьироваться в зависимости от назначения агента-задачи. Необходимо выполнить как можно больше задач. Назначив не более одного агента для каждой задачи и не более одной задачи для каждого агента таким образом. Чтобы общая стоимость назначения была минимизирована.

В качестве альтернативы можно описать проблему с помощью теории графов:

Задача присваивания состоит в нахождении в взвешенном двудольном графесоответствия заданного размера. В котором сумма весов ребер минимальна.

Если число агентов и задач равно. То задача называется сбалансированным распределением. В противном случае это называется несбалансированным назначением.[1] Если общая стоимость назначения для всех задач равна сумме затрат для каждого агента (или сумме затрат для каждой задачи. Что в данном случае одно и то же). То задача называется линейным назначением. Обычно, когда говорят о задаче присвоения без какой-либо дополнительной квалификации, то

подразумевают линейную уравновешенную задачу присвоения.

Примеры

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

Теперь предположим. Что есть четыре свободных такси. Но все же только три клиента. Это проблема несбалансированного назначения. Один из способов решить эту проблему-придумать четвертую фиктивную задачу, возможно, называемую

Это сводит проблему к задаче сбалансированного назначения. Которая затем может быть решена обычным способом и все же дать наилучшее решение проблемы.

Подобные корректировки могут быть сделаны для того. Чтобы разрешить больше задач. Чем агенты, задачи. На которые должно быть назначено несколько агентов (например. Группа из большего числа клиентов. Чем поместится в одном такси). Или максимизировать прибыль. А не минимизировать затраты.

Формальное определение

Формальное определение задачи присваивания (или задачи линейного присваивания) таково:

Даны два множества A и Tодинакового размера вместе с весовой функцией C : A × TR. Найдите биекцию f : AT такую. Что функция стоимости:

aAC(a,f(a)){\displaystyle \sum _{a\in A}C(a,f(a))}

сводится к минимуму.

Обычно весовая функция рассматривается как квадратная вещественная

матрица C, так что функция затрат записывается как:

aACa,f(a){\displaystyle \sum _{a\in A}C_{a,f(a)}}

Проблема является

Наивное решение задачи назначения состоит в том. Чтобы проверить все назначения и рассчитать стоимость каждого из них. Это может быть очень неэффективно. Так как при

n агентах и n задачах существует n! (факториал n) различные назначения. К счастью, существует множество алгоритмов решения задачи во времени полиномом по n.

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

Сбалансированный назначение

В задаче сбалансированного присваивания обе части двудольного графа имеют одинаковое число вершин. Обозначаемое через

n.

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

O(mn+n2logn){\displaystyle O(mn+n^{2}\log n)}

равна [2], где m-число ребер. В настоящее время это самое быстрое время выполнения сильно полиномиального алгоритма для этой задачи. Если все веса являются целыми числами. То время выполнения может быть улучшено

O(mn+n2loglogn){\displaystyle O(mn+n^{2}\log \log n)}

, но результирующий алгоритм является только слабо полиномиальным.[3] Если веса являются целыми числами. А все веса не более C (где C>1-некоторое целое число). То задача может быть решена за >

O(mnlog(nC)){\displaystyle O(m{\sqrt {n}}\log(n\cdot C))}

слабо полиномиальное время методом. Называемым весовым масштабированием.[4][5][6]

В дополнение к глобальным методам существуют локальные методы, основанные на поиске локальных обновлений (а не полных путей расширения). Эти методы имеют худшие асимптотические гарантии времени выполнения. Но на практике они часто работают лучше.

Эти алгоритмы называются алгоритмами аукциона . Алгоритмамиpush-relabel или алгоритмами preflow-push. Было показано. Что некоторые из этих алгоритмов эквивалентны[7]

Некоторые из локальных методов предполагают. Что граф допускает идеальное совпадение; если это не так. То некоторые из этих методов могут работать вечно.[1]:3 Простой технический способ решить эту проблему-расширить входной граф до полного двудольного графа, добавив искусственные ребра с очень большими весами. Эти веса должны превышать веса всех существующих соответствий. Чтобы предотвратить появление искусственных ребер в возможном решении.

Как показали Малмули. Вазирани и Вазирани[8], задача идеального соответствия минимального веса преобразуется в поиск миноров в матрице смежности графа. Используя лемму об изоляции, минимальное идеальное соответствие веса в графе может быть найдено с вероятностью не менее½. Для графа с n вершинами требуется

O(log2(n)){\displaystyle O(\log ^{2}(n))}

время.

Несбалансированное назначение

В задаче несбалансированного назначения большая часть двудольного графа имеет n вершин. А меньшая часть-r

Несбалансированное назначение может быть сведено к сбалансированному назначению.

Наивное сокращение состоит в том. Чтобы добавить

nr{\displaystyle n-r}

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

n(nr){\displaystyle n(n-r)}

новые грани. Более эффективное сокращение называется методом удвоения. Здесь новый граф G’ строится из двух копий исходного графа G: прямой копии Gf и обратной копии Gb. Обратная копия G’теперь есть n+r вершин. Между копиями нужно добавить два вида связывающих ребер:[1]:4-6

  • От большой к большой: от каждой вершины в большей части

    Gfдобавьте ребро с нулевой стоимостью к соответствующей вершине в Gb.

  • Small-to-small: если исходный граф не имеет одностороннего идеального соответствия. То из каждой вершины в меньшей части Gfдобавьте очень дорогостоящее ребро к соответствующей вершине в Gb.

В общем, в большинстве

n+r{\displaystyle n+r}

случаев требуются новые края. Результирующий график всегда имеет идеальное соответствие размеров

n+r{\displaystyle n+r}

. Идеальное соответствие с минимальной стоимостью на этом графике должно состоять из соответствий с минимальной стоимостью и максимальной мощностью в Gf и Gb. Основная проблема с этой техникой удвоения заключается в том. Что при этом нет никакого прироста скорости

rn{\displaystyle r\ll n}

.

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

O(ms+s2logr){\displaystyle O(ms+s^{2}\log r)}

сильно полиномиальном времени. В частности, если s=r, то время выполнения

O(mr+r2logr){\displaystyle O(mr+r^{2}\log r)}

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

O(ms+s2loglogr){\displaystyle O(ms+s^{2}\log \log r)}

.[1]:6

Решение методом линейного программирования

Задача задания может быть решена путем представления ее в виде линейной программы. Для удобства изложим задачу максимизации. Каждое ребро (i,j), где i находится в A, а j-в T. Имеет вес

wij{\displaystyle w_{ij}}

. Для каждого ребра (i,j) имеется переменная

xij{\displaystyle x_{ij}}

. Переменная равна 1, если ребро содержится в совпадении. И 0 в противном случае. Поэтому мы устанавливаем ограничения домена:

0xij1 for i,jA,T,{\displaystyle 0\leq x_{ij}\leq 1{\text{ for }}i,j\in A,T,\,}

xijZ for i,jA,T.{\displaystyle x_{ij}\in \mathbb {Z} {\text{ for }}i,j\in A,T.}

Общий вес соответствия:

(i,j)A×Twijxij{\displaystyle \sum _{(i,j)\in A\times T}w_{ij}x_{ij}}

. Цель состоит в том. Чтобы найти идеальное соответствие максимального веса.

Чтобы гарантировать. Что переменные действительно представляют собой идеальное соответствие. Мы добавляем ограничения, говорящие. Что каждая вершина соседствует ровно с одним ребром в соответствии, т. Е.

jTxij=1 for iA,   iAxij=1 for jT,{\displaystyle \sum _{j\in T}x_{ij}=1{\text{ for }}i\in A,\,~~~\sum _{i\in A}x_{ij}=1{\text{ for }}j\in T,\,}

В целом у нас есть следующие LP:

maximize  (i,j)A×Twijxij{\displaystyle {\text{maximize}}~~\sum _{(i,j)\in A\times T}w_{ij}x_{ij}}

subject to  jTxij=1 for iA,   iAxij=1 for jT{\displaystyle {\text{subject to}}~~\sum _{j\in T}x_{ij}=1{\text{ for }}i\in A,\,~~~\sum _{i\in A}x_{ij}=1{\text{ for }}j\in T}

0xij1 for i,jA,T,{\displaystyle 0\leq x_{ij}\leq 1{\text{ for }}i,j\in A,T,\,}

xijZ for i,jA,T.{\displaystyle x_{ij}\in \mathbb {Z} {\text{ for }}i,j\in A,T.}

Это целочисленная линейная программа. Однако мы можем решить ее без ограничений на интегральность (то есть отбросить последнее ограничение). Используя стандартные методы решения непрерывных линейных программ. Хотя эта формулировка допускает также дробные значения переменных. В этом частном случае LP всегда имеет оптимальное решение. Где переменные принимают целочисленные значения. Это происходит потому. Что матрица ограничений дробного LP полностью унимодулярна – она удовлетворяет четырем условиям Хоффмана и Гейла.

Это также может быть доказано непосредственно.[9]:31-37 Пусть x-оптимальное решение дробного LP, w(x) — его полный вес, а k(x)-число неинтегрированных переменных. Если k(x)=0, мы закончили. В противном случае существует, скажем. Дробная переменная

xi1,j2{\displaystyle x_{i1,j2}}

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

xi3,j2{\displaystyle x_{i3,j2}}

. По аналогичным соображениям на i3 должна быть другая переменная. Смежная с i3 с дробным значением. Скажем

xi3,j4{\displaystyle x_{i3,j4}}

. По аналогичным соображениям мы перемещаемся из одной вершины в другую. Собирая ребра с дробными значениями. Поскольку граф конечен. В какой-то момент мы должны иметь цикл. Без потери общности можно предположить, что цикл заканчивается в вершине i1, поэтому последняя дробная переменная в цикле есть

xi1,j2m{\displaystyle x_{i1,j_{2m}}}

. Таким образом. Число ребер в цикле равно 2м – это должно быть даже так. Как граф двудольный.

Предположим. Что мы добавим некоторую константу е ко всем четным переменным цикла и удалим ту же самую константу е из всех нечетных переменных цикла. Для любого такого eсумма переменных вблизи каждой вершины остается неизменной (1). Поэтому вершинные ограничения все еще выполняются. Более того, если e достаточно мало, то все переменные остаются между 0 и 1, так что ограничения области также удовлетворяются. Легко найти самую большую букву е это поддерживает ограничения области: это либо наименьшая разница между нечетной переменной и 0, либо наименьшая разница между четной переменной и 1. Теперь у нас есть одна дробная переменная меньше. Поэтому k(x) уменьшается на 1. Объективное значение остается неизменным. Поскольку в противном случае мы могли бы увеличить его. Выбрав e положительным или отрицательным. Что противоречит предположению о его максимальности.

Повторяя процесс удаления цикла. Мы приходим не более чем через n шагов к решению. В котором все переменные являются интегральными.

Другие методы и аппроксимационные алгоритмы

Существуют и другие подходы к решению проблемы присвоения. Рассмотренные Дуаном и Петти[10] (см. таблицу II). В их работе предлагается аппроксимационный алгоритм для задачи присваивания (и более общей задачи сопоставления максимального веса), которая выполняется в линейном времени для любой фиксированной границы ошибки.

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

Ссылки и дальнейшее чтение

  1. ^ b c d
  2. ^ Фредман, Майкл Л.; Тарьян, Роберт Эндре (1987-07-01). J. ACM. 34 (3): 596–615. doi:10.1145/28869.28874. ISSN 0004-5411. S2CID 7904683.
  3. ^ Торуп, Миккель (2004-11-01). Журнал компьютерных и системных наук. Специальный выпуск STOC 2003. 69 (3): 330–353. doi:10.1016/j.jcss.2004.04.003. ISSN 0022-0000.
  4. ^ Габов, Х.; Тарьян, Р. (1989-10-01). SIAM Journal on Computing. 18 (5): 1013–1036. doi:10.1137/0218069. ISSN 0097-5397.
  5. ^ Голдберг, А.; Кеннеди, Р. (1997-11-01). SIAM Journal on Discrete Mathematics. 10 (4): 551–572. doi:10.1137/S0895480194281185. ISSN 0895-4801.
  6. ^ Орлин, Джеймс Б.; Ахуджа, Равиндра К. (1992-02-01). Математическое программирование. 54 (1-3): 41-56. doi:10.1007/BF01586040. ISSN 0025-5610. S2CID 18213947.
  7. ^ Варгас, Маркос К.; Валенсия, Карлос Э.; Перес, Серхио Л.; Альфаро, Карлос А. (2018-10-08). arXiv:1810.03562v1 [матем.ОК].
  8. ^ Mulmuley, Ketan; Vazirani, Umesh; Vazirani, Vijay (1987). Комбинаторика. 7 (1): 105-113. doi:10.1007/BF02579206. S2CID 47370049.
  9. ^ Gärtner, Bernd; Matoušek, Jiří (2006). Понимание и использование линейного программирования. Берлин: Шпрингер. ISBN 3-540-30697-8.
  10. ^ Дуань, Ран; Петти, Сет (2014-01-01). (PDF). Журнал ACM. 61: 1–23. doi:10.1145/2529989. S2CID 207208641.