Исправленные упражнения: Задача о назначении

Контенус

Исправлены упражнения о задачах с заданиями

На странице представлено несколько исправленных упражнений по задачам автоматизированного планирования и составления расписаний, особенно по задачам назначения.

Упражнение 1

Сеть Атлантического побережья заслуживает четырех городов. Офис хочет выделить четыре растения. Стоимость отправки энергии с завода в каждый город описана ниже:

	Роли	Атланта	Дарем	Клемсон
Завод А	210	90	180	160
Завод Б	100	70	130	200
Завод С	175	105	140	170
Завод Д	80	65	105	120

Растение может заслужить только один город, а город может брать энергию только от одного растения. Найдите лучшее задание по минимальной цене.

Решение

После первого сокращения:

	р	В	Д	ПРОТИВ
В	105	0	55	15
Б	15	0	25	75
ПРОТИВ	35	0	0	10
Д	0	0	5	0

После второго сокращения:

	р	В	Д	ПРОТИВ
В	90	0	40	0
Б	0	0	10	60
ПРОТИВ	55	15	0	10
Д	0	15	5	0

Решение: 90+100+140+120=450.

Упражнение 2

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

8	16	15	91	64
83	42	93	75	27
76	95	75	81	50
20	42	96	90	24
38	28	2	15	81

Решение

Найдите решение присваивания этой матрицы. Перестройте столбцы так, чтобы решение образовало диагональ.

Упражнение 3

Три робота {a,b,c} должны выполнить три задачи {t1, t2, t3} в следующей сетке. Роботу требуется один день, чтобы переместиться из одной ячейки в одну из соседних.

В следующей таблице мы перечисляем дни, в течение которых каждый робот может выполнять каждую задачу в одиночку. Задания должны быть выполнены как можно быстрее.

Решение

Добавьте расстояние до Манхэттена в днях в последнюю таблицу. Решить задачу с заданием.

Упражнение 4

Braneeast Airlines должна укомплектовать персоналом несостоявшиеся рейсы между Нью-Йорком и Чикаго, указанные в таблице ниже. Каждая из бригад Бранаста живет либо в Нью-Йорке, либо в Чикаго. Каждый день экипаж должен летать одним рейсом Нью-Йорк-Чикаго и одним рейсом Чикаго-Нью-Йорк с перерывом между рейсами не менее часа.

Бранист хочет спланировать работу бригад так, чтобы свести к минимуму общее время простоя. Составьте задачу о назначении, которую можно использовать для достижения этой цели. Конечно, некоторые задания невозможны. Найдите полетные задания, минимизирующие общее время простоя. Сколько бригад должно базироваться в каждом городе? Предположим, что в конце дня каждая бригада должна быть в своем родном городе.

Решение

Таблица назначения строится следующим образом: для первого рейса из Чикаго с учетом времени его прибытия в Нью-Йорк, сколько времени экипажу приходится ждать в аэропорту. Например, первый рейс из Чикаго прибывает в 10:00:

Полет	1	2	3	4	5	6	7
Покинуть Нью-Йорк	7	8	10	12	14	16	18
время ожидания	невозможно	невозможно	невозможно	2	4	6	8

Заметим, что рейсы 4, 5, 6, 7 из Чикаго не могут быть отправной точкой, поэтому мы вычисляем время ожидания от рейса в Нью-Йорк. Обратите внимание, что рейс 7 из Нью-Йорка не может быть отправной точкой, поэтому мы вычисляем время ожидания от рейса в Чикаго. Для каждого элемента таблицы мы сохраняем вычисленное наименьшее значение (для рейса из Чикаго и Нью-Йорка).

Решение:

Старт в Нью-Йорке: (1.3), (2.4), (3.5), (5.6), (6.7).

Старты в Чикаго: (4.1), (7.2).

Общее время простоя = 25 часов.

Упражнение 5

Рассмотрим данные таблицы ниже. Если экипаж, базирующийся в Мумбаи, прибывает в Дели данным рейсом, он должен вернуться в Мумбаи более поздним рейсом. Предположим, что для любой данной пары экипаж будет базироваться в городе, что приводит к меньшей остановке.

Задача состоит в том, чтобы найти пары так, чтобы минимизировать время нахождения на земле вдали от дома, при условии минимального интервала в один час между прибытием и отъездом. Учитывая парные полеты, где должны базироваться экипажи?

Решение

Как и в предыдущем упражнении, сначала вычислите матрицы времени пересадки, одну для пересадки в Мумбаи, а другую для Дели.

Теперь мы вычисляем минимум значений для 36 пар и строим таблицу ниже. Например, (7,2) является минимумом между (7,2) в первой матрице и (2,7) во второй.

Решением этой задачи являются пары (7,3) из Мумбая, (8,4) из Мумбаи, (9,2) из Дели, (10,5) из Мумбаи, (11,6) из Дели, (12, 1) из Дели с общим временем простоя = 18ч.

Упражнение 6

Решите следующую задачу как задачу о назначениях.

Свернуть в 4 раза₁₁+6X₁₂+5Х₁₃+5Х₁₄+7X₂₁+4X₂₂+5Х₂₃+6X₂₄ +4X₃₁+7X₃₂+6X₃₃+4X₃₄ +5Х₄₁+3X₄₂+4X₄₃+7X₄₄

Св. Х₁₁+Х₁₂+Х₁₃+Х₁₄=1

Икс₂₁+Х₂₂+Х₂₄+Х₂₄=1

Икс₃₁+Х₃₂+Х₃₃+Х₃₄=1

Икс₄₁+Х₄₂+Х₄₃+Х₄₄=1

Икс₁₁+Х₂₁+Х₃₁+Х₄₁=1

Икс₁₂+Х₂₂+Х₃₂+Х₄₂=1

Икс₁₃+Х₂₃+Х₃₃+Х₄₃=1

Икс₁₄+Х₂₄+Х₃₄+Х₄₄=1

Решение

Вот таблица для решения:

Упражнение 7

Решите следующую задачу как задачу о назначениях.

Решение

Проблема назначения описана в таблице ниже:

	1	2	3
1	5	9	ниже
2	ниже	2	ниже
3	ниже	1	1

Упражнение 8

Департамент истории искусств предлагает шесть курсов в семестр. На кафедре семь профессоров, каждый из которых может вести только определенные курсы, как показано в таблице. Можно ли поручить шесть курсов профессорам, чтобы ни один профессор не читал более одного курса?

Решение

Проблема назначения описана в таблице ниже:

	Муравей	летучая мышь	Кошка	Додо	Лягушка	комар	Боров
Античный	1	1	1	1	ниже	ниже	ниже
эпоха Возрождения	1	ниже	ниже	ниже	1	1	ниже
Барокко	1	ниже	ниже	ниже	1	ниже	ниже
Импрессионизм	ниже	ниже	ниже	ниже	1	1	ниже
Современный	ниже	ниже	1	ниже	ниже	1	1
Современный	1	ниже	ниже	ниже	ниже	1	ниже
дурачок	1	1	1	1	1	1	1

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