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

Отрицательных оценок нет. Назначение Х₂ оптимально, обозначим его через Х₂^*.

Суммарная эффективность, отвечающая полученному варианту назначения равна:

условных единиц эффективности

Назначение Х₂ оптимально. Итак, оптимальный вариант назначения имеет вид:

х_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. Обозначим через

наибольший элемент столбца матрицы (r₁=45, r₂=49, r₃=48, r₄=49, r₅=44, r₆=46, r₇=45, r₈=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. Проведем вычисления для элементов первой строки: (d₁₁=7, d₁₂=29, d₁₃=30, d₁₄=1, d₁₅=27, d₁₆=22, d₁₇=0, d₁₈=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 ,во втором столбце – 0_6,2 , в третьем столбце – 0_4,3, в четвертом столбце – 0^*_3,4 , в шестом столбце – 0_8,6, в седьмом столбце – 0_{1,7 ,} в восьмом столбце – 0_5,8. Нули в пятом столбце – 0_4,5 нельзя отметить звездочкой, так как они лежат в строке, в которой уже есть нуль со звездочкой – 0_4,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 и считаем эти столбцы занятыми. Незанятый нуль находитсяв четвертой строке пятого столбца 0_{4,5 ,} во второй строке и шестой строках седьмого столбца. Помечаем их штрихом 0^'_{4,5 ,} 0^'_{2,7 ,} 0'_6,7. Переходим к пункту 3.

П.3. Столбец 3 считаем незанятым и знак «+» сверху снимаем (обводим в рамку), а четвертую строку объявляем занятой и помечаем знаком «+» справа. Возвращаемся к третьему абзацу п.2.

П.2. Незанятых нулей нет, переходим к п.5.

П.5. Среди незанятых элементов находим минимальный, который обозначим через

, ε=d_3,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