Смешанное целочисленное линейное программирование (MILP)

Введение в оптимизацию на Python

Jasmin Ludolf

Content Developer

Смешанное целочисленное линейное программирование

  • MILP
  • Метод оптимизации, применяемый, когда переменные ограничений дискретны
Введение в оптимизацию на Python

Платья или смокинги

  • Спрос:

    • Платья: не более $20$ по $\$ 1000$
    • Смокинги: не более $12$ по $\$ 600$

  • Производство платья:

    • Ткань $\$ 110$
    • Г-н С. 6 часов по $\$40/ч$
    • Г-жа Т. 3 часа по $\$35/ч$
  • Производство смокинга:
    • Ткань $\$ 75$
    • Г-н С. 4 часа по $\$40/ч$
    • Г-жа Т. 1 час по $\$35/ч$

Пара в платье и смокинге

Введение в оптимизацию на Python

Платья или смокинги

  • Ограничения:
    • Г-н С.: не более 40 часов
    • Г-жа Т.: не более 20 часов

 

  • Найти оптимальное количество платьев и смокингов для максимизации прибыли

Человек держит красную ткань и примеряет её на манекен для создания платья

Введение в оптимизацию на Python

Целевая функция и ограничения

  • $g$: количество платьев за неделю
  • $t$: количество смокингов за неделю

  • $C$: стоимость ткани + зарплата г-на С. + альтернативные издержки г-жи Т.

  • Альтернативные издержки: стоимость выбора пошива вместо других обязанностей

$C=110g+240g+105g+75t+160t+35t$

$C=455g+270t$

Затраты Ткань Г-н С. Г-жа Т.
Платье $\$110$ $\$40/ч \times 6ч = \$240$ $\$35/ч \times 3ч = \$105$
Смокинг $\$75$ $\$40/ч \times 4ч = \$160$ $\$35/ч \times 1ч = \$35$
Введение в оптимизацию на Python

Целевая функция и ограничения

  • Выручка: $R=1000g+600t$
  • Затраты: $C=455g+270t$
  • Прибыль: $\Pi=R-C=(1000g+600t)-(455g+270t)=545g+330t$

 

  • Ограничения:

    • Спрос: $g\leq20$, $t\leq12$

    • Предложение: $6g+4t\leq40$, $3g+t\leq20$

Введение в оптимизацию на Python

MILP в SciPy

from scipy.optimize import milp, Bounds, LinearConstraint


result = milp([-545, -330],

              integrality=[1, 1],

              bounds=Bounds([0, 0], [20, 12]),

              constraints=LinearConstraint([[6, 4], [3, 1]], ub=[40, 20]))
Введение в оптимизацию на Python

MILP в SciPy

print(result.message)
print(f'The optimal number of gowns produced is: {result.x[0]:.2f}')
print(f'The optimal number of tuxedos produced is: {result.x[1]:.2f}') 

Optimization terminated successfully. (HiGHS Status 7: Optimal)
The optimal number of gowns produced is: 6.00
The optimal number of tuxedos produced is: 1.00
Введение в оптимизацию на Python

Целочисленность

result = milp([-545, -330],  
              bounds=Bounds([0, 0], [20, 12]), 
              constraints=LinearConstraint([[6, 4], [3, 1]], ub=[40, 20]))
...

The optimal number of gowns produced is: 6.67
The optimal number of tuxedos produced is: 0.00
Введение в оптимизацию на Python

Последствия игнорирования целочисленности

  • Предложенное решение: 6,67 платья и 0,00 смокингов $\rightarrow$

    • Округление до 7 платьев и 0 смокингов

      • Г-н С.: $6g+4t=6\times7 + 4\times0 = 42$
      • $42 \gt 40$

    • Усечение до 6 платьев и 0 смокингов

      • Г-н С.: $6g+4t=6\times6 + 4\times0 = 36$
      • Г-жа Т.: $3g+1t=3\times6 + 1\times0 = 18$
      • $\Pi=545g+330t=545\times 6+330 \times 0=3270$
      • Упущено $330 (почти 10%) прибыли!
Введение в оптимизацию на Python

Давайте потренируемся!

Введение в оптимизацию на Python

Preparing Video For Download...