Programmmation linØaire

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.

Introduction à la programmation linéaire

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.

Modélisation d’un problème d’optimisation linéaire

La modélisation se fait en trois étapes :

1. Définition des variables de décision.
2. Expression de la fonction objectif en fonction de ces variables.
3. Expression des contraintes sous forme d’égalités ou d’inégalités linéaires.

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ᵖ.

Exemple : Problème de nutrition

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.

• Variables de décision : xᵢ quantité de l’aliment aᵢ.
• Fonction objectif : Min z = ∑ cᵢ xᵢ = (c₁ ... cₙ)(x₁ ... xₙ)ᵗ.
• Contraintes :

∑ 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

Formes standards et canoniques des programmes linéaires

Un programme linéaire peut s’écrire sous deux formes principales :

• Forme standard :

Max (ou Min) z = CᵗX
s.c. :
AX = b
X ≥ 0

• Forme canonique :

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.

Exemple de transformation

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 :

• La contrainte x₁ − x₂ ≥ 2 s’écrit x₂ − x₁ ≤ −2, que l’on transforme en égalité avec une variable d’écart x₃ ≥ 0 :

x₂ − x₁ + x₃ = −2

• La contrainte 2x₁ + 3x₂ ≤ 4 s’écrit :

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

Solutions réalisables, solutions de base et solutions optimales

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.

• Solution réalisable : vecteur X ∈ Rⁿ vérifiant AX = b et X ≥ 0.
• Base : matrice B(m,m) inversible extraite de A.
• Solution réalisable de base : solution réalisable X telle que les composantes hors base X_N = 0 et X_B = B⁻¹b.

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.

Exemple

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.

Résultats fondamentaux de la programmation linéaire

Théorème :

1. Si une solution réalisable existe, alors il existe une solution réalisable de base.
2. Si une solution optimale existe, alors il existe une solution optimale réalisable de base.

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).

Cas particuliers et classification des problèmes

• Problème non réalisable : pas de solution satisfaisant les contraintes.
• Problème non borné : il existe des solutions réalisables avec des valeurs de fonction objectif arbitrairement grandes (ou petites).
• Problème avec solution optimale : il existe une solution réalisable qui maximise (ou minimise) la fonction objectif.

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.

Exemple complet : résolution par introduction de variables d’écart

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₁).

Glossaire des termes clés

• Programmation linéaire (PL) : optimisation d’une fonction linéaire sous contraintes linéaires.
• Programmation linéaire en nombres entiers (PLNE) : PL avec contraintes que les variables soient entières.
• Variables de décision : variables dont les valeurs sont à déterminer pour optimiser la fonction objectif.
• Fonction objectif : fonction linéaire à maximiser ou minimiser.
• Contraintes : égalités ou inégalités linéaires que doivent satisfaire les variables.
• Domaine réalisable : ensemble des solutions satisfaisant les contraintes.
• Forme standard : PL avec contraintes sous forme d’égalités et variables ≥ 0.
• Forme canonique : PL avec contraintes sous forme d’inégalités ≤ et variables ≥ 0.
• Variables d’écart : variables ajoutées pour transformer des inégalités en égalités.
• Solution réalisable : solution satisfaisant toutes les contraintes.
• Solution de base : solution réalisable avec un nombre minimal de variables non nulles (égale au rang de A).
• Solution optimale : solution réalisable qui maximise ou minimise la fonction objectif.
• Base : matrice carrée inversible extraite de la matrice des contraintes.
• Problème non réalisable : aucun vecteur ne satisfait les contraintes.
• Problème non borné : la fonction objectif peut être rendue arbitrairement grande (ou petite) dans le domaine réalisable.

Points clés à retenir

• La programmation linéaire consiste à optimiser une fonction linéaire sous contraintes linéaires.
• Un problème de PL peut toujours être mis sous forme standard ou canonique.
• Les variables d’écart permettent de transformer les inégalités en égalités.
• Les solutions optimales se trouvent parmi les solutions réalisables de base, qui sont finies en nombre.
• Un problème de PL peut être non réalisable, non borné ou posséder une solution optimale.
• La méthode du simplexe exploite la structure des solutions de base pour trouver une solution optimale.
• La PLNE ajoute la contrainte d’intégralité des variables, ce qui complique la résolution.
• La modélisation rigoureuse des variables, contraintes et fonction objectif est essentielle pour appliquer la PL.