Файл: пензенский государственный университет политехнический институт.docx

---

Содержание

---

---

Введение

Актуальность темы исследования. Задача о назначениях является одной из фундаментальных задач математического программирования. Она широко используется в прикладной деятельности и имеет множество интерпретаций. В частности, математическая модель задачи о назначениях позволяет формально описать и провести количественный анализ таких ситуаций, как определение победителей конкурсных торгов, подбор персонала на вакантные должности, прикрепление транспорта к одному из маршрутов, распределение работ между механизмами, распределение целей между средствами поражения и т.д. Существуют стандартные алгоритмы поиска оптимального решения задачи о назначениях с простейшей линейной моделью, позволяющие получить точное решение за полиномиальное время. К таким алгоритмам относятся венгерский метод и метод Мака.

Как правило, формулировка большинства прикладных задач о назначениях не удовлетворяет простейшей линейной модели и требует ее обобщения. Результатом обобщения является задача с нелинейной целевой функцией (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., Богданова Е. Л., Соловейчик К. А.), открытая задача (Абу-Абед Ф.Н., Медведева О. А., Иванова А. В., Муха В. С.), задача с матрицей затрат, элементы которой произвольного знака (Лелякова Л. В., Харитонова А. Г., Чернышова Г. Д.) задача с запретами на отдельные назначения (Эддоус М., Стэнсфилд Р., Медведева О. А.). В связи с этим задача описания эквивалентных преобразований задачи о назначениях и разработки алгоритма приведения обобщенной модели к эквивалентной форме, позволяющей использовать существующие стандартные алгоритмы решения, является актуальной.

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

Задачи исследования. Для достижения указанной цели необходимо решить следующие задачи:

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

---