Задача. пример. Решить задачу о назначениях, условия которой занесены в таблицу 1

• Название: Решить задачу о назначениях, условия которой занесены в таблицу 1
• Анкор: Задача
• Дата: 17.09.2021
• Размер: 73.43 Kb.
• Имя файла: пример.docx
• Тип: Решение; #233323
• страница: 3 из 5

Как только количество выделенных столбцов увеличивается еще на один столбец, возвращаемся к Шагу 2 и составляем построчно разности R_i (таблица 13).

Таблица 13

	T1	T2	T3	T4	T5	Ri
M1	10	8	9	18	11	10-8 = 2
M2	13	9	6	12	14	12-6 = 6
M3	3	5	4	4	5	---
M4	18	12	12	17	15	15-12 = 3
M5	11	9	14	19	10	10-9 = 1 -min Ri
	А´	А	А	А´	А´

Прибавим min R_i =1 ко всем элемента множества А (таблица 14).

Таблица 14

	T1	T2	T3	T4	T5
M1	10	9	10	18	11
M2	13	10	6	12	14
M3	3	6	5	4	5
M4	18	13	13	17	15
M5	11	10	15	19	10
	А´	А	А	А´	А´

Условно подчеркнем элемент с₅₅=10. В пятом столбце не подчеркнутых элементов, поэтому условное подчеркивание может быть явным. «Перетащим» подчеркивание в пятой строке из второго столбца в пятый. Так как удалось «перетащить» подчеркивание, то итерация завершена и переходим в начало.

Итерация 3

После завершения второй итерации таблица назначений выглядит так (таблица 15).

Таблица 15

	T1	T2	T3	T4	T5
M1	10	9	10	18	11
M2	13	10	6	12	14
M3	3	6	5	4	5
M4	18	13	13	17	15
M5	11	10	15	19	10
	А´	А´	А´	А´	А´

Разобьем множество всех столбцов на два подмножества А и А´, выделяя выбранный столбец цветом (таблица 16).

Таблица 16

	T1	T2	T3	T4	T5
M1	10	9	10	18	11
M2	13	10	6	12	14
M3	3	6	5	4	5
M4	18	13	13	17	15
M5	11	10	15	19	10
	А´	А	А´	А´	А´

Составим разности построчно (таблица 17).

Таблица 17

	T1	T2	T3	T4	T5	Ri
M1	10	9	10	18	11	10-9 = 1
M2	13	10	6	12	14	---
M3	3	6	5	4	5	---
M4	18	13	13	17	15	13-13 = 0- min Ri
M5	11	10	15	19	10	---
	А´	А	А´	А´	А´