Optimisation en Python — Récapitulatif

Librairies nécessaires

pip install pulp scipy ortools pymoo numpy matplotlib

---

1. Programmation Linéaire (LP) — PuLP

Objectif : Maximiser/minimiser une fonction linéaire sous contraintes linéaires.

Exemple : Maximiser le profit de production de chaises et tables.

from pulp import *

prob = LpProblem("Maximiser_profit", LpMaximize)

x = LpVariable("chaises", lowBound=0)
y = LpVariable("tables", lowBound=0)

# Fonction objectif
prob += 10*x + 25*y

# Contraintes
prob += 2*x + 4*y <= 100  # heures
prob += 3*x + 2*y <= 80   # bois

prob.solve()
print(f"Chaises: {x.value()}, Tables: {y.value()}, Profit: {value(prob.objective)}€")
# Chaises: 20.0, Tables: 15.0, Profit: 575.0€

---

2. Programmation en Nombres Entiers (ILP) — PuLP

Objectif : Comme LP mais les variables doivent être entières.

Différence : Ajouter cat='Integer' aux variables.

from pulp import *

prob = LpProblem("Production_entiere", LpMaximize)

x = LpVariable("chaises", lowBound=0, cat='Integer')  # ← Integer
y = LpVariable("tables", lowBound=0, cat='Integer')

prob += 10*x + 25*y
prob += 2*x + 4*y <= 100
prob += 3*x + 2*y <= 80

prob.solve()
print(f"Chaises: {int(x.value())}, Tables: {int(y.value())}")

---

3. Optimisation Non-Linéaire — scipy

Objectif : Minimiser une fonction non-linéaire avec ou sans contraintes.

Méthodes : Multiplicateurs de Lagrange, Gradient descent, KKT.

Exemple : Minimiser f(x,y) = (x-3)² + (y-2)² sous contrainte x+y = 4.

from scipy.optimize import minimize

def objectif(vars):
    x, y = vars
    return (x-3)**2 + (y-2)**2

contrainte = {'type': 'eq', 'fun': lambda v: v[0] + v[1] - 4}

resultat = minimize(objectif, [0, 0], constraints=contrainte)
print(f"x={resultat.x[0]:.2f}, y={resultat.x[1]:.2f}")
# x=2.50, y=1.50

---

4. Programmation Dynamique — Python pur

Objectif : Décomposer un problème complexe en sous-problèmes résolus une seule fois.

Exemple classique : Problème du sac à dos (Knapsack).

def knapsack(poids_max, poids, valeurs):
    n = len(poids)
    dp = [[0]*(poids_max+1) for _ in range(n+1)]

    for i in range(1, n+1):
        for w in range(poids_max+1):
            dp[i][w] = dp[i-1][w]
            if poids[i-1] <= w:
                dp[i][w] = max(dp[i][w], dp[i-1][w-poids[i-1]] + valeurs[i-1])

    return dp[n][poids_max]

objets_poids  = [2, 3, 4, 5]
objets_valeur = [3, 4, 5, 6]
print(f"Valeur max: {knapsack(5, objets_poids, objets_valeur)}")
# Valeur max: 7

---

5. Optimisation Combinatoire — Voyageur de commerce (TSP) — ortools

Objectif : Trouver le chemin le plus court passant par toutes les villes.

from ortools.constraint_solver import routing_enums_pb2, pywrapcp

# Matrice de distances entre 4 villes
distances = [
    [0, 10, 15, 20],
    [10, 0, 35, 25],
    [15, 35, 0, 30],
    [20, 25, 30, 0],
]

manager = pywrapcp.RoutingIndexManager(len(distances), 1, 0)
routing = pywrapcp.RoutingModel(manager)

def distance(i, j):
    return distances[manager.IndexToNode(i)][manager.IndexToNode(j)]

routing.SetArcCostEvaluatorOfAllVehicles(routing.RegisterTransitCallback(distance))
params = pywrapcp.DefaultRoutingSearchParameters()
solution = routing.SolveWithParameters(params)

index = routing.Start(0)
route = []
while not routing.IsEnd(index):
    route.append(manager.IndexToNode(index))
    index = solution.Value(routing.NextVar(index))
print(f"Chemin optimal: {route}")
# Chemin optimal: [0, 1, 3, 2]

---

6. Optimisation Multi-objectifs / Front de Pareto — pymoo

Objectif : Optimiser simultanément plusieurs objectifs contradictoires.

Exemple : Minimiser coût ET délai → trouver le front de Pareto.

from pymoo.algorithms.moo.nsga2 import NSGA2
from pymoo.problems import get_problem
from pymoo.optimize import minimize
import matplotlib.pyplot as plt

problem = get_problem("zdt1")
algo = NSGA2(pop_size=100)
res = minimize(problem, algo, ('n_gen', 100), verbose=False)

plt.scatter(res.F[:, 0], res.F[:, 1], s=10)
plt.xlabel("Objectif 1 (coût)")
plt.ylabel("Objectif 2 (délai)")
plt.title("Front de Pareto")
plt.show()

---

7. Théorie des Jeux — Minimax — Python pur

Objectif : Maximiser le gain minimum garanti face à un adversaire rationnel.

import numpy as np

# Matrice de gains du joueur 1
gains = np.array([
    [3, -1],
    [2,  4],
])

# Stratégie minimax : maximise le minimum garanti
min_par_ligne = gains.min(axis=1)
meilleure_ligne = np.argmax(min_par_ligne)
print(f"Stratégie optimale : ligne {meilleure_ligne}, gain garanti : {min_par_ligne[meilleure_ligne]}")
# Stratégie optimale : ligne 1, gain garanti : 2

---

Résumé des librairies

Méthode	Librairie	Installation
Programmation Linéaire	pulp	pip install pulp
Nombres Entiers	pulp	pip install pulp
Non-linéaire	scipy	pip install scipy
Dynamique	Python pur	—
TSP / Combinatoire	ortools	pip install ortools
Multi-objectifs / Pareto	pymoo	pip install pymoo
Minimax / Jeux	numpy	pip install numpy

---

Arbre des méthodes

Optimisation
├── Linéaire (LP)        → PuLP / scipy.linprog
├── Entiers (ILP)        → PuLP (cat='Integer')
├── Non-linéaire         → scipy.optimize.minimize
├── Dynamique            → Python pur (memoization / tableau)
├── Combinatoire         → ortools (TSP, ordonnancement)
├── Multi-objectifs      → pymoo (NSGA-II, front de Pareto)
└── Théorie des jeux     → numpy (minimax, Nash)