Смекни!
smekni.com

Экономико-математический практикум (стр. 8 из 9)

Отрицательных оценок нет. Назначение Х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

П.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