Задача о назначении с дополнительными работами и исполнителями | Статья в сборнике международной научной конференции

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

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


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


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

Похожие статьи

Математическая модель управления обучением и её решение...

Математическое моделирование социальных процессов, решение задач оптимального управления и планирования приобретают всё большую актуальность в настоящее время в самых разнообразных сферах человеческой деятельности ([1], [2], [3]...

Организация решения задач динамического программирования

Основная цель работы — показать, как решаются три задачи динамического программирования: оптимальная замена оборудования, оптимальное распределение ресурсов, минимизация затрат на строительство и эксплуатацию предприятий.

Итеративный алгоритм для задачи о назначении

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

Приложения линейного программирования к решению...

Метод решения рассматриваемых ниже задач связан с именем российского Лауреата Нобелевской премии по экономике Л. В. Канторовича (за вклад в теорию оптимального распределения ресурсов; 1975 г.; взгляд на математику как на единую дисциплину...

Декомпозиционный метод решения транспортной задачи...

3. Метод решения задачи. Задачу (1)−(4) можно рассматривать как задачу на условный экстремум и использовать метод множителей Лагранжа.

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

Решение многокритериальных задач линейного...

Рис. 1. Оптимальное решение задачи.

Решение транспортных задач с применением программирования... Решение интервальной задачи дробно-линейного программирования сведением к задаче линейного программирования.

целевая функция, оптимальное решение задачи, ограничение...

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

Анализ существующих методов решения транспортной...

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

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

Оптимизация по условиям Куна — Таккера | Статья в журнале...

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

Обсуждение

Социальные комментарии Cackle

Похожие статьи

Математическая модель управления обучением и её решение...

Математическое моделирование социальных процессов, решение задач оптимального управления и планирования приобретают всё большую актуальность в настоящее время в самых разнообразных сферах человеческой деятельности ([1], [2], [3]...

Организация решения задач динамического программирования

Основная цель работы — показать, как решаются три задачи динамического программирования: оптимальная замена оборудования, оптимальное распределение ресурсов, минимизация затрат на строительство и эксплуатацию предприятий.

Итеративный алгоритм для задачи о назначении

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

Приложения линейного программирования к решению...

Метод решения рассматриваемых ниже задач связан с именем российского Лауреата Нобелевской премии по экономике Л. В. Канторовича (за вклад в теорию оптимального распределения ресурсов; 1975 г.; взгляд на математику как на единую дисциплину...

Декомпозиционный метод решения транспортной задачи...

3. Метод решения задачи. Задачу (1)−(4) можно рассматривать как задачу на условный экстремум и использовать метод множителей Лагранжа.

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

Решение многокритериальных задач линейного...

Рис. 1. Оптимальное решение задачи.

Решение транспортных задач с применением программирования... Решение интервальной задачи дробно-линейного программирования сведением к задаче линейного программирования.

целевая функция, оптимальное решение задачи, ограничение...

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

Анализ существующих методов решения транспортной...

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

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

Оптимизация по условиям Куна — Таккера | Статья в журнале...

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

Задать вопрос