Решение полученной матрицы венгерским методом на максимум

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

Матрица эффективности

Претендент

Должность

директор маркетолог экономист бухгалтер юрист IT-специалист Наталья 0,61 0,59 0,705 0,679 0,593 0,594 Екатерина 0,48 0,78 0,637 0,694 0,578 0,564 Кристина 0,53 0,586 0,414 0,423 0,531 0,718 Виктория 0,65 0,701 0,679 0,494 0,641 0,533 Валерия 0,477 0,524 0,638 0,68 0,672 0,533 Елизавета 0,555 0,72 0,438 0,738 0,562 0,44

 

Решим полученную матрицу венгерским методом на максимум. Для упрощения вычислений умножим все числа матрицы на 100 и округлим до целых.

Матрица имеет вид:

61	59	71	68	59	59
48	78	64	69	58	56
53	59	41	42	53	72
65	70	68	49	64	53
48	52	64	68	67	53
56	72	44	74	56	44

 

Модифицируем матрицу умножением всех элементов на (-1) и затем сложением их с максимальным элементом матрицы «78» так, чтобы матрица не содержала бы отрицательных элементов:

17	19	7	10	19	19
30	0	14	9	20	22
25	19	37	36	25	6
13	8	10	29	14	25
30	26	14	10	11	25
22	6	34	4	22	34

 

Этап 1.

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

						min
10	12	0	3	12	12	7
30	0	14	9	20	22	0
19	13	31	30	19	0	6
5	0	2	21	6	17	8
20	16	4	0	1	15	10
18	2	30	0	18	30	4

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

 

	5	12	0	3	11	12
	25	0	14	9	19	22
	14	13	31	30	18	0
	0	0	2	21	5	17
	15	16	4	0	0	15
	13	2	30	0	17	30
min	5	0	0	0	1	0

После вычитания минимальных элементов получаем полностью редуцированную матрицу.

2. Метод проб и ошибок. Методом проб и ошибок проводим поиск, для которого все назначения имеют нулевую стоимость.

В итоге получаем следующую матрицу:

5	12	0	3	11	12
25	0	14	9	19	22
14	13	31	30	18	0
0	0	2	21	5	17
15	16	4	0	0	15
13	2	30	0	17	30

Поскольку расположение нулевых элементов в матрице не позволяет образовать систему из 6-х независимых нулей (в матрице их только 2), то решение недопустимое.

3. Проводим модификацию матрицы. Вычеркиваем строки и столбцы с возможно большим количеством нулевых элементов:

столбец 2 и столбец 4:

5	12	0	3	11	12
25	0	14	9	19	22
14	13	31	30	18	0
0	0	2	21	5	17
15	16	4	0	0	15
13	2	30	0	17	30

Получаем сокращенную матрицу (элементы выделены):

5	0	3	11	12
25	14	9	19	22
14	31	30	18	0
0	2	21	5	17
13	30	0	17	30

Минимальный элемент сокращенной матрицы = 0 вычитаем из всех элементов сокращенной матрицы.

5	0	3	11	12
25	14	9	19	22
14	31	30	18	0
0	2	21	5	17
13	30	0	17	30

Затем складываем минимальный элемент с элементами, расположенными на пересечениях вычеркнутых строк и столбцов:

5	12	0	3	11	12
25	0	14	9	19	22
14	13	31	30	18	0
0	0	2	21	5	17
15	16	4	0	0	15
13	2	30	0	17	30

Этап 2.

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

						min
5	12	0	3	11	12	0
25	0	14	9	19	22	0
14	13	31	30	18	0	0
0	0	2	21	5	17	0
15	16	4	0	0	15	0
13	2	30	0	17	30	0

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

	5	12	0	3	11	12
	25	0	14	9	19	22
	14	13	31	30	18	0
	0	0	2	21	5	17
	15	16	4	0	0	15
	13	2	30	0	17	30
min	0	0	0	0	0	0

После вычитания минимальных элементов получаем полностью редуцированную матрицу.

2. Метод проб и ошибок. Методом проб и ошибок проводим поиск допустимого решения, для которого все назначения имеют нулевую стоимость.

В итоге получаем следующую матрицу:

5	12	0	3	11	12
25	0	14	9	19	22
14	13	31	30	18	0
0	0	2	21	5	17
15	16	4	0	0	15
13	2	30	0	17	30

 

Поскольку расположение нулевых элементов в матрице не позволяет образовать систему из 6-х независимых нулей, то решение недопустимое.

3. Проводим модификацию матрицы. Вычеркиваем строки и столбцы с возможно большим количеством нулевых элементов:

Получаем сокращенную матрицу (элементы выделены):

 

 

5	12	0	3	11	12
25	0	14	9	19	22
14	13	31	30	18	0
0	0	2	21	5	17
15	16	4	0	0	15
13	2	30	0	17	30

Минимальный элемент сокращенной матрицы = 13 вычитаем из всех элементов сокращенной матрицы.

12	1	6
1	18	5
0	17	4

Затем складываем минимальный элемент с элементами, расположенными на пересечениях вычеркнутых строк и столбцов:

5	25	0	16	24	25
12	0	1	9	6	22
1	13	18	30	5	0
0	13	2	34	18	30
15	29	4	13	13	28
0	2	17	0	4	30