Programmation linéaire en nombres mixtes (MILP)

Introduction à l'optimisation en Python

Jasmin Ludolf

Content Developer

Programmation linéaire mixte en nombres entiers

  • MILP
  • Technique d'optimisation utilisée quand des variables de contrainte sont discrètes
Introduction à l'optimisation en Python

Robes ou smokings

  • Demande :

    • Robes : au plus $20$ à $\$ 1000$
    • Smokings : au plus $12$ à $\$ 600$

  • Production d'une robe :

    • Tissu $\$ 110$
    • M. S 6 heures à $\$40/h$
    • Mme T 3 heures à $\$35/h$
  • Production d'un smoking :
    • Tissu $\$ 75$
    • M. S 4 heures à $\$40/h$
    • Mme T 1 heure à $\$35/h$

Un couple vêtu d'une robe et d'un smoking

Introduction à l'optimisation en Python

Robes ou smokings

  • Contraintes :
    • M. S au plus 40 heures
    • Mme T au plus 20 heures

 

  • Trouver le nombre optimal de robes et de smokings pour maximiser le profit

Une personne tenant un tissu rouge et le posant sur un mannequin pour créer une robe

Introduction à l'optimisation en Python

Objectif et contraintes

  • $g$ : nombre de robes par semaine
  • $t$ : nombre de smokings par semaine

  • $C$ : coût du tissu + salaire de M. S + coût d'opportunité de Mme T

  • Coût d'opportunité : coût de coudre plutôt que d'autres tâches

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

$C=455g+270t$

Coût Tissu M. S Mme T
Robe $\$110$ $\$40/h \times 6h = \$240$ $\$35/h \times 3h = \$105$
Smoking $\$75$ $\$40/h \times 4h = \$160$ $\$35/h \times 1h = \$35$
Introduction à l'optimisation en Python

Objectif et contraintes

  • Revenu : $R=1000g+600t$
  • Coût : $C=455g+270t$
  • Profit : $\Pi=R-C=(1000g+600t)-(455g+270t)=545g+330t$

 

  • Contraintes :

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

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

Introduction à l'optimisation en Python

MILP dans 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]))
Introduction à l'optimisation en Python

MILP dans 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
Introduction à l'optimisation en Python

Intégralité

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
Introduction à l'optimisation en Python

Conséquences d'omettre l'intégralité

  • Solution proposée : 6,67 robes et 0,00 smoking $\rightarrow$

    • Arrondir à 7 robes et 0 smoking

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

    • Tronquer à 6 robes et 0 smoking

      • M. S : $6g+4t=6\times6 + 4\times0 = 36$
      • Mme T : $3g+1t=3\times6 + 1\times0 = 18$
      • $\Pi=545g+330t=545\times 6+330 \times 0=3270$
      • Perte de $330 (près de 10\%)$ de profit !
Introduction à l'optimisation en Python

Passons à la pratique !

Introduction à l'optimisation en Python

Preparing Video For Download...