i

UNIVERSITE CHEIKH ANTA DIOP DE DAKAR

Faculté des Sciences Economiques et de Gestion (FASEG)
Notes de cours sur la
PROGRAMMATION LINEAIRE et JEUX A DEUX PERSONNES et A SOMME
NULLE
Année 2011-2012
Diaraf SECK 1

1. Version 01 : Ces notes de cours pour la quatrième année, sont conçues à partir de références
données dans la présentation du programme cf fichier nommé Programme R.O..
C’est un document en amélioration avec des compléments et ajouts d’autres chapitres. Les chapitres
sur la dualité et analyse de la sensibilité sont en cours de réalisation avec le LaTex. Le chapitre sur la
théorie des jeux est incomplet ( cf le cours dispensé pour les parties manquantes). Nous nous excusons
des coquilles qui n’ont pas pu être enlevées dans cette version.
 TABLE DES MATIÈRES

Table des matières ii

Liste des tableaux iii

Table des figures iv

Liste des notations 1

1 Programmation Linéaire 1
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Introduction à l’algorithme du simplexe . . . . . . . . . . . . . . . . . . 9

2 Dualité en Programmation linéaire 17

3 Programmation linéaire paramétrique : Analyse de la sensibilité 18

4 Jeux à deux personnes et à somme nulle 19

4.1 Généralité sur la théorie du jeux . . . . . . . . . . . . . . . . . . . . . . . 19
4.2 Généralisation en stratégie pures . . . . . . . . . . . . . . . . . . . . . . 28
4.3 Jeux à informations Incompletes . . . . . . . . . . . . . . . . . . . . . . . 29

ii
L ISTE DES TABLEAUX

iii
TABLE DES FIGURES

iv
 HAPITRE
1

C
P ROGRAMMATION L INÉAIRE

1.1 Introduction

Soit un phénomène é économique y, résultat de plusieurs effets élémentaires :

e1 , e2 , · · · , e n .
Si l’on suppose que les effets élémentaires considérés sont additifs, on a :

y = e1 + e2 + · · · + e n

Si l’on suppose, en outre, que chacun des effets élémentaires en est proportionnel à
sa cause xi , on peut écrire :

y = a1 x1 + a2 x2 + · · · + a n x n (1.1)

a1 , a2 , · · · , an étant les coefficients de proportionnalité.

L’égalité est du premier degré par rapport au variables : on dit encore qu’elle est une
fonction linéaire de ces variables.
Il arrive que dans beaucoup de problème, les mêmes effets soient tous proportionnels
aux causes ( au moins de facon suffisament approchée) ; le problème peut alors se

1
Chapitre 1. Programmation Linéaire 2

décrire uniquement au moyen de formes linéaires :

y1 = a11 x1 + a12 x2 + · · · + a1n xn

ym = am1 x1 + am2 x2 + · · · + amn xn
.. .. ..
. . ··· .
y m +1 = a ( m +1)1 x 1 + a ( m +1)2 x 2 + · · · + a ( m +1) n x n

Si on suppose que :
y1 ≤ b1 , y2 ≤ b2 , · · · , yn ≤ bn

i.e en écrivant en contrainte, on permet l’optimisation du (m + 1)eme effet : max ym+1 ,

ym+1 est la fonction économique du problème.
On peut aussi s’interesser au problème de minimum du (m + 1)me effet : min ym+1

Remarque 1 : max( f ) = −min(− f )

1.1.1 Présentation Théorique

Un programme linéaire (P.L) est un problème du type :

n
max z = ∑ cj xj
j

sous les contraintes 

 ∑n a x ≤ b i = 1, · · · , m
j ij j i
 x ≥0 j = 1, · · · , n
j

où les coefficients et variables c j , aij , bi , et xi appartiennent à l’ensemble R des nombres

réels.

Exemple 1 max(z = x1 + 3x2 )




 x1 + x2 ≤ 14


 −2x + 3x ≤ 12

1 2


 2x1 − x2 ≤ 12


 x ,x ≥ 0

1 2
Chapitre 1. Programmation Linéaire 3

Exemple 2 min(z = x2 − x1 )



 2x1 − x2 ≥ −2


 x −x ≤2

1 2


 x1 + x2 ≤ 5


 x ,x ≥ 0

1 2

Exemple de problème non linéaire :

Un consommateur dispose de trois biens X1 , X2 , X3 , dont les prix unitaires respec-

tifs sont 100F, 400F, 250F. La consommation du triplet de biens ( x1 , x2 , x3 ) est traduite
par une fonction d’utilité définie par :
1
z = z( x1 , x2 , x3 ) = x12 ( x2 + 4) x3

où xi > 0, avec xi quantité consommée du bien Xi , i = 1, 2, 3. On suppose que le

revenu du consommateur est égal à 36000F.
L’objectif du consommateur est de maximiser sa satisfaction compte tenu de son re-
venu.
Donc le modèle mathématique est
1



 max[ x12 ( x2 + 4) x3 ]

100x1 + 400x2 + 250x3 ≤ 35000



 x > 0, x > 0, x > 0
1 2 2

est un programme non linéaire.

1.1.2 Resolution Graphique

Théorème 1 : L’ensemble des solutions réalisable d’un programme linéaire détermine dans
l’espace de décision 1 un ensemble convexe (appelé domaine réalisable) qui est :
– Soit l’ensemble vide
– Soi un ensemble polyédrique convexe non borné
1. espace des variables structurelles (les x j sont les variables structurelles)
Chapitre 1. Programmation Linéaire 4

– Soit un polyèdre convexe

Théorème 2 S’il existe au moins une solution optimale (finie), il existe au moins une solu-
tion optimale, qui est un sommet du domaine réalisable.
Dans le cas où il n’ya que deux (ou trois) variables, il est possible de représenter graphique-
ment l’ensemble des solutions réalisables et d’enduire la (les) solution(s) (s’il existe au moins
une), compte tenue des théorème rappelés ci-dessus.

Exemple 3 max(z = 5x1 + 7x2 )




 x1 + x2 ≥ 6


 x ≥4

1


 x2 ≤ 3


 x ,x ≥ 0

1 2

L’espace de décision est le plan ( x1 , x2 ). La solution optimale est donc F = (6, 8), z vaut
30

Exemple 4 min(z = x2 − x1 )



 2x1 − x2 ≥ −2


 x − 2x ≤ −8

1 2


 x1 + x2 ≤ 5


x1 , x2 ≥ 0


Chapitre 1. Programmation Linéaire 5

2x1 − x2 = − 2

C
x1 − x2 = − 2 x1 − x2 = 5

D B

Les solutions optimales sont donc :

7 3
– les deux sommets A(2, 0) ey B( , )
2 2
– les points réalisables qui s’en déduisent par combinaison linéaire convexe i.e le
segment [ A, B].

Exemple 5 max(z = 5x1 + 7x2 )




 x1 + x2 ≥ 6


 x ≥4

1


 x2 ≤ 3


 x ,x ≥ 0

1 2

Le maximum est infini !

En effet :
L’ensemble des solutions réalisables est un ensemble polyédrique convexe non borné. Prenons
un point sur la droite x2 = 3 qui s’éloigne indéfiniment alors z la fonction économique prend
des valeurs très grandes.
La valeur maximale de z est donc infinie.

max z = +∞
Chapitre 1. Programmation Linéaire 6

et elle est « atteinte »au point ( x1 = ∞, x2 ≤ 3)

Exemple 6 min(z = x1 + 3x2 )




 x1 + x2 ≤ 14


 −2x + 3x ≤ 12

1 2


 2x1 − x2 ≤ 12


x1 , x2 ≥ 0



Il est laissé en exercice

Exemple 7 min(z = x2 − x1 )



 2x1 − x2 ≥ −2


 x −x ≤2

1 2


 x1 + x2 ≤ 5


 x ,x ≥ 0

1 2

Il est laissé en exercice

Exemple 8 min(z = x2 − x1 )



 2x1 − x2 ≥ 14


 x − 2x ≤ −8

1 2

 x1 + x2 ≤ 5




 x ,x ≥ 0

1 2

S=∅

Exemple 9 Une entreprise a la faculté de fabriquer sur une machine donnée, travaillant 45
heures par semaines, trois produits différents P1 , P2 , P3 . L’article P1 laisse un profit net de
400F, l’article P2 de 12F et, enfin, l’article P3 de 3F. Les rendements de la machine sont
respectivement pour les trois produits, et dans le même ordre : 50, 25 et 75 articles par heures.
On sait, d’autre part, grâce à une étude de marché, que les possibilités de vente ne dépassent
pas : 1000 objets P1, 500 objets P2 et 1500 objets P3, par semaine. On se pose le problème de
repartir la capacité de production entre les 3 produits, de manière à maximiser le profit.
Chapitre 1. Programmation Linéaire 7

Remarque 2 Un raisonnement purement économique suffit à résoudre la question.

En effet on cherche les rendements horaires exprimés en unités monétaires.
P1 → 4 = 200F
P2 → 12 = 300F
P1 → 3 = 225F
Si l’on veut maximiser le profit, on fabrique :
– La plus grande quantité possible de P2
– Ensuite les objets P3 dont le rendement monétaire vient en second
– Si l’on n’a pas épuisé le temps de production, produire les articles P1
Il n’est pas difficle de voir que la solution consiste à fabriquer tous les objets P2, ce qui occupe
la machine pendant 20h, puis tous les objets P3 −→ 20h, finalement, il ne reste que 5h pour
fabriquer les objets P1, ce qui correspond à une quantité de 5 × 50 = 250 articles P1.
Résultat :
articles P1 : 250, P2 : 500, P3 : 1500.
Profit total : 250 + 500 + 1500 = 11500

Formes Algébriques

x1 quantité de l’objet P1
x2 quantité de l’objet P2
x3 quantité de l’objet P3
que nous à fabriquer pour obtenir un profit maximal. Les quantités des articles P1, P2, P3
ne doivent pas depasser respectivement : 1000, 500, 1500 par semaine, on a donc :

1. x1 ≤ 1000

2. x2 ≤ 500

3. x3 ≤ 1500

50 objets de P1 −→ 1h
x1
x1 objets de P1 −→ h
50
x2
x2 objets de P2 −→ h
25
Chapitre 1. Programmation Linéaire 8

x3
x3 objets de P3 −→ h
75
Or la somme des temps de fabrications ne dépasse 45h, disponibilité totale de la ma-
[Link] aura donc
x1 x x
+ 2 + 3 ≤ 45
50 25 75
Soit
3x1 + 6x2 + 2x3 ≤ 6750 (1.2)

1), 2), 3) et 4) sont les contraintes exprimées par l’énoncé. Il y’a 3 contraintes cachées :
x1 , x2 , x3 ont un sens physique précis : ce sont des nombres d’objets dont la fabrication
est envisagée ; donc
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0

Objet du problème : choisir x1 , x2 , x3 tels que le profit soit maximal. Le profit n’est
autre que :
4x1 + 12x2 + 3x3

d’où PB : maxz = 4x1 + 12x2 + 3x3 , avec z =fonction économique.

Signification géométrique

Comme on a 3 variables, la solution du problème est donné par un point de l’es-

pace de coordonnées x1 , x2 etx3 déterminées.
3x1 + 5x2 + 2x3 = 6750 est l’espace du plan P4, de l’espace à 3 dimension et la
contrainte 4) signifie que les points solutions doivent necessairement se trouver à l’in-
térieur ou à la surface ou à la surface du tétraède OA0 B0 C 0 formé par les plans de co-
ordonnées et le plan P4 ; le plan P4 coupe Ox1 en A0 (2250, 0, 0), Ox2 en B0 (0, 1125, 0),
Ox3 en C 0 (0, 0, 3375).

Difficultés de généralisation

En dimension 3 déja il nous des éléments de géométrie descriptive pour pouvoir

trouver maxz = 11500.
Chapitre 1. Programmation Linéaire 9

Quand le nombre de variables est supérieur à 3, la résolution graphique est impos-

sible car on ne peut faire de graphes dans une dimension n avec n > 3. D’autres part,
le raisonnement économique échoue lorsque le nombre de contraintes augmente.

1.2 Introduction à l’algorithme du simplexe

Revenons à notre problème de maximisation de l’exercice 5, les contraintes




 x1 ≤ 1000


 x ≤ 500

2


 x3 ≤ 1500


 3x + 5x + 2x ≤ 6750

1 2 3

peuvent être écrites sous forme .... en introduisant des variables appelées variables
d’écart. 


 x1 + x4 = 1000


 x + x = 500

2 5


 x3 + x6 = 1500


 3x + 2x + 2x + x = 6750

1 2 3 7

Ces variables d’écart ont ici un sens physique : ce sont respectivement les différences
entre les quantités limités et les quantités fabriquées des produits P1, P2, P3 en ce qui
1
concerne x4 , x5 , x6 , le temps inutilisé (en ) à la fabrication, pour ce qui est x7 .
150

=⇒ x4 ≥ 0, x5 ≥ 0, x6 ≥ 0 et x7 ≥ 0

(I) admet une solution évidente : x4 = 1000, x5 = 500, x6 = 1500, x7 = 6750, qui
consiste à ne rien fabriquer i.e x1 = x2 = x3 = 0.
Dans ce cas le profit z = 4x1 + 12x2 + 3x3 est évidemment nul. Le point représentatif
de cette solution dans à trois dimension est O = (0, 0, 0)
Chapitre 1. Programmation Linéaire 10

 
x
 1
   x2 

  
1 0 0 1 0 0 0  
  1000
  x   
  3 
0 1 0 0 1 0 0    500 
 
( I ) ⇐⇒   x  = 
  4 

0 0 0 0 0 1 0   1500
 
  x   
5
3 6 2 0 0 0 1   6750
 x6 
 
x7

(~e1 , ~e2 , ~e3 , ~e4 ) forme une base orthonormée d’un espace vectoriel de dimension 4, R4
(~
e1 est unitaire).

Remarque 3 Il y’a autant de vecteurs unitaires que de contraintes d’inégalités.

Si x1 = x3 = 0 et x2 = 500 alors C = (0, 500, 0) est un point adjacent à 0 sur le

polyèdre.
( β) =⇒ x5 = 0



 x4 = 1000 − x1


x = 500 − x5


 2


donc (I) ⇐⇒ x6 = 1500 − x3


x7 = 6750 − 3x1 − 5(500 − x5 ) − 2x3






 = 3750 − 3x − 2x + 6x

1 3 5
 
x
 1
   x2 

  
1 0 0 1 0 0 0     1000
  x   
  3 
0 1 0 0 1 0 0    500 
 
⇐⇒   x  = 
  4 

0 0 1 0 0 1 0   1500
 
  x   
5
3 0 2 0 −6 0 1    3750
 x6 
 
x7
=⇒ x4 , x2 , x6 , x7 sont les nouvelles variables de base donc entrée de x2 et sortie de
x5 . Le passage d’un sommet d’un polyèdre à un sommer adjacent dans l’espace à
Chapitre 1. Programmation Linéaire 11

N dimensions (autant que de variables principales), se traduit par l’échange d’un

vecteur à m dimension (autant que de contraintes) ; nous saurons donc faire cette
opération qui est classique.
La fonction économique devient :

au départ z = 4x1 + 12x2 + 3x3 = 0

si x2 = 500 − x5 alors z = 4x1 + 12(500 − x5 ) + 3x3

⇐⇒ z = 4x1 + 3x3 + 12x5 + 6000

Observation

On remarque que les coefficients de la fonction économique représentent à chaque

pas ce que rapporterait (en unités monétaires) l’augmentation d’une unité de la va-
leur des variables figurant dans la fonction économique, au pas considéré. Au départ
l’expression (a) signifie que l’augmentation de la variable x1 ( qui vaut alors λ) de
1 unité ferait gagner 4 unités monétaires ; l’augmentation de la variable x2 (qui vaut
alors 0) de 1 unité ferait gagner 12 u.m ; l’augmentation de la variable x (qui vaut 0)
de 1 unité ferait gagner 3 u.m. L’expression de (b) signifie qu’après avoir x2 = 500,
l’augmentation de x1 de 1 unité continerait à faire gagner 4 u.m et celle de x3 de 1
unité, 3 u.m, mais que l’augmentation de x5 de 1 unité ferait perdre de 12 u.m (ga-
gner 12).
Autrement dit, les coefficients de la fonction économique, qui subissent les mêmes
transformation que les vecteurs colonnes de la matrice auxquels ils appartiennent,
sont aux sens économique, les coûts marginaux (ou profits marginaux attachés aux
variables figurant dans la fonction économique).

1.2.1 Idée et Ligne de conduite de l’algorithme du simplexe

L’algorithme du simplexe consiste à progresser d’une sommet initial vers un som-

met adjacent en ayant de ne pas diminuer la valeur de la fonction économique.
Chapitre 1. Programmation Linéaire 12

En plus les variables principales et les variables d’écart doivent toujours être posi-
tives ou nulles.
Questions : Comment on fait pour progresser ? Comment choisir les vecteurs qui
entrent dans la bases et ceux qui en sortent ?

Méthodes

A j : sont les vecteurs colonnes.

Inscrivons maintenant face à la valeur qu’elle a dans la solution initiale, l’indice i de
la variable xi (i.e ici du départ x4 = 1000, x5 = 500, x6 = 1500, x7 = 6750), les indices
i sont donc : (4, 5, 6 et 7).
On notera xij : l’élément situé à l’intersection d’une ligne i et d’une colonne j.
Les éléments de la colonne A0 situé sur la ligne i sera simplement désigné par xi .
Les éléments de la fonction économiquee sont traités des nombres inscrits dans les
colonnes A j correspondantes. Ces éléments seront appelés ∆ j .

Exemple 10 ∆1 = 4 ∆7 = 0

Initialement z = 0 car ( x1 = x2 = x3 = 0).

Les formules du changemebnt de coordonnées, réalisé par la sortie d’un vecteur aide
la base et l’entrée d’un A j , sont :

nouvelle valeur de la fonction économique

xi
z0 = z + ∆, z étant l’ancienne valeur
xij j

nouvelle valeur de l’élément de la ligne k dans la colonne A0

xi
xk0 = xk − xkj , xk étant l’ancienne valeur
xij
Chapitre 1. Programmation Linéaire 13

nouvelle valeur de l’élément de la ligne de la colonne Al

0 xil
xkl = xkl − xkj , (k 6= i ) xkl étant l’ancienne valeur
xij

nouvelle valeur de l’élément de la ligne i de la colonne Ak

xil
xil0 = , (k = i ) xil étant l’ancienne valeur
xij
Dans ces conditions comme à chaque pas, on que z0 ≥ z, il faudra prendre ∆ j positif
( xxi sera positif, car xi > 0 comme élément du second membre et xij sera pris positif).
ij

En principe on gagnera à prendre ∆ j > 0 aussi élévés que possible.

1.2.2 Premier critère de Dantzig

Pour déterminer la colonne A j qui doit entrer dans la base, on choisit celle qui
∂z
compose le ∆ j positif le plus grand i.e l’expression marginale la plus élevée max
j ∂xij

Exemple 11
z = 4x1 + 12x2 + 3x3
∂z ∂z ∂z
=4 = 12 =3
∂x1 ∂x2 ∂x3
=⇒ A2 qui entre das la base

On veut que : ∀k, xk0 ≥ 0

x
i.e xk − xkj i ≥ 0
xij
x
i.e xk ≥ xkj i
xij
x
Si l’on prend i ≥ 0, comme xk ≥ 0 alors :
xij
xi
xk ≥ xkj si xkj ≤ 0
xij
xi
=⇒ xk0 = xk − xkj ≥0
xij
Chapitre 1. Programmation Linéaire 14

xi x
xkj ≥ 0 =⇒ ≤ i
xij xkj
xi
Donc xk0 ≥ 0 si on prend, parmi les quotients obtenus pour toutes les valeurs i, le
xij
plus petit positif d’entre eux.

1.2.3 Deuxième critère de Dantzig

Pour determiner la colonne Ai qui doit sortir de la base, on choisit celle d’indice
x
i, tel que i soit le plus petit positif ( l’indice j ayant été déterminer par l’application
xij
du premier critère). L’optimum sera atteint dès que le premier critère ne sera plus
applicable i.e lorsque tous les ∆ j relatifs aux variables hors base seront négatifs, ceux
relatifs aux variables de base étant nuls.

Exemple 12 Comme j = 2, i ∈ (4, 5, 6, 7)

x4 1000 x 500 x 1500 x 6750
= = ∞; 5 = = 500 ; 6 = = ∞; 7 = = 1125
x42 0+ x52 1 x62 0+ x72 6
xi
le plus petit est réalisé pour i = 5 donc A5 sort de la base remplacéée par A2 .
xi2
Appliquond le changement de coordonnées :

x5 x5
z = z+ ∆2 xk0 = xk − xkl
x52 x52

0 x5l
xkl = xkl − xk2 ( k 6 = 5)
x52
0 x5 x5
x5l = ∆2 etx50 =
x52 x52
xij (ici x52 ) qui joue un rôle fondamental est appelé élément distingué ou pivot de la
transformation.

1.2.4 Règle pratique de transformation du tableau

Outil : méthode du pivot

Chapitre 1. Programmation Linéaire 15

i A1 A2 A3 A4 A5 A6 A7 A0
4 1 0 0 1 0 0 0 1000 L1
5 0 1 0 0 1 0 0 500 L2
6 0 0 1 0 0 1 0 1500 L3
7 3 6 2 0 0 0 1 3750 L40
z 4 12 3 0 0 0 0 0 L5
4 1 0 0 1 0 0 0 1000 L1
2 0 1 0 0 1 0 0 500 L2
6 0 0 1 0 0 1 0 1500 L3
7 3 0 2 0 -6 0 1 3750 L40 = L4 − 6L2
z 4 0 3 0 -12 0 0 -6000 L50 = L5 − 12L2
1 1 0 0 1 0 0 0 1000 L1
2 0 1 0 0 1 0 0 500 L2
6 0 0 1 0 0 1 0 1500 L3
7 0 0 2 -3 -6 0 1 750 L4 ” = L4 − 3L1
7 0 0 1 - 32 -3 0 1 375 L4 ”
z 0 0 3 -4 -12 0 0 -10000 L5 ” = L50 − 4L1
1 1 0 0 1 0 0 0 1000 L1
2 0 1 0 0 1 0 0 500 L2
6 0 0 0 3
2 3 1 - 21 1125 L30 = L3 − L4 ”
3 0 0 1 - 32 -3 0 1
2 375 L4 ”
000
z 4 12 3 0 0 0 0 -11125 L5 = L5 ” − 3L4 ”
1 1 0 0 0 -2 - 23 1
3 250 L10 = − L3 ” + L1
2 0 1 0 0 1 0 0 500 L2
4 0 0 0 1 2 2
3 - 31 750 L3 ” = 23 L30
000
3 0 0 1 0 0 1 0 1500 L4 = L4 ” + 23 L3 ”
z 0 0 0 0 -4 - 13 − 34 -11500 L5IV = L5 ” −
3L4 ”
Chapitre 1. Programmation Linéaire 16

Arrêt de l’algorithme.
maxz = 11500

pour x1 = 250 x2 = 500 x3 = 1500

Exemple 13 Une entreprise fabrique deux biens B1 et B2 en utilisant trois facteurs de pro-
duction : du travail T (dont l’unité de mesure est l’heure), une machine M (dont l’utilisation
est mesurée en heures et une matière première, P, (en tonnes). La quantités de ces ressources
nécessaires à la fabrication d’un unité de Bi (i = 1, 2) sont données par le tableau suivant
 HAPITRE
2

C
D UALITÉ EN P ROGRAMMATION
LINÉAIRE

A VENIR ! Désolé cf cours dispensé en amphi

17
 HAPITRE
3

C
P ROGRAMMATION LINÉAIRE
PARAMÉTRIQUE : A NALYSE DE LA
SENSIBILITÉ

A VENIR ! Désolé cf cours dispensé en amphi

18
 HAPITRE
4

C
J EUX À DEUX PERSONNES ET À SOMME
NULLE

4.1 Généralité sur la théorie du jeux

But : Etude des situations de conflit

Les intérêts des adversaires ne coincident pas et parfois même sont opposés.
Chaque participant peut exercer une certaine influence sur le déroulement des évè-
nements mais n’est pas capable de s’en rendre complètement maître.

Exemple 14 Situation de conflit :

– jeux de sociétés et de sport : échec, damier, domino, yooké, wure, etc
– compétition économique

Définition 1 Les jeux sont conduits selon des règles déterminées. A l’issue d’un jeu, chaque
participant obtient un gain ou une perte.
une perte = gain exprimé en valeurs négatives.
Nous considérons dans ce chapitre les jeux à deux personnes.

19
Chapitre 4. Jeux à deux personnes et à somme nulle 20

Définition 2 Un jeu est dit à somme nulle si les les intérêts des joueurs sont directement
opposés (le gain d’un des joueurs est égal à la perte de l’autre).

Certains jeux sont liés au hasard (coup au but, donne des cartes). Pour formaliser les
modèles de tels jeux, on introduit en plus des coups personnes, des coups aléatoire.
Dans ce cas ona que des coups aléatoire, on attribue une distribution de probabilité
des résultats possibles.
L’un des facteurs décisifs qui determinent le comportement des joueurs est l’informa-
tion dont disposent l’une et l’autre partie sur sa position et celle de l’adversaire ainsi
que sur le comportement passé des participants.
Il ya :
– Des jeux à information complète, ex : jeux de wuré, yooké
– Des jeux à information complète, ex : certaines compétition économique entre
deux entreprises, jeux de cartes (dominos)

Remarque 4 On peut représenter graphiquement les règles du jeu, la succession des coups
personnels et aléatoire et les résultats sous la forme de ce que l’on appelle une arborescence :
ceci s’appelle la forme developpée du jeu.
Mais l’abondance des classes de jeux développés rend très difficile l’édification d’un théorie
unique d’exploration et de résolution des jeux

Définition 3 On appelle stratégie d’un jeu un système de règle qui déterminent de façon
univoque le comportement d’un joueur à chaque coup en fonction de la situation définie par
la marche du jeu.

Remarque 5 La notion de stratégie permet de ... les jeux les plus développés à une forme type
unique, dit forme normal du jeu.
Un joueur ayant choisi une stratégie peut ne pas participer au jeu. Une personne neutre peut
conduire le jeu suivant les instruction qu’il a données.

Définition 4 On appelle stratégie pure d’un joueur, chacune des stratégies déterminées que
peut choisir un joueur.
Chapitre 4. Jeux à deux personnes et à somme nulle 21

Définition 5 Lorsque le jeu est à deux personnes, sa forme normale est dite rectangulaire.
Un jeu rectangulaire, à nombre fini de stratégies pures est dit matriciel.

Dans ce qui suit nous ne considérons que les jeux matriciels à somme nulle.
Soit A un joueur disposant de m stratégies 1er joueur.
Soit B un joueur disposant de n stratégies 2eme joueur.
On admet de plus que si A choisit le ieme stratégie et B la jeme , le gain de A (et donc la
perte de B) est aij .
M = ( aij ) est appelé la matrice de paiement ou matrice de gain.
1≤i≤m
1≤j≤n

Remarque 6 Lors de la formalisation de la concurrence (conflit) réelle, la composition d’une

matrice de paiement est une tâche complexe.
Les principes qui définissent l’établissement d’une matrice de paiement se situent d’une façon
générale en dehors de la théorie des jeux et relèvent de l’application concrète à laquelle est lié
l’énoncé du problème.

La tâche de la théorie des jeux consiste à élaborer des principes qui déterminent le
comportement des joueurs dans chaque situation de conflit concrète.
Il y’a des jeux dans lesquels chacun des participants peut choisir une stratégie pure,
comportement lui assurant certain gain indépendamment de la conduite de l’adver-
saire et tel que les gains assurés des joueurs ne different que par le signe.
Si A choisit la stratégie i0 et B j0 , alors le gain de A est ai0 j0 et celui de B − ai0 j0 .
Si A choisit io et B refuse de choisir j0 , le gain de A ne peut qu’augmenter.
Donc quand B choisit j0 , il empêche A de gagner plus que ai0 j0 . Ainsi

aij0 ≤ ai0 j0 ≤ ai0 j i = 1, · · · , m; j = 1, cdots, n (4.1)

On dit que dans de tels jeux les stratégies pures sont optimales.

Définition 6 Un couple de nombre (i0 , j0 ) qui correspond à des stratégies optimales des
joueurs est appelé point-selle de la matrice de paiement et le nombre ai0 j0 la textbfvaleur
du jeu.
Chapitre 4. Jeux à deux personnes et à somme nulle 22

Remarque 7 La matrice (de paiement) ou de gains peut avoir plusieurs point-selles qui tous
déterminent une valeur unique du jeu.

Proposition 1 Un jeu a une solution en stratégie pure si l’on peut dégager dans la matrice
de paiement une élément ai0 j0 qui verifie la relation 4.1 ∀i, j

Remarque 8 Dans les jeux avec point selle, chaque joueur peut s’assurer dans chaque partie
indépendamment du comportement de l’adversaire, une situation dite d’équilibre i.e une si-
tuation qu’il est naturelle de considerer comme résultant d’un comportement intelligent des
adversaires.

Exemple 15 Soient deux personnes A et B préoccupées par un jeu dont la règle s’exprime
B
I II II
par le tableau ci-dessous : 1 1 0 -2
A 2 2 1 2
3 -1 -1 0

A chaque coup, chacun des joueurs doit choisir indépendamment de l’autre une des
stratégies pures à sa disposition.
A peut choisir de jouer les stratégies 1, 2 ou 3.
B peut choisir de jouer les stratégies I, II ou III.
1ier cas
Si A joue la ligne 1 :
A gagne un jeton si B joue dans la colonne I.
B ni gain ni perte si B joue II.
A perd 2 jetons si B joue III.
2e cas
A joue la ligne 2 :
A gagne 2 jetons si B joue I.
A gagne 1 jetons si B joue I I.
A gagne 2 jetons si B joue I I I.
Chapitre 4. Jeux à deux personnes et à somme nulle 23

3e cas
A joue la ligne 3 :
A gagne 1 jetons si B joue I.
A gagne 1 jetons si B joue I I.
A ni gain ni perte si B joue I I I.
La situation est évidemment tout l’inverse pour B.
1ier cas
Si B joue I :
B perd un jeton si A joue la ligne 1.
B perd 2 jetons si A joue la ligne 2.
B gagne 1 jeton si A joue la ligne 3
Et ainsi de suite.....
M1 est la matrice des gains de A (ou matrice des pertes de B). C’est un jeu à 2 per-
sonnes à somme nulle cas chaque adversaire gagne ce que l’autre perd.

4.1.1 Observations

A n’a pas intêret à jouer les lignes 1, ou 3 ; s’il pire la ligne 1, il ne peut esperer
gagner qu’un jeton mais risque d’en perdre 2, s’il joue la ligne 3, il ne peut esperer
aucun gain.
S’il joue la ligne 2, il est assuré de gagner au moins un jeton quelle que soit la décision
de B.
Dans ces conditions, B, se rendant compte que son adversaire doit nécessairement
jouer la stratégie 2, emploira de son côté, la stratégie II i.e limitera sa perte à un jeton
par coup.
La valeur du jeu (gain de A ou perte de B à chaque coup) est 1.

j = I, I I, I I I
a1I I ≤ 1 = a2I I ≤ a2j
i = 1, 2, 3
Chapitre 4. Jeux à deux personnes et à somme nulle 24

=⇒ 1 est le point selle la valeur du jeu.

Approfondissement de l’exemple : B
Soit

q1 q2 q3 q4
I II II IV
p1 a11 a12 a13 a14
A p2 a21 a22 a23 a24
p3 a31 a32 a33 a34

On suppose maintenant que dans M2 , a32 est un point selle (nous le supposerons
unique).
Imaginons que A et B ne se soient pas rendu compte que cet élément est point selle
i.e le plus petit sur la ligne et le plus grand dans la colonne.
A et B auront tendance à jouer :
– A : lignes 1, 2 et 3 avec des fréquences p1 , p2 , p3
– B : colonnes I, I I, I I I, IV avec des fréquences q1 , q2 , q3 , q4
de manière à obtenir le plus grand gain possible, et , le second, la plus petite perte.
Supposons que A cherche à determiner les fréquences p1 , p2 , p3 , p4 de ses choix, s’il
s’exprime ces fréquences en fraction de l’unité on a :

p1 + p2 + p3 = 1 p1 , p2 , p3 geq0

B joue I, la recette de A s’écrira :

a11 p1 + a21 p2 + a31 p3

B joue I I, elle deviendra :

a12 p1 + a22 p2 + a32 p3

B joue I I I, A obtiendra :
a13 p1 + a23 p2 + a33 p3

B joue IV, la recette de A s’écrira :

a14 p1 + a24 p2 + a34 p3

Chapitre 4. Jeux à deux personnes et à somme nulle 25

Il est probable que B jouera lui même les colonnes avec les fréquences q1 , q2 , q3 , et q4
telles que
q1 + q2 + q3 + q4 = 1

la recette de A se montera finalement à :

3 3 3 3
R A = q1 ∑ ai1 pi + q2 ∑ ai2 pi + q3 ∑ ai3 pi + q4 ∑ ai4 pi
i =1 i =1 i =1 i =1
Un raisonnement analogue nous donne que la perte de B peut s’écrire :
4 4 4
PB = p1 ∑ a1j q j + p2 ∑ a2j q j + p3 ∑ a3j p j
j =1 j =1 j =1

En developpant R A et R B on voit que R A = PB . A : joueur maximisant, désire évidem-

ment dépasser, si c’est possible ou au moins atteindre la valeur g du jeu (on suppose
qu’elle existe).
Donc son gain doit être le plus élevé possible, même dans le cas où le joueur se bor-
nerait à une stratégie pure ; d’où 4 cas selon type :

q1 = 1, q2 = q3 = q4 = 0

q1 = 1, q2 = 1, q3 = q4 = 0

ou
q1 = q2 = 0, q3 = 1q4 = 0

q1 = q2 = q3 = 0, q4 = 1

on a alors : 


 a11 p1 + a21 p2 + a31 p3 ≥ g


a p + a22 p2 + a32 p3 ≥ g


 12 1


(I) a13 p1 + a23 p2 + a33 p3 ≥ g


a14 p1 + a24 p2 + a34 p3 ≥ g







 p1 + p2 + p3 = 1
Dans le cas (q1 = q2 = q3 = q4 = 1)
Comme a32 est un point selle on a :

i = 1, 2, 3
a12 ≤ a32 ≤ a3j
j = 1, 2, 3, 4
Chapitre 4. Jeux à deux personnes et à somme nulle 26

=⇒ a31 = a32 + α31 a34 = a32 = a32 + α34

a33 = a32 + α33

a12 = a32 + α12 a22 == a32 + α22

avec
α31 , α32 , α33 , α34 , α12 , α22 > 0

donc I devient :



 a11 p1 + a21 p2 + ( a31 + α31 ) p3 ≥ g


( a − α12 ) p1 + ( a32 − α22 ) p2 + a32 p3 ≥ g


 32


(I0) a13 p1 + a23 p2 + ( a32 − α33 ) p3 ≥ g


a14 p1 + a24 p2 + ( a32 + α34 ) p3 ≥ g







 p1 + p2 + p3 = 1

La 2e inégalité ⇐⇒

a32 ( p1 + p2 + p3 ) − ( p1 α12 + p2 α22 ) ≥ g

⇐⇒ a32 − ( p1 α12 + p2 α22 ) ≥ g (4.2)

Comme α12 , α22 > 0 et p1 , p2 ≥ 0.

Le maximum de 4.2 est atteint si p1 = p2 = 0 i.e a32 ≥ g Au contraire pour le joueur
B, minimisant, sa perte doit être la plus faible possible :



 a11 q1 + a12 q2 + a13 q3 + a14 q4 ≥g


 a p +a p +a p +a q ≥g

12 1 22 2 23 3 24 4
(I I)


 a31 p1 + a32 p2 + a33 p3 + a34 q4 ≥g


q +q +q +q =1


1 2 3 4




 a11 q1 + ( a32 − α12 )q2 + a13 q3 + a14 q4 ≥ g


a21 q1 + ( a32 − α22 )q2 + a23 q3 + a24 q4 ≥ g


⇐⇒


 ( a32 + α31 )q1 + a32 q2 + ( a32 + α33 )q3 + ( a32 + α34 )q4 ≥ g (3)


q1 + q2 + q3 + q4 = 1


Chapitre 4. Jeux à deux personnes et à somme nulle 27

(3) ⇐⇒ a32 (q1 + q2 + q3 + q4 ) + α31 q1 + α33 q3 + α34 q4 ≤ g

⇐⇒ a32 + α31 q1 + α33 q3 + α34 q4 ≤ g

Le minimum est atteint si q1 = q2 = q3 = 0 D’où la solution optimale du jeu est :

p3 = 1; q2 = 1

q1 = q3 = q4 = p1 = p2 = 0

Remarque 9 On voit que dans un jeu à point selle, la propriété se généralise évidemment il
faut prendre pk = 1 et ql = 1 si le point selle est à l’intersection de la keme ligne et de la l eme
colonne.

Remarque 10 Le comportement des deux personnes jouant le jeu dont la règle est résumée
par M1 peut être aussi examiné d’un point de vue rudimentaire, en supposant seulement que
ces joueurs sont, tous deux intelligents et prudents

Hyp : A et B intelligent et prudents

A cherche à gagner le plus possible mais comme il est intelligent, il sait que de sont
coté, son adversaire cherchera à perdre le moins possible.
Sa prudence le conduit alors à determiner pour chacune des stratégies à sa disposi-
tion, le gain minimal qui figure dans la ligne correspondante :

– pour l1 : -2
– pour l2 : 1
– pour l3 : -1
et à choisir la stratégue qui correspond au maximum de ces gains = maxmin soit la
ligne 2 ou stratégie 2.
B quant à lui est amené, par un raisonnemen symétrique à determiner la perte maxi-
male colonne par colonne i.e stratégie pure par stratégie pure.
– col I c’est 2
– col II c’est 1
Chapitre 4. Jeux à deux personnes et à somme nulle 28

– col III c’est 2

Il choisira la perte minimale parmi celle-ci soit 1, qui correspond à la col II ou stratégie
II.
1 = minmax (ou minimum des maximum en colonne)
g A = p B avec (g A gain de A et p B perte de B)
i.e maxmin = minmax.

4.2 Généralisation en stratégie pures

La théorie des jeux se sert souvent des notions de minmax et de maxmin.

En stratégie pures :
minmax ( aij ) = min(max aij )
j i

maxmin( aij ) = max(min aij )

i j

Proposition 2 De façon générale

maxmin( aij ) ≤ minmax ( aij )

Cette inégalité devient une égalité si et seulement si le jeu possède un point selle en stratégies
pures.

Dans un jeu où le choix de chacun des joueurs est limité à des stratégies pures le gain
assuré du premier joueur qui montre naturellement le choix de l’adversaire est égal à
minmax ( aij ).
Le 2e joueur, tout en ignorant le choix de l’adversaire peut l’empêcher de gagner plus
de minmax ( aij ).
Donc g A est compris entre :

maxmin( aij ) ≤ q A ≤ minmax ( aij )

Si A obtient une information sur les intentions de l’adversaire, son gain assuré de-
vient :
minmax ( aij )
Chapitre 4. Jeux à deux personnes et à somme nulle 29

alors
σ = minmax ( aij ) − maxmin( aij )

σ est l’accroissement du gain assuré du premier joueur. Cette information ne pré-

sente un avantage pour le 1er joueur que si le prix à payer pour obtenir l’information
n’excède pas la valeur de σ. Dans un jeu à stratégies pures avec point selle une in-
formation sur le choix de l’adversaire ne change pas le gain assuré d’un joueur (cas
proposition 2.2 minmax = maxmin)

4.3 Jeux à informations Incompletes

Un très grand nombre de situations de conflit rendent impossible l’existence de

stratégies pures des joueurs susceptibles d’amener un point d’équilibre indépendam-
ment du comportement des adversaires.
La théorie permet cependant d’élaborer un comportement tel que le joueur qui l’ob-
serve dans chaque partie puisse s’assurer en un point d’indépendance.
La collection de nombre W = (w1 , w2 , · · · , wn ) est la stratégie mixte du second joueur.
Alors
ui ≥ 0 i = 1, 2, · · · , mw j ≥ 0 j = 1, 2, · · · , n

et
m n
∑ ui = 1; ∑ w j = 1
1 1
Une stratégie pure peut être définie comme une stratégie mixte dont toutes les com-
posantes sont nulles sauf une.
=⇒ Les stratégies pures des deux adversaires s’écrivent sous la forme des vecteurs
unitaires.
INACHEVE : A COMPLETER. Désolé