- Предложен новый метод решения задачи о назначении, основанный на декомпозиции исходной задачи на ряд двумерных оптимизационных задач. Целочисленность и монотонность по целевой функции итерационного процесса решения обеспечивает конечность алгоритма. В результате может получиться или единственное оптимальное решение исходной задачи о назначении, или система ограничений, из которой можно получить все оптимальные решения.
- Введение. В [1] предлагается метод решения классической транспортной задачи, основанный на декомпозиции исходной задачи на последовательность двумерных задач с последовательно модифицируемыми целевыми функциями. В настоящей работе метод распространяется на случай задачи о назначении, когда имеются дополнительные работы и исполнители, а затраты линейно зависят от соответствующих слабых переменных. Тем самым, алгоритм [1] напрямую переносится на важный класс нелинейных задач транспортного типа.
- 1. Постановка задачи. Имеется, как и в обычной задаче о
назначении n работ и n исполнителей. Стоимость выполнения
ой
работы
ым
исполнителем равна
.
Кроме того, имеются еще n дополнительных работ. Каждую
ую
дополнительную работу может выполнять только
й
исполнитель. Имеется также n дополнительных исполнителей. Каждый
ый
дополнительный исполнитель может выполнять только
ую
(обычную, не дополнительную работу). Стоимость выполнения
й
дополнительной работы равна
,
стоимость работы
го
дополнительного исполнителя
.
Задача состоит в минимизации общей стоимости выполнения работ при
обеспечении выполнения всех обычных работ. - Формальная запись задачи:
-
(1) -
(2) -
(3) -
- принимают значения нуль или единица. (4) -
Кроме того, будем считать
четными числами, что не ограничивает общности рассмотрения. -
2. Метод решения задачи. Положим
и образуем 2n оптимизационных задач с одним ограничением. Первый
этап. Сформируем одномерных задач. - Первые n оптимизационных задач:
-
(5) -
при ограничениях (4) и при
м ограничении из (1),
. - Вторые n оптимизационных задач:
-
(6) -
при ограничениях (4) и при
м ограничении из (2),
. - Задачи вида (1), (4), (5) и (2), (4), (6) решаются простым выбором переменной, у которой целевой функции минимальный коэффициент. Если минимальных коэффициентов несколько, то в качестве решения записывается, что сумма соответствующих переменных равна единице.
- Если объединение оптимальных решений всех 2n задач (1), (4), (5) и (2), (4), (6) является допустимым решением задачи (1) – (4), то оно является оптимальным решением задачи (1) – (4).
-
В противном случае начинается итерационный процесс решения
оптимизационных задач с двумя ограничениями – по одному
ограничению из (1) и (2) и с целевой функцией, в которой из (3)
присутствуют только переменные, которые имеются в выбранных
ограничениях. Первая задача с двумя ограничениями запишется: -
(7) -
(8) -
(9) - при ограничениях (4).
-
Если
,
то оптимальным решением задачи (4), (7)-(9) будет
. -
Если
,
то в оптимальное решение задачи (4), (7)-(9) со значением 1 войдут
переменные с индексами, на которых реализуется
- Если
,-
то в качестве решения в обоих ограничениях записывается
в сумме той переменной, с индексом которой реализуется выписанный
минимум.
-
После решения задачи пересчитываются
и
.
Если
меньше соответствующего минимума (для определенности пусть это будет
),
то получаем
и
.
Если
равно минимуму, то полагаем
и
.
Если
больше минимуму, то полагаем
и
.
Всегда можно сделать это так, что
и
будут целыми числами. Описанные значения величин
и
обеспечивают совпадение объединения оптимальных решений двух задач с
одним ограничением с оптимальным решением задачи с двумя
ограничениями. -
Так же, как и в общем случае обобщенной транспортной задачи [1],
имеет место монотонное возрастание суммы значений целевых функций
всех
задач с двумя ограничениями. В силу ограниченности и целочисленности
процесса предел достигается за конечное число шагов. Если по
достижении предела объединения оптимальных решений задач с одним
ограничением является допустимым решением задачи (1)-(4), то тем
самым получено оптимальное решение исходной задачи (1)-(4).
- Предельное состояние множества задач с одним ограничением не обязательно непосредственно позволяет получить оптимальное решение исходной задачи. Такую ситуацию назовем вырождением. Вопросы вырождения рассматривали в [1]. Вырождение имеет место и в приводимом ниже примере. Состояние вырожденности преодолевается дополнительными процедурами.
- 3. Пример. Имеется 5 обычных работ и 5 обычных исполнителей. Кроме того, имеется 5 дополнительных работ, не обязательных для выполнения, и 5 дополнительных исполнителей, которым не обязательно предоставлять работу. Необходимо минимизировать общие расходы при выполнении всех обычных работ и предоставлении работы всем обычным исполнителям. Формальная запись задачи:
-
-
, 
-
Объединение
оптимальных решений задач с одним ограничением не является
допустимым решением исходной задачи - Далее решаются задачи с двумерными ограничениями вида:
-
1)
-
2)
-
3)
-
4)
-
Здесь используется сокращённая запись, где фигурируют только индексы
переменных. Нетрудно видеть, что допустимого решения исходной задачи
сразу не получается. В частности, в первых четырёх двумерных задачах
поочередно не допускаются в список на включение в решение. В этом
состоянии, вообще, невозможно составить матрицу претендентов на
включение в оптимальное решение. Положение, однако, легко
исправляется, если в целевых функциях передать по единице из
соответственно в
.
- После этого матрица претендентов на включение в решение может быть выписана:
-
В вычисленной матрице первые пять строк соответствуют пяти обычным
исполнителям. Вторые пять строк соответствуют пяти дополнительным
исполнителям. Первые пять столбцов соответствуют пяти обычным
работам, вторые – пяти дополнительным работам. Единицы стоят
на местах переменных
,
,
,
претендующих на включение в оптимальное решение исходной задачи в
соответствии со значениями коэффициентов в задачах с одним
ограничением.
- Нетрудно видеть, что при однозначности
и
имеется ровно шесть оптимальных решений: три варианта - по два из
трех
,
,
в сочетании с двумя вариантами
,
и
,
,
например -
-
- Литература:
- А.П. Тизик, В.И. Цурков. Метод последовательных изменений параметров функционала для решения транспортной задачи // Автоматика и телемеханика. 2012. №1. P. 148-158.
