Библиографическое описание:

Кузовлев Д. И., Тизик А. П., Тресков Ю. П. Задача о назначении с дополнительными работами и исполнителями [Текст] // Технические науки в России и за рубежом: материалы II Междунар. науч. конф. (г. Москва, ноябрь 2012 г.). — М.: Буки-Веди, 2012. — С. 16-18.


Предложен новый метод решения задачи о назначении, основанный на декомпозиции исходной задачи на ряд двумерных оптимизационных задач. Целочисленность и монотонность по целевой функции итерационного процесса решения обеспечивает конечность алгоритма. В результате может получиться или единственное оптимальное решение исходной задачи о назначении, или система ограничений, из которой можно получить все оптимальные решения.
Введение. В [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)
Здесь используется сокращённая запись, где фигурируют только индексы переменных. Нетрудно видеть, что допустимого решения исходной задачи сразу не получается. В частности, в первых четырёх двумерных задачах поочередно не допускаются в список на включение в решение. В этом состоянии, вообще, невозможно составить матрицу претендентов на включение в оптимальное решение. Положение, однако, легко исправляется, если в целевых функциях передать по единице из соответственно в .
После этого матрица претендентов на включение в решение может быть выписана:

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

Литература:
  1. А.П. Тизик, В.И. Цурков. Метод последовательных изменений параметров функционала для решения транспортной задачи // Автоматика и телемеханика. 2012. №1. P. 148-158.


Основные термины (генерируются автоматически): исходной задачи, решение исходной задачи, решением задачи, оптимальное решение исходной, оптимизационных задач, оптимальным решением задачи, решения задачи, декомпозиции исходной задачи, транспортной задачи, допустимым решением задачи, оптимальных решений, Формальная запись задачи, оптимальных решений задач, оптимальное решение задачи, метод решения задачи, решением исходной задачи, решения исходной задачи, Метод решения задачи, решения транспортной задачи, классической транспортной задачи.

Обсуждение

Социальные комментарии Cackle
Задать вопрос