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

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

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

Таблица 1 – Условия задачи о назначениях

10	5	9	18	11
13	6	6	12	14
3	2	4	4	5
18	9	12	17	15
11	6	14	19	10

Определить оптимальное назначение так, чтобы срок выполнения всех работ было минимальным.

Решение.

Условия задачи означают, что имеется 5 работ и 5 исполнителей, которые могут выполнять работы с разной скоростью. Время выполнения работ представлена в таблице в ед. времени.

Таблица 2

Исполнители	Работы
	T1	T2	T3	T4	T5
M1	10	5	9	18	11
M2	13	6	6	12	14
M3	3	2	4	4	5
M4	18	9	12	17	15
M5	11	6	14	19	10

В каждой строке подчеркнем минимальный элемент (таблица 3).

Таблица 3

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

Заметим, что во второй строке минимальный элемент равен 6 = c₂₂ = c₂₃, при этом стоит подчеркнуть c₂₃ с целью максимально «растащить» подчеркнутые элементы по столбцам.

Итерация 1

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

Таблица 4

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

Составим в каждой строке разности R_i и определим среди них минимальную. Разности будут существовать только в тех строках, где среди элементов подмножества А есть подчеркнутые элементы (таблица 5).

Таблица 5

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

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

Таблица 6

	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
	А´	А	А´	А´	А´