ОПТИМАЛЬНОЕ РАСПРЕДЕЛЕНИЕ ПРОЕКТОВ МЕЖДУ ИСПОЛНИТЕЛЯМИ (ЗАДАЧА О НАЗНАЧЕНИЯХ)

Методические указания по решению задачи

В общем виде задача о назначениях формулируется следующим образом.

Пусть имеются п работ и п кандидатов для их выполнения. Назначению i-го кандидата (i=1, ..., п) на j-ю работу (j=1, .... п) соответствует определенная эффективность (прибыль, производительность) или затраты какого-либо ресурса c_ij . Требуется найти такие назначения кандидатов на все работы, которые обеспечат наибольшую эффективность, т. е. минимум суммарных затрат или максимум прибыли (производительности). При этом каждого кандидата можно назначить только на одну должность и каждая работа может быть выполнена только одним кандидатом.

Математическая постановка задачи имеет вид:

где х _ij — искомая переменная;

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

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

Использование Венгерского метода (алгоритма) для решения задачи оптимального распределения заданий между исполнителями сводится к последовательному выполнению определенных этапов:

1. В каждой строке матрицы назначения находим минимальный элемент и вычитаем его из всех элементов строки.

2. В каждом столбце полученной матрицы находим минимальный элемент и вычитаем его из всех элементов столбца.

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

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

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

6. Если каждая строка и каждый столбец матрицы содержит ровно один отмеченный ноль, то получено оптимальное решение. Каждый из отмеченных нулей прикрепляет поставщика к потребителю. В противном случаем проводим минимальное количество пересекающихся вертикальных и горизонтальных прямых через все нули. Среди не зачеркнутых этими прямыми чисел ищем минимум. Этот минимум вычитаем их всех не зачеркнутых чисел и прибавляем ко всем числам на пересечении прямых. К полученной матрице применяем вышеприведенный алгоритм, начиная с шага 3.

Пример

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

Матрица времени приведена ниже. В i- ой строке j-го столбца матрицы указано время на выполнение i-м ученым j-го проекта.

Требуется выбрать научного руководителя для выполнения каждого проекта так, чтобы суммарное время выполнения всех проектов было минимальным.

Решени е

Находим минимальный элемент в каждой строке матрицы и вычитаем его из всех элементов строки.

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

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

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

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

Находим минимальный элемент среди не зачеркнутых этими прямыми чисел: min (4, 13, 7, 1, 11, 8) = 1. Вычитаем найденный минимум из всех не зачеркнутых чисел и прибавляем его ко всем числам, стоящими на пересечении прямых. Получим матрицу:

К полученной матрице применяем вышеописанный алгоритм.

Теперь в каждой строке и в каждом столбце матрицы находится ровно один отмеченный ноль. Получено оптимальное распределение: за первым ученым закрепляем четвертый проект; за вторым — первый; за третьим — второй; за четвертым — третий.

Для того, чтобы найти суммарное распределение (суммарную длительность выполнения проектов), нужно сложить числа, расположенные в исходной матрице на месте отмеченных нулей. Получим: 5 + 3 + 8 + 6 = 22.

Стоит отметить, что задача о назначениях может решаться и на максимум (чтобы суммарное распределение было максимальным). В этом случае каждый элемент матрицы умножается на -1, складывается с максимальным элементом и к полученной матрице применяется вышеописанный алгоритм.

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

Условие задачи. Институт получил гранты на выполнение исследовательских проектов. В качестве научных руководителей проектов рассматриваются кандидатуры ученых, обладающих соответствующим опытом и способностями. Один ученый может быть руководителем только одного проекта.

а) Каждый ученый оценил время, необходимое ему для реализации проекта в месяцах. Матрицы времени приведены ниже. В i- ой строке j-го столбца матрицы указано время на выполнение i-м ученым j-го проекта. Требуется выбрать научного руководителя для выполнения каждого проекта так, чтобы суммарное время выполнения всех проектов было минимальным.

б) Каждый ученый оценил число объектов, которые будут модернизированы в результате реализации предлагаемых проектов. Матрицы числа объектов приведены ниже. В i- ой строке j-ого столбца матрицы указано число объектов, предложенных i-м ученым по j-му проекту. Требуется выбрать научного руководителя для выполнения каждого проекта так, чтобы суммарное число объектов по всем проектам было максимальным.

Исходные данные по вариантам

Вариант 1				Вариант 2				Вариант 3				Вариант 4
11	21	9	8	6	17	3	4	8	8	11	22	17	20	11	16
12	14	7	12	8	13	3	8	6	12	12	15	16	27	13	12
9	19	10	10	7	10	1	8	9	10	9	20	18	23	13	16
13	17	9	12	4	15	4	6	8	12	13	18	14	25	14	14



Вариант 5				Вариант 6				Вариант 7				Вариант 8
6	19	11	13	4	5	8	9	10	20	13	6	19	10	11	14
10	15	11	15	9	6	3	2	8	13	14	10	22	14	13	19
10	12	9	14	2	4	2	7	11	18	11	8	23	12	12	12
8	17	12	11	10	6	5	5	10	16	15	10	21	14	15	20

Вариант 9				Вариант 10				Вариант 11				Вариант 12
15	13	17	4	4	5	7	2	17	14	12	8	22	19	21	12
17	13	13	8	7	6	8	4	16	11	10	8	17	20	18	12
16	11	10	8	6	7	13	3	13	16	13	6	16	17	15	8
13	14	15	6	12	3	10	4	15	18	12	4	14	21	17	10

Вариант 13				Вариант 14				Вариант 15				Вариант 16
11	21	9	8	6	17	3	4	8	8	11	22	17	20	11	16
12	14	7	12	8	13	3	8	6	12	12	15	16	27	13	12
9	19	10	10	7	10	1	8	9	10	9	20	18	23	13	16
13	17	9	12	4	15	4	6	8	12	13	18	14	25	14	14

Вариант 17				Вариант 18				Вариант 19				Вариант 20
6	19	11	13	4	5	8	9	10	20	13	6	19	10	11	14
10	15	11	15	9	6	3	2	8	13	14	10	22	14	13	19
10	12	9	14	2	4	2	7	11	18	11	8	23	12	12	12
8	17	12	11	10	6	5	5	10	16	15	10	21	14	15	20

Вариант 21				Вариант 22				Вариант 23				Вариант 24
15	13	17	4	4	5	7	2	17	14	12	8	22	19	21	12
17	13	13	8	7	6	8	4	16	11	10	8	17	20	18	12
16	11	10	8	6	7	13	3	13	16	13	6	16	17	15	8
13	14	15	6	12	3	10	4	15	18	12	4	14	21	17	10

Вариант 25				Вариант 26				Вариант 27				Вариант 28
11	21	9	8	6	17	3	4	8	8	11	22	17	20	11	16
12	14	7	12	8	13	3	8	6	12	12	15	16	27	13	12
9	19	10	10	7	10	1	8	9	10	9	20	18	23	13	16
13	17	9	12	4	15	4	6	8	12	13	18	14	25	14	14

Вариант 29				Вариант 30
11	21	9	8	6	17	3	4
12	14	7	12	8	13	3	8
9	19	10	10	7	10	1	8
13	17	9	12	4	15	4	6

Список использованной литературы

1. Глухов, В.В. Математические модели менеджмента [Электронный ресурс] : учебное пособие / В.В. Глухов, М.Д. Медников. — Электрон. дан. — Санкт-Петербург : Лань, 2017. — 500 с. — Режим доступа: https://e.lanbook.com/book/96247.

2. Федосеев В.В. Математическое моделирование в экономике и социологии труда. Методы, модели, задачи: учеб. пособие / В.В. Федосеев. — М.: ЮНИТИ-ДАНА, 2012. - 167 с.

3. Шелехова, Л.В. Методы оптимальных решений [Электронный ресурс] : учебное пособие / Л.В. Шелехова. — Электрон. дан. — Санкт-Петербург : Лань, 2017. — 304 с. — Режим доступа: https://e.lanbook.com/book/91895.

ПРИЛОЖЕНИЕ А

МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ
РОССИЙСКОЙ ФЕДЕРАЦИИ

федеральное государственное автономное образовательное
учреждение высшего образования «КРЫМСКИЙ федеральный универCитет им. В.И. вернадского»

институт экономики и управления
(структурное подразделение)

КАФЕДРА МЕНЕДЖМЕНТА

КОНТРОЛЬНАЯ РАБОТА ПО ДИСЦИПЛИНЕ
"АДМИНИСТРАТИВНЫЙ МЕНЕДЖМЕНТ"

Вариант__

Выполнил:

обучающийся группы__________

ФИО________________________

Проверила:

ст. преподаватель кафедры менеджмента