Монж: оптимальное назначение

Задача о назначениях является одной из старейших задач комбинаторной оптимизации. Еще в 1784 году ее исследовал Монж (Monge) (в своих работах он использовал термин «задача о транспортировке». Монж был мотивирован задачей транспортировки земли, которую он рассматривал как дискретную, комбинаторную задачу транспортировки молекул: «Когда необходимо перевезти землю из одного места в другое, необходимо учитывать как количество перевозимой земли, так и наличие свободного места там, куда она перевозится. Цена транспортировки одной молекулы пропорциональна ее весу и расстоянию перевозки, а значит, полная цена перевозки должна быть пропорциональна сумме произведений весов молекул на пройденное расстояние».

Формально, Мондж рассматривает следующую задачу: «Пусть на плоскости заданы две области, ABCD и abcd, ограниченные произвольным контуром, непрерывные или дискретные, найти пусть которому должна следовать каждая молекула М первой области, чтобы перейти в некоторую молекулу m второго области, таким образом, что в результате этого перемещения область ABCD была перемещена в область abcd, и сумма произведений веса каждой молекулы на пройденное ей расстояние было минимальным». Мондж предложил геометрический метод решения данной задачи. Несмотря на его геометрическую интуитивность, он был не совсем верен, как заметил в 1928 году Аппель.

Теорема Эгервари

В 1931 году Эгервари опубликовал «взвешенный» вариант теоремы Кёнига: Пусть элементы a_ij матрицы A размера n неотрицательные целые числа, и пусть для некоторых наборов неотрицательных чисел L_i и M_j выполнены условия: а_ij <= L_i + M_j (для всех I и j), тогда получим что min sum (L_k + M_k) = max (a_1p(1) + .. + a_np(n)), где максимум берется по всем перестановкам p.

Доказательство, предложенное Эгервари, сугубо алгоритмично и ведет к алгоритму, использующему «невзвешенную» задачу о паросочетании в качестве подзадачи. Пусть W – максимальное число в матрице А, тогда алгоритму потребуется применить задачу о Паросочетании O(nW) раз, а суммарное время работы алгоритма составит O(nWB(n)), где B(n) – наилучшая оценка времени работы алгоритма нахождения максимального Паросочетания. Этот метод послужил основой для сформулированного в 1955 году «Венгерского метода» Куна, которые мы подробнее рассмотрим далее.

Другим результатом Эгервари было установление следующей двойственной природы задачи о взвешенном Паросочетании: пусть G = (V, E) – двудольный граф и пусть w: E -> R неотрицательная весовая функция. Тогда вес максимального Паросочетания в G равняется минимальному значению y(V), где y: V -> R, таково что: y >= 0  и y_u + y_v >= w(uv).

Е годы

Первый алгоритм для задачи о назначениях был опубликован Истерфилдом (Easterfield) в 1946 году. Мотивация этого алгоритма была следующей: «Что касается исследования в области задач демобилизации вооруженных сил, представляется возможным организовать переход людей из расформированных отрядов в другие отряды таким образом, чтобы их не пришлось потом переводить снова то момента их демобилизации. Более того, исследования количеств людей в различных группах позволили бы организовать этот процесс с наименьшим возможным количеством задержек. К сожалению, непредвиденный конец Японской войны не дал возможности проверить эффективность этой теории в деле. Тем не менее, алгоритм, изложенный в данной статье, возник именно в процессе исследований в этой области».

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

Идея Истерфильда основана на переборе всех подмножеств вершин в лексикографическом порядке, что привело к алгоритму со сложностью O(n^2 * 2^n) (что является улучшением по сравнению с перебором всех перестановок, на который требуется n! действий). Этот алгоритм был в дальнейшем уточнен в 1960 году.

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

Диниц рассматривал задачу о назначениях применительно к распределению работы среди людей. Он писал: «Как было сказано, в задаче о назначениях возникает лишь конечное число перестановок. Поэтому с математической точки зрения достаточно рассмотреть все перестановки и выбрать из них оптимальную. Например, если мы рассмотрим задачу для хотя бы для 10 человек, возникнет более трех с половиной миллионов перестановок, поэтому данный математический подход окажется неприменимым на практике».

В 1949 году Робинсон в отчете для RAND написал что его «неудачный попытки» решения задачи о коммивояжере привели к интересному алгоритму решения задачи о назначениях, основанном на «отмене циклов». Идея его была следующей: рассмотрим произвольную перестановку p. Для всех i,j определим «длину» L_ij = a_jp(j) – a_ip(i) если j != p(i), и бесконечности в противном случае. Если в графе с такими длинами возникнет цикл отрицательного веса, это позволит сразу улучшить перестановку p. Если же такого цикла не окажется, то перестановка p оптимальна. Как отметил Робинсон, данный метод можно применять к графам из 50 вершин, при условии наличия необходимых вычислительных средств.

Ранние 1950е

На семинаре по теории игр в Принстонском Университете в 1951 году, Фон Нейман (Von Neumann) указал на то, что задача о назначениях может быть сформулирована в виде игры с нулевой суммой для двух игроков, и нахождение ее решения эквивалентно поиску оптимальной стратегии в этой игре. Игра устроена следующим образом: пусть задана матрица A. Первый игрок будет играть строками этой матрицы, второй игрок – столбцами. Первый игрок выбирает номер строки, второй – номер столбца, после чего первый «платит» второму A_ij «денег». Индексы строк и столбцов чередоваться не могут, таким образом игра продолжается n раундов (где n – размер матрицы).

Сведение данной игры к задаче о назначениях не очевидно. В дальнейшем к этой идее обращались Браун (Brown) и Робинсок. Фон Нейман также заметил, что поиск оптимальной стратегии по видимому можно осуществить за время пропорциональное некоторой степени n, что заметно меньше чем «очевидное» решение за время n!. Тем не менее, никакой аргументации этого наблюдения не последовало. Похожие идеи также были в работах Дулмага (Dulmage) и Гальперина (Halperine) (1955) и Купманса (Koopmans) и Бекмана (Beckmann) (1955, 1957).

В работах Лорда (Lord) (1952) и Двайера (Dwyer) (1954), был изложен некоторый геометрический подход («метод оптимальных регионов»). Обзор методов решения задачи о назначениях по состоянию на 1953 год был сделан Моцкиным (Motzkin) в 1956 году.