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

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

Прибавим min R_i =0 ко всем элементам множества А. Очевидно, что в этом случае значения элементов множества А останутся теми же. Условно подчеркнем элемент с₄₃, из которого вычитали. Это подчеркивание не может стать явным, так как в третьем столбце уже есть подчеркнутый элемент 23.

Поэтому вводим третий столбец в множество А и составляем разности построчно (таблица 18).

Таблица 18

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

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

Таблица 19

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

Условно подчеркнем элемент с₁₁, из которого вычитали. Однако, в первом столбце есть подчеркнутый элемент, поэтому про условное подчеркивание забываем и вводим первый столбец в множество А. После увеличения множества А на очередной столбец, составляем построчно разности (таблица 20).

Таблица 20

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

min R_i = 1. От выбора строки с min R_i оптимальная эффективность назначения не зависит. Поэтому выберем ту строку, в которой можно будет «претащить» подчеркивание. Если взять min R_i =с₁₅=11, то придется условно подчеркнуть элемент в пятом столбце. Но в этом столбце уже есть подчеркнутый элемент. Если взять min R_i =с₃₄=4, то придется условно подчеркнуть элемент в четвертом столбце. В этом столбце нет подчеркнутых элементов и «перетащить» подчеркивание удастся. Если взять min R_i =с₄₅=15, то придется условно подчеркнуть элемент в пятом столбце. Но в этом столбце уже есть подчеркнутый элемент.

Выбор строки с min R_i = 1 очевиден: min R_i = с₃₄. В этом случае подчеркивание в третьей строке будет в четвертом столбце. Прибавим 1 ко всем элементам множества А и перенесем подчеркивание (таблица 21).

Таблица 21

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

Итерация 4

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

Таблица 22

	T1	T2	T3	T4	T5	Ri
M1	11	11	12	18	11	11-11 = 0
M2	14	12	8	12	14	---
M3	4	8	7	4	5	---
M4	19	15	15	17	15	15-15 = 0
M5	12	12	17	19	10	---
	А´	А	А´	А´	А´