Целевая функция и оптимальное размещение
Целевая функция — величина, которую нужно сделать наименьшей или наибольшей, записанная формулой через выбор, который мы делаем. В задачах о размещении склада она равна сумме стоимостей доставки: число грузов, умноженное на расстояние до каждого пункта. Для файла A её считают перебором всех мест, а для файла B — пересчётом при сдвиге места на соседний пункт.
Как составить и найти целевую функцию
Пункты стоят на дороге в точках , из пункта везут грузов. Склад ставят в одном из пунктов.
- Целевая функция: — стоимость, если склад в пункте . Ответ — наименьшее .
- Число контейнеров вместимостью для предметов — округление вверх: , в Python
(t + V - 1) // V. - На кольце из пунктов расстояние равно .
- Перебор всех с суммой внутри — , только для файла A.
- Сдвиг склада вправо на : , где — сумма весов пунктов до включительно, — остальных.
Целевая функция и ограничения
Математическая модель практической задачи состоит из трёх частей. Переменные — то, что мы выбираем: номер пункта для склада. Ограничения — условия, которым выбор обязан удовлетворять: склад стоит в одном из пунктов, контейнер вмещает не больше предметов. Целевая функция — величина, которую нужно сделать наименьшей или наибольшей, записанная формулой через переменные.
Для склада на прямой дороге стоимость доставки из пункта — число грузов , умноженное на расстояние . Целевая функция — сумма этих стоимостей по всем пунктам: . Составьте её по условию и проверьте на примере из условия, прежде чем писать быструю программу.
Пример
Магазины стоят на дороге на 2-м, 5-м и 9-м километре, им нужно 4, 2 и 3 доставки. Склад ставят у одного из магазинов, стоимость — число доставок, умноженное на расстояние. Где поставить склад?
- 1..
- 2..
- 3..
- 4.Наименьшая стоимость 24 у магазина на 5-м километре. Программа печатает три пары: место и стоимость.
Ответ: 5-й километр, стоимость 24
Число контейнеров: округление вверх
Если предметы везут в контейнерах вместимостью , а неполный контейнер всё равно едет целиком, число контейнеров для предметов — округление вверх: . Это вес пункта в целевой функции. Деление t // V округляет вниз и теряет неполный контейнер.
В целых числах округление вверх записывают как (t + V - 1) // V. Если делится на , прибавка не даёт нового контейнера, иначе даёт ровно один.
Пример
Контейнер вмещает 36 пробирок. Сколько контейнеров нужно для 100, 72, 73 и 5 пробирок?
- 1.100: , два полных контейнера и один на 28 пробирок.
- 2.72: , ровно два полных.
- 3.73: , одна пробирка требует третьего контейнера.
- 4.5: . Программа печатает те же числа.
Ответ: 3, 2, 3 и 1
Перебор всех мест
Самая простая программа перебирает все пункты и для каждого считает циклом по всем пунктам. Это шагов: для файла A из сотни строк — мгновенно, для файла B из миллионов строк — слишком долго, подробнее в теме файл A и файл B. Перебор нужен, чтобы проверить быструю программу на файле A и на примере из условия.
Пример
Пункты на 1-м, 2-м, 5-м, 7-м, 8-м и 10-м километре сдают 100, 200, 4, 3, 2 и 190 пробирок, контейнер вмещает 96 пробирок. Лабораторию ставят в одном из пунктов, стоимость — число контейнеров, умноженное на расстояние. Найдите наименьшую стоимость.
- 1.Числа контейнеров: 2, 3, 1, 1, 1, 2.
- 2.Для лаборатории на 2-м километре: .
- 3.Для лаборатории на 5-м километре стоимость тоже 32, для остальных пунктов она больше. Программа читает данные из файла и печатает 32.
f = open('27_A.txt')cap = 96n = int(f.readline())x = []w = []for i in range(n): p, t = map(int, f.readline().split()) x.append(p) w.append((t + cap - 1) // cap)best = Nonefor j in range(n): cost = sum(w[i] * abs(x[i] - x[j]) for i in range(n)) if best is None or cost < best: best = costprint(best)
Ответ:
Расстояние на кольцевой дороге
На кольцевой трассе длиной с пунктами через 1 км можно ехать в обе стороны. Между пунктами и по одной стороне км, по другой км, и машина едет по короткой: расстояние равно . Целевая функция та же сумма, только с этим расстоянием. Быстрый расчёт для кольца разобран в теме кольцо: утроенный список.
Пример
На кольце длиной 6 км пункты стоят на каждом километре, им нужно 8, 20, 5, 13, 7 и 19 комплектов. Стоимость — число комплектов, умноженное на расстояние. В каком пункте поставить цех?
- 1.Для цеха в пункте 6 расстояния до пунктов 1–5 равны 1, 2, 3, 2, 1: до пунктов 1 и 2 короче ехать вперёд через нулевой километр.
- 2..
- 3.Программа перебирает все шесть пунктов и печатает 6 96: меньше 96 нет.
Ответ: пункт 6, стоимость 96
Пересчёт стоимости при сдвиге склада
Пусть пункты упорядочены по возрастанию . Сдвинем склад из пункта в соседний пункт , на км. Все пункты до включительно стали дальше на , а пункты от — ближе на . Поэтому , где — сумма весов пунктов до включительно, — сумма весов остальных.
Посчитайте для первого пункта одним циклом, затем идите вправо и пересчитывайте , и за несколько действий. Вся программа — . Стоимость убывает, пока меньше , поэтому лучшее место — первый пункт, на котором сумма весов от начала до него включительно доходит до половины общей суммы.
f = open('27_A.txt')cap = 36n = int(f.readline())x = []w = []for i in range(n): p, t = map(int, f.readline().split()) x.append(p) w.append((t + cap - 1) // cap)cost = 0for i in range(n): cost += w[i] * (x[i] - x[0])best = costleft = 0right = sum(w)for i in range(n - 1): left += w[i] right -= w[i] cost += (x[i + 1] - x[i]) * (left - right) best = min(best, cost)print(best)
Пример задания
Открытый банк ФИПИ
У медицинской компании есть N пунктов приёма биоматериалов на анализ. Все пункты расположены вдоль автомагистрали и имеют номера, соответствующие расстоянию от нулевой отметки до конкретного пункта. Известно количество пробирок, которое ежедневно принимают в каждом из пунктов. Пробирки перевозят в специальных транспортировочных контейнерах вместимостью не более 36 штук. Каждый транспортировочный контейнер упаковывается в пункте приёма и вскрывается только в лаборатории. Стоимость перевозки биоматериалов равна произведению расстояния от пункта до лаборатории на количество контейнеров с пробирками. Общая стоимость перевозки за день равна сумме стоимостей перевозок из каждого пункта в лабораторию. Лабораторию расположили в одном из пунктов приёма биоматериалов таким образом, что общая стоимость доставки биоматериалов из всех пунктов минимальна. Определите минимальную общую стоимость доставки биоматериалов из всех пунктов приёма в лабораторию.
Входные данные
Дано два входных файла (файл A и файл B), каждый из которых в первой строке содержит число N (1 ≤ N ≤ 10 000 000) – количество пунктов приёма биоматериалов. В каждой из следующих N строк находится два числа: номер пункта и количество пробирок в этом пункте (все числа натуральные, количество пробирок в каждом пункте не превышает 1000). Пункты перечислены в порядке их расположения вдоль дороги, начиная от нулевой отметки.
В ответе укажите два числа: сначала значение искомой величины для файла А, затем – для файла B.
Типовой пример организации данных во входном файле
6
1 100
2 200
5 4
7 3
8 2
10 190
При таких исходных данных и вместимости транспортировочного контейнера, составляющей 96 пробирок, компании выгодно открыть лабораторию в пункте 2. В этом случае сумма транспортных затрат составит: 1 ꞏ 2 + 3 ꞏ 1 + 5 ꞏ 1 + 6 ꞏ 1 + 8 ꞏ 2.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.
Предупреждение: для обработки файла B не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.