umk_2001_028

–	14	16	63	64	41	73	70
14	–	33	71	74	56	62	40
16	33	–	84	85	29	36	55
63	71	84	–	43	71	46	20
64	74	85	43	–	84	44	51
41	56	29	71	84	–	67	55
73	62	36	46	44	67	–	45
70	40	55	20	51	55	45	–

6.5. На станке изготавливают однотипные изделия различных цветов, причем необходимо изготовить по одному изделию каждого цвета. Издержки на наладочные работы включают в себя только расходы, связанные с изменением цвета выпускаемых изделий. Требуется составить такой календарный план, при котором суммарные издержки на наладочные работы минимальны. Расходы на наладочные работы зависят от цвета изделия, изготовленного последним. Стоимость (в тыс. руб.) перехода от цвета i к цвету j задается матрицей С. Найти планы, используя алгоритмы «БЛИЖАЙШИЙ СОСЕД» и «БЛИЖАЙШАЯ ВСТАВКА». Найти оптимальный план.

	1	2	3	4	5	6
1	–	1	2	3	4	5
2	2	–	3	4	5	6
3	3	4	–	5	6	7
4	4	5	6	–	7	8
5	5	6	7	8	–	9
6	6	7	8	9	10	–

6.6. Промышленное предприятие состоит из трех цехов, между которыми расположены дороги и подъездные пути. В цехах находятся шесть заводских контор (пункты 2, 3, 4, 5, 6, 7), в которых следует вести уборку. Уборочная машина со всем инвентарем для уборки находится в пункте 1. Инженер-технолог, выполняющий работу по уче- ту постоянных издержек, с помощью нормативного справочника определил время, необходимое для уборки контор и перехода из одной конторы в другую. Однако он решает найти наиболее экономный маршрут. Расстояния между пунктами (в метрах) приведены в матрице. Определите наиболее экономный маршрут и его длину.

	1	2	3	4	5	6	7
1	–	40	90	120	–	–	90
2	40	–	130	–	–	–	–
3	90	130	–	80	–	–	–
4	120	–	80	–	70	–	80
5	–	–	–	70	–	60	–
6	–	–	–	–	60	–	140
7	90	–	–	80	–	140	–

Инженер-технолог решает, что необходимо исследовать возможность использования внешних дорог. Кроме того, правила техники безопасности ограничивают скорость передвижения уборочной машины по внутренним дорогам до 4,4 км/ч, а по внешним – до 8,2 км/ч. В таблицах, приведенных ниже, даны длины внешних дорог.

Дополнительные внешние дороги (неориентированное ребро):

Дорога	Расстояние, м
1–4	140
1–7	180
6–7	150

Новые внешние дороги:

Дорога	Расстояние, м
3–5	190
4–6	110

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

6.7. Пусть G=(V, E, C) – полный неориентированный взвешенный граф, |V|=n – число вершин в графе, C – неотрицательная матрица весов, АБС(G) – маршрут коммивояжера, построенный алгоритмом «БЛИЖАЙШИЙ СОСЕД», АБВ(G) – маршрут коммивояжера, построенный алгоритмом «БЛИЖАЙШАЯ ВСТАВКА», Опт(G) – оптимальный маршрут, |АБС(G)|, |АБВ(G)|, |Опт(G)| – длины соответствующих маршрутов. Справедливы теоремы:

40

41

1. Если C – n´n – матрица стоимостей (n³2), которая симметрична (C[i, j]=C[j, i] для любых i и j) и удовлетворяет неравенству треугольника (C[i, j]£C[i, k]+C[k, j] для любых i, j и k), то |АБС(G)|/|Опт (G)|£( élognù +1)/2.

2. Если C – n´n – матрица стоимостей (n³2), которая симметрич- на и удовлетворяет неравенству треугольника, то |АБВ(G)|/|Опт (G)|<2.

Для заданной произвольной симметричной матрицы стоимостей можно сделать так, чтобы выполнялось неравенство треугольника, добавляя к каждому элементу матрицы max{C[i, j]}. Означает ли это, что теоремы 1) и 2) верны для симметричных матриц стоимостей, для которых неравенство треугольника не выполняется?

7. ЗАДАЧИ НА РАЗНЫЕ ТЕМЫ

7.1. Задача определения минимального числа исполнителей для выполнения твердого плана заданий. Предположим, что имеется n заданий Ti, обусловленных временем начала ai и временем окончания

bi (ai£bi), и что время перехода от Ti ê Tj задается при i¹j числом tij³0. Сколько нужно исполнителей, чтобы выполнить все задания плана?

Предложите математическую модель этой задачи как задачи дискретной оптимизации. Рассмотрите конкретную задачу.

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

	Çàäà-	Начало	Конец	1	2	3	4	5	6	7	8	9	10
	íèå
	1	13.00	13.30	–	60	10	230	180	20	15	40	120	30
	2	18.00	20.00	10	–	40	75	40	5	30	60	5	15
	3	22.30	23.00	70	30	–	0	70	30	20	5	120	70
	4	16.00	17.00	0	50	75	–	20	15	10	20	60	10
	5	16.00	19.00	200	240	150	70	–	15	5	240	90	65
	6	12.00	13.00	20	15	20	75	120	–	30	30	15	45
	7	14.00	17.00	15	30	60	45	30	15	–	10	5	0
	8	23.00	24.00	20	35	15	120	75	30	45	–	20	10
	9	20.10	21.00	25	60	15	10	100	70	80	60	–	120
	10	13.45	15.00	60	60	30	30	120	40	50	60	70	–

7.2. По воздушной линии за год должно быть осуществлено n рейсов. На множестве рейсов задано отношение предшествования. Будем говорить, что рейс F1 предшествует рейсу F2 (запись F1 f F2), если самолет может сначала сделать рейс F1, и лишь затем рейс F2. Ясно, что так определенное отношение предшествования является транзитивным и антисимметричным. Требуется определить минимальное число самолетов, необходимое для выполнения расписания. Предложите математическую модель этой задачи, как задачи дискретной оптимизации. Разберите конкретный пример:

n = 9;

рейсу 3 предшествует рейс 1; рейсу 4 предшествуют рейсы 1, 2; рейсу 5 предшествует рейс 2; рейсу 6 предшествуют рейсы 3, 4; рейсу 7 предшествует рейс 3; рейсу 8 предшествуют рейсы 6, 7; рейсу 9 предшествуют рейсы 5, 7.

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

7.3.Предположим, что организации надо нанять переводчиков с французского, немецкого, греческого, итальянского, испанского, английского и китайского языков на русский и что имеется 5 кандидатур A, B, C, D и E. Каждая кандидатура владеет некоторым подмножеством из указанного выше множества языков и требует вполне определенной заработной платы. Необходимо решить, каких переводчиков надо нанять, чтобы затраты на заработную плату были наименьшими. Требования на оплату труда у всех претендентов одинаковые. Рассмотреть пример, когда: французским языком владеют переводчики A, C, D; немецким – A и B, греческим – B, итальянским – A и D, испанским – C, английским – B, C, E, китайским – D и E.

7.4.Пусть даны n заявок на проведение занятий в одной и той же аудитории. Два различных занятия не могут перекрываться по време-

ни. В каждой заявке указаны начало и конец занятия (si è fi для i-й заявки). Разные заявки могут пересекаться и тогда можно удовлетворить только одну из них. Отождествим каждую заявку с промежут-

êîì [si, fi), так что конец одного занятия может совпадать с началом другого, и это не считается пересечением. Заявки с номерами i и j

42

43

совместны, если интервалы [si, fi) è [sj, fj) не пересекаются (иными словами, если fi£sj èëè fj£si). Задача о выборе заявок состоит в том, чтобы набрать максимальное количество совместных друг с другом заявок. Разработайте жадный алгоритм решения данной задачи.

7.5.Задачу о выборе заявок можно решать с помощью динами- ческого программирования, вычисляя последовательно (для i=1, 2,

…, n) число mi – максимально возможное число совместных заявок среди заявок с номерами 1, 2, …, i (считая что выполнены неравен-

ñòâà f1£f2£ … £fn). Сравнить время работы такого алгоритма и жадного алгоритма.

7.6.Пусть по-прежнему имеется множество заявок на проведение занятий (смотрите условия предыдущих задач). В каждой заявке указаны начало и конец, но аудиторий сколько угодно. Надо распределить заявки по аудиториям, используя как можно меньше аудиторий. Разработайте эффективный жадный алгоритм, решающий эту задачу.

7.7.Для задачи о выборе заявок возможны несколько способов жадного выбора, и не все они годятся. Покажите на примере, что правила «на каждом шаге выбирать заявку наименьшей длительности, совместную с уже выбранными», а также «на каждом шаге выбирать заявку, совместную с наибольшим количеством остающихся», не годятся.

7.8.Дискретная задача о рюкзаке. На складе хранится n вещей.

Вещь номер i стоит vi долларов и весит wi килограммов (vi è wi – целые числа). Надо взять вещей на максимальную сумму, причем максимальный вес, который можно унести в рюкзаке, равен W (число W также целое). Какие вещи надо положить в рюкзак? Приведите пример, показывающий, что для данной задачи жадный алгоритм не дает оптимум. Разработайте основанный на динамическом программировании алгоритм решения дискретной задачи о рюкзаке. Алгоритм должен работать за O(nW), где n – количество вещей, W – максимальный вес рюкзака).

7.9.Пусть в дискретной задаче о рюкзаке вещи можно упорядо- чить таким образом, чтобы одновременно выполнялись неравенства

w1£w2£ … £wn è v1³v2³ … ³vn. Разработайте эффективный алгоритм нахождения оптимального набора и докажите, что он правилен.

7.10.Профессор едет по шоссе из Петербурга в Москву, имея при себе карту с указанием всех стоящих на шоссе бензоколонок и расстояния между ними. Известно расстояние, которое может проехать машина с полностью заправленным баком. Разработайте эффективный алгоритм, позволяющий выяснить, на каких бензоколонках надо заправляться, чтобы количество заправок было минимальным. (В на- чале пути бак полон.)

7.11.Дано n точек x1, x2, …,xn на координатной прямой. Требуется покрыть все эти точки наименьшим числом отрезков длины 1. Разработайте эффективный алгоритм, решающий эту оптимизационную задачу.

Список литературы

Асанов М. О. Дискретная оптимизация. Екатеринбург: УралНАУКА, 1998. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислитель-

ных алгоритмов. М.: Мир, 1979.

Беров В. И., Лапунов А. В., Матюхин В. А. и др. Особенности национальных задач по информатике. Киров: ООО «Триада-С», 2000.

Вирт Н. Алгоритмы и структуры данных. М.: Мир, 1989.

Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: Построение и анализ. М.: МЦНМО, 1999.

Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир, 1978. Липский В. Комбинаторика для программистов. М.: Мир, 1988. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Тео-

рия и практика. М.: Мир, 1980.

Свами М., Тхуласираман К. Графы, сети и алгоритмы. М.: Мир, 1984. Филлипс Д., Гарсиа-Диас А. Методы анализа сетей. М.: Мир, 1984. Форд Л., Фалкерсон Д. Потоки в сетях. М.: Мир, 1966.

44

	СОДЕРЖАНИЕ
1.	Поиск в графе ..............................................................................................................	4
2.	Задача о минимальном остове ..................................................................................	11
3.	Пути в сетях ..............................................................................................................	14
4.	Задача о максимальном потоке и ее приложения ..................................................	22
5.	Паросочетания в двудольных графах .....................................................................	29
6.	Задача коммивояжера ...............................................................................................	39
7.	Задачи на разные темы .............................................................................................	42
Список литературы .......................................................................................................		45

Учебное издание

ЗАДАЧИ И УПРАЖНЕНИЯ ПО ДИСКРЕТНОЙ ОПТИМИЗАЦИИ

Составитель Крутова Людмила Игоревна

Редактор и корректор В. И. Попова Компьютерная верстка Н. В. Комардиной

ЛР ¹ 020257 от 22.11.96. Подписано в печать 19.11.2001. Формат 60х84		1/ .
Бумага для множительных аппаратов. Гарнитура Times.		16
Уч.-изд. л. 2,5. Усл. печ. л. 2,67. Тираж 100 экз. Заказ	.

Издательство Уральского университета. 620083, Екатеринбург, пр. Ленина, 51. Отпечатано в ИПЦ «Издательство УрГУ». 620083, Екатеринбург, ул. Тургенева, 4.