Programmation linéaire

Nazih Abderrazzak Gadhi

Forme standard d´un programme linéaire

La forme standard d´un programme linéaire (P) est :

Fondements de la Nazih Abderrazzak Gadhi 2

programmation linéaire
Définition :
On appelle solution réalisable de (P), tout point x=(x1, x2, …, xn) qui vérifie toutes
les contraintes de (P).
Définition :
On appelle ensemble réalisable de (P), l´ensemble de toutes les solutions
réalisables de (P).
Définition :
Une solution réalisable est dite optimale réalisable, si elle minimise ou maximise
la fonction objectif.

Fondements de la Nazih Abderrazzak Gadhi 3

programmation linéaire
Proposition :
Tout problème de la programmation linéaire peut se mettre sous la forme standard.
Démonstration:
1. Contraintes de type :

est appelé variable d´écart.

Fondements de la Nazih Abderrazzak Gadhi 4
programmation linéaire
2. Contraintes de type :

est appelé variable de surplus.

Fondements de la Nazih Abderrazzak Gadhi 5

programmation linéaire
3. Existence des variables libres :
• Méthôde 1 :

• Méthôde 2 :

Fondements de la Nazih Abderrazzak Gadhi 6

programmation linéaire
Remarque :

Fondements de la Nazih Abderrazzak Gadhi 7

programmation linéaire
Exemple :

Fondements de la Nazih Abderrazzak Gadhi 8

programmation linéaire
 • Méthôde 1 :

Fondements de la Nazih Abderrazzak Gadhi 9

programmation linéaire
 • Méthôde 2 :

Fondements de la Nazih Abderrazzak Gadhi 10

programmation linéaire
Ainsi,

Fondements de la Nazih Abderrazzak Gadhi 11

programmation linéaire
Algorithme du simplexe

Algorithme du Nazih Abderrazzak Gadhi 12

simplexe
 Itération du simplexe !!!!

Partant d'un sommet du polygone initial, c'est à dire d'une solution de base
réalisable initiale, on cherche un sommet adjacent, c'est à dire d'une solution de
base réalisable adjacente qui augmente la valeur de la fonction objectif.

Si on veut obtenir une méthode de résolution générale (la méthode graphique

n'est pas possible en grandes dimensions), il faut donc savoir comment passer
d'une solution de base réalisable à une solution de base réalisable adjacente.

Algorithme du Nazih Abderrazzak Gadhi 13

simplexe
Après avoir trouvé un sommet de départ (c.à.d une solution de base réalisable
de départ), chaque itération du simplexe, qui correspond à un changement de de
sommet ( changement de base réalisable ), se déroule en trois étapes :

1. Choix de la variable entrante dans la nouvelle base.

2. Choix de la variable sortante de l'ancienne base.

3. Reformulation du problème en fonction de la nouvelle base.

Algorithme du Nazih Abderrazzak Gadhi 14

simplexe
Résolution algébrique d´un (PL) simple
On considère le problème :

max z = 3x1 + 5x2

sujet à : 3x1 + 2x2 ≤ 18

x1 ≤ 4
2x2 ≤ 12
x1, x2 ≥ 0
Sa représentation graphique est :

Algorithme du Nazih Abderrazzak Gadhi 15

simplexe
Définition :
On appelle sommets adjacents deux sommets que l’on peut joindre par une arête.
Exemple :
Par exemple, (4,3) est adjacent à (2,6) mais (4,3) n’est pas adjacent à (0,0).

Remarque :
Le principe de l’algorithme du Simplexe est de déterminer une solution optimale en
allant de sommet en sommet adjacent.

Algorithme du Nazih Abderrazzak Gadhi 16

simplexe
Pour pouvoir démarrer l’algorithme du Simplexe, il faut ramener les contraintes
d’inégalité en des contraintes d’égalité. Ainsi, notre problème sera sous la
forme standard.
Remarque : Maximiser z, revient à minimiser ( Z = -z ) puis multiplier par -1.

Nous sommes en présence d´un système de trois équations à cinq inconnues.

Algorithme du Nazih Abderrazzak Gadhi 17
simplexe
Premier programme de base : Programme initial

Pour déterminer le programme initial, on pose habituellement à zéro les variables

principales du modèle; ce qui correspond à x1 =0 et x2 = 0.

Notre système de 3 équations à 5 inconnues devient alors un système de 3

équations à 3 inconnues que l´on va pouvoir manipuler : x3 =18 , x4 =4 et x5 = 12
Par conséquent, on obtient la solution de base réalisable (0,0,18,4,12)
où
Variables hors base : x1 =0 et x2 = 0

Variables de base : x3 =18 , x4 =4 et x5 = 12

Pour cette solution de base : Z=0

Algorithme du Nazih Abderrazzak Gadhi 18

simplexe
Algorithme du Nazih Abderrazzak Gadhi 19
simplexe
La nouvelle solution de base est :

Algorithme du Nazih Abderrazzak Gadhi 20

simplexe
 On exprime maintenant Z en fonction des nouvelles variables hors base :

Algorithme du Nazih Abderrazzak Gadhi 21

simplexe
La nouvelle solution de base est :

Algorithme du Nazih Abderrazzak Gadhi 22

simplexe
 On exprime maintenant Z en fonction des nouvelles variables hors base :

Finalement, du fait que z = - Z, on obtient zmax = 36.

Algorithme du Nazih Abderrazzak Gadhi 23

simplexe
Méthode du simplexe appliquée à L´exemple
On associe à chaque itération (opération) de l´exemple un tableau:

Algorithme du Nazih Abderrazzak Gadhi 24

simplexe
Détermination de la variable d´entrée :

Algorithme du Nazih Abderrazzak Gadhi 25

simplexe
 On associe à chaque itération (opération) de l´exemple un tableau:

V.E.

Algorithme du Nazih Abderrazzak Gadhi 26

simplexe
Détermination de la variable de sortie :

Algorithme du Nazih Abderrazzak Gadhi 27

simplexe
 On associe à chaque itération (opération) de l´exemple un tableau:

V.E.

V.S.

Algorithme du Nazih Abderrazzak Gadhi 28

simplexe
Opérations algébriques

Algorithme du Nazih Abderrazzak Gadhi 29

simplexe
V.S.

V.E.

Algorithme du Nazih Abderrazzak Gadhi 30

simplexe
Algorithme du Nazih Abderrazzak Gadhi 31
simplexe
 Algorithme du simplexe
Soit le programme linéaire (P) suivant :

Algorithme du Nazih Abderrazzak Gadhi 32

simplexe
Etape 1 :

Algorithme du Nazih Abderrazzak Gadhi 33

simplexe
Etape 2 :

Algorithme du Nazih Abderrazzak Gadhi 34

simplexe
Etape 3 :

Opérations élémentaires du pivot :

Algorithme du Nazih Abderrazzak Gadhi 35

simplexe
Problème ayant une infinité de solutions:
C´est le cas, si au niveau d´un tableau optimal, une des variables hors
base a un coût nul.

Dans ce cas, si on la fait entrer dans la base, on va obtenir une autre solution de
base optimale sans que la valeur de Z ne change.

⇒ le segment formé par les deux solutions de base optimales contient toutes les
solutions optimales du problème.

Algorithme du Nazih Abderrazzak Gadhi 36

simplexe
 Exemple:

max z = 3x1 + 2x2

sujet à : 3x1 + 2x2 ≤ 120

x1 + x2 ≤ 50
x1, x2 ≥ 0

Algorithme du Nazih Abderrazzak Gadhi 37

simplexe
 T1 x1 x2 s1 s2 bi
s1 33 2 1 0 120 →
s2 1 1 0 1 50
-z 3 2 0 0 0
↑

T2 X1 x2 s1 s2 bi
x1 1 2/3 1/3 0 40
s2 0 1/3
1/3 -1/3 1 10 →
-z 0 0 -1 0 -120
↑
Algorithme du Nazih Abderrazzak Gadhi 38
simplexe
 T3 x1 x2 s1 s2 bi

x1 1 0 1 -2 20
x2 0 1 -1 3 30
-z 0 0 -1 0 -120

Le segment formé par les deux solutions de base optimales

(40, 0, 0, 10) et (20, 30, 0, 0) contient toutes les solutions
optimales du problème.

Algorithme du Nazih Abderrazzak Gadhi 39

simplexe
 Multiplicateurs du simplexe
Définition :
Le vecteur des multiplicateurs du simplexe, associé à la base B, est le vecteur
colonne

tel que :
La base optimale B* est constituée des colonnes des variables de
base finales, lues dans le tableau initial.

L´inverse de la base optimale B* est constituée des colonnes des

variables de base initiales, lues dans le tableau final.
Exemple :
Tableau initial du simplexe :

Algorithme du Nazih Abderrazzak Gadhi 42

simplexe
 Tableau final du simplexe :

Algorithme du Nazih Abderrazzak Gadhi 43

simplexe
La base optimale B* est constituée des colonnes 1, 4 et 2
(variables de base finales, lues dans le tableau initial )

Algorithme du Nazih Abderrazzak Gadhi 44

simplexe
L´inverse de la base optimale B* est constituée des colonnes 3, 4 et 5
(variables de base initiales, lues dans le tableau final)

Algorithme du Nazih Abderrazzak Gadhi 45

simplexe
De plus,

Algorithme du Nazih Abderrazzak Gadhi 46

simplexe
 Application
Modification du terme b dans le problème original

On modifie b de telle sorte que B* demeure réalisable optimale ( on ne touche

pas aux coûts ).

Par conséquent:

On doit avoir :

Peut-on déduire le nouveau Z optimal ? Quelle interprétation économique peut-on faire ?

Algorithme du Nazih Abderrazzak Gadhi 47

simplexe
Exemple :

Algorithme du Nazih Abderrazzak Gadhi 48

simplexe
 On a :

Par définition, on a :

Algorithme du Nazih Abderrazzak Gadhi 49

simplexe
 Ainsi :

Donc : B* demeure une base réalisable optimale.

De plus, x1 diminue de 4/3, x4 augmente de 7/3 et x2 augmente de 1.

Ainsi, Z* = (-3 * 2/3 )+ (0 * 13/3 )+ (-5 * 7 ) = -37.

Algorithme du Nazih Abderrazzak Gadhi 50

simplexe
 On a aussi,

Ainsi, Z* = -36 + Z* = -36 – 1 = -37.

Algorithme du Nazih Abderrazzak Gadhi 51

simplexe
 Intérprétation économique :

Algorithme du Nazih Abderrazzak Gadhi 52

simplexe