Programme R.

O
Première partie : Programmation linéaire
Chapitre1 : Introduction à la R.O (recherche Opérationnelle)
Chapitre2 : Elaboration d’un problème de programmation linéaire
Chapitre3 : Les méthodes de résolution d’un problème de programmation linéaire

Deuxième partie : La théorie des graphes

Chapitre4 : Définitions théorèmes
Chapitre5 : Représentions des graphes
Chapitre6 : Les graphes
 Chapitre 1 : Introduction à la R.O
La R.O est née pendant la seconde guerre mondiale des efforts conjugués d’éminents mathématiciens comme
Von Neumann, Dantzig et Blachette. Il avait été demandé à ses savants de fournir des techniques visant à
optimiser les ressources militaires. C’est pourquoi le qualitatif opérationnel vient du fait que les premières
applications de ce discipline avait trait aux opérations militaires.

1. Définition
La R.O est une discipline scientifique qui utilise des modèles mathématiques, statistiques et algorithmes pour
résoudre des problèmes de gestion et d’aide à la prise de décision. On peut aussi la définir comme l’ensemble
des méthodes et techniques rationnelles visant à trouver le meilleur choix possible. Elle vise à fournir des
bases rationnelles pour la prise de décision souvent dans le but de contrôler ou d’optimiser des systèmes.
La R.O s’applique à la compréhension et à la modélisation des systèmes industriels et du secteur public
traduisant ses systèmes en modèle théorique basé sur la mathématique, la statistique et l’informatique. Depuis
une dizaine d’années le champ d’application de la R.O s’est élargi à des domaines comme l’économie,
finance, le marketing, la planification d’entreprise et plus récemment la gestion de systèmes de santé et de
l’environnement.

2. Exemples d’application de la R.O

La R.O est appliquée dans tous domaines économiques :
a. Le commerce :
Elle permet de planifier la tournée d’un véhicule de livraison qui doit passer des points fixer avant de revenir
à son point de départ tout en cherchant à minimiser la distance parcourue : c’est un problème typique de R.O
et il est appelé le problème du voyageur de commerce.
b. La logistique :
Ce travail consiste à remplir un conteneur avec des objets de taille et de valeur variable. Si le conteneur a une
capacité finit ou limité, nous devons chercher à maximiser la valeur placé dans le conteneur : c’est le
problème du sac à dos.
 Chap 2 : La formulation de programmation linéaire
I. Définition d’un programme linéaire
Un programme linéaire (PL) est un problème d’optimisation mathématique qui consiste a trouvé la valeur
maximale ou minimale d’une fonction linéaire appelée fonction objective sous un ensemble de contraintes.
Ces contraintes sont représentées par des équations ou des inéquations linéaires qui limitent les valeurs
possibles de la fonction objective. En des termes plus simples il s’agit de trouver la meilleure allocation
possible des ressources limitées pour atteindre un objectif spécifique.
La linéarité signifie que les relations entre les variables sont représentées par des équations ou des
inéquations du premier degré sans terme exponentiels et sans logarithme. La programmation linéaire est une
technique largement utilisé en RO en raison de sa capacité à modéliser une grande variété de problèmes.
II. Les étapes d’une formulation d’un programme linéaire
La formulation d’un problème d’optimisation comporte 3 étapes suivantes :
1. Le choix des variables du modèle
On appelle variable du modèle toute quantité utile à la résolution du problème et dont le modèle doit
déterminer sa valeur. Elles sont aussi appelé les variables de décisions à déterminer pour atteindre l’objectif
d’optimisation.
Exemple : une entreprise spécialisée dans la fabrication de matériels informatique propose à son catalogue
d’ordinateur des centaines de références. Pour simplifier on s’intéresse seulement à deux types d’ordinateur
l’IM4 et l’IM5. Chacun d’eux possède un processeur le même mais les deux modèles diffère en particulier
par le nombre barrette mémoire. Plus précisément l’IM4 a 2 barrettes alors que l’IM5 a 6 barrettes.
Le marché pour ces composantes est tel qu’on ne peut espérer acheter au prêt des fournisseurs habituels plus
de 10000 processeurs par trimestre à venir et plus de 48000 barrettes mémoires. Une autre limitation risque
d’intervenir sur la production. L’assemblage est caractérisée par une opération délicate qui pour IM4 est de 3
mn et pour IM5 d’1 mn. Pour ces deux machines l’assemblage a un volume de 24000 mn pour le trimestre à
venir. En fin de compte l’entreprise ne peut espérer retirer un profit de 400£ pour IM4 et 800£ pour IM5.
L’objectif est alors de déterminer les quantités de chacun des deux types d’ordinateur pour obtenir le plus
grand profit.
Solution :
Choisir les variables du modèle
On choisit
IM4 correspond à x1
IM5 correspond à x2
2. Formulation mathématique de l’objectif
L’objectif ou le critère est la détermination des quantités des variables de décision pour maximiser le profit
Max 400x1 + 800 x2
3. Formulation des contraintes
Les contraintes du problème sont des relations qui limitent l’atteinte de l’objectif elle exprime d’une
inéquation
 Contraintes
 Processeur
X1+X2 ≤ 10 000
Barrette mémoire
2x1 + 6x2 ≤ 48 000
Assemblage
3x1 + x2 ≤ 24 000
Le programme linéaire peut s’écrire
Max 400x1 + 800x2
Sous contraintes
X1+X2 ≤ 10 000

2x1 + 6x2 ≤ 48 000

3x1 + x2 ≤ 24 000
Exemple 2 :
Une usine fabrique 2 pièces p1 et p2 à partir de 2 ateliers a et b. Les temps d’usinage sont pour p1 3h dans
l’atelier A et 6h dans l’atelier b et pour p2 4h dans l’atelier a et 3h dans l’atelier b. le temps de disponibilité
de l’atelier a est 160h et celui de l’atelier est de 180h. La marge bénéficiaire est de 1200f pour une pièce p1 et
1000f pour une pièce p2.
Ecrire le programme linéaire correspondant.
Solution :
Choisir les variables du modèle
P1 correspond à x
P2 correspond à y
Formulation mathématique de l’objectif
Maximiser le bénéfice
Max 1200x + 1000y
Formulation des contraintes
Contraintes
Atelier a
3x+4y ≤ 160
Atelier b

6x + 3y ≤ 180

Le programme linéaire peut s’écrire

Max 1200x + 1000y
Sous contraintes
3x+4y≤160
6x+3y≤180
 X ≥0, y ≥0

Exemple 3 :

La société JET produit 2 types de peintures A et B de 3 matières premières M1, M2 et M3.

Peinture de type A nécessite 10Kg de M1, 2Kg de M2 et 3Kg de M3. Son prix de vente est de 1200f.
Peinture de type B nécessite 5Kg de M1 et 3Kg de M2. Son prix de vente est de 1000f.
La société dispose de 200Kg de M1, 60Kg de M2 et 34Kg de M3.
Ecrire le programme linéaire qui permet de maximiser le profit de l’entreprise.

Solution :

Variables de décision

 Soit x1 correspond à la peinture A.

 Soit x2 correspond à la peinture B.

Fonction objectif

Maximiser le profit:

Max1200x1+1000x2

Contraintes

Matière première M1 (disponible : 200 kg)

 A utilise 10 kg, B utilise 5 kg :

10x1+5x2≤200

Matière première M2 (disponible : 60 kg)

 A utilise 2 kg, B utilise 3 kg :

2x1+3x2≤60

Matière première M3 (disponible : 34 kg)

 A n’en utilise pas, B n’en utilise pas :

x1≤34

Programme linéaire

Max 1200x1+1000x2
Sous contraintes :
10x1+5x2≤200
2x1+3x2≤60
x1≤34
x1≥0, x2≥0
 3. LA RESOLUTION D’UN PROBLEME DE
PROGRAMMATION LINEAIRE

La résolution d’un problème de programmation linéaire peut être réalisée de deux manières différentes en
fonction du nombre de variable de décision.
1. La résolution graphique :
La méthode graphique est utilisée si la fonction objective contient deux variables de décisions.
La résolution graphique est réalisée à travers les étapes suivantes :
a) La transformation du problème d’infériorité à un problème d’égalité
Elle consiste à remplacer les infériorités par des égalités exemple
-Problème d’infériorité :
Max 400x1+800x2
S /C
X1+x2≤1000
2X1+6x2≤48000
3x1+x2≤24000
-problème d’égalité
Max 400x1+800x2
S/C
X1+x2=1000
2X1+6x2=48000
3x1+x2=24000
b) Calcul des coordonnées des points
Chaque contrainte d’égalité correspond à une droite qu’on doit tracer à partir de deux points
avec des coordonnées choisies.
Exemple :
(D1)=x1+x2=10000
Si x1=0, x2=10000
A (0,10000)
Si x1=7000
7000+x2=10000
X2 = 10000-7000
X2=3000
B(7000,3000)

(D2)=2x1+6x2=48000
Si x1=0, 6x2=48000
X2=48000/6
X2=8000
A (0,8000)
Si 6x2=6000
2x1+6*6000=48000
2X1+36000 = 48000
2X1=48000-36000
2x1=12000
X1=12000/2
X1=6000
B(6000,6000)

(D3)=3x1+x2=24000
 Si x1=5000
3*5000+x2=24000
15000+x2=24000
X2=24000-15000
X2=9000
A (5000,9000)
Si x2=0
3x1=24000
X1= 24000 /3
X1=8000
B(8000,0)

(D1) : A(0,10000), B (7000 ,3000)

(D2) : A(0,8000), B (6000 ,6000)
(D3) : A(5000,9000), B (8000 ,0)
A2(3000,7000)
Echelle 1cm = 1000
c) Calcul des profits des points choisis
Fonction d’objective=
-Maxz 400x1+800x2
B (7000 ,3000) x1 7000 x2 3000
Maxz = 400*7000+800*3000
Maxz = 2800000+2400000
Maxz = 5200000

-Maxz 400*0+800*8000
A (0 ,8000) x1 0 x2 8000
Maxz = 6400000

-Maxz 400*8000+800*0
B (8000 ,0) x1 8000 x2 0
Maxz = 3200000

-Maxz 400*3000+800*7000
A2 (3000 ,7000) x1 3000 x2 7000
Maxz = 1200000+5600000
Maxz = 6800000

B (7000 ,3000) Maxz=5200000

A(0,8000) Maxz =6400000
B (8000 ,0) Maxz =3200000
A2(3000,7000) Maxz =6800000

Le point qui a le profit le plus élevé est choisi comme étant la solution le point A2 est alors
choisi.
A2 (3000 ,7000) x1= IM4= 3000
x2 =IM5= 7000
 L’entreprise doit produire 3000 ordinateurs de type IM4 et 7000 ordinateurs de type IM5 pour
avoir le profit le plus utilisé 6800000.

EXERCICE :
-Problème d’infériorité :
Max 1200x1+1000x2
S /C
10x1+5x2≤200
2x1+3x2≤60
x1≤34
-problème d’égalité
Max 1200x1+1000x2
S/C
10x1+5x2=200
2x1+3x2=60
x1=34

2 .La méthode du simplexe

La méthode n’est utilisée que pour la résolution des problèmes linéaires dont la fonction objective ne contient
que 2 variables de décisions or plusieurs variables de décisions peuvent être retrouvés dans les problèmes
linéaires et donc la méthode graphique ne serait plus applicable et doit être remplacer par la méthode du
simplexe. Cette méthode est initiée par Dantzig
 Exemple d’application de la méthode du simplexe
Soit le problème Maxz 160x1+300x2+500x3

S/C{3x1+3,5x2+5x3<=2250
{4x1+5x2+8x3<=3000
{x1+1,5x2+3x3<=900
{x1<=100
{x2<=150
{x3 <=75
{x1>=0, x2>=0, x3>=0

Cette formulations des problèmes linéaires est appelée la forme canonique.

Les variables x1 x2 x3 sont appelées variables de décisions ou variables initiales dont le modèle doit
déterminer leurs valeurs.
La résolution d’un problème linéaire par la méthode du simplexe est réalisée à travers les étapes
suivantes :
a) La transformation de la forme canonique à la forme standard
Un problème de programmation linéaire est dit sous forme standard si toutes les contraintes
sont transformées en contraintes d’égalités et toutes les variables sont positives.
Pour passer de la forme canonique à la forme standard il faut introduire dans les contraintes
une variable d’écart notée E.
EXEMPLE :
La forme standard Maxz 160x1+300x2+500x3

S/ {3x1+3,5x2+5x3 e1=2250
{4x1+5x2+8x3 e2=3000
{x1+1,5x2+3x3 e3=900
{x1 e4=100
{x2 e5=150
 {x3 e6=75
{e1, e2, e3, e4 ; e5, e6 >0
b) Le premier tableau du simplexe

I x1 x2 X3 E1 E2 E3 E4 E5 E6 C
E1 3 3,5 5 1 0 0 0 0 0 2250
E2 4 5 8 0 1 0 0 0 0 3000
E3 1 1,5 3 0 0 1 0 0 0 900
E4 1 0 0 0 0 0 1 0 0 100
E5 0 1 0 0 0 0 0 1 0 150
E6 0 0 1 0 0 0 0 0 1 75
Z 160 300 500 0 0 0 0 0 0 0
c) Les critères de Dantzig et le texte d’optimalité
Les critères de Dantzig sont appliqués au premier tableau et sont
-première critère : on fait entrer dans la base (Itération) la variable de décision ayant le
coefficient dans la fonction objective le plus importée ou le plus élevée.
La variable initiale déterminée nous donne la colonne du pivot
EMPLE : le coefficient le plus est 500 pour la variable x3.
x3 doit entrer dans la base, la colonne du pivot est la colonne x3.
-deuxième critère :
On divise chaque coefficient de la colonne du pivot par sa contrainte. On choisit la variable
d’écart ayant le résultat le plus faible et doit sortir de la base et être remplacer par la variable
de décision entrante.

EMEMPLE :
E1 : 2250/5= 450
E2 : 300/8 = 375
E3 : 900/3 = 300
E6: 75/1 = 75
75 est le résultat le plus faible dont e6 doit sortir de la case et être remplacer par x3,
E6 correspond à la ligne du pivot.
Le pivot est obtenu au point de rencontre de la colonne et de la ligne du pivot.
I x1 x2 X3 E1 E2 E3 E4 E5 E6 C
E1 3 3,5 5 1 0 0 0 0 0 2250
E2 4 5 8 0 1 0 0 0 0 3000
E3 1 1,5 3 0 0 1 0 0 0 900
E4 1 0 0 0 0 0 1 0 0 100
E5 0 1 0 0 0 0 0 1 0 150
E6 0 0 1 0 0 0 0 0 1 75
Z 160 300 500 0 0 0 0 0 0 0

-Texte d’optimalité :
La transformation (consistant à faire entrer dans la base des variables de décisions à la place
des variables d’écart) continue jusqu’à obtenir tous coefficient de la fonction objective nulle
ou négative.
- Deuxième tableau du simplexe
Pour remplir le deuxième tableau il faut commencer par :
-la colonne du pivot : on annule tous les coefficients de cette colonne sauf le pivot
-la ligne du pivot : on divise tous les coefficients de cette ligne par le pivot.
I x1 x2 X3 E1 E2 E3 E4 E5 E6 C
E1 3 3,5 0 1 0 0 0 0 -5 1875
E2 4 5 0 0 1 0 0 0 -8 2400
E3 1 1,5 0 0 0 1 0 0 -3 675
E4 1 0 0 0 0 0 1 0 0 100
E5 0 1 0 0 0 0 0 1 0 150
X3 0 0 1 0 0 0 0 0 1 75
Z 160 300 0 0 0 0 0 0 -500 -37500

I x1 x2 X3 E1 E2 E3 E4 E5 E6 C
E1 3 3,5 0 1 0 0 0 0 -5 1875
E2 4 5 0 0 1 0 0 0 -8 2400
E3 1 1,5 0 0 0 1 0 0 -3 675
E4 1 0 0 0 0 0 1 0 0 100
E5 0 1 0 0 0 0 0 1 0 150
X3 0 0 1 0 0 0 0 0 1 75
Z 160 300 0 0 0 0 0 0 -500 -37500

I x1 x2 X3 E1 E2 E3 E4 E5 E6 C
E1 3 3,5 0 1 0 0 0 0 -5 1875
E2 4 5 0 0 1 0 0 0 -8 2400
E3 1 1,5 0 0 0 1 0 0 -3 675
E4 1 0 0 0 0 0 1 0 0 100
E5 0 1 0 0 0 0 0 1 0 150
X3 0 0 1 0 0 0 0 0 1 75
Z 160 300 0 0 0 0 0 0 -500 -37500

E1 : 1875/3,5=
E2 : 2400/5 =
E3 : 675/1,5 = E5 : 150/1 = 150
150 est le résultat le plus faible dont e6 doit sortir de la case et être remplacer par x2,
E c5orrespond à la ligne du pivot.
Le pivot est obtenu au point de rencontre de la colonne et de la ligne du pivot

I x1 x2 X3 E1 E2 E3 E4 E5 E6 C
E1 3 0 0 1 0 0 0 -3,5 -5 1350
E2 4 0 0 0 1 0 0 -5 -8 1650
E3 1 0 0 0 0 1 0 -1,5 -3 450
E4 1 0 0 0 0 0 1 0 0 100
X2 0 1 0 0 0 0 0 1 0 150
X3 0 0 1 0 0 0 0 0 1 75
Z 160 0 0 0 0 0 0 -300 -500 -82500

I x1 x2 X3 E1 E2 E3 E4 E5 E6 C
E1 3 0 0 1 0 0 0 -3,5 -5 1350
E2 4 0 0 0 1 0 0 -5 -8 1650
E3 1 0 0 0 0 1 0 -1,5 -3 450
E4 1 0 0 0 0 0 1 0 0 100
X2 0 1 0 0 0 0 0 1 0 150
X3 0 0 1 0 0 0 0 0 1 75
Z 160 0 0 0 0 0 0 -300 -500 -82500

I x1 x2 X3 E1 E2 E3 E4 E5 E6 C
E1 3 0 0 1 0 0 0 -3,5 -5 1350
E2 4 0 0 0 1 0 0 -5 -8 1650
E3 1 0 0 0 0 1 0 -1,5 -3 450
E4 1 0 0 0 0 0 1 0 0 100
X2 0 1 0 0 0 0 0 1 0 150
X3 0 0 1 0 0 0 0 0 1 75
Z 160 0 0 0 0 0 0 -300 -500 -82500

I x1 x2 X3 E1 E2 E3 E4 E5 E6 C
E1 0 0 0 1 0 0 -3 -3,5 -5 1050
E2 0 0 0 0 1 0 -4 -5 -8 1250
E3 0 0 0 0 0 1 -1 -1,5 -3 350
X1 1 0 0 0 0 0 1 0 0 100
X2 0 1 0 0 0 0 0 1 0 150
X3 0 0 1 0 0 0 0 0 1 75
Z 0 0 0 0 0 0 -160 -300 -500 -98500

-texte d’optimalité :
Tous les coefficients de la fonction objective sont nuls ou négatifs : on arrête l’itération donc
l’entreprise doit produire
X1 = 100
X2= 150
X3= 75
Et le bénéfice optimal 98500 .

DEUXIEME PARTIE : LA THEORIE DES GRAPHES

CHAP 3 : LES GRAPHES

I. DEFINITIONS
Un graphe est un ensemble de nœud qui est reliés entre eux par des arcs.
EX de graphe :
Un arc relie 2 nœuds entre eux. Il peut être représenté par un couple (x, y) ou x et y sont des nœuds.
Un arc peut être orienté c’est-à-dire l’ordre de x et y est important dans le couple (x, y) .
Exemple : arc orienté (x, y)
x y
Un arc peut être non orienté et dans ce cas l’ordre n’a pas d’importance donc (x, y) = (y, x) avec non orienté
x y
Ce pendant un arc non orienté peut être transformé en deux arcs orientés
x y

-BOUCLE :
On appelle boucle un arc dont le nœud de départ et nœud d’arrivé sont les mêmes.
EXEMPLE :
Arc : (A, A) A
Arc : (B, B) B
-Demi-degré intérieur :
On appelle demi-degré intérieur d’un nœud le nombre arc adjacents qui y arrivent. C’est aussi le nombre
d’arcs qui entrent dans un nœud.
Il est noté : le nœud A dt (A)
-Demi-degré extérieur :
On appelle demi-degré extérieur d’un nœud le nombre arc adjacents qui en partent. C’est aussi le nombre
d’arcs sortant dans un nœud.
Il est noté :d- (A)
Le degré d’un nœud est la somme du demi-degré intérieur et du demi-degré extérieur.
Il est noté d(A)= dt (A) + d- (A)
Exemple : calculer le degré du nœud A

d(A)= dt (A) + d- (A)

dt (A)=4
d- (A)=4
d(A)=4+4=8
d(A)=8
-chaine :
on appelle chaine de x à y une séquence d’arc ou deux qui se suivent sont adjacents et x est l’extrémité du
premier arc (nœud de départ) et y est l’extrémité du dernier arc (nœud d’arrivé)
Exemple : à partir du premier arc
La chaine (A , G)
A nœud de départ
G nœud d’arrivé
A-D-G=(A , G)
i. A-B-E-G=(A , G)
-le chemin : Est une chaine dont les arcs sont orientés du nœud de départ au nœud d’arrivé.
Exemple pour aller de A à G nous pouvons utiliser les chemins suivants :
ch1 :A-D-G
ch2 :A-B-E-G
ch3 :A-C-F-G
ch4 :A-C-D-G
ch5 :A-B-D-G
-la longueur d’un point : est la somme des longueurs de chaque arc qui compose le chemin
ch1 :A-D-G=54
ch2 :A-B-E-G=49
ch3 :A-C-F-G=45
ch4 :A-C-D-G=43
ch5 :A-B-D-G=47

II. La recherche du plus court chemin

1 .L’algorithme de DIJKSTRA
Cet algorithme est utilisé dans un circuit orienté ou non orienté de longueur positive pour déterminer le
chemin le plus court entre plusieurs possibilités .il est utilisé dans circuit de production (la production par
atelier) et dans les trafics routiers et ferroviaires.
Exemple 1 : le graphe ci-dessous représente le plan d’une vie ou l’emplacement des maisons est représenté
par le point A et celui du lycée par le point G. en utilisant l’algorithme de DIJKSTRA, trouvez
A B C D E F G H
0A
 0A 7A 12A
7A 25B 16B
12A 22C 29C
21C 16B 43E
21C 25D 31E
25D

28F
42H 28F
42H

A-B-E-D-F-H-G=42Km
Exemple 2 :
A B C D E F G

A-C-D-G=43Km
A B C D E F G
0A
0A 1A 2A
1A 2A 3B 4B
5C 6C
3B 5D 6D
5D 4B 8F

10E
8E

A-B-f-G=8km