Решение задачи о назначениях

Симплексный алгоритм

Рассмотрим задачу о назначениях, условия которой приведены на рисунке1.

Если применить метод выбора исходного решения для вычислительных оценок (1. Вычесть наименьший коэффициент строки i из всех остальных коэффициентов затрат в этой строке, что даст новый вектор коэффициентов. 2. Вычесть наименьшую компоненту этого нового вектора из всех элементов столбца /, вследствие чего получается таблица относительных затрат. 3.

Исходный базис показан на рисунке 1. Отметим, что три маршрута (во второй строке) имеют нулевые значения переменных, что указывает на вырожденность. Можно проследить за всеми итерациями, рассмотрев рисунки 3−9, содержащие последовательности полученных оценок и пробные решения. Отметим также, что значение целевой функции не меняется вплоть до отыскания последнего решения.

Метод, основанный на алгоритме максимального потока/минимальной стоимости

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

Алгоритм сводится к следующим шагам.

Шаг 1. При заданных оценках строк , i = 1, 2,.. ., п, и столбцов , j = 1, 2,.. ., п, дающих неотрицательные относительные оценки ()? 0, определяется, существует ли допустимое решение, в которое входят только маршруты с нулевыми относительными оценками. В случае положительного ответа на этот вопрос — останавливаемся, так как решение оптимально. В противном случае осуществляется переход к шагу 2.

Шаг 2. Оценки и изменяются таким образом, чтобы относительная оценка по крайней мере одного нового маршрута была равна нулю. Возвращаются к шагу 1. Шаг 1 всегда можно начать, используя значения оценок, определяемые с помощью метода выбора исходного решения (В данном примере относительные оценки являются элементами таблицы на рис. 2.) Однако для сравнения рассматриваемого метода с симплексным алгоритмом удобно начать со значений, приведенных в таблице на рис. 10. Алгоритм максимального потока используется на шаге 1 для определения существования допустимого решения, содержащего только маршруты с нулевыми элементами таблицы на рис. 10. Имеются упрощенные табличные приемы реализации этого алгоритма, но поскольку основной целью в данном случае является разъяснение эффективности алгоритма максимального потока для решения задачи о назначениях, в последующем изложении эти приемы, позволяющие сокращать объем вычислений, не применяются.

Сеть, содержащая маршруты (дуги) с нулевыми относительными.

оценками, соответствующими элементам таблицы на рис. 10, построена на рис. 12. Обозначения узлов соответствуют строке i таблицы на рис. 10, и аналогично обозначения соответствуют столбцу j

Рис. поток в сети модели назначений.

этой таблицы. Все дуги, исходящие из источника и входящие в сток, имеют пропускную способность, равную единице, что соответствует ограничениям по строкам и столбцам задачи о назначениях. Если бы максимальный поток в сети был равен четырем, то соответствующее этому потоку решение являлось бы оптимальным, поскольку единичный поток по дуге () означает, что = 1. Пробное решение, в котором величина потока равна трем, показано на рис. 12. Алгоритм максимального потока реализован на рис. 13, показывающем, что в такой сети поток увеличить нельзя. Поэтому необходимо перейти к шагу 2.

Рациональный путь изменения значений величин и заключается в следующем. Поскольку поток в сети, изображенной на рисунке 13, максимален, но меньше четырех единиц, необходимо ввести по крайней мере одну новую дугу (,). Исходя из характера потокового алгоритма, целесообразно ограничиться только такими дугами, у которых узел помечен, а узел не помечен. Если ввести в сеть такую дугу, то шаги потокового алгоритма можно продолжить, что позволит просмотреть по крайней мере еще один узел .

Однако, изменяя значения величин и , необходимо проявлять осмотрительность, чтобы не нарушить равенства — - = 0 для дуг, по которым в текущем решении проходит ненулевой поток, а также для дуг, помеченных знаком + в процессе просмотра сети. В противном случае может оказаться невозможным продолжение просмотра после реализации шага 1.

Рис. просмотр сети для обнаружения возможности увеличения потока.

Кроме того, необходимо сохранить соотношение — -? 0 для всех i и j.

Правило, обеспечивающее выполнение всех этих условий, формулируется следующим образом.

1) Прибавить величину к , если помечен узел .

2) Вычесть величину из , если помечен узел .

Здесь — наименьшая относительная оценка для дуг между каждым помеченным узлом и непомеченным узлом.

На рис. 13 узлы и помечены, а узлы не помечены.

Следовательно, в таблице на рис. 13 нужно просмотреть элементы на пересечении строк 3 и 4 со столбцами 1, 2, 3, в результате чего получаем.

.

В таблице на рис. 11 приведены измененные значения и , а также новые значения относительных оценок. Отметим, что теперь дуга (, ) имеет относительную оценку, равную нулю, хотя дуге () соответствует положительная относительная оценка. Сеть, отображающая это решение, показана на рис. 14. Алгоритм максимального потока на такой сети продолжает работать и помечаются узлы и, наконец, сток. Знаки + и — на дугах определяют путь, увеличивающий поток, который приводит к оптимальному решению, показанному на рис. 15.

Повторим еще раз вкратце рассмотренный алгоритм. Начав с пробных значений и на шаге 1, нужно применить алгоритм максимального потока к соответствующей сети. Если полученная в результате величина общего потока в сети равна п, то решение оптимально и вычислительная процедура заканчивается. В противном случае следует перейти к шагу 2, на котором значения и изменяются в соответствии с правилами (5) и (6). Далее возвращаются к шагу 1 и несколько измененной в результате выполнения этого шага сети, в которую введена по крайней мере одна новая дуга (в предположении, что соответствующий коэффициент для этой дуги равен ), а некоторые неиспользуемые дуги могут быть исключены. Затем вновь возвращаются к алгоритму максимального потока, применяя его к схеме потока, полученной на предыдущем шаге. Вновь проверяют, равна ли величина потока, общего в сети, числу п и т. д.

Рис. 14. измененная сеть.

Рис. 15. окончательное решение.

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

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

Одним из следствий доказательства сходимости является то, что для получения решения не требуется применять шаг 2 более чем.

0,5(раз. Эта верхняя граница, как правило, намного превышает действительное число повторений шага 2. Вместе с тем следует подчеркнуть, что даже такая верхняя граница значительно меньше, чем , которая является верхней оценкой сходимости симплексного алгоритма, выраженной через число возможных базисных решений.

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

Чтобы приступить к шагу 1 изложенного выше метода, нужно найти оценки и , такие, чтобы все относительные оценки были не отрицательными. Без потери общности можно предположить, что все, поскольку всегда можно прибавить некоторую положительную константу с* к каждому коэффициенту . Тогда шаг 1 изложенного ранее метода можно начать, положив. Если выполнить это условие, то оказывается, что последовательность получаемых решений содержит минимальную стоимость по сравнению со всеми остальными значениями при одной и той же величине потока в сети. Это обстоятельство позволяет изменить структуру алгоритма, что в свою очередь обеспечивает возможность обобщения потокового метода для решения более сложных сетевых задач. Смысл алгоритма заключается в том, чтобы увеличивать общую величину потока таким образом, чтобы это увеличение происходило при минимальных приращениях затрат. Так, если F единиц потока распределяются по сети, с помощью излагаемого метода отыскивается путь минимальной стоимости, увеличивающий поток, причем увеличение потока производится именно на этом пути. Метод отыскания пути минимальной стоимости основан на алгоритме выбора кратчайшего маршрута.

Алгоритм минимальной стоимости/максимального потока сводится к выполнению следующих шагов.

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

Рис. сеть, соответствующая методу минимальной стоимости максимального потока.

Если между узлами и существует поток, то вводится дуга () и ее длина принимается равной —. При таком принципе построения сети можно увеличить поток из источника в сток по любому пути новой сети по сравнению с величиной потока в исходной сети.

Шаг 2. Найти кратчайший маршрут из источника в сток в новой сети. По стандартным правилам увеличить поток по этому маршруту (пути) в исходной сети. Если все ограничения модели назначений удовлетворяются, то вычислительная процедура заканчивается. В противном случае осуществляется переход к шагу 1.

Изложенный метод демонстрируется на примере рис. 1. Предположим, что в результате применения алгоритма найдено решение минимальной стоимости для величины потока в три единицы. Это решение совпадает с рис. 12, а его стоимость составляет 28(= 2 + 18 + 8).

Новая сеть, построенная на шаге 1, показана на рис. 16. Отметим, что источник связан только с узлом , а сток — только с узлом поскольку все остальные дуги являются насыщенными. Сеть содержит дуги (), () и (), так как в текущем решении поток имеет противоположное направление. В текущем решении потоки по всем остальным дугам равны нулю.

Рис. кратчайший маршрут.

Далее к этой сети применяется алгоритм выбора кратчайшего маршрута, который приводит к результату, показанному на рис. 17. Направление единичного потока по указанному маршруту дает оптимальное решение, согласующееся с рис. 15. Отметим, что направление единичного потока по дуге () означает, что в исходной сети поток по дуге () должен быть снят. Поскольку длина кратчайшего пути равна 24, общая стоимость окончательного решения составляет 52 (=28 + 24). Длина кратчайших маршрутов из каждого узла является оптимальным значением -, и аналогично длина кратчайшего маршрута из каждого узла есть оптимальное значение .[2].