Méthodes et modélisation
pour l’optimisation
M1 informatique
2024/2025
Johan Thapper
Trouver des informations
‣ elearning.univ-eiffel.fr/course/view.php?id=11421
‣ slides
‣ feuilles de td et de tp
‣ rendus
‣ exercices travaillés
‣ anciens examens
Organisation
‣ Cours 6 x 2h
‣ Johan Thapper <[email protected]>
‣ TD/TP 6 x 2h
‣ Éric Fusy — Initiaux gr.1, Initiaux gr.2
‣ Johan Thapper — Apprentis
Contrôle des connaissances
‣ 1 examen sur table (en janvier)
‣ sur les notions abordées aux cours, TD et TP
‣ 1 feuille recto-verso manuscrite autorisée
‣ 2 QCM (7.5%+7.5%)
‣ sur les notions abordées aux cours et TD
‣ 2 rendus de TP (7.5%+7.5%)
‣ vous avez le droit de travailler en binôme
Pour réussir à l’examen
‣ Présence active au cours
‣ Révision pour les TD et TP indispensable
‣ Travail sérieux et appliqué aux TD et TP
‣ Des anciens épreuves sont en ligne pour s’entrainer
et pour voir ce qui est attendu à l’examen
Acquis supposés
‣ Algèbre linéaire − + =
‣ indépendance linéaire + − =
‣ élimination de Gauss − − =
‣ Notions de la logique propositionnelle → ≡¬ ∨
‣ variable Booléenne, connecteur, affectation,
forme normale conjonctive (CNF)
‣ Notions de la théorie des graphes
‣ Notions de la théorie de complexité
‣ temps polynomial vs exponentiel P ≠ NP ?
𝟣
𝟤
𝟥
𝟥
𝗑
𝗑
𝗑
𝟤
problème NP-dif cile : SAT, coloration de graphe, …
𝟣
𝟤
𝟥
𝗑
𝟥
𝗑
𝗑
𝟣
‣
𝗑
𝗒
𝗑
𝗒
𝟣
𝟤
𝟥
𝟤
𝗑
𝟤
𝗑
𝗑
𝟥
fi
Modélisation et résolution d’un problème
Une entreprise veut installer la bre optique entre ses bâtiment A, B, C, D et E.
Le coût de chaque lien potentiel (point à point) est donné dans le tableau
suivant :
A B C D E
A 10 15 10
B 10 7 18
C 15 15
D 10 7 15 20
E 18 20
Minimiser le coût total de l’installation.
Supposition : il suffit d’avoir un chemin direct ou
indirect entre chaque paire de bâtiments.
fi
Problème initial Problème formel
minimiser le coût trouver un arbre couvrant minimum
18
A B C D E B E
A 10 15 10
B 10 7 18
10 20
7
C 15 15
A D
D 10 7 15 20 10
E 18 20 15 15
C
algorithme : Kruskal
18
poser des lignes entre : B E
A et B
B et D
10
7
B et E
A D
C et D
coût total : 10+7+18+15 = 50 15
C
Modélisation et résolution d’un problème
‣ Modélisation
‣ Traduire un problème A (le problème initial, sous forme verbale)
en un problème B (le problème formel, le modèle)
‣ Expliciter les suppositions faites
‣ Résolution
‣ Résoudre le problème B avec un algorithme / un logiciel
‣ Récupération d’une solution
‣ Transformer la solution de B en une solution de A
Exemple : affectation de fréquence
Un nombre d’émetteurs est localisé comme dans la gure suivante :
Si deux émetteurs sont trop proches, ils ne peuvent pas transmettre sur la
même fréquence à cause d’interférences.
Minimiser le nombre de fréquences utilisées.
fi
Problème initial Problème formel
minimiser le nombre de fréquences trouver une coloration de graphe
avec un nombre minimal de couleurs
sommet = émetteur
arête = interférence
logiciel dédié :
``solveur’’
Solution
affectation :
fréquence 1 (X Mhz)
fréquence 2 (Y Mhz)
fréquence 3 (Z Mhz)
nombre minimal : 3
couleur = fréquence
Modélisation
1. Décider d’un vocabulaire de modélisation
‣ Graphes, géométrie, logique, …
2. Chercher les variables de décision et expliciter leur
signi cation
‣ Potentiellement plusieurs choix possibles
‣ Un bon choix facilite la prochaine étape
3. Introduire des contraintes qui modélisent le problème
‣ Question à se poser : comment les solutions au problème formel B
correspondent-elles aux solutions au problème initial A ?
fi
Partie 1
La programmation linéaire
Exemple : robes et pantalons
Une petite entreprise fabrique des robes et des pantalons. Elle dispose de
deux machines : une machine pour couper le tissu et une machine pour la
couture. Pour fabriquer une robe, il faut une demi heure pour couper le tissu et
20 minutes pour la couture. Pour fabriquer un pantalon, il faut 15 minutes de
coupure et une demi heure pour la couture. Une robe se vend 40 euros et un
pantalon se vend 50 euros. L’entreprise fonctionne 8 heures par jour.
Supposition : on peut coudre jusqu’à 8 heures par
jour sans attendre la coupure.
Maximiser le bénéfice tiré de la vente.
Robes et pantalons - modélisation
1. Vocabulaire de modélisation
‣ Variables réelles, fonction objectif et inégalités linéaires
2. Chercher les variables de décision et expliciter
leur signi cation
‣ Soit x le nbr de robes et y le nbr de pantalons à fabriquer / jour
3. Exprimer les contraintes en inégalités linéaires
‣ On coupe au plus 8 heures par jour : 1/2 x + 1/4 y ≤ 8
‣ On coud au plus 8 heures par jour : 1/3 x + 1/2 y ≤ 8
‣ x et y sont non-négatifs : x, y ≥ 0
fi
1/2 x + 1/4 y ≤ 8 (coupure)
y≥0 béné ce par robe béné ce par pantalon
1200 32
800 24 bénéfice = 40x + 50y
l’optimum
400 16 x = 12
y = 8
bénéfice = 0
bénéfice = 880
8
x≥0
8 16 24 32
droite iso-objectif
1/3 x + 1/2 y ≤ 8 (couture)
x — nombre de robes par jour
y — nombre de pantalons par jour solutions admissibles
fi
fi
Un programme linéaire (LP)
fonction objectif
max 40⋅x + 50⋅y
1/2⋅x + 1/4⋅y ≤ 8
1/3⋅x + 1/2⋅y ≤ 8
contraintes x, y ≥ 0 contraintes
de non-négativité ≤, =, ≥
variables de décision :
x : le nombre de robes
y : le nombre de pantalons
La programmation linéaire
‣ Entrée
‣ variables réelles : , , …,
‣ type (min/max) et la fonction objectif (linéaire) :
+ − +
‣ équations et inégalités (non strictes et linéaires) :
+ − ≤
+ + =
La fonction objectif est linéaire si elle peut être écrite comme une
combinaison linéaire des variables : + +…+ +
Une contrainte (équations et inégalités) est linéaire si elle peut être
écrite comme une combinaison linéaire des variables ≤ , = , ≥
𝟣
𝟣
𝟤
𝟤
𝗇
𝗇
𝟣
𝟣
𝟣
𝟤
𝟣
𝟤
𝟤
𝗇
𝟤
𝟥
𝟥
𝟥
𝖼
𝗑
𝖼
𝖼
𝖼
𝖼
𝗑
𝖼
𝗑
𝖼
𝗈
𝗇
𝗌
𝗍
𝗑
𝗆
𝗑
𝟣
𝟤
𝖺
𝗑
𝗑
𝗑
𝟩
𝗑
𝗑
𝗑
𝗑
𝗑
𝟧
𝗑
𝗑
𝟤
𝗑
𝟥
𝟣
𝟦
𝟤
Exemple
max 100⋅x + 10⋅y + z - 35⋅w + 5
0.5⋅x + 5⋅y + 5.5⋅z ≤ 8
z ≥ (8 + x)/2
1/3⋅x + 1/6⋅y + 1/9⋅w = 8
x, w ≥ 0
‣ Les coef cients sont réelles
‣ Les contraintes peuvent être ≤, ≥ ou =
‣ z ≥ (8 + x)/2 ⟺ 2⋅z - x ≥ 4 est linéaire
fi
Contre-exemple
min 10⋅x2 + 10⋅y2
5⋅x + 6⋅y < 10
max(2⋅y, y+8) ≤ 10
|x + y| ≥ 10
‣ La fonction objectif n’est pas linéaire
‣ Les inégalités doivent être non-strictes
‣ max(2⋅y, y+8) ≤ 10 et |x + y| ≥ 10 ne sont pas linéaires
Sorties possibles
objectif +
≤
≤
solution admissible optimale
= , =
𝗒
𝟤
𝗑
𝗆
𝖺
𝗑
𝟤
𝗑
𝗒
𝗒
𝟤
𝗑
𝟤
Sorties possibles
objectif +
− ≥−
− ≤
optimum non borné
x = y = c est admissible pour tout c ≥ 0
𝗑
𝗒
𝟤
𝗆
𝖺
𝗑
𝗑
𝗒
𝗑
𝗒
𝟣
Sorties possibles
objectif +
≤
≥
pas de solution
admissible
𝗑
𝟤
𝗆
𝖺
𝗑
𝗑
𝗒
𝗑
𝟣
La programmation linéaire (LP)
‣ Sorties possibles
‣ une solution admissible optimale
‣ toute solution admissible a une valeur inférieure ou égale à
l’optimum (la version de maximisation)
‣ “optimum non borné”
‣ pour tout N ∈ ℝ, on peut trouver une solution admissible avec
une valeur > N (la version de maximisation)
‣ “pas de solution (admissible)” — s’il n’en existe aucune
‣ les contraintes sont contradictoires
Résolution efficace en théorie et en pratique
‣ L’algorithme du simplexe (Dantzig 1947)
‣ ef cace et utilisé en pratique
‣ exponentiel dans le pire des cas
‣ Algorithmes de complexité polynomiale
‣ la méthode de l’ellipsoïde (Khachiyan 1979)
‣ polynomiale, ef cace en théorie mais pas en pratique
‣ les méthodes de points intérieurs (Karmarkar 1984, …)
‣ polynomiales, ef caces en théorie et en pratique
fi
fi
fi
Un peu d’histoire
‣ Kantorovitch (~1939, URSS), Dantzig (1947, États-Unis)
‣ “Programmation” = plani cation (le terme date des années 1950)
“Le théâtre de Paris vous propose une programmation riche, du grand spectacle à la comédie familiale.”
“La programmation de la télévision de service public peut comprendre tous les genres de contenus.”
‣ Applications importantes
‣ plani cation, logistique et contrôle dans de nombreux domaines : télécom,
transport aérien, maritime et terrestre, industrie de production, …
‣ Kantorovitch lauréat du “Prix de la Banque de Suède en
sciences économiques en mémoire d'Alfred Nobel” (1975)
‣ domaine : théorie de l'allocation optimale des ressources
fi
fi
L’optimisation plus généralement
‣ Recherche d’un élément optimal dans un espace de
configurations
‣ C — l’espace de con gurations (arbres couvrants, solutions admissibles)
‣ f : C → ℝ — la fonction objectif
‣ type d’optimisation — maxx∈C f(x) ou minx∈C f(x)
‣ Résolution exacte
‣ en temps polynomial (arbre couvrant minimum, programmation linéaire)
‣ en temps exponentiel (coloration de graphe, SAT)
‣ Résolution approchée
‣ Heuristiques (algorithmes gloutons, recherche locale)
fi
Contenu du cours
‣ Méthodes
‣ L’algorithme du simplexe (programmation linéaire)
‣ L’algorithme DPLL (SAT) et CDCL (con ict driven clause learning)
‣ Solveurs — logiciels optimisés pour la résolution de problèmes
‣ Modélisation
‣ Traduire un problème sous forme verbale
‣ en un programme linéaire (LP) — 4 séances
‣ en une formule propositionnelle en CNF (SAT) — 2 séances
‣ Optimisation
‣ Maximiser ou minimiser un objectif linéaire sous des contraintes
linéaires
fl
