Contents

1 Théories des graphes 1

1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Circulation sur un graphe . . . . . . . . . . . . . . . . . . . . . 3
1.3 Recherche d’une plus courte chaine . . . . . . . . . . . . . . . . 4
1.4 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

2 Modélisation par la programmation linéaire 11

2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.2 Mise en équation d’un programme linéaire (Modélisation) . . . . 13
2.3 Présentation mathématique d’un système linéaire . . . . . . . . 13
2.4 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

3 Résolution graphique d’un programme linéaire 20

3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.2 Méthode graphique . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.3 Exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3.3.1 Problème de maximisation . . . . . . . . . . . . . . . . . 24
3.3.2 Problème avec solution non bornée . . . . . . . . . . . . 25
3.3.3 Problème impossible . . . . . . . . . . . . . . . . . . . . 25
3.3.4 Problème à solutions multiples . . . . . . . . . . . . . . . 25
3.3.5 Problème de dégénérescence . . . . . . . . . . . . . . . . 26

4 Résolution par la méthode de simplexe 28

4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
4.2 Variables d’écart et d’excédent . . . . . . . . . . . . . . . . . . . 29

i
CONTENTS ii

4.3 Variables de base et variables hors base . . . . . . . . . . . . . . 29

4.4 Solutions admissibles . . . . . . . . . . . . . . . . . . . . . . . . 30
4.5 Résolution du programme linéaire (P L) . . . . . . . . . . . . . . 30
4.6 Le critère d’arrêt . . . . . . . . . . . . . . . . . . . . . . . . . . 35
4.7 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
4.8 Exemple 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
4.9 Exemple 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

5 Dualité 42
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
5.2 Interprétation de la dualité . . . . . . . . . . . . . . . . . . . . . 43
5.3 Forme canonique du dual . . . . . . . . . . . . . . . . . . . . . . 45
5.4 Application . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

Recherche opérationnelle CHEMKHI Majed

Chapter 1

Théories des graphes

Contents
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . 2

1.2 Circulation sur un graphe . . . . . . . . . . . . . . 3

1.3 Recherche d’une plus courte chaine . . . . . . . . 4

1.4 Applications . . . . . . . . . . . . . . . . . . . . . . 5

1
1.1. INTRODUCTION 2

1.1 Introduction
Soit le graphe ci-dessous:

Figure 1.1: Exemple d’un graphe.

• La figure 1.1 représente un graphe.

• Les points 1, 2, 3, 4, 5 et 6 sont les Sommets de ce graphe.

• Les lignes reliant deux sommets sont appelés des arêtes.

• L’ordre d’un graphe est égale au nombre de ces sommets.

• On dit que deux sommets sont adjacentes s’ils sont reliés par une arête.

• Le degré d’un sommet est le nombre d’arêtes dont ce sommet est une
extrémité.

Définition
• Un graphe est Complet si chaque sommet est adjacent à tous les autres.
• Un sommet est isolé s’il n’est adjacent à aucun autre sommet.
Notation
Un graphe complet d’ordre n est noté Kn .
Remarque
∀n ≥ 2, le nombre d’arêtes d’un graphe complet Kn est Cn2 .
Lemme de poignées de main
La somme des degrés des sommets d’un graphe est égale à deux fois le nombre
des arêtes de ce graphe.

Recherche opérationnelle CHEMKHI Majed

1.2. CIRCULATION SUR UN GRAPHE 3

Conséquence
Le nombre des sommets de degrés impair d’un graphe est pair.
Exemple

• B et D sont deux sommets de degré impair.

• B et D sont deux points (impair).

1.2 Circulation sur un graphe

• Une chaine dans un graphe G est une suite finie S0 , a1 , S1 , a2 , S2 , a3 , ..., an , Sn
débutant et finissant par un sommet, alternant sommet et arête de telle
manière que chaque arête soit encadrée par ses sommets extrémités.

• La longueur d’une chaine est le nombre d’arêtes qui le décomposent.

• Une chaine est dite fermée si son origine et son extrémité sont confon-
dues.

• Un cycle est une chaine fermée composée d’arêtes toutes distinctes.

Notation
La chaine S0 , a1 , S1 , a2 , S2 , a3 , ..., an , Sn est notée S0 − S1 − S2 , −, ..., −Sn .
Définition: ”Connexe”
Un graphe G est dit connexe si on peut relier deux quelconques de ses sommets
par une chaine.
Définition: ”Chaine eulérienne/Cycle eulérien”

Recherche opérationnelle CHEMKHI Majed

1.3. RECHERCHE D’UNE PLUS COURTE CHAINE 4

• Une chaine eulérienne est une chaine vérifiant:

– Elle contient toutes les arêtes du graphe.

– Chaque arête n’est décrite qu’une seule fois.

• Un cycle eulérien est une chaine eulérienne fermée.

Remarque
Une chaine eulérienne ne peut pas contenir plusieurs fois la même arête, mais
elle peut passer plusieurs fois par le même sommet.
Théorème 1: ”Euler”
Un graphe connexe G admet une chaine eulérienne si et seulement si tous ses
sommets sont de degré pair ou deux uniquement de ses sommets sont de degré
impair (ce sont les extrémités de la chaine).
Théorème 2: ”Euler”
Un graphe connexe G admet un cycle eulérien si et seulement si tous ses som-
mets sont de degré pair.

1.3 Recherche d’une plus courte chaine

Définition:

• Un graphe pondéré est un graphe dont les arêtes sont affectées à des
coefficients positifs.

• Le poids d’une chaine est la somme des coefficients des arêtes qui le
composent.

• Une plus courte chaine entre deux sommets est parmi les chaines qui
les relient une chaine de poids minimum.

Recherche opérationnelle CHEMKHI Majed

1.4. APPLICATIONS 5

1.4 Applications
Exercice 1
Une personne souhaite inviter six amis qui nous désignons 1, 2, 3, 4, 5 et 6.
Malheureusement, certains de ces six amis ont des relations difficiles, ce sont
celles recensés dans le tableau suivant:

1 2 3 4 5 6
En relation difficile avec 2 1, 5, 6 5 5 2, 3, 4, 6 2, 5

On veut résoudre le problème (P ) suivant : combien de personne au maximum

peuvent être invitées ensemble sans risque de problème?

1. Représenter chaque ami par un point.

2. Relier deux points représentant deux personnes ayant une relation diffi-
cile.

3. Résoudre le problème (P ).

Exercice 2
Dessiner un graphe d’ordre 4 telque chaque sommet est adjacent à tous les
autres.
Exercice 3

1. Dessiner un graphe de sommet A, B, C, D et E telque:

• A adjacent à C, D et E.

• B adjacent à D.

• C adjacent à A et E.

2. Déterminer le nombre d’arêtes ayant pour extrémité D.

Exercice 4
Soit les graphes suivants:

Recherche opérationnelle CHEMKHI Majed

1.4. APPLICATIONS 6

1. Pour chacun de ces graphes, donner:

(a) Le degré de chaque sommet.

(b) La somme des degrés de tous les sommets.

(c) Le nombre d’arêtes.

2. Conclure.

Exercice 5
Dans un graphe (G), on considère la chaine:

A−B−C −B−D−A−E−B−C −X −Y

1. Déterminer la longueur de cette chaine.

2. Déterminer une autre chaine de (G) qui débute par A et se termine par
Y.

3. Déterminer alors sa longueur.

Exercice 6
Parmi ces graphes, reconnaitre ceux qui sont connexe en justifiant.

Recherche opérationnelle CHEMKHI Majed

1.4. APPLICATIONS 7

Exercice 7
Cinq pays sont représentés ci-dessous avec leur frontière.

1. Déterminer le graphe correspondant.

2. De quel pays doit-on partir pour visiter tous les autres pays en fran-
chissant chaque frontière une fois et une seule?

3. Est-il possible de partir d’un pays et d’y revenir en franchissant chaque

frontière une fois et une seule ?

Recherche opérationnelle CHEMKHI Majed

1.4. APPLICATIONS 8

Correction des exercices

Correction exercice 1
1.2.

3.

Donc, 4 personnes.
Correction exercice 2

Remarque: C’est un graphe complet.

Correction exercice 3

Recherche opérationnelle CHEMKHI Majed

1.4. APPLICATIONS 9

Correction exercice 4
A/

Degré de Somme de degré Nombre

Graphe chaque de tous d’arrêtes
sommet les sommets
A:2
G1 B:2 6 3
C:2
A:2
B:3
G2 C:2 12 6
D:3
E:2
A:2
B:4
G3 C:2 14 7
D:4
E:2
A:3
B:3
C:4
G4 D:4 22 11
E:2
F:4
G:2

B/ Conclusion:
• G1
I Connexe.
I Admet une chaine eulérienne (tous les sommets sont de degré paire).
I Admet un cycle eulérien.

Recherche opérationnelle CHEMKHI Majed

1.4. APPLICATIONS 10

• G2
I Connexe.
I Admet une chaine eulérienne.
I N’admet pas un cycle eulérien.
• G3
I Connexe.
I Admet une chaine eulérienne.
I Admet un cycle eulérien.
• G4
I Connexe.
I Admet une chaine eulérienne (tous les sommets sont de degré paire).
I N’admet pas un cycle eulérien.
Correction exercice 5

1. La longueur de cette chaine est 10.

2. A-E-B-C-X-Y :(G’).

3. La longueur de (G’) est 5.

Recherche opérationnelle CHEMKHI Majed

Chapter 2

Modélisation par la
programmation linéaire

Contents
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . 12

2.2 Mise en équation d’un programme linéaire (Mod-

élisation) . . . . . . . . . . . . . . . . . . . . . . . . . 13

2.3 Présentation mathématique d’un système linéaire 13

2.4 Applications . . . . . . . . . . . . . . . . . . . . . . 14

11
2.1. INTRODUCTION 12

2.1 Introduction
Les problèmes de programmation linéaires sont généralement liés à des prob-
lèmes d’allocation des ressources limitées, de la meilleur façon possible, afin de
maximiser un profit ou de minimiser un cout.
Le terme meilleur fait référence à la possibilité d’avoir un ensemble de décisions
possible qui réalisent la même satisfaction ou le même profit. Ces décisions
sont en général le résultat d’un problème mathématique.
Exemple
Une entreprise fabrique des portes et des fenêtres. Les profits réalisés sont de
30d par porte et 50d par fenêtre.
L’entreprise dispose de 3 ateliers :
Pour produire une porte, il faut 1h dans l’atelier N1 et 3h dans l’atelier N3 .
Pour produire une fenêtre, il faut 1h dans l’atelier N2 et 2h dans l’atelier N3 .
− L’atelier N1 est disponible pendant 4h par jour.
− L’atelier N2 est disponible pendant 12h par jour.
− L’atelier N1 est disponible pendant 18h par jour.
Combien de fenêtres et des portes doit-on produire afin de réaliser le profit
total de l’entreprise ?
• Mise en équation
Soit
x1 : Nombre des portes produites par jour.
x2 : Nombre des fenêtres produites par jour.
(Remarque: x1 et x2 sont les variables de décisions)
Profit: z = 30x1 + 50x2 (d/j)
Nombre d’heures consommées par jours dans chaque atelier:



 1x1 + 0x2 ≤ 4h

≤

 0x + 1x
1 2 12h


 3x1 + 2x2 ≤ 18h


 x ≥ 0, x ≥ 0
1 2

=⇒ Ceci s’appelle un programme linéaire.

Recherche opérationnelle CHEMKHI Majed

2.2. MISE EN ÉQUATION D’UN PROGRAMME LINÉAIRE
(MODÉLISATION) 13

2.2 Mise en équation d’un programme linéaire

(Modélisation)
Les étapes (les procédures) d’écrire un programme linéaire sont :

1. Définir les variables de décisions.

• Les variables doivent permettre d’écrire la fonction objectif (économique)

et toutes les contraintes décrite l’énoncé.

• Il faut préciser les unités de mesures de variable de décision.

2. Exprimer/Calculer la fonction objectif.

La fonction objectif exprime le but.

3. Ecrire les contraintes pour limiter les variables.

4. Evaluer le programme linéaire pour voir s’il respecte bien les énoncés
(fonction objectif et contraintes).

• Si oui, on accepte le programme linéaire.

• Si non, on revient à la première étape.

2.3 Présentation mathématique d’un système

linéaire
Un programme linéaire consiste à trouver le maximum ou le minimum d’une
forme linéaire dite fonction objectif en satisfaisant certaines équations et égal-
ités dites contraintes.
En langage mathématique, on décrira de tels modèles de la manière suivantes
:
Soit n variable de décision x1 , x2 , ..., xn réelles ou entiers positives ou négatives.
La fonction objectif est une forme linéaire en fonction des variables de décision
de type :
Z = c1 x1 + c2 x2 + ... + cn xn

Recherche opérationnelle CHEMKHI Majed

2.4. APPLICATIONS 14

Où les coefficients ci doivent avoir des valeurs bien déterminées et peuvent être
positifs, négatifs ou nuls.
Supposons que ces variables de décisions doivent vérifier un système d’équations
linéaires définie par M inégalités (>, <, ≤ ou ≥) ou égalités.



 a11 x1 + a12 x2 + ... + a1n xn ≤ (ou ≥ ou =) b1

a21 x1 + a22 x2 + ... + a2n xn ≤ (ou ≥ ou =) b2


..


 .


aM 1 x1 + aM 2 x2 + ... + aM n xn ≤ (ou ≥ ou =) bn


avec aij et bj doivent avoir des valeurs bien déterminées et peuvent être positifs,
négatifs ou nuls.
En suivant les étapes de formulation ci-dessus, on peut représenter le pro-
gramme linéaire (P.L) comme suit:

M ax(ouM in)Z = c1 x1 + c2 x2 + ... + cn xn




 a11 x1 + a12 x2 + ... + a1n xn ≤ (ou ≥ ou =) b1

a21 x1 + a22 x2 + ... + a2n xn ≤ (ou ≥ ou =) b2




..

s.c : .


aM 1 x1 + aM 2 x2 + ... + aM n xn ≤ (ou ≥ ou =) bn






 x ≥ 0, i = 1, ..., n
i

2.4 Applications
Exercice 1 ’Problème d’agriculture’
Un agriculteur veut allouer 150 hectares de surface irrigable entre culture de
tomates et celles de piments. Il dispose de 480 heures de main d’oeuvre et de
440 m3 d’eau. Un hectare de tomates demande 1 heure de main d’oeuvre, 4 m3
d’eau et donne un bénéfice net de 100 dinars. Un hectare de piments demande
4 heures de main d’oeuvre, 2 m3 d’eau et donne un bénéfice net de 200 dinars.
Le bureau du périmètre irrigué veut protéger le prix des tomates et ne lui
permet pas de cultiver plus de 90 hectares de tomates. Quelle est la meilleure
allocation de ses ressources ?
Réponse:

Recherche opérationnelle CHEMKHI Majed

2.4. APPLICATIONS 15

Soit
x1 : Surface allouer pour la tomate.
x2 : Surface allouer pour le piment.

M axZ : 100x1 + 200x2




 1x1 + 4x2 ≤ 480


 4x1 + 2x2


 ≤ 440
s.c : x1 ≤ 90


x1 + x2 ≤ 150






 x ≥ 0, x ≥ 0
1 2

Exercice 2 ’Problème de médecine’

Un spécialiste en médecine a fabriqué un médicament (des pilules) pour guérir
les sujets atteints d’un rhume. Ces pilules sont fabriquées selon deux formats :
• Petite taille : elle contient 2 grains d’aspirine, 5 grains de bicarbonate et
1 grain de codéine.
• Grande taille : elle contient 1 grain d’aspirine, 8 grains de bicarbonate et
6 grains de codéine.
Pour guérir la maladie, le sujet a besoin de 12 grains d’aspirine, 74 grains de
bicarbonate et 24 grains de codéine. Déterminer le nombre de pilules minimales
à prescrire au sujet pour qu’il soit guérit.
Réponse:
Soit
x1 : Nombre de pilules de petite taille.
x2 : Nombre de pilules de grande taille.

M inZ : x1 + x2




 2x1 + 1x2 ≥ 12

≥

 5x + 8x
1 2 74
s.c :


 1x1 + 6x2 ≥ 24


 x ≥ 0, x ≥ 0
1 2

Recherche opérationnelle CHEMKHI Majed

2.4. APPLICATIONS 16

Exercice 3 ’Problème de production’

Pour fabriquer deux produits P1 et P2 on doit effectuer des opérations sur trois
machines M1 , M2 et M3 , successivement mais dans un ordre quelconque. Les
temps unitaires d’exécution sont donnés par le tableau suivant:

M1 M2 M3
P1 11 mn 7 mn 6 mn
P2 9 mn 12 mn 16 mn

On supposera que les machines n’ont pas de temps d’inactivité.

Les disponibilités des machines sont:
• 165 heures pour la machine M1 .
• 140 heures pour la machine M2 .
• 160 heures pour la machine M3 .
Le produit P1 donne un profit unitaire de 900 dinars et le produit P2 un
profit unitaire de 1000 dinars. Dans ces conditions, combien doit-on fabriquer
mensuellement de produits P1 et P2 pour avoir un profit total maximum ?
Réponse:
Soit
x1 : Nombre de produit P1 fabriquer.
x2 : Nombre de produit P2 fabriquer.

M axZ : 900x1 + 1000x2




 11x1 + 9x2 ≤ 165 × 60 = 9900

≤ 140 × 60 = 8400

 7x + 12x
1 2
s.c :


 6x1 + 16x2 ≤ 160 × 60 = 9600


 x1 ≥ 0, x2 ≥ 0
Exercice 4 ’Problème d’alimentation’
On se propose de réaliser une alimentation économique pour des bestiaux,
qui contient obligatoirement 4 sortes de composants nutritifs, A, B, C et D.
L’industrie alimentaire produit précisément deux aliments M et N qui conti-

Recherche opérationnelle CHEMKHI Majed

2.4. APPLICATIONS 17

ennent ces composants : 1 Kg d’aliment M contient 100 g de A, 100 g de C,

200 g de D ; 1 Kg d’aliment N contient 100 g de B, 200 g de C, 100 g de D.
Un animal doit consommer par jour au moins : 0.4 Kg de A ; 0.6 Kg de B ;
2 Kg de C ; 1.7 Kg de D. L’aliment M coûte 10 DT le Kg et N coûte 4 DT le
Kg. Quelles quantités d’aliments M et N doit-on utiliser par jour et par animal
pour réaliser l’alimentation la moins coûteuse ?
Réponse:
Soit
x1 : Quantités d’aliments M.
x2 : Quantités d’aliments N.

M inZ : 10x1 + 4x2




 100x1 + 0x2 ≥ 0.4 × 1000 = 400





 0x1 + 100x2 ≥ 0.6 × 1000 = 600
s.c : 100x1 + 200x2 ≥ 2 × 1000 = 2000


200x1 + 100x2 ≥ 1.7 × 1000 = 1700






 x1 ≥ 0, x2 ≥ 0

⇐⇒

M inZ : 10x1 + 4x2




 x1 ≥ 4





 x2 ≥ 6
s.c : x1 + 2x2 ≥ 20


2x1 + x2 ≥ 17






 x ≥ 0, x ≥ 0
1 2

Exercice 5 ’Sélection de Médias’

Une entreprise désire effectuer une campagne publicitaire dans la télévision,
la radio et les journaux pour un produit lancé récemment sur le marché. Le
but de la campagne est d’attirer le maximum possible de clients. Les résultats
d’une étude de marché sont donnés par le tableau suivant:

Recherche opérationnelle CHEMKHI Majed

2.4. APPLICATIONS 18

Télévision
Radio Journaux
Locale Par satellite
Coût d’une publicité 40 DT 75 DT 30 DT 15 DT
Nombre de client 400 900 500 200
potentiel par publicité
Nombre de client 300 400 200 100
potentiel femme par publicité

Pour la campagne, on prévoit de ne pas payer plus que 800DT pour toute la
campagne et on demande que ces objectifs soient atteints :
• Au minimum 2000 femmes regardent, entendent ou lisent la publicité.
• La campagne publicitaire dans la télévision ne doit pas dépasser 500 DT.
• Au moins 3 spots publicitaires seront assurés par la télévision locale et
au moins de deux spots par la télévision par satellite.
• Le nombre des publicités dans la radio ou dans les journaux sont pour
chacun entre 5 et 10.
Réponse:
Soit
x1 : Nombre de client potentiel pour la télévision locale.
x2 : Nombre de client potentiel pour la télévision par satellite.
x3 : Nombre de client potentiel pour la radio.
x4 : Nombre de client potentiel pour les journaux.

Recherche opérationnelle CHEMKHI Majed

2.4. APPLICATIONS 19

M inZ : 400x1 + 900x2 + 500x3 + 200x4




 40x1 + 75x2 + 30x3 + 15x4 ≤ 800

300x1 + 400x2 + 200x3 + 100x4 ≥ 2000






40x1 + 75x2 ≤ 500





≥ 3

 x 1
s.c :


 x2 ≥ 2





 5 ≤ x3 ≤ 10

5 ≤ x4 ≤ 10






x1 , x2 , x3 , x4 ≥ 0


Recherche opérationnelle CHEMKHI Majed

Chapter 3

Résolution graphique d’un

programme linéaire

Contents
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . 21

3.2 Méthode graphique . . . . . . . . . . . . . . . . . . 21

3.3 Exemples . . . . . . . . . . . . . . . . . . . . . . . . 24

20
3.1. INTRODUCTION 21

3.1 Introduction
Le présent chapitre étudiera les méthodes de résolution pratique d’un pro-
gramme linéaire. La méthode graphique est l’une des premières méthodes
utilisées à ce sujet. Toutefois si on parle de résolution graphique alors on doit
se limiter à une représentation à deux variables et au plus à trois variables.
Pour généraliser, on va étudier les problèmes à n variables, il y a trois familles
d’algorithmes résolvant les programmes linéaires: le simplexe, les ellipsoı̈des et
les points intérieurs.
Dans ce cours on s’intéressera à la méthode de simplexe.

3.2 Méthode graphique

Procédure pour résoudre graphiquement un programme linéaire (P.L)
(à deux variables au maximum : deux axes)

1. Représenter un repère sur le plan ou chaque axe correspond à une variable

et choisir les échelles de chaque axe.

2. Pour chaque contrainte du programme linéaire, il faut déterminer les

points du plan qui respectent la contrainte et hachurer les points qui
respectent les contraintes:

a. Pour une contrainte d’égalité ax1 + bx2 = c, il suffit de tracer la droite

d’équation ax1 + bx2 = c et prendre tous les points du plan qui sont
sur la droite (les deux demi-plan).

b. Pour une contrainte d’inégalité ax1 +bx2 ≤ c, la contrainte représente

un demi-plan. On commence par représentation de la droite d’équation
ax1 + bx2 = c qui délimite le demi-plan, ensuite, on choisit un point
qui n’appartient pas à cette droite et on vérifie si ce point respecte la
contrainte. Si le point respecte le contrainte, on choisit le demi-plan
qui contient le point, si non, on choisit le demi-plan qui ne contient
pas ce point.

Recherche opérationnelle CHEMKHI Majed

3.2. MÉTHODE GRAPHIQUE 22

Quand on termine l’étape 2, les points du plan hachurés respectent toutes

les contraintes et s’appelle ’le domaine des solutions réalisables’.

3. Trouver la (où les) meilleur(s) solution(s) parmi toutes les solutions réal-
isables.

On va expliquer la méthode graphique par un exemple. On considère le prob-

lème linéaire à deux variables suivant:

M axZ : 40x1 + 60x2




 2x1 + x2 ≤ 70

≤

 x +x
1 2 40
s.c :


 x1 + 3x2 ≤ 90


 x1 ≥ 0, x2 ≥ 0
Chaque contrainte représente géométriquement un demi-plan. L’intersection
des demi-plans déterminés par les droites représente l’ensemble des solutions
qui satisfont aux contraintes. Graphiquement, on peut les schématiser dans
un repère (x1 , x2 ).

Recherche opérationnelle CHEMKHI Majed

3.2. MÉTHODE GRAPHIQUE 23

Définitions

1. On appelle solution réalisable (SR) toute solution vérifiant toutes les

contraintes (même les contraintes de signe).

2. On appelle domaine réalisable (DR) l’ensemble de tous les points

satisfaisant toutes les contraintes du programme linéaire

Dans notre exemple, le point (15, 10) appartient au DR. Ce point est dit réal-
isable. Par contre le point (30, 20) n’y appartient pas, parce qu’il ne satisfait
pas les contraintes: Ce point est dit non réalisable.
Par la suite, pour trouver la solution optimale (s’il en existe une) il suffit
d’examiner les points extrêmes de la région réalisable (rappelons que la PL est
un problème d’optimisation combinatoire). Dans la figure, on observe 5 points
extrémaux dont le point (15, 25) est optimal.

Caractéristique d’un PL
Le domaine réalisable d’un programme linéaire est ou bien vide ou un polyèdre
(c’est-à-dire convexe).
Théorème Pour un programme linéaire donné, si un optimum existe, au moins
un point extrême est optimal.
Corollaire Si un programme linéaire admet un optimum unique alors cet
optimum doit être un point extrême.
Les démonstrations de ces résultats ne sont le sujet de ce cours.
L’ensemble des solutions réalisables pour un problème à 2 variables est représenté
graphiquement par un polyèdre dans le plan. Pour un problème de taille plus

Recherche opérationnelle CHEMKHI Majed

3.3. EXEMPLES 24

élevée, on peut encore lui associer un polyèdre avec des sommets, des faces,
des arêtes, mais qui ne peut plus donner lieu à une représentation géométrique,
sauf si on reste dans R3 .

3.3 Exemples
Dans cette section on donne quelques exemples de résolution graphique de
problèmes linéaires relatifs au différents cas possibles:

3.3.1 Problème de maximisation

M axZ : 100x1 + 200x2




 x1 + x2 ≤ 150


 4x1 + 2x2


 ≤ 440
s.c : x1 + 4x2 ≤ 480


x1 ≤ 90






 x ≥ 0, x ≥ 0
1 2

Recherche opérationnelle CHEMKHI Majed

3.3. EXEMPLES 25

la solution optimale est B(40, 110).

3.3.2 Problème avec solution non bornée

M axZ : −2x1 + 3x2




 x1 ≤ 5
s.c : 2x1 − 3x2 ≤ 6


x1 ≥ 0, x2 ≥ 0


On peut augmenter la valeur de la fonction objectif dans la direction des flèches

indéfiniment donc la solution est non bornée.

3.3.3 Problème impossible

M inZ : 3x1 + 2x2


 x1 + 2x2

 ≤ 2
s.c : 2x1 + 4x2 ≥ 8


x1 ≥ 0, x2 ≥ 0


L’espace des solutions réalisables est vide, il est l’intersection des deux zones
grises.

3.3.4 Problème à solutions multiples

M axZ : x1 + 3x2

Recherche opérationnelle CHEMKHI Majed

3.3. EXEMPLES 26




 2x1 + 6x2 ≤ 30

≤

 x 1 10
s.c :


 x2 ≤ 4


 x1 ≥ 0, x2 ≥ 0

L’ensemble des points décrit par le segment [AB] représente les solutions op-
timales du problème linéaire.

3.3.5 Problème de dégénérescence

M axZ : x1 + x2




 3x1 + 2x2 ≤ 40

≤

 x 1 10
s.c :


 x2 ≤ 5


 x1 ≥ 0, x2 ≥ 0

Recherche opérationnelle CHEMKHI Majed

3.3. EXEMPLES 27

La solution optimale B(10, 5) est dite dégénérée si trois contraintes concourent

en ce point.

Recherche opérationnelle CHEMKHI Majed

Chapter 4

Résolution par la méthode de

simplexe

Contents
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . 29

4.2 Variables d’écart et d’excédent . . . . . . . . . . . 29

4.3 Variables de base et variables hors base . . . . . . 29

4.4 Solutions admissibles . . . . . . . . . . . . . . . . . 30

4.5 Résolution du programme linéaire (P L) . . . . . . 30

4.6 Le critère d’arrêt . . . . . . . . . . . . . . . . . . . . 35

4.7 Applications . . . . . . . . . . . . . . . . . . . . . . 35

4.8 Exemple 1 . . . . . . . . . . . . . . . . . . . . . . . . 35

4.9 Exemple 2 . . . . . . . . . . . . . . . . . . . . . . . . 38

28
4.1. INTRODUCTION 29

4.1 Introduction
Un programme linéaire (PL) mis sous la forme particulière où toutes les con-
traintes sont des équations et toutes les variables sont non négatives est dit
sous forme standard. Il est noté (PL=).

4.2 Variables d’écart et d’excédent

Avant que l’algorithme du simplexe puisse être utilisé pour résoudre un pro-
gramme linéaire, ce programme linéaire doit être converti en un programme
équivalent où toutes les contraintes technologiques sont des équations et toutes
les variables sont non négatives.

a. Contraintes de type (≤): Pour chaque contrainte i de ce type, on rajoute

une variable d’écart ei , tel que ei est une variable positive ou nulle.

Exemple: 3x1 + 2x2 ≤ 2 se transforme en 3x1 + 2x2 + e1 = 2, e1 ≥ 0.

b. Contraintes de type (≥): Pour chaque contrainte i de ce type, on retranche

une variable d’excédent ei , tel que ei est une variable positive ou nulle.
Exemple: 3x1 + 2x2 ≥ 2 se transforme en 3x1 + 2x2 − e1 = 2, e1 ≥ 0.

Un programme linéaire qui contient des contraintes (technologiques) de type

(≥) est noté (P L). Un programme linéaire qui contient des contraintes (tech-
nologiques) de type (≥, ≤, =) est noté (P G).
Un programme linéaire (P L), resp (P G) converti tel que toutes les contraintes
technologiques sont des équations et toutes les variables sont non négatives est
noté (P L =), resp (P G =).

4.3 Variables de base et variables hors base

Considérons un système d’équations à n variables et m équations où n ≥ m.
Une solution de base pour ce système est obtenue de la manière suivante :

a. On pose n − m variables égales à 0. Ces variables sont appelées variables

hors base (V.H.B.).

Recherche opérationnelle CHEMKHI Majed

4.4. SOLUTIONS ADMISSIBLES 30

b. On résout le système pour les m variables restantes. Ces variables sont

appelées les variables de base (V. B.).

c. Le vecteur de variables obtenu est appelé solution de base (il contient les
variables de base et les variables hors base).

Une solution de base est admissible si toutes les variables de la solution de

base sont ≥ 0.
Remarque Il est vraiment important d’avoir le même nombre de variables
que d’équations.

4.4 Solutions admissibles

Toute solution de base de (P L =) pour laquelle toutes les variables sont non
négatives, est appelée solution de base admissible. Cette solution de base
admissible correspond à un point extrême.

4.5 Résolution du programme linéaire (P L)

Programme linéaire

(P L) M axZ : 1000x1 + 1200x2




 10x1 + 5x2 ≤ 200


 2x1 + 3x2


 ≤ 60
s.c : x1 ≤ 34


x2 ≤ 14






 x1 ≥ 0, x2 ≥ 0
Programme linéaire standard

(P L =) M axZ : 1000x1 + 1200x2

Recherche opérationnelle CHEMKHI Majed

4.5. RÉSOLUTION DU PROGRAMME LINÉAIRE (P L) 31




 10x1 + 5x2 + e1 = 200





 2x1 + 3x2 + e2 = 60
s.c : x1 + e3 = 34


x2 + e4 = 14






 x ,x ,e ,e ,e ,e ≥ 0
1 2 1 2 3 4

Etape A: Tableau initial

Le tableau initial se construit de la manière suivante:

• L’encadré bleu correspond aux coefficients des contraintes du (P L =).

• L’encadré vert correspond aux Zj : c’est à dire les coefficients dans ×ai .

Exemple pour la colonne de x1 nommée (a1 ):

0 × 10 + 0 × 2 + 0 × 1 + 0 × 0 = 0

Les encadrés roses correspondent aux coefficients (Cj ) des variables dans la
fonction objectif (Z).
L’encadré gris correspond à la valeur des variables de base.
L’encadré orange correspond à la valeur de Z, donc la valeur de la fonction
objectif qui se calcule de la façon suivante:

0 × 200 + 0 × 60 + 0 × 34 + 0 × 14 = 0

Etape B: Choix de la variable entrante (dans la base)

• Maximum des Cj − Zj pour des problèmes de max.

Recherche opérationnelle CHEMKHI Majed

4.5. RÉSOLUTION DU PROGRAMME LINÉAIRE (P L) 32

• Minimum des Cj − Zj pour des problèmes de min.

• Dans notre exemple: x2 a le plus grand Cj − Zj donc, il entre dans la base.
Etape C: Choix de la variable sortante
Dans un problème de min ou de max, la variable sortante sera le minimum
des:

bi
, aik > 0
aik
Dans notre exemple, nous devons évaluer:
Var. entrante

14 est le minimum, donc e4 est la variable qui sort de la base.

Etape D: Pivotage

Recherche opérationnelle CHEMKHI Majed

4.5. RÉSOLUTION DU PROGRAMME LINÉAIRE (P L) 33

La cellule bleue est nommée le pivot. Pour passer au tableau suivant et donc
effectuer la première itération, il est essentiel d’utiliser le pivot.
Le pivotage s’effectue de la manière suivante:
On commence par diviser la ligne du pivot par le chiffre du pivot.
Dans notre exemple, on divise par 1.

Nous poursuivons avec la matrice identité pour les variables de base. Nous
inscrivons 1 à l’intersection de chaque variable et 0 ailleurs.

Nous devons calculer les nouvelles valeurs pour les cases restantes à partir du
tableau précédent (tableau initial pour la première itération).

Recherche opérationnelle CHEMKHI Majed

4.5. RÉSOLUTION DU PROGRAMME LINÉAIRE (P L) 34

Tableau initial:

Dans notre exemple, le 10 contenu dans l’encadré rouge provient de la formule

suivante:

element de la ligne du pivot ∗ element de la colonne du pivot

10 −
pivot
0∗5
Donc, 10 − 1
= 10
Faisons un autre exemple avec l’encadré vert. Nous obtenons ?3 de la façon
suivante:

3∗1
0− = −3
1

Recherche opérationnelle CHEMKHI Majed

4.6. LE CRITÈRE D’ARRÊT 35

Les cases restantes se calculent de la même façon.

Lorsque le tableau est rempli (comme ci-dessus), il est possible de passer à la
deuxième itération qui s’effectue de la même façon.

4.6 Le critère d’arrêt

Nous arrêtons lorsque nous obtenons le critère d’optimalité. L’algorithme du
simplexe s’arrête lorsque:
• Cj − Zj ≤ 0 pour un problème de max.
• Cj − Zj ≥ 0 pour un problème de min.

4.7 Applications

4.8 Exemple 1
(P L) M axZ : 30x1 + 50x2




 x1 ≤ 4

≤

 2x2 12
s.c :


 3x1 + 2x2 ≤ 18


 x ≥ 0, x ≥ 0
1 2

⇐⇒

(P L =) M axZ : 30x1 + 50x2

Recherche opérationnelle CHEMKHI Majed

4.8. EXEMPLE 1 36




 x1 + e1 = 4


 2x2 + e2 = 12
s.c :


 3x1 + 2x2 + e3 = 18


 x ,x ,e ,e ,e ≥ 0
1 2 1 2 3

x2 : variable entrante.
e2 : variable sortante.
2 : pivot.



 x 1 = x2 = 0





 e1 = 4
S.A : e2 = 12


e3 = 18






 Z = 0

Recherche opérationnelle CHEMKHI Majed

4.8. EXEMPLE 1 37

x1 : variable entrante.
e3 : variable sortante.
3 : pivot.



 x1 = e2 = 0





 e1 = 4
S.A : x2 = 6


e3 = 6






 Z = 300

Recherche opérationnelle CHEMKHI Majed

4.9. EXEMPLE 2 38

La solution optimale est:


 x1 = 2


x2 = 6


Z = 360


4.9 Exemple 2
(P L) M axZ : 1000x1 + 1200x2




 10x1 + 5x2 ≤ 200


 2x1 + 3x2


 ≤ 60
s.c : x1 ≤ 34


x2 ≤ 14






 x1 ≥ 0, x2 ≥ 0
⇐⇒

(P L =) M axZ : 1000x1 + 1200x2

Recherche opérationnelle CHEMKHI Majed

4.9. EXEMPLE 2 39




 10x1 + 5x2 + e1 = 200





 2x1 + 3x2 + e2 = 60
s.c : x1 + e3 = 34


x2 + e4 = 14






 x ,x ,e ,e ,e ,e ≥ 0
1 2 1 2 3 4

{x1 , x2 } : Variables hors base.

{e1 , e2 , e3 , e4 } : Variables de base.

x2 : variable entrante.
e4 : variable sortante.
1 : pivot.



 x1 = e2 = 0


e1 = 200






 e2 = 60
S.A :


 e3 = 34





 e4 = 14


 Z = 0

Recherche opérationnelle CHEMKHI Majed

4.9. EXEMPLE 2 40

x1 : variable entrante.
e2 : variable sortante.
2 : pivot.



 x1 = e4 = 0


e1 = 130






 e2 = 18
S.A :


 e3 = 34





 x2 = 14


 Z = 16800

e4 : variable entrante.

Recherche opérationnelle CHEMKHI Majed

4.9. EXEMPLE 2 41

e1 : variable sortante.
10 : pivot.



 e2 = e4 = 0


e1 = 40






 e3 = 50
S.A :


 x1 = 9





 x2 = 14


 Z = 25800

La solution optimale est:


 x1 = 15


x2 = 10


Z = 27000


Recherche opérationnelle CHEMKHI Majed

Chapter 5

Dualité

Contents
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . 43

5.2 Interprétation de la dualité . . . . . . . . . . . . . 43

5.3 Forme canonique du dual . . . . . . . . . . . . . . . 45

5.4 Application . . . . . . . . . . . . . . . . . . . . . . . 47

42
5.1. INTRODUCTION 43

5.1 Introduction
Tout programme linéaire (noté Primal) possède un programme équivalent (noté
Dual).

Primal Dual
Données A, b, c Données A, b, c
Minimiser Maximiser

En général

Contraintes ≤ ≥ =
Variables ≥ ≤ ≶

5.2 Interprétation de la dualité

Une compagnie, appelé MEUBLE, produit des:
• Bureaux.
• Tables.
• Chaises.
La fabrication de chaque type de produit nécessite de la matière première
(bois) et deux types d’activités: menuiserie et finition. On désire maximiser le
revenu. La quantité requise de chaque ressource est donnée comme suit:

Produit
Bureau Table Chaise Quantité disponible
Ressource de ressource
Bois (plaque) 8 6 1 48
Menuiserie (heure) 2 1.5 0.5 8
Finition (heure) 4 2 1.5 20
Prix de revient (DT) 60 30 20

On définit
x1 : Nombre de bureaux fabriqués.

Recherche opérationnelle CHEMKHI Majed

5.2. INTERPRÉTATION DE LA DUALITÉ 44

x2 : Nombre de tables fabriquées.

x3 Nombre de chaises fabriquées.
Le programme linéaire (P ) est le suivant:

M axZ : 60x1 + 30x2 + 20x3




 8x1 + 6x2 + x3 ≤ 48 (ressource bois)

≤

 2x + 1.5x + 0.5x
1 2 3 8 (ressource menuiserie)
s.c :


 4x1 + 2x2 + 1.5x3 ≤ 20 (ressource f inition)


 x1 ≥ 0, x2 ≥ 0, x3 ≥ 0

Supposons qu’un entrepreneur veut acheter toutes les ressources de MEUBLE.

Il veut certainement que le prix total de ces ressources soit minimal. On définit
alors:
y1 : Prix d’une plaque de bois.
y2 : Prix d’une heure menuiserie.
y3 : Prix d’une heure de finition.
L’entrepreneur doit payer: W (y) = 48y1 + 8y2 + 20y3 et désire minimiser
W , mais il doit payer suffisamment pour convaincre MEUBLE de vendre ses
ressources.
Par exemple, il doit payer au moins 60DT pour une combinaison de:
8 Plaques de bois.
2 Heures de menuiserie.
4 Heures de finition.
car MEUBLE peut utiliser ces ressources pour fabriquer un bureau et le vendre
pour 60DT. L’entrepreneur doit payer au moins 60DT, si non MEUBLE ne
verra aucune raison de lui vendre ses ressources.
=⇒ 8y1 + 2y2 + 4y3 ≥ 60
De même on a : 6y1 + 1.5y2 + 2y3 ≥ 30
et y1 + 0.5y2 + 1.5y3 ≥ 20
de plus, y1 , y2 , y3 ≥ 0
Le problème dual peut être donné comme suit :

Recherche opérationnelle CHEMKHI Majed

5.3. FORME CANONIQUE DU DUAL 45

(D) M inW = 48y1 + 8y2 + 20y3




 8y1 + 2y2 + 4y3 ≥ 60

≥

 6y + 1.5y + 2y
1 2 3 30
s.c :


 y1 + 0.5y2 + 1.5y3 ≥ 20


 y1 ≥ 0, y2 ≥ 0, y3 ≥ 0
Constatations
• Programme primal

(P ) M axZ : 60x1 + 30x2 + 20x3




 8x1 + 6x2 + x3 ≤ 48

≤

 2x + 1.5x + 0.5x
1 2 3 8
s.c :


 4x1 + 2x2 + 1.5x3 ≤ 20


 x1 ≥ 0, x2 ≥ 0, x3 ≥ 0
• Programme dual

(D) M inW = 48y1 + 8y2 + 20y3




 8y1 + 2y2 + 4y3 ≥ 60

≥

 6y + 1.5y + 2y
1 2 3 30
s.c :


 y1 + 0.5y2 + 1.5y3 ≥ 20


 y1 ≥ 0, y2 ≥ 0, y3 ≥ 0

5.3 Forme canonique du dual

Ressource i Demande j
Produit j aij cj
Coût i bi

• Problème primal (Demandeur de produit) : quelle quantité xi de

ressource i acheter pour satisfaire la demande à coût minimum.

Recherche opérationnelle CHEMKHI Majed

5.3. FORME CANONIQUE DU DUAL 46

X X
min bi x i s.c aij xi ≥ cj ∀j
i i

• Problème dual (Vendeur de produit) : à quel prix proposer les produits

pour maximiser le profit tout en restant compétitif.

X X
max cj w j s.c aij wj ≤ bi ∀i
j j

Conclusion Données A, b, c

 min z= cx


(P ) : s.c Ax ≥ b


x≥ 0


 max v= wb


(D) : s.c wA ≤ c


w≥ 0


min max
Primal Dual
Dual Primal
Variable ≥ 0 Contrainte ≤ 0
Variable ≤ 0 Contrainte ≥ 0
Variable ≶ 0 Contrainte =
Contrainte ≥ 0 Variable ≤ 0
Contrainte ≤ 0 Variable ≥ 0
Contrainte = Variable ≶ 0

Forme canonique du dual

1. La relation de dualité est involutive puisque le dual du dual est identique

au primal.

2. La matrice des coefficients des contraintes de D (resp. (P)) est la trans-

posée de celle de P (resp. (D)).

Recherche opérationnelle CHEMKHI Majed

5.4. APPLICATION 47

3. Les composants du second membre de D (resp.(P)) sont les coefficients

de la fonction objectif de P (resp.(D)).

4. Chaque colonne (ou variable) de P (resp.(D)) résulte en une contrainte

dans D (resp.(P)).

5. Lorsque (P ) est un problème de maximisation avec des contraintes de

type ≤, (D) est un problème de minimisation avec des contraintes de
type ≥, et vice versa.

Exemple 1:

Exemple 2:

5.4 Application
Soit

(P L) : M inZ = 6x1 + 9x2




 20x1 + 5x2 ≥ 25

≥ 60

 30x + 20x + 2y
1 2 3
s.c :


 5x1 + 10x2 ≥ 15


 x1 , x2 ≥ 0

Recherche opérationnelle CHEMKHI Majed

5.4. APPLICATION 48

On pose:
 
  x1
C= 6 9 ,X =  
x2
     
20 5 25 y1
     
A=
 30 20  , b =  60  , Y =  y2 
    
5 10 15 y3
Donc,

(P L) : M inZ = CX


 AX ≥ b
s.c :
 X ≥0

Le problème du al (D) est:

(D) : M axW = bt Y


 At Y ≤ Ct
s.c :
 Y ≥0
Donc,

(D) : M axW = 25y1 + 60y2 + 15y3


 20y1 + 30y2 + 5y3

 ≤ 6
s.c : 5y1 + 20y2 + 10y3 ≤ 9


y1 , y2 ≥ 0


⇐⇒

(D =) : M axW = 25y1 + 60y2 + 15y3

Recherche opérationnelle CHEMKHI Majed

5.4. APPLICATION 49


 20y1 + 30y2 + 5y3 + e1 = 6


s.c : 5y1 + 20y2 + 10y3 + e2 = 9


y1 , y2 , e1 , e2 ≥ 0


y2 : variable entrante.
e1 : variable sortante.
30 : pivot.



 y1 = y2 = y3 = 0


 e1 = 6
S.A :


 e2 = 9


 W = 0

Recherche opérationnelle CHEMKHI Majed

5.4. APPLICATION 50

y3 : variable entrante.
e2 : variable sortante.
20
3
: pivot.



 y1 = y3 = e1 = 0

 1
 y2 = 5
S.A :


 e2 = 5


 W = 12

La solution optimale de (D) est:

Recherche opérationnelle CHEMKHI Majed

5.4. APPLICATION 51




 y1 = 0


 y 3
2 = 40
3


 y3 = 4

63

 W = 4

D’où, la solution optimale de (P L) est:


3
 x1 =

 2
3
x2 = 4

 63
Z =

4

Recherche opérationnelle CHEMKHI Majed