umk_2001_028
.pdfМИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ УРАЛЬСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ им. А. М. ГОРЬКОГО
ЗАДАЧИ И УПРАЖНЕНИЯ ПО ДИСКРЕТНОЙ ОПТИМИЗАЦИИ
Екатеринбург Издательство Уральского университета
2001
Подготовлено кафедрой математической экономики
С о с т а в и т е л ь Л. И. Крутова
©Л. И. Крутова, составление, 2001
©Уральский государственный университет, 2001
Утверждено учебно-методической комиссией математико-механического факультета 15 мая 2001 г.
Издание предназначено для проведения практических занятий по курсу дискретной оптимизации, контрольных мероприятий и самостоятельной работы студентов математико-механического факультета. Приводятся задачи по следующим темам:
–алгоритмы поиска в графе;
–кратчайшие пути в сетях;
–построение минимального остова графа;
–паросочетания в двудольных графах;
–задача об оптимальном назначении;
–задача о максимальном потоке и ее приложения;
–задача коммивояжера.
Решение задач и упражнений требует знания теоретических основ алгоритмов на графах и сетях, применения различных приемов программирования. Многие задачи могут быть интересны и полезны не только студентам-математикам, но и представителям других специальностей.
Некоторые задачи составлены с использованием уже опубликованных материалов, приведенных в списке литературы. Часть задач использовалась для тренировок национальной сборной России к международным соревнованиям по программированию и предлагалась на различных соревнованиях, в частности, на командных чемпионатах Урала и в полуфинальных соревнованиях Северовосточного европейского региона ACM 1998–1999 гг.
Информация по олимпиадным задачам содержалась на: http://acm.timus.ru
http://contest.ur.ru
http://informatics.vspu.kirov.ru/anton
3
1.ПОИСК В ГРАФЕ
1.1.Доказать, что сумма степеней вершин графа G = (V, E) равна 2m, где m – число ребер графа.
1.2.Доказать, что число вершин нечетной степени в любом графе
четно.
1.3.Граф G = (V, E) называется двудольным, если существует разбиение V = XИY, XЗY = Ж, такое что каждое ребро eОE имеет вид e={x, y}, xОX, yОY. Предложить два алгоритма, проверяющих, будет ли данный граф двудольным, за время O(n+m) – один, основанный на поиске в глубину, другой – на поиске в ширину.
1.4.Доказать, что граф является двудольным тогда и только тогда, когда он не содержит простых циклов нечетной длины (длина цикла определяется числом ребер).
1.5.Докажите, что дерево является двудольным графом.
1.6.Использовать алгоритмы поиска в глубину и поиска в ширину для получения числа компонент связности неориентированного графа и самих компонент связности, представленных списками вершин.
1.7.Написать два алгоритма, проверяющих за время O(n+m) ацикличность данного графа G =( V, E), где V – вершины, E – ребра, |V| = n, |E| = m.
1.8.В заданном лабиринте найти путь между двумя данными узлами: провести ломаную, проходящую через свободные узлы лабиринта, звенья которой горизонтальны или вертикальны. Под лабиринтом понимается матрица из n строк и m столбцов, состоящая из нулей и единиц. Узел лабиринта – элемент матрицы. Ноль соответствует свободной точке лабиринта, единица – занятой. Даны координаты «входа» и «выхода» (номер строки, номер столбца). Задан также порядок просмотра узлов лабиринта (4 направления), например:
|
|
Написать программы поиска пути в лабирин- |
3 |
|
|
|
те, используя методы решения: 1) поиск в глуби- |
|
1 ∙ |
2 |
ну; 2) поиск в ширину. Каким свойством будет |
4обладать путь в лабиринте, построенный поиском в ширину?
1.9.Программно реализовать алгоритм построения минимального по числу изгибов пути в лабиринте.
1.10.На шахматной доске стоят белый конь и черная пешка. Определить маршрут коня, заверша-
ющийся уничтожением черной пешки. |
|
|
|
1 |
2 |
||
Пешка неподвижна, конь не должен по- |
|||
|
|
||
8 |
3 |
||
падать под удар пешки. Рассмотреть два |
|||
|
|
||
|
Ê |
||
алгоритма, используя поиск в глубину и |
|
||
поиск в ширину, при следующем поряд- |
7 |
4 |
|
ке просмотра полей: |
6 |
5 |
1.11.«Дельта-волна». На треугольном поле, устроенном так, как показано на рисунке, клетки пронумерованы последовательными натуральными числами от единицы до бесконечности. Путешественнику требуется пройти из клетки с
номером M в клетку с номером N. Путешественник может попадать в соседние клетки только через ребра треугольников (не через вершины). Количество ребер, которое ему нужно будет пересечь в пути, называется длиной маршрута. Напишите программу, которая вычисляет длину кратчайшего маршрута для заданных точек M и N. Числа M, N – натуральные, не менее еди-
ницы и не более 1 млрд.
1.12.«Кубик в лабиринте». На прямоугольном поле из X на Y квадратных клеток находится куб со стороной, равной длине стороны клетки. За один ход куб может перекатываться через ребро, перемещаясь на соседнюю по вертикали или горизонтали клетку. Между некоторыми клетками могут стоять стенки, которые являются препятствиями. Куб не может перекатываться через препятствия. Куб также не может покидать пределы поля. Требуется определить минимальное число ходов, необходимых для того, чтобы переместить куб из заданной начальной клетки с координатами A и B в заданную конечную клетку с координатами C и D. При этом в конечном положе-
4 |
5 |
нии верхняя грань должна быть та же, что и в начальном положении. Напишите программу, определяющую минимальное число ходов. Ограничения: все числа натуральные; 2≤X,Y≤10.
В первой строке входного файла IN.TXT указаны размеры поля X (по горизонтали) и Y (по вертикали), отделенные друг от друга одним или несколькими пробелами. Таким же образом во второй строке указаны A и B, а в третьей – C и D. Далее может следовать (а может и не следовать) информация о стенках.
После символа ‘v’, расположенного в отдельной строке, перечисляются пары чисел, говорящие о вертикальных стенках. Здесь пара чисел N и M определяет стенку между клетками N, M и N+1, M. Каждая пара чисел расположена в отдельной строке. Пустых строк между парами нет.
После символа ‘h’, стоящего в отдельной строке, перечисляются (таким же образом) пары чисел, говорящие о горизонтальных стенках. Пара чисел N и M определяет стенку между клетками N, M и N, M+1.
Выходной файл OUT.TXT должен содержать минимальное число ходов, а при невозможности перемещения – сообщение «Нет решения».
Пример входного и выходного файлов
IN.TXT |
OUT.TXT |
10 2 |
11 |
1 1
10 1 v
2 1
6 2 h
41
1.13.«Минимальное покрытие». Среди заданного множества
отрезков прямой с целочисленными координатами концов [Li, Ri] необходимо выбрать подмножество наименьшей мощности, целиком покрывающее отрезок [0, M], где M – натуральное число. Предложите алгоритм сложности O(M+i), где i – число отрезков, напишите про-
грамму.
Ограничения: 1≤M≤5000; | Li |, | Ri | ≤50000; i≤100000.
Âпервой строке входного файла IN.TXT указана константа M.
Âпоследующих строках перечислены пары чисел Li Ri , каждая пара с новой строки, числа в парах отделены друг от друга одним или несколькими пробелами. Список завершается парой чисел 0 0.
Программа должна формировать в первой строке выходного файла OUT.TXT требуемое минимальное число отрезков из исходного множества, необходимое для покрытия отрезка [0, M]. Далее должен следовать список покрывающего подмножества, упорядоченный по возрастанию координат левых концов отрезков. Список отрезков выводится в том же формате, что и во входном файле IN.TXT, завершающую пару [0,0] выводить не следует.
Если покрытие отрезка [0, M] исходным множеством отрезков
[Li, Ri] невозможно, то файл OUT.TXT должен содержать единственную фразу «Нет решения».
Примеры входного и выходного файлов
IN.TXT |
IN.TXT |
1 |
1 |
–1 0 |
–1 0 |
–5 –3 |
0 1 |
2 5 |
0 0 |
0 0 |
|
OUT.TXT |
OUT.TXT |
Нет решения |
1 |
|
0 1 |
1.14. «ПсевдоГо». Играют на доске 8 на 8 клеток. Два игрока – один белыми камнями (W), другой – черными (B). Каждый ход заключается в выкладывании одного своего камня на доску. Цель игры – захватить камень соперника. Захватить камень соперника значит окружить его своими камнями по вертикали и горизонтали. Доска слева показывает три захваченных белых камня. Необходимо также отслеживать группы камней. Группа – это камни одного цвета, которые касаются друг друга вертикально или горизонтально. Группа считается захваченной в тех же случаях, что и одиночный камень, т. е. вокруг нее (во всех соседних клетках по вертикали и горизонтали) стоят камни другого цвета. Доска справа показывает две захваченных группы белых камней и одну не захваченную (в углу). В «ПсевдоГо» захваченные камни остаются и играют так же, как и остальные.
6 |
7 |
WB..BWB. |
WWB.BWWB |
B....B.. |
B....BB. |
........ |
........ |
...BB... |
....BB.. |
...BWB.. |
...BWWB. |
....B... |
...BWB.. |
........ |
....B... |
........ |
........ |
Программа должна считать из входного файла расстановку камней на доске. Так как неизвестна очередность хода, необходимо найти и вывести лучшие варианты следующего хода для белых, а затем в той же (исходной) позиции и для черных. Лучший ход – тот, которым захватывается самая большая по количеству камней группа противника, которая до этого хода не была захвачена. При этом может быть захвачено сразу несколько групп камней – засчитывается только максимальная. Если таких ходов несколько – выведите все, если их нет, выведите символ N. Играть дальше и делать сам ход не надо.
Входной файл: расстановка камней на доске. В первых строках идет перечисление позиций белых камней в формате <номер столбца> <номер строки>. Оба номера от 1 до 8. Потом идут два числа 0. В следующей строке начинается аналогичное перечисление позиций черных камней, заканчивающееся также двойным нулем.
Файл выходных данных: лучшие варианты хода для белых (в одну строку) в формате <номер столбца> <номер строки>, или буква N, если таких нет; в следующей строке – то же самое для черных. Ходы должны быть сортированы в порядке возрастания столбцов, а при их
совпадении – в порядке возрастания строк. |
|
|
||||||
Пример входных данных |
|
|
|
|
||||
1 |
1 |
1 2 |
3 3 |
3 1 |
4 2 |
|
|
|
5 5 |
2 7 |
1 8 |
2 3 |
1 6 |
3 8 |
1 4 |
0 0 |
|
2 1 |
2 2 |
3 2 |
5 4 |
4 5 |
6 5 |
2 6 |
1 3 |
|
1 |
7 |
2 8 |
0 0 |
|
|
|
|
|
Пример выходных данных |
|
|
|
|
||||
N |
|
|
|
|
|
|
|
|
1 |
5 |
3 1 |
3 7 |
5 6 |
|
|
|
|
Рассмотрите случай, когда засчитываются все камни из захваченных групп.
1.15.Центральная вершина графа G=(V, E) – это такая вершина u, что значение max{d(u, v): v V} является наименьшим из возможных, где d(u, v) – расстояние между u и v. Покажите, что дерево имеет либо одну центральную вершину, либо две смежные центральные вершины.
1.16.Каждому из N работников предприятия присвоили личный табельный номер – целое число от 1 до N и сообщили его, а затем поручили секретарю разослать по почте удостоверения с личными номерами. Но секретарь разложила их по конвертам случайным образом. Для восстановления порядка, когда у работника находится удостоверение с его номером, необходимо организовать обмен удостоверений. Каждый работник может обменять в один день удостоверение, которое находится у него, на другое удостоверение только с одним другим работником. В один день могут обмениваться удостоверениями любое количество пар работников. Известно общее число работников предприятия и для каждого работника – номер удостоверения, которое работник получил по почте. Найти минимальное количество дней, необходимое для того, чтобы все работники получи- ли свои удостоверения.
1.17.Имеется N человек (1≤N≤1000). Каждому приписано некоторое число, которое определяет количество человек, с которыми ему предписано познакомиться. При этом знакомство взаимно, т. е., если человек с номером i знакомится с человеком с номером j, то и человек с номером j знакомится с человеком с номером i. Необходимо так организовать знакомства, чтобы после их реализации люди могли быть разбиты на 2 команды таким образом, что в первой команде находятся люди, знакомые друг с другом (каждый знает каждого), а во второй – только незнакомые (никто никого не знает). При этом численность первой команды должна быть максимальна.
1.18.«Дефрагментация». В файловой системе операционной системы «Новое поколение» все дисковое пространство делится на N кластеров одинакового размера, пронумрованных целыми числами от 1 до N. Каждый файл занимает один или более кластеров в любом месте диска. Все кластеры, которые не заняты файлами, считаются свободными. Файл может быть считан наиболее быстрым способом, если все его кластеры располагаются в следующих один за другим дисковых кластерах в естественном порядке.
8 |
9 |
Вращение диска с постоянной скоростью приводит к тому, что для доступа к кластерам требуется различное время. Поэтому чтение кластеров, находящихся близко к началу диска, выполняется быстрее, чем чтение находящихся близко к концу. Все файлы заранее нумеруются целыми числами от 1 до К в порядке убывания частоты доступа. При оптимальном размещении файлов на диске файл номер 1 будет занимать кластеры 1, 2, ..., S1, файл номер 2 займет кластеры S1+1, S1+2, ..., S1+S2 и т. д. (здесь Si является числом кластеров, которые занимает i-й файл).
Для того чтобы разместить файлы на диске оптимально, выполняется операция перемещения кластеров. Операция перемещения одного кластера включает чтение одного занятого кластера с диска в память и запись его содержимого в некоторый свободный кластер. После этого первый из них объявляется свободным, а второй объявляется занятым. Ваша цель – разместить файлы на диске оптимально, выполнив минимальное число операций перемещения кластеров.
Входные данные
Первая строка входного файла содержит два натуральных числа N и K, разделенных пробелом (1≤K<N≤10000). Затем следуют K строк, каждая из которых описывает один файл. Описание i-го файла начи- нается с числа Si , представляющего число кластеров в данном i-м файле (1≤Si<N). Далее идут Si целых чисел, разделенных пробелами, которые указывают номера кластеров i-го файла на диске в естественном порядке. Все номера кластеров различны, и всегда имеется хотя бы один свободный кластер на диске.
Выходные данные
Ваша программа должна написать в выходной файл любую последовательность операций перемещения кластеров, которая требуется для размещения файлов оптимальным способом. Целые числа Pj è Qj, разделенные пробелом, показывают, какой кластер куда помещается.
Число операций перемещения кластеров должно быть минимальным. Если файлы на диске уже размещены оптимально, то в выходной файл надо записать единственную строку «No optimization needed».
Пример 1 входного файла
20 3
4 2 3 11 12
1 7
3 18 5 10
Пример1 выходного файла
2 1
3 2
113
124
186
108
5 20
7 5
207
Пример 2 входного файла
30 4
2 1 2
3 3 4 5
2 6 7
8 8 9 10 11 12 13 14 15
Пример 2 выходного файла
No optimization needed
1.19. Использовать алгоритм с возвратом для нахождения размещения 8 взаимно не нападающих друг на друга ферзей на шахматной доске.
2.ЗАДАЧА О МИНИМАЛЬНОМ ОСТОВЕ
2.1.Найти минимальный остов для графа, показанного на рисунке двумя алгоритмами: Борувки – Краскла и Ярника – Прима – Дейкстры.
|
|
2 |
1 |
5 |
6 |
7 |
|
2 |
|
|
|||
|
2 |
3 |
4 |
|
5 |
|
|
|
|
||||
|
5 |
|
1 |
6 |
|
|
1 |
3 |
|
|
|||
|
7 |
6 |
7 |
|
|
|
|
4 |
|
|
|
||
|
|
|
|
|
|
2.2. Дорожное управление планирует строительство автомобильных дорог, которые соединят пять населенных пунктов. Все эти пункты должны быть соединены друг с другом либо непосредственно, либо дорогой, проходящей через другой пункт. Затраты (в миллионах
10 |
11 |
рублей) на строительство дорог приводятся в таблице. Какие дороги следует построить?
|
|
|
В пункт |
|
|
||
|
|
A |
B |
C |
D |
E |
|
|
|
|
|
|
|
|
|
|
A |
– |
70 |
50 |
30 |
10 |
|
|
|
|
|
|
|
|
|
Èç |
B |
70 |
– |
20 |
40 |
60 |
|
|
|
|
|
|
|
||
C |
50 |
20 |
– |
25 |
30 |
||
пункта |
|||||||
|
D |
30 |
40 |
25 |
– |
40 |
|
|
|
|
|
|
|
|
|
|
E |
10 |
60 |
30 |
40 |
– |
|
|
|
|
|
|
|
|
|
2.3. Телефонная компания арендовала место, обозначенное узлом 1 для основного центра связи, и определила расположение дополнительных центров (узлы 2, 3, …, 7). Необходимо проложить кабель так, чтобы каждый дополнительный центр связи был связан с основным либо непосредственно, либо через другие дополнительные центры. В целях экономии компания стремится израсходовать кабеля как можно меньше. Расстояния между центрами даны в таблице:
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
1 |
– |
10 |
20 |
30 |
30 |
20 |
50 |
|
|
|
|
|
|
|
|
2 |
10 |
– |
15 |
40 |
60 |
30 |
20 |
|
|
|
|
|
|
|
|
3 |
20 |
15 |
– |
30 |
50 |
10 |
20 |
|
|
|
|
|
|
|
|
4 |
30 |
40 |
30 |
– |
20 |
70 |
10 |
|
|
|
|
|
|
|
|
5 |
30 |
60 |
50 |
20 |
– |
20 |
60 |
|
|
|
|
|
|
|
|
6 |
20 |
30 |
10 |
70 |
20 |
– |
40 |
|
|
|
|
|
|
|
|
7 |
50 |
20 |
20 |
10 |
60 |
40 |
– |
|
|
|
|
|
|
|
|
2.4.Доказать, что если вес дерева представляет собой монотонно возрастающую симметричную функцию, зависящую от реберных весов, то остовное дерево, минимизирующее эту весовую функцию, должно быть тем же самым кратчайшим остовом (вес которого минимизирует сумму весов ребер).
2.5.В графе каждая вершина представляет некоторое лицо, а реб-
ðà {vi, vj} отражают тот факт, что лицо vi может общаться с лицом vj и наоборот. Требуется определить такой способ передачи конфиденциального сообщения между 12 лицами, при котором вероятность утечки
информации будет наименьшей. Каждой передаче сообщения от vi ê vj приписывается некоторая вероятность pij того, что послание может быть перехвачено посторонним лицом. Эти вероятности в процентах даны в таблице:
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
6 |
|
|
5 |
|
|
|
|
|
|
|
2 |
6 |
|
15 |
18 |
8 |
|
11 |
|
|
|
|
|
3 |
|
15 |
|
8 |
|
|
|
18 |
6 |
|
|
|
4 |
|
18 |
8 |
|
|
10 |
7 |
|
|
|
17 |
|
5 |
5 |
8 |
|
|
|
15 |
9 |
|
|
|
|
|
6 |
|
|
|
10 |
15 |
|
|
|
|
|
3 |
|
7 |
|
11 |
|
7 |
9 |
|
|
9 |
4 |
13 |
12 |
|
8 |
|
|
18 |
|
|
|
9 |
|
14 |
|
|
5 |
9 |
|
|
6 |
|
|
|
4 |
14 |
|
19 |
|
|
10 |
|
|
|
|
|
|
13 |
|
19 |
|
|
2 |
11 |
|
|
|
17 |
|
3 |
12 |
|
|
|
|
7 |
12 |
|
|
|
|
|
|
|
5 |
|
2 |
7 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2.6.Предложить алгоритм построения остова максимального веса.
2.7.В графе с положительными весами ребер любое множество ребер, связывающее все вершины и обладающее минимальным суммарным весом (среди подмножеств, связывающих все вершины), является деревом. Приведите пример, показывающий, что это не так, если веса ребер могут быть отрицательные.
2.8.Пусть T – минимальный остов графа G. Составим упорядо- ченный список всех ребер остова T. Покажите, что для любого другого минимального остова получится тот же самый список.
2.9.Пусть в связном неориентированном графе G=(V, E) ребра разделяются на два класса: класс «плохих» и класс «хороших» ребер. Предложите алгоритм сложности О(m), строящий остов такого графа с минимально возможным количеством «плохих» ребер.
12 |
13 |
2.10.Исследовать min-max задачу построения остова. А именно, весом остова T графа G считаем число c(T)=max{c(e): e T}. Требуется найти остов минимального веса. Аналогично сформулируйте и исследуйте max-min задачу построения остова.
2.11.Пусть M – множество точек на плоскости. Рассмотрим граф, вершинами которого являются точки множества М, все они считаются смежными, а веса ребер равны расстоянию между соответствующими точками. Минимальный остов этого графа называется минимальным связывающим деревом (МСД) множества М. Предложите алгоритм построения МСД множества М сложности O (n logn), где n=|M|.
Докажите, что степень вершины в МСД не более 6, если рассматривается евклидова метрика, и не более 8, если рассматривается прямоугольная метрика: d(x,y)=|x1–y1| + |x2–y2|.
3.ПУТИ В СЕТЯХ
3.1.Почтовому ведомству требуется определить наиболее экономные маршруты доставки писем из заданного города в каждый другой город, отмеченный на изображенной ниже карте. Числа, приписанные звеньям сети, указывают приближенные транспортные затраты на выполнение соответствующих рейсов. Найти пути минимальной стоимости.
1 |
|
12 |
|
|
|
|
|
|
2 |
3 |
|
||
25 |
|
|
|
|||
|
|
|
||||
|
|
9 |
|
|||
|
|
|
|
|||
|
|
|
|
|
||
|
|
18 |
|
|
8 |
|
3 |
|
|
4 |
5 |
||
|
|
|
|
|||
|
|
5 |
11 |
21 |
2 |
|
|
|
|
|
|
||
|
|
|
6 |
|
7 |
|
|
|
|
4 |
|||
|
|
|
|
|
|
|
3.2. Города A и B соединены одним скоростным шоссе. Агентство автомобильных перевозок решило оценить минимальную стоимость проезда между ними на автомобиле. Агентство располагает списком довольно большого числа заправок по дороге из A в B, кроме того, для каждой заправки из этого списка знает ее размещение на
трассе и стоимость бензина на ней. Предполагается, что обычно водитель ведет себя следующим образом:
1)всегда выезжает из города А с полным баком;
2)заехав на заправку, он всегда доливает бак до полного (при этом учитываются и доли литра бензина);
3)никогда не останавливается на заправке, если бак полон более чем наполовину (кроме тех случаев, когда иначе он не сможет доехать до следующей заправки);
4)сумма, уплачиваемая водителем на заправке, всегда округляется до ближайших 10 к.;
5)на каждой заправке, где он остановился, водитель тратит 20 р. на покупку еды.
Первая строка входного файла содержит действительное число – расстояние от А до B (в километрах). В следующей строке – четыре числа – соответственно емкость бака в литрах (целое); число километров, проезжаемое на одном литре (целое); деньги, затраченные на заправку в городе A (в рублях с копейками); и число N<91 – коли- чество заправок в списке. Далее следуют N строк, в каждой из которых стоят два числа – расстояние от города А до этой заправки (целое число километров) и стоимость бензина на ней (в рублях за литр). Заправки упорядочены по возрастанию расстояния от города А.
Выходной файл должен содержать минимальную стоимость поездки в рублях, округленную до ближайших 10 к., во второй строке – последовательность заправок, которые водителю надо посетить.
Пример входных данных
400
40 6 120.50 2
160 5.20
240 3.40
Пример выходных данных
276.50
2
3.3. В стране N городов, в каждом из которых есть аэропорт. Авиакомпания, занимающаяся перевозкой грузов, имеет самолет и желает максимально выгодно его использовать. Для некоторых пар городов (A, B) известны время перелета из A в B и сумма выручки за доставку груза из A в B. Напишите программу, которая по этим данным нахо-
14 |
15 |
дит для самолета замкнутый путь, максимизирующий среднюю выручку за единицу времени.
Считается, что самолет может вместить не более одного груза, а временем стоянки самолета в аэропорту следует пренебречь.
Входные данные
В первой строке входного файла содержится число городов N (1≤N≤100) и число возможных прямых рейсов M. В каждой из следующих M строк записана четверка чисел (i, j, bij, cij), описывающая возможный рейс между городами i и j со временем перелета bij и выручкой cij. Время перелета и выручка – положительные вещественные числа.
Выходные данные
В первой строке выходного файла должна содержаться средняя выручка за единицу времени, а во второй – замкнутый маршрут, заданный номерами своих вершин в порядке следования, на котором эта максимальная выручка достигается. Первая и последняя вершины маршрута должны совпадать. Входные данные будут таковы, что решение заведомо будет существовать.
Пример входного файла
3 3 1 2 1.0 2.0
2 3 1.0 2.0
3 1 2.0 1.0
Пример выходного файла
1.25
1 2 3 1
3.4.Предложите алгоритм, который бы определял, имеется или нет в данной сети с произвольными весами дуг контур отрицательной стоимости.
3.5.Рассмотрим проект по организации сбыта нового изделия. В таблице приводятся продолжительности работ, необходимых для его выполнения. Найти минимальное время выполнения проекта, резерв времени для каждой работы.
¹ |
|
Продол- |
Предшест- |
|
Работы |
житель- |
вующие |
||
|
||||
|
|
ность |
работы |
|
|
|
|
|
|
0 |
Планирование работ |
3 |
– |
|
1 |
Составление учебного плана |
6 |
0 |
|
|
|
Окончание табл. |
||
|
|
|
|
|
|
¹ |
|
Продол- |
|
Предшест- |
|
Работы |
житель- |
|
вующие |
||
|
|
||||
|
|
ность |
|
работы |
|
|
|
|
|
|
|
2 |
Отбор слушателей |
4 |
|
0 |
|
3 |
Подготовка брошюры |
3 |
|
0 |
|
4 |
Проведение учебных занятий |
1 |
|
1, 2, 3 |
|
5 |
Поставка образцов продукции |
4 |
|
0 |
|
6 |
Печатание брошюры |
5 |
|
3 |
|
7 |
Подготовка рекламных материалов |
5 |
|
0 |
|
8 |
Выпуск рекламных материалов |
1 |
|
7 |
|
9 |
Распространение брошюры |
2 |
|
6 |
|
3.6. Крупный станок состоит из четырех узлов. Узлы 1 и 2 объединяются в узел 4, а соединение узлов 3 и 4 дает готовое изделие. Изза необходимости согласования некоторых деталей узла 3 с деталями узла 2 нельзя собрать узел 3 раньше, чем будут иметься детали для узла 2. Основные работы даны в таблице. Дать сетевую модель и определить время изготовления станка.
|
|
Продол- |
Предшест- |
|
Работы |
житель- |
вующие |
|
|
ность |
работы |
|
|
|
|
A |
Закупка деталей для узла 1 |
5 |
– |
B |
Закупка деталей для узла 2 |
3 |
– |
C |
Закупка деталей для узла 3 |
10 |
– |
D |
Изготовление узла 1 |
7 |
A |
E |
Изготовление узла 2 |
10 |
B |
F |
Изготовление узла 4 |
5 |
D, E |
G |
Изготовление узла 3 |
9 |
B, C |
H |
Окончательная сборка |
4 |
F, G |
I |
Окончательная проверка и испытания |
2 |
H |
3.7. Задача о замене оборудования. Предприятие приобретает новое оборудование. Через n лет планируется его полная замена. Однако может оказаться выгодным заменить оборудование раньше или сделать несколько замен. Даны:
pi – стоимость оборудования в начале i-го года;
16 |
17 |
rk – эксплуатационные расходы в течение k-го года;
sj – ликвидационная стоимость оборудования в начале j-го года. Решение о покупке нового оборудования может приниматься в начале каждого года, исходя из общих затрат Cij. Как организовать замену оборудования с наименьшими затратами? Построить сетевую модель данной задачи. Сформулировать как задачу выбора кратчай-
øåãî ïóòè.
3.8. Фирма приобретает дополнительное оборудование. Через 3 года планируется установка новой автоматизированной линии, после чего оборудование станет ненужным. Однако может оказаться выгодным заменить оборудование через год или два или даже осуществить две замены (через год и через два года). В таблице приведены полные расходы (с учетом стоимости эксплуатации и выручкой от продажи), связанные с покупкой оборудования в конце года i и его продажей в конце года j:
Ãîä |
|
Год продажи |
|
||
|
|
j |
|
||
покупки |
|
|
|
||
|
|
|
|
|
|
i |
1 |
|
2 |
|
3 |
|
|
|
|||
|
|
|
|
|
|
0 |
7 |
|
11 |
|
25 |
1 |
|
|
8 |
|
15 |
2 |
|
|
|
|
9 |
|
|
|
|
|
|
3.9.Автотранспортное предприятие собирается покупать новые автомобили по крайней мере каждые 4 года. Решение о покупке новых автомобилей может приниматься в начале каждого года, исходя из затрат на их приобретение, эксплуатационных расходов на период, в течение которого автомобили будут использоваться, и ликвидационной стоимости машин в момент, когда они заменяются на новые. Когда в течение восьмилетнего периода следует заменять автомобили, чтобы минимизировать общие затраты? Планируемые общие затраты (тыс. дол.) приведены в таблице на с. 19.
3.10.Промышленной компании надо составить план замены оборудования на ближайшие 4 года. На данный период ожидаются следующие расходы и амортизационные стоимости. Существующая цена станка составляет 7000 р. Ожидается ежегодное увеличение цен на станки на 10 %. В первые два года станки изнашиваются на 25 %, а в последующие два года – на 15 %. Издержки на техническое обслужи-
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
1 |
|
14 |
27 |
38 |
47 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
|
|
17 |
32 |
44 |
54 |
|
|
|
|
|
|
|
|
|
|
|
|
|
3 |
|
|
|
18 |
34 |
47 |
58 |
|
|
|
|
|
|
|
|
|
|
|
|
4 |
|
|
|
|
19 |
36 |
50 |
61 |
|
|
|
|
|
|
|
|
|
|
|
5 |
|
|
|
|
|
20 |
38 |
53 |
65 |
|
|
|
|
|
|
|
|
|
|
6 |
|
|
|
|
|
|
22 |
41 |
56 |
|
|
|
|
|
|
|
|
|
|
7 |
|
|
|
|
|
|
|
23 |
43 |
|
|
|
|
|
|
|
|
|
|
8 |
|
|
|
|
|
|
|
|
24 |
|
|
|
|
|
|
|
|
|
|
вание и текущий ремонт в ближайшие 4 года составят 1200, 1500, 1900 и 2400 р. соответственно. Станки можно заменять каждый год или каждые 2, 3 и 4 года. Составить план замены оборудования, при котором общие издержки на ближайшие 4 года были бы минимальными.
3.11. Пролетающие время от времени в ближайшей близости от нашего спутника Луны астероиды захватываются ее гравитационным полем и, будучи ничем не задерживаемы, врезаются с огромной скоростью в лунную поверхность, оставляя в память о себе порядочных размеров кратеры приблизительно круглой формы. Найти максимально длинную цепочку вложенных друг в друга кратеров.
Входные данные: первая строка входного файла содержит целое число N – количество кратеров, отмеченных на карте (1≤N≤500). Следующие N строк содержат описания кратеров с номерами от 1 до N. Описание каждого кратера занимает отдельную строку и состоит из трех целых чисел, принадлежащих диапазону [–32768, 32767] и разделенных пробелами. Первые два числа представляют собой декартовы координаты его центра, а третье – радиус. Все кратеры различны.
Выходные данные: первая строка выходного файла должна содержать длину искомой цепочки кратеров, вторая – номера кратеров из этой цепочки, начиная с меньшего кратера и кончая самым большим. Номера кратеров должны быть разделены пробелами. Если существует несколько длиннейших цепочек, следует вывести любую из них.
Пример входного файла
4
0 0 30 –15 15 20 15 10 5 10 10 10
18 |
19 |