3. Задачи для самостоятельного решения

1. Является ли граф Петерсена гамильтоновым ?

2. Существует ли в графе G₂ эйлеровы цепи и циклы ? Нарисовать граф.

3. Доказать, что в графе без вершин с нулевой полустепенью исхода (захода) имеется простой контур.

4. Доказать, что число различных деревьев, которые можно построить на М вершинах, равно М^М-2 .

5. Пусть G-граф, множество вершин которого совпадает с отрезком натурального ряда (1,2,3,…,n), а множество ребер определяется так: несовпадающие сершины U и V смежны тогда и только тогда, когда числа U и V взаимно простые. Требуется :

а) записать матрицу S;

б) показать, является ли граф G связным ?

6. Найти компоненты сильной связности графа G₁:

7. Является ли граф G планарным ? Доказать.

8. Построить подграф графа G, порожденный вершинами .

9. Доказать, что графы (а) изоморфны, а графы (б) неизоморфны:

а) б)

10. Сориентирвать граф G₅:

11. Найти ,,Ʋ графаG₆:

12. Определить степень связности графа G₇:

13. В графе G₁найти минимальный путь из вершиныV₁ в вершинуV₇.

14. Определить минимальный путь из V₁ вV₇во взвешенном орграфеG₃, имеющим матрицу длин дугL:

15. Найти хроматическое число графа G₂.

16. В изображенном на рис. 3.1 графе параметры дуг соответствуют верхним границам потоков по ним. Найти:

а) цепь с максимальной пропускной способностью из узла 1 в узел 8;

б) максимальный поток из узла 1 в узел 9;

в) максимальный поток между всеми парами узлов.

Рис. 3.1

17. Мебельная фабрика производит обеденные столы. Изготовление стола состоит из трех основных этапов: сборка, окраска, сушка. Сборка может производиться в одном из цехов A,B или C, окраска - в одном из цехов B,C,D или E ( но не в том же, в котором производится сборка ), сушка - в цехе F. Поскольку цеха оснащены различным оборудованием, то время выполнения операций в них не одинаковое. Средняя продолжительность ( в минутах ) выполнения каждой операции приводится в таблице.

Цех	A	B	C	D	E	F
Сборка	55	62	66	-	-	-
Окраска	-	45	35	50	40	-
Сушка	-	-	-	-	-	60

Во второй таблице дано время перевозки продукции между цехами:

	A	B	C	D	E	F
A	-	14	11	12	18	15
B	14	-	7	10	8	12
C	11	7	-	5	6	22
D	12	10	5	-	14	5
E	18	8	6	14	-	10
F	15	12	22	5	10	-

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

18. Компания TransAuto должна отправить колонну грузовиков из города 1 в город 11 по одному из маршрутов, проходящих через города 2,3,...,10. Длина автодорог, имеющихся между городами ( в милях ), дана в таблице.

	1	2	3	4	5	6	7	8	9	10	11
1		75						116
2			85	92
3				35			70
4					85			55	68
5						60	32		52	100
6									110		88
7										105
8									90
9
10											100

Все дороги с двусторонним движением, но не являются равноценными. Через города ...8,4,5,10,... проходит автомагистраль первого класса, через города ...2,4,9,6,... – магистраль второго класса. Грузовик расходует 6 галлонов бензина на 100 миль пути на дороге 1 класса, 8 галлонов - на дороге 2 класса, 12 галлонов - на остальных дорогах. Стоимость 1 галлона бензина - 6 долларов. Плата за проезд по дороге 1 класса - 10 $ с каждой машины, по дороге 2 класса - 5 $ ( возможен бесплатный переезд с дороги 1 класса на дорогу 2 класса ). Кроме того, на дороге, соединяющей города 4 и 9, имеется мост, проезд по которому стоит 6 $ с машины.

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

19. В одном из сельских районов имеется 7 ферм и 2 элеватора, соединенных между собой сетью автодорог. В таблице указаны длины дорог, соединяющих эти объекты. На некоторых из дорог имеются мосты, пропускная способность которых указана в скобках. Во второй таблице указана производительность каждой фермы.

Свою продукцию фермеры должны отвозить на элеваторы, однако они не имеют возможности вывезти весь произведенный продукт в виду ограниченноц пропускной способности мостов. Местный бюджет позволяет произвести капитальный ремонт одного моста. Какой из мостов следует отремонтировать ( и на сколько увеличить его пропускную способность ), так чтобы фермеры могли подъезжать к элеватору по возможности более короткими путями?

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

	1	2	3	4	5	6	7	8	9
1	-	22	24	16	41	38	62	63	23
2		-	19	23	26	42	43	52	37
3			-	14	20	28	30	33	33
4				-	36	22	40	39	17
5					-	43	18	31	58
6						-	34	27	25
7							-	13	64
8								-	53

21. Проект исследований и научно-технических разработок состоит из четырех задач: A,B,C,D, темпы решения которых зависят от выделенной для этой цели суммы. В таблице указано время выполнения задачи в месяцах ( первое число ) и стоимость в тысячах долларов ( второе число ).

Темп	A	B	C	D
Низкий	6,6	5,8	6,2	7,10
Средний	4,8	3,9	3,3	5,12
Высокий	3,9	2,10	1,5	3,18

Требуется определить:

1. За какое наименьшее время может быть выполнен проект, если на его осуществление может быть выделено 35000 $ ?

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

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

Управляющий станцией должен дать указание, по каким трубопроводам должна перекачиваться нефть, чтобы вся она могла быть доставлена на станцию, однако ему никак не удается это сделать. Возможно ли это вообще? Если нет, то пропускную способность какого трубопровода (но только одного!) следует увеличить и на какую величину, чтобы задача стала выполнимой?

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

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

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

Построить схему транспортировки угля, имеющую минимальную стоимость.

25. Компания осуществляет перевозку товаров с двух складов А и B в магазины C, D и E. Поскольку товары являются скоропортящимися, их нужно доставлять точно в срок, указанный заказчиком. В рассматриваемый день компания имеет заказы на выполнение следующих рейсов:

Компания располагает двумя грузовиками. Во второй таблице задано время передвижения между складами и магазинами в минутах, а также расходы при проезде между объектами без груза (в скобках).

Составить расписание перевозок, которое давало бы компании наибольшую прибыль.

26. Фирма должна удовлетворить спрос на продукцию в течение пяти периодов. Заданы следующие исходные данные:

Стоимость хранения единицы продукци на складе в течение одного периода равна 1 долл., однако если она хранится более одного периода, то стоимость хранения возрастает на 1 $ в каждый последующий период. Уровень запасов в начале первого периода составляет 50 единиц.

Составить производственный план на пять периодов, минимизирующий расходы фирмы.

27. Компания, изготавливающая лыжи, имеет три фабрики A,B, и C. Стоимость изготовления одной пары лыж, не считая стоимости древесины, а также максимальная месячная выработка известны: для фабрики A: 15 $ и 2500 пар, для B - 20 $ и 4000, для C - 10 $ и 4800.Kомпания получает древесину у двух поставщиков по цене 50 центов за фунт у первого и 40 у второго. На изготовление одной пары лыж идет 8 фунтов древесины.Затраты на транспортировку одного фунта древесины от поставщиков на фабрики равны: для первого: 1,2 и 3 $ на A,B,C соответственно, для второго - 4,3 и 2.

Компания продает свою продукцию главным образом в трех городах: X,Y и Z. Для каждого из них известна продажная цена единицы товара - 90 $, 75 $ и 100 $, и предполагаемый спрос - 7000,4000 и 4500 в месяц для городов X,Y и Z соответственно. Затраты на транспортировку единицы продукции с фабрик в города приводятся в таблице:

	X	Y	Z
A	2	2	3
B	3	5	6
C	2	1	4

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

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

	Начало	Конец	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	15	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	-

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

29. Владелец магазина приобрел 90 телевизоров, заплатив 40 $ за каждый. Ему известна их прогнозируемая продажная цена для каждого из последующих пяти периодов времени. Кроме того, изменяются затраты на хранение товара. Данные приведены в таблице.

Сколько телевизоров нужно продать в каждый из периодов, чтобы максимизировать прибыль?

30. Нефтяная компания Black Gold Petroleum должна построить нефтепровод, соединяющий месторождение M с одним из нефтеперерабатывающих заводов F1 или F2. Перекачка нефти осуществляется при помощи насосных станций, которые должны отстоять друг от друга не более чем на 100 миль и могут располагаться в населенных пунктах 1,...,8. В таблице даны расстояния между всеми объектами в милях, а также стоимость строительства насосной станции в каждом из пунктов в тысячах $ (в последнем столбце). Стоимость одной мили нефтепровода равна в среднем 72000$.

Как следует проложить нефтепровод?

31. Предприятия, производящие водные лыжи, имеют четыре общегосударственные оптовые базы, с которых лыжи распределяются по пяти различным магазинам. Найти схему транспортировки лыж, имеющую минимальную стоимость, при условии, что базы располагают 120,200,330,400 парами лыж, а магазинам требуется 200,250,300, 100 и 150 пар сответственно. Затраты на транспортировку задаются матрицей стоимостей.

	Магазины
	1	2	3	4	5
1	5	7	3	15	9
2	6	2	8	5	6
3	3	9	8	2	2
4	7	6	8	7	4

32. Цех получил срочный заказ на изготовление некоторого изделия. Процесс его изготовления включает 8 последовательных операций, каждая из которых может быть выполнена на одном из трех станков А,B или C.В первой табдице дано время выполнения каждой операции (в минутах),

	Операция
	1	2	3	4	5	6	7	8
A	65	140	35	65	95	15	30	20
B	75	120	60	50	80	40	40	15
C	90	110	45	45	45	20	25	25

во второй - время переналадки станка для выполнения последующих операций для станка А (первое число), B (второе) и C (третье).

Каково минимальное время изготовления изделия?

33. Десять городов связаны между собой линиями связи, состоящими из различного числа телефонных каналов. Каждая линия имеет ограниченную надежность и может иногда выходить из строя на непродолжительное время. В таблице задано количество телефонных каналов на каждой линии (первое число), а также вероятность ее отказа (в процентах, второе число).

Фирма, расположенная в городе 1, для постоянной связи с филиалом, расположенным в городе 10, должна иметь в распоряжении пучок из 15 телефонных каналов прямой связи. На каких линиях ей следует арендовать каналы, тобы: 1) пучок имел бы не более 4 промежуточных центров коммутации (в данном случае городов, кроме конечных 1 и 10) и 2) Вероятность блокировки связи была минимальной?

34. Добываемый уран перевозится с рудника на три завода A,B,C, где он обогащается, в результате чего образуется высокорадиоактивное вещество шестифтористый уран. Затем его доставляют десяти предприятиям, на которых оно должно быть преобразовано в топливо для ядерных реакторов. Правительство, исходя из соображений безопасности, разработало десятибалльную шкалу, характеризующую степень риска при транспортировке шестифтористого урана по различным маршрутам (число 10 соответсовует наибольшему риску). Соответствующие значения, а также требуемый объем поставок (кг в день) на каждое из 10 предприятий, приводятся в таблице.

	1	2	3	4	5	6	7	8	9	10
A	9	8	7	4	6	3	8	6	5	2
B	1	7	9	10	8	3	6	7	5	4
C	3	3	5	7	7	8	9	1	2	3
Спрос	100	100	300	150	200	90	110	50	50	100

Заводы могут производить шестифтористый уран в количествах 600 кг (А), 400 кг (B), 500 кг (C) в день. Найти схему транспортировки, при которой общий риск минимален.

35. На линии последовательной сборки имеется 6 рабочих мест, на которые необходимо назначить рабочих. Имеется 9 кандидатов на эти вакантные места. Администрации предприятия известна квалификация каждого рабочего и, следовательно, она может оценить эффективность его работы на каждом рабочем месте. Данные приведены в таблице.

	Рабочее место
	1	2	3	4	5	6
1	3	4	2	7	8	0
2	6	10	0	0	4	0
3	6	9	4	4	10	0
4	0	0	6	7	8	9
5	10	8	3	0	6	5
6	0	6	2	0	4	0
7	9	6	9	0	0	4
8	6	0	0	3	5	0
9	4	5	0	0	2	0

Эффективность работы всего конвейера определяется минимальной из эффективностей работы на каждом из мест. Какое назначение должна сделать администрация, чтобы эффективность работы конвейера была максимальной?

36. Программа обучения в бизнес-школе включает 11 дисциплин: A, B, C, D, E, F, G, H, I, J, K. Однако для получения диплома не обязательно изучать их все, достаточно изучить последовательно несколько дисциплин в одном из следующих порядков: A, D, H; A, E, G, I; A, F, I; B, C, G, I; B, J или B, C, K, H. В таблице приведены максимальное количество слушателей, которые одновременно могут изучать данную дисциплину, а также стоимость обучения. Продолжительность обучения для каждой дисциплины - 1 месяц.

Дисциплина	Количество	Стоимость
A	30	50
B	20	80
C	10	10
D	10	60
E	20	20
F	30	60
G	40	20
H	15	40
I	50	10
J	20	90
K	20	10

1) Какое максимальное количество слушателей могут быть обучены за 6 месяцев?

2) Тот же вопрос при условии, что никто из них не желает платить за обучение более 120 $.

37. Фирма Dog's Tail владеет четырьмя заводами, производящими летающие сковородки. Себестоимость продукции и цены на сырье для различных заводов не одинаковые. В данном районе имеется пять пунктов сбыта продукции, в каждом из них установлены свои цены на продукцию.

Требуется определить оптимальный план производства и распределения продукции.

38. East Texas Freight Company (EFTC) производит перевозки автотранспортом крупногабаритного оборудования. EFTC предлагают заключить контракт о перевозке неупакованного груза между семью предприятиями НАСА в г. Хьюстоне, штат Техас. По этому контракту требуется перевозить несколько видов оборудования с большим вертикальным габаритом. EFTC определила минимальную высоту проезда под мостами и надземными коммуникациями для каждой из дорог, соединяющих предприятия. Эти данные приведены в таблице (0 - нет прямой дороги).

	1	2	3	4	5	6	7
1	-	11	30	0	0	0	14
2	11	-	0	12	15	0	0
3	30	0	-	20	9	13	0
4	0	15	0	-	10	14	0
5	12	0	9	10	-	0	0
6	0	0	20	14	0	-	0
7	14	0	0	18	0	9	-

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

39. Восемь вычислительных центров (ВЦ) связаны между собой цифровыми каналами связи в единую информационно-вычислительную сеть. Пропускные способности каналов (кб/сек) даны в таблице.

Для обеспечения требуемого уровня надежности связи между двумя ВЦ необходимо, чтобы маршрут передачи информации проходил не более чем через два промежуточных узла. ВЦ обмениваются пакетами данных сравнительно редко, но объем передаваемой за один сеанс информации может быть велик, поэтому желательно, чтобы путь передачи информации имел бы как можно большую пропускную способность.

Какие маршруты следует выбрать для обмена данными между каждой из пар ВЦ?

40. Таможенная полиция подозревает, что между городами A и B, расположенными по разные стороны государственной границы, осуществляется контрабандная торговля. Города соединены между собой сетью автомобильных дорог, проходящих также через города C...L. Для пресечения незаконной торговли полиция предполагает разместить на некоторых дорогах контрольно-пропускные пункты таким образом, чтобы проехать из A в B, минуя все эти КПП, было бы невозможно. Стоимость содержания КПП (тыс. долл/год) для каждой из дорог приведена в таблице.

На каких дорогах следует разместить контрольно-пропускные пункты, чтобы минимизировать недовольство налогоплательщиков штата?

41. Фирме Red Ass для организации постоянной связи между городами A и L необходимо арендовать каналы на телефонных линиях, соединяющих эти города, а также города B...K. Стоимость аренды для каждой линии приведена в таблице.

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

42. Промышленная компания планирует производство кондиционеров, состоящих из трех основных частей: корпуса, вентилятора и мотора. Затраты на оборудование предприятия станками, производящими корпуса, вентиляторы и моторы, равны 20000, 50000 и 80000 $ соответственно. Однако, если вначале наладить выпуск вентиляторов, то затраты на остальное оборудование будут уменьшены на 5 %. Если вначале пустить в производство моторы, то затраты на оснащение предприятия станками двух других типов уменьшатся на 10 %. Если же в первую очередь выпускать корпуса, то остальные затраты уменьшатся на

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

43. Фирма Alamo получила заказ на кирпич, производимый на ее заводе. Заказ должен быть выполнен в ближайшие 24 часа, а время на выполнение одного рейса до заказчика и обратно составляет 8 часов. Фирма располагает четырьмя грузовиками, но имеет возможность арендовать у фирмы Gilder Rent-A-Truck еще три грузовика. Грузоподъемность (в т.) и эксплуатационные расходы (за один рейс) для каждого грузовика указаны в таблице.

Всего было заказано 200 т. кирпича. Определить схему перевозки, имеющую минимальную стоимость.