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

П.2. Незанятый нуль находится в третьей строке пятого столбца 0_3,5. Помечаем штрихом 0^'_3,5. Во второй строке седьмого столбца находится нуль со штрихом. Помечаем штрихом 0^'_2,7и считаем седьмой столбец незанятым, знак «+» сверху снимаем, а вторую строку объявляем занятой и помечаем знаком «+» справа.

+	+	+	+	+	+	+
D₂=	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

П.5. Переходим к пункту 2. Помечаем звездочкой 0*_6,5,штрихом 0^'_8,3, 0^'_2,7. В третьей нет

, следовательно, переходим к пункту 4, ε=d_6,4=7 после преобразований, получим матрицу D₃

+	+	+	+	+	+	+
D₃=	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

П.4. Строим цепочку из нулей. Начиная от только что отмеченного штрихом нуля (0^’_2,7), идем по строке до

_5,2 цепочка состоит из двух элементов Ц: 0_7,2, 0^’_5,2. В матрице такие цепочки обозначают так

. После преобразования получим новый набор нулей со звездочкой (

), который содержит на одну звездочку больше, чем предыдущий набор.

Проводим следующие пересчеты.

+	+	+	+	+	+
D₃=	25	0	0^*	27	19	16	20	32	+
	3	43	2	7	23	14	5	0^*	+
	6	32	0	23	20	5	18	7	+
	0^*	36	10	0	0	5	2	17
	0	0'	9	19	5	45	19	12	+
	15	24	10	7	0’	0^*	5	5
	22	0^*	13	8	9	15	22	9
	6	32	0	20	7	34	0^*	8	+

Процесс окончен, так как число нулей со звездочкой равно размерности матрицы эффективности.

Оптимальный вариант выбора (1,2)(2,7)(3,8)(4,1)(5,4),(6,6),(7,5),(8,3). Это значит, что первая невеста выберет второго жениха, вторая невеста седьмого жениха, третья –восьмого, четвертая первого, пятая четвертого, шестая – шестого, седьмая невеста пятого жениха, а восьмая невеста выберет третьего жениха.

При этом максимальная суммарная эффективность (суммарная продолжительность жизни всех семей) равна:

(единиц эффективности)