Devoir de mathématiques optimisation linéaire -Programmation
Télécharger PDFOptimisation Linéaire - Devoir Surveillé
L'optimisation linéaire est un domaine essentiel des mathématiques appliquées permettant de maximiser ou minimiser une fonction objectif sous un ensemble de contraintes linéaires. Ce document traite de la méthode du simplexe, de la dualité et de la programmation en nombres entiers.
Méthode du Simplexe, Pénalités et Dualité
Problème Primal (P.1)
L'objectif est de résoudre le programme linéaire suivant par la méthode géométrique ou algorithmique :
Maximiser : Z = 6x₁ + x₂
Sous les contraintes :
- -7x₁ + 2x₂ ≤ 14
- x₂ ≤ 4
- 2x₁ - 2x₂ ≤ 3
- x₁ ≥ 0, x₂ ≥ 0
Établissement du Problème Dual
Le passage au problème dual se fait en utilisant le tableau des correspondances. Dans ce cadre, chaque contrainte du problème primal donne naissance à une variable duale, et les coefficients de la fonction objectif deviennent les seconds membres du dual.
Pour ce problème dual, l'algorithme du simplexe ne peut pas s'appliquer dès le début car l'origine n'est pas nécessairement une solution de base réalisable. Il est alors nécessaire d'utiliser la méthode des pénalités (méthode du Grand M) pour établir un premier tableau de base. La solution peut ensuite être trouvée en utilisant le théorème de dualité et le principe de complémentarité.
Programmation en Nombres Entiers
On considère le problème (P.2) qui reprend les bases de (P.1) avec une contrainte supplémentaire : x₁ doit appartenir à l'ensemble des entiers naturels (ℕ).
Analyse du Tableau Optimal
Le dernier tableau du simplexe fournit la solution optimale continue suivante :
| Base | x₁ | x₂ | x₃ | x₄ | x₅ | Second Membre |
|---|---|---|---|---|---|---|
| Z | 0 | 0 | 6/7 | 5/7 | 0 | 104/7 |
| x₂ | 0 | 1 | 0 | 1 | 0 | 4 |
| x₅ | 0 | 0 | -2/7 | 10/7 | 1 | 33/7 |
| x₁ | 1 | 0 | 1/7 | 2/7 | 0 | 22/7 |
Dans cette solution, x₁ est égal à 22/7 (soit environ 3,14). Cette valeur n'étant pas entière, elle ne constitue pas une solution optimale pour le problème (P.2).
Méthode des Coupes de Gomory
Pour obtenir une solution entière pour x₁, on applique la méthode des coupes. Cette technique consiste à ajouter une contrainte supplémentaire (une coupe) qui réduit le domaine de recherche sans éliminer de solutions entières admissibles. En portant cette nouvelle contrainte sur le graphique, on observe une modification du domaine des solutions permettant d'identifier le nouveau sommet optimal où x₁ est entier.
Modélisation d'un Problème de Besoins Vitaux
Une personne souhaite couvrir ses besoins minimaux en vitamines au moindre coût :
- Vitamine A : 7 unités
- Vitamine C : 5 unités
- Vitamine D : 2 unités
Données des Produits
- Marque 1 (4 euros) : 2A, 3C, 3D
- Marque 2 (2 euros) : 4A, 1C, 5D
Ce problème est un cas classique de programmation linéaire. Il s'agit de minimiser la fonction de coût C = 4x₁ + 2x₂ sous les contraintes de seuils nutritionnels. Étant donné qu'il n'y a que deux variables de décision (les deux marques), une résolution graphique est tout à fait envisageable en traçant les droites de contraintes et en identifiant la zone de faisabilité.
FAQ : Foire Aux Questions
Pourquoi x1 = 22/7 n'est pas acceptable dans le problème P.2 ?
Le problème P.2 impose que x₁ soit un nombre entier (x₁ ∈ ℕ). La valeur 22/7 étant fractionnaire, elle doit être ajustée via des méthodes spécifiques comme les coupes de Gomory ou le Branch and Bound.
Qu'est-ce que le théorème de dualité ?
Le théorème de dualité stipule que si le problème primal possède une solution optimale, alors le problème dual en possède une également, et les valeurs des fonctions objectifs à l'optimum sont égales.
Quand doit-on utiliser la méthode des pénalités ?
La méthode des pénalités est utilisée lors de l'initialisation de l'algorithme du simplexe lorsqu'une solution de base de départ (comme l'origine) n'est pas réalisable, souvent à cause de contraintes de type "supérieur ou égal" (≥).