Transformer les problèmes non linéaires

Introduction à l'optimisation en Python

Jasmin Ludolf

Content Developer

Maximiser une fonction non linéaire

  • Une artiste produit jusqu'à 16 toiles à un coût $C(q) = \sqrt q$ où $q$ est la quantité
  • La demande inverse est $p=\frac{3}{\sqrt q}$ où $p$ est le prix
  • $\max \Pi = pq - C=\frac{3}{\sqrt q}q-\sqrt q = 2\sqrt q$

$$\max 2\sqrt q$$

$$s.t.\ \ \ \ q\leq 16 $$

Femme peignant sur une toile

Introduction à l'optimisation en Python

SciPy ou PuLP ?

  • SciPy : milp exige une fonction objectif linéaire
  • PuLP :
model = LpProblem('Artist', LpMaximize)
q = LpVariable('q', lowBound=0, upBound=16)
model += 2 * q**(1/2)

--> 3 model += 2 * q**(1/2)

TypeError: unsupported operand type(s) for ** or pow(): 'LpVariable' and 'float'
Introduction à l'optimisation en Python

Substituer pour linéariser

  • Poser $z = \sqrt q$
  • $\rightarrow$ $\Pi=2\sqrt q =2z$
  • $\rightarrow$ contrainte de capacité $z^2\leq 16\Leftrightarrow z\leq 4$
model = LpProblem('Artist', LpMaximize)
z = LpVariable('z', lowBound=0, upBound=4, cat='Integer')
model += 2 * z

model.solve() 
print(f"Solution is {LpStatus[model.status]}.")
print(f"The optimal number of paintings is {round(z.varValue**2)}.")

Solution is Optimal. 
The optimal number of paintings is 16.
Introduction à l'optimisation en Python

Budgétisation d'investissement avec projets dépendants

Énoncé du problème

  • Projets $A$, $B$, $C$ ; $A$ est un préalable à $B$
  • Profits respectifs $V$ = [250, 200, 300]
  • Investissement requis $I$ = [2000, 1900, 2500] et seulement 4600 $ sont disponibles

Modélisation

  • Variables binaires $o_A$, $o_B$, $o_C$ ; indiquent la sélection des projets

$\max\ \ o_AV_A + o_Ao_BV_B + o_CV_C$

$s.t.\ \ \ \ o_AI_A + o_Ao_BI_B + o_CI_C\leq 4600$

Icône de gestion budgétaire

Introduction à l'optimisation en Python

Linéarisation : produit de binaires

  • Remplacer $o_Ao_B=o_{AB}$
  • Ajouter des contraintes
    • $o_{AB}\leq o_{A}$
    • $o_{AB}\leq o_{B}$
    • $o_{AB}\geq o_{A} + o_{B} -1$
  • Le problème se réduit à

$$\max\ \ o_AV_A + o_{AB}V_B + o_CV_C$$

$$s.t.\ \ \ \ o_AI_A + o_{AB}I_B + o_CI_C\leq 4600$$

$$ o_{A} + o_{B} -1 \leq o_{AB}\leq o_{A}, o_{B}$$

Introduction à l'optimisation en Python

Affectation des ressources avec coût de formation

  • Allouer 120 tâches pour minimiser le coût
  • Senior ($S$), junior ($J$) et stagiaire ($I$)
  • Coût de formation du stagiaire : 500 $
  • Coût par tâche résolue $c$ = [30, 40, 5]
  • Vecteur $x$ : tâches attribuées de façon optimale
  • Binaire $o$ : indique si le stagiaire est formé
  • $TC = 30x_S+40x_J+(5x_I+500)o$

Personne avec crayon à côté d'une grande liste de tâches

Introduction à l'optimisation en Python

Linéarisation : produit binaire–continu

  • La méthode Big‑M introduit un grand nombre $M$
  • Remplace le produit par $z = (5x_I+500)o$
  • Imposer :
    • $-oM\leq z \leq oM$
    • $-(1-o)M \leq z- (5x_I+500)o \leq (1-o)M$
Introduction à l'optimisation en Python

Passons à la pratique !

Introduction à l'optimisation en Python

Preparing Video For Download...