Mieszane programowanie liniowo-całkowitoliczbowe (MILP)

Wprowadzenie do optymalizacji w Pythonie

Jasmin Ludolf

Content Developer

Mieszane programowanie liniowo-całkowitoliczbowe

  • MILP
  • Technika optymalizacji stosowana, gdy zmienne ograniczeń są dyskretne
Wprowadzenie do optymalizacji w Pythonie

Suknie czy smokingi

  • Popyt:

    • Suknie: maks. $20$ po $\$ 1000$
    • Smokingi: maks. $12$ po $\$ 600$

  • Produkcja sukni:

    • Tkanina $\$ 110$
    • Pan S: 6 godz. po $\$40/h$
    • Pani T: 3 godz. po $\$35/h$
  • Produkcja smokingów:
    • Tkanina $\$ 75$
    • Pan S: 4 godz. po $\$40/h$
    • Pani T: 1 godz. po $\$35/h$

Para ubrana w suknię i smoking

Wprowadzenie do optymalizacji w Pythonie

Suknie czy smokingi

  • Ograniczenia:
    • Pan S: maks. 40 godzin
    • Pani T: maks. 20 godzin

 

  • Znaleźć optymalną liczbę sukni i smokingów maksymalizującą zysk

Osoba trzymająca czerwoną tkaninę i układająca ją na manekinie, tworząc suknię

Wprowadzenie do optymalizacji w Pythonie

Funkcja celu i ograniczenia

  • $g$: liczba sukni w ciągu tygodnia
  • $t$: liczba smokingów w ciągu tygodnia

  • $C$: koszt tkaniny + wynagrodzenie Pana S + koszt alternatywny Pani T

  • Koszt alternatywny: koszt szycia zamiast wykonywania innych obowiązków

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

$C=455g+270t$

Koszt Tkanina Pan S Pani T
Suknia $\$110$ $\$40/h \times 6h = \$240$ $\$35/h \times 3h = \$105$
Smoking $\$75$ $\$40/h \times 4h = \$160$ $\$35/h \times 1h = \$35$
Wprowadzenie do optymalizacji w Pythonie

Funkcja celu i ograniczenia

  • Przychód: $R=1000g+600t$
  • Koszt: $C=455g+270t$
  • Zysk: $\Pi=R-C=(1000g+600t)-(455g+270t)=545g+330t$

 

  • Ograniczenia:

    • Popyt: $g\leq20$, $t\leq12$

    • Podaż: $6g+4t\leq40$, $3g+t\leq20$

Wprowadzenie do optymalizacji w Pythonie

MILP w 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]))
Wprowadzenie do optymalizacji w Pythonie

MILP w 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
Wprowadzenie do optymalizacji w Pythonie

Całkowitoliczbowość

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
Wprowadzenie do optymalizacji w Pythonie

Konsekwencje pominięcia całkowitoliczbowości

  • Proponowane rozwiązanie: 6,67 sukni i 0,00 smokingów $\rightarrow$

    • Zaokrąglenie do 7 sukni i 0 smokingów

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

    • Obcięcie do 6 sukni i 0 smokingów

      • Pan S: $6g+4t=6\times6 + 4\times0 = 36$
      • Pani T: $3g+1t=3\times6 + 1\times0 = 18$
      • $\Pi=545g+330t=545\times 6+330 \times 0=3270$
      • Utracony zysk: $330 (prawie 10%)!
Wprowadzenie do optymalizacji w Pythonie

Czas na ćwiczenia!

Wprowadzenie do optymalizacji w Pythonie

Preparing Video For Download...