Задача о назначениях (стр. 1 )

Задача о назначениях

Вы покидаете Мехико по автостраде, которая вьется по вулканическим горам, отделяющим огромное плато, где возвышается столица, от роскошной долины, где прячется Куэрнавака — жемчужина и главный город штата Морелос. Если у вас есть время, то покиньте автостраду и сделайте крюк, чтобы заглянуть в Таско — чудо красок и город серебра, не гнусного торгашеского серебра, а подлинного серебра, чеканного. Вы неожиданно попадаете в тропическую жару Герреро и через несколько часов пути перед вами предстанет Акапулько, эта царица пляжей Тихого океана.

Солнце поднимается, сверкая над двадцатьюпляжной бухтой, окаймленной кокосовыми пальмами, отелями, сказочными виллами, а когда, после жаркого дня, светило дойдет до горизонта, перед вами с пика де ля Куэста предстанет ни с чем не сравнимое зрелище заката на Тихом океане: небо озарено всеми цветами, от голубого до красного, от сиреневого до желтого… В этой феерии вы, быть может, заметите даже легендарный зеленый луч, появляющийся в тот момент, когда солнце исчезает.

Затем глубокой ночью вы будете присутствовать при смертельных прыжках в воду ныряльщиков из Кебрады. Это прыжки с высоты 35 метров в узкий фиорд, где шумит разбушевавшееся море, которое зажженный на скалах костер населяет фантастическими существами.

Десятки тысяч жителей Мехико совершают это четырех - шестичасовое путешествие в конце недели или на каникулах, чтобы вкусить от восхитительного тепла Акапулько (тепло это иногда слишком интенсивно, но без него пропало бы все очарование тропиков). Из Мехико в Акапулько едут на собственных автомобилях и на автомобилях друзей, автостопом и самолетом, в роскошном автобусе и в «грузовике», который был грузовиком уже 20 лет тому назад (заметьте, что в Мексике автобус называется «грузовиком», но не следует искать в этом слове презрительного оттенка: некоторые грузовики столь комфортабельны, что могут конкурировать с самолетами).

Рейс Мехико — Акапулько обслуживают роскошные автобусы компании «Золотой Пеликан», а также автобусы конкурирующих компаний. Обслуживающая автобус бригада состоит из шофера, всегда веселого, иногда болтливого, и кондукторши, всегда красивой и редко болтливой (с точки зрения путешественников-мужчин). Вот расписание движения по маршруту Мехико — Акапулько и Акапулько — Мехико:

Мехико – Акапулько
Отправление из Мехико	Номер рейса	Прибытие в Акапулько
06:00	a	12:00	Время в пути 6 часов
07:30	b	13:30
11:30	c	17:30
19:00	d	01:00
00:30	e	06:30

Акапулько – Мехико
Прибытие в Мехико	Номер рейса	Отправление из Акапулько
11:30	1	05:30	Время в пути 6 часов
15:00	2	09:00
21:00	3	15:00
00:30	4	18:30
06:00	5	00:00

Среди многочисленных проблем, которые встают перед «Золотым Пеликаном», довольно важной оказывается проблема местожительства бригад автобусов. При решении ее нужно минимизировать, учитывая требования расписания, общее время пребывания бригады вне дома. При этом исходят из совершенно очевидных финансовых соображений, так как оплата бригад не зависит от того, находятся ли они в пути или ожидают своего возвращения домой, в Мехико или в Акапулько. Кроме того, принимаются во внимание соображения социального порядка — не разлучать надолго главу семьи с остальными ее членами (правда, один из шоферов предлагал считать оптимумом как раз противоположное). С другой стороны, существуют физиологические пределы работы: ни одна бригада не должна пускаться в путь, не отдохнув в течение хотя бы четырех часов. Вместе с тем бригада не должна ждать рейса более чем 24 часа.

В этих условиях задача может быть сформулирована следующим образом. Где должны жить бригады и какие рейсы они должны обслуживать, чтобы суммарное время, которое все бригады теряют на ожидание обратного рейса, было бы минимальным при том ограничении, что время ожидания каждой бригады должно быть больше 4 часов и меньше 24 часов?

Жить в Акапулько было бы мечтой каждого, но во главе «Пеликана» стоит человек, по – видимому, совершенно равнодушный к очарованиям Тихого океана.

Предположим, например, что бригада живет в Мехико и обслуживает рейс c в направлении на Акапулько и рейс 2 в противоположном направлении. Эта бригада должна ждать в Акапулько 15,5 часа (от 17.30 до 09.00). Составим путем аналогичных расчетов две таблицы потерянного времени, считая в первом случае, что все бригады проживают в Мехико, а во втором,— что все они живут в Акапулько.

Таблица 6.1

Все бригады живут в Мехико

	1	2	3	4	5
a	17,5	21	3	6,5	12
b	16	19,5	1,5	5	10,5
c	12	15,5	21,5	1	6,5
d	4,5	8	14	17,5	23
e	23	2,5	8,5	12	17,5

Таблица 6.2

Все бригады живут в Акапулько

	1	2	3	4	5
a	18,5	15	9	5,5	0
b	20	16,5	10,5	7	1,5
c	0	20,5	14,5	11	5,5
d	7,5	4	22	18,5	13
e	13	9,5	3,5	0	18,5

Составим теперь на основе этих двух таблиц третью, каждый элемент которой будет являться меньшим из чисел, занимающих соответственные клетки в двух исходных таблицах. При этом мы не будем, однако, принимать во внимание числа, не превосходящие четырех (учитывая потребности бригады в отдыхе). Например, если нам представится выбор между числами а1 (место жительства в Мехико) и 1а (место жительства в Акапулько), то выбрать следует а1, дающее нам ожидание в 17,5 часа вместо 18,5 часа. Напротив, из b3 (Мехико) и 3b (Акапулько) мы выбираем 3b, хотя этому варианту и не соответствует меньшее время, ибо вариант b3 оставляет на отдых меньше 4 часов и потому неприемлем (или же свыше 24 часов, что мы предусмотрительно вовсе не учитываем в наших таблицах).

Таблица 6.3

Минимальные времена ожидания

	1	2	3	4	5
a	17,5	15	9	5,5	12
b	16	16,5	10,5	5	10,5
c	12	15,5	14,5	11	5,5
d	4,5	8	14	17,5	13
e	13	9,5	8,5	12	17,5

Назовем назначением факт приписания бригады одному из рейсов (скажем, al, 2a, а3 и т. д.). Очевидно, каждая бригада может быть назначена лишь на один прямой и на один обратный рейс. Таким образом, любое возможное решение задачи о назначениях может быть представлено таблицей, в клетках которой стоят числа 0 или 1, причем в каждой строке и в каждом столбце имеется ровно одна единица (символизирующая выбранное назначение).

Таблица 6.4

Пример возможного решения

	1	2	3	4	5
a	0	1	0	0	0
b	1	0	0	0	0
c	0	0	0	0	1
d	0	0	1	0	0
e	0	0	0	1	0

Например, решение, описываемое таблицей 6.4, соответствует рейсам 2а, b1, 5c, d3, e4, как это легко установить по предыдущим таблицам; при таком варианте трем бригадам следует жить в Мехико, а двум — в Акапулько. Суммарные потери времени будут составлять: