Введение 4
1 Анализ задачи о назначениях и алгоритмов ее решения 8
1.1 Модели задач линейного программирования 8
1.2 Эквивалентные преобразования моделей задач линейного
программирования 10
1.3 Простейшая линейная модель задачи о назначениях и ее особенности . 11
1.4 Анализ алгоритмов решения простейшей линейной задачи о
назначениях 12
1.5 Анализ моделей и алгоритмов решения задач о назначениях 15
1.6 Анализ эквивалентных преобразований моделей задач о назначениях .. 21
Выводы 32
2 Модели и алгоритмы решения однокритериальных обобщенных
линейных задач о назначениях 33
2.1 Модель и алгоритм решения задачи с недопустимыми комбинациями
назначений 33
2.2 Модель и алгоритм решения задачи с порядком назначений 39
2.3 Модель и алгоритм решения задачи с приоритетными назначениями ... 45
Выводы 49
3 Модели многокритериальных задач о назначениях и алгоритмы их
решения 51
3.1 Модель простейшей линейной многокритериальной задачи о
назначениях 51
3.2 Алгоритм решения простейшей линейной многокритериальной
задачи о назначениях 53
3.3 Решение простейшей линейной многокритериальной задачи о
назначениях с использованием линейной свертки 55
3.4 Решение простейшей линейной многокритериальной задачи о
назначениях с использованием мультипликативной свертки 58
3.5 Решение простейшей линейной многокритериальной задачи о
назначениях с использованием свертки на основе отклонения от идеальной точки 61
3.6 Модель и алгоритм решения многокритериальной задачи о
назначениях с целевыми функциями противоположного направления 63
3.7 Модель и алгоритм решения многокритериальной открытой задачи
о назначениях 65
3.8 Модель и алгоритм решения многокритериальной задачи с
недопустимыми назначениями 67
3.9 Модель и алгоритм решения многокритериальной задачи с
порядком назначений 69
3.10 Модель и алгоритм решения многокритериальной задачи с
приоритетными назначениями 72
Выводы 74
Заключение 75
Список использованных источников 76
Приложение А Листинг программы поиска оптимального решения открытой задачи о назначениях 84
Приложение Б Листинг программы поиска оптимального решения
задачи о назначениях с матрицей затрат, элементы которой произвольного знака 86
Приложение В Листинг программы поиска оптимального решения задачи с недопустимыми назначениями 88
Приложение Г Листинг программы поиска оптимального решения задачи с порядком назначений 90
Приложение Д Листинг программы поиска оптимального решения задачи с приоритетными назначениями 93
Приложение Е Листинг программы поиска оптимального решения простейшей линейной многокритериальной задачи о назначениях с использованием свертки на основе отклонения от идеальной точки 95
Актуальность темы исследования. Задача о назначениях является одной из фундаментальных задач математического программирования. Она широко используется в прикладной деятельности и имеет множество интерпретаций. В частности, математическая модель задачи о назначениях позволяет формально описать и провести количественный анализ таких ситуаций, как определение победителей конкурсных торгов, подбор персонала на вакантные должности, прикрепление транспорта к одному из маршрутов, распределение работ между механизмами, распределение целей между средствами поражения и т.д. Существуют стандартные алгоритмы поиска оптимального решения задачи о назначениях с простейшей линейной моделью, позволяющие получить точное решение за полиномиальное время. К таким алгоритмам относятся венгерский метод и метод Мака.
Как правило, формулировка большинства прикладных задач о назначениях не удовлетворяет простейшей линейной модели и требует ее обобщения. Результатом обобщения является задача с нелинейной целевой функцией (Misevicius A., Burkard R. E., Каширина И. Л., Лагздин А. Ю.), многокритериальная задача (Scarelli А, Cela E., Кочкаров Р. А., Ларичев О. И.), интервальная и нечеткая задачи (Salehi K., Kumar A., Леденева Т. М., Попов В. П., Майорова И. В.), многоиндексная задача (Pusztaszeri J. F., Rensing P. E., Гимади Э. Х., Афраймович Л. Г.) и пр. Такое многообразие математических моделей задач о назначениях, обусловленное их прикладной направленностью, порождает огромное число алгоритмов их решения. Большое количество исследований связано с разработкой
алгоритмов решения на графах (Гимади Э. Х., Айран Н. М., Сердюков А. И., Коркишко Н. М., Кордюков Р. Ю., Допира Р. В., Иванова А. В.), разработкой алгоритмов, основанных на модификации метода динамического программирования (Martello S., Burkard R., Лагздин А. Ю., Забудский Г. Г.), модификации метода ветвей и границ (Burkard R., Balas E., Magos D., Афраймович Л. Г., Тюнтяев А. С.), построением генетических алгоритмов решения (Fleurent C., Holland J. H., Ramadoss S. K., Каширина И. Л.,
Семенов Б. А., Гуляницкий Л. Ф.), созданием алгоритмов решения, основанных на использовании двойственных методов
(Goldfarb D., Медведева О. А., Чернышова Г. Д., Малюгина О. А.). Часто предложенные алгоритмы характеризуются громоздкостью используемого математического аппарата, а также не гарантируют нахождения оптимального решения в общем случае, что может привести к значительным экономическим потерям в контексте многих прикладных задач. При этом недостаточно внимания уделяется вопросам эквивалентных преобразований, с помощью которых можно существенно упростить исходную математическую модель задачи и привести ее к виду, для которого уже разработан эффективный алгоритм решения. Известны лишь отдельные примеры задач о назначениях, для нахождения оптимального решения которых используются эквивалентные преобразования - это задача с целевой функцией на максимум (Butkovic P., Burkard R., Богданова Е. Л., Соловейчик К. А.), открытая задача (Абу-Абед Ф.Н., Медведева О. А., Иванова А. В., Муха В. С.), задача с матрицей затрат, элементы которой произвольного знака (Лелякова Л. В., Харитонова А. Г., Чернышова Г. Д.) задача с запретами на отдельные назначения (Эддоус М., Стэнсфилд Р., Медведева О. А.). В связи с этим задача описания эквивалентных преобразований задачи о назначениях и разработки алгоритма приведения обобщенной модели к эквивалентной форме, позволяющей использовать существующие стандартные алгоритмы решения, является актуальной.
Целью магистерской диссертации является построение математических моделей линейных обобщенных задач о назначениях и разработка алгоритмов решения, основанных на эквивалентных преобразованиях математических моделей...
В работе выделены особенности математической модели простейшей линейной задачи о назначениях. Рассмотрены различные обобщения простейшей линейной модели и предложена классификация задач о назначениях по основным признакам, к которым относятся вид целевой функции и их количество, направление оптимизации, тип коэффициентов целевой функции, размерность неизвестных. Проведен анализ алгоритмов решения задач о назначениях. Исследованы алгоритмы, основанные на эквивалентных преобразованиях задач о назначениях.
Разработаны эквивалентные преобразования в простейшую линейную модель комбинаций недопустимых назначений, порядка назначений, приоритетных назначений.
Разработаны математические модели однокритериальных обобщенных задач о назначениях, отличительной особенностью которых является их эквивалентность простейшей линейной модели.
Разработаны математические модели многокритериальных
обобщенных задач о назначениях, отличительной особенностью которых является их эквивалентность многокритериальной простейшей линейной модели.
Разработаны алгоритмы решения однокритериальных и многокритериальных обобщенных задач о назначениях, которые, в отличие от известных, основаны на эквивалентных преобразованиях математических моделей, что позволяет использовать для нахождения оптимального решения стандартные алгоритмы.
Разработан комплекс программ, использование которых позволяет найти точное решение обобщенной задачи о назначениях с помощью эквивалентных преобразований и с использованием стандартных алгоритмов.
Помощь студентам и аспирантам в выполнении работ от наших партнеров
