Большие данные с большими яйцами, или ILP для самых маленьких.
Что такое линейное программирование?
LP (linear programming) - задача оптимизации с ограничениями, где и целевая функция, и ограничения являются линейными. Соответственно ILP - integer linear programming, добавляет ограничения на переменные - они должны быть целочисленными, (см картинку 1)
Как решать?
Эффективный на практике метод решения задачи линейного программирования предложили почти сто лет назад - симплекс-метод. Он основан на некоторых соображениях матана и линала, в которые сейчас мы погружать не будем. Для задачи целочисленного линейного программирования все становится СИЛЬНО СЛОЖНЕЕ.
Однако, если вы python базированный гигачад шлепа, вам скорее всего не нужно задумываться над тем, как именно это решается - вы возьмете cvxpy и он goes brrrr
Составление задачи
В вашем случае основной проблемой будет составить непосредственно задачу - как описать какой-то реальный процесс на математическом языке, еще и чтобы оно решалось нормально? Давайте разберемся.
Для этого есть простой чеклист:
- ввести переменные, соответствующие задаче
- ввести целевую функцию - то, что мы хотим максимизировать/минимизировать (доход/удовлетворенность/etc.)
- ввести ограничения на переменные (например, мы не можем произвести больше продукции чем у нас есть, вложить больше денег и тому подобное)
Пример
Для примера возьмем задачу из письменного экзамена по курсу в РЭШ который я вел, условие и решение на картинке 2. Что тут важно?
- ввели переменные - в нашем случае это булевая переменная, отвечающая за выполнение фрилансером i работы j
- ввели целевую функцию - максимизируем чистую прибыль системы
- ограничение 1 - каждый исполнитель не может выполнять более двух задач
- ограничение 2 - каждую задачу выполняет не более 1 исполнителя
Подставили чиселки, пихнули в cvxpy - получили решение.
Всем спасибо за внимание! Если тут наберется 100 огоньков и побольше репостов то будет вторая часть с разбором более сложных задач и некоторых трюков