Змішане цілочисельне лінійне програмування (MILP)

Вступ до оптимізації в Python

Jasmin Ludolf

Content Developer

Змішане цілочисельне лінійне програмування

  • MILP
  • Метод оптимізації, коли змінні обмежень є дискретними
Вступ до оптимізації в Python

Сукні чи смокінги

  • Попит:

    • Сукні: не більш як $20$ за $\$ 1000$
    • Смокінги: не більш як $12$ за $\$ 600$

  • Виробництво суконь:

    • Тканина $\$ 110$
    • Mr. S 6 год за $\$40/год$
    • Ms. T 3 год за $\$35/год$
  • Виробництво смокінгів:
    • Тканина $\$ 75$
    • Mr. S 4 год за $\$40/год$
    • Ms. T 1 год за $\$35/год$

Пара в вечірній сукні та смокінгу

Вступ до оптимізації в Python

Сукні чи смокінги

  • Обмеження:
    • Mr. S щонайбільше 40 год
    • Ms. T щонайбільше 20 год

 

  • Знайдіть оптимальну кількість суконь і смокінгів для максимізації прибутку

Людина тримає червону тканину й одягає її на манекен, створюючи сукню

Вступ до оптимізації в Python

Ціль і обмеження

  • $g$: кількість суконь за тиждень
  • $t$: кількість смокінгів за тиждень

  • $C$: вартість тканини + зарплата Mr. S + альтернативна вартість Ms. T

  • Альтернативна вартість: ціна вибору шиття замість інших обов'язків

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

$C=455g+270t$

Вартість Тканина Mr. S Ms. T
Сукня $\$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 смокінгів

      • Mr. S: $6g+4t=6\times7 + 4\times0 = 42$
      • $42 \gt 40$

    • Усікати до 6 суконь і 0 смокінгів

      • Mr. S: $6g+4t=6\times6 + 4\times0 = 36$
      • Ms. T: $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...