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

• Автор: Афанасьева, Любовь Дмитриевна
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2013
• Место защиты: Омск
• Количество страниц: 108 с. : ил.

Оглавление
Введение
Глава 1. Математические модели оптимизации для задач планирования и управления персоналом

1.1. Задачи оптимального назначения

1.2. Применение задач о покрытии, разбиения и размещения

1.3. Оптимизация на графах

1.4. Об устойчивом паросочетании

1.5. О методах решения задач

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

2.1. Проектирование групп с учетом межличностных и иерархических отношений

2.2. Образование групп с максимизацией степени комфортности отношений
2.3. Распределение специалистов но производственным сменам
Глава 3. Разработка и реализация алгоритмов
3.1. Построение и исследование алгоритмов
3.2. Описание комплекса программ
3.3. Результаты вычислительного эксперимента

Заключение
Список литературы
Приложение

Введение
Актуальность темы. Современный этап развития прикладной математики характеризуется активной разработкой и применением математических моделей и методов в планировании, проектировании, исследовании социально-экономических и технических систем [31, 75, 81]. Весьма актуальными являются проблемы управления персоналом, в частности задачи формирования производственных групп, что обусловлено появлением новых компаний, развитием торговых сетей, повышением требований к специалистам и рядом других факторов. При создании производственных групп приходится рассматривать множество вопросов, касающихся назначения на должности, качества и своевременности выполнения работ, обеспечения условий труда и т.д. Требуется также учитывать межличностные, иерархические отношения в коллективе, ресурсные и иные ограничения [3,82].
Одним из известных подходов к исследованию и решению задач формирования производственных групп является применение аппарата математического моделирования, в том числе дискретной оптимизации [17, 62,71,72]. В настоящее время можно выделить ряд направлений в указанной области:
- разработка и использование моделей целочисленного линейного программирования (ЦЛП), построенных на основе известных задач о назначениях (ЗН) и их обобщений;
применение задач о покрытии, оптимального разбиения и размещения;
- оптимизация на графах;

помощью конструктивного преобразования, которое отображает любую индивидуальную задачу первого типа в эквивалентную ей индивидуальную задачу второго тина. Такое преобразование позволяет превратить любой алгоритм решения второй задачи в соответствующий алгоритм решения первой. Будем говорить, что задача Пі сводится к П2, если существует преобразование входных данных любой индивидуальной задачи Д Є Пі во входные данные некоторой индивидуальной задачи /2 Є П2, а полученное оптимальное решение задачи Д ~ в оптимальное решение Д. Считается, что Пі полиномиально сводится к П2, если это преобразование может быть осуществлено за полиномиальное время [23,70].
Следует отметить, что 3? тесно связана с задачей Мгп¥1 в — С С (см. раздел 1.3), свойства которой могут быть использованы при исследовании задачи (2.1)—(2.5) и алгоритмов ее решения. Пусть (7 = (V, Е) - граф индивидуальной задачи (2.1)-(2.5), СД = (ІД, 7Д) ~ ераф для соответствующей задачи МіпШІБ — РС. Определим отображение Р : (7 —» 6Д, предназначенное для полиномиального сведения & к МіпУ/Ів — РС. Опишем построение графа Осі- Дуги С из множества Е преобразуются в вершины графа Д<2, а именно Д(е) Є 1Д тогда и только тогда, когда е = (і,у) Є Е и Д > 0, г € Д, причем вес вершины і?(е) равен сц. Если еі = (Д,Д), е2 = (Д,Д) Є £т и вершины ДД2ЄУ1, д,І2 Є Д такие, что (Д,Д) Є Е2, (Д,Д) Є Д3, то ребро
(іДеі),іДе2)) Є ЕЛ. Если г Є Уі, то для любых Єї = (г, Д) Є Ді и е2 = (*> Д) Є Ді ребро (Д(еі), Д(е2)) € Еа- Если у Є ЕД то для любых О = (Д,І) Є Еі, е2 = (Д,і) Є 1?і ребро (^(еі),Д(е2)) Є Е<і. Если для некоторой вершины і Є Vі величина Д > 1, то вершина і и ребра, соответствующие ей, в графе СД дублируются Д раз.
Справедлива следующая
Теорема 2.1. Задача полиномиально сводится к задаче о
независимом множестве минимального суммарного веса фиксированной мощности.
Доказательство. Воспользуемся отображением Т для