|
Рис.
Схема возможных
маршрутов движения
Постройте кольцевой маршрут проезда всех городов минимальной длины
по данным матрицы расстояний:
1
2
3
4
5
6
1
∞
0,4 1,1 2,9 1,5 1,2
2
0,2 ∞
0,2 2,9 1,9 1,6
3
1
2,2 ∞
1,8 1,6 2,4
4
3
2,5 2
∞
3,2 4,4
5
2,1 2,6 2,7 4
∞
2
6
3,1 2,3 3
5
1,3 ∞
20. Курьер работает в Красногорске. Ему нужно доставить документы в
Тушино, Строгино, поселок Архангельское и в госпиталь им. Вишневского, после
чего вернуться в офис. Необходимо составить кратчайший (в км) маршрут объез-
да этих населенных пунктов, матрица расстояний (в км) представлена ниже.
Рис.
Схема возможных
маршрутов движения
169
1
2
3
4
5
1
∞
9
11
8,5 11
2
9
∞ 11
3
15
3
11 11
∞ 9,5 10
4
8,5
3
9,5
∞ 14
5
11 15 10
14
∞
21. Торговому представителю оптической фирмы «Око» необходимо, вы-
летев из Москвы (1), посетить выставки в следующих городах: Новосибирск
(2), Якутск (3), Хабаровск (4), Владивосток (5), Пекин (6). Воспользовавшись
услугами туристического агентства Global Travel, торговый представитель дол-
жен составить кольцевой маршрут с минимальными затратами.
Таблица
Пункты маршрута, расстояния и стоимость проезда
Travel
Расстояние, км
Стоимость, евро
Москва — Новосибирск
2 800
170
Москва — Якутск
4 900
280
Москва — Пекин
5 700
400
Москва — Владивосток
6 400
350
Москва — Хабаровск
6 125
300
Новосибирск — Якутск
2 700
160
Новосибирск — Хабаровск
3 600
210
Новосибирск — Пекин
2 950
190
Новосибирск — Владивосток
3 680
210
Якутск — Хабаровск
1 580
110
Якутск — Владивосток
2 100
150
Якутск — Пекин
2 650
160
Владивосток — Пекин
1 380
100
Владивосток — Хабаровск
630
60
Хабаровск – Пекин
1780
120
1
2
3
4
5
6
1
∞
2 800
4 900
6 125
6 400
5 700
2
2 800
∞
2 700
3 600
3 680
2 950
3
4 900
2 700
∞
1 580
2 100
2 650
4
6 125
3 600
1 580
∞
630
1 780
5
6 400
3 680
2 100
630
∞
1 380
6
5 700
29 950
2 650
1 780
1 380
∞
22.
Компании MSI необходимо доставить ноутбуки по торговым точкам,
расположенным в районах железнодорожных вокзалов Москвы, используя сле-
дующие станции метро: Савеловская (Савеловский) (1), Рижская (Рижский) (2),
Комсомольская (Ленинградский вокзал) (3), Комсомольская (Ярославский вок-
зал) (4), Комсомольская (Казанский вокзал) (5), Курская (Курский вокзал) (6),
Павелецкая (Павелецкий вокзал) (7), Киевская (Киевский вокзал) (8), Белорус-
ская (Белорусский вокзал) (9). Постройте кольцевой маршрут проезда всех вок-
залов за минимальное время, проезд в минутах показан в матрице:
170
1
2
3
4
5
6
7
8
9
1
∞
13
11
11
11
14
19
13
8
2
13
∞
8
8
8
11
16
16
10
3
11
8
∞
10
10
3
8
13
8
4
11
8
10
∞
10
3
8
13
8
5
11
8
10
10
∞
3
8
13
8
6
14
11
3
3
3
∞
5
14
11
7
19
16
8
8
8
5
∞
9
14
8
13
16
13
13
13
14
9
∞
6
9
8
10
8
8
8
11
14
6
∞
23. Индивидуальному предпринимателю для выполнения заказа необхо-
димо посетить пять городов за минимальное время. Маршрут должен быть за-
мкнут, а каждый пункт доставки должен быть посещен один раз по следующим
городам: Иваново, Рязань, Ярославль, Нижний Новгород, Кинешма. Время про-
езда между городами представлено в таблице.
Таблица
Время проезда между городами
Иваново
Рязань
Ярославль
Нижний
Новгород
Кинешма
Иваново
∞
7 ч 39 мин
3 ч 37 мин
4 ч 48 мин
2 ч 50 мин
Рязань
7 ч 39 мин
∞
8 ч 13 мин
4 ч 45 мин
7 ч 26 мин
Ярославль
3 ч 37 мин
8 ч 13 мин
∞
8 ч 33 мин
4 ч 35 мин
Нижний Но-
вогород
4 ч 48 мин
4 ч 45 мин
8 ч 33 мин
∞
2 ч 37 мин
Кинешма
2 ч 50 мин
7 ч 26 мин
4 ч 35 мин
2 ч 37 мин
∞
24.
Фирме, занимающейся оптовой продажей планшетных компьютеров,
необходимо доставить товар в пять городов наиболее рациональным способом.
Маршрут должен быть замкнутым. В наличии есть только один автомобиль, на
котором можно осуществить доставку в города: Москва, Тула, Владимир, Ли-
пецк, Руза. Время проезда между городами представлено в таблице.
Таблица
Время проезда между городами
Москва
Тула
Владимир
Липецк
Руза
Москва
—
2 ч 30мин
3 ч
5 ч 30 мин
1 ч 50 мин
Тула
2 ч 30мин
—
5 ч 10мин
3 ч 40мин
3 ч 20мин
Владимир
3 ч
5 ч 10мин
—
6 ч 50мин
4 ч 30мин
Липецк
5 ч 30 мин
3 ч 40мин
6 ч 50мин
—
6 ч 40мин
Руза
1 ч 50 мин
3 ч 20мин
4 ч 30мин
6 ч 40мин
—
25. Курьеру необходимо посетить пять пунктов доставки товаров, нахо-
дящихся около разных станций метро Москвы. Маршрут должен быть замкнут,
а каждый пункт должен быть посещен курьером только один раз. Пункты до-
ставки находятся около следующих станций метрополитена: Речной вокзал,
171
Серпуховская, Кантемировская, Парк победы, Домодедовская, ВДНХ, а время
проезда представлено ниже.
1
2
3
4
5
6
1
∞
31
43
33
50
34
2
31
∞
24
16
32
25
3
43
24
∞
35
8
36
4
33
16
35
∞
43
28
5
50
32
8
43
∞
44
6
34
25
36
28
44
∞
26. Представителю компании «Трэйд» необходимо объехать пять городов
на поезде. Маршрут должен быть замкнут, а каждый пункт доставки докумен-
тов может быть посещен представителем только один раз в следующих горо-
дах: Подольск, Тула, Тверь, Нижний Новгород, Санкт-Петербург. Время проез-
да между городами представлено в таблице.
Таблица
Время проезда между городами
Подольск
Тула
Тверь
Нижний
Новгород
Санкт-
Петербург
Подольск
∞
2 ч 53 мин
2 ч 45 мин
5 ч 42 мин
5 ч 50 мин
Тула
2 ч 53 мин
∞
4 ч 30 мин
7 ч 38 мин
7 ч
Тверь
2 ч 45 мин
4 ч 30 мин
∞
7 ч 43 мин
2 ч 54 мин
Нижний
Новогород
5 ч 42 мин
7 ч 38 мин
7 ч 43 мин
∞
14 ч 56мин
Санкт-
Петербург
5 ч 50 мин
7 ч
2 ч 54 мин
14 ч 56мин
∞
7.5. Задачи о раскрое материалов
(минимизация обрезков)
Задача об одной из самых ресурсосберегающих технологий для заготови-
тельного производства, поскольку приводит к экономии материалов и сниже-
нию отходов, линейного раскроя материалов (проволоки, труб, швеллера, про-
филя, уголков, проводов, рулонов материалов на продольные и поперечные по-
лосы и других видов изделий), который обеспечивает необходимый комплект
изделий при минимальных отходах по длине, площади, массе, стоимости. Вы-
краивают одежду, обувь, детали корпуса корабля, кузова автомобиля, фюзеля-
жа самолета.
Промышленное применение задачи оптимального раскроя мате-
риалов для одномерного раскроя (1D) — резка труб, кабелей и стальных прут-
ков, бумажной, пленочной и сталепрокатной промышленностях при изготовле-
нии плоских металлических (железных или бронзовых) листов, фотобу-
172
маги, гофрокартона, металлизированная пленка для упаковки продуктов пита-
ния, покрытая пластиком бумага (упаковочный картон для жидкостей, для упа-
ковки соков); двумерные (2D) — при производстве мебели, одежды и стекла;
трехмерные (3D) — распределение объектов в контейнеры для водного транс-
порта. По данным Конфедерации европейских производителей бумаги в 2012 г.,
1331 бумагоделательных машин производят в среднем отходов на 73 млн дол.
каждая. Экономия даже на 1% будет весьма существенной.
1.
Предприниматель арендовал технологическую линию деревообрабаты-
вающих станков для изготовления вагонки. Магазин «Стройматериалы» заказал
комплекты упаковки из трех элементов: по две вагонки длиной 2 м и одной ва-
гонки длиной 1,25 м. Поставщик завозит на грузовом автомобиле доски толщи-
ной 20 мм, шириной 100 мм, длиной по 6,5 м — 200 шт. и длиной по 4 м —
50 шт.
Рассчитайте, как распилить доски на станках, чтобы продать максималь-
ное количество комплектов с минимальными отходами.
2. Продукция ткацкой фабрики выпускается в виде рулонов ткани шири-
ной 2,20 м и 1,50 м. Длина ткани в рулонах соответственно по 84 м и 120 м. Из
ткани шьют спальные комплекты: односпальные и двуспальные. Цена одно-
спального комплекта — 800 руб., а двуспального — 1000 руб., расход ткани на
изготовление комплектов приведен в таблице. Определите, какое количество
комплектов каждого вида можно изготовить, чтобы получить максимальную
выручку от продажи.
Таблица
Do'stlaringiz bilan baham: |
