Programmation Linéaire
Solution Réalisable
▶ Consièrons un PL sous forme standard A⃗x = ⃗b où A ∈ Mm,n
est de rang plein m ≤ n.
▶ rang(A) = nombre maximal de lignes linéairement
indépendentes (= nombre de colonnes indépendentes).
▶ Alors le système A⃗x = ⃗b admet toujours une solution:
• une infinité de solutions si m < n (cas à étudier),
• une solution unique A−1⃗b si m = n (rien à maximiser).
Definition (Solution Réalisable)
Une solution réalisable est tout vecteur ⃗x ∈ Rn qui satisfait les
contraintes du PL (A⃗x = ⃗b, ⃗x ≥ 0).
▶ On travaillera particulièrement avec les solutions de bases
réalisables.
Programmation Linéaire
Solution de Base Réalisable
▶ Un ensemble de m indices, B ⊂ {1, 2, . . . , n}, est une base si
la sous-matrice AB = [aij ]1≤i≤m,j∈B est invertible.
• Les variables en base sont les ⃗xB = {xj , j ∈ B}.
!
⃗xB
• Et ⃗x = , où ⃗xH = {xj , j ∈
/ B} constituent les
⃗xH
variables hors base.
▶ Alors la matrice A peut être décomposée comme
h i
A = AB | AH en réarrangeant au besoin les indices et
A⃗x = AB ⃗xB + AH ⃗xH .
Programmation Linéaire
Solution de Base Réalisable
Definition !
⃗xB
On appelle solution de base tout ⃗x = tel que ⃗xH = ⃗0
⃗xH
(pas nécessairement
! réalisable). Une solution de base réalisable
⃗xB
⃗x = ⃗0 satisfait en plus A⃗x = ⃗b et donc ⃗xB = A−1 ⃗
B b.
▶ Le nombre maximal de solutions de bases est de Cnm
(réalisables ou non).
▶ Nous avons la caractérisation suivante des solutions (de base)
réalisables.
Programmation Linéaire
Solution de Base Réalisable
Theorem (Polytope convexe des solutions réalisables)
• L’ensemble P = {⃗x ∈ Rn | A⃗x = ⃗b}, des solutions réalisables
d’un PL, est un polytope convexe fermé (possiblement non borné).
• Les sommets du polytope P sont constitués par l’ensemble des
solutions de base réalisables du PL.
• L’optimum du PL, s’il existe, est atteint en au moins un sommet
de P.
▶ Il suffit donc de parcourir les sommets du polyhèdre P pour
trouver la valeur optimale d’un PL standard.
▶ Il y a 3 cas de figures possibles:
• Un problème irréalisable (P = ∅).
•P= ̸ ∅ et la fonction objective est non bornée sur P. Alors il
n y a pas de solution (le supremum est zmax = +∞).
• P ̸= ∅ et la fonction objective est bornée sur P. Il existe
alors au moins une solution.
Programmation Linéaire
Complexité Du Parcours Exhaustif Des Sommets de P
▶ La résolution du sytème AB ⃗xB = ⃗b par factorisation LU ou la
méthode de Gauss requière environ O(m3 ) opérations.
▶ Alors, le nombre d’opérations requises pour trouver toutes les
solutions de base est de l’ordre de O(m3 · Cnm ). Ceci croit très
vite avec m et n.
▶ Il faut alors une méthode alternative qui réduise la complexité
du problème.
▶ On aura besoin de la proposition suivante pour passer d’un
sommet à un autre.
Programmation Linéaire
Vecteur Des Coûts Réduits
Lemma (Coût Réduit)
!
⃗x0B
Soit ⃗x0 = ⃗0H une solution de base réalisable associée à une
!
⃗xB
base B. Alors pour tout ⃗x = ∈ P on a:
⃗xH
⃗c · ⃗x = ⃗c · ⃗x0 + LT
H⃗xH , (1)
où ⃗LH = ⃗cHT − ⃗cBT A−1
B AH est le vecteur des coûts réduits.
Proof.
On a A⃗x = ⃗b alors ⃗xB = A−1 ⃗
B (b − AH ⃗
xH ) et donc:
⃗c · ⃗x = ⃗cB · ⃗xB + ⃗cH · ⃗xH = ⃗cBT A−1⃗ c T A−1 AH ⃗xH + ⃗cH · ⃗xH .
B b −⃗ B B
Programmation Linéaire
L’Algorithme Du Simplexe (Dantzig 1947)
▶ Trouver une solution de base réalisable ⃗x0 associée à une base
B.
▶ Ensuite déterminer le vecteur des coûts réduits ⃗LH .
▶ Si tous les coefficients de ⃗LH sont négatifs ou nuls, alors ⃗x0
est optimal.
▶ Sinon on change de base en faiant entrer un indice e et sortir
un autre indice s de façon à améliorer au mieux la fonction
⃗ = A−1
objective. Soit w ⃗e
B A , alors les indices e, s et la valeur
de la coordonée xe sont donnés par:
e = arg max{(⃗LH )j / (⃗LH )j > 0}.
j
n (⃗x ) o
B i
⃗xe = min / wi > 0 .
i wi
n (⃗x ) o
B i
s = arg min / wi > 0 .
Programmation Linéaire
L’Algorithme Du Simplexe (Exemple)
Example (Exemple 1 continued)
Renommons les variables x , y , u, v de notre exeple précédent par
x1 , x2 , x3 , x4 . Alors le PL s’écrit.
max(z = 8x1 + 10x2 )
2x1 + x2 + x3 = 50
x1 + 2x2 + x4 = 70
x1 , x2 , x3 , x4 ≥ 0
Programmation Linéaire
Exemples (Simplexe)
▶ Refaire l’exemple 2 de la dernière fois en utilisant l’algorithme
du simplexe.
▶ Résoudre par la méthode du simplexe le PL suivant:
max(z = 2x1 − 4x2 + 5x3 )
3x1 + 2x2 + x3 ≤ 6
3x1 − 6x2 + 7x3 ≤ 9
x1 , x2 , x3 ≥ 0
Programmation Linéaire
Résolution Exemple 1 Avec R
library(lpSolve) # pour charger "lpSolve" pour la PL
obj = c(8,10); contr.drt = c(50, 70) # definition de "c" et
contr.mat = matrix(c(2,1,1,2), nrow = 2, byrow = 'TRUE')
# en colonnes par defaut
contr.dir <- c("<=", "<=") # vecteurs des inegalites
optimal=lp(direction="max", obj, contr.mat, contr.dir, cont
print("La valeur optimale et le sommet realise sont:")
## [1] "La valeur optimale et le sommet realise sont:"
optimal$objval; optimal$solution
## [1] 380
## [1] 10 30
