Задача выбора (назначения). Венгерский метод решения

Понятия и термины в задаче выбора

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

Постановка задачи выбора

Пусть каждый из П_i должностных лиц должен быть назначен на одну из Д_j должностей (следовательно, i, j = 1(1)n. ). Обозначим через d_ij производительность труда (эффект исполнения обязанностей) лица П_i в должности Д_j. Оптимальное назначение состоит в таком распределении претендентов (личного состава) по должностям, при котором суммарная производительность с эффектом деятельности будет наибольшей. Если xij =1, когда претендент П_i выступает в должности Д_j ; x_ij =0, в остальных случаях, то необходимо максимизировать функцию

Нетрудно видеть, что эту задачу, названную задачей выбора (или задачей о назначениях), легко свести к обычной транспортной задаче, если потребовать минимизации новой линейной формы

Условие баланса в задаче выбора может быть записано в виде равенства m = n. В случае нарушения баланса m ≠ n необходимо добавит либо фиктивных претендентов (если m<n), либо фиктивные должности (если m >n). Задачу выбора можно решить одним из методов решения задач транспортного типа, например методом потенциалов, рассмотренным ранее. Однако специфический характер системы ограничений позволяет существенно упростить алгоритм решения задачи выбора. Один из упрощенных алгоритмов, разработанный венгерским математиком Я. Эгервари, получил наибольшее распространение и был назван в честь своего создателя "венгерским" способом. В основе этого способа используются, так называемые "эквивалентные" преобразования матрицы D_{[m, n]}. Две прямоугольные матрицы А_{[m, n]} и D_{[m, n]} одинаковой размерности m× n называются эквивалентными, если а_ij =d_ij +p_i + r_j, где p_i и r_j - некоторые произвольные действительные числа, [i=1(1)m; j=1(1)n]. Из последней формулы видно, что эквивалентное преобразование сводится к суммированию ко всем элементам любой строки или столбца одного и того же числа. Покажем, что оптимальные планы двух задач выбора, матрицы которых эквивалентны, совпадают. Пусть Х*_{[m, n]} - оптимальный план задачи выбора с матрицей ||a_ij||, элементы которой вычисляются по формуле суммы. По определению оптимального плана

Но суммы для p_i и r_j не зависят от выбранного плана, поэтому можно заключить, что план Х*_{[m, n]} минимизирует линейную форму задачи, т.е. является оптимальным для задачи выбора с эквивалентной матрицей ||d_ij||. Переход от одной матрицы к другой, ей эквивалентной, будем обозначать стрелкой ||d_ij|| → ||а_ij||. Приведем структурно-логическую схему алгоритма венгерского способа, которая включает предварительный этап и три этапа вычислений. Ниже рассмотрим эти этапы.

1. Предварительный этап состоит из определения начального (исходного) плана и соответствующего ему выбора, а также эквивалентного преобразования матрицы ||d_ij||. При этом под "выбором" будем понимать множество элементов d_ij, соответствующих х_ij = 1. Эти элементы условимся обозначать d*_ij.

Пример 1. Пусть заданы матрицы D_[3,3], и план Х_[3,3] для плана необходимо определить выбор, соответствующий плану.

Решение: Искомый выбор получаем при выписывании элементов матрицы D_[3,3], отвечающих х_ij = 1. Этот выбор получает вид d₁₁ = 0; d₂₃ = 5; d₃₂ = 0. Начальный план задачи выбора может быть построен тем же способом, что и в транспортной задаче общего вида, причем способ северо-западного угла здесь вырождается в диагональный способ, при котором х_ij = δ_ij = 1 при i = j; х_ij = δ_ij = 0 при i≠ j; δ_ij - дискретная дельта-функция или символ Кронекера.

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

2. Сущность первого этапа заключается в проверке всех элементов выбора d_ij эквивалентной матрицы, полученной на предварительном этапе. Если все d_ij = 0, то план оптимален и ему соответствует наибольшее значение линейной формы Q*= 0 (при любом другом плане это значение будет отрицательным). Если же некоторые d_ij < 0, то значение функции цели можно увеличить путем перехода на 2-м этапе к новому улучшенному плану.

3. Основным содержанием 2-го этапа. является переход к новому опорному плану, для которого значение линейной формы больше. С этой целью по следующему правилу строится так называемая цепочка пересчета:
- начальным узлом цепочки назначается любой ненулевой элемент выбора d'_ij ≠ 0;
- в качестве следующего узла цепочки выбирается нуль в строке d'_ij; и т. д.

Цепочка пересчета построенная на 2-м этапе, может оказаться либо замкнутой, либо разомкнутой. Если цепочка замкнута, то необходимо перейти к новому выбору (а, следовательно, и к новому плану) путем включения в него нулей и исключения ненулевых элементов замкнутой цепочки. В противном случае, когда цепочка пересчета оказалась незамкнутой, следует перейти к 3-му этапу.

4. Сущность третьего этапа состоит в том, что путем эквивалентного преобразования матрицы число нулей возрастает, но при этом по возможности сохраняются нули незамкнутой цепочки, построенной на предыдущем этапе. Чтобы добиться этого, необходимо из строк, содержащих элементы выбора в граничных клетках незамкнутой цепочки пересчета, вычесть максимальные элементы этих же строк. Затем эти же элементы следует добавить к столбцам, содержащим нули незамкнутой цепочки (тем самым общее число нулей в цепочке останется прежним). После завершения 3-го этапа необходимо (в соответствии со структурно-логической схемой алгоритма) вернуться к 1-му этапу, т.е. снова проверить полученный план на оптимальность.

Пример 2. Рассмотрим методику решения венгерским способом одной из распространенных задач, получившей название "задачи о назначениях". Предположим, что на предприятие возникли 4 вакансии В_j, j =1(1)4 на сходные должности. По объявлению о наборе специалистов подали заявление 4-ро претендентов С_i, i =1(1)4.

Предприятие заинтересовано в наиболее рациональном использовании специалистов, поэтому перед назначением они были проверены компетентной комиссией, определившей (методом экспертных оценок) ту условную прибыль d_ij, которую предприятие получит, если i-й специалист будет назначен на j-ю должность (i,j = 1(1)4 ).

Значения d_ij, установленные комиссией, приведены в матрице D_[4,4], а вид решения задается матрицей Х*_[4,4]

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

Решение. В соответствии с алгоритмом (см. схему) решение задачи заключается в ряде последовательных эквивалентных преобразований матрицы ||d_ij||. Будем исходный план выбирать способом северо-западного угла, а числа p_i и r_j, с помощью которых осуществляются преобразования, записывать около соответствующей строки или столбца матрицы. Тогда цепочка преобразований будет выглядеть следующим образом:

Цепочки в матрицах обозначены пунктиром со стрелками указывающими направление переходов между элементами матриц

Заключение

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