1.

Objectifs du cours: Le cours de recherche opérationnelle vise principalement

l'initiation des étudiants à acquérir une connaissance des méthodes susceptibles
d'aider, de façon opérationnelle, à la prise de décision dans divers contextes en
économie, en finance et en gestion.
Au terme de ce cours, l'étudiant(e) devra pouvoir :
- reconnaître la structure (courante) des problèmes qui pourraient se formuler
sous forme de programmes linéaires;
- résoudre ces problèmes, interpréter les principaux résultats;
- reconnaître les implications pour la prise de décision.

2. Contenu du cours

Chapitre.1 Les rappels; l’introduction, la définition et l’objectif de la

recherche opérationnelle
I) Les rappels: les systèmes d’inéquations linéaires et l’algèbre linéaire
1) les systèmes d’inéquations linéaires.
2) l’algèbre linéaire:
A) les matrices,
a) la définition,
b) les opérations sur les matrices,
c) les matrices particulières,
d) le pivot de Gauss.
B) Les systèmes d’équations linéaires,
a) définition,
b) écriture matricielle des systèmes d’équations linéaires.
II) Introduction, définition et objectif de la recherche opérationnelle.
Chapitre 2: la programmation linéaire
I) Définition et exemples,
II) Formulation mathématique ou modèle mathématique des programmes
linéaires,
III) Résolution des programmes linéaires
A) la méthode graphique,
B) la méthode algébrique ou méthode du simplexe,
C) complément sur l’algorithme du simplexe: la méthode en deux phases,
IV) la dualité des programmes linéaires,
V) le dual du simplexe.

Chapitre3. Le problème de transport

I) Introduction,
II) le problème classique de transport,
1) le modèle mathématique du problème de transport,
2) la détermination de la solution initiale ou plan initial ou solution basique d’un
problème de transport,
a) la méthode du coin nord-ouest,
b) la méthode de l’élément minimal.
3) la résolution d’un problème de transport

3. Bibliographie
1) Yves Nobert, Roch Ouellet, Régis Parent, la recherche opérationnelle 3 ème
édition, Guëtan Morin, éditeur.
2) GRACEM, mathématiques appliquées à la gestion, seconde édition tome 1.
3) Robert Faure, Bernard Lemaire, Christophe Picouleau, précis de recherche
opérationnelle (méthodes et exercices d’application), 5ème édition, Dunod, Paris
2000.
4) J.F. Phélizon, méthodes et modèles de la recherche opérationnelle,
Economica, 1998.
5) [Link]: solveur,
6) [Link]

PROGRAMME
Chapitre I : Rappel d’algèbre linéaire, introduction et définition
Chapitre II : La programmation linéaire
I. Définition et exemple
II. Formulation mathématique ou modèle mathématique des programmes
linéaires
III. Résolution des programmes linéaires
 A) La méthode graphique
B) La méthode algébrique : méthode de simplexe
C) Complément sur l’algorithme du simplexe :
a) la méthode en deux phases
b)la méthode du grand «M» ou méthode des pénalités
IV. La dualité des programmes linéaires
V. Le dual du simplexe
VI. L’analyse post-optimale
Chapitre III : Le problème de transport
I. Introduction
II. le problème classique de transport
Chapitre IV : Les problèmes d’ordonnancement
Bibliographie
1) Yves Nobert, Roch Ouellet, Régis Parent, la recherche opérationnelle 3 ème
édition, Guëtan Morin, éditeur
2) GRACEM mathématiques appliquées à la gestion, seconde édition tome
1
3) [Link] : solveur
Chapitre I : Rappel d’algèbre linéaire, introduction et définition
I. Rappel d’algèbre linéaire : (voir les cahiers de la 2ème année)
II. Introduction et définition :
La modélisation et la résolution des problèmes de gestion à l’aide des méthodes
quantitatives et statistiques appuyé d’un support informatique sont utilisés dans
le milieu industriel, dans les institutions bancaires et organismes financiers, dans
les domaines hospitaliers, dans les sociétés d’assurance etc.
Les problèmes sont nombreux et variés et font souvent appel à divers techniques
qui relèvent d’un domaine qui a pris son essor au cours de la 2 ème guerre
mondiale pour résoudre divers problèmes de nature militaire et qui a été identifié
<< Recherche Opérationnelle>> ou RO, en anglais <<Operational research>>.
La RO est l’ensemble des techniques rationnelles d’analyse et de résolution de
problèmes concernant notamment l’activité économique et visant à élaborer les
décisions les plus efficaces pour aboutir au meilleur résultat. Elle permet de
déterminer une meilleure organisation des systèmes <<homme-machines>>
sous contrainte des ressources limités. Elle a pour but d’aider le gestionnaire à
déterminer ses politiques et ses gestions scientifiquement.
Dans la plupart des cas, les techniques utilisées sont : la programmation
linéaire, les problèmes de transport et d’affectation, les problèmes
d’ordonnancement, la gestion des stocks etc… qui font appel à des méthodes
mathématiques.
Les demandes d’application sont multiples et variées par exemple en économie,
en gestion, en stratégie politique et militaire.
Chapitre II : La programmation linéaire
I. Définition et exemple :
a) Définition : Parmi les techniques et modèles mathématiques utilisés en
RO, la programmation linéaire occupe une place prépondérante. Cette
méthode mathématique consiste à trouver la solution d’un problème
ramené à la recherche de l’optimum (maximum ou minimum) d’une
fonction linéaire des plusieurs variables (dite fonction économique)
liée par une série de contrainte elle-même estimée sous forme
d’équation ou d’inéquation linéaires.
b) Exemples :
1) Un problème de production : il s’agit de déterminer le plan
optimal de production ou de fabrication.
 Une entreprise fabrique plusieurs produits, ce qui exige des
ressources particulières (matière première, machine, personnel) en
quantité limitée. Chaque produit rapporte un certain bénéfice connu
à l’entreprise. Quelles produits l’entreprise doit-elle fabriquer et
quelle quantité pour réaliser le bénéfice total le plus élevé ?
2) Un problème de transport : une entreprise dispose de plusieurs
dépôts contenant chacun un certain nombre de containers.
Différents magasins commande des containers. On connait le
coût de transport de chaque dépôt au magasin. Quelle est
l’organisation de livraison des containers pour minimiser le coût
total de transport ?
3) Un problème d’affectation : tâches doivent être affecté à
machines (une tâche par machine). Le coût d’exécution de chaque
tâche par chacune des machines est connu. Quelle est l’affectation
qui minimise le coût total.
II. Formulation mathématique ou modèle mathématique des
programmes linéaires :
Il s’agit de réaliser une transformation mathématique d’un problème d’ordre
économique technique ou financier.
Dans la plupart des exercices de programmation linéaire, la difficulté est de
mettre en équation le problème posé.
Il s’agit dans tous les cas de bien lire et d’analyser l’énoncé pour trouver :
1) Les variables de décision ou variables d’action ou variables d’activité
ou variables structurelles : ces variables désignent les quantités sur
lesquelles il faut agir, elles correspondent aux nombres ou quantités de
biens produits ou fabriqués (le nombre de biens produits ou de pièces
fabriquées, les nombres de messages diffusés par les différents types de
médias, le volume d’investissement dans les différents types
d’investissement par exemple les titres : action et obligation).
On les désigne généralement par
2) La fonction économique : elle est liée au bénéfice unitaire et au coût
unitaire de fabrication ou de production, ou au prix unitaire de vente des
produits ou pièces.
En économie :
Pour trouver la fonction économique on multiplie les bénéfices unitaires
ou coûts unitaires aux prix de vente unitaire par les variables de décisions
correspondantes et on les additionne.
 La fonction économique est une fonction à maximiser ou à minimiser. On
a un problème de maximisation lorsqu’il s’agit de gagner c’est-à-dire
avoir un gain ou un revenu. On a un problème de minimisation lorsqu’il
s’agit de dépenser c’est-à-dire on a une dépense ou une perte.
3) Les contraintes : il y a deux (2) types de contraintes : les contraintes à
caractère économique et les contraintes de signes.
a. Les contraintes à caractère économique : ce sont les contraintes
structurelles ou fonctionnelles et doivent-être conformes à la lettre et à
l’esprit du problème. Elles sont liées aux ressources ou matières
premières (c’est-à-dire comment elles ont été utilisées) et aux
conditions de production ou de fabrication. A chaque ressource ou
matière première doit correspondre une contrainte à caractère
économique.
Pour construire une contrainte liée aux ressources on doit traduire
mathématiquement l’utilisation d’une ressource pour la fabrication ou
production des différents biens.
b. Les contraintes de signes : c’est la non négativité des variables de
décision c’est-à-dire qu’elles sont supérieures ou égales à zéro ).
On les appelle encore les contraintes naturelles.
Ainsi un problème de programmation linéaire comprend : une fonction
économique ou fonction objective et un système de contraintes (un système
d’équation ou d’inéquation linéaire).
NB : dans un problème de maximisation toutes les contraintes liées aux
ressources sont du genre inférieurs ou égales . Et dans un problème de
minimisation elles sont du genre supérieures ou égales .
Exemples
III. Résolution des programmes linéaires :
Il y a la méthode graphique et la méthode algébrique ou méthode du simplexe.
A. La méthode graphique :
NB : elle est valable uniquement pour les problèmes où il y a deux variables.
L’algorithme de la méthode : méthode du gradient
1er pas: construire le domaine des solutions admissibles (c’est-à-dire
résoudre le système d’inéquations) noté D.
Si D est vide (tout est hachuré ou barré), alors le problème n’a pas de
solution.
Si le domaine D n’est pas vide, alors
2ème pas : construire le vecteur normal ou vecteur gradient noté .
Il a pour coordonnées les coefficients des variables dans la fonction
économique: .

3ème pas : tracer la ligne de niveau. Elle a pour équation :

Dans la pratique c’est une droite qui est perpendiculaire au vecteur normal.
Remarque : toutes les lignes de niveau sont parallèles les unes aux autres.
4ème pas : faire déplacer parallèlement à elle-même la ligne de niveau dans la
direction du vecteur normal.
Dans un problème de minimisation le ou (les) premier point d’intersection de
la ligne de niveau avec le domaine D sera le minimum. S’il n y a pas de
premier point, alors on dit que le problème n’a pas de solution et en ce
moment .
Dans un problème de maximisation le ou (les) dernier point d’intersection de
la ligne de niveau avec le domaine D sera le maximum. S’il n y a pas de
dernier point, alors on dit que le problème n’a pas de solution et en ce
moment .
Remarque: s’il y a deux solutions , alors la solution générale s’écrit
de la manière suivante :
B. La méthode algébrique ou méthode du simplexe ou méthode de G. B
Dantgiz
Cette méthode encore appelée méthode des tableaux est une méthode
itérative qui permet d’améliorer la solution d’un problème à un autre.
L’ensemble des solutions est un polygone convexe appelé simplexe.
L’algorithme de la méthode du simplexe:
1er pas: écrire le problème sous la forme standard (la forme initiale est
appelée forme canonique) c’est-à-dire transformer toutes les inégalités des
contraintes à caractère économique en des égalités en ajoutant si on a et
en retranchant si on a une nouvelle variable non négative appelée
variable d’écart. Economiquement ce sont des produits fictifs.
Dans une contrainte, on doit avoir obligatoirement une et une seule variable
d’écart et les variables d’écart doivent être distinctes.
2ème pas : choisir les variables de base notées VB et les variables hors base
notées VHB.
Généralement les variables de base correspondent aux variables d’écart, elles
doivent avoir comme coefficient l’unité et à chaque contrainte doit
correspondre une variable de base.
3ème pas : trouver la solution initiale ou solution de base. Pour cela, on annule
les variables hors base. Economiquement elle correspond à ne rien faire.
4ème pas : vérifier si la solution est optimale.

Pour cela on doit construire un tableau appelé de simplexe :

. .
. .

- correspond aux numéros des variables de base,

- correspond aux coefficients des variables de base dans la
fonction économique,
- correspond aux coefficients des variables dans la fonction
économique,
- correspond aux différents variables c’est-à-
dire : ,
- correspond aux termes constants c’est à dire les seconds
membres des contraintes.
On calcule qui est le produit scalaire de est le coût
d’opportunité pour produire x j unités du bien j.

Enfin on calcule appelé le coût marginal

Considérons d’abord les problèmes de maximisation:
- si tous les sont supérieurs ou égales à zéro (0), alors la solution est
optimale.
- si au moins il existe un négatif, alors la solution n’est pas optimale et on
doit continuer.
5ème pas : trouver la nouvelle solution. Pour ce faire on choisit la colonne où
il y a le plus petit négatif (s’il y a deux ou trois voir plus, on choisit un au
hasard). Cette colonne correspond à la colonne de pivot ou colonne
dirigeante ou directrice. Elle correspond à la variable entrante. Dans le
tableau elle est indiquée à l’aide d’une flèche verticale. Cette variable doit
entrer dans la base à la place d’une autre variable appelée variable sortante
qui correspond à la ligne de pivot. Dans le tableau elle est indiquée à l’aide
d’une flèche horizontale. Pour trouver la variable sortante, on divise les
par les éléments correspondant de la colonne de pivot et on choisit le plus
petit résultat c’est à dire:

les X N(s )
min  
les éléments correspondants de la colonne de Pivot
Remarque : ici, on ne tient pas compte du résultat de la division par un
nombre négatif et par zéro (0).

 240 400 600 0  0

Exemple : min  ; ; ;  .
 2 0  10 20  20
L’élément qui se trouve sur l’intersection de la ligne et de la colonne de pivot
est appelé l’élément de pivot.
Enfin pour trouver la nouvelle solution, on fait le pivotage autour de
l’élément de pivot de la manière suivante:
- diviser tous les éléments de la ligne de pivot par l’élément de pivot,
- fixer cette ligne et écrire toutes les autres lignes en fonction de celle-
là(c’est-à-dire annuler tous les autres éléments de la colonne ou encore
éliminer la variable entrante dans toutes les autres lignes) . Enfin on trouve
ainsi un nouveau problème avec une nouvelle solution et on revient au 4ème
pas.
Remarque
- Une solution réalisable est une solution qui vérifie toutes les contraintes
naturelles.
- Une solution admissible est une solution qui vérifie toutes les contraintes.
- est une variable décisionnelle entrante et est une variable
décisionnelle sortante : l’entreprise produira les biens de types et
abandonnera la production des biens de types .
- est une variable décisionnelle entrante et est une variable d’écart
sortante : l’entreprise produira les biens de types et épuisera les
ressources de types .
- est une variable d’écart entrante et est une variable décisionnelle
sortante : l’entreprise évitera d’épuiser les ressources de types et
abandonnera la production des biens de types
est une variable d’écart entrante et est une variable d’écart sortante :
l’entreprise évitera d’épuiser les ressources de types et les ressources de
type .

L’interprétation économique des différentes variables du problème:

a- Les variables de décision :
Les variables de décision désignent les quantités ou les nombres de biens
produits ou fabriqués.
b- Les variables d’écart :
Les variables d’écart désignent les quantités de ressources inutilisées ou les
volumes d’heures inutilisées.
Les différentes observations ou questions possibles(à connaître
obligatoirement):
1) Qu’est-ce que c’est qu’une ressource excédentaire ?
- Une ressource est dite excédentaire, si la variable d’écart associée à la
contrainte est différente de zéro dans le tableau optimal ou dernier
tableau. S’il s’agit des volumes d’heures, alors on parle de sous-emploi.
2) Qu’est-ce que c’est qu’une ressource déficitaire ?
- Une ressource est dite déficitaire lorsque la variable d’écart associée à la
contrainte est égale à zéro dans le dernier tableau ou tableau optimal. S’il
s’agit des volumes d’heures, alors on parle de pleine capacité.
Remarque: si on a utilisé la méthode graphique, alors pour répondre à ces
questions, il suffit de remplacer les par leur valeur dans les contraintes. Si
on a l’égalité, alors on dit que la contrainte est saturée et la ressource est
déficitaire et dans le cas contraire la contrainte n’est pas saturée et la
ressource est excédentaire.
3) L’entreprise a-t-elle une autre alternative ?
Cette question veut dire tout simplement si la solution est unique ou pas.
- La solution est unique (pas d’alternative) si tous les des variables hors
base (VHB) dans le dernier tableau ou tableau optimal sont différents de
zéro .
- Si au moins l’un des des VHB est nul dans le dernier tableau, alors la
solution n’est pas unique (il existe une autre alternative).
Pour trouver la nouvelle solution (une autre solution), on introduit la VHB
dont le dans la base.
4) Quelles sont les ressources qu’il faut prioritairement apporter ?
Ce sont les ressources déficitaires c’est-à-dire épuisées.
- Une ressource est déficitaire (la contrainte correspondante est saturée) si
la variable d’écart si la variable d’écart correspondante est nulle dans le
dernier tableau.
- Une ressource excédentaire (la contrainte correspondante n’est pas
saturée) est une ressource dont la variable d’écart correspondante n’est
nulle dans le dernier tableau. La valeur de la variable d’écart est quantité
de ressources restante.
Remarque : lorsqu’il s’agit des volumes d’heures à exécuter, on parle de
pleine capacité et de sous-emploi.
Si dans le tableau optimal une variable de base est nulle, alors on dit que le
problème admet une multitude de bases optimales avec unicité dans la
solution optimale. Dans ce cas la conséquence de cette particularité est que le
problème dual aura une infinité de solutions optimales.
5) Quelle la base optimale ?
La base optimale ou est l’ensemble des variables de base dans le
tableau optimal.
6) Quelles sont les matrices et son inverse :
- la matrice est une matrice carrée qui se trouve toujours sous les
colonnes respectives des variables de base dans le tableau (s) mais lit dans le
tableau initial ou premier tableau. Autrement dit pour écrire la matrice
on prend les variables de base du dernier tableau et leurs coefficients
 correspondants dans le premier tableau. Exemple: si x1 est une variable de
base du dernier tableau, alors on écrit les éléments de la colonne A1 dans le
premier tableau.
la matrice est l’inverse de la matrice et se trouve toujours sous
les colonnes respectives des variables de base de départ mais lit dans le
tableau(s) optimal du simplexe. Autrement dit pour écrire la matrice
on prend les variables de base du premier tableau et leurs coefficients
correspondants dans le dernier tableau ou tableau optimal. Exemple: si x3 est
une variable de base du premier tableau, alors on écrit les éléments de la
colonne A3 dans le dernier tableau.
Remarque à l’itération (s) on a:

-  
A(j s )  BN( s )
1 1
Aj ,

- X N( s )  B 
( s ) 1 1
N XN
Oû (s) est le numéro du tableau et 1 veut dire le premier tableau.

Exemple : l’exercice 2 de la fiche d’exercices: problème de Pyrofour

F ( x)  1500 x1  1800 x2  max

5 x1  3x2  270,
7 x  8 x  800,
 1 2

4 x1  6 x2  360,
 x1  0, x2  0.

La forme standard: on ajoute partout une nouvelle variable car on a  .

5 x1  3 x2  x3  270,
7 x  8 x  x  800,
 1 2 4

4 x1  6 x2  x5  360,
 x j  0, j  1,...,5 ou 1  j  5.

Choix des variables: VB: x3 , x4 , x5 ; VHB: x1 , x2 .

Solution initiale:
X 0  x1  0, x2  0, x3  270, x4  800, x5  360 ; F ( X 0 )  0 .
Vérification si la solution est optimale tableau de simplexe
Premier tableau du simplexe:

N (s ) cj 1500 1800 0 0 0 X N(s )

C N(s ) A1 A2 A3 A4 A5

3 0 5 3 1 0 0 270
4 0 7 8 0 1 0 800
5 0 4 6 0 0 1 360

Z j  C N( s ) A j 0 0 0 0 0 0

 j  Z j Cj -1500 -1800 0 0 0

La solution n’est pas optimale car il y a des j

négatifs( 1  1500  0,  2  1800  0 ).
Recherche de la nouvelle solution: On choisit la colonne oû il y a le plus
petit  j négatif(ici c’est  2  1800 ) . Elle est la colonne de Pivot et elle
correspond à la variable entrante dans le tableau suivant. Il s’agit de la
variable x2 dont on indique dans le tableau à l’aide d’une flèche verticale.
Pour savoir la variable sortante on calcule l’expression:
 270 800 360  360
min  , ,  . D’ oû la variable sortante est x5 . Elle
 3 8 6  6
correspond à la ligne de Pivot et on l’indique dans le tableau à l’aide d’une
flèche horizontale. L’élément situé sur l’intersection de la ligne et de la
 colonne de Pivot est appelé l’élément de Pivot. Ici c’est 6 dont on encadre
dans le tableau. En fin pour faire entrer la variable x2 à la place de x5 nous
allons faire le pivotage autour de l’élément de Pivot de la manière suivante:
- diviser tous les éléments de la ligne de pivot par l’élément de pivot c’est-à-
dire par 6 pour avoir 1,
- fixer cette ligne et écrire toutes les autres lignes en fonction de celle-là(c’est-à-
dire annuler tous les autres éléments de la colonne ) c’est-à-dire transformer 3 en
0 pour la première ligne et 8 en 0 pour la deuxième ligne. On appelle les lignes
du premier tableau par L1 , L2 , L3

Deuxième tableau du simplexe:

L3
Les transformations: L3  , L1  L1  3L3 , L2  L2  8L3 .
6

N (s ) cj 1500 1800 0 0 0 X N(s )

C N(s ) A1 A2 A3 A4 A5

3 0 3 0 1 0 1 90

2
4 0 5 0 0 1 4 320

3 3
2 1800 2 1 0 0 1 60
3 6
Z j  C N( s ) A j 1200 1800 0 0 300 108
000
 j  Z j Cj -300 0 0 0 300

La solution n’est pas optimale car il y a un  j négatif( 1  300  0 ). Ici il

y a un seul  j négatif d’oû la variable entrante est x1 (la première colonne est la
colonne de Pivot). Pour trouver la variable sortante on a:
 
 90 320 60  90
min  , ,   , d’oû la première ligne est la ligne de Pivot et la
 3 5 2
 3
3 3
variable sortante est x3 .

Troisième tableau du simplexe:

L1 5 2
Les transformations: L1  , L2  L2  L1 , L3  L3  L1 .
3 3 3

N (s ) cj 1500 1800 0 0 0 X N(s )

C N(s ) A1 A2 A3 A4 A5

1 1500 1 0 1 0 1 30

3 6
4 0 0 0 5 1 19 270
 
9 18
2 1800 0 1 2 0 5 40

9 18
Z j  C N( s ) A j 1500 1800 100 0 250 117
000
 j  Z j Cj 0 0 100 0 250

La solution est optimale car tous les  j sont positifs u nuls c’est-à-dire  0 .

Pour trouver la solution d’un tableau: les valeurs des variables de base sont
(s )
les valeurs des X N dans le tableau et toutes les variables hors base sont nulles:
      
La solution optimale est: x  ( x1 , x2 , x3 , x4 , x4 )  (30, 40, 0, 270, 0) et
F ( x)  117 000 . Remarque: le problème initial dépendait de deux variables
d’oû la solution optimale réelle est: x  ( x1 , x2 )  (30, 40) et
F ( x)  117 000 .
Les réponses aux questions possibles
1) L’interprétation économique des variables
Il y a deux types de variables: les variables de décision et les variables d’écart.
a) les variables de décision(les variables de décision désignent les quantités

ou les nombres de biens produits ou fabriqués). Ici elles sont: x1  30 le

nombre de fours de type F1 fabriqués et x2  40 le nombre de fours de type
F2 fabriqués.
b) les variables d’écart(les variables d’écart désignent les quantités de
ressources inutilisées ou les volumes d’heures inutilisées). Ici elles sont:
x3  0 le nombre d’heures inutilisées par les machines, x4  270 le nombre

d’heures inutilisées par les ouvriers, x5  0 le nombre d’heures inutilisées par
les techniciens.
2) La base optimale: ce sont les variables de base du dernier tableau ou tableau
 x1 
  
optimal: ici Bopt ou BN   x4  .
x 
 2
3) La solution unique(il n’y a pas d’alternative): La solution est unique (pas
d’alternative) si tous les des variables hors base (VHB) dans le dernier tableau
ou tableau optimal sont différents de zéro. Ici la solution est unique car tous les
 j des variables hors base dans le dernier tableau sont différents de
0 ( 3  100  0,  5  250  0) , d’où la société Pyrofour n’a pas une autre
alternative ou possibilité. Son plan de production ou de fabrication est unique
c’est-à-dire 30 fours de type F1 et 40 fours de type F2.

4) La matrice BN
(s )
 
et son inverse BN
( s ) 1
.
 (s )
a) La matrice BN : les variables de base du dernier tableau étant
x1 , x4 et x2 , d’où pour écrire la matrice BN(s ) on prend la 1ère
colonne(correspondant à x1 ), la 4ème colonne(correspondant à x4 ) et la 2ème
colonne(correspondant à x2 ) du premier tableau de simplexe.

 5 0 3
 
Ainsi BN
(s )
 7 1 8 .
 4 0 6
 

b) La matrice BN  
( s ) 1
: les variables de base du premier tableau étant

 
x3 , x4 et x5 , d’où pour écrire la matrice BN( s ) on prend la 3ème
1

colonne(correspondant à x3 ), la 4ème colonne(correspondant à x4 ) et la 5ème

colonne(correspondant à x5 ) du dernier tableau ou tableau optimal de simplexe.
 1 1
 0  
 3 6
Ainsi BN  (s ) 1
 
 9
5 19
1  .
18 
 2 5 
  0 
 9 18 

NB: En multipliant BN
(s )
par B 
( s ) 1
N on trouve la matrice unité c’est-à-dire
1 0 0
 
BN( s )   
BN( s )
1
  0 1 0 .
0 0 1
 
Remarque: On peut aussi trouver ces deux matrices en considérant le premier et
le deuxième tableau(en ce moment le deuxième tableau joue le rôle de dernier
tableau): Par exemple ici les variables de base du deuxième tableau étant
x3 , x4 et x2 , d’où pour écrire la matrice BN(s ) on prend la 3ère
colonne(correspondant à x3 ), la 4ème colonne(correspondant à x4 ) et la 2ème
colonne(correspondant à x2 ) du premier tableau de simplexe.
 1 0 3
 
Ainsi BN
(s )
 0 1 8 .
0 0 6
 
Les variables de base du premier tableau étant x3 , x4 et x5 , d’où pour écrire la

matrice B  ( s ) 1
N on prend la 3ème colonne(correspondant à x3 ), la 4ème
colonne(correspondant à x4 ) et la 5ème colonne(correspondant à x5 ) du
deuxième tableau de simplexe.

 1
1 0  
 2
 
Ainsi BN
(s ) 1


4
 0 1  
3
 1 
0 0 
 6 
Remarque: A l’itération (s) on a:

-  
A(j s )  BN( s )
1
A(j1) ,

- X N( s )  B ( s ) 1 (1)
N XN .
Oû (s) est le numéro du tableau et (1) veut dire le premier tableau.
Exemple: a) pour trouver les éléments de la première colonne du
 1
1 0  
 2
deuxième tableau on multiplie la matrice BN  
(s ) 1


4
  0 1   par
3
 1 
 0 0 
 6 
 les éléments de la première colonne du premier tableau c’est-à-dire
 1
1 0  
 2  5
 
0 1  4   7 .
 3  
 1   4
0 0 
 6 
(s )
b) Pour trouver les X N du deuxième tableau on multiplie la matrice
 1
1 0  
 2
  1 4
BN(s )   0 1   par les X N(s ) du premier tableau c’est-à-dire
 3
 1 
 0 0 
 6 
 1
1 0  
 2   270 
 
 0 1  4    800  .
 3  
 1   360 
0 0 
 6 
NB: Si on a besoin des éléments du dernier tableau ou tableau optimal on
prend la matrice BN  ( s ) 1
de ce tableau(tableau optimal) pour faire la
multiplication avec les éléments correspondants du premier tableau.
5) L’indication des ateliers qui ont travaillé en plein capacité(ou les
ressources qu’il faut prioritairement apporter)
 
La première contrainte est saturée car x3  0 ( x3 est la variable d’écart liée à
la contrainte ), d’oû les machines ont travaillé en pleine capacité. La deuxième
 
contrainte n’est pas saturée car x4  270 ( x4 est la variable d’écart liée à la
contrainte ) d’oû les ouvriers n’ont pas travaillé en pleine capacité(il les reste
270 heures). On dit qu’il y a sous-emploi. La troisième contrainte est saturée car
x5  0 ( x5 est la variable d’écart liée à la contrainte ), d’oû les techniciens ont
travaillé en pleine capacité. Lorsqu’il s’agit des ressources on dit que la
ressource a été épuisée(ressource déficitaire qu’il faut prioritairement apporter)
ou la ressource n’a pas été épuisée(ressource excédentaire). Ici les ateliers qui
ont travaillé en pleine capacité sont les ateliers des machines et les techniciens.
IV) La dualité des programmes linéaires
NB: à chaque problème de programmation linéaire correspond un autre
problème appelé son problème dual ou tout simplement son dual. Le premier
problème est appelé le primal.
1) L’algorithme de la construction du dual:
1er pas: Préparer les contraintes à caractère économique de la manière suivante:
- si le primal est un problème de maximisation, alors toutes les contraintes à
caractère économique doivent être du genre  (toutes les contraintes du genre
 doivent être multipliées par -1),
- si le primal est un problème de minimisation, alors toutes les contraintes à
caractère économique doivent être du genre  (toutes les contraintes du genre
 doivent être multipliées par -1),
2ème pas: Identifier ou sélectionner les variables du dual(elles doivent être
différentes de celles du primal c’est-à-dire prendre une autre variable par
exemple si on avait les x au primal, prendre les y au dual). A chaque
contrainte à caractère économique du primal doit correspondre à une variable du
dual.

3ème pas: Construire la fonction économique du dual. Pour cela on multiplie et

on les additionne les termes constants des contraintes du primal par les variables
correspondantes du dual. Si le primal est un problème maximisation, alors son
dual sera un problème de minimisation et vice versa.
4ème pas: Construire les contraintes du dual. La matrice des contraintes du dual
est la transposée de la matrice des contraintes du primal. Par exemple si le
primal est de la forme F ( x)  Cx  max s / c Ax  b , alors le dual sera
F ( y)  by  min s / c At y  C . Ainsi les coefficients des variables dans la
fonction économique du primal deviennent les termes constants du second
membre du dual. Si le dual est un problème de maximisation, alors toutes les
contraintes doivent être du genre  . Si le dual est un problème de
minimisation, alors toutes les contraintes doivent être du genre  .
NB: la variable du dual correspondant à la contrainte d’égalité du primal n’a pas
de contrainte de signe.
Le tableau de construction du dual:
Primal Dual
Maximisation Minimisation
Matrice des contraintes(m, n) Transposée de la matrice des
contraintes(m, n)
Seconds membres des contraintes Coefficients de la fonction
économique
Coefficients de la fonction Seconds membres des contraintes
économique
Nombre de contraintes Nombre de variables
ième contrainte de type  ième variable de type  0

ième contrainte de type  ième variable de type  0

ième contrainte de type  ième variable quelconque(  )
jème variable de type  0 jème contrainte de type 
jème variable de type  0 jème contrainte de type 
jème variable de type quelconque jème contrainte de type 
(  )
Exemple 1.
1
F ( x)  x1  x2  max
2
 x1  x2  3,
 x  x  1
 1 2

 x1  2
 x1  0, x2  0.

Solution on a le feu vert car on a un problème de maximisation et toutes les

contraintes sont du genre  .
 x1  x2  3, y1
 x  x  1 y
 1 2 2

 x1  2 y3
 x1  0, x2  0.

Dual: F ( y )  3 y1  y2  2 y3  min

 1
y
 1  y 2  y3  ,
2

 y1  y2  1,
 y  0, y  0, y  0.
 1 2 3

Exemple 2.
F ( x)   x1  x2  min

2 x1  x2  2,
 x  2 x  2
 1 2

 x1  x2  5
 x1  0, x2  0.

Solution:
Première manière: on a pas le feu vert car on a un problème de minimisation et
toutes les contraintes ne sont pas du genre  . On va multiplier la 3ème contrainte
par -1.

2 x1  x2  2, 2 x1  x2  2, y1
 x  2 x  2  x  2 x  2 y
 1  1

2
 
2 2

 1 2x  x   5  x1  x2  5 y3
 x1  0, x2  0.  x1  0, x2  0.

Dual: F ( y )  2 y1  2 y2  5 y3  max
2 y1  y2  y3  1,

 y1  2 y2  y3  1,
 y  0, y  0, y  0.
 1 2 3

Deuxième manière: on a pas besoin de multiplier la 3ème contrainte par -1.

F ( y )  2 y1  2 y2  5 y3  max

2 y1  y2  y3  1,

 y1  2 y2  y3  1,
 y  0, y  0, y  0.
 1 2 3

Exemple 3.
F ( x)  2 x1  x2  max

 x1  2 x2  2,
x  x  6
 1 2

 x2  5
 x1  , x2  .

Solution:

 x1  2 x2  2, y1
x  x  6
 1 2 y2

 x2  5 y3
 x1  , x2  .
Dual

F ( y )  2 y1  6 y2  5 y3  min

 y1  y2  2,

 2 y1  y2  y3  1,
 y  0, y  , y  .
 1 2 3

2) Les théorèmes de la dualité

Théorème 1. Le dual du dual(le bidual) est le primal c’est-à-dire c’est le
problème lui-même.
Théorème 2. Soit un couple de programmations linéaires duaux:
n
F ( x)   C j x j  max
F ( x)  Cx  max j 1

(I)  Ax  b, ou n
   aij x j  bi , i  1,..., m
 x  0.  j 1
 x  0, j  1,..., n.
 j

m
F ( y )   bi yi  min
F ( y )  by  min i 1
(II)  A y  C ,
t
ou m
  aij yi  C j , j  1,..., n
 y  0.  i 1
 y  0, i  1,..., m.
 i
Théorème: le théorème fondamental de la dualité
Si l’un des problèmes (I) ou (II) admet une solution optimale, alors l’autre
 
problème admet aussi une solution optimale et on a F ( x )  F ( y ) .
Si l’un des problèmes (I) ou (II) n’admet pas de solution optimale, alors l’autre
problème aussi n’admet pas de solution optimale.
Théorème 3. Le théorème des écarts complémentaires
 
Si x et y sont respectivement les solutions optimales de (I) et (II), alors les
égalités suivantes sont vérifiées:

 n 
( Ax  b) y  0 ou   aij xj  bi  yi  0 et
 
 
 j 1 
m 
( A y  C ) x  0 ou   aij yi  C j  xj  0 .
t  

 i 1 
3) L’interprétation économique du problème dual
Le problème dual est un problème alternatif à la production c’est-à-dire au lieu
de produire l’entreprise décide de vendre ses ressources à une autre entreprise
concurrente. L’entreprise concurrente cherche donc le prix yi d’une unité de
m
ressource i qu’elle est prête à payer pour que son prix total d’achat  bi yi soit
i 1
minimal. Les variables du dual yi sont donc les prix de vente des différentes

ressources. La valeur optimale duale yi est appelée la valeur marginale de la
ressource i .
Remarque:

- Si yi  yi , alors on peut dans l’hypothèse de poursuite de la production
acheter des unités supplémentaires de la i ème ressource (c’est à dire c’est
intéressant d’acheter des unités supplémentaires et dans certains cas
d’embaucher des travailleurs supplémentaires). En d’autre terme le prix de la
ressource a baissé.

- Si yi  yi , alors on peut céder des unités supplémentaires de la i ème
ressource c’est-à-dire on peut vendre (dans ce cas il n’est pas intéressant
d’acheter des unités supplémentaires et dans certains cas d’embaucher des
travailleurs supplémentaires).
4) Lecture des valeurs optimales du primal ou du dual dans le tableau
optimal du simplexe:
A partir du tableau optimal de l’un ou l’autre des problèmes, on peut obtenir la
solution optimale de l’autre. Pour cela on fait une correspondance entre les
variables de décision et les variables d’écart du primal et du dual c’est-à-dire les
variables de décision du primal doivent correspondre aux variables d’écart du
dual et vice-versa.
Primal Variables de décision Variables d’écart
…………….. …………………
Dual Variables d’écart Variables de décision
………………. …………………..
Une fois le lien établi on associe à chacune de ces variables les valeurs
correspondantes au signe près de la ligne  j dans un problème de maximisation
et la valeur absolue de  j dans un problème de minimisation.

Exemple: le problème de pyrofour

1) Construire son problème dual,
2) trouver la solution de son problème dual à l’aide du théorème des écarts
complémentaires,
3) trouver la solution de son problème dual à l’aide du dernier tableau ou tableau
optimal du simplexe du primal.
4) est-il intéressant d’acheter des heures supplémentaires des machines au coût
horaire de:
a) 80 F ?
b) 150 F ?
Solution
1) F ( x)  1500 x1  1800 x2  max

5 x1  3 x2  270, y1
7 x  8 x  800, y
 1 2 2

4 x1  6 x2  360, y3
 x1  0, x2  0.

Dual

F ( y )  270 y1  800 y2  360 y3  min

5 y1  7 y2  4 y3  1500,

3 y1  8 y2  6 y3  1800,
 y  0, y  0, y  0.
 1 2 3

2) La solution du primal étant: x  ( x1 , x2 )  (30, 40) et

F ( x)  117 000 .
Remarque: on prend les contraintes dont on connaît la solution

D’après le théorème des écarts complémentaires on a:

(5 x1  3 x2  270) y1  0, (5  30  3  40  270) y1  0  y1  0,

   
  
 1
( 7 x  8 x2  800 ) y 2  0,  (7  30  8  40  800) y2  0  y2  0,
      
(4 x1  6 x2  360) y3  0. (4  30  6  40  360) y3  0  y3  0.

Dans ce système d’équations seulement (7  30  8  40  800)  0 c’est pour


cela que y 2  0 .
NB: 1) si l’un des facteurs est nul, alors l’autre n’est pas nul,
2) le théorème des écarts complémentaires nous permet de savoir parmi les
variables du dual celles qui sont nulles.

On prendre les contraintes du dual à l’optimum et on remplace y 2 par sa valeur.
On trouve ainsi le système suivant:

5 y1  4 y3  1500,

 
3 y1  6 y3  1800.
   
En résolvant ce système on trouve y  ( y1 , y2 , y3 )  (100, 0, 250) et
F ( y  )  270  100  800  0  360  250  117000 .
 
On constate que toujours F ( x )  F ( y ) .

3) Le primal a comme variables de décision x1 et x2 et a comme variables

d’écart x3 , x4 et x5 tandis que le dual a comme variables de décision y1 , y 2
et y3 et a comme variables d’écart y4 et y5 . En faisant la correspondance
entre les variables d’écart du primal et les variables de décision du dual on
trouve: y1  x3 , y2  x4 , y3  x5 . Ainsi d’après le tableau optimal du
 
primal on a: y1  x3  y1  3  100 , y2  x4  y2   4  0 ,
y3  x5  y3  5  250 .
     
D’oû y  ( y1 , y2 , y3 )  (100, 0, 250) et F ( y )  117000 .

4) On a y  (100, 0, 250) .

D’oû y1  100

a) si y1  80 , alors on a y1  y1 d’oû il est intéressant d’acheter des heures
supplémentaires des machines à 80 F(le coût a diminué de 100-80= 20 F).

b) si y1  150 , alors on a y1  y1 d’oû il n’est pas intéressant d’acheter des
heures supplémentaires des machines à 150 F(le coût a augmenté de 150-100=
50 F).

Exemple 1 : une entreprise de mécanique fabrique trois types de pièces

dans trois ateliers : Usinage, Montage et Finition.
Les données techniques et commerciales relatives à cette fabrication sont résumées
dans le tableau suivant :

Nombre d’heures-machines nécessaires à la Prix de vente

fabrication des pièces unitaire des
Usinage Montage Finition pièces (francs)
Pièces 355
Pièces 515
Pièces 925
Coût variable 60 80 50
de l’heure
Capacité de 2 000 2 400 2 400
l’atelier
Formuler le modèle mathématique de ce problème.
Solution 1 :

Soient les nombres respectifs des pièces de types fabriqués par

l’entreprise de mécanique :
Les bénéfices unitaires des pièces sont :

Pièces :

Pièces :

Pièces :
Exemple 2 : une société fabrique deux pièces . Les prix unitaires des pièces
sont respectivement et . Chaque pièce est traitée successivement dans
trois ateliers. Le nombre d’heures-machines est indiqué dans le tableau suivant :

Atelier I Atelier II Atelier III

Pièce 3h 5h 2h

Pièce 1h 3h 3h

Pour éviter un schéma technique :

_ L’atelier I doit obligatoirement fournir au moins ,

_ L’atelier II au moins ,

_ L’atelier III au moins .

Ecris le programme linéaire permettant de minimiser le coût de fabrication de ces

pièces.
Solution 2 :

Soient les nombres respectifs des pièces de types fabriqués.

Solution de d’exercice 11 :

Soient les nombres respectifs des articles fabriqués :

Les bénéfices unitaires des articles sont :

Solution de l’exercice 12 :
Soient les nombres respectifs des pièces de types fabriquées :

Les bénéfices unitaires des pièces sont :

Pièces :

Pièces :