Optimisation lineaire 1ere annee mathematiques -Programmatio
Télécharger PDFOptimisation Linéaire : Devoir Surveillé et Exercices Corrigés
Ce document présente des exercices d'optimisation linéaire portant sur la méthode du simplexe, la dualité, la programmation en nombres entiers et la formalisation de problèmes réels. Ces concepts sont essentiels pour les ingénieurs en mathématiques appliquées afin de résoudre des problèmes de décision complexes.
Exercice 1 : Méthode du Simplexe, Pénalités et Dualité
L'objectif de cet exercice est d'étudier un programme linéaire sous différentes approches de résolution.
Résolution géométrique et algébrique
On considère le programme linéaire (P.1) suivant :
Maximiser {Z = 8x1 + x2}
Sous les contraintes :
1) x1 + x2 ≤ 5
2) -x1 + x2 ≥ 0
3) 6x1 + 2x2 ≤ 21
4) x1 ≥ 0, x2 ≥ 0
Pour résoudre ce problème, on peut utiliser la méthode géométrique en représentant le domaine des solutions réalisables dans le plan (x1, x2). La solution optimale se trouve à l'un des sommets du polygone formé par les contraintes.
Établissement du problème dual
Le problème dual est construit à partir du problème primal. Selon le tableau des correspondances, chaque contrainte du primal correspond à une variable du dual, et chaque variable du primal correspond à une contrainte du dual. L'objectif du dual sera de minimiser une fonction liée aux ressources (les seconds membres du primal).
L'algorithme du simplexe standard ne peut pas s'appliquer dès le début car certaines contraintes sont de type "supérieur ou égal" (≥ 0), ce qui empêche d'avoir une solution de base réalisable immédiate. On utilise alors la méthode des pénalités (ou méthode du Grand M) pour introduire des variables artificielles et démarrer l'algorithme.
Principe de complémentarité
Pour trouver la solution du problème dual, on utilise le théorème de dualité et le principe de complémentarité. Ce dernier stipule que si une contrainte du primal est strictement satisfaite (marge positive), alors la variable duale correspondante est nulle à l'optimum.
Exercice 2 : Programmation en Nombres Entiers
On considère maintenant le problème (P.2) où la variable x1 doit être un nombre entier (x1 ∈ ℕ), tandis que x2 reste positif ou nul.
Méthode des coupes de Gomory
À partir du tableau optimal du simplexe continu, si la valeur de x1 n'est pas entière, on applique la méthode des coupes. Cela consiste à générer une nouvelle contrainte, appelée coupe de Gomory, à partir d'une ligne du tableau contenant une valeur fractionnaire. Cette contrainte supplémentaire est ajoutée au système pour réduire le domaine de recherche sans exclure de solutions entières.
L'application de cette méthode permet d'approcher progressivement la solution optimale entière en éliminant les portions du domaine qui ne contiennent que des solutions fractionnaires.
Exercice 3 : Formalisation d'un problème de coût alimentaire
Un élevage de caribous nécessite une alimentation spécifique composée de sel, sucre, gras et basilic. Deux aliments sont disponibles sur le marché : le Royal-Caribou et le Kebab-Caribou.
Formulation mathématique
L'objectif est de minimiser le coût quotidien de l'alimentation par animal.
Variables de décision :
- x1 : quantité de Royal-Caribou (en kg)
- x2 : quantité de Kebab-Caribou (en kg)
Données nutritionnelles :
- 1kg de Royal-Caribou contient : 100g de sel, 100g de gras, 200g de basilic.
- 1kg de Kebab-Caribou contient : 100g de sucre, 200g de gras, 100g de basilic.
Besoins minimaux par jour :
- Sel : 0,4 kg
- Sucre : 0,6 kg
- Gras : 2 kg
- Basilic : 1,7 kg
Fonction objectif : Minimiser Z = 10x1 + 4x2
Il s'agit bien d'un problème de programmation linéaire car la fonction à minimiser et les contraintes de consommation sont toutes des fonctions linéaires des variables x1 et x2. Ce problème peut être résolu graphiquement car il ne comporte que deux variables de décision.
FAQ : Questions Fréquemment Posées
Quelle est la différence entre le problème primal et le problème dual ?
Le problème primal est le problème de base que l'on cherche à résoudre (souvent une maximisation de profit). Le problème dual est une formulation alternative qui fournit des informations sur la valeur marginale des ressources utilisées (prix d'ombre).
Pourquoi utiliser la programmation en nombres entiers ?
Elle est indispensable lorsque les variables de décision représentent des unités indivisibles, comme des machines, des personnes ou, dans certains cas, des quantités de produits qui ne peuvent être vendues par fractions.
Quand la méthode géométrique est-elle applicable ?
La méthode géométrique est principalement utilisée pour des problèmes comportant deux variables de décision (x1 et x2). Au-delà de trois variables, la représentation graphique devient impossible et l'utilisation de l'algorithme du simplexe est nécessaire.