Programmmation linØaire
Programmmation linØaire
Recherche OpØrationnelle · course
Fiche de révisionFiche de cours
Rédigée à partir de ce document, puis vérifiée avant publication.
Ce matériel couvre les bases de la programmation linéaire (PL) et de la programmation linéaire en nombres entiers (PLNE). Il s'adresse aux étudiants en recherche opérationnelle ou optimisation, souhaitant comprendre la modélisation, les formes standards des programmes linéaires, les résultats fondamentaux, ainsi que des exemples concrets et des méthodes de résolution comme la méthode graphique et le simplexe.
Un problème d'optimisation consiste à minimiser une fonction objectif f(x) sous la contrainte que x appartient à un ensemble réalisable S. Ici, x ∈ Rⁿ est un vecteur des variables de décision, f : Rⁿ → R est la fonction objectif, et S est le domaine réalisable défini par des contraintes.
En optimisation numérique, f et S sont généralement définis par des fonctions deux fois différentiables, et les algorithmes utilisent des informations locales (dérivées) pour trouver un optimum local. En recherche opérationnelle, on s'intéresse à l'optimisation discrète, notamment la programmation linéaire (PL) où f est affine et S est un polyèdre défini par des contraintes linéaires (égalités ou inégalités).
La programmation linéaire en nombres entiers (PLNE) ajoute la contrainte que les variables doivent être entières. Elle est utilisée dans des problèmes combinatoires comme le voyageur de commerce ou les réseaux.
La modélisation se fait en trois étapes :
On peut toujours transformer un problème de maximisation en un problème de minimisation en changeant le signe de la fonction objectif, ce qui simplifie l’étude.
Un problème de programmation linéaire se présente sous la forme :
Max (ou Min) z = Cᵗ × X sous contraintes : AX ≤ b, HX = d, X ≥ 0
où z ∈ R, C ∈ Rⁿ, X ∈ Rⁿ, A est une matrice m×n, b ∈ Rᵐ, H est une matrice p×n, et d ∈ Rᵖ.
On dispose de n types d’aliments a₁, ..., aₙ. Chaque unité de l’aliment aᵢ apporte eᵢ calories, vᵢ vitamines, pᵢ protéines et coûte cᵢ. L’objectif est d’acheter des quantités xᵢ de ces aliments pour satisfaire au moins E calories, V vitamines et P protéines au moindre coût.
∑ eᵢ xᵢ ≥ E ∑ vᵢ xᵢ ≥ V ∑ pᵢ xᵢ ≥ P xᵢ ≥ 0 pour i = 1,...,n
Instance numérique :
| Aliment | a₁ | a₂ | a₃ | a₄ | a₅ | a₆ |
|---|---|---|---|---|---|---|
| Calories | 110 | 205 | 160 | 160 | 420 | 260 |
| Protéines | 2 | 12 | 54 | 285 | 22 | 80 |
| Vitamines | 4 | 32 | 13 | 8 | 4 | 14 |
| Coût | 3 | 24 | 19 | 9 | 20 | 19 |
Objectif : satisfaire E = 2000 calories, V = 800 vitamines, P = 55 protéines au moindre coût.
Formulation :
Min z = 3x₁ + 24x₂ + 19x₃ + 9x₄ + 20x₅ + 19x₆ s.c. : 110x₁ + 205x₂ + 160x₃ + 160x₄ + 420x₅ + 260x₆ ≥ 2000 2x₁ + 12x₂ + 54x₃ + 285x₄ + 22x₅ + 80x₆ ≥ 55 4x₁ + 32x₂ + 13x₃ + 8x₄ + 4x₅ + 14x₆ ≥ 800 xᵢ ≥ 0 pour i = 1,...,6
Un programme linéaire peut s’écrire sous deux formes principales :
Max (ou Min) z = CᵗX s.c. : AX = b X ≥ 0
Max (ou Min) z = CᵗX s.c. : AX ≤ b X ≥ 0
On peut passer de l’une à l’autre en introduisant des variables d’écart Y ≥ 0 telles que :
AX ≤ b ⇔ ∃ Y ≥ 0 tq AX + Y = b
On obtient alors un système sous forme standard avec les variables X et Y.
Considérons le programme :
Min (5x₁ − 3x₂) s.c. : x₁ − x₂ ≥ 2 2x₁ + 3x₂ ≤ 4 −x₁ + 6x₂ = 10 x₁ ≥ 0, x₂ ≥ 0
Transformation en forme standard :
x₂ − x₁ + x₃ = −2
2x₁ + 3x₂ + x₄ = 4, x₄ ≥ 0
On obtient ainsi :
Min z = 5x₁ − 3x₂ + 0x₃ + 0x₄ s.c. : −x₁ + x₂ + x₃ = −2 2x₁ + 3x₂ + x₄ = 4 −x₁ + 6x₂ = 10 x₁, x₂, x₃, x₄ ≥ 0
Soit un programme linéaire (P) sous forme standard :
Max z = CᵗX s.c. : AX = b X ≥ 0
avec A une matrice m×n de rang m.
Une solution réalisable qui maximise (ou minimise) la fonction objectif est appelée solution optimale. La valeur correspondante est la valeur optimale du problème.
Considérons le problème (E) :
max z = x₁ + 2x₂ + 3x₃ − 4x₄ s.c. : x₁ − x₂ + x₃ + x₅ = 1 x₁ − x₃ − x₄ + x₆ = −1 x₂ + x₃ + x₄ + x₇ = 1 xᵢ ≥ 0 pour i = 1,...,7
Le vecteur
X = (0, 0, 0.5, 0.5, 0.5, 0, 0.5)
est une solution réalisable avec une valeur de fonction objectif égale à −0.5.
Une solution optimale est :
X = (0, 0, 1, 0, 0, 0, 0)
avec une valeur optimale z = 3.
Théorème :
Idée de démonstration : Si une solution réalisable X a plus de m composantes strictement positives, on peut construire une combinaison linéaire qui élimine certaines variables sans sortir du domaine réalisable, jusqu’à obtenir une solution avec exactement m variables strictement positives (solution de base).
De même, pour une solution optimale, on peut construire une solution optimale de base en procédant de façon similaire.
Remarque importante : Le nombre de solutions réalisables de base est fini et au plus égal à C(n, m) (combinaison de n éléments pris m à m).
Exemple de problème non réalisable :
Max 3x₁ − x₂ s.c. : x₁ + x₂ ≤ 2 −2x₁ − 2x₂ ≤ −10 x₁, x₂ ≥ 0
Il n’existe aucune solution réalisable.
Exemple de problème non borné :
Max x₁ − x₂ s.c. : −2x₁ + x₂ ≤ −1 −x₁ − 2x₂ ≤ −2 x₁, x₂ ≥ 0
Pour tout M ∈ R, il existe une solution réalisable telle que x₁ − x₂ > M.
Considérons :
Max Z = 100x₁ + 200x₂ s.c. : 3x₁ + 4x₂ ≤ 42 x₁ + 3x₂ ≤ 24 x₁, x₂ ≥ 0
On introduit les variables d’écart y₁, y₂ ≥ 0 :
3x₁ + 4x₂ + y₁ = 42 x₁ + 3x₂ + y₂ = 24
Forme matricielle :
Max z = (100, 200, 0, 0) × (x₁, x₂, y₁, y₂)ᵗ s.c. : [3 4 1 0] [1 3 0 1] × (x₁, x₂, y₁, y₂)ᵗ = (42, 24)ᵗ x₁, x₂, y₁, y₂ ≥ 0
On partitionne la matrice A en B et N :
B = [3 0
1 1], N = [4 1
3 0]
La solution de base initiale (variables hors base nulles) est :
x_B = B⁻¹b = (14, 10), x_N = (0, 0)
avec x_B = (x₁, y₂) et x_N = (x₂, y₁).