6-RECHERCHE OPERATIONNELLE

INT1801/SEMESTRE II RECHERCHE OPERATIONNELLE PROPRIETE CNFEPD 1













RECHERCHE OPÉRATIONNELLE

LEÇON N°01 : INTRODUCTION A LA RECHERCHE OPÉRATIONNELLE ET À
LA PROGRAMMATION LINÉAIRE
LEÇON N°02 : ÉLÉMENTS DE LA THÉORIE DES GRAPHES
LEÇON N°03 : PROGRAMMATION LINEAIRE : LA METHODE DU SIMPLEXE
LEÇON N°04 : RECHERCHE D’UN CHEMIN DE LONGUEUR MINIMALE ET DE
LONGUEUR MAXIMALE DANS UN GRAPHE VALUE METHODE DE FORD
LEÇON N°05 : PROBLEME D’ORDONNANCEMENT : METHODE PERT
LEÇON N° 06 : LE CHOIX D’INVESTISSEMENTS

OBJECTIF PÉDAGOGIQUE

A la fin de cette matière, le stagiaire doit être capable d’appliquer les notions de la théorie
des graphes.

INT1801/SEMESTRE II RECHERCHE OPERATIONNELLE PROPRIETE CNFEPD 2

LEÇON N°01 : INTRODUCTION A LA RECHERCHE
OPÉRATIONNELLE ET À LA PROGRAMMATION LINÉAIRE

OBJECTIF PÉDAGOGIQUE : À la fin de cette leçon, le stagiaire doit être capable de :

1- Définir la recherche opérationnelle
2- Définir un programme linéaire
3- Résoudre graphiquement un programme linéaire à 2 inconnues

PLAN DE LA LEÇON:

I- LA RECHERCHE OPÉRATIONNELLE

1- Préceptes de la recherche opérationnelle
2- Démarche

II- LA PROGRAMMATION LINÉAIRE

1- Introduction générale
2- Qu’est ce qu’un programme linéaire
3- Résolution par la méthode graphique d’un programme linéaire

CONCLUSION

EXERCICES CORRIGÉS

INT1801/SEMESTRE II RECHERCHE OPERATIONNELLE PROPRIETE CNFEPD 3

I- LA RECHERCHE OPÉRATIONNELLE :

1- Préceptes de la recherche opérationnelle :

- Réfléchir avant d’agir ;
- Ne pas se fier au bon sens. Appuyez ses décisions sur des bases rationnelles ;
- Tirer le meilleur parti des moyens dont on dispose dans des circonstances données.

Ces préceptes qui pouvaient être ceux du parfait manager, sont ceux de la recherche
opérationnelle.

La RO consiste en l’application de méthodes scientifiques pour élaborer des décisions et
chercher à résoudre ainsi des problèmes complexes se rencontrant dans la direction et la
gestion de grands systèmes d’hommes, de machines, de matériaux et d’argent dans
l’industrie, le commerce, l’administration et la défense. La R.O propose une véritable
démarche scientifique pour les aborder.


- Chercher à comprendre et à structurer un système complexe en construisant un « modèle » ;
- Utiliser cette compréhension et ce modèle pour prédire est améliorer les performances du
système discipline carrefour, la recherche opérationnelle utilise pour arriver à ses fins des
techniques propres à d’autres disciplines scientifiques: Mathématiques, Statistiques,
Economique, Informatique.

2- Démarche:

Un premier exemple issu d’un grand domaine d’application de la RO, la logistique, va nous
servir à illustrer cette démarche.

Une entreprise doit livrer chaque matin quatre clients à partir d’un dépôt central. Un livreur
à bord d’un camion se rend donc dans les magasins des clients pour décharger ses
marchandises avant de retourner à son point de dépôt.

L’entreprise dans un 1er temps, cherche à organiser la tournée du livreur. Plus celle-ci est
courte, non seulement plus vite elle permet au livreur de participer à d’autres tâches, mais
surtout plus elle sera économique pour l’entreprise.

Dans ce cas, tout le système, représenté, par le livreur, les clients, l’entreprise et son
environnement, doit être pris en compte.

Après appréciation du coût de voyage entre deux (02) clients, exprimé en temps ou en unités
monétaires, le critère choisi à été unique: tournée dont la somme des coûts des liaisons
empruntées est la plus petite possible.

L’incertitude de certaines données pourraient être prise en compte, le temps de liaison entre
2 clients peut fluctuer suivant les heures de la journée, seule une valeur probable peut être
connue. D’autres contraintes peuvent exister. Que se passe-t-il si le volume de marchandises
à livrer aux clients excède la capacité du camion? Si certains clients ne sont présents que

INT1801/SEMESTRE II RECHERCHE OPERATIONNELLE PROPRIETE CNFEPD 4

pendant une certaine période de la matinée? Tout ceci montre que la construction d’un
modèle est délicate. Le problème posé est: Dans quel ordre le camion doit-il visiter les clients
pour accomplir une tournée de coût total minimal (le plus petit possible)? Les tournées
possibles sont au nombre de 24 :(1 2 3 4, 1 2 4 3, 1 3 2 4, 1 3 4 2, 2 1 3 4, 2 1 4 3, ……….),
quelle est donc celle qui fournit le circuit le moins coûteux. En énumérant ces 24 solutions et
en calculant le coût total des liaisons à assurer, la tournée cherchée sera nécessairement
trouvée. En calculant à la main, plus on moins maladroitement, cela prendra 5 minutes.

Passons maintenant à un ordre de grandeur supérieure, plus proche que la réalité: Vingt cinq
clients, par exemple, chiffre encore assez faible par rapport à une clientèle donnée réelle.
Les tournées possibles sont au nombre de 25! = 25 x 24x 23 x….x 2x 1, plus question de calcul
manuel, alors peut être un ordinateur? Mais pas d’illusions, même un ordinateur calculant
assez rapidement prendrait un temps équivalent à plusieurs siècles pour trouver la meilleure
tournée entre les 25 clients. Ceci est surprenant et montre qu’il faut parcourir à un modèle
mathématique (exprimant le problème) et ensuite le résoudre.

L’élaboration d’un modèle consiste en la définition de variables de décision, associées ici par
exemple au choix ou nom d’une liaison à emprunter entre 2 clients, la définition des
contraintes (passer par chaque client une et une seule fois) et de l’objectif représenté par un
but à optimiser (coût minimal) et ceci en fonction de ces variables.

Une fois le problème ainsi posé ; commence l’étude de la conception et de la mise en œuvre
informatique d’une méthode de résolution. Ce problème de tournée est appelé problème du
voyageur de commerce, il a acquis sa renommée pour plusieurs raisons qui ont éclairé
d’autres aspects de la R.O.

II- LA PROGRAMMATION LINÉAIRE :

1- Introduction générale à la programmation linéaire :

Établir un schéma de fabrication qui utilise de manière optimale un stock de matière
première limité, transporter des denrées de différents entrepôts vers différents magasins au
meilleur coût possible, tout en satisfaisant la demande des magasins et respectant la
disponibilité de chaque entrepôt : Voilà quelques exemples classiques de problèmes
économiques pour lesquels il importe de disposer de modèles mathématiques à la fois
simples, puissants et informatisables (en égard au nombre considérable de données à traiter).
On parle traditionnellement à leur sujet de programmation mathématique sans que le mot
« programmation » ne fasse en quelque manière que ce soit, référence à l’aspect
informatique : il s’agit dans chaque cas d’établir un schéma ou « programme » de fabrication,
de transport, optimisant une fonction économique (fonction bénéfice, fonction coût) dans
laquelle les variables sont soumises à des contraintes (limitation de stock de matière
premières) respect de l’offre et de la demande …).

Nous ferons lors de la modélisation, une hypothèse simplificatrice supplémentaire: « tout est
linéaire », la fonction économique et les contraintes. Cette réduction sévère couvre toutefois
une gamme importante d’applications pratiques et constitue le prix à payer pour obtenir le
modèle simple et puissant recherché: La programmation linéaire.

INT1801/SEMESTRE II RECHERCHE OPERATIONNELLE PROPRIETE CNFEPD 5


2- Qu’est ce qu’un programme linéaire ?

Pour illustrer cette définition commençons par un exemple.

2.1- Un premier exemple-type: Maximisation d’un bénéfice: Une usine fabrique
2 produits P1 et P2 à l’aide de 3 matières premières M1, M2 et M3 dont on dispose en quantités
limitées. Sous tous les cieux, et tous les régimes se pose le problème de l’utilisation optimale
de ce stock de matières premières, c’est à dire la détermination d’un schéma (programme)
de fabrication tel que:

- Les contraintes de ressources en matières premières sont respectées ;
- Le bénéfice réalisé par la vente de la production est maximum.

Modèle mathématique:

a- Données numériques des contraintes :

- La disponibilité en matières premières :






- Les caractéristiques techniques de la fabrication sont données dans le tableau ci-après ; y
figurent les quantités de matières premières nécessaires à la fabrication d’une unité de
chaque produit Pi.





b- Hypothèses de linéarité du modèle :

(L1) Linéarité des contraintes:On suppose que la fabrication est à rendement constant ; c’est
à dire, d’après le tableau ci-dessus pour fabriquer x1 unités de (P1) il faut ×1 unités de M1, ×1
unités de M2 et 2 ×1 unités de M3 , de même, la fabrication de ×2 unités du produit P2,
nécessite 3 ×2 de M1, ×2 unités de M2 et ×2 unités de M3.

(L2) Linéarité de la fonction économique: On suppose que le bénéfice peut être exprimé à
l’aide des bénéfices unitaires c1 et c2 sous la forme Z = c1 x1 + c2 x2.

c1 est le bénéfice unitaire.

C’est à dire : bénéfice réalisé par la fabrication d’une unité du produit P1, le bénéfice réalisé
par la fabrication de x 1 unités du produit P1 est alors c1 x 1. De même que pour le produit P2,
le bénéfice réalisé par la fabrication de ×1 unités de P1 et ×2 unités de P2 est Z = c1 × 1 + c2 × 2
ce qu’on a appelé fonction économique.


M1
M2
M3
P1
P2

1
3
1
1
2
1

18 unités de M1
8 unités de M2

INT1801/SEMESTRE II RECHERCHE OPERATIONNELLE PROPRIETE CNFEPD 6

c- Réalisabilité d’un schéma de production :

Un schéma de production est un couple désignant les

quantités de P1 et P2 fabriquées, il doit évidemment vérifier les contraintes x 1 ≥ 0, x 2 ≥ 0.

Un tel schéma est-il réalisable? A-t-on suffisamment de matières premières pour assurer une
telle production? Le niveau de fabrication nécessite x 1 + 3 x 2 unités de M1, x 1 + x 2 unités de
M2, 2 x 1 + x 2 unités de M3
.

Les disponibilités en matières premières montrent que le schéma
n’est réalisable que lorsque x1 et x2 vérifient


Les inéquations :



d- Le problème à résoudre est :











Soit le s matrices:


C = (c1, c2) le problème s’écrit matriciellement sous la forme:

Trouver X ≥ o tel que A x ≤ B et C x maximum ; ce que nous noterons



2.2 - Un deuxième exemple-type: Minimisation d’un coût:Dans une raffinerie, la
distillation de deux types de pétroles bruts B1 et B2 fournit 3 qualités d’essences E1, E2 et E3.

La raffinerie doit approvisionner un distributeur d’essences ; le problème consiste à
déterminer le meilleur schéma de distillation, c'est-à-dire les quantités de bruts à distiller
telles que :









(max)
z
c
b
A
0
x
x 1
x 1 + 3 x 2 ≤ 18
x 1 + x 2 ≤ 8
Trouver deux nombres x 1, x 2 tels que:

1- x 1 ≥ 0, x 2 ≥ 0 x 1 + 3 x 2 ≤ 18



x 1 + x 2 ≤ 8
x 1
x 1 1 3 18
X= , A= 1 1 , B = 8

INT1801/SEMESTRE II RECHERCHE OPERATIONNELLE PROPRIETE CNFEPD 7

1- Les quantités d’essences obtenues satisfont la demande ;
2- Le coût des quantités de bruts est minimum.

Modèle mathématique:

a- Données numériques de contraintes :

- La demande du distributeur est : 500 litres de E1, 400 litres de E2 et 600 litres de E3 ;
- La distillation de B1 et B2 fournit respectivement :

B1 : 10% de E1, 10% de E2, et 30% de E3.
B2 : 50% de E1, 20% de E2, et 20% de E3.

b- Hypothèses de linéarité du modèle :

(L1) linéarité des contraintes :On suppose que la qualité des bruts est toujours la même, et
que la distillation s’opère à rendement constant.

Exemple 1 :

La distillation d’un m3 de B1 produit 0,1 m3 de E1, 0,1 m3 de E2, et 0,3 m3 de E3.

La distillation de x1 m3 de B1 produit alors 0,1 ×1 m3 de E1 et alors 0,1x1 m3 de E2 et 0,3 x1 m3
de E3.

(L2) Linéarité de la fonction économique : Les coûts des bruts sont de 20 $ / m3 pour B1 et
de 25 $ / m3 pour B2 ;

On suppose une fois de plus qu’il n’y a pas de tarif dégressif.

c- Réalisabilité d’un schéma de distillation :

x 1
Un schéma de distillation est un couple désignant les quantités






x 2

(en m3) de B1 et B2 distillés; il doit évidemment vérifier les contraintes x 1 ≥ o et x 2 ≥ o ; un
tel schéma est réalisable lorsqu’il permet de satisfaire la demande du distributeur. Pour cela
x 1 et x 2 doivent vérifier :




Remarques:

1- Attention aux unités ! La demande du distributeur indiquée plus haut est exprimée en
litres, les quantités de bruts sont en m3 ;

2- Pour trouver les inéquations précédentes ; complétons, l’exemple précèdent : La
distillation de x 2 m3 de B2 produit 0,5 x 2 m3 de E1, 0,2 x 2 m3 de E2, 0,2 x 2 m3 de E3. Donc la
distillation de x 1 m3 de B1 et de x 2 m3 de B3 produit (0,1 x 1 + 0,5 x 2) m3 de E1 et (0,1 x 1
0,1 x 1 + 0,5 x 2 ≥ 0,5
0,1 x 1 + 0,2 x 2 ≥ 0,4

INT1801/SEMESTRE II RECHERCHE OPERATIONNELLE PROPRIETE CNFEPD 8

+ 0,2 x 2) m3 de E2, et (0,3 x 1 + 0,2 x 2) de E3. Ces quantités doivent être supérieures ou
égales à la demande.

d- Le problème à résoudre est :













(Z représente le coût total des bruts distillés)

Matriciellement ce problème s’écrit :

Trouver X ≥ 0 tel que A X ≥ B et C X minimum avec :

X =
; A =
; B =
; C =


Ce que nous noterons :




e- Changement d’unités: Formellement, d’un point de vue strictement mathématique, le
problème (P) peut s’écrire de manière équivalente sous la forme :




















2
x
1
x










2,0
3,0
2,0
1,0
5,0
1,0










6,0
4,0
5,0


25
,
20






min)
(
Z
X
C
B
X
A
0
X
Trouver deux nombres x 1 et x 2 tels que:


x 1 ≥ 0 , x 2 ≥ 0

0,1 x 1 + 0,5 x 2 ≥ 0,5

0,1 x 1 + 0,2 x 2 ≥ 0,4

0,3 x 1 + 0,2 x 2 ≥ 0,6
Z = 20 x 1 + 25 x 2 est le plus petit possible
(P)
Trouver 2 nombres x1 et x2 tels que


x 1 ≥ 0 ; x 2 ≥ 0

x 1 + 5 x 2 ≥ 5
x 1 +2 x 2 ≥4
(P′)

INT1801/SEMESTRE II RECHERCHE OPERATIONNELLE PROPRIETE CNFEPD 9

3- Résolution par la méthode graphique:

Soit le modèle du 1er exemple :




Soit : C1 = 3
et C2 = 2 ;

Résoudre graphiquement ce modèle revient à trouver les valeurs de x1 et x2 qui vérifient le
système d’inéquations et donne la plus grande valeur à la fonction économique Z.

On construit d’abord les droites d’équations respectives.



x1 + 3 x 2 = 18


x 1 + x 2 = 8

2 x 1 + x 2 = 14

Et éliminer, pour chacune de ces droites, le demi-plan dont les points ont des coordonnées
qui ne satisfont pas à l’inéquation correspondante.












Pratiquement, on trace les droites et on utilise les coordonnées de l’origine (o, o) pour
chacune des inéquations afin de vérifier que le signe de la région contenant ladite origine
convient ou non au sens de l’inéquation. On hachure ensuite la partie qui ne convient pas
comme ci-dessous indiqué:

D1 : x 1 + 3 x 2 = 18 passe par A
B




















(max)
Z
C
C
14
2
0
0
,
8
18
3
2
2
1
2
,
1
2
1
2
1
x
x
x
x
x
x
x
x
x
x
1
2
1










6
0
2
1
x
x










0
18
2
1
x
x
Rappel: Toute droite D d’équation a x + by + c = o

L’expression a x + by + c est strictement positive dans l’un et négative dans l’autre,
des deux demi-plans de frontière D ; que la droite d’unité partage le plan en 3
parties :

Les points appartenant à la droite et ayant des coordonnées vérifiant a x + by +
c = o.
Les 2 demi-plans délimités par (D) et dans lesquels, l’expression a x + by + c
garde un signe constant (nous l’admettrons sans démonstration).

INT1801/SEMESTRE II RECHERCHE OPERATIONNELLE PROPRIETE CNFEPD 10

D2 : x 1 + x 2 = 8 passe par C
D


D3 : 2 x 1 + x 2 = 14 passe par E
F















0
8
2
1
x
x










8
0
2
1
x
x










0
7
2
1
x
x










14
0
2
1
x
x
(OAPHE) contient
Toutes les solutions possibles (réalisables)
F
D
A
O
E
C
(D3)
(D2)
(D1)
x1
B
P
x2
H
3
P;
6
H;
Figure 1

INT1801/SEMESTRE II RECHERCHE OPERATIONNELLE PROPRIETE CNFEPD 11

Les coordonnées des points intérieurs et sur les côtés vérifient les contraintes, il faut donc
chercher celui qui donne le bénéfice le plus élevé.

Pour le savoir, on remplacera dans la fonction économique.


Z = 3 x1 + 2 x2 les coordonnées de chacun des points du domaine des solutions réalisables, on
obtient alors :


ZO = 3 (0) + 2 (0) = 0

ZA = 3 (0) + 2 (6) = 12

ZP = 3 (3) + 2 (5) = 19








ZE = 3 (7) + 2 (0) = 21

L’optimum est atteint au point H avec :






Un autres exemple: Soit le modèle (P/), comme il est à 2 inconnues, on peut facilement le
résoudre par la méthode graphique.

On construit d’abord les droites d’équations respectives :



x 1 + 5 x2 = 5


x 1 + 2 x2 = 4


3 x 1 + 2 x2 = 6

Et éliminer pour chacune de ces droites, le demi-plan dont les points ont des coordonnées qui
ne satisfont pas à l’inéquation correspondante.

D1 = x1 + 5 x2 = 5 passe par les points A
, B


D2 = x1 + 2 x2 = 4 passe par les points C
, D


D3 = 3 x1 + 2 x2 = 6 passe par les points E
, F















1
0






0
5






2
0






0
4






3
0






0
2
ZH = 3 (6) + 2 (2) = 22
*
x1 = 6
x2 = 2

INT1801/SEMESTRE II RECHERCHE OPERATIONNELLE PROPRIETE CNFEPD 12






















Remarque: Comme dans l’exemple précèdent, après avoir tracé les droites, on utilise les
coordonnées de l’origine (0,0) pour chacune des inéquations afin de vérifier le signe de la
région contenant ladite origine convient ou non au sens de l’inéquation, on hachure ensuite la
partie qui ne convient pas soit la première inéquation : x1 + 5 x2 ≥ 5, le point d’origine
ne
vérifie pas cette inéquation car 0 + 5 (0) ≥ 5 n’est pas vérifiée, on hachure alors la région qui
contient ce point, dans la figure précédente la partie non hachurée représente le domaine
des solutions possibles (réalisables).

Quel est le point qui minimise le coût total des bruts distillés ? pour répondre à cette
question, on remplace dans la fonction économique : 20 x1 + 25 x2 les coordonnées de chacun
des points : E, G, H, B

ZE = 20 (0) + 25 (3) = 75 $





ZH = 20 (10/3) + 25 (1/3) = 225/3 = 75 $

ZB = 20 (5) + 25 (0) = 100 $

Le minimum est atteint au point G =










0
0






2
/
3
1
x1 = 1
x2 = 3/2

H


(D3)
Figure 2
1 10/3
G = , H =
(D1)
(D2)
ZG = 20 (1) + 25 (3/2) = 115/2 = 57,5$
*

INT1801/SEMESTRE II RECHERCHE OPERATIONNELLE PROPRIETE CNFEPD 13

Remarque: Comment calculer un point d’intersection entre deux droites ? Il suffit de
résoudre le système d’équations constitué des équations des 2 droites. Prenons l’exemple de
la figure 2.

Le point d’intersection H entre les deux droites (D2) et (D1) : le calcul des coordonnées du
point H consiste à résoudre le système d’équations :




CONCLUSION:

Nous avons appris à modéliser un problème de maximisation ou de minimisation et de le
résoudre par la méthode graphique, modéliser un problème consiste à l’exprimer par un
modèle mathématique qu’on appellera, dans la leçon suivante, un programme linéaire. La
résolution par la méthode graphique n’est facile que si le modèle contient au plus deux
inconnues.

Dans la leçon suivante on introduira une méthode de résolution quand le modèle est à plus
que deux inconnues.

































4
x
2
x
5
x
5
x
2
1
2
1





1/3
x
10/3
x
2
1

INT1801/SEMESTRE II RECHERCHE OPERATIONNELLE PROPRIETE CNFEPD 14

EXERCICES CORRIGÉS :

EXERCICE N°1:

Résoudre graphiquement les programmes linéaires suivants
(P1)
(P2)
(P3)


EXERCICE N°2 :

Un laboratoire pharmaceutique doit élaborer un fortifiant à l’aide de 3 produits P1, P2, P3, des
normes en vigueur imposent au fortifiant une teneur minimal en vitamines V1 et V2, plus
précisément 8 unités de V1 et 12 unités de V2. Les teneurs en vitamines de chacun des
produits sont :


P1
P2
P3
V1
3
1
8
V2
4
2
9

Les coûts unitaires de chacun des produits sont : C1 = 24, C2 = 10, C3 = 72. Evidemment,
le laboratoire cherche à fabriquer son fortifiant au coût minimal, tout en respectant les
normes.

Exprimer ce problème sous forme d’un programme linéaire.

NB: Il n’est pas demandé de résoudre le programme linéaire.

EXERCICE N°3:

Soit deux produits P1, P2 fabriqués sur deux machines M1, M2 la production d’une unité de P1
exige 4 heures machines sur M1 et 2 heures machines sur M2, La production d’une unité de P2
exige 8 heures machines sur M1 et 2 heures machines sur M2.


M1
M2
Profit unitaire
P1
4
2
4
P2
8
2
6
Disponibilités
des Mi
84
24


1- Modéliser mathématiquement ce problème sous forme d’un programme linéaire noté (P)
sachant que l’objectif est de maximiser le profit.

2- Résoudre (P) par la méthode gra














0
x
,
0
x
4
x
x
2
4
x
2
x
x
3
x
2
Z
Max
2
1
2
1
2
1
2
1





















0
x
,
0
x
5

x
x
4

2x
x
2
x
2
x
3
x
2
x
Z
Max
2
1
2
1
2
1
2
1
2
1
















5
x
x
2
x
2
x
2
x
2x
x
x
Z
Min
2
1
2
1
2
1
2
1

INT1801/SEMESTRE II RECHERCHE OPERATIONNELLE PROPRIETE CNFEPD 15

SOLUTION DES EXERCICES:

EXERCICE N°1:

Résolution de (P1):

On commence par tracer les droites d’équations respectives :

D1 : x1 + 2 x2 = 4 passe par les points A =
, B =

D2 : 2 x1 + x2 = 4 passe par les points C =
, D =


















Pour chacune des droites tracées, on hachure la partie du plan dont les points ne vérifient pas
l’inéquation correspondante (OAEC) décrit le domaine des solutions réalisables, on l’appelle
aussi le domaine d’acceptabilité.

On compare les points O, A, C et E, on remplace leurs coordonnées dans la fonction
économique.

ZO = 2 (0) + 3 (0) = 0

ZA = 2 (0) + 3 (2) = 6

ZC = 2 (2) + 3 (0) = 4



*








2
0






0
4






0
2
ZE = 2 (
3
4
) + 3 ( 3
4 ) = 20 / 3

C
O
A
E
B
x1
(D1)
D
(D2)
x2

Figure 3

INT1801/SEMESTRE II RECHERCHE OPERATIONNELLE PROPRIETE CNFEPD 16

La meilleure solution est atteinte au point E =


x1 = 4/3

x2 = 4/3

Z = 20/3

Résolution de (P2) :

La droite D1 : - 3 x1 + 2 x2 = 2 passe par les points A :
, B:


La droite D2 : - x1 + 2 x2 = 4 passe par les points C :
, D :


La droite D3 : x1 + x2 = 5 passe par les points E :
, F :









































3
/
4
3
/
4






1
0








0
3
2






2
0






0
4






5
0






0
5






3
2
G
,
(D1
)
x1
x2
(D3)
(D2
)
Domaine
d’acceptabilité
الشكل-
4
-

2 1
G ; H
(D1)
(D2)
(D3)
x1
X2
Figure 4
Domaine
d’acceptabilité

INT1801/SEMESTRE II RECHERCHE OPERATIONNELLE PROPRIETE CNFEPD 17

ZO = 0 + 2 (0) = 0
ZA = 0 + 2 (1) = 2
ZF = 5 + 2 (0) = 5






*



ZH = 1 + 2. 5/2 = 6
L’optimum est atteint au point G =






Résolution de (P3):
D1 = - 2 x1 + x2 = 2 passe par les points A
, B




D2 = x1 - 2 x2 = 2 passe par les points C
, D


D3 = x1 + x2 = 5 passe par les points E
, F








3
2






2
0






0
1






1
0






0
2






5
0






0
5
ZG = 2 + 2 (3) = 8
x1 = 2
x2 = 3
Domaine
d’acceptabilité
D1
D3
x1
Figure 5
4 1
H ; P

INT1801/SEMESTRE II RECHERCHE OPERATIONNELLE PROPRIETE CNFEPD 18

(OAPHD) est le domaine des solutions réalisables.

- La valeur minimale de la fonction économique est atteinte au point :

ZO = 0 + 0 = 0
ZA = 0 + 2 = 0
ZG = -1 + 4 = 3





*

ZD = -2 + 0 = - 2

La solution optimale se trouve en H :







EXERCICE N°2 :

Soient x1, x2, x3 les nombres d’unités utilisées des produits P1, P2 et P3 respectivement : x1 ≥
0, x2 ≥ 0, x3 ≥ 0.

- Chaque unité de P1 contient 3 unités de la vitamine V1, x1 unités de V1 contiennent 3x1
unités de la vitamine V1 ;

- Chaque unité de P2 contient 1 unité de la vitamine V1 , x2 unités de P2 contiennent x2 unités
de la vitamine V1 ;

- Chaque unité de P3 contient 8 unités de V1, x3 unités de P3 contiennent 8 x3 unités de V1.

Les normes en vigueur imposent au fortifiant une teneur minimale de 8 unités de V1, c'est-à-
dire : le fortifiant doit contenir 8 unités de V1 ou plus ; soit :

3 x1 + x2 + 8 x3 ≥ 8

De même, le fortifiant doit contenir au moins 12 unités de la vitamine V2, D’après les teneurs
des 3 produits en V2, on a :

4 x1 + 2x2 + 9 x3 ≥ 12

La fonction économique à minimiser est 24 x1 + 10 x2 + 72 x3 , le programme linéaire associé à
ce problème est :





















Z(min)
x
72
x
10
x
24
12
x
9
x
2
x
4
8
x
8
x
x
3
0
x
;
0
x
;
0
x
3
2
1
3
2
1
3
2
1
3
2
1
ZH = - 4 + 1 = - 3
x1 = 4
x2 = 1

INT1801/SEMESTRE II RECHERCHE OPERATIONNELLE PROPRIETE CNFEPD 19

EXERCICE N°3:

1- Modéliser le problème consiste à exprimer les contraintes (sur les heures de disponibilité
des machines) et la fonction économique (qui est le profit à maximiser) en fonction des
inconnues x1, x2 nombres d’unités de P1, P2 à produire respectivement.

- Si on décide de produire x1 unités de P1 , et x2 unités de P2, on a besoin de 4 x1 + 8 x2 heures
machines sur M1, et 2x1 + 2x2 heures machine sur M2.

- Comme le temps de disponibilité des machines est limité : 84 heures sur M1 et 24 heures sur
M2, on a les contraintes suivantes :

4 x1 + 8 x2 ≤ 84
2 x1 + 2x2 ≤ 24

-
Le profit réalisé est : 4 x1 + 6 x2 qui est la fonction économique à maximiser :

Alors:


Est le programme linéaire associé à ce problème.

2- Résolution par la méthode graphique :

















(max)
Z
x
6
x
4
24
x
2
x
2
84
x
8
x
4
0
x
;
0
x
2
1
2
1
2
1
2
1
x2
(D2)
(D1)
B
x1
Domaine
d’acceptabilité
x2
D2
D1
Figure 6

INT1801/SEMESTRE II RECHERCHE OPERATIONNELLE PROPRIETE CNFEPD 20

Tracés des droites :


D1 : 4 x1 + 8 x2 = 84 passe par les points A
, B

D2 : 2 x1 + 2 x2 = 24 passe par les points C
, D


Calcul de la meilleure solution :
ZO = 4 (0) + 6 (0) = 0
ZA = 4 (0) + 6 (10,5) = 63




*


ZD = 4 (12) + 6 (0) = 48
L’optimum est donc atteint au point E :




































5,
10
0






0
21






12
0






0
12
ZE = 4 (3) + 6 (9) = 66
x1 = 3 ; x2 = 9
Z = 66

INT1801/SEMESTRE II RECHERCHE OPERATIONNELLE PROPRIETE CNFEPD 21

LEÇON N°02 : ÉLÉMENTS DE LA THÉORIE DES GRAPHES

OBJECTIF PÉDAGOGIQUE : À LA fin de cette leçon, le stagiaire doit être capable de
définir un graphe, un chemin, et un circuit, et de déterminer les niveaux de génération dans
un graphe sans circuit.

PLAN DE LA LEÇON :


INTRODUCTION

I- QU’EST-CE QU’UN GRAPHE ?

1- Définition
2- Exemple

II - VOCABULAIRE DE LA THÉORIE DES GRAPHES

III - CONCEPTS NON- ORIENTÉS

IV - RECHERCHE DE NIVEAU DANS UN GRAPHE SANS CIRCUIT

1- Définition de niveau de génération
2- Méthode de détermination des niveaux de chaque sommet à partir d’un exemple

V- CONCLUSION

EXERCICES CORRIGÉS

INT1801/SEMESTRE II RECHERCHE OPERATIONNELLE PROPRIETE CNFEPD 22

INTRODUCTION :

On regroupe généralement sous le titre de théorie des graphes des problèmes assez variés qui
ont tous comme caractéristiques communes de pouvoir être visualisés : des points
représentant des individus, des objets, des situations…..; sont joints par des flèches ou des
lignes symbolisant les relations existants entre eux. Jusqu’au milieu du 20ème siècle, la théorie
des graphes s’est développée en liaison avec des problèmes de physique et chimie, mais aussi
dans le cadre de recréations mathématiques (jeux). Ce n’est qu’après 1945 qu’on vit
apparaître des applications dans le domaine de la gestion, classées avec beaucoup d’autres,
sous le titre général de problème de recherche opérationnelle.

À la fin de ce cours le stagiaire doit être capable de définir un graphe, un chemin, et un
circuit, et de déterminer les niveaux de génération dans un graphe sans circuit.

I - QU’EST-CE QU’UN GRAPHE ?

Il convient de distinguer les graphes orientés de ceux qui ne le sont pas. Nous nous
intéressons ici aux premiers et nous donnerons par la suite quelques exemples des seconds.

1- Définition :

Les graphes orientés que nous traiterons dans cette leçon peuvent être considérés comme des
schémas représentant simplement la structure d’un problème. Ils sont généralement
déterminés par la donnée de :

a- Un ensemble fini
d’éléments appelés sommets du graphe ; Si X possède n
éléments distincts, le graphe sera dit d’ordre n.
b- Un ensemble fini
, dont les éléments sont des couples ordonnés de
sommets appelés arcs.

U est donc une famille d’éléments du produit cartésien


Exemple :Le graphe G(x, u) suivant, présente les résultats d’un tournoi d’échecs = les
sommets x1, x2, x3, x4 représentent les 4 concurrents, et l’existence d’un arc (xi, x j) ou plus
exactement la présence dans 4 de l’arc (xi, xj) indique que le joueur xi a remporté la partie
unique l’opposant au joueur xj.













n
2
1
,...
,
X
x
x
x



n
u
,....,
u
,
u
U
2
1




.
X
Y
X,
/x
y
x,
X
X




x1
X3
X4
X2

INT1801/SEMESTRE II RECHERCHE OPERATIONNELLE PROPRIETE CNFEPD 23


II- VOCABULAIRE DE LA THÉORIE DES GRAPHES :

Voici, quelques définitions de base relatives aux arcs et aux sommets d’un graphe G (X,U).

1- Extrémités d’un arc :

Un arc u = (x, y) possède une extrémité initiale x et une extrémité terminale y.

2- Boucle :

Une boucle est un arc dont les deux extrémités coïncident, elle est de la forme (x, x).

3- Arcs adjacents (voisins) :

Deux ou plusieurs arcs sont dits adjacents, s’ils ont au moins une extrémité en commun.

Exemple : Dans le graphe précédent les arcs (x1, x2) et (x3, x2) sont voisins, les arcs (x1, x4),
(x2, x4) et (x3, x4) sont eux aussi voisins ou adjacents.

4- Successeur :

On dit qu’un sommet y est un successeur d’un sommet x, s’il existe un arc ayant x comme
extrémité initiale et y comme extrémité terminale. L’ensemble des successeurs d’un sommet
x est noté T +(x).

Exemple : Dans le graphe précédent ; x4 est successeur du sommet x1 ; x1 n’est pas
successeur de x2 car il n’existe pas un arc (x2, x1).

5- Prédécesseur :

On dit qu’un sommet y est un prédécesseur du sommet x , s’il existe un arc ayant y comme
extrémité initiale et x comme extrémité terminale. L'ensemble des prédécesseurs d’un
sommet x est noté T– (x).

Exemple : Dans le graphe précèdent ; x1 est un prédécesseur du sommet x2 ; x1 n’a pas de
prédécesseur.

Remarque :

- Si x est prédécesseur de y alors y est successeur de x ;
- Dans quelques ouvrages, vous pouvez trouver que le mot prédécesseur est remplacé par
précèdent.














4
3
1
3
4
2
3
2
4
1
2
1
4
3
2
1
x
,
x
,
x
,
x
,
x
,
x
,
x
,
x
,
x
,
x
,
x
,
x
U
x
,
x
,
x
,
x
X



INT1801/SEMESTRE II RECHERCHE OPERATIONNELLE PROPRIETE CNFEPD 24

6- Sommets adjacents (voisins) :

Un sommet x est adjacent au sommet y, s’il est prédécesseur ou successeur de y. Ces
sommets peuvent aussi être qualifiés de voisins, on peut aussi dire que deux sommets sont
voisins s’il existe un arc qui les relie. On note par T(x) l’ensemble des sommets voisins de x,
T(x) = T +(x) U T – (x).

Exemple :Dans l’exemple précédent :


x1
x2
x3
x4


















7- Sommet isolé :

Un Sommet isolé est un sommet qui n’a pas de voisins.

8- Chemin :

Un chemin est une suite d’arcs dont l’extrémité terminale de chacun est l’extrémité initiale
du suivant, sauf pour le dernier.

Exemple :Dans le graphe suivant :














est un chemin ;
est un autre chemin.

Le chemin
est formé des arcs

,
.

Le chemin
est formé des arcs

,
.


T

T
T


4
3
2
x
,
x
,
x
φ


4
3
2
x
,
x
,
x


4
3 x
,
x

1
x


4
3
1
x
,
x
,
x


4
x


2
1 x
,
x


4
2
1
x
,
x
,
x



3
2
1
x
,
x
,
x


3
2
1
x
,
x
,
x


4
5
3
1
x
,
x
,
x
,
x


2
4
3
1
x
,
x
,
x
,
x


4
5
3
1
x
,
x
,
x
,
x


3
1 x
,
x


5
3 x
,
x


4
5 x
,
x


2
4
3
1
x
,
x
,
x
,
x


3
1 x
,
x


4
3 x
,
x


2
4 x
,
x
X4
x1
X3
X2
X5

INT1801/SEMESTRE II RECHERCHE OPERATIONNELLE PROPRIETE CNFEPD 25

Un chemin peut donc être défini soit par la suite des sommets qu’il contient, soit par la suite
d’arcs qui le composent.

Remarque : Si dans un chemin, l’extrémité initiale du premier arc coïncide avec l’extrémité
terminale du dernier arc, on parlera alors de circuit.

Exemple :Dans le graphe précédent
est un circuit,
est un
circuit.

III - CONCEPTS NON ORIENTÉS :

Si entre deux sommets x,y d’un graphe, il existe un arc (x,y) et un arc (y,x) , il peut
intuitivement paraître plus simple de remplacer ces deux arcs par un lien sans orientation. Si
cette situation se produit pour tous les couples de sommets, il n’y a plus aucune orientation à
en considération. On considère alors au lieu de l’arc (x,y), l’ensemble formé par les points x,y
qu’on note e = (x y) et qu’on appelle arête.

Le graphe non orienté est noté G(X, E) où X est l’ensemble des sommets et E l’ensemble des
arêtes.

IV- RECHERCHE DE NIVEAU DANS UN GRAPHE SANS CIRCUIT :

1- Définition de niveau de génération :

Dans un graphe sans circuit, il est possible de numéroter les sommets du graphe de telle sorte
que le numéro affecté à chaque sommet soit inférieur à celui des suivants (successeurs) et
supérieur à celui des précédents (prédécesseurs) ; ce numéro attribué à chaque sommet est
précisément le niveau de génération ou rang du sommet en question.

Les sommets de niveau 0 sont ceux qui n’ont aucun précèdent, ceux de rang 1 sont ceux dont
les précédents appartiennent au rang 0. Les sommets de niveau 2 ont des précédents de
niveau 0 ou 1 et ainsi de suite.

2- Méthode de détermination des niveaux de chaque sommet à
partir d’un exemple :
Soit le graphe suivant :















1
2
4
3
1
x
,
x
,
x
,
x
,
x


1
2
4
1
x
,
x
,
x
,
x
a
f
g
e
b
d
c

INT1801/SEMESTRE II RECHERCHE OPERATIONNELLE PROPRIETE CNFEPD 26

La détermination du niveau de chaque sommet se fait en plusieurs étapes :

Étape N° 1 :On écrit le dictionnaire des précédents dans le tableau suivant :

X
T– (x)
a
b
b
néant
c
b,e,f
d
a
e
g
f
g,e
g
a

Étape N°2 : On recherche ensuite dans ce dictionnaire des lignes vides, il se trouve qu’il n’y
en a qu’une, en l’occurrence la ligne « b ».

Par conséquent, « b » n’ayant aucun précédent est donc un sommet de niveau 0, ce que l’on
note : N0 =


On barre ensuite tous les « b » dans les colonnes X et T– (x) d’où le tableau N°1 suivant :

X
T– (x)
a
néant
c
e,f
d
a
e
g
f
g,e
g
a

On constate que la ligne « a » devient vide donc « a » est de niveau 1 soit : N1 =


Étape N°3 : On barre ensuite tous les « a » dans le tableau N°1, on obtient le tableau N°2
suivant :

X
T– (x)
c
e,f
d
néant
e
g
F
g,e
g
néant

Les lignes « d » et « g » deviennent vides, d et g sont des sommets de niveau 2, soit :

N2 =






b

a


g
d,

INT1801/SEMESTRE II RECHERCHE OPERATIONNELLE PROPRIETE CNFEPD 27

Étape N°4 : On barre ensuite tous les « d » et « g » d’où le tableau N°3, suivant :

X
T– (x)
c
e,f
e
néant
f
e

La ligne « e » devient vide, à son tour, ce qui signifie que le sommet e est de niveau 3, soit :

N3 =


Étape N°5 : On barre tous les « e », d’où le tableau N°4 suivant :





La nouvelle ligne vide est la ligne « f », donc le sommet f est de rang 4, soit : N4 =


Étape N°6 :On barre ensuite tous les « f », et on obtient le tableau N°5 ci-dessous :

X
T– (x)
c
néant

La ligne du sommet c étant vide, le sommet c sera de niveau 5, soit enfin :

N5 =


En résumé, les différents niveaux sont :

N0 =
N3 =

N1 =
N4 =

N2 =
N5 =


Cette détermination des niveaux du graphe, va nous permettre de représenter le graphe
précédant par un graphe plus lisible et plus facile à exploiter, car ordonnancé par niveau de
génération.












e

f

c

b

e

a

f


g
d,

c
X
T– (x)
c
f
f
néant
f
N3
N4
N5
N2
b
d
a
g
e
c
N0
N1

INT1801/SEMESTRE II RECHERCHE OPERATIONNELLE PROPRIETE CNFEPD 28

Ce graphe est identique au premier, sauf que la connaissance des niveaux de chaque sommet
a fait que sa représentation soit plus lisible que celle du 1er graphe.

V- CONCLUSION : UTILITÉ DU CONCEPT DE GRAPHE EN
RECHERCHE OPÉRATIONNELLE :

Un graphe peut représenter toutes sortes de situations dans les phénomènes d’organisation.
Par exemple, un réseau (c'est-à-dire un graphe comportant une entrée et une sortie) peut
correspondre à des canalisations où circule un fluide (liquide ou gaz).

Dans ce cas là, les quantités entrantes (par exemple par unité de temps) en un sommet
doivent être égales aux quantités sortantes (par unité de temps) en ce même sommet. Il est
facile, en effet, de comprendre que si trois canalisations apportent en un sommet A des
débits respectifs de 2,3 et 1 litres/mn.

Soit en tout 6L/mn(1), les canalisations qui partent de A doivent avoir un débit total de 6L
/mn. Mais un graphe n’est pas toujours un réseau représentant des circulations quelconques.






Souvent, une flèche entre deux points, implique seulement une relation de succession par
exemple, le graphe suivant peut valoir dire seulement que A précède B qui lui-même précède
C.





On dit qu’un graphe est value si, à tout arc qui le constitue, correspond une valeur numérique
qu’on écrit seulement sur la figure, à proximité de cet arc. Ces valeurs peuvent être des
quantités,
transportées,
des
débits,
des
coûts,
des
durées,
etc….
A
2
2
3
1
4
B
A
C

INT1801/SEMESTRE II RECHERCHE OPERATIONNELLE PROPRIETE CNFEPD 29

EXERCICES CORRIGÉS :

EXERCICE N°1 :

Soit le graphe G = (X,U) donné par sa représentation dictionnaire restreinte aux prédécesseurs
des sommets (voir tableau 1).

X
1
2
3 4
5
6
7
8
9
10
précéde
nts
–
1,
3
– 1
3
8,
9
2,5 2,4,
5
4
7,8,
9

- Dresser le graphe puis déterminer les niveaux de génération du graphe.

EXERCICE N°2 :

Soit un ensemble E =
.

On définit dans E la relation par:

x R y
x
E, y
E, (x est multiple de y ) et (x
y).

1- En utilisant les concepts de la théorie des graphes, proposer une représentation de cette
relation : définir l’ensemble des sommets X, celui des arcs U et dresser G = (X, U).

2- En utilisant le vocabulaire de la théorie des graphes que représente :

a- Un nombre premier.

b- Le sous-ensemble des éléments de E multiples d’un élément x de E.

c- Le sous-ensemble des éléments de E qui divise un élément x de E.

d- Le cardinal de E.

3- Donner le dictionnaire des prédécesseurs (précédents) du graphe obtenu.

Notes :

- Un nombre premier est un nombre qui n’est divisible que par 1 et lui-même : ex : 3, 7,
17,47….

- Le cardinal d’un ensemble est le nombre d’éléments qu’il contient. Le cardinal de
l’ensemble L =
est 3 ; le cardinal de l’ensemble vide est égal à zéro.










11
,9,
18
,6,2,0






5
,3,0


INT1801/SEMESTRE II RECHERCHE OPERATIONNELLE PROPRIETE CNFEPD 30

EXERCICE N°3 :

- Donner un ordonnancement par niveau des graphes suivants :








































Présenter les graphes sous forme plus lisible, les sommets étant disposés selon leurs niveaux
respectifs.



2
1
7
5
3
4
6
A
B
E
F
G
C
H
D

INT1801/SEMESTRE II RECHERCHE OPERATIONNELLE PROPRIETE CNFEPD 31

SOLUTION DES EXERCICES :

EXERCICE N°1 :



















Détermination des niveaux de génération :

Étape n°1 :D’après le dictionnaire des précédents, les sommets 1 et 3 sont de niveau 0, car
ils n’ont pas de prédécesseurs, soit N0 =

Étape n°2 :On supprime les sommets 1 et 3 du tableau, ce qui permet d’obtenir le tableau
suivant :

X
précédents
2
/
4
/
5
/
6
8,9
7
2,5
8
2,4,5
9
4
10
7,8,9

Les sommets de niveau 1 sont : N1 =
.








5,4,2
8
1
4
9
3
2
7
5
6
10

INT1801/SEMESTRE II RECHERCHE OPERATIONNELLE PROPRIETE CNFEPD 32

Étape n°3 : En supprimant les sommets de niveau 1 du tableau, on a :

X
P(x)
6
8,9
7
/
8
/
9
/
10
7,8,9

Les sommets de niveau 2, sont N2 =
.

Étape n° 4 :Ceci permet d’obtenir le tableau suivant :

X
P(x)
6
/
10
/

Les sommets du dernier niveau (3) sont N3 =
.

On a les niveaux de générations suivants :

N0 =
.
N1 =
.
N2 =
.
N3 =
.

EXERCICE N°2 :

1- La représentation de l’ensemble E ainsi que celle de la relation par un graphe
G = (X,U) peut être faite de la manière suivante :
X = E
U =

















9,8,7


10
,6

3,1


5,4,2


9,8,7


10
,6




y
x
et
y
de
multiple
est
x
X,
y
X,
x
/
y
x,



0
9
18
6
11
2

INT1801/SEMESTRE II RECHERCHE OPERATIONNELLE PROPRIETE CNFEPD 33

Ainsi :


2-
a- Un nombre premier n’a pas de successeurs ;
b- Le sous ensemble des éléments de E multiples d’un élément x de E représente
l’ensemble des prédécesseurs de x dans le graphe.

Exemples : Les multiples de 2 ; 6 et 18 sont les précédents du sommet dans le graphe.

c- Le sous ensemble des éléments de E qui divisent un élément x de E représente
l’ensemble des successeurs de x.

Exemple : Les diviseurs de 18 sont 2, 6,9 et ce sont ces successeurs dans le graphe

d- Le cardinal de E (qui est égale à 6) est l’ordre du graphe.
3-
X
précédents
0
/
2
0, 6,18
6
0,18
9
0,18
18
0
11
0

EXERCICE N°3 :

Pour le graphe1, présentons le dictionnaire des précédents :

X
P(x)
1
/
2
1
3
1,2,5
4
3,5
5
1
6
3,4
7
2,3

Les sommets de niveau 0 sont : N0 = 
1 , on supprime ce sommet du tableau ce qui donne :

X
P(x)
2
/
3
2,5
4
3,5
5
/
6
3,4
7
2,3














9,
18
,
6,
18
,
2,
18
,
2,6
,
11
,0
,
9,0
,
18
,0
,
6,0
,
2,0
U
,11
0,2,6,18,9
X



INT1801/SEMESTRE II RECHERCHE OPERATIONNELLE PROPRIETE CNFEPD 34

Les sommets de niveau 1 sont : N1 =

5,2
, la suppression des ces sommets, permet d’obtenir
le tableau suivant :

X
P(x)
3
/
4
3
6
3,4
7
3

L’ensemble N2 =
3 , sa suppression du tableau donne :

X
P(x)
4
/
6
4
7
/

On peut facilement déduire du tableau que N3 =

7,4
et N4 =
6 .

Soit :

















Pour le deuxième graphe, représentons aussi le dictionnaire des précédents :

X
P(x)
A
E
B
A,E,D
C
D,B,H
D
E
E
/
F
E,D
G
A,B ,C
H
F,D
N0 = 
1
N1 = 

5,2

N2 = 
3
1
7
3
5
2
6
4

INT1801/SEMESTRE II RECHERCHE OPERATIONNELLE PROPRIETE CNFEPD 35

N0 =
et le nouveau tableau est le suivant :

X
P(x)
A
/
B
A,,D
C
D,B,H
D
/
F
D
G
A,B ,C
H
F,D

N1=
sa suppression du tableau permet d’obtenir le tableau suivant :
X
P(x)
B
/
C
B,H
F
/
G
B ,C
H
F

N2 =
, On supprime ces 2 sommets du tableau ce qui permet d’obtenir le tableau
suivant :

X
P(x)
C
H
G
C
H
/

N3 =
, N4 =
et N5 =
peuvent être déduits de la même façon.

L’ordonnancement par niveau de ce graphe est :
















E


D
A,


F
B,

H

C

G
N0 = 
E
N1 = 

D
A,

N2 = 

F
,
B

N3 = 
H
N1
N3
N4
N5
N0
N2
E
A
D
F
H
C
G
B

INT1801/SEMESTRE II RECHERCHE OPERATIONNELLE PROPRIETE CNFEPD 36

LEÇON N°03 : PROGRAMMATION LINEAIRE : LA METHODE DU
SIMPLEXE

OBJECTIF PÉDAGOGIQUE : À la fin de cette leçon, le stagiaire doit être capable
d’écrire un programme linéaire sous forme canonique, sous forme standard et de résoudre un
programme de maximisation par la méthode algébrique et la méthode du simplexe.

PLAN DE LA LEÇON :

INTRODUCTION

I - NOTATION GENERALE D’UN PROGRAMME LINÉAIRE

II - FORMES CANONIQUE ET STANDARD D’UN PROGRAMME LINEAIRE

1- Notion de forme canonique.
2- Forme standard
3- Introduction de variables d’écart et de variables artificielles.

III - METHODES DE RESOLUTION DE MAXIMISATION

1- Méthode algébrique de substitution
2- Présentation pratique (Méthode du simplexe)

CONCLUSION

EXERCICES RESOLUS

BIBLIOGRAPHIE

INT1801/SEMESTRE II RECHERCHE OPERATIONNELLE PROPRIETE CNFEPD 37

INTRODUCTION :

Les problèmes de la programmation linéaire se posent lorsque l’on cherche à rendre optimum
(minimum ou maximum) une fonction linéaire1 de plusieurs variables, ces variables étant
assujetties à des contraintes linéaires, c'est-à-dire, du premier degré. Soulignons, à ce propos
qu’une contrainte est linéaire, lorsqu’elle s’exprime par une égalité ou inégalité dont le
premier membre est une combinaison linéaire ou forme linéaire des variables et le second un
nombre réel.

Afin d’étudier le programme linéaire, vous devez avoir des notions sur la résultions du
système d’équation linéaire par la méthode de substitution.

I - NOTATION GENERALE D’UN PROGRAMME LINEAIRE :

Soient les deux programmes linéaires suivants :

1- Trouver
0
x
0,...,
x
0,...,
x
,
0
x
n
i
2
1




tels que :







Et rendant :

n
n
i
i
2
2
1
1
x
c
......
x
c
.....
x
c
x
c





Maximum.

Remarque : On appellera b1, b2,……..bm, le second membre

2- Trouver
0
...x
;.........
0
;......x
0
x
;
0
x
n
i
2
1




tels que :









Et rendant :

n
n
i
i
2
2
1
1
x
c
......
x
a
.....
x
c
x
c





Minimum

En utilisant les notations matricielles, on peut abréger l’écriture de ces programmes
linéaires :

1 On a appelé cette fonction, la fonction économique.




…………………………………………



………………………………………………

INT1801/SEMESTRE II RECHERCHE OPERATIONNELLE PROPRIETE CNFEPD 38



Programme N° 1




Programme N° 2



Où










B =







Tout programme linéaire est donc formé de 3 grandes parties notamment :

a -
D’inconnues appelées «variables non-négatives » :

0
x
0.........
x
,
0
x
n
2
1



Dans le 1er et le 2ème programme.

b - D’équations ou inéquations au nombre de m : tenant lieu de contraintes et que doient
vérifier les n variables, chacune des équations ou inéquations étant une combinaison linéaire
du 1er degré par rapport aux variables non négatives.

Exemple :




c -D’une « fonction économique » à maximiser ou à minimiser ;


Z
x
......c
x
.....c
x
c
x
c
:
Ex
n
n
i
i
2
2
1
1




dans laquelle les coefficients Ci peuvent être positifs,
négatifs ou nuls.

De façon générale, la programmation linéaire a pour but la recherche de l’optimum d’une
fonction linéaire (fonction économique) comportant plusieurs inconnues positives ou nulles
liées, entre elles, par des relations linéaires indépendantes et formant un système
d’équations et inéquations appelées contraintes.

Trouver


Trouver










. . . .
. . . .
. . . .

A =
B =
X =
C =

INT1801/SEMESTRE II RECHERCHE OPERATIONNELLE PROPRIETE CNFEPD 39

II - FORMES CANONIQUE ET STANDARD D’UN PROGRAMME
LINEAIRE :

L’objectif de ce paragraphe est de définir les formes d’un programme linéaire, ces dernières
seront utiles pour introduire une autre méthode (dite du simplexe) pour la résolution d’un
programme linéaire.

1- Notion de forme canonique :

Lorsque l’ensemble de contraintes se présente sous forme d’inégalités 


ou
,
ou parle de
forme canonique.
Toutefois, il convient de distinguer un programme canonique de type I d’un programme
canonique de type II.

a - Un programme canonique de type I :Est un programme dans lequel les
contraintes inégalités sont tournées dans le sens « inférieur ou égal », l’objectif recherché
étant la maximisation de la fonction économique.

b - Un programme canonique de type II :A des contraintes inégalités tournées dans le
sens « supérieur ou égal » l’objectif est un minimum.

Exemples :









* Forme canonique de type I * Forme canonique de type II

c- Notion de forme mixte :Parfois, les contraintes sont tournées les unes dans un sens,
les autres dans le sens opposé, l’objectif pouvant être soit un maximum soit un minimum.
Mais on peut également avoir un mélange d’égalité (=) ou d’inégalités


ou
. Un tel
programme est un programme mixte. On dit aussi qu’il se présente sous forme mixte.

Exemples de formes mixtes ou de programmes mixtes :

INT1801/SEMESTRE II RECHERCHE OPERATIONNELLE PROPRIETE CNFEPD 40

2- Forme standard :

Dans un programme écrit sous forme standard, toutes les contraintes représentent des
égalités. L’objectif pouvant être le maximum ou le minimum.

Exemples :














La forme canonique s’avère plus pratique dans le cadre de la résolution par la méthode
graphique. Quant à la forme standard, elle n’apparaît intéressante que dans les méthodes
matricielles et plus particulièrement dans la méthode du simplexe que G.B Dantzig développa
à partir de 1948, et qui demeure encore la méthode la plus efficace.

Soulignons enfin que dans la méthode du simplexe, tous programme se présentant sous forme
canonique, doit être ramené sous la forme standard avec introduction de variables d’écart ou
artificielles selon le cas et selon des règles bien précises, ainsi que nous le verrons par la
suite.

3- Introduction de variables d’écart et de variables artificielles
(dans la méthode du simplexe) :

Le problème de l’introduction de variables d’écart et de variables artificielles ne peut se
poser que lors du passage de la forme canonique à la forme standard et dans le cadre de la
méthode du simplexe. Les exemples suivants permettront certainement de cerner tous les
aspects du problème. Nous appellerons VR = variables réelles ; VE = variables d’écart ; VA =
variables
artificielles.

INT1801/SEMESTRE II RECHERCHE OPERATIONNELLE PROPRIETE CNFEPD 41

Forme Canonique

Forme Standard Correspondante
N°1



2
1
2
1
2
1
2
1
2
1
200x
150x
Max
550
40x
15x
500
25x
10x
240
30x
20x

0
x
0
x













N°1


0
x
0
x
2
1



0
x
0
x
0
x
5
4
3




V.R V.E


5
4
3
2
1
5
2
1
4
2
1
3
2
1
0x
0x
0x
200x
150x
Max
550
x

40x

15x

500
x

25x

10x

240
x

30x

20x















N°2











4
x

x
8
4x
2x
15

3x

x
5

0
x
0
x

2
1
2
1
2
1
2
1



2
1
20x
10x
Max


N°2
0
x
0
x
2
1



0
x
0
x
0
x
5
4
3




0
x 6 

V.R V.E
V.A



6
5
4
3
2
1
6
5
2
1
4
2
1
3
2
1
Mx
0x
0x
0x
20x
10x
Max
4
x

x

x

x
8
x

4x

2x

15

x

3x

5x

















N°3





x
10
5x
Max

12

x
3
x
2
15

x
5
3x

0

x
0

x


2
2
1
2
1
2
1
1 










N°3


0
x
0
x
2
1



0
x
0
x
4
3




V.R V.E V.A










2
1
x

3x
2x
5
1

x

5x
3x

4
2
1
3
2
1



4
3
2
1
Mx
0x
x
0
1
5x
Max




N°4










16
2x
8x
4
2

8x
x
4

0
x
0
x

2
1
2
1
2
1




2
1
8x
10x
Max



N°4


0
x
0
x
2
1



0
x
0
x
0
x
5
4
3





V.R V.E V.A


5
4
3
2
1
5

2
1
4
3
2
1
Mx
-
Mx


0x


8x

10x
Max

16

x


2x
8x
4
2

x

x
-

8x
x
4















N°5


2
1
2
1
2
1
2
1
2
1
x
5
1
20x
Max

0
1

x
5

2x
6
1

x
6
1
8x

4
1
2x

x
7

0
x
0
x















N°5


0
x
0
x
2
1



0
x
0
x
0
x
5
4
3




0
x6 


V.R V.E
V.A

INT1801/SEMESTRE II RECHERCHE OPERATIONNELLE PROPRIETE CNFEPD 42



6
5
4
3
2
1
6
2
1
4
2
1
5
3
2
1
Mx
Mx
0x
0x
x
5
1
20x
Max


0
1

x

x
5
2x
6
1

x

x
6
1
8x
14

x

x

2x
7x




















N°6


3
2
1
X3
2
1
3
2
1
3
2
1
3
2
1
30x
20x
10x
Max


50

5
15x
3x
40

5x
8x
7x
50

10x
5x

8x

0
x
0
x
0
x



















N°6


0
x
0
x
2
1


0
x
0
x
0
x
0
x
6
5
4
3






V.R V.A


6
5
4
3
2
1
6
3
2
1
5
3
2
1
4
3
2
1
Mx
Mx
Mx
30x
20x
10x
Max

0
5

x


x
5
x
5
1
3x
0
4

x

x
5
8x
7x
0
5

x

x
10
5x
8x






















N°7


2
1
2
1
2
1
2
1
x
0
1
3x
Min
14
7x
2x
0
1
6x
5x
0
x
0
x












N°7


0
x
0
x
2
1



0
x
0
x
0
x
0
x
6
5
4
3






V.R V.E V.A



6
5
4
3
2
1
6
4
2
1
5
3
2
1
Mx
Mx
0x
0x
10x
3x
Min

4
1

x
x
7x
2x
10

x
x
6x
5x



















N°8


2
1
2
1
2
1
2
1
3x
x
Min
3
1
x
2
1
5x
1
2
x
9
x
0
1
0
x
0
x













N°8
0
x
0
x
2
1


0
x
0
x
0
x
5
4
3






V.R V.E V.A



5
4
3
2
1
4
2
1
5
3
2
1
Mx

0x

x
0

3x
x
Min
3
1



x
x
2
1
5x
1
2

x


x
-

x
9
x
0
1














N°9

0
x
0
x
2
1



0
x3 





3
2
1
3
2
1
3
2
1
3
2
1
4x

2x

9x
Max
20
-

7x

x

x
50

x

x

4x
100

10x

5x

x
3















N°9

0
x
0
x
2
1


0
x
0
x
0
x
5
4
3




0
x
0
x
7
6



V.R V.E
V.A



7
6
5
4
3
2
1
7
3
2
1
5
3
2
1
6
4
3
2
1
Mx

Mx

0x

0x

4x

2x

9x
Max
20
-

x



7x

x

x
50



x


x

x

4x
100

x

x
-
10x

5x

x
3






















INT1801/SEMESTRE II RECHERCHE OPERATIONNELLE PROPRIETE CNFEPD 43


 On voit à travers ces exemples que les variables artificielles interviennent exclusivement
dans les contraintes égalités (=) ou inégalités tournées dans le sens « supérieur ou égal à », le
second membre étant positif et l’objectif pouvant être le maximum ou le minimum.

 Si l’objectif est un minimum, les variables artificielles sont accompagnées d’un coefficient
positif M, dans la fonction économique. Si par contre il s’agit d’une maximisation, les
variables artificielles devront être accompagnées dans la fonction économique, d’un
coefficient négatif que l’on convient de noter –M avec
0
M
.

 D’autre part, toutes les contraintes de la forme :

1
n
1n
2
12
1
11
q
x
a
........
x
a
x
a






Deviennent des équations dans la forme standard et exigent l’introduction de variables
d’écart affectées d’un (+1), que l’objectif soit un minimum ou un maximum. Dans la fonction
économique ces variables d’écart seront accompagnées d’un coefficient nul quelque soit
l’objectif. Car elles représentent des écarts ou marges ou encore des bénéfices unitaires de
productions fictives (dans le cadre de la fabrication par exemple). Soulignons enfin que les
contraintes du type (≤) n’exigent que la présence de variables d’écart et jamais de variables
artificielles et ceci indépendamment de l’objectif envisagé.

Par contre, les contraintes de la forme :
1
n
1n
2
12
1
11
q
x
.........a
x
a
x
a





Requièrent la présence de variables d’écart et de variables artificielles. Les variables d’écart
sont affectées d’un (-1) et les variables artificielles d’un (+1) quelque soit l’objectif.

Mais dans la fonction économique on aura un coefficient nul pour la variables d’écart et (-M)
pour la variable artificielle si l’objectif est un maximum ; et dans le cas contraire, la variable
d’écart sera toujours affectée d’un coefficient nul dans la fonction économique tandis que la
variable artificielle est affectée d’un (+M).

Terminons en soulignant que les contraintes de type (=) n’admettent point de variables
d’écart mais seulement de variables artificielles affectées du signe correspondant à celui du
second membre. Dans la fonction économique, on agit exactement comme dans le cadre des
inéquations sus-énoncées.


N°10


2
1
2
1
2
1
2
1
1
x
10x
Min
3
7x
3x
0
1
2x
x
5
x
2x
x













N°1
0

0
x
0
x
2
1


0
x
0
x
0
x
5
4
3




0
x
0
x
0
x
8
7
6




V.R V.E
V.A



8
7
6
5
4
3
2
1
8
5
2
1
7
4
2
1
6
3
2
1
Mx
Mx
Mx
0x
0x
0x
x
x
10
Min


3
x
x
7x
3x
10
x
x
2x
x
5
x
x
x
2x

























INT1801/SEMESTRE II RECHERCHE OPERATIONNELLE PROPRIETE CNFEPD 44

III - METHODES DE RESOLUTION DE MAXIMISATION :

1- Méthode algébrique de substitution :

1.1- Principe de la méthode :

Étape 1 : Dresser la forme canonique du problème posé.

Étape 2 : Passer de la forme canonique à la forme standard en transformant les inéquations
en équations et en introduisant les variables d’écart ou artificielles selon le cas.

Étape 3 : Poser la solution extrême de base en utilisant d’abord les variables réelles comme
variables non principales (qu’on appellera variables hors base ou variables nulles).

Les autres variables non nulles obtenues, constituant les variables principales ou variables
dans la base. A ce stade la fonction économique est nulle.

Étape 4 : Passer à la 1ère itération (répétition) afin de trouver une solution de base meilleure,
c'est-à-dire améliorer la valeur de la fonction économique.

Pour y parvenir on sélectionnera une variable entrante et une variable sortante selon les
critères de Dantzig suivants :

a - Critère d’entrée :La variable entrante est une variable hors base qui dans la fonction
économique présente le coefficient positif le plus élevé.

b - Critère de sortie :La variable sortante est une variable dans la base, qui correspond au
plus petit rapport positif des seconds membres des contraintes aux coefficients de la variable
entrante (l’infini et les nombres négatifs étant exclus).

Étape 5 : On arrête les différentes itérations dés que la fonction économique ne contient
plus que des coefficients négatifs ou nuls.

Exemple :Résoudre le programme linéaire suivant à l’aide de la méthode de substitution :









Le programme linéaire (S1) est déjà sous forme canonique, pour avoir la forme standard, il
s’agit seulement d’ajouter des variables d’écart
0
x
,
0
x
,
0
x
5
4
3









S1

INT1801/SEMESTRE II RECHERCHE OPERATIONNELLE PROPRIETE CNFEPD 45











- Recherche de la solution de base : En utilisant l’énoncé de l’étape 3 ; la première
solution de base (qu’on a appelé solution extrême), les variables réelles (sont appelées hors
base ou non principales ou nulles). Ici on a :
0
x
;
0
x
2
1




Les autres variables non nulles, sont les variables dans la base ; on déduit leurs valeurs en
remplaçant dans (S2).

De la 1ère équation :
140
x 3 

De la 2ème équation :
104
x 4 

De la 3ème équation :
360
x5 


A ce stade, la fonction économique est nulle

La solution extrême de base est :














1ère Itération : C’est l’étape 4, le but est de trouver une solution de base meilleure c'est-à-
dire améliorer la fonction économique.

Pour choisir la variable entrante ; c’est l’une des variables hors base qui a le coefficient
positif le plus grand dans la fonction économique ; dans notre exemple : c’est
1
x .

Si
1
x entre dans la base ; elle ne sera plus nulle, quelle est la valeur à affecter à
1
x :


À partir des équations (S2) ; on peut obtenir le système (S3)












2
1
5
2
1
4
3
3x
5x
360
x
x
x
104
x
S



Or
où
d'
,
base
la
de
hors
est
elle
car
0
x2 
:

0
Z
360
x
104
x
140
x
B
0
x
,
0
x
:
HB
5
4
3
2
1







Équation d’échange


S2

INT1801/SEMESTRE II RECHERCHE OPERATIONNELLE PROPRIETE CNFEPD 46












1
5
1
4
1
3
4
5x
360
x
x
104
x
2x
140
x
S






Le niveau maximum à affecter à


70
70,104,72
Min
x
:
est
x
1
1


. On affecte donc la valeur
1
x
à
70
; et on cherche la variable sortante. Ce sera celle qui s’annulera après substitution de
70
par
x1
.






La variable sortante est donc
3
x

La nouvelle solution obtenue à partir de cette 1ère itération est :










2ème Itération :Dans (S3) l’équation d’échange est celle qui fournit la variable sortante, soit :

2
1
3
x
2x
140
x





Dans cette équation, on exprime la variable entrante à l’aide de variables hors base
3
2
x
et
x

soit :
2
3
1
x
2
1
x
2
1
70
x





On remplace ensuite cette nouvelle expression de
1
x dans les différentes équations de (S3) ce
qui donne :

































2
3
1
2
2
3
5
2
2
3
4
x
2
1
x
2
1
70
x
x
3
x
2
1
x
2
1
70
5
360
x
x
x
2
1
x
2
1
70
104
x

490
4.0
7.70
34
x
10
x
70
x
B
0
x
;
0
x
HB
4
5
1
3
2













Or

INT1801/SEMESTRE II RECHERCHE OPERATIONNELLE PROPRIETE CNFEPD 47



















2
3
1
2
3
5
2
3
4
x
2
1
x
2
1
70
x
x
2
1
x
2
5
10
x
x
2
1
x
2
1
34
x


2
2
3
4x
x
2
1
x
2
1
70
7
Z












2
3
x
2
1
x
2
7
490
Z





On obtient donc le système :

























2
3
2
3
1
2
3
4
5
x
2
1
x
2
7
490
Z
x
2
1
x
2
1
70
x
x
2
1
x
2
1
34
x
S


La variable entrante sera donc
2
x car elle possède le coefficient positif le plus élevé dans la
fonction économique.

Niveau à affecter à
2
x (tout en maintenant
,
0
x 3 
car elle reste hors base).





















2
2
1
2
5
2
4
6
x
2
1
490
Z
x
2
1
70
x
x
2
1
10
x
x
2
1
34
x
S

140
x
0
x
2
1
70
0
x
20
x
0
x
2
1
10
0
x
68
x
0
x
2
1
34
0
x
2
2
1
2
2
5
2
2
4






















20
68,20,140
Min
x2


; La plus grande valeur qu’on peut affecter à
2
x est la petite des
valeurs 

140
,
20
,
68
donc
20
x2 
.

Or

Equation d’échange

INT1801/SEMESTRE II RECHERCHE OPERATIONNELLE PROPRIETE CNFEPD 48

Détermination de la variable sortante :

























500
10
490
Z
60
20
2
1
70
x
0
20
2
1
10
x
24
20
2
1
34
x
S
1
5
4
7


La variable sortante est donc
5
x

Solution de la 2ème itération :










L’équation d’échange est celle qui fournit la variable sortante, c’est
2
3
5
x
2
1
x
2
5
10
x




On utilise cette équation pour exprimer
2
x en fonction des nouvelles variables hors base :

3
5
2
5x
2x
20
x





On substitue cette expression dans (S7) :




































3
5
3
3
5
3
1
3
5
3
4
3
5
2
5x
20
2x
2
1
x
2
7
490
Z
5x
20
2x
2
1
-
x
2
1
70
x
5x
20
2x
2
1
-
x
2
1
34
x
5x
20
2x
x























5
3
5
3
1
5
3
4
3
5
2
8
x
x
500
x
3x
60
x
x
2x
24
x
5x
20
2x
x
:
S



La fonction économique n’est plus composée que de coefficients négatifs. Il n’est donc plus
possible d’améliorer ni d’augmenter cette fonction économique. La solution précédente est
donc optimale.

500
24
x
20
x
60
x
B
0
x
,
0
x
HB
4
2
1
5
3








INT1801/SEMESTRE II RECHERCHE OPERATIONNELLE PROPRIETE CNFEPD 49


500
24
x
20
x
60
x
B
0
x
,
0
x
:
HB
4
2
1
5
3









2- Présentation pratique (Méthode du simplexe) :

Elle a le principe de la méthode précédente, mais a l’avantage d’organiser tous les systèmes
d’équations sous forme de tableaux.

2.1- Principe de la méthode :

1- Obtenir la forme canonique.

2- Obtenir la forme standard.

3- Tableau n° 0 : Recherche de la solution extrême de base :

Les variables d’écart sont considérées au départ comme variables principales ou variable dans
la base.

Les variables réelles sont non principales et se trouvent hors de la base. La fonction
économique est alors nulle. Avec le tableau N° 0, on prépare le tableau N° 1 en choisissant
respectivement la variable entrante, la variable sortante et le pivot :

- La variable entrante correspond au coefficient le plus élevé dans la fonction économique. La
colonne de la variable entrante prend alors le nom de colonne pivot.

- La variable sortante correspondra au plus petit rapport positif issu de la division de la
colonne second membre (les bi) par la colonne variable entrante. Cette variable sortante de
la base et sur la même ligne que le plus petit rapport positif. La ligne de la variable sortante
prend le nom de ligne pivot.

- Le pivot se trouvera à l’intersection de la ligne pivot et de la colonne pivot.

Il s’agira ensuite de rendre la colonne pivot unitaire : c’est à dire, arriver à un pivot égal à 1
et tous les autres éléments de la même colonne pivot égaux à zéro jusqu'à la fonction
économique (dernière ligne du tableau). Chaque itération s’arrête dés que la colonne pivot
est devenue totalement unitaire.

4- On construit les différents tableaux jusqu'à ce que la fonction économique ne contienne
plus que des nombres négatifs ou nulles ; cas où il n’est plus possible d’améliorer la fonction
économique.

Remarque :Le pivot ne peut jamais être égal à 0

INT1801/SEMESTRE II RECHERCHE OPERATIONNELLE PROPRIETE CNFEPD 50

Exemple : Résoudre par, la méthode du simplexe, le programme linéaire suivant :










Forme standard :









Tableau n° 0 :


Variable sortante
4
x



To
1
x
2
x
3
x
4
x b
Rapport
A
3
x 1
5
1
0
1
1
11/1
B
4
x
3
0
1
5

5 / 2
C
-Z
3
2
0
0
0


Variable entrante dans la base
1
x : elle a le plus grand coefficient.

La solution extrême de base est :






























Remarques :

1- L’ordre dans lequel on écrit la liste des variables de la base (x3, x4) est important.
2- À l’intersection de la colonne pivot (=1) et de la ligne pivot (=2)

Se trouve la valeur 2 entourée, il s’agit du pivot.

Tableau n°1 : 1ère itérationIl s’agit de transformer le tableau N° 0, en un tableau équivalent
(ce sera le tableau N° 1) de telle sorte que la colonne pivot devient unitaire :

1- Arriver à 1 pivot = 1, pour cela il suffit de diviser toute la ligne du pivot par 2 (valeur du
pivot).


2
1
2
1
2
1
2
1
2x
3x
Max
5

3x
2x

11

5x

x
0
x
0
x










4
3
2
1
4
2
1
3
2
1
4
3
2
1
0x
0x
2x
3x
Max
5

x
3x
2x
11
x
5x
x

0
x
0
x
0
x
0
x

















Hors base :
0
x
x
2
1



Base :
5
x
,
11
x
4
3



2
Variable sortante = x 4

INT1801/SEMESTRE II RECHERCHE OPERATIONNELLE PROPRIETE CNFEPD 51

2- Tous les autres éléments de la même colonne pivot égaux à zéro, pour cela il suffit de
trouver pour chaque cas la transformation nécessaire, en utilisant la ligne du pivot.

Pour notre exemple, trouvons les transformations nécessaires d’abord.

La ligne B devient
2
/
5
2
/
1
0
2
/
3
1
:
'
2
/
B
B
est
c




La ligne A :




2
17
2
1
1
2
7
0
A
11
0
1
5
1
A
2
5
1/2
0
2
3
1
B
1














La ligne C :




2
15
2
3
0
2
5
0
C
0
0
0

2
3
C
2
15
3/2
0
2
9
3
B
3

















On obtient alors le tableau N° 1 :


T1
1
x
2
x
3
x
4
x
b
A
3
x 0
2
7

1
2
1


2
17


B
1
x 1

0
2
1
2
5

C -Z
0
2
5

0
2
3


2
15



Solution optimale :

HB :
0
x
x
4
2



B :
2
17
x
,

2
5
x
3
1



Z =
2
15


2.3- Un autre exemple :Résoudre par la méthode du simplexe le programme suivant :












































2
3


Z
3x
2x
Max
3
4x
x
2
2x
x

0
x
0
x
2
1
2
1
2
1
2
1












INT1801/SEMESTRE II RECHERCHE OPERATIONNELLE PROPRIETE CNFEPD 52

Forme standard :








Tableau N° 0 :







Ligne pivot :
4
x
Variable sortante.








Colonne pivot :
2
x variable entrante










La solution extrême de base est :

HB :
0
x
0
,
0
x
2
1



B :
0
x
,
2
x
4
3



Z = 0

Tableau N° 1 : 1ère Itération





Ligne pivot :
3
x variable sortante







Colonne pivot :
1
x variable entrante





T0
1
x
2
x
3
x
4
x
b
rappor
t

A

3
x

1

2
1
0
2


B

4
x

1

0
1
3

4
3

C
-Z
2
3
0
0
0


T1
1
x
2
x

3
x

4
x
b
rapport

A

3
x

2
1
0
1

2
1
1
2
1
/
2
1


B
2
x


1
0



3
4
1
/
4
3



C -Z
4
5 0
0
4
3


4
9



2
2
2
1

4
1
4
1
4
3
Pivot
4



Variables réelles variables d’écart

Pivot

INT1801/SEMESTRE II RECHERCHE OPERATIONNELLE PROPRIETE CNFEPD 53

Explication : (Comment a-t-on obtenu T1)

B
1
4
0
1
3


4
B
B1

4
1
1
0
4
1
4
3




B

4
1
1
0
4
1
4
3

A

1
2
1
0
2





B
2
A
A

2
1
0
1
2
1


2
1





C’est l’opération nécessaire pour obtenir la valeur 0 sur la colonne pivot




B

4
1
1
0
4
1
4
3

C

2
3
0
0
0





B
3
C
C

4
5
0
0
4
3


4
9





C’est l’opération nécessaire pour obtenir la valeur 0 sur la colonne pivot.

La solution est :














Tableau N° 2 : 2ème Itération






Ligne pivot : x2 : variable sortante




Colonne
pivot :
4
x variable entrante




HB :
0
x
x
4
1



B :
4
3
x
,
2
1
x
2
3



Z =
4
9


T2
X1
X2 X3
X4
b
rapport
A

X1
1
0
2
-1
1
Rapport
négatif

B

X2
0
1
2
1


2
1
2
1
1
2
1
/
2
1


C

-Z
0
0
2
5


2
1
4
14
