Faculté Des Sciences De L'Ingénieur

Recherche Opérationnelle
G.CIVIL4
Prof H. MONAIM

Année Universitaire: 2024/2025 Universite Privée de Fés, Maroc.

[Link]@[Link]
 R.O, AU 24/25.

Introduction: Comme il a été dit dans le chapitre I, résoudre un programme linéaire

consiste à maximiser (ou minimiser) une fonctionnelle linéaire d’un nombre fini quel-
conque de variables positives ou nulles, ces variables devant respecter un nombre fini
quelconque de contraintes linéaires. Un programme linéaire peut toujours s’écrire de
la façon suivante:

Max ou MinZ(x1 , x2 , ..., xn )

Sujet de
(P) M .xT ≤ ou bien ≥ b


Avec M ∈ Mn (R) et x = (x1 , x2 , ..., xn ), b = (b1 , b2 , ..., bn ) ∈ Rn .

Bien entendu, la méthode géométrique pour déterminer l’optimum de ce système
fonctionne parfaitement, mais un exemple légèrement plus compliqué, avec 3 produits
par exemple, serait difficile à représenter graphiquement: il faudrait avoir recours à la
3ème dimension. Un exemple à 4 dimensions serait extrêmement difficile à résoudre de
cette façon. D’autre part, cette méthode ne décrit pas réellement un algorithme.

En revanche, en admettant que la solution optimale est effectivement présente sur

la frontière du simplexe, on peut imaginer qu’au lieu d’explorer tout l’espace continu
du simplexe, on puisse se contenter de rechercher l’optimum sur ses mêmes frontières.
On passe donc d’une recherche dans un espace de dimension n à une recherche dans un
espace de dimension n − 1. De manière récursive, en supposant que dans le cas général
aucun des espaces de dimension n − 1 n’est parallèle aux fonctions paramétrées qu’on
cherche à optimiser, on peut se contenter de rechercher l’optimum sur les frontières de
ses mêmes sous-espaces, de dimension n − 2, et ainsi de suite.
De cette manière, on finit par rechercher l’optimum sur un ensemble fini de points
(de dimension 0), qui sont les sommets du simplexe. Chacun de ces points forme une
base du simplexe et peut être trouvé par manipulation du système linéaire d’inéquations
qui définit le simplexe. On pourrait imaginer de les énumérer tous et de tester la fonc-
tion de profit sur chacun d’entre eux afin de trouver l’optimum. Cependant, le nombre
de ces points grandit de manière exponentielle en fonction de la dimensionnalité du
problème.

G. Dantzig (1914-2005) a le premier proposé de partir d’une base connue du sim-

plexe respectant les contraintes (une base réalisable), puis de se déplacer le long des
arêtes du simplexe, c’est-à-dire les droites reliant les bases entre elles, de manière à tou-
jours augmenter la fonction de profit le plus rapidement possible, tout en continuant
à respecter les contraintes. En procédant de cette manière, de base réalisable en base
réalisable, on constate qu’on arrive le plus souvent à trouver l’optimum en un nombre
de déplacements proportionnels à la dimensionnalité du problème, et non plus expo-
nentiel en fonction de celle-ci.
Un modèle peut s’écrire sous la forme générale suivante:

Max ou MinZ(x1 , x2 , ..., xn )

 Sujet de:

a11 x1 + a12 x2 + ... + a1r1 xr1 ≤ ou bien ≥ b1

a21 x1 + a22 x2 + ... + a2r2 xr2 ≤ ou bien ≥ b2

(P) .. .. .. .. ..


 . . . . .

aℓ1 x1 + aℓ2 x2 + ... + aℓrl xrℓ ≤ ou bien ≥ bl


Prof. H. MONAIM Université Privée de Fès

 R.O, AU 24/25.

Avec ai j ∈ R et x = (x1 , x2 , ..., xn ), b = (b1 , b2 , ..., bn ) ∈ Rn .

Transformations fondamentales pour passer de la forme générale à la forme canon-
ique:
MinZ(x1 , x2 , ..., xn ) devient Max − Z(x1 , x2 , ..., xn )
et
aℓ1 x1 + aℓ2 x2 + ... + aℓrl xrℓ ≥ bℓ devient −aℓ1 x1 − aℓ2 x2 − ... − aℓrl xrℓ ≤ −bℓ
et
(
aℓ1 x1 + aℓ2 x2 + ... + aℓrl xrℓ ≤ bℓ
aℓ1 x1 + aℓ2 x2 + ... + aℓrl xrℓ = bℓ devient
−aℓ1 x1 − aℓ2 x2 − ... − aℓrl xrℓ ≤ −bℓ
et
xℓ = xℓ+ − xℓ−
(
xℓ ∈ R devient
xℓ+ , xℓ− ≥ 0
et
xℓ + c ≥ 0 devient xℓ′ ≥ 0 avec xℓ′ = xℓ + c.
Passage de la forme canonique à la forme standard:
MaxZ(x
1 , x2 , ..., xn ) Sujet de:
a x + a12 x2 + ... + a1r1 xr1 ≤ b1
 11 1


(P) .. .. .. .. ..
 . . . . .

 a x + a x + ... + a x ≤ b
ℓ1 1 ℓ2 2 ℓrl rℓ ℓ

Avec ai j ∈ R et xk ≥ 0, b = (b1 , b2 , ..., bn ) ∈ Rn .

Devient.
MaxZ(x
 1 , x2 , ..., xn ) Sujet de:
a x + a12 x2 + ... + a1r1 xr1 + u1 = b1
 11 1


(P) .. .. .. .. ..
 . . . . .

 a x + a x + ... + a x + u = b
ℓ1 1 ℓ2 2 ℓrl rℓ ℓ ℓ

Avec ai j ∈ R, xk , uk ≥ 0 et b = (b1 , b2 , ..., bn ) ∈ Rn .

0.0.1 Un algorithme élémentaire du simplexe

La méthode que G. Dantzig a développée consiste en une manipulation explicite des
inégalités pour trouver les solutions de base réalisables, qu’on appelle maintenant
méthode du simplexe.

Nous la présentons ici en suivant l’exemple de la nourriture pour chiens. Cette

méthode, à base de tableaux, ne se prête pas très facilement à une mise en œuvre
informatique, mais est celle qui est la plus souvent présentée dans les textes classiques
sur la programmation linéaire. Il est donc utile de l’avoir vue au moins une fois.
L’idée générale sera reprise au cours des exemples des sections suivantes et au mo-
ment du déroulement de l’algorithme que nous proposons. Elle se décompose en les
phases suivantes:

Étapes de l’algorithme:

Prof. H. MONAIM Université Privée de Fès

 R.O, AU 24/25.

1- Partir d’une solution réalisable et calculer la fonction objectif en ce point.

2- Trouver les arêtes de frontières de l’ensemble réalisable passant par ce point, et
calculer si la fonction objectif s’améliore en se déplaçant le long de cette arête.
3- Se déplacer le long de l’arête donnant la plus grande augmentation.
4- Répéter (2) et (3) jusqu’à ce que la fonction objectif n’augmente plus. On a trouvé
la solution optimale.
On commence par l’exemple suivant:
- Soit une entreprise de nourriture pour chiens, qui fabrique 2 types de granulés:
le Wag-Tail (W) et le Bark-Mad (B).
- Chacun des types utilise un mélange de légumes, bœuf et poisson, dans les pro-
portions suivantes

Ingrédient Quantité totale (kg) Quantité dans B (kg) Quantité dans W (kg)
Légumes 1400 4 4
Poisson 1800 6 3
Bœuf 1800 2 6

1. On suppose que la compagnie opère un bénéfice de 12 euros sur chaque paquet

de B et de 8 euros sur ceux de W.
2. Comment l’entreprise peut-elle faire pour maximiser son profit?
Le modèle est la forme générale suivante:
Max 12B + 8W
Sujet
 de:
4B + 4W ≤ 1400

(P) 6B + 3W ≤ 1800

2B + 6W ≤ 100

Avec B,W ≥ 0.
Résolution graphique du problème

Prof. H. MONAIM Université Privée de Fès

 R.O, AU 24/25.

Variables artificielles:
Par ajout des variables artificielles {X,Y, Z}, le modèle (P) peut être mis sous la forme
standard suivante:

Max 12B + 8W
Sujet
 de:
4B + 4W + X = 1400

(P) 6B + 3W +Y = 1800

2B + 6W + Z = 1800

Avec B,W, X,Y, Z ≥ 0.

Terminologie:

- L’ensemble des valeurs des variables B,W, X,Y, Z respectant toutes les con-
traintes forme une solution réalisable.

- Une solution avec m équations et n inconnues, n ≥ m avec certaines de ces vari-

ables nulles, est une solution de base.

- L’ensemble des m variables non nulles forme une base.

Choix initial:

- Pour former une solution de base, on doit choisir 3 variables et mettre les autres
sont nulles.

- On peut poser B = W = 0 et résoudre pour les variables X,Y, Z.

- Ce qui
 donne:
X = 1400 − 4B − 4W

(P) Y = 1800 − 6B − 3W

Z = 1800 − 2B − 6W


- Géométriquement, cette solution est réalisable et correspond à l’origine. Mal-

heureusement, pour ce choix, P = 0, ce qui n’est clairement pas optimal.

De manière itérative, on cherche à améliorer cette solution.

Première itération:

1- Pour augmenter P, on peut choisir d’augmenter B ou W . Comme B offre le plus

grand gain, on choisit cette variable. W reste à 0.

2- On introduit donc B dans la base, mais B ne peut pas être plus grand que 300,
sinon Y deviendrait négatif. On choisit donc B = 300, ce qui induit Y = 0.

3- On réexprime le système avec ces données:

2

 X = 200 + Y − 2W
3




 B = 300 − 1 Y − 1 W


(P) 6 2

 1

 Y = 1200 + Y − 5W
3




P = 3600 − 2Y + 2W


Prof. H. MONAIM Université Privée de Fès

 R.O, AU 24/25.

Maintenant, le profit est de 3600.

Second itération:

1- On peut encore faire mieux en augmentant W , mais pour que X reste positive, W
ne peut pas être plus grand que 100.

2- On introduit donc W dans la base, avec W = 100 ce qui induit X = 0.

3- On réexprime le système avec ces données:

1 1

 X = 100 − X + Y


 2 3
1 1


 B = 250 + X − Y


(P) 4 3
5 4
Z = 700 + X − Y





 2 3
4


 P = 3800 − X − Y

3
Maintenant, le profit est de 3800. Avec X = Y = 0 et B = 250,W = 100, ainsi que
Z = 700.

0.0.2 Simplexe
Dans cette partie, on va introduire l’algorithme du simplexe sur les tableaux.

On considère le modèle canonique suivant:

Max Z(x1 , x2 ) = 30x1 + 50x2

Sujet
 de:
3x1 + 2x2 ≤ 1800

(P) x1 ≤ 400

x2 ≤ 600

Avec x1 , x2 ≥ 0.

En ajoutant des variables d’écart, on obtient le modèle standard suivant:

Max Z(x1 , x2 ) = 30x1 + 50x2

Sujet
 de:
3x1 + 2x2 + x3 = 1800

(P) x1 + x4 = 400

x2 + x5 = 600

Avec x1 , x2 , x3 , x4 , x5 ≥ 0.

Ce modèle est à la forme canonique.

On commence par une solution initiale (x1 , x2 ) = (0, 0).
On obtient alors

x3 = 1800, x4 = 400, x5 = 600, et Z(0, 0) = 0

Le tableau initial est comme suit

Prof. H. MONAIM Université Privée de Fès

 R.O, AU 24/25.

On choisis la variable à introduire dans la base.

La colonne de x2 est appelée colonne pivot c. On divise les bi par Eic .

Prof. H. MONAIM Université Privée de Fès

 R.O, AU 24/25.

Ici La colonne pivot est 2.

bi
La plus petite valeure des determine la ligne pivot l.
Eic

Ici La ligne pivot est 3.

On remplace x5 par x2 et divise la ligne l par le pivot Elc .

Ici Le pivot est E32 = 1.

On remplie le nouveau tableau par la formule:

Eic
Ei′ j = Ei j − El j
Elc

Prof. H. MONAIM Université Privée de Fès

 R.O, AU 24/25.

Ici
Ei′ j = Ei j − Ei2 E3 j
Si les valeurs de la fonctions objectif sont négatives ou nulles on arrête.

Sinon, on reprends dès l’étape 2. (Ici on a une valeure strictement positive 30).
Pour detreminer le pivot, on divise b par sa colonne.

Prof. H. MONAIM Université Privée de Fès

 R.O, AU 24/25.

Le pivot est E11 = 3.

On remplace x3 par x1 et divise la ligne 1 par le pivot E11 = 3.

On remplie le nouveau tableau par la formule:

Eic′ ′
Ei j ” = Ei j − ′ El j
Elc

Ici
′
Ei1
Ei j ” = Ei′ j − E′
3 1j
Comme toutes les valeures de la fonction objectif sont négatifs. Le processus doit
s’arrêter et on a la valeur optimale est p = 36000 atteinte au point (200, 600).

Prof. H. MONAIM Université Privée de Fès

 R.O, AU 24/25.

Considèrons le problème suivant:

Max Z(x1 , x2 ) = x1 + 5x2 + x3

Sujet
 de:

 x1 + 3x2 + x3 ≤ 3

 −x1 + 3x3 ≤ 2
(P)

−2x1 − 4x2 + x3 ≥ −4

x1 + 3x2 − x3 ≤ 2

Avec x1 , x2 , x3 ≥ 0.

Ce modèle est à la forme canonique?

Le problème sous la forme standard

Max Z(x1 , x2 ) = x1 + 5x2 + x3

Sujet de:


 x1 + 3x2 + x3 + x4 ≤ 3

 −x1 + 3x3 + x5 ≤ 2
(P)

 2x1 + 4x2 − x3 + x6 ≤ 4

x1 + 3x2 − x3 + x7 ≤ 2

Avec x1 , x2 , x3 , x4 , x5 , x6 , x7 ≥ 0.

Le tableau corrspondant est alors sous forme

Prof. H. MONAIM Université Privée de Fès

 R.O, AU 24/25.

La dernière ligne du tableau correspond à une expression possible de z comme

fonction affine, l’opposé du terme constant se trouvant en bas à droite du tableau.
On part de la solution réalisable (x1 , x2 , x3 , x4 , x5 , x6 , x7 ) = (0, 0, 0, 3, 2, 4, 2) et, puisque le
terme en x1 dans la dernière ligne du tableau (=1) est positif, on va augmenter x1 (sans
modifier ni x2 ni x3 ) jusqu’à ce que l’une des variables x4 , x5 , x6 ou x7 devienne nulle.
Ceci se produit pour x1 = 2, pour lequel à la fois x6 et x7 deviennent nuls. On choisit
donc de faire rentrer x1 en base, et de faire sortir (par exemple) x6 .
On obtient le tableau suivant

Et par suite

Ou encors

Notes importantes:

- S’il existe une variable dont la base a un coefficient positif dans la ligne z de
Nalinnes, et que tous les coefficients correspondants dans le tableau sont nuls ou
négatifs, alors la solution est infinie.

Prof. H. MONAIM Université Privée de Fès