Programmation Linéaire

Introduction

Introduction

Recherche opérationnelle

résolution de problèmes d’optimisation

 Introduction

Introduction

Recherche opérationnelle

résolution de problèmes d’optimisation

aide à la décision
 Introduction

Origine

En 1940, au cours de la seconde guerre mondiale, le gouvernement anglais charge

Patrick Blackett de diriger une équipe de recherche pour résoudre certains
problèmes tels que
l’implantation optimale de radars de surveillance,
la gestion des convois d’approvisionnement.
Le terme opérationnelle vient du fait que le travail du groupe était lié à des
opérations militaires.
 Introduction

Origine

En 1940, au cours de la seconde guerre mondiale, le gouvernement anglais charge

Patrick Blackett de diriger une équipe de recherche pour résoudre certains
problèmes tels que
l’implantation optimale de radars de surveillance,
la gestion des convois d’approvisionnement.
Le terme opérationnelle vient du fait que le travail du groupe était lié à des
opérations militaires.

Après la guerre, ces techniques se sont considérablement développées du fait de

la multiplication des domaines d’application,
l’explosion des capacités de calcul des ordinateurs.
 Introduction

La RO est généralement est liée à plusieurs domaines :

Mathématiques appliquées, Informatique, Économie

 Introduction

La RO est généralement est liée à plusieurs domaines :

Mathématiques appliquées, Informatique, Économie

Les applications sont nombreuses :

les chaı̂nes logistiques, la planification,

la gestion de production, l’ordonnancement, la gestion des stocks,
les problèmes d’ingénierie, les réseaux de télécommunication,
etc...
 Programmation linéaire

Sommaire

1 Introduction
2 Programmation linéaire
Formulation du problème
Méthode et interprétation
graphique
Algorithme du simplexe
Détail de l’algorithme
 Programmation linéaire Formulation du problème

Formulation du problème

Programmation Linéaire (PL) = optimisation d’une fonction linaire de variables

devant satisfaire un ensemble de contraintes linéaires de type inégalités et/ou
égalités.
opt z = f (x)
g(x) ≤ d
h(x) = b
xi ≥ 0
avec x = (x1 , . . . , xn ) les variables de décision.
 Programmation linéaire Formulation du problème

Formulation du problème

Programmation Linéaire (PL) = optimisation d’une fonction linaire de variables

devant satisfaire un ensemble de contraintes linéaires de type inégalités et/ou
égalités.
opt z = f (x)
g(x) ≤ d
h(x) = b
xi ≥ 0
avec x = (x1 , . . . , xn ) les variables de décision.

Les composantes d’une problème de PL sont :

les variables : ce sont les valeurs à trouver, la solution du problème [x],

les contraintes : donne l’espace des solutions admissibles [g(·), d, h(·), b],
qu’est-ce qu’on veut optimiser ? [f (·)].
 Programmation linéaire Formulation du problème

Problèmes d’optimisation linéaire sous contraintes :


fonction économique opt z = c 1 x1 + c 2 x2 + . . . c n xn

t11 x1 + t12 x2 + . . . + t1n xn ≤ d1



t21 x1 + t22 x2 + . . . + t2n xn ≤ d2



contraintes .

 ..


tm1 x1 + tm2 x2 + . . . + tmn xn ≤ dm

non-négativité xi ≥ 0 i = 1, . . . , n

(ici, nous écrivons seulement des contraintes inégalités)

 Programmation linéaire Formulation du problème

Exemple 1

Une entreprise fabrique 2 produits, A et B, à partir de 3 matières différentes, M1 ,

M2 et M3 :
pour fabriquer A, il faut 1 tonne de M1 et 2 tonnes de M2 ,
pour fabriquer B, il faut 1 tonne de M1 , 1 tonne de M2 et 1 tonne de M3 .

La vente de 1 tonne de A rapporte 150€ tandis que la vente de 1 tonne de B

rapporte 100€.

L’entreprise possède un stock de :

300 tonnes de M1 ,
400 tonnes de M2 ,
250 tonnes de M3 .
 Programmation linéaire Formulation du problème

Exemple 1

Une entreprise fabrique 2 produits, A et B, à partir de 3 matières différentes, M1 ,

M2 et M3 :
pour fabriquer A, il faut 1 tonne de M1 et 2 tonnes de M2 ,
pour fabriquer B, il faut 1 tonne de M1 , 1 tonne de M2 et 1 tonne de M3 .

La vente de 1 tonne de A rapporte 150€ tandis que la vente de 1 tonne de B

rapporte 100€.

L’entreprise possède un stock de :

300 tonnes de M1 ,
400 tonnes de M2 ,
250 tonnes de M3 .

F Question : combien faut-il fabriquer de produits A et B pour avoir le maximum

de bénéfice ?
 Programmation linéaire Formulation du problème

Analysons le problème :

variables :
x1 → nombre de produits A
x2 → nombre de produits B

le profit est donné par les ventes : z = 150x1 + 100x2

les contraintes sont liées au stock des matières

 Programmation linéaire Formulation du problème

Analysons le problème :

variables :
x1 → nombre de produits A
x2 → nombre de produits B

le profit est donné par les ventes : z = 150x1 + 100x2

les contraintes sont liées au stock des matières

formulation du problème de PL :

max z = 150x1 + 100x2

x1 + x2 ≤ 300
2x1 + x2 ≤ 400
x2 ≤ 250

xi ≥ 0 i = 1, 2
 Programmation linéaire Formulation du problème

Exemple 2

Considérons 3 magasins, A, B et C, ayant commandé 200 containers chacun.

250 containers sont disponibles au dépôt D1 ,
450 containers sont disponibles au dépôt D2 .

Les coûts de transport par containers sont :

magasin A B C
dépôt D1 3.4 2.2 2.9
dépôt D2 3.4 2.4 2.5
 Programmation linéaire Formulation du problème

Exemple 2

Considérons 3 magasins, A, B et C, ayant commandé 200 containers chacun.

250 containers sont disponibles au dépôt D1 ,
450 containers sont disponibles au dépôt D2 .

Les coûts de transport par containers sont :

magasin A B C
dépôt D1 3.4 2.2 2.9
dépôt D2 3.4 2.4 2.5

F objectif : minimiser le coût total de transport des containers des dépôts vers les
magasins.
 Programmation linéaire Formulation du problème

Analysons le problème :

variables :
x1A → nombre de containers depuis le dépôt D1 vers le magasin A
x2A → nombre de containers depuis le dépôt D2 vers le magasin A

(idem pour B et C : x1B , x2B , x1C , x2C )

le coût total de transport est donné par :

z = 3.4x1A + 3.4x2A + 2.2x1B + 2.4x2B + 2.9x1C + 2.5x2C

les contraintes sont liées à la disponibilité des dépôts et à la demande des magasins
 Programmation linéaire Formulation du problème

Analysons le problème :

variables :
x1A → nombre de containers depuis le dépôt D1 vers le magasin A
x2A → nombre de containers depuis le dépôt D2 vers le magasin A

(idem pour B et C : x1B , x2B , x1C , x2C )

le coût total de transport est donné par :

z = 3.4x1A + 3.4x2A + 2.2x1B + 2.4x2B + 2.9x1C + 2.5x2C

les contraintes sont liées à la disponibilité des dépôts et à la demande des magasins

formulation du problème de PL :

min z = 3.4x1A + 3.4x2A + 2.2x1B + 2.4x2B + 2.9x1C + 2.5x2C

x1A + x1B + x1C ≤ 250

x2A + x2B + x2C ≤ 450
x1A + x2A = 200
x1B + x2B = 200
x1C + x2C = 200

xi ≥ 0 i = 1A, 2A, 1B, 2B, 1C, 2C.

 Programmation linéaire Méthode et interprétation graphique

Méthode et interprétation graphique

La méthode graphique pour résoudre un problème de PL est faisable seulement

pour des problèmes à 2, voire 3, variables.

Dans le cas d’un problème à 2 variables, les contraintes peuvent être tracées dans
le plan à 2 dimensions (x1 , x2 ).

On peut alors visualiser l’espace des solutions admissibles. Il faut alors ensuite
déterminer le point du plan, de coordonnées (x∗1 , x∗2 ), optimisant la fonction
économique.
 Programmation linéaire Méthode et interprétation graphique

Méthode et interprétation graphique

La méthode graphique pour résoudre un problème de PL est faisable seulement

pour des problèmes à 2, voire 3, variables.

Dans le cas d’un problème à 2 variables, les contraintes peuvent être tracées dans
le plan à 2 dimensions (x1 , x2 ).

On peut alors visualiser l’espace des solutions admissibles. Il faut alors ensuite
déterminer le point du plan, de coordonnées (x∗1 , x∗2 ), optimisant la fonction
économique.

Reprenons le problème de l’exemple 1 :

max z = 150x1 + 100x2

x1 + x2 ≤ 300 (1)
2x1 + x2 ≤ 400 (2)
x2 ≤ 250 (3)

xi ≥ 0 i = 1, 2 (4)
 Programmation linéaire Méthode et interprétation graphique

Représentons dans le plan (x1 , x2 ), les 5 contraintes.

 Programmation linéaire Méthode et interprétation graphique

Représentons dans le plan (x1 , x2 ), les 5 contraintes.

x2
(1)

(3)

(2)
x1
(4)

⇒ Nous pouvons visualiser l’espace des solutions admissibles.

⇒ Quel point choisir ?
 Programmation linéaire Méthode et interprétation graphique

fonction objectif : z = 150x1 + 100x2

3 z
soit : x2 = − x1 +
2 100
 Programmation linéaire Méthode et interprétation graphique

fonction objectif : z = 150x1 + 100x2

3 z
soit : x2 = − x1 +
2 100
x2

x1
 Programmation linéaire Méthode et interprétation graphique

fonction objectif : z = 150x1 + 100x2

3 z
soit : x2 = − x1 +
2 100
x2

-3/2
x1
 Programmation linéaire Méthode et interprétation graphique

fonction objectif : z = 150x1 + 100x2

3 z
soit : x2 = − x1 +
2 100
x2

x*

x1
 Programmation linéaire Méthode et interprétation graphique

x∗ est le point (x∗1 , x∗2 ) qui maximise le bénéfice z.

La solution x∗ est appelée la solution optimale.

La solution est à l’intersection des contraintes (1) et (2) : (x∗1 , x∗2 ) = (100, 200)

La valeur du bénéfice est donc : z = 35000€.

 Programmation linéaire Méthode et interprétation graphique

x∗ est le point (x∗1 , x∗2 ) qui maximise le bénéfice z.

La solution x∗ est appelée la solution optimale.

La solution est à l’intersection des contraintes (1) et (2) : (x∗1 , x∗2 ) = (100, 200)

La valeur du bénéfice est donc : z = 35000€.

Bénéfice dans d’autres cas :

équilibre entre les produits A et B → x1 = x2 = 130

⇒ z = 32500€ perte de 7%
 Programmation linéaire Méthode et interprétation graphique

x∗ est le point (x∗1 , x∗2 ) qui maximise le bénéfice z.

La solution x∗ est appelée la solution optimale.

La solution est à l’intersection des contraintes (1) et (2) : (x∗1 , x∗2 ) = (100, 200)

La valeur du bénéfice est donc : z = 35000€.

Bénéfice dans d’autres cas :

équilibre entre les produits A et B → x1 = x2 = 130

⇒ z = 32500€ perte de 7%

maximum de produits A → x1 = 200 et x2 = 0

⇒ z = 30000€ perte de 14%

 Programmation linéaire Méthode et interprétation graphique

x∗ est le point (x∗1 , x∗2 ) qui maximise le bénéfice z.

La solution x∗ est appelée la solution optimale.

La solution est à l’intersection des contraintes (1) et (2) : (x∗1 , x∗2 ) = (100, 200)

La valeur du bénéfice est donc : z = 35000€.

Bénéfice dans d’autres cas :

équilibre entre les produits A et B → x1 = x2 = 130

⇒ z = 32500€ perte de 7%

maximum de produits A → x1 = 200 et x2 = 0

⇒ z = 30000€ perte de 14%

maximum de produits B → x1 = 0 et x2 = 250

⇒ z = 25000€ perte de 29%

 Programmation linéaire Méthode et interprétation graphique

Exemple 3 :

max z = 6x1 + 5x2

x1 + x2 ≤ 8 (1)
−2x1 + 3x2 ≤ 6 (2)
x1 − x2 ≤ 2 (3)

xi ≥ 0 i = 1, 2 (4)
 Programmation linéaire Méthode et interprétation graphique

Représentons dans le plan (x1 , x2 ), les 5 contraintes.

x2
(1)

(2)

x1
(4)
(3)
 Programmation linéaire Méthode et interprétation graphique

fonction objectif : z = 6x1 + 5x2

6 z
soit : x2 = − x1 +
5 5

21 / 56
 Programmation linéaire Méthode et interprétation graphique

fonction objectif : z = 6x1 + 5x2

6 z
soit : x2 = − x1 +
5 5
x2

x*

x1

La solution est à l’intersection des contraintes (1) et (3) : (x∗1 , x∗2 ) = (5, 3)

La valeur optimale est donc : z = 9.

 Programmation linéaire Algorithme du simplexe

Algorithme du simplexe

Problème de programmation linéaire :


fonction économique opt z = c1 x1 + c2 x2 + . . . cn xn

t11 x1 + t12 x2 + . . . + t1n xn ≤ d1





 t21 x1 + t22 x2 + . . . + t2n xn ≤ d2
contraintes .
.
.




tm1 x1 + tm2 x2 + . . . + tmn xn ≤ dm


non-négativité xi ≥ 0 i = 1, . . . , n
 Programmation linéaire Algorithme du simplexe

Algorithme du simplexe

Problème de programmation linéaire :


fonction économique opt z = c1 x1 + c2 x2 + . . . cn xn

t11 x1 + t12 x2 + . . . + t1n xn ≤ d1





 t21 x1 + t22 x2 + . . . + t2n xn ≤ d2
contraintes .
.
.




tm1 x1 + tm2 x2 + . . . + tmn xn ≤ dm


non-négativité xi ≥ 0 i = 1, . . . , n

Pour résoudre ce problème quelque soit la dimension et de façon systématique, il

existe l’algorithme du simplexe. Un simplexe est un polyèdre convexe de Rn
possédant (n + 1) sommets.
 Programmation linéaire Algorithme du simplexe

Forme standard du problème de PL

Les inégalités sont transformées en égalités avec l’introduction de variables d’écart

e e
tj1 x1 + . . . + tjn xn ≤ dj ⇔ tj1 x1 + . . . + tjn xn + xj = dj xj ≥ 0
 Programmation linéaire Algorithme du simplexe

Forme standard du problème de PL

Les inégalités sont transformées en égalités avec l’introduction de variables d’écart

e e
tj1 x1 + . . . + tjn xn ≤ dj ⇔ tj1 x1 + . . . + tjn xn + xj = dj xj ≥ 0


fonction économique opt z = c1 x1 + c2 x2 + . . . cn xn

t11 x1 + t12 x2 + . . . + t1n xn + xe1 = d1


t21 x1 + t22 x2 + . . . + t2n xn + xe2



 = d2
contraintes .
.
.



tm1 x1 + tm2 x2 + . . . + tmn xn + xem

= dm


xi ≥ 0 i = 1, . . . , n
non-négativité
xej ≥ 0 j = 1, . . . , m
 Programmation linéaire Algorithme du simplexe

Notons n le nombre de variables total : variables initiales xi + variables d’écart xej .

Nous pouvons réécrire le problème sous la forme :

opt z = cx

Tx = d
x ≥ 0
 Programmation linéaire Algorithme du simplexe

Notons n le nombre de variables total : variables initiales xi + variables d’écart xej .

Nous pouvons réécrire le problème sous la forme :

opt z = cx

Tx = d
x ≥ 0

reprenons l’exemple 1

max z = [150 100 0 0 0]x

max z = 150x1 + 100x2  
  x1  
1 1 1 0 0  x2  300
x1 + x2 + x3 = 300  2 1 0 1 0

 x3

 =  400 
2x1 + x2 + x4 = 400 ⇔ 0 1 0 0 1

 x4

 250
x2 + x5 = 250 x5

xi ≥ 0 i = 1, ..., 5
x ≥ 0
 Programmation linéaire Algorithme du simplexe

Dans la suite nous considérerons la formulation du problème suivant :

min z = cx

Tx = d
x ≥ 0
x (n × 1), c (1 × n), T (m × n) et d (m × 1). Nous supposerons que le système des
contraintes est non-redondant et que m < n.
 Programmation linéaire Algorithme du simplexe

Dans la suite nous considérerons la formulation du problème suivant :

min z = cx

Tx = d
x ≥ 0
x (n × 1), c (1 × n), T (m × n) et d (m × 1). Nous supposerons que le système des
contraintes est non-redondant et que m < n.

Nous appellerons une base B une sous-matrice de T de dimension (m × m) dont les m

colonnes sont linéairement indépendantes. Le rang de la matrice B est donc égal à m.
 Programmation linéaire Algorithme du simplexe

Dans la suite nous considérerons la formulation du problème suivant :

min z = cx

Tx = d
x ≥ 0
x (n × 1), c (1 × n), T (m × n) et d (m × 1). Nous supposerons que le système des
contraintes est non-redondant et que m < n.

Nous appellerons une base B une sous-matrice de T de dimension (m × m) dont les m

colonnes sont linéairement indépendantes. Le rang de la matrice B est donc égal à m.

Dans ce cas, le problème peut s’écrire (avec éventuellement une réorganisation des indices)

min z = cB xB + cR xR

BxB + RxR = d
x ≥ 0

xB (m × 1) sont les variables de base, xB = (xi , i ∈ I)

xR (n − m × 1) sont les variables hors base, xR = (xj , j ∈ J)
 Programmation linéaire Algorithme du simplexe

La solution du système T x = d en posant xR = 0 est appelée la solution de base

associée à la base B. Cette solution est
−1
xB = B d
xR = 0
Cette solution satisfait les contraintes, et si xB ≥ 0, la solution est admissible. La
valeur objectif est alors :
−1
z = cB B d
 Programmation linéaire Algorithme du simplexe

La solution du système T x = d en posant xR = 0 est appelée la solution de base

associée à la base B. Cette solution est
−1
xB = B d
xR = 0
Cette solution satisfait les contraintes, et si xB ≥ 0, la solution est admissible. La
valeur objectif est alors :
−1
z = cB B d

Interprétation graphique : on montre qu’une solution de base admissible correspond à

un sommet du polyèdre.

26 / 56
 Programmation linéaire Algorithme du simplexe

La solution du système T x = d en posant xR = 0 est appelée la solution de base

associée à la base B. Cette solution est
−1
xB = B d
xR = 0
Cette solution satisfait les contraintes, et si xB ≥ 0, la solution est admissible. La
valeur objectif est alors :
−1
z = cB B d

Interprétation graphique : on montre qu’une solution de base admissible correspond à

un sommet du polyèdre.

L’algorithme du simplexe est une procédure itérative qui “navigue” de sommet en

sommet tout en cherchant à réduire la valeur objectif z. A chaque itération, il change
de base B (admissible) de façon “intelligente” jusqu’à atteindre la valeur optimal zmin .
 Programmation linéaire Algorithme du simplexe

Utilisation d’un solveur

max z = x1 + x2

x1 + 3x2 ≤ 12
x1 − x2 ≤ 4

xi ≥ 0 i = 1, 2
 Programmation linéaire Algorithme du simplexe

Utilisation d’un solveur

max z = x1 + x2

x1 + 3x2 ≤ 12
x1 − x2 ≤ 4

xi ≥ 0 i = 1, 2

x2

x1
 Programmation linéaire Algorithme du simplexe

Utilisation d’un solveur

max z = x1 + x2

x1 + 3x2 ≤ 12
x1 − x2 ≤ 4

xi ≥ 0 i = 1, 2

x2

valeur sur chaque sommet :

(1) → z = 0
(2)
(2) → z = 4
(3) (3) → z = 8
(4) → z = 4
(1) (4) x1
 Programmation linéaire Algorithme du simplexe

Utilisation d’un solveur

max z = x1 + x2

x1 + 3x2 ≤ 12
x1 − x2 ≤ 4

xi ≥ 0 i = 1, 2

x2

valeur sur chaque sommet :

(1) → z = 0
(2)
x* (2) → z = 4
(3) (3) → z = 8 → optimal
(4) → z = 4
(1) (4) x1
Solution : x1 = 6 et x2 = 2.

SSI-RO 27 / 56
 Programmation linéaire Algorithme du simplexe

Solveur d’Excel

Le solver est intégré à Excel mais doit être simplement activé.

 Programmation linéaire Algorithme du simplexe

Solveur d’Excel

Le solver est intégré à Excel mais doit être simplement activé.

28 / 56
Programmation linéaire Algorithme du simplexe
Programmation linéaire Algorithme du simplexe
 Programmation linéaire Algorithme du simplexe

Solveur de Scilab

La fonction karmarkar() permet de résoudre le problème :

min cT x
Ae x = be
Ai x ≤ bi

D’autres solveurs sont disponibles à partir de modules d’extension du logiciel.

30 / 56
 Programmation linéaire Algorithme du simplexe

Solveur de Scilab

La fonction karmarkar() permet de résoudre le problème :

min cT x
Ae x = be
Ai x ≤ bi

Syntaxe :

xopt = karmarkar(Ae, be, c, [], [], [], [], [], Ai, bi)

D’autres solveurs sont disponibles à partir de modules d’extension du logiciel.

 Programmation linéaire Algorithme du simplexe

Dans le cas de notre exemple :

min [−1 − 1] x
     
1 3 12 x1
x≤ avec x=
1 −1 4 x2
 Programmation linéaire Algorithme du simplexe

Dans le cas de notre exemple :

min [−1 − 1] x
     
1 3 12 x1
x≤ avec x=
1 −1 4 x2

Dans Scilab :

--> c = [-1 -1]’;

--> Ai = [1 3 ; 1 -1];
--> bi = [12 ; 4];
-->
--> [xopt,fopt] = karmarkar([], [], c, [], [], [], [], [], Ai, bi)

fopt =
- 7.9999347
xopt =
5.9999347
2.

31 / 56
 Programmation linéaire Détail de l’algorithme

Détail de l’algorithme

Considérons la forme standard du problème de PL :

min z = cx

Tx = d
x ≥ 0
x (n × 1), c (1 × n), T (m × n) et d (m × 1). Nous supposerons que le système des
contraintes est non-redondant et que m < n.

Reformulation à partir d’une base B ∈ Rm×m :

min z = cB xB + cR xR

BxB + RxR = d
x ≥ 0

xB (m × 1) sont les variables de base, xB = (xi , i ∈ I)

xR (n − m × 1) sont les variables hors base, xR = (xj , j ∈ J)
 Programmation linéaire Détail de l’algorithme

Forme équivalente du problème :

 
min z = cB B −1 d − cB B −1 R − cR xR

xB + B −1 RxR = B −1 d
x ≥ 0

Soit :
 Programmation linéaire Détail de l’algorithme

Forme équivalente du problème :

 
min z = cB B −1 d − cB B −1 R − cR xR

xB + B −1 RxR = B −1 d
x ≥ 0

Soit :

min z = a00 − α0 xR

xB + AxR = a0

x ≥ 0
 Programmation linéaire Détail de l’algorithme

Forme équivalente du problème :

 
min z = cB B −1 d − cB B −1 R − cR xR

xB + B −1 RxR = B −1 d
x ≥ 0

Soit :

min z = a00 − [a01 . . . a0(n−m) ]xR

   
min z = a00 − α0 xR a11 ... a1(n−m) a10
 . .. .   . 
xB + . .  xR =  . 
xB + AxR = a0 ⇔  . . .   . 
am1 ... am(n−m) am0
x ≥ 0

x≥0
 Programmation linéaire Détail de l’algorithme

Supposons qu’il existe une solution de base initiale admissible :

−1
xB = B d ≥0
xR = 0

conduisant à une valeur objectif z = cB B −1 d.

 Programmation linéaire Détail de l’algorithme

Supposons qu’il existe une solution de base initiale admissible :

−1
xB = B d ≥0
xR = 0

conduisant à une valeur objectif z = cB B −1 d.

Nous définissons le tableau simplexe associé à une base B à partir des coefficient de la
forme équivalente
xj , j ∈ J (variables hors base)

z a00 a01 . . . a0(n−m)

a10

xi , i ∈ I .
. aij
(variables .
de base)
am0

I est l’ensemble des var. de base, xi avec i = 1, . . . , m (dimension de xB )

J est l’ensemble des var. hors base, xj avec j = 1, . . . , n − m (dimension de xR )
 Programmation linéaire Détail de l’algorithme

Le tableau fournit une lecture simple des valeurs courantes :

a00 est la valeur courante de la fonction économique,

ai0 est la valeur courante des variables de base, xi avec i ∈ I.
 Programmation linéaire Détail de l’algorithme

Le tableau fournit une lecture simple des valeurs courantes :

a00 est la valeur courante de la fonction économique,

ai0 est la valeur courante des variables de base, xi avec i ∈ I.

3 cas peuvent se présenter :

absence de solution optimale finie,

amélioration d’une solution de base admissible,
obtention d’une solution de base optimale (arrêt de l’algo).
 Programmation linéaire Détail de l’algorithme

Cas de l’absence de solution optimale finie :

Soit une solution de base admissible, s’il existe k ∈ J tel que

a0k > 0,
aik ≤ 0, ∀i ∈ I,
la fonction économique z peut être aussi petite que l’on veut. Il n’y a donc pas de
solution optimale finie.
 Programmation linéaire Détail de l’algorithme

Cas de l’absence de solution optimale finie :

Soit une solution de base admissible, s’il existe k ∈ J tel que

a0k > 0,
aik ≤ 0, ∀i ∈ I,
la fonction économique z peut être aussi petite que l’on veut. Il n’y a donc pas de
solution optimale finie.

z a00 × ... × >0 × ... ×

× ... × ≤0 × ... ×
xi , i ∈ I ≥0 . . .
. . .
(variables . . .
de base) × ... × ≤0 × ... ×
 Programmation linéaire Détail de l’algorithme

Cas d’amélioration d’une solution de base admissible :

Soit une solution de base admissible et supposons que ∀k ∈ J tel que a0k > 0, il existe
au moins un indice i ∈ I pour lequel aik > 0. Définissons l’indice l tel que
 
al0 ai0
= min .
alk i|aik >0 aik
Si on remplace le vecteur de base associé à la variable xl par le vecteur hors base associé
à la variable xk , on obtient une nouvelle base admissible avec une meilleure solution.
 Programmation linéaire Détail de l’algorithme

Cas d’amélioration d’une solution de base admissible :

Soit une solution de base admissible et supposons que ∀k ∈ J tel que a0k > 0, il existe
au moins un indice i ∈ I pour lequel aik > 0. Définissons l’indice l tel que
 
al0 ai0
= min .
alk i|aik >0 aik
Si on remplace le vecteur de base associé à la variable xl par le vecteur hors base associé
à la variable xk , on obtient une nouvelle base admissible avec une meilleure solution.

a00 × ... × >0 × ... ×

.
.
.
← >0
.
.
.
calcul de
ai0 ← ≥0 >0
aik
.
.
.
← >0
.
.
.
 Programmation linéaire Détail de l’algorithme

Cas de l’obtention d’une solution optimale : (arrêt de l’algo)

Soit une solution de base admissible. Cette solution est optimale si ∀j ∈ J on a a0j ≤ 0.
 Programmation linéaire Détail de l’algorithme

Cas de l’obtention d’une solution optimale : (arrêt de l’algo)

Soit une solution de base admissible. Cette solution est optimale si ∀j ∈ J on a a0j ≤ 0.

a00 ≤0

≥0