В этой статье будет решена задача о назначениях из области дискретной математики. Статья разделена на две части, в первой будет приведена вся теория, а во второй уже программа и ее частичная реализация на языке C# с приведением результатов работы приложения.
1 Разработка математического обеспечения
1.1 Описание задачи
В данном проекте требуется на программном уровне реализовать операций композиции для бинарных нечетких отношений двух типов:
- Max-min – максиминная композиция;
- Min-max – минимаксная композиция.
Данные операции основываются на дискретной математике. Сама задача складывается из нескольких последовательных действий:
- Изучение нечетких отношений;
- Составление композиции для бинарных нечетких отношений;
- Разработка алгоритма составления композиции;
- Программная реализации полученного алгоритма;
- Реализация графического интерфейса приложения;
- Тестирование программы;
- Написание пояснительной записки.
С практической точки зрения данные операции можно применить при решении достаточно распространённой задачи – задачи о назначениях. Представим себе задание: нужно очень эффективным способом реализовать некоторый относительно большой проект. Для создания этого проекта была отобрана команда прекрасно разбирающихся в различных областях, первоклассных разработчиков. И так уж сложилось, что остались некоторые сведения (накопленная статистика) о степени эффективности владения технологиями для каждого из разработчиков. Разработчиков в команде столько, сколько и технологий будет использовано в проекте. Самим заданием является поиск способа как самым эффективным способом задействовать наибольшее количество технологий, назначив каждому разработчику свою задачу. То есть принимая во внимание личные способности каждого из разработчиков, оптимально распределить между ними области ответственности за используемые технологии. Способов как решить эту задачу достаточно много. Одним из самых популярных способов решить данную задачу является Венгерский алгоритм.
Тем не менее задача до сих пор актуальна при распределении сотрудников по должностям. И в случае, когда сотрудников, должностей и критериев очень много, обычные методы могут оказаться очень трудоемкими. На данный момент для решения такой задачи возможно использование генетического алгоритма и его модификации (интерактивный генетический алгоритм). То есть возникает достаточно сложная многокритериальная задача поиска оптимальной альтернативы, которую можно разбить на две задачи. Если вакансия одна, а претендентов много, то для лица принимающего решения выбор эффективного распределения будет сделан с помощью использование метода многокритериальный выбора альтернатив с использованием правил нечеткого вывода.
В данном проекте программная реализация операции композиции для бинарных нечетких отношений будет наложена на решение задачи о назначениях в случае нескольких должностей и нескольких вакансий.
1.2 Математическая модель композиции нечетких бинарных отношений
Большинство алгоритмов в нашей жизни основывается на математике. Одним из важных разделов математики является дискретная математика, изучающая логику, графы, множества и так далее. Задание данного проекта основывается на понятиях дискретной математики, ее функциях и методах.
Начать следует с определения нечеткого множества. Теория нечетких множеств представляет собой обобщение и переосмысление важнейших направлений классической математики. У ее истоков лежат идеи и достижения многозначной логики, которая указала на возможности перехода от двух к произвольному числу значений истинности и поставила проблему оперирования понятиями с изменяющимся содержанием; теории вероятностей, которая, породив большое количество различных способов статистической обработки экспериментальных данных, открыла пути определения и интерпретации функции принадлежности; дискретной математики, которая предложила инструмент для построения моделей многомерных и многоуровневых систем, удобный при решении практических задач.
Подход к формализации понятия нечеткого множества состоит в обобщении понятия принадлежности. Пусть существует четкое множество A = {1, 3, 5, 7, В, Л}. И существует функция принадлежности µ, которая показывает нам, принадлежит выбранный элемент какому-нибудь множеству или нет. Функция принадлежности четвертого элемента равно µ = 1, так как 7 принадлежит множеству А. Если же взять функцию принадлежности элемента, не принадлежащего множеству А, например, элемент равный 2, то µ = 0 (рисунок 1).
Нечеткие множества есть естественное обобщение обычных множеств, когда мы отказываемся от бинарного характера функции принадлежности и предполагаем, что она может принимать любые значения на отрезке [0,1]. Таким образом элемент, принадлежащий нечёткому множеству, описывается с помощью пары значений: самого элемента и его степени принадлежности. Например, пусть А теперь нечеткое множество, а µ дала определенные значения, тогда А = {<1; 0.5>, <3; 0.7>, <5; 1>, <7; 0.25>, <В; 0.9>, <Л; 0.4>}.
Следующим понятием необходимым для реализации задания проекта является понятие нечеткого отношения. Теория нечетких отношений находит также приложение в задачах, в которых традиционно применяется теория обычных (четких) отношений. Как правило, аппарат теории четких отношений используется при качественном анализе взаимосвязей между объектами исследуемой системы, когда связи носят дихотомический характер и могут быть проинтерпретированы в терминах "связь присутствует", "связь отсутствует", либо, когда методы количественного анализа взаимосвязей по каким-либо причинам неприменимы и взаимосвязи искусственно приводятся к дихотомическому виду. Например, когда величина связи между объектами принимает значения из ранговой шкалы, выбор порога на силу связи позволяет преобразовать связь к требуемому виду. Однако, подобный подход, позволяя проводить качественный анализ систем, приводит к потере информации о силе связей между объектами либо требует проведения вычислений при разных порогах на силу связей. Этого недостатка лишены методы анализа данных, основанные на теории нечетких отношений, которые позволяют проводить качественный анализ систем с учетом различия в силе связей между объектами системы.
Четкое отношение представляет из себя подмножество декартового произведения двух множеств. Например, А = {1, 2, 4} и В = {3, Д} два четких множества, а R это отношение «присутствует четное число», тогда R = {(2, 3), (2, Д), (4, 3), (4, Д)}. Нечетким же отношением считается также подмножество декартового произведения двух четких множеств, но с функцией принадлежности µ. Если условие оставить тем же, но представить, что R это нечеткое отношение, тогда R = {<(2, 3); 0,5>, <(2, Д); 0,1>, <(4, 3); 0,7>, <(4, Д); 0,8>}.
Композиции бинарных нечетких отношений основываются на двух нечетких отношениях, заданных на трех множествах. Пусть R и S два бинарных нечеткие множества, где R задано на X×Y, а S задано на Y×Z. Тогда композицией двух бинарных нечетких отношений называют третье бинарное нечеткое отношение, заданное на X×Z, где функция принадлежности задается с помощью формул. Существует множество формул для нахождения значения принадлежности композиций бинарных нечетких отношений (рисунок 2). Самые распространённые это максиминная и max-prod композиции.
При наложении двух необходимых по варианту композиций на задачу о назначениях: максиминная композиция дает информацию о степени соответствия кандидата его вакансии основываясь на требуемых параметрах, а минимаксная помогает решать задачи с минимаксным критерием. Такой критерий возникает, когда необходимо минимизировать максимальное из значений потерь [18].
Множество X будет включать в себя те профессии, которые необходимы на предприятии в данный момент. Множество Z фамилии людей, которые хотят устроиться на работу по одной из профессий. А множество Y включает в себя набор характеристик, которые необходимы для той или иной вакансии, а также на которые тестировались кандидаты. Таким образом создается две матрица, пересечении строк и столбцов в которых дают значение функции принадлежности. Таблица 1 и таблица 2 демонстрируют такой пример.
Далее применив формулы для нахождения значений функций принадлежности получится еще одна матрица, включающая в себя фамилии кандидатов, вакансии, а пересечением строк и столбцов будут значения функции. Чем значение функции больше, тем кандидат лучше подходит на данную вакансию. Таблица 3 показывает конечные значения на приведенном примере.
Работа данного алгоритма изображена на рисунке 3 в виде двух графов. Изначально дано три множества представленными вершинами графа, где Ф – это фамилии, Х – это выбранные характеристики, В – это вакансии, на которые устраиваются люди. Вес ребер обозначает значение функции принадлежности бинарного нечеткого отношения. При выполнении максиминной композиции, образуется граф с из двух множеств, а вес ребер уже показывает полученной по формуле композиции значение.
Таким образом можно оценить каждого из кандидатов по персональным характеристикам, а также их пригодность для какой-либо из вакансий. Все это позволяют сделать композиции бинарных нечетких отношений.
1.3 Алгоритм математического функционирования
Математический алгоритм составления минимаксной и максиминной композиций очень прост. Имея две необходимые нам таблицы со значениями R и S, необходимо выделить строку одной из таблиц, например, R, брать в ней поочередно каждый из элементов и сравнивать с точки зрения максимума или минимуму, в зависимости от поставленной задачи, с элементами, стоящими в тех же столбцах всех строк второй таблицы S.
Первой итерацией внутреннего цикла считается то, когда были получены результаты сравнения отдельно взятых элементов строки таблицы R с элементами строки таблицы S, столбцы всех элементов должны совпадать соответственно. Затем ищется максимальное или минимальное значение из полученных и записывается в конечную таблицу как первый элемент. Затем в первой таблице остается та же самая строка, а во второй берется следующая и так далее, пока не закончатся строки второй таблицы.
Итерацией внешнего цикла считается то, когда заканчивается внутренний цикл, после чего меняется строка первой таблицы, выходом из этого цикла является окончание строк первой таблицы. В конечном результате получится заполненная таблица со значениями полученные от композиции бинарных нечетких отношений (рисунок 4).
Во второй части цикла статей будет приведена программа и ее частичная реализация на языке C# с приведением результатов работы приложения.
Подписывайтесь на наши источники, чтобы не пропустить:
https://t.me/podcust_rabot9g
https://www.youtube.com/@Rabot9gi
https://vk.com/rabot9gi
