RECHERCHE OPERATIONNELLE

Ahmed Fouad El Ouafdi

Département d’informatique
Faculté des sciences Agadir
2022/2023

1
Objec1fs du module

• Comprendre les possibilités et les limites de ce type de méthodes,

• Reconnaître les problèmes pour lesquels la RO pourrait se révéler un
instrument
• Perme=re de formaliser et d'analyser les problèmes de décision
complexes rencontrés dans plusieurs domaines, citons : logisCque et
distribuCon, planificaCon, emploi du temps...

2
CONTENU DU MODULE

1. Programmation linéaire : Méthode de simplexe et dualité

2. Programmation en nombres entiers
3. Terminologie des graphes
4. Algorithmes du chemin critique
5. Problème du flot optimal
6. La méthode PERT
7. PrograFile d’attente

3
Recherche opérationnelle (RO)

• Ensemble des méthodes et techniques rationnelles orientées

vers la recherche du meilleur choix dans la façon d'opérer en
vue d'aboutir au résultat visé ou au meilleur résultat possible ou
encore au résultat optimal.
• Elle fait partie des « aides à la décision » dans la mesure où
elle propose des modèles conceptuels en vue d'analyser et de
maitriser des situations complexes pour permettre aux
décideurs de comprendre, d'évaluer les enjeux et d'arbitrer ou
de faire les choix les plus efficaces.

4
 Origines de la RO

• Période : 2éme guerre,

Responsable : armée britannique,
Problèmes posés : implantation optimale de radars de
surveillance.

• RO = Application des mathématiques et des méthodes

scientifiques aux opérations militaires.

5
• Modélisation
Traduction de problèmes réels en
équations mathématiques
• Optimisation
Identification de la meilleure configuration
possible d’un système
• Simulation
Reproduction du fonctionnement d’un
système complexe par un ordinateur

6
Techniques de la RO

vLa programmation mathématique

ü programmation linéaire
ü programmation quadratique
ü programmation en nombres entiers
ü programmation non linéaire

vAnalyses de réseaux et graphes

vThéories des files d’attentes Simulation
vAnalyse statistique et intelligence artificielle
vThéorie des jeux
vChamps d’application de la RO
ü Industries Gouvernement Agences Hôpitaux
ü Institutions d’éducation ...

7
Modèle de programma1on linéaire

• Modéliser un problème en programmation linéaire consiste à identifier :

üles variables intrinsèques (inconnues)
üles différentes contraintes au quelles sont soumises ces variables
ü l’objectif visé (optimisation).

• Deux propriétés particulières :

1. Additivité des variables : l’effet global des actions prises (variables) est égale à la
somme des effets particuliers de chacune des actions (variables). Il n’y a pas
d’effet croisé des actions
2. Les variables prennent toujours des valeurs non négatives

8
9
Exemple introduc1f: cas Produc1on
1 lingot Acier LQ (300DH) 1 lingot Acier HQ (800€)

2kg 1kg

4kWh 5kWh

3h 10h

Produc@on par lot de 1000 lingots.

Les contraintes de l’entreprise sont sur les ressources :

8 000kg 20 000kWh 30 000h

Pb : Combien de lots de lingots de chaque type faut-il produire

pour maximiser le chiffre d’affaires ? 9
10

Chap. 2 - Programmation linéaire

2.2 Formalisation du programme

• Variable de décisions
• Contraintes
• Fonction-objectif

10
 Formalisa)on du problème (1/3)
11

1) Variables de décision

11
 Formalisa)on du problème (2/3)
12

2) Contraintes

Il y a aussi des contraintes logiques : on produit des quantités

positives !

12
 Solu)ons
13

Solutions admissibles

L’ensemble des solu@ons admissibles est, en général, infini :

c’est un polygone convexe = un « simplexe »

13
 Représenta)on graphique
14

1)Matière premières 2)Energie 3)Laminage 4)Logique 14

 Formalisa)on du problème (3/3)
15

3) Critère d’op@misa@on – Fonc@on-objec@f

La fonction-objectif étant linéaire, et les contraintes étant des

inéquations linéaires, on parle d’une programmation linéaire.

15
 Formalisa)on du problème (3/3)
16

4) Programme linéaire d’op@misa@on

La fonction-objectif étant linéaire, et les contraintes étant des

inéquations linéaires, on parle d’une programmation linéaire.

16
 Solutions
17

Solu@on op@male

Théorème
S’il existe une solu@on op@male, alors elle est égale à un
sommet du simplexe de l’ensemble des solu@ons admissibles.

17
18

Programmation linéaire

Méthode graphique
• Sommets du simplexe
• Droite isoprofit
• Fonc@on-objec@f

18
 Méthode graphique
19

Point O :

19
 Méthode graphique
20

Point D, solu@on de :

Toute la Ma?ère Première est u@lisée :

la contrainte est « saturée »
càd la ressource est épuisée

Z=1200k€

20
 Méthode graphique
21

Point C, solution de :

Les contraintes Ma?ère Première et Energie

sont saturées

Z=2067k€

21
 Méthode graphique
22

Point A, solution de :

La contrainte Laminage est saturée

Z=2400k€

22
 Méthode graphique
23

Point B, solu@on de :

Les contraintes Laminage et Energie

sont saturées

Z=2520k€

23
 Méthode graphique
24

24
25

Chap. 2 - Programma1on linéaire

2.4 Algorithme du simplexe

• Forme canonique
• Forme standard
• Solution initiale
• Tableau initial
• Variable entrant dans la base
• Variable sortant de la base
• Arrêt de l’algorithme

25
 Algorithme du simplexe (max)
26

• Pour 2 variables, l’ensemble des solu@ons admissibles est

un polygone convexe. On peut u@liser la méthode graphique.

• Au-delà de trois variables, la méthode graphique n’est plus

u@lisable. On u@lise alors « l’algorithme du simplexe »

26
 Algorithme du simplexe
27

Algorithme du simplexe

27
 Forme canonique
28

Maximiser

28
 Forme canonique
29

Pour écrire le programme sous forme canonique,

il faut éventuellement effectuer les transforma@ons :

29
 Variables d’écart
30

Exemple :

quan@té de Ma@ère Première restante

quan@té d’Energie restante
quan@té de Laminage restant

30
 Forme standard
31

Forme canonique Forme standard

Exemple :

31
 Solu)on ini)ale admissible
32

1) Soit il y a une solu@on ini@ale admissible évidente :

2) Soit il n’y a pas de solution initiale admissible évidente :

Ce cas sera traité en TD.

32
 Etape 0 : tableau initial
33

Base Résultat
2 1 1 0 0 8
4 5 0 1 0 20
3 10 0 0 1 30

-Z 300 800 0 0 0 0

33
 Etape 0 : tableau initial
34

Base Résultat
2 1 1 0 0 8
4 5 0 1 0 20
3 10 0 0 1 30
-Z 300 800 0 0 0 0

• La fonction-objectif s’écrit en fonction des variables hors-

base : coefficients non nuls pour les variables hors-base.
• On lit la valeur de –Z dans Résultat. 34
 Etape 1 : choix du pivot, variable entrante
35

300 800 0 0 0 0

35
 Interprétation géométrique
36

Base Résultat

2 1 1 0 0 8
4 5 0 1 0 20
3 10 0 0 1 30
-Z 300 800 0 0 0 0

36
 Etape 1 : choix du pivot, variable sortante
37

Base Résultat
2 1 1 0 0 8
4 5 0 1 0 20
3 10 0 0 1 30

37
 Interprétation géométrique
38

Base Résultat Rapport

2 1 1 0 0 8 8/1=8
4 5 0 1 0 20 20/5=4
3 10 0 0 1 30 30/10=3
-Z 300 800 0 0 0 0

On choisit le plus pe?t rapport :

38
 Etape 1 : choix du pivot
39

Base Résultat Rapport

2 1 1 0 0 8 8/1=8
4 5 0 1 0 20 20/5=4
3 10 0 0 1 30 30/10=3
-Z
-z 300 800 0 0 0 0

1) Variable entrant : plus grand coefficient de la fonction objective

2) Variable sortant : plus petit rapport

On obtient ainsi le coefficient qui va servir de pivot

39
 Etape 2 : mise à jour du tableau
40

Base Résultat

2 1 1 0 0 8
4 5 0 1 0 20
3 10 0 0 1 30
-Z 300 800 0 0 0 0

Base Résultat

1,7 0 1 0 -0,1 5

2,5 0 0 1 -0,5 5

0,3 1 0 0 0,1 3

-Z 60 0 0 -80 0 -2 400

40
 Interprétation géométrique
41

Base Résultat
1,7 0 1 0 -0,1 5
2,5 0 0 1 -0,5 5
0,3 1 0 0 0,1 3
-Z 60 0 0 -80 0 -2 400

41
 Itération étape 1
42

Et on recommence à l’étape 1, si l’on peut améliorer la fonction-objectif.

Base Résultat Rapport

1,7 0 1 0 -0,1 5
2,5 0 0 1 -0,5 5 5/2,5=2
0,3 1 0 0 0,1 3 3/0,3=10
-Z 60 0 0 -80 0 -2 400 -2 400

42
 Itération étape 2
43

Base Résultat

1,7 0 1 0 -0,1 5
2,5 0 0 1 -0,5 5
0,3 1 0 0 0,1 3
-z 60 0 0 -80 0 -2 400

Base Résultat

0 0 1 -0,68 0,24 1,6

1 0 0 0,4 -0,2 2

0 1 0 -0,12 0,16 2,4

-Z 0 0 0 -24 -68 -2 520

Et on recommence à l’étape 1, si l’on peut améliorer la fonction-objectif. 43

 Interprétation géométrique
44

Base Résultat
0 0 1 -0,68 0,24 1,6
1 0 0 0,4 -0,2 2
0 1 0 -0,12 0,16 2,4
-Z 0 0 0 -24 -68 -2 520

44
45

Arrêt de l’algorithme
Base Résultat

0 0 1 -0,68 0,24 1,6

1 0 0 0,4 -0,2 2

0 1 0 -0,12 0,16 2,4

-Z 0 0 0 -24 -68 -2 520

Le programme est donc optimum : on lit dans Résultat :

45
l’algorithme du simplexe

46
Forme standard
• Après avoir transformé les contraintes d’inégalité en égalités, nous retrouvons le
problème sous sa forme standard où certaines variables peuvent être des
variables d’écart:

min
Sujet à
z = c1 x1 + c2 x2 + ... + cn xn
a11 x1 + a12 x 2 + ... + a1n x n = b1
a 21 x1 + a 22 x 2 + ... + a 2 n x n = b2
. . . .
. . . .
a m1 x1 + a m 2 x 2 + ... + a mn x n = bm
x1 , x 2 , ..., x n ³ 0
47
 min z

Sujet à

a11 x1 + a12 x 2 + ... + a1n x n = b1

a 21 x1 + a 22 x 2 + ... + a 2 n x n = b2
. . . .
. . . .
a m1 x1 + a m 2 x 2 + ... + a mn x n = bm

c1 x1 + c 2 x 2 + ... + c n x n - z = 0
x1 , x 2 , ..., x n ³ 0

48
Simplexe –forme avec tableaux
Itération typique
• Décrivons une itération typique pour résoudre le problème général avec le simplexe – forme avec
tableaux

• Le système
x1 + + a 1m +1 x m +1 + ... + a 1s x s + ... + a 1n x n = b1
x2 + + a 2 m +1 x m +1 + ... + a 2 s x s + ... + a 2 n x n = b 2
. . . .
x r + + a rm +1 x m +1 + ... + a rs x s + ... + a rn x n = b r
. . . .
x m + a mm +1 x m +1 + ... + a ms x s + ... + a mn x n = b m
c m +1 x m +1 + ... + c s x s + ... + c n x n = z - z

49
Itération typique

peut être représenter dans le tableau suivant

50
Étape 1: Choix de la variable d’entrée
{ }
c s = min c j
1£ j £ 0
• En se référant à la dernière ligne du tableau, soit
Variable d’entrée
Si c s ≥ 0, alors la solution
courante est optimale et
l’algorithme s’arrête

Si c s < 0, alors xs est la

variable d’entrée

51
Étape 2: Choix de la variable de sortie
xi = bi - a is xs ³ 0
Si a is £ 0 " 1 £ i £ m
le problème n’est pas Variable d’entrée
borné et l’algo. s’arrête

Si $ i tel que a is > 0

alors la sol. demeure réalisable
ó " i tel que a is > 0
bi
xi = b i - a is x s ³ 0 Û x s £
a is
La variable d’entrée xs prend la valeur –
br ìï b i üï
xs = = min í : a is > 0ý
a rs 1£ i £ m ïî a is ïþ
52
Étape 2: Choix de la variable de sortie

Variable d’entrée

Variable de sortie

53
Étape 3: Pivot L’élément de pivot est à l’intersection de la
ligne
a rs de la variable d’entrée xs et de la colonne
de la variable de sortie xr
Variable d’entrée

a rs

Variable de sortie

a rs

54
Étape 3: Pivot
Divisons la ligne r par l’élément
de pivot a rs afin d’obtenir la
ligne r résultante
Variable d’entrée
a rs

Variable de sortie

1
a rs

55
Étape 3: Pivot
Divisons la ligne r par l’élément
de pivot a rs afin d’obtenir la
ligne r résultante
Variable d’entrée
a rs

Variable de sortie

1 ar m +1 arn br
!1!
ars ars ars ars

56
Étape 3: Pivot
Multiplions la ligne r résultante
par a is pour la soustraire de la
ligne i du tableau. Ceci ramène le
coefficient de la variable d’entrée xs à 0. Variable d’entrée
a rs

Variable de sortie

1 ar m +1 arn br
!1!
ars ars ars ars

57
Étape 3: Pivot
Multiplions la ligne r résultante
par a is pour la soustraire de la
ligne i du tableau. Ceci ramène le
coefficient de la variable d’entrée xs à 0. Variable d’entrée
a rs

Variable de sortie

1 ar m +1 arn br
!1!
ars ars ars ars

58
Étape 3: Pivot
Multiplions la ligne r résultante
par a is pour la soustraire de la
ligne i du tableau. Ceci ramène le
coefficient de la variable d’entrée xs à 0. Variable d’entrée
a rs

Variable de sortie

1 ar m +1 arn br
!1!
ars ars ars ars

59
Étape 3: Pivot
Multiplions la ligne r résultante
par a is pour la soustraire de la
ligne i du tableau. Ceci ramène le
coefficient de la variable d’entrée xs à 0. Variable d’entrée
a rs

Variable de sortie

1 ar m +1 arn br
!1!
ars ars ars ars

60
Tableau résultant
pour amorcer la prochaine itération

61
 Problèmes équivalents

min z = –8x – 6y min z

Sujet à Sujet à
5x + 3y + 𝑢 =30 5x + 3y + u =30
2x + 3y +𝑝 =24 2x + 3y + p =24
1x + 3y + h = 18 1x + 3y +h = 18
x, y, u, p, h ≥ 0 –8x –6y –z = 0
x, y, u, p, h ≥ 0
u, p, h : des variables d’écart

62
 Tableau équivalent au système

min z = –8x – 6y min z

Sujet à Sujet à
5x + 3y + u =30 5x + 3y + u =30
2x + 3y + p =24 2x + 3y + p =24
1x + 3y + h = 18 1x + 3y + h = 18
x, y, u, p, h ≥ 0 –8x –6y –z = 0
x, y, u, p, h ≥ 0

u = 30 – 5x – 3y
p = 24 – 2x – 3y
h = 18 – 1x – 3y
z = 0 –8x – 6y

63
 u = 30 – 5x – 3y
p = 24 – 2x – 3y
h = 18 – 1x – 3y
z = 0 –8x – 6y

Étale 1: Critère d’entrée

Pour déterminer la variable d’entrée,
nous choisissons l’élément le plus
petit de la dernière ligne du tableau
c s = min c j
1£ j £ n
{ } min {–8, –6, 0, 0, 0} = –8.
x est donc la variable d’entrée

64
 u = 30 – 5x – 3y
p = 24 – 2x – 3y

h = 18 – 1x – 3y

z =0 –8x – 6y

Étape 2: critère de sortie variable d’entrée

Pour identifier la variable de sortie

déterminons le min des quotients des

termes de droite divisés par les

éléments correspondants dans la

colonne de la variable d’entrée

qui sont positifs:

br ìï b i üï
xs = = min í : a is > 0ý
a rs 1£i £ m ï a is ïþ
î

65
 u = 30 – 5x – 3y
p = 24 – 2x – 3y
h = 18 – 1x – 3y
z = 0 –8x – 6y

Étape 2: critère de sortie variable d’entrée

min {30/5, 24/2, 18} = 30/5 = 6

La variable correspondante u
devient la variable de sortie
br ìï b i üï
xs = = min í : a is > 0ý
a rs 1£i £ m ï a is ïþ
î

66
 u = 30 – 5x – 3y
p = 24 – 2x – 3y
h = 18 – 1x – 3y
z = 0 –8x – 6y

Variable de sortie variable d’entrée

Étape 3 : Pivot
Transformation du système ou
du tableau

67
• variable de sortie

variable d’entrée
Ceci est équivalent à
(5x + 3y + u =30) / 5 => x + 3/5y + 1/5u =6

En terme du tableau, ceci est équivalent à diviser la ligne de la variable de

sortie par le coefficient de la variable d’entrée dans cette ligne

68
 Divisons cette ligne par 5
• variable de sortie

variable d’entrée
Ceci est équivalent à
(5x + 3y + u =30) / 5 => x + 3/5y + 1/5u =6

En terme du tableau, ceci est équivalent à diviser la ligne de la variable de

sortie par le coefficient de la variable d’entrée dans cette ligne

69
 Divisons cette ligne par 5
variable de sortie

variable d’entrée

Le tableau qui en résulte est le suivant

x + 3 / 5 y + 1/ 5u = 6

70
 Divisons cette ligne par 5
variable de sortie

variable d’entrée

Le tableau qui en résulte est le suivant

x + 3 / 5 y + 1/ 5u = 6

71
 deuxième ligne
moins
2(la première ligne)

Ceci est équivalent à : p = 24 – 2(6 – 1/5u – 3/5y) +2x – 2x – 3y

ó 2x + 3y + p – 2 (x +3/5y + 1/5u) = 24 – 2(6)

ó 2x + 3y + p = 24

– 2 (x +3/5y + 1/5u = 6)
0x + 9/5y –2/5u + p = 12

72
 deuxième ligne
moins
2(la première ligne)

Le tableau devient

0 x + 9 / 5 y - 2 / 5u + p = 12

73
 deuxième ligne
moins
2(la première ligne)

Le tableau devient

0 x + 9 / 5 y - 2 / 5u + p = 12

74
En répétant le processus pour les autres lignes du tableau

75
Méthode du simplexe – notation matricielle

76
Méthode du simplexe – notation matricielle
• Le problème de programmation linéaire sous la forme standard

min

z = c1 x1 + c2 x2 + ... + cn xn
Sujet à

a11 x1 + a12 x 2 + ... + a1n x n = b1

T
a 21 x1 + a 22 x 2 + ... + a 2 n x n = b2
min z = c x
. . . .
peut aussi s’écrire

Sujet à Ax = b
x³0 . . . .
c, x Î R n , b Î R m a m1 x1 + a m 2 x 2 + ... + a mn x n = bm
A matrice m ´ n
x1 , x 2 , ..., x n ³ 0

77
Problème du restaurateur:
x y u p h min z = -8 x - 6 y
Sujaet à 5 x + 3 y + u = 30
æ5 3 1 0 0 ö
ç ÷ 2 x + 3 y + p = 24
A = ç 2 3 0 1 0÷
ç 1 3 0 0 1÷ 1x + 3 y + h = 18
è ø x, y , u , p , h ³ 0

c T = [ -8, -6, 0, 0, 0]
min z = c T x
Sujet à Ax = b
é30 ù x³0
b = êê 24 úú
êë18 úû c, x Î R 5 , b Î R 3
A matrice 3 ´ 5

78
Méthode du simplexe – notation matricielle
min z

Sujet à

a11 x1 + a12 x 2 + ... + a1n x n = b1

a 21 x1 + a 22 x 2 + ... + a 2 n x n = b2
min z
Sujet à Ax =b
. . . .
. . . .
cT x - z = 0
a m1 x1 + a m 2 x 2 + ... + a mn x n = bm
x³0
c, x Î R n , b Î R m c1 x1 + c 2 x 2 + ... + c n x n - z = 0
A matrice m ´ n x1 , x 2 , ..., x n ³ 0

79
Méthode du simplexe – notation matricielle

• Considérons le problème de programmation linéaire sous sa forme

matricielle
min z
Sujet à Ax =b
cT x - z = 0
x³0

• Supposons que m ≤ n et que la matrice A est de plein rang (i.e., rang(A) = m,

ou que les lignes de A sont linéairement indépendantes )
• Une sous matrice B de A est une base de A si elle est mxm et non singulière
(i.e, B-1 existe)

80
Méthode du simplexe – notation matricielle

• Une sous matrice B de A est une base de A si elle est mxm et non singulière
(i.e, B-1 existe)
• Pour faciliter la présentation, supposons que la base B que nous considérons
est composée des m premières colonnes de A, et ainsi

A = [B ! R ]
Dénotons également

éxB ù éc B ù
x=ê ú c=ê ú
ëxR û ëc R û

• Le problème original peut s’écrire

81
 min z
min z
é xB ù
Sujet à Ax =b Sujet à [ B! R] ê x ú = b
ë Rû
cT x - z = 0
é xB ù
x³0 é cB ! cR ù ê ú - z = 0
T T
ë û x
ë Rû
x³0

82
 min z
min z é xB ù
Sujet à BxB + RxR =b
Sujet à [ B! R] ê x ú = b
ë Rû
cBT xB + cRT xR - z = 0 é xB ù
é cB ! cR ù ê ú - z = 0
T T
xB , xR ³ 0 ë û x
ë Rû
x³0

83
• Exprimons xB en fonction de xR en utilisant les contraintes du problème
Bx B + Rx R = b

B -1 ( Bx B + Rx R ) = B -1b

B -1 Bx B + B -1 Rx R = B -1b
Ix B + B -1 Rx R = B -1b

• Ainsi
Ix B = - B -1 Rx R + B -1b

84
 En remplaçant xB par sa valeur
min z en fonction de xR dans l’équation
de la fonction économique
Sujet à BxB + RxR =b Notons que ces deux problèmes sont
cBT xB + cRT xR - z = 0 équivalents car le deuxième est obtenu
du premier à l’aide d’opérations
xB , xR ³ 0 élémentaires utilisant une matrice
non singulière B-1
min z
Sujet à IxB + B -1RxR = B -1b
cBT (- B -1RxR + B -1b) + cRT xR - z = 0
xB , xR ³ 0
85
 min z
Sujet à IxB + B -1RxR = B -1b
cBT (- B -1RxR + B -1b) + cRT xR - z = 0
xB , xR ³ 0

min z
En regroupant les coefficients de xR
Sujet à IxB + B -1RxR = B -1b
0 xB + (cRT - cBT B -1R ) xR - z = -cBT B -1b
xB , xR ³ 0
86
 min z
Sujet à Ix B + B -1 Rx R = B -1b
0 x B + (c TR - c TB B -1 R) x R - z = -c TB B -1b
xB , xR ³ 0

Le problème se traduit dans le tableau suivant

87
-

88
Les variables de xB (dénotées Les variables de xR (dénotées
jusqu’ici variables dépendantes) jusqu’ici variables
qui sont associées aux colonnes indépendantes) sont dénotées
de la base B, sont dénotées variables hors base
variables de base

89
Pour obtenir la solution de base associée à la base B,
posons xR = 0
et alors xB = B-1b.
La solution de base est réalisable si xB ≥ 0

90
Puisque tout tableau du simplexe est associé à une base de A constituée
des colonnes associées aux variables de base (variables dépendantes),
il s’ensuit que dans l’algorithme du simplexe, nous passons d’une
solution de base réalisable à une nouvelle solution de base réalisable
ayant une valeur plus petite ou égale.

91
Notion de multiplicateurs du simplexe

• Considérons la dernière ligne du tableau du simplexe associé à la base B qui correspond aux
vecteurs des coûts relatifs des variables:

cBT cRT

cBT = 0 = cBT - cBT = cBT - cBT B -1 B

cRT = cRT - cBT B -1 R

c = éë cB , cR
T T T
ùû = éë cBT , cRT ùû - cBT B -1 [ B ! R ] = c T - cBT B -1 A 92
Notion de multiplicateurs du simplexe

c T = c T - cBT B -1 A

Dénotons le vecteur défini ppar

Î Rm
p T = cBT B -1 π est le vecteur des multiplicateurs
Alors du simplexe associé à la base B.
c T = cT - p T A
Ou
[c1," , cn ] = [c1," , cn ] - p T [ a!1," , a!n ]
c j = c j - p T a• j

où
a • j colonne de la matrice de
dénote la jième
contrainte A

93
Notion de multiplicateurs du simplexe

c j = c j - p T a• j

• Le vecteur des multiplicateurs du simplexe π permet de calculer

les coûts relatifs
c j directement à partir des données originales du
problème.

• Les composantes πi (i=1,2,…,m) du vecteur des multiplicateurs peuvent être

considérés comme des poids associés aux lignes i du tableau (ou aux
contraintes i du problème) tel que la soustraction d’une combinaison linéaire
des lignes avec ces poids de la dernière ligne du tableau permet d’annuler les
coûts relatifs des variables de base.

94
Sensitivité de la valeur optimale aux
modifications des termes de droite

• Les multiplicateurs du simplexe associés à une base optimale permettent de mesurer l’effet de
modifier les termes de droite sur la valeur optimale d’un problème.
• Considérons le problème original et un autre où les termes de droite sont modifiés

min z min z!
Sujet à Ax = b Sujet à Ax! = b + Db
cT x - z = 0 c T x! - z! = 0
x³0 x! ³ 0

95
Sensitivité de la valeur optimale aux
modifications des termes de droite
min z min z!
Sujet à Ax = b Sujet à Ax! = b + Db
cT x - z = 0 c T x! - z! = 0
x³0 x! ³ 0

• Dénotons par B* une base optimale du problème original, et la solution de base optimale
correspondante x*R = 0
x* * = B*-1b = b ³ 0
B

*-1
dont la valeur (optimale pourz *le=problème)
c T* x* * + cest
T *
x
R R = c T
donnée* B
par b = c T
*b
B B B B

96
Sensitivité de la valeur optimale aux
modifications des termes de droite
min z min z!
Sujet à Ax = b Sujet à Ax! = b + Db
cT x - z = 0 c T x! - z! = 0
x³0 x! ³ 0

Db
• Choisissons la valeur de de telle sorte que
B *-1 (b + Db) = B *-1b + B *-1 Db ³ 0

• Donc B* demeure une base réalisable pour le nouveau problème modifié

puisque la solution de base associée est
~
x R* = 0
~
x B** = B *-1 (b + Db) ³ 0
97
Sensitivité de la valeur optimale aux
modifications des termes de droite

• Donc B* demeure une base réalisable pour le nouveau problème modifié puisque la solution de
base associée est
~* c *T = c T - p *T A
xR = 0
~
x B** = B *-1 (b + Db) ³ 0 p *T = c T* B*-1
B

c j coûts c ni la matrice A n’ont été modifiés, alors le vecteur des

• De plus, puisque ni les j
multiplicateur π* reste inchangé. Par conséquent les coûts
relatifs demeurent inchangés et donc non négatifs pour le nouveau problème.

Donc B* demeure donc une base optimale pour le nouveau problème.

98
 cj

Sensitivité de la valeur optimale aux

modifications des termes de droite

• Une solution optimale pour le nouveau problème est donc:

~
x R* = 0
~
x * = B *-1 (b + Db) ³ 0
B*

p *T = c T* B*-1
B
• Évaluons la valeur optimale du nouveau problème:
z!* = c T* x! * * + cRT x! *R z * = c T* B*-1b
B B B
*-1
=c B T
(b + Db)
B*
= c T* B*-1b + c T* B*-1Db
B B
= z + p Db
* *T

m
= z* + åi =1
p i* Dbi

99
Sensitivité de la valeur optimale aux
modifications des termes de droite
• Évaluons la valeur optimale du nouveau problème:.

z!* = c T* x! * * + cRT x! *R
B B
=c B T *-1
(b + Db) Ainsi, p i* indique la taux de variation
B* unitaire de la valeur optimale de la
= c T* B*-1b + c T* B*-1Db fonction économique lorsque le terme
B B
= z + p *T Db
* de droite bi de la contrainte i est modifié
m d’une quantité Dbi choisie de telle
= z* + åi =1
p i* Dbi sorte que la base demeure réalisable
pour le nouveau problème.

100
Problème du restaurateur transformé en min

• Transformons les contraintes d’inégalité du problème du restaurateur en

égalité avec les variables d’écart u, p et h:

min z = –8x – 6y min z = –8x – 6y

Sujet à Sujet à
5x + 3y ≤ 30 5x + 3y + u =30
2x + 3y ≤ 24 2x + 3y + p =24
1x + 3y ≤ 18 1x + 3y + h = 18
x, y ≥ 0 x, y, u, p, h ≥ 0

101
 x y u p h -z
p *T = c T* B*-1
1 1
B

x 1 0 0 - 0 3
4 4 é 1
0 -
1 ù
ê 4 4 ú
1 3 ê 1 ú é 3
p 0 0 - 1 - 0 3 p *T = [ -8 0 - 6] ê - 1 -
3
ú = ê - 0 - ùú
1
4 4 ê 4 4 ú ë 2 2û
1 5 ê 1 5 ú
y 0 1 - 0 0 3 ê - 12 0
12 ú
ë û
12 12
3 1
-z 0 0 0 1 54
2 2

z!* = z * + p *T Db
é Db ù
é 3 1ùê 1 ú 3 1
= -54 + ê - 0 - ú Db2 = -54 - Db1 + 0Db2 - Db3
ë 2 2 û ê Db ú 2 2
ë 3û

3
Db1 < 0 Þ - Db1 > 0 Þ z!* > z *
2

102