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

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

Условно подчеркнем тот элемент, из которого вычитали, чтобы получить min R_i = 1, то есть подчеркнем элемент с₃₁=3. В первом столбце нет подчеркиваний, значит условное подчеркивание может быть явным. Поэтому прежнее подчеркивание удаляем и в третьей строке подчеркиваем первый элемент – получаем новое подчеркивание (таблица 7).
Таблица 7

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

Как только удалось одно подчеркивание «перетащить» в другой столбец, итерация закончена. За одну итерацию можно «перетащить» лишь одно подчеркивание. Далее возвращаемся в Начало. При возвращении в Начало снимаем все выделения, то есть все столбцы в подмножестве А´(таблица 8).

Итерация 2

Таблица 8

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

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

Таблица 9

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

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

Таблица 10

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

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

Таблица 11

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

Условно подчеркнем элемент c₄₃=12, из которого вычитали, чтобы получить min R_i = 2. Так как в третьем столбце уже есть подчеркнутый элемент, то «перетащить» подчеркивание с элемента c₄₂ на c₄₃ не удастся. Поэтому столбец с условно подчеркнутым элементам вводим в подмножество А (таблица 12)

Таблица 12

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