Организация приема Деда Мороза
За 100 дней до Рождества Санта открыл мастерскую, и семейные визиты приветствуются, как организовать эти семейные визиты более разумно?
У каждой семьи есть 10 вариантов выбора от 0 до 9, число представляет количество дней до Рождества, например, 1 для 24 декабря, каждая семья должна организовать только одно посещение.
Количество семей — 5000, то есть family_id — [0, 4999], а количество посетителей в день должно быть в пределах 125-300.
Идеи решения проблем
Чтобы более обоснованно рассчитать организационные способности Санты, мы используем два показателя: стоимость предпочтения и штраф за учет.
1) Предпочтительная стоимость, отражающая персональные возможности Санта-Клауса.
2) бухгалтерский штраф, который представляет собой финансовые затраты на организацию Деда Мороза.
Если количество людей, принимаемых в день, N(d) больше 125, это будет переполнено, что приведет к чрезмерным затратам на уборку.Формула расчета:
Где N(d) представляет текущий день, а N(d+1) представляет предыдущий день (поскольку N представляет количество дней до Рождества)
Окончательная оценка = стоимость предпочтения + бухгалтерский штраф
Окончательная подача договоренностей для каждой семьи submit.csv
Этапы реализации кода
Шаг 1, загрузка данных
Шаг 2, предварительная обработка данных
1) Рассчитайте матрицу Perference Cost pcost_mat
2) Рассчитайте матрицу бухгалтерских затрат acost_mat
3) Подсчитайте количество человек в каждой семье FAMILY_SIZE.
4) Склонность каждой семьи к выбору (выбор_) ЖЕЛАЕМЫЙ
Step3, используйте LP и MIP для решения схемы планирования
1) Сначала используйте LP для планирования для большинства семей
2) Используйте MIP для планирования остальных семейств.
3) Обобщить результаты обеих сторон => окончательная схема планирования
Шаг 4, оценка результатов
В соответствии со стандартом оценки рассчитать
Score = preference cost + accounting penalty
Шаг 5, оптимизация программы
Найдите лучший результат, изменив выбор family_id
После каждого изменения план оценивается и выбирается меньший план оценки.
%%time в jupyter может указать время для однократного запуска кода ячейки
np.sort(a), сортировать по возрастанию
np.argsort(a), возвращает индекс массива от меньшего к большему
@njit(fastmath=True)
numba — это интерактивный компилятор для python, при вызове функции python код заменяется выполнением машинного кода
Numba может ускорить функции Python с большой вычислительной нагрузкой
@njit означает, что все используют ускорение
fastmath=True, включает быстрое математическое поведение функции
считать
Исследование операций имеет простую идею решения, но трудно найти удовлетворительные результаты.
Текущая идея решения похожа на исчерпание грубой силы, и пространство для решения очень огромно => Невозможно получить лучшие результаты за ограниченное время.
Для задач выпуклой оптимизации (таких как линейное программирование) оптимальное решение может быть получено напрямую.
Если это невыпуклая оптимизация, невозможно определить, является ли это глобальным оптимальным решением или локальным оптимальным решением.В промышленности обычно используются эвристические алгоритмы, такие как генетические алгоритмы.
Метод ветвей и границ , основной принцип эвристического алгоритма - улучшение исчерпания грубой силы, максимальное сокращение пространства поиска и более быстрое получение возможных решений.