Programmation Linéaire

Conditions D’Arrêt de l’Algo du Simplexe

▶ Si tous les coûts réduits sont négatifs (⃗LH < 0), alors il existe
un optimum unique.
▶ Si (⃗LH )e = 0 et xe > 0 alors l’optimum est atteint mais n’est
pas unique.
▶ Cas dégénéré: Si (⃗LH )e = 0 et xe = 0, alors l’unique
optimum est atteint.
▶ Si (⃗LH )e > 0 et xe = +∞ alors la fonction objective n’est pas
majorée et il n’y
n a pas de solutionooptimale (zmax = +∞).
c’est le cas où (⃗xwBi)i / wi > 0 = ∅.
Base Dégénérée Et Règle De Bland (Simplexe)

Definition
Une solution de base réalisable est dite dégénérée si une des
variables en base est nulle. Dans ce cas l’algorithme du simplexe
peut tourner indéfiniment en retrouvant une base déjà rencontrée.

Theorem
L’algorithme du simplexe s’arrête en temps fini si aucune base
dégénérée n’est rencontrée lors de son implémentation.

▶ Règle de Bland(1977): On choisit l’indice le plus petit si

plusieurs variables sont susceptibles d’entrer dans la base.
Alors l’algorithme du simplexe est garantie de s’arrêter en
temps fini.
Variables Auxilliaires
▶ Il peut s’avèrer fastidieux de trouver à priori une solution de
base réalisable pour un PL donné.
▶ En introduisant des variables auxilliaires a1 , a2 , . . . , am ≥ 0,
on peut initialiser le problème originel par une base réalisable
en résolvant le problème auxilliaire (PLA) suivant.
m
X
min ai
(~
x,~
a)
i=1
(
A⃗x + ⃗a = ⃗b
⃗x ≥ 0, ⃗a ≥ 0
▶ Le PL originel admet une solution de base réalisable si et
seulement si le problème auxillaire PLA admet une solution
optimale avec ⃗a = ⃗0.
▶ Donc on tourne l’algorithme du simplexe pour PLA. Si à la fin
la valeur optimale est nulle, on cherche à éliminer les variables
artificielles, en se passant au besoin des contraintes
rédondantes. Sinon le problème est irréalisable (P = ∅).
Algorithme Du Simplexe À Deux Phases

1. Phase 1: Introduire le problème auxilliaire à résoudre par la

méthode du simplexe pour obtenir une base initiale. Et utiliser
la règle de Bland pour la variable entrante.
2. Phase 2: Après avoir obtenu une solution de base réalisable,
dérouler l’algorithme du simplexe pour le problème originel,
toujours en appliquant la règle de Bland.

Example (Fiche 1 Pb.2)

max(2x1 − x2 )
~
x


 2x2 + 3x3 = 1
2x1 + 3x2 − x3 = 5
x1 , x2 , x3 ≥ 0


Programmation Linéaire

Complexité du Simplexe
▶ Klee & Minty (1972) ont produit un exemple de PL avec une
complexité exponentielle en O(2n ) opérations.
▶ Mais en général, la complexité de l’algorithme du simplexe est
polynomiale en O(m3 ) par rapport au nombre m de
contraintes.
▶ Des méthodes ont été tenté pour réduire la complexité du
simplexe.
▶ Pour certains problèmes particuliers (transport), la complexité
est réduite due à la sparsité de la matrice A des contraintes.
Programmation Linéaire
Un Problème De Transport
Example (Fiche 1 Pb.6 — Dantzig 1963)
Un distributeur dispose de deux conserveries situées à Seattle et
San Diego. Les conserveries peuvent remplir 350 et 650 caisses de
boîtes par jour, respectivement.
Le distributeur exploite trois entrepôts à travers les US, un à New
York, un autre à Chicago et un dernier à Kansas City. Chacun des
entrepôts peut vendre au moins 300 caisses par jour.
Il souhaite déterminer le nombre de caisses à expédier des deux
conserveries vers les trois entrepôts, en minimisant le coût total de
transport, afin que chaque entrepôt reçoive autant de caisses qu’il
peut en vendre quotidiennement.
Le fret par caisse et par millier de miles est de 90 USD. Formuler
un programme linéaire pour ce problème. Les distances entre les
différentes locations sont présentées en milliers de miles dans le
tableau suivant.
Programmation Linéaire
Un Problème De Transport
Example (Fiche 1 Pb.6 Continued)
New York (E1) Chicago (E2) Kansas City (E3
Seattle (C1) 2500 1700 1800
San Diego (C2) 2500 1800 1400

Solution
Dénotons par Xij , le nombre de caisses à convoyer Ci Ej. Alors le
PL à résoudre est le suivant:
  


 min z = 225X11 + 153X12 + 162X13 + 225X21 + 162X 22 + 126X23

X11 + X12 + X13 ≤ 350





X21 + X22 + X23 ≤ 650




X11 + X21 ≥ 300



 X12 + X22 ≥ 300
X13 + X23 ≥ 350

Programmation Linéaire
Le Problème De Transport Général
▶ Le problème de transport peut être exprimé de manière
générale sous la forme suivante:

Xm X n


 min cij xij
aij


i=1 j=1







n


 X
xij = ai (LTP)


 j=1


 Xm




 xij = bj
i=1



xij ≥ 0 ∀i, j


m
X n
X
▶ Avec la condition de balance ai = bj .
i=1 j=1
▶ Nous étudierons le (LTP) dans le cadre de l’optimisation en
nombres entiers.
Programmation Linéaire
Le Problème Dual
Definition (Dual d’un PL)
Soient ⃗c ∈ Rn , A ∈ Mm,n , et ⃗b ∈ Rm . Considèrons le
programme linéaire canonique suivant:

max ⃗c · ⃗x (2)
⃗ n
x ∈R
(
A⃗x ≤ ⃗b
⃗x ≥ 0
On définit le dual du PL (2) par le problème de PL suivant:

min ⃗b · ⃗y (3)
⃗ m
y ∈R
(
AT ⃗y ≥ ⃗c
⃗y ≥ 0
Programmation Linéaire
Le Problème Dual
▶ Le problème de maximisation sur Rn devient une minimisation
sur Rm (ou vice-versa).

▶ Le vecteur objectif ⃗c est interchangé avec le vecteur des

contraintes ⃗b.

▶ La matrice des contraintes A ∈ Mm,n , est remplacée par sa

transposée AT ∈ Mn,m ,.

▶ Et les contraintes d’inégalités changent de direction.

▶ Le théorème suivant établit la relation entre les solutions des
problèmes primal et dual.

Theorem (Théorème De Dualité)

Un PL admet une solution optimale ssi son dual aussi admet une
solution optimale avec la même valeur objective.
Programmation Linéaire

Le Problème Dual
Theorem (Des Écarts Complémentaires)
Soient ⃗x ∈ Rn et y ∈ Rm deux solutions réalisables respectivement
d’un (PL) et de son dual (DL). Une condition nécessaire et
suffisante pour quelles soient toutes les deux optimales est:
 h i
 yi (A⃗x )i − bi = 0, ∀i = 1, . . . , m;
h i
 x c − (AT ⃗ y ) = 0, ∀j = 1, . . . , n.
j j j
Programmation Linéaire
Théorème Des Écarts Complémentaires
Example (Fiche 1 - Pb3.)
Considèrons le PL suivant:

max(2x + y)
~
x


 x + 2y ≤ 14

 2x − y ≤ 10

 x −y ≤3


x , y ≥ 0.
 20 11 T
(a) Vérifier que ⃗x∗ = , est une solution réalisable.
3 3
(b) Écrire le problème dual et montrer en utilisant le théoréme
 20 11 T
des écarts complementaires que ⃗x∗ = , est une
3 3
solution optimale.
Programmation Linéaire
Analyse de Sensibilité
Example (Analyse de Sensibilité)
Considèrons le PL suivant:

max(x − 5y)
~
x


 −x + y ≤ 5

 x + 4y ≤ 40
 2x + y ≤ 20



x , y ≥ 0.
(a) Vérifier que ⃗x∗ = (4, 9)T est une solution optimale.

(b) On fait varier légèrement une composante du vecteur des

contraintes ⃗b = (5, 40, 20)T de sorte que la fonction objective
décroisse et que la base optimale reste la même. Quelle doit être
cette composante de ⃗b? Et dans quel sens la varier, une croissance
ou une décroissance?