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

Размещено на http://www.allbest.ru/

УДК 519.854.64

Омский филиал ФГБУН Института математики

им. С.Л. Соболева СОРАН

О РЕШЕНИИ ОДНОЙ ЗАДАЧИ ПРОЕКТИРОВАНИЯ МАЛЫХ ГРУПП С ИСПОЛЬЗОВАНИЕМ ДИСКРЕТНОЙ ОПТИМИЗАЦИИ

А.А. Колоколов

И.А. Циглер

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

При решении задач подобного типа применимы модели и методы дискретной оптимизации, в частности, аппарат целочисленного линейного программирования (ЦЛП). Важными аспектами исследования рассматриваемых задач являются изучение их структуры и сложности, разработка алгоритмов точного и приближенного решения, анализ этих алгоритмов и другие вопросы [1-9]. Во многих случаях задача управления персоналом сводится к задаче о назначениях и некоторым её обобщениям[1, 2, 4-6, 8]. профессиональный программирование хореографический

2. Постановка задачи

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

Определим двудольный граф G с множествами вершин = {,…,} и

= {,…,}, и множеством ребер E ={(,) :?, ?}, . Вершины из множества отвечают претендентам 1-го типа, а вершины множества - претендентам 2-го типа. Ребра соответствуют наличию совместимости претендентов разных типов.

Вершины ?, ? имеют веса и соответственно, , указывающие на степень профессиональной подготовки претендента. Каждому ребру назначен вес , ?, ?, отвечающий степени совместимости пары (,). Количество пар формируемой группы равно заданному числу p. Обозначим символом б нижнюю границу указанной совместимости.

Введем переменные:

,

,

,

,

Модель ЦЛП выглядит следующим образом:

,

при ограничениях:

,

,

,

Целевая функция заключается в максимизации общего уровня профессиональной подготовки группы (суммируются веса вершин претендентов 1-го и 2-го типов). Ограничения (2) и (3) гарантируют, что каждый претендент 1-го типа может состоять в паре только с одним претендентом 2-го типа, и наоборот. Условие (4) означает, что необходимо сформировать группу ровно из р пар, а неравенство (5) ограничивает снизу суммарную степень совместимости членов группы.

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

Таким образом, математическая модель модифицируется и примет вид:

,

при условиях (2)-(4), (6) и ограничении:

Здесь неравенство (7) указывает на ограниченность снизу общего уровня профессиональной подготовки группы.

Можно также рассматривать двухкритериальную постановку задачи, математическая модель которой имеет следующий вид:

,

,

при ограничениях (2)-(4), (6).

3. Вычислительный эксперимент

Нами решались задачи для хореографической группы из 15 претендентов, среди которых 8 юношей и 7 девушек. Требовалось найти 3 пары, состоящие из претендентов с максимальным суммарным уровнем профессиональной подготовки. Анализ результатов исследования для выявления степени совместимости пар показал, что группа претендентов достаточно неоднородна в плане совместимости претендентов разных типов. Задачи решались с использованием пакета прикладных программ GAMS на основе модельных данных, подготовленных нами с целью апробации предложенной математической модели.

Степень совместимости пар(параметр ) варьировалась от 0 до 15. Достаточно сбалансированным оказалось решение для , при котором оптимальное значение целевой функции равно 13. Полученные результаты показали, что данная модель применима для формирования малых групп, в частности хореографической направленности. Отметим также, что при уменьшении величины б, оптимальное значение целевой функции монотонно возрастает (см. рис.1).

Рис. 1. График зависимости оптимального значения целевой функции от параметра

Заключение

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

Работа выполнена при поддержке РФФИ, проект № 13-01-00862

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

1. Афанасьева, Л. Д. Исследование и решение одной задачи формирования производственных групп / Л. Д. Афанасьева, А. А. Колоколов // Вестник УГАТУ,2013. - № 5. - С. 20-25.

2. Колоколов, А. А. Разработка моделей и алгоритмов для задачи управления персоналом с учетом логических ограничений / А. А. Колоколов, Н. А. Рубанова, И. А. Циглер // Проблемы оптимизации сложных систем : Труды XI Международной Азиатской школы-семинара. - Алматы : НЦ НТИ, 2015. - Часть II. - С.746-749.

3. Колоколов, А. А. Решение задач формирования учебных групп с учетом международного фактора / А. А. Колоколов, А. А. Соловьев, И. И. Домбровская, О. А. Барауля // Проблемы оптимизации сложных систем : Труды XI Международной Азиатской школы-семинара. - Алматы : НЦ НТИ, 2015. - Часть II. - С.750-751.

4. Kolokolov, A. A. Research of Production Groups Formation Problem Subject to Logical Restrictions / A. A Kolokolov, L. D Afanasyeva // Journal of Siberian Federal University: Mathematics & Physics, 2013. - № 6 - P. 145-149.

5. Колоколов, А. А. Анализ и решение некоторых задач формирования производственных групп / А. А. Колоколов, Н. А. Рубанова // Проблемы оптимизации и экономические приложения : материалы VI международной конференции. - Омск, 2015. - 99 с.

6. Циглер, И. А. О некоторых алгоритмах решения задач формирования производственных групп с учетом логических ограничений / И. М. Истомина, И. А. Циглер // Проблемы оптимизации и экономические приложения: материалы VI международной конференции. - Омск, 2015. - 95 с.

7. Новиков, Д. А. Математические модели формирования и функционирования команд / Д. А. Новиков. - М. : Издательство физико-математической литературы. - 2008. - 186 с.

8. Burkard R.E., Dell'Amico M., Martello S. Assignment problems. - Philadelphia: SIAM, 2009. - 382 p.

9. Кисельгоф, С. Г. Обобщенные паросочетания при предпочтениях, являющихся простейшими полупорядками: стабильность и оптимальность по Парето / С. Г. Кисельгоф // Автоматика и телемеханика. - 2014. - № 6. - С. 103-114.

Аннотация

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

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

Ключевые слова: Математическое моделирование, дискретная оптимизация, целочисленное программирование, оптимизация на графах, формирование малых групп

Размещено на Allbest.ru