Отрицательных оценок нет. Назначение Х2 оптимально, обозначим его через Х2*.
Суммарная эффективность, отвечающая полученному варианту назначения равна:
условных единиц эффективностиНазначение Х2 оптимально. Итак, оптимальный вариант назначения имеет вид:
х1,4=1 (первая невеста выберет четвертого жениха),
х2,7=1 (вторая невеста выберет седьмого жениха),
х3,5=1 (третья невеста выбрала пятого жениха),
х4,3=1 (четвертая невеста выбрала третьего жениха),
х5,8=1 (пятая невеста выберет восьмого жениха),
х6,2=1 (шестая невеста выберет второго жениха),
х7,1=1 (седьмая невеста выберет первого жениха),
х8,6=1 (восьмая невеста выберет шестого жениха).
При этом варианте назначений получим максимальную эффективность
единиц эффективности.2. Венгерский метод.
Предварительный этап. Исходная матрица C:
31 | 13 | 11 | 41 | 10 | 17 | 38 | 25 |
35 | 20 | 26 | 8 | 17 | 14 | 38 | 36 |
12 | 37 | 38 | 49 | 38 | 22 | 10 | 13 |
28 | 21 | 48 | 43 | 44 | 29 | 26 | 12 |
37 | 22 | 39 | 46 | 26 | 20 | 44 | 49 |
22 | 49 | 19 | 2 | 20 | 30 | 45 | 16 |
45 | 27 | 5 | 21 | 30 | 21 | 34 | 23 |
43 | 33 | 20 | 29 | 3 | 46 | 33 | 21 |
Шаг 1. Обозначим через
наибольший элемент столбца матрицы (r1=45, r2=49, r3=48, r4=49, r5=44, r6=46, r7=45, r8=49). Каждый элемент -го столбца вычтем из , результаты вычислений будем помещать на место вычитаемого. Аналогичные преобразования проводим в остальных столбцах. Получим неотрицательную матрицу , в каждом столбце которой есть хотя бы один нуль.C1 = | 14 | 36 | 37 | 8 | 34 | 29 | 7 | 24 |
10 | 29 | 22 | 41 | 27 | 32 | 7 | 13 | |
33 | 12 | 10 | 0 | 6 | 24 | 35 | 36 | |
17 | 28 | 0 | 6 | 0 | 17 | 19 | 37 | |
8 | 27 | 9 | 3 | 18 | 26 | 1 | 0 | |
23 | 0 | 29 | 47 | 24 | 16 | 0 | 30 | |
0 | 22 | 43 | 28 | 14 | 25 | 11 | 23 | |
2 | 16 | 28 | 20 | 41 | 0 | 12 | 25 |
Шаг 2. Преобразуем матрицу
. Для этого обозначим через минимальный элемент строки , который последовательно вычтем из элементов той же строки, результаты поместим на место уменьшаемого. Наименьший элемент первой строки матрицы равен 7. Проведем вычисления для элементов первой строки: (d11=7, d12=29, d13=30, d14=1, d15=27, d16=22, d17=0, d18=17). Такие же вычисления проведем для остальных строк, получим неотрицательную матрицу , в каждом столбце и каждой строке которой есть хотя бы один нуль.D= | 7 | 29 | 30 | 1 | 27 | 22 | 0* | 17 |
3 | 22 | 15 | 34 | 20 | 25 | 0 | 6 | |
33 | 12 | 10 | 0* | 6 | 24 | 35 | 36 | |
17 | 28 | 0* | 6 | 0 | 17 | 19 | 37 | |
8 | 27 | 9 | 3 | 18 | 26 | 1 | 0* | |
23 | 0* | 29 | 47 | 24 | 16 | 0 | 30 | |
0* | 22 | 43 | 28 | 14 | 25 | 11 | 23 | |
2 | 16 | 28 | 20 | 41 | 0* | 12 | 25 |
Основной этап. После второго шага предварительного этапа получим неотрицательную матрицу
, эквивалентную матрице эффективностей :П.1. В первом столбце матрицы
отметим звездочкой 0*7,1 ,во втором столбце – 06,2 , в третьем столбце – 04,3, в четвертом столбце – 0*3,4 , в шестом столбце – 08,6, в седьмом столбце – 01,7 , в восьмом столбце – 05,8. Нули в пятом столбце – 04,5 нельзя отметить звездочкой, так как они лежат в строке, в которой уже есть нуль со звездочкой – 04,3,. Число звездочек равно семи, что меньше размерности матрицы (8), переходим к п.2.D= | + | + | + | + | + | + | + | |
7 | 29 | 30 | 1 | 27 | 22 | 0* | 17 | |
3 | 22 | 15 | 34 | 20 | 25 | 0’ | 6 | |
33 | 12 | 10 | 0* | 6 | 24 | 35 | 36 | |
17 | 28 | 0* | 6 | 0’ | 17 | 19 | 37 | + |
8 | 27 | 9 | 3 | 18 | 26 | 1 | 0* | |
23 | 0* | 29 | 47 | 24 | 16 | 0’ | 30 | |
0* | 22 | 43 | 28 | 14 | 25 | 11 | 23 | |
2 | 16 | 28 | 20 | 41 | 0* | 12 | 25 |
П.2. Помечаем знаком «+» сверху столбцы: 1, 2, 3, 4,6, 7,8 и считаем эти столбцы занятыми. Незанятый нуль находитсяв четвертой строке пятого столбца 04,5 , во второй строке и шестой строках седьмого столбца. Помечаем их штрихом 0'4,5 , 0'2,7 , 0'6,7. Переходим к пункту 3.
П.3. Столбец 3 считаем незанятым и знак «+» сверху снимаем (обводим в рамку), а четвертую строку объявляем занятой и помечаем знаком «+» справа. Возвращаемся к третьему абзацу п.2.
П.2. Незанятых нулей нет, переходим к п.5.
П.5. Среди незанятых элементов находим минимальный, который обозначим через
, ε=d3,5=6. Преобразуем матрицу : незанятые элементы уменьшим на 6; дважды занятые увеличим на 6; остальные элементы оставим без изменения. Получим матрицу , в которой имеется один незанятый нуль, переходим к четвертому абзацу п.2.+ | + | + | + | + | + | + | ||
D1= | 7 | 29 | 24 | 1 | 21 | 22 | 0* | 17 |
3 | 22 | 9 | 34 | 14 | 25 | 0’ | 6 | + |
33 | 12 | 4 | 0* | 0’ | 24 | 35 | 36 | |
23 | 34 | 0* | 12 | 0’ | 23 | 25 | 43 | + |
8 | 27 | 3 | 3 | 12 | 26 | 1 | 0* | |
23 | 0* | 23 | 47 | 18 | 16 | 0’ | 30 | |
0* | 22 | 37 | 28 | 8 | 25 | 11 | 23 | |
2 | 16 | 22 | 20 | 35 | 0* | 12 | 25 |