Programmazione lineare mista intera (MILP)

Introduzione all'ottimizzazione in Python

Jasmin Ludolf

Content Developer

Programmazione lineare mista intera

  • MILP
  • Tecnica di ottimizzazione quando le variabili vincolate sono discrete
Introduzione all'ottimizzazione in Python

Abiti o smoking

  • Domanda:

    • Abiti: Al massimo $20$ a $\$ 1000$
    • Smoking: Al massimo $12$ a $\$ 600$

  • Produzione abito:

    • Tessuto $\$ 110$
    • Sig. S 6 ore a $\$40/h$
    • Sig.ra T 3 ore a $\$35/h$
  • Produzione smoking:
    • Tessuto $\$ 75$
    • Sig. S 4 ore a $\$40/h$
    • Sig.ra T 1 ora a $\$35/h$

Una coppia in abito da sera e smoking

Introduzione all'ottimizzazione in Python

Abiti o smoking

  • Vincoli:
    • Sig. S al massimo 40 ore
    • Sig.ra T al massimo 20 ore

 

  • Trova il numero ottimale di abiti e smoking per massimizzare il profitto

Persona che tiene un tessuto rosso e lo posa su un manichino per creare un vestito

Introduzione all'ottimizzazione in Python

Obiettivo e vincoli

  • $g$: numero di abiti in una settimana
  • $t$: numero di smoking in una settimana

  • $C$: costo tessuto + salario Sig. S + costo opportunità Sig.ra T

  • Costo opportunità: costo di scegliere il cucito rispetto ad altri compiti

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

$C=455g+270t$

Costo Tessuto Sig. S Sig.ra T
Abito $\$110$ $\$40/h \times 6h = \$240$ $\$35/h \times 3h = \$105$
Smoking $\$75$ $\$40/h \times 4h = \$160$ $\$35/h \times 1h = \$35$
Introduzione all'ottimizzazione in Python

Obiettivo e vincoli

  • Ricavi: $R=1000g+600t$
  • Costi: $C=455g+270t$
  • Profitto: $\Pi=R-C=(1000g+600t)-(455g+270t)=545g+330t$

 

  • Vincoli:

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

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

Introduzione all'ottimizzazione in Python

MILP in 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]))
Introduzione all'ottimizzazione in Python

MILP in SciPy

print(result.message)
print(f'Il numero ottimale di abiti prodotti è: {result.x[0]:.2f}')
print(f'Il numero ottimale di smoking prodotti è: {result.x[1]:.2f}') 

Ottimizzazione terminata con successo. (HiGHS Status 7: Optimal)
Il numero ottimale di abiti prodotti è: 6.00
Il numero ottimale di smoking prodotti è: 1.00
Introduzione all'ottimizzazione in Python

Integralità

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

Il numero ottimale di abiti prodotti è: 6.67
Il numero ottimale di smoking prodotti è: 0.00
Introduzione all'ottimizzazione in Python

Conseguenze di omettere l’integralità

  • Soluzione proposta 6,67 abiti e 0,00 smoking $\rightarrow$

    • Arrotonda a 7 abiti e 0 smoking

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

    • Tronca a 6 abiti e 0 smoking

      • Sig. S: $6g+4t=6\times6 + 4\times0 = 36$
      • Sig.ra T: $3g+1t=3\times6 + 1\times0 = 18$
      • $\Pi=545g+330t=545\times 6+330 \times 0=3270$
      • Persi $330 (quasi 10%) di profitto!
Introduzione all'ottimizzazione in Python

Ayo berlatih!

Introduzione all'ottimizzazione in Python

Preparing Video For Download...