Khadija ARFAOUI R4.
04 : Méthodes d’optimisation
R4.04 : Méthodes d’optimisation
TD 1
Partie 1 : Formulation et résolution d’un programme linéaire
1. Les conditions de formulation d’un PL
La programmation linéaire comme étant un modèle admet des hypothèses (des conditions) que
le décideur doit valider avant de pouvoir les utiliser pour modéliser son problème. Ces
hypothèses sont :
1. Les variables de décision du problème sont positives
2. Le critère de sélection de la meilleure décision est décrit par une fonction linéaire de ces
variables, c’est à dire, que la fonction ne peut pas contenir par exemple un produit croisé de
deux de ces variables.
3. Les restrictions relatives aux variables de décision (exemple : limitations des ressources)
peuvent être exprimées par un ensemble d’équations linéaires. Ces équations forment
l’ensemble des contraintes.
4. Les paramètres du problème en dehors des variables de décisions ont une valeur connue avec
certitude (aucune autre variable outre que les variables de décision ne doivent figurer dans la
formulation du problème).
2. Etapes de formulation d’un PL :
Généralement il y a trois étapes à suivre pour pouvoir construire le modèle d'un programme
linéaire :
1. Identifier les variables du problème à valeur non connues (variable de décision) et les
représenter sous forme symbolique (par exemple : x, y, z).
2. Identifier les restrictions (les contraintes) du problème et les exprimer par un système
d’équations linéaires.
3. Identifier l’objectif ou le critère de sélection et le représenter sous une forme linéaire en
fonction des variables de décision. Spécifier si le critère de sélection est à maximiser ou à
minimiser.
1
Khadija ARFAOUI R4.04 : Méthodes d’optimisation
Exemple n°1 :
Un fabricant produit 2 types de yaourts à la fraise A et B à partir de 3 matières premières :
Fraise, de Lait et de Sucre. Chaque yaourt doit respecter les proportions suivantes de matières
premières :
Les matières premières sont en quantité limitée : 800 kilos de Fraises, 700 kilos de Lait et 300
kilos de sucre. La vente des yaourts A rapportent 4 € par kilo et les yaourts B 5€
Formulez ce problème sous la forme d’un programme linéaire en respectant les conditions
de formulation et en suivant les étapes indiquées.
Exercice 1 :
Vous êtes en charge de la gestion de production d'une entreprise de fabrication de meubles.
Vous disposez de deux types de matières premières : le bois et le métal. Vous pouvez utiliser
ces matières premières pour produire deux types de meubles : des chaises et des tables. Chaque
chaise nécessite 2 unités de bois et 3 unités de métal, et chaque table nécessite 5 unités de bois
et 4 unités de métal. Vous avez un stock limité de bois (180 unités) et de métal (200 unités)
disponibles pour produire des meubles. De plus, vous avez un nombre limité d'heures de travail
disponibles pour produire des meubles (80 heures). Il est nécessaire 1 heure pour produire une
chaise et 2 heures pour produire une table.
Enfin, chaque chaise rapporte un bénéfice de 15€ et chaque table rapporte un bénéfice de 20€.
Votre objectif est de maximiser les bénéfices en produisant le nombre optimal de chaises et de
tables.
1. Modélisez mathématiquement le problème de production sous forme de programme
linéaire.
2. Résolvez le modèle graphiquement en utilisant les techniques de programmation
linéaire.
3. Résolvez le modèle en utilisant l'algorithme simplex.
4. L’entreprise souhaite réduire le nombre d’heures de travail à 75 heures. Reformulez le
problème en prenant en compte la nouvelle contrainte.
5. Est-ce que le nouveau problème peut être résolu graphiquement ? pourquoi ?
6. Quelle méthode peut-on utiliser dans ce cas ?
7. Résoudre ce problème graphiquement en utilisant l’algorithme Branch and Bound
8. Donnez la solution optimale
9. Reformulez le problème cette fois pour déterminer le nombre d’heures minimum à
travailler pour réaliser le gain précédent
2
Khadija ARFAOUI R4.04 : Méthodes d’optimisation
10. Donnez le code correspondant en python
11. Donnez la solution optimale.
Exercice 2 : L’algorithme A* :
Soit le graphe G et l’heuristique h(n) suivants :
On souhaite appliquez l’algorithme A * au problème du voyage en Roumanie en appliquant
l’heuristique h(n) de la distance à vol d’oiseau dont les valeurs sont décrites dans le tableau
suivant. La ville de départ est Lugoj et celle de destination est Bucharest.
3
Khadija ARFAOUI R4.04 : Méthodes d’optimisation
1. Simulez l’exécution de l’algorithme A* et donnez l’ensemble d’itérations avec le
contenu des listes « Open » et « Closed » à chaque fois.
2. Donnez la solution finale de l’algorithme A*
3. L’heuristique h(n) est-elle admissible ? justifiez.
Exercice 3 : L’algorithme A* :
Considérez la carte suivante. L’objectif est de trouver le chemin le plus court de A vers I. On
donne également trois heuristiques, h1, h2 et h3.
1. Est-ce que h1, h2 et h3 sont admissibles ? Justifier.
2. Est-ce que h4 = max(h1, h3) est admissible ? Justifier.
3. Appliquer la recherche A* en utilisant h1. Donner la solution finale.
4. Appliquer la recherche A* en utilisant h3. Donner la solution finale.
5. Appliquer la recherche A* en utilisant h4. Donner la solution finale.
6. Si vous avez le choix entre trois heuristiques admissibles h1, h2 et h3 = max(h1,h2)
laquelle choisissez-vous ? Justifier.