ИСПОЛЬЗОВАНИЕ НЕЧЁТКОЙ ЛОГИКИ В ЗАДАЧЕ О НАЗНАЧЕНИЯХ

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

В базовом представлении задачи у нас присутствуют: 1) множество исполнителей; 2) множество задач; 3) переменные, которые несут информацию о назначении работ определенным людям. Переменные, отвечающие за назначение, могут быть равны либо нулю, тогда работа не назначена определенному человеку, либо единице, тогда работа назначена определенному человеку. Таким образом, можно заметить, что в задаче используется чёткая логика.

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

Из математической логики известно, что нечёткое бинарное отношение – это выражение вида:

 , где

 - набор из двух элементов, причем , ,

 – функция принадлежности данного нечёткого отношения, X₁ и X₂ – множества, на которых задано наше отношение.

Функция принадлежности – это функция, принимающая значения в некотором вполне упорядоченном множестве M (например, М = [0,1]) [2, с. 9].

Основой нашего алгоритма являются композиции нечётких бинарных отношений, а именно: (max-min) композиция и (min - max) композиция.

(max-min) композиция – это нечёткое бинарное отношение, которое задано на декартовом произведении множеств X и Z и у которого функция принадлежности определяется выражением вида:

, где

нечёткое отношение R определено на декартовом произведении множеств X и Y, а нечёткое отношение Q определено на декартовом произведении множеств Y и Z.

(min-max) композиция – это нечёткое бинарное отношение, которое задано на декартовом произведении множеств X и Z и у которого функция принадлежности определяется выражением вида:

, где

нечёткое отношение R определено на декартовом произведении множеств X и Y, а нечёткое отношение Q определено на декартовом произведении множеств Y и Z.

Итак, если рассматривать задачу о назначениях, то (max-min)-композиция, предоставляет количественную оценку соответствия кандидата вакансии, а (min-max)-композиция, наоборот, позволяет определить несоответствие кандидата вакансии.

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

Выполнив композиции двух данных нечётких бинарных отношений, а именно (max-min) и (min-max), мы сможем с высокой степенью вероятности сказать, для каких работ наиболее пригодны определённые работники, т.е. в матричном виде это можно представить следующим образом: матрица размерности n*n, где строки – работники, а столбцы – работы, а пересечение строк и столбцов – это значение функции принадлежности для соответствующей работы и работника. Чтобы найти по этой таблице наиболее выгодное соответствие работников и работ, существует два метода решения данной задачи – это метод Мака и Венгерский алгоритм. Оба метода основаны на том факте, что положения оптимального выбора не меняются, если к каждому элементу некоторой строки или столбца добавить одно и то же значение или вычесть его [1, с. 96].

В данной работе был выбран Венгерский алгоритм. Первое, что необходимо сделать – это свести задачу нахождения максимальных значений к диаметрально противоположной, т.е. к задаче нахождения минимальных значений. Это достигается следующим путем: 1) из всех значений таблицы выбирается максимальное, 2) каждое значение таблицы заменяется разностью максимального элемента и исходного.

Второй этап - это распределение всех подлежащих назначению единиц в клетки с нулевой стоимостью, а именно если мы имеем некоторую функцию и необходимо найти её минимальное значение, то неважно на каком уровне располагается вся функция, т.е. общее понижение не изменяет формы поверхности. Итак, на данном этапе нужно: 1) В каждой строке таблицы найти наименьший элемент и вычесть его из всех элементов данной строки, 2) Повторить ту же процедуру для столбцов, 3) Строим двудольный граф по полученной таблицы, где нули, там будут ребра, где не нули – ребер нет.

Третий этап – поиск наибольшего паросочетнания в графе среди максимальных методом увеличивающихся цепей. Максимальное паросочетание не является наибольшим, если присутствуют увеличивающиеся цепи, т.е.: 1) Концы цепи – экспонированные вершины (неучавствующие в паросочетании), 2) Кол-во ребер в цепи – нечетно; 3) Проход на цепи от не принадлежащих вершин паросочетанию к принадлежащим.

Четвертый этап – альфа-преобразование. Нужно по вершинам, принадлежащие множествам X_m и Y_m, т.е. множествам экспонированных вершин, полученный после выбора максимального паросчетания, нужно построить чередующуюся цепь и выделить множества X^| и Y^|. X^| - множество, соединяющее X_m и X – множество кандидатов. Кол-во ребер в цепи должно быть четным. Y^| - множество вершин, ч/з которые мы проходим, строя чередующуюся цепь. В матрице выбираем строки X^| и Y \ Y^| столбцы. Выбираем из пересечений минимальный (это и есть альфа-преобразование). И к строкам, которые мы выбрали, прибавляем данный минимальный элемент, но вычитаем из столбцов, которые не брали.

Пятый этап – повторить 3 и 4 этап, если остались экспонированные вершины. Если же таких вершин больше нет, то получено совершенное паросочетание, являющееся искомым решением.

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

После вывода решения задачи о назначении, расширенной на нечёткую логику, было принято решение практической проверки алгоритма. Из числа студентов 6 факультета Самарского университета было выбрано 5 человек. Для упрощения работы с данными была написана программа.

Рисунок 1. Начальное окно работы программы

Рисунок 2. Таблица работников и оценка их навыков

Рисунок 3. Таблица работ и уровень навыков, необходимых для их выполнения.

Рисунок 4. Таблица соответствия работников и работ

Рисунок 5. Оптимальный выбор назначения работников на работы

Список литературы:

1. Банди Б.Д. Основы линейного программирования: Издательство «Радио и связь». Редакция переводной литературы, 1989 – 145с.
2. Круглов В.В., Дли М.И., Р.Ю. Голунов Нечеткая логика и искусственные нейронные сети: ФИЗМАТЛИТ, 2001 – 201с.