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

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

Тизик А. П., Кузовлев Д. И., Тресков Ю. П. Итеративный алгоритм для задачи о назначении [Текст] // Технические науки: теория и практика: материалы Междунар. науч. конф. (г. Чита, апрель 2012 г.). — Чита: Издательство Молодой ученый, 2012. — С. 41-43. — URL https://moluch.ru/conf/tech/archive/7/2160/ (дата обращения: 21.09.2018).


Предложен новый метод решения задачи о назначении, основанный на декомпозиции исходной задачи на ряд двумерных оптимизационных задач. Целочисленность и монотонность по целевой функции итерационного процесса решения обеспечивает конечность алгоритма. В результате может получиться или единственное оптимальное решение исходной задачи о назначении, или система ограничений, из которой можно получить все оптимальные решения.
Введение. В данной работе метод последовательных изменений параметров функционала для транспортных задач [1] конкретизируется для задачи о назначении (см., например, [2]). Специфика задачи о назначении выявляет особенности применения данного алгоритма. Булевость переменных приводит к более простым формулам, а интерпретация при вырождении является более прозрачной.

1. Предварительные рассмотрения. Имеется следующая классическая задача о назначении (см., например, [2]):

(1.1)

(1.2)

(1.3)

-целые, , (1.4)

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

Вычислим и составим оптимизационных задач с ограничениями (1.1):

; (1.5)

-целые, , (1.6)

Составим также ещё оптимизационных задач с ограничениями (1.2) и (1.6):

(1.7)

Задачи вида (1.1), (1.5), (1.6), и (1.2), (1.6), (1.7) решаются простым выбором наименьших коэффициентов целевой функции, а именно, пусть в задаче вида (1.1), (1.5), (1.6)
, тогда
Точно так же решаются и задачи (1.2), (1.6), (1.7).
Предположим, что все задач (1.1), (1.5), (1.6) и (1.2), (1.6), (1.7) решены. Объединение оптимальных решений всех одномерных задач назовём псевдорешением исходной задачи о назначении, а соответствующую сумму значений целевых функций значением целевой функции псевдорешения. Очевидно, что значение целевой функции псевдорешения не превосходит значения целевой функции оптимального решения исходной задачи (1.1) – (1.4), причём этот факт не зависит от способа разбиения каждого на два слагаемых.
Теорема 1. Если объединение оптимальных решений всех задач (1.1), (1.5), (1.6) и (1.2), (1.6), (1.7) - (псевдорешение исходной задачи о назначении) является допустимым решением задачи исходной задачи (1.1) – (1.4), то оно является оптимальным решением задачи (1.1) – (1.4).

2. Конструкции алгоритма. Пусть объединение оптимальных решений задач (1.1), (1.5), (1.6) и (1.2), (1.6), (1.7) не является допустимым решением исходной задачи (1.1) – (1.4). В этом случае строим пошаговый процесс решения следующих двумерных оптимизационных задач. На первом шаге выпишем первое ограничение из (1.1), (), и первое ограничение из (1.2), ():

(2.1)

(2.2)

Составим целевую функцию:

.(2.3)

и рассмотрим задачу (1.6), (2.1) – (2.3).

При решении задачи (1.6), (2.1) – (2.3) могут иметь место три случая.

Первый случай:

(2.4)

Тогда полагаем и задача (1.6), (2.1) – (2.3) решена. После решения задачи (1.6), (2.1) – (2.3) найдём новые и сначала из системы уравнений

Затем, при необходимости, округлим до ближайшего целого в меньшую сторону, а - в большую сторону.

Второй случай:

Пусть

(2.5)

Тогда обозначим и , вместо решения выписываем ограничения, . Вычисляем новые значения и .

Третий случай:

(2.6)

Тогда, очевидно, что , и задача (1.6), (2.1) – (2.3) решена. Далее, найдём новые и из системы уравнений

Округлим до целого так же, как и во втором случае. Сформируем с новыми значениями и две одномерные задачи. Первая задача

(2.7)

при ограничениях (1.6), (2.1) и вторая задача

(2.8)

при ограничениях (1.6), (2.2).

Имеет место следующее утверждение.

Теорема 2. Во всех вышеперечисленных случаях (выполняется соотношение (2.4), (2.5) или (2.6)) объединение оптимальных решений одномерных задач (1.6), (2.1), (2.7) и (1.6), (2.2), (2.8) с новыми значениями и является оптимальным решением двумерной задачи (1.6), (2.1) – (2.3).

Теорема 3. Объединение решений одномерных задач является оптимальным решением исходной задачи о назначении (1.1) – (1.4).
Теорема 4. Любое допустимое решение редуцированной задачи о назначении, полученной в результате пошагового процесса есть её оптимальное решение.
Итак, оптимальное решение исходной задачи о назначении есть объединение значений переменных, определённых однозначно в итоге пошагового процесса с произвольным допустимым решением редуцированной задачи о назначении.
Рассмотрим, наконец, случай когда в результате пошагового процесса для некоторых переменных в одной из одномерных задач получено некоторое значение, а в другой – ограничение совместно с другими переменными. В этом случае допустимое решение исходной задачи может быть ещё не достигнуто. Возможна ситуация, когда система итоговых ограничений формирует ограничения задачи о назначении с запретами, которая может не иметь допустимых решений. Это будет рассмотрено после примера 1. Верно, однако, следующее утверждение.
Лемма. Оптимальное решение задачи о назначении не изменится, если при сохранении неотрицательности продолжительности выполнения работ изменить на одну и ту же величину все продолжительности выполнения работ одного исполнителя или продолжительность выполнения одной работы всеми исполнителями.
Дальнейшие конструкции алгоритма будут использовать результаты леммы. Они направлены на увеличение количества переменных, входящих в ограничения за счёт переменных с найденным значением. В итоге все переменные окажутся записанными в ограничениях или же оставшиеся переменные с найденным значением не нарушают допустимого решения исходной задачи.
Итак, пусть в результате пошагового процесса допустимое решение исходной задачи о назначении (оно же и оптимальное) не получено. Пусть, для простоты и определённости превышено ограничение первой группы с номером , в котором имеет место
, но в ограничениях второй группы имеют место равенства
, , ,
и, кроме того
. (2.9)
Обозначим через = для в ограничении , а так же в ограничении и, наконец, в ограничении . При этом, очевидно. =0, =0, =0. Вычислим =, где и - переменные, попавшие в ограничения по итогам итерационного процесса (т.е. рассматриваемые на предмет присвоения им положительных значений), и по аналогии обозначим и .
Далее пусть =. Тогда очевидно, что, если, пользуясь утверждением Леммы, передать из целевой функции одномерной задачи (возможно увеличив её предварительно на достаточную величину) с номером ограничения величину в одномерные задачи с номерами , и соответственно, то, по крайней мере, в одной из пар задач с номерами ограничений , (,или ,) в ограничениях появится ещё одна переменная, которая может быть больше нуля, и тем самым неравенство (2.9) станет содержать больше переменных. После некоторого (заведомо меньшего, чем ) количества таких процедур будет получено оптимальное решение исходной транспортной задачи.

Литература:
1. Тизик А.П., Цурков В.И. Метод последовательных изменений параметров функционала в задаче о назначении // Автоматика и телемеханика. 2011. №12.
2. Гольштейн Е.Г., Юдин Д.Б. Задачи линейного программирования транспортного типа, М.: Наука, 1969 г.


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

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

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

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

Применение метода линейного программирования для решения...

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

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

Задача о назначении с дополнительными работами...

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

Решение интервальной задачи дробно-линейного...

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

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

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

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

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

Получим второе допустимое решение . Целочисленное решение задач линейного программирования методом ветвей и границ с помощью Excel.

Обзор методов решения задачи удовлетворения ограничений

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

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

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

Решение задач оптимального раскроя средствами MS Excel.

Интерактивный подход к решению задач линейного... В процессе решения задач...

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

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

Обсуждение

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

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

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

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

Применение метода линейного программирования для решения...

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

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

Задача о назначении с дополнительными работами...

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

Решение интервальной задачи дробно-линейного...

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

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

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

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

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

Получим второе допустимое решение . Целочисленное решение задач линейного программирования методом ветвей и границ с помощью Excel.

Обзор методов решения задачи удовлетворения ограничений

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

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

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

Решение задач оптимального раскроя средствами MS Excel.

Интерактивный подход к решению задач линейного... В процессе решения задач...

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

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

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