Knowledge Sharing. Задачи комбинаторной оптимизации

1.

Knowledge Sharing
Задачи комбинаторной оптимизации

2.

Оптимизация маршрутов (TSP)
Видео о решении задачи TSP на YouTube

3.

Оптимизация маршрутов (VRP)

4.

Оптимизация расписаний

5.

Оптимизация потоков
50
60
30
10
40
40

6.

Методы решения задач оптимизации
Наборы правил, жадные алгоритмы
Быстрая реализация, высокая
скорость работы, низкое качество
Солверы: Linear Programming, Mixed
Integer Programming, Constraint
Programming
Быстрая реализация, низкая скорость
скорость работы, высокое качество
Обучение с подкреплением
Долгая реализация, высокая скорость
работы, среднее качество

7.

Задача
Вы производитель ювелирных изделий. У вас в наличии имеется:
• Драгоценные камни = 500 штук
• Золото = 1.5 кг
• Серебро = 1 кг
Из этих материалов вы производите три типа изделий, каждое из которых требует разного набора ресурсов:
• Кольцо = 1 драгоценный камень + 2г золота
• Ожерелье = 15 драгоценных камней + 4г золота + 1г серебра
• Браслет = 2г золота + 2г серебра
Каждое изделие вы можете продать по определенной цене:
• Кольцо = 7000р
• Ожерелье = 25000р
• Браслет = 10000р
Максимизируйте прибыль и запланируйте свое производство.

8.

Ссылки и ключевые слова
• Google colab: https://colab.research.google.com/
• Python MIP: https://www.python-mip.com/
• Google OR-tools: https://developers.google.com/optimization
• Pyomo: https://www.pyomo.org/
• Gurobi: https://www.gurobi.com/
• Coursers: https://www.coursera.org/learn/discrete-optimization
Mixed Inter Programming, Linear Programming, Combinatorial Optimization,
Discrete Optimisation, Knapsack, Traveling Salesman, Vehicle Routing,
Scheduling, Resource Planning, Network Flow, Assignment