1 Optimisation Linéaire

1.1 Introduction

Dans ce chapitre, l’objectif est de familiariser l’étudiant avec les notions relatives à la
programmation linéaire. Plusieurs exemples illustrent les différents domaines d'application de
la programmation linéaire. De manière générale, la résolution de problèmes de programmation
mathématique vise à déterminer l'allocation optimale (c'est-à-dire la meilleure combinaison
possible) de ressources limitées pour atteindre certains objectifs. Les allocations doivent
minimiser ou maximiser une fonction dite objectif. En économie, ces fonctions sont par
exemple le profit ou le coût.

La forme générale d'un problème d’est la suivante :

Optimiser z f x1 , x2 ,..., xn
souscontraintes

(1.1)
hi x1 , x2 ,..., xn bi avec i 1,2,..., m

et Li xi U i

où les fonctions f et hi sont des fonctions numériques à n variables. La fonction f est la

fonction objectif à optimiser, tandis que les égalités (=), ou inégalités ( , ), hi sont les
contraintes. Li et Ui sont les bornes inferieur et supérieur, respectivement, qu’une variable de
décision xi peut prendre.

Selon la nature des fonctions f et hi, on peut être confronté à plusieurs types de problèmes de
d’optimisation. Lorsque les fonctions f et hi, i = 1,...,m sont linéaires, il s'agit d'un problème de
programmation linéaire. Si de plus, on impose que les variables ne peuvent prendre que des
valeurs entières, on parle de programmation linéaire entière. Les problèmes dans lesquels la

1
fonction f ou hi sont non-linéaires font partie de l’optimisation non-linéaire. S’il n’y a pas de
contrainte, on dit que le problème est sans contraintes, sinon il est avec contraintes. Si les
bornes inferieur et supérieur ne sont pas définis, on dit que le problème est non-borné ou
ouvert, sinon c’est un problème borné.
La fonction Optimiser peut être soit Maximiser (Max), ou Minimiser (Min). On utilise la
fonction Max lorsqu’on veut augmenter le bénéfice par exemple, et la fonction Min lorsque on
veut minimiser les frais, les déchés, les couts de production, etc. Le choix de l’une des deux
fonctions dépond de ce que nos objectifs. De plus, il faut noter qu’on peut convertir un
problème de maximisation à un problème de minimisation en utilisant cette relation, et vis
versa :
Max( z ) Min( z ) (1.2)
Dans la majorité des logicielles qu’ont des modules d’optimisation, comme Matlab, Python ou
R, ces modules d’optimisation sont programmés pour résoudre des problèmes de minimisation
uniquement. Donc, si vous êtes confrontés à résoudre un problème de maximisation en
utilisant Matlab, par exemple, il est impératif de convertir votre problème de maximisation à
un problème de minimisation en utilisant la relation Eq. (1.2).

1.2 Formulation générale d’un programme linéaire

La programmation linéaire est une technique simple qui consiste à représenter des
relations complexes par des fonctions linéaires et à trouver ensuite les points optimaux. Le
mot important de la phrase précédente est représenté. Les relations réelles peuvent être
beaucoup plus complexes, mais nous pouvons les simplifier en relations linéaires. Un
problème de programmation linéaire (PL), revient donc à :
Optimiser z c1 x1 c2 x2 ... cn xn
souscontraintes

ai1 x1 ai 2 x2 ... ain xn bi (1.3)

avec i 1,2,..., m
et x j 0, j 1,2,..., n

où aij, bi et cj sont des constantes connues.

2
Les contraintes xj > 0, j = 1,...,n sont appelées contraintes de non-négativité.

Principalement, il y a trois étapes à suivre pour pouvoir formuler un programme linéaire :

1- Il faut tout d’abord identifier les variables du problème à valeur non connues (variable
de décision) et les représenter sous forme symbolique (exemple : x1, x2 ).
2- Identifier l’objectif à optimiser et le représenter sous une forme linéaire en fonction
des variables de décision, puis spécifier si le critère de sélection : maximiser ou à
minimiser.
3- Voir les restrictions du problème et les exprimer par des équations linéaires (les
contraintes).

Voyons à présent quelques exemples simples de programmation linéaire que l'on peut
rencontrer dans différents contextes réels. Ces exemples ont pour but de formuler
mathématiquement un problème donné.

1.2.1 Problème de production

Dans cette partie, nous allons voir comment formuler mathématiquement deux
problèmes de production, en utilisant les fonctions Max et Min.

Exemple 1.1 : Une entreprise fabrique des chaises et des tables à l’aide de deux machines A
et B. Chaque produit passe obligatoirement par les deux machines. Pour produire une chaise,
il faut 2 heures de machine A et 1 heure de machine B. Pour produire une table, il faut 1
heure de machine A et 2 heures de machine B. L'entreprise réalise un bénéfice de 3$ sur
chaque chaise et de 4$ sur chaque table. Les deux machines A et B sont disponibles 12 heures
par jour au maximum. Le problème consiste à savoir combien de chaises et de tables il faut
fabriquer pour maximiser le bénéfice.(Dodge et al., 2004)

Pour facilité la formulation mathématique, nous traçons un tableau comme indiquer ci-
dessous, tout en précisant : un, le nombre d'heures nécessaires pour produire une table unique
et chaise unique par chaque machine ; deux, le nombre total des heures disponibles pour
chaque machine ; et trois, le profit pour chaque unité de chaise et de table produite.

3
 Machine Produit Disponibilité
Chaise Table
A 2 1 12
B 1 2 12
Bénéfice par
3 4
unité

Posons maintenant x1 le nombre des chaises et x2 le nombre des tables produites

quotidiennement. Sachant qu’une chaise génère un bénéfice de 3$ tandis qu’une table est de
4$, le bénéfice journalier, qu’on va appeler z, peut être évalué par la formule suivante :

z 3 x1 4 x2 (1.4)

L’équation (1.4) est notre fonction objectif. Puisque on veut augmenter le bénéfice de
l’entreprise, notre problème sera un problème de maximisation (Max).

Passons maintenant à la formulation des. Puisque la disponibilité des machines est limitée, on
ne peut pas accroître la production indéfiniment. Les deux machines A et B ne peuvent pas
fonctionner plus de 12 heures par jour pour une raison ou une autre. Par exemple : on doit
cesser les machines la nuit pour ne pas dérangé les voisins ; employer une équipe de nuit
s’avère très chère. Donc, on sait que pour produire une chaise, il faut 2 heures de machine A
alors que pour une table il n'en faut qu'une heure. La contrainte disponibilité concernant la
machine A s’écrit comme suit :
2 x1 1x2 12 (1.5)

De même, une chaise nécessite 1 heure de machine B, tandis qu'une table en demande 2. La
contrainte concernant la machine B, avec la même durée maximale de 12 heures par jour, est
donnée par :
1x1 2 x2 12 (1.6)

De plus, comme on ne peut pas produire de quantités négatives, il faut ajouter encore deux
contraintes de non-négativité :
x1 0 (1.7)
et
x2 0 (1.8)

4
Le problème consiste donc à trouver les valeurs des variables x1 et x2 qui maximisent le
bénéfice journalier (1.4) tout en satisfaisant les contraintes (1.5) à (1.8).
En résumé, le problème s'écrit sous la forme :

Max z 3 x1 4 x2
souscontraintes
2 x1 x2 12 (1.9)
x1 2 x2 12
et x1 , x2 0

Passons maintenant au dexieme exemple ou nous utilisons la fonction Min.

Exemple 1.2 : Une compagnie possède deux mines de charbon A et B. La mine A produit
quotidiennement 1 tonne de charbon de qualité supérieure (1er choix), 1 tonne de qualité
moyenne (2ème choix), et 6 tonnes de qualité inférieure (3ème choix). La mine B produit par
jour 2, 4 et 3 tonnes de chacune des trois qualités. La compagnie doit produire au moins 90
tonnes de charbon de qualité supérieure, 120 tonnes de qualité moyenne et 180 tonnes de
qualité inférieure.
Sachant que le coût de production journalier est le même dans chaque mine, soit 1 000, quel
est le nombre de jours de production dans la mine A et dans la mine B qui minimisent le coût
de production de la compagnie ?(Dodge et al., 2004)

De la même façon que le précédant exemple, nous dressons un tableau tout en indiquant : le
tonnage de charbon produit par choix dans chaque mine ; l’objectif de production de charbon
par choix, ainsi que les frais journalier dans chaque mine.

Charbon Mine Objectif de

A B production
er
1 choix 1 2 90
2ème choix 1 4 120
3ème choix 6 3 180
Frais
1000 1000
journalier

5
Soit x1 et x2 le nombre des jours de travail dans les mines A et B, respectivement. En voulant
réduire les frais de production, systématiquement, il s’agit d’un problème de minimisation
dont la fonction objectif est la somme des frais journalier des deux mines A et B. la fonction
objectif qu’on doit minimiser s’écrit comme suit :

z 1000 x1 1000 x2 (1.10)

Pour satisfaire ces besoins, la compagnie doit produire au moins 90 tonnes de charbon de
qualité supérieur. Puisque la mine A produit une tonne par jour du charbon 1er choix tandis
que la mine B produit 2 tonnes, la contrainte de production du charbon 1er choix s’écrit :

x1 2 x2 90 (1.11)

De même, pour les deux autres qualités de charbon, on trouve :

x1 4 x2 120 (1.12)

6 x1 3 x2 180 (1.13)

Puisque il n’y a pas des jours négatifs, on ajoute deux contraintes de non-négativité :

x1 , x2 0 (1.14)

En résumé, Le problème de programmation linéaire s'écrit donc :

Max z 1000 x1 1000 x2

souscontraintes
x1 2 x2 90
(1.15)
x1 4 x2 120
6 x1 4 x2 180
et x1 , x2 0

1.2.2 Problème de Mélange

Exemple 1.3 : Un industriel veut produire un alliage Z à 30% de plomb, 30% de zinc et 40%
d’étain. Supposons qu’il puisse se procurer sur le marché des alliages A, B, C, D, E, F, G, H,
I dont les compositions et les prix respectifs sont donnés dans le tableau suivant :

6
 Compositions des A B C D E F G H I Alliage à
alliages (en %) x1 x2 x3 x4 x5 x6 x7 x8 x9 fabriquer
Plomb 10 10 40 60 30 30 30 50 20 30%
Zinc 10 30 50 30 30 40 20 40 30 30%
Etain 80 60 10 10 40 30 50 10 50 40%
Coût au Kilo ($) 4.1 4.3 5.8 6 7.6 7.5 7.3 6.9 7.3
Combien doit-il acheter de chaque alliage A, B, C, D, E, F, G, H et I pour obtenir au prix de
revient minimum un 1 Kg de l’alliage Z ?(Dantzig, 1966)

L’Exemple 1.3 est un problème typique de ce que n’appelle un problème de mélange. On

suppose x1 à x9 sont les masses des alliages A à I respectivement, que l’industriel doit
mélanger pour produire son alliage désiré. L’objectif de l’industriel est de minimisé le cout du
produit final, toute en respectant les fractions massique du contenu, a savoir 30% du plomb,
30% du zinc et 40% d’étain. La fonction objectif pour minimiser le cout s’écrit comme
suivant :

Min z 4.1x1 4.3 x2 5.8 x3 6 x4 7.6 x5 7.5 x6 7.3 x7 6.9 x8 7.3 x9 (1.16)

Le produit final doive avoir des proportions bien déterminées de chaque composant, ni plus, ni
moins. Dans ce cas, des contraintes d’égalité doive être imposées. Pour le cas du plomb, on a :
10 x1 10 x2 40 x3 60 x4 30 x5 30 x6 30 x7 50 x8 20 x9 30 (1.17)
Pour le Zinc
10 x1 30 x2 50 x3 30 x4 30 x5 40 x6 20 x7 40 x8 30 x9 30 (1.18)

et fin, l’étain
80 x1 60 x2 10 x3 10 x4 40 x5 30 x6 50 x7 10 x8 50 x9 40 (1.19)

Puisque les proportions de chaque composant sont définies pour 1kg, la somme totale des
masses x1 à x9 doit être égale à 1kg. Pour satisfaire cette condition, on rajoute une autre
contrainte :

x1 x2 x3 x4 x5 x6 x7 x8 x9 1 (1.20)

7
Naturellement, une masse ne peut pas avoir une valeur négative, on rajoute des contraintes de
non-négativité. Ceci nous ramène à écrire le programme linéaire suivant :

Min z 4.1x1 4.3 x2 5.8 x3 6 x4 7.6 x5 7.5 x6 7.3 x7 6.9 x8 7.3 x9

souscontrainte
10 x1 10 x2 40 x3 60 x4 30 x5 30 x6 30 x7 50 x8 20 x9 30
10 x1 30 x2 50 x3 30 x4 30 x5 40 x6 20 x7 40 x8 30 x9 30 (1.21)
80 x1 60 x2 10 x3 10 x4 40 x5 30 x6 50 x7 10 x8 50 x9 40
x1 x2 x3 x4 x5 x6 x7 x8 x9 1
et x j 0, j 1,2,...,9

1.2.3 Problème de découpage

Pour comprendre le problème de découpage, considérant cet exemple : Un

chaudronnier dispose dans son magasin des barres brutes en acier d’une longueur Lbarre = 1m.
Il doit découper des pièces de longueurs L1 = 50cm, L2 = 30cm et L3 = 20cm (voir la Figure
1.1). De plus, il a besoin de découper trois pièces de chaque longueur. La question est quelle
est le nombre minimum de barres brutes qu’il doit utiliser pour satisfaire ces besoins avec le
minimum de chute ?

Figure 1.1 Les plans de découpage d’une barre d’acier

8
Il y’a plusieurs façons de découper une barre, ce qu’on appelle plans de découpage (dans
certain livre, on les appelle motifs de découpage). Comme on peut le voir dans la Figure 1.1, il
y’a 7 plans de découpage possibles qu’on peut les résumer dans le Tableau 1.1, selon le
nombre de chaque longueur.

Tableau 1.1 List des Plans de découpe.

N° du Plan Quantité Chute
L1 L2 L3 (en cm)
1 2 0 0 0
2 1 1 1 0
3 0 2 2 0
4 1 0 2 10
5 0 0 5 0
6 0 3 0 10
7 0 1 3 10

Sans faire des calcules, il claire que notre chaudronnier a besoin de 3 barre qu’il doit découper
selon les Plans 1, 2 et 3, respectivement. Utiliser d’autres plans peut satisfaire ces besoins,
mais ils génèrent soit de la chute (plans 4, 6 et 7) soit des pièces supplémentaires (plan 5).

Maintenant, on considère que ce chaudronnier a reçu une commande pour fabriquer 15 pièces
de longueur L1, 26 pièces de longueur L2 et 13 de L3. Quelle est le nombre minimal de barre
brute qu’il doit s’en procurer pour satisfaire la commande ? Dans ce cas, le calcule mentale
devient très difficile. D’une manière générale, le programme linéaire du problème de
découpage s’écrit comme suivant :

n
Min z xj
j 1

souscontraintes
n
(1.22)
aij x j bi i 1,..., m
j 1

et x j 0

9
où n est le nombre des plans, m est le nombre des pièces (ou des modèles), xj est le nombre de
fois ou le plan j est utilisé, aij est le nombre du modèle i obtenue en utilisant le plan j, bi est le
nombre totale du modèle i qui doit être fabriquer.

Dans notre cas, on a trois modèles de longueur à réaliser (m = 3) et 7 plans de découpe (n = 7).
En faisant usage du Tableau 1.1, le programme linéaire sous forme mathématique s’écrit :

Min z x1 x2 x3 x4 x5 x6 x7
souscontraintes
2 x1 1x2 0 x3 1x4 0 x5 0 x6 0 x7 15
(1.23)
0 x1 1x2 2 x3 0 x4 0 x5 3 x6 1x7 26
0 x1 1x2 2 x3 2 x4 5 x5 0 x6 3 x7 13
et x j 0 j 1,2,...,7

Il important de noter que le PL défini par l’Eq. (1.23) ainsi que dans sa forme générale (Eq.
1.22) sert à minimiser le nombre des barres identiques sans considération des chutes. Dans le
cas contraire où on a un stock de barres avec longueur différents, la fonction objectif doit être
modifié en introduisant les longueur des barres en stock et en minimisant les chutes.
Considérons l’exemple suivant :

Exemple 1.4 : Une usine fabrique 3 types de bureaux:

108 petits bureaux (hauteur pied = 40cm)
125 bureaux moyens (hauteur pied = 60cm)
100 grands bureaux (hauteur pied = 70cm)
Découpe des pieds dans des barres d’acier
Diamètre constant
Deux longueurs disponibles : 1,5 m et 2 m
Comment satisfaire la commande de bureaux en minimisant les chutes sachant que chaque
bureau nécessite 4 pieds ?(Ferry, 2020)

Comme l’exemple précédant, nous commençons à établir les plans de découpe pour les deux
longueurs des barres brutes. Il existe 6 plans de découpe pour la barre de longueur 1.5m et 9
plans pour celle de 2m.

10
Les plans de découpe des deux barres doivent être numérotés de façon continue comme
indiqué dans le Tableau 1.2. Adoptons la notation suivante :

n1 : nombre des plans de découpe de la barre type 1 (n1 = 6)

n2 : nombre des plans de découpe de la barre type 2 (n2 = 9)
n : nombre totale des plans de découpe (n = n1+ n2 = 15)
xj : nombre de barres découpées selon le plan de découpe j (j = 1,…, n = 15)
L1 et L2 : longueur des barres brutes (L1 = 1.5m et L2 = 2m)
m : le nombre des types des pieds (m = 3)
Hi : la hauteur de chaque type de pied (i = 1,…, m = 3)
bi : la demande selon chaque type de pied (B1 = 432, B2 = 500 et B3 = 400)
aij : le nombre des pieds de type i produit en utilisant le plans de découpe j

Tableau 1.2 List des Plans de découpe de l’exemple 1.4.

N° du Plan Pieds de Pieds de Pieds de Chute (cm)
de découpe type 1 type 2 type 3
(0.4m) (0.6m) (0.7m)
Barre de 1 0 0 2 10
type 1
2 0 1 1 20
(1,5m)
3 2 0 1 0
4 0 2 0 30
5 2 1 0 10
6 3 0 0 30
Barre de 7 0 1 2 0
type 2
8 1 0 2 20
(2m)
9 0 2 1 10
10 1 1 1 30
11 3 0 1 10
12 0 3 0 20
13 2 2 0 0
14 3 1 0 20
15 5 0 0 0
Demande 4×108=432 4×125=500 4×100=400

11
Le programme linéaire du l’exemple 1.4 s’écrit :
n1 n m
Min z L1 xj L2 xj bi H i
j 1 j n1 1 i 1

souscontraintes
n
(1.24)
aij x j bi avec i 1,2,..., m
j 1

et x j 0 j 1,2,..., n

La fonction objectif ici sert à minimiser les chutes qui est égale à la longueur totale des barres
brutes utilisées moins la longueur réel totale des l’ensemble des pieds produit. Deux types de
contrainte sont utilisés, des contraintes pour satisfaire la demande sur chaque type de pied, et
des contraintes de non-négativités. En introduisant les valeurs réelles de notre PL, on aura :
Min z 1.5 x1 ... x6 2 x7 ... x15 432 0.4 500 0.6 400 0.7
Souscontrainte
2 x3 2 x5 3x6 x8 x10 3 x11 2 x13 3 x14 5 x15 432
(1.25)
x2 2 x4 x5 x7 2 x9 x10 3 x12 2 x13 x14 500
2 x1 x2 x3 2 x7 2 x8 x9 x10 x11 400
xj 0 j 1,2,...,15

1.2.4 Problème de Transport

Ce type de problème se définit comme suit : il s’agit d’optimiser le cout de transport

d’une marchandise d’un ensemble de point de départ vers un autre ensemble de point
d’arrivée. En connaissant les quantités disponibles de chaque point de départ, les quantités
requises aux points de réception (point d’arrivée), et le coût de transport d'une quantité
unitaire de la marchandise d'un point de départ vers un point d’arrivée, il est possible de
déterminer un plan de transport optimal en utilisant la programmation linéaire.

Considérant l’exemple suivant :

Example 1.5 : Une entreprise de production de semoule possède trois usines situées à Bouira,
Sétif et Biskra. Le blé nécessaire à la production arrive dans les ports du Bejaia et Annaba.
Les quantités hebdomadaires de blé nécessaires à chaque usine sont respectivement de 400,
300 et 200 tonnes. La quantité hebdomadaire qui arrive au port de Bejaia est de 550 tonnes,

12
et elle est de 350 tonnes à Annaba. Les coûts de transport d'un port à une usine sont donnés
dans le tableau suivant :

Le port Localisation de l’usine

Bouira (1) Sétif (2) Biskra (3)
Bejaia (1) 100 90 150
Annaba (2) 140 130 170
Couts de transport en Dinar par tonne

Le but est de déterminer les poids de blé à envoyer à chaque usine depuis chaque port afin
que :
• chaque usine reçoive, au moins, la quantité du blé qu'elle demande
• les quantités demandées à chaque port n'excèdent pas les quantités disponibles
• le coût total de transport soit minimum

On admet : xij est la quantité du blé transporté du port i a l’usine j avec un prix par tonne Cij.
Si est la quantité du blé disponible dans le port i, et Dj et la quantité demandée par l’usine j.
Pour simplifier la compréhension du problème, la Figure 1.2 schématise le plan de transport
qui doit être optimisé en déterminant les quantités optimales xij.

x11
Usine de Bouira (1)
C11=100 x21 D1 = 400
Port de Bejaia (1) C12=90
S1 = 550 C13=180 x12
Usine de Sétif (2)
C21=140 x22
D2 = 300

Port de Annaba (2) C22=130

x13
S2 = 350 C23=170
Usine de Biskra (3)
x23
D3 = 200

Figure 1.2 Plan de transport de l’exemple 1.5

13
Pour formuler le PL sous forme mathématique, nous associons l’indice i avec les ports (point
de départ), et l’indice j avec les usines (point d’arrivée). n et m sont les nombres totales des
ports et des usines respectivement. Les contraintes de demande de chaque usine j imposent :
n
xij Dj (1.26)
i 1

Les contraintes sur le stock disponibles dans les ports

m
xij Si (1.27)
j 1

Les contraintes de non-négativités

xij 0 i, j (1.28)

Le cout total du transport à optimiser

n m
Min z Cij xij (1.29)
i 1 j 1

En introduisant les valeurs numériques de l’exemple 1.5, le PL s’écrit :

Min z 100 x11 90 x12 180 x13 140 x21 130 x22 170 x23
souscontraintes
x11 x21 400
x12 x22 300
(1.30)
x13 x23 200
x11 x12 x13 550
x21 x22 x23 350
xij 0, i 1,2 j 1,2,3

1.3 PL continu, PL discret et PL mixte

Un programme linéaire est dit continu lorsque tous c’est variables de décisions
appartiens à un ensemble continue des nombre réels. Si en revient à l’exemple précédant, le
problème de transport, la quantité de blé transport d’un port à une usine peut être 0, 20.8, ou
55.785 tonnes. Dans ce cas la, le problème de transport est dit continu. Supposant maintenant
que le blé arrive au port dans des sacs de 500kg, on ne peut pas expédier 55.785 tonnes car sa
nécessite l’ouverture d’un sac pour extraire 285 kg du blé supplémentaire. Cependant, en peut
résoudre se problème en supposant que x, le variable de décision, appartient à un ensemble

14
discret composé des multiple de 0.5 tonne, x (0, 0.5, 1, 1.5, 2, 2.5, ….., N×0.5). Dans ce cas,
le programme linéaire est dit discret.

Maintenant, supposons que dans le port de Bejaia, le blé arrive en vrac, tandis que dans le port
de Annaba arrive conditionner en sac de 500kg. Dans ce cas, les variables de décision liées au
port de Béjaia, à savoir x11, x12 et x13 appartient à un ensemble continu, tandis que les variables
liées au port d’Annaba, x21, x22 et x23 appartiennent à un ensemble discret. Le programme
linéaire dans ce cas est dit mixte car il contient des variables continues et des variables
discrets.

1.4 Résolution graphique

La résolution graphique est une approche simple et facile. La procédure consiste à

tracer les isolines (contours) de la fonction objectif et des contraintes. La région réalisable (à
définir par la suite) et la solution optimale peuvent être identifiées visuellement. A noter que
la résolution graphique des PLs devient impossible à réaliser si le nombre des variables de
décision augment.

Il existe 4 types de solution qu’un PL peut avoir : 1-une solution unique, 2-un segment de
solutions, 3-solution inexistante, 4-solution à l’infinie. Nous allons étudier ces quatre solutions
en utilisant des exemples.

1.4.1 Solution unique

Considérons le problème suivant :

Min z x1 2 x2
souscontraintes
4 x1 6 x2 9 (1.31)
x1 x2 4
x1 , x2 0

Afin de résoudre le PL de l’Eq. (1.31), nous cherchons tous d’abor l’ensemble des solutions
qui satisfassent la première contrainte. Pour se faire, nous traçons la droite –4x1+6x2=9, et
nous déterminons la zone ou chaque paire (x1, x2) satisfaite la contrainte –4x1+6x2 9. Il est
clair que cette zone ce situe en bas de la droite, comme indiquer dans la Figure 1.3a.

15
 Figure 1.3a En gris, zone des solutions qui Figure 1.3b En gris, zone des solutions qui
satisfassent la première contrainte. satisfassent la deuxième contrainte.

Figure 1.3c En gris, zone des solutions qui Figure 1.3d Isolines de la fonction objectif.
satisfassent les contraintes de non-négativités.

Figure 1.4 Région des solutions réalisables ainsi que la localisation de la solution optimale.

16
Nous ferons la même chose pour la deuxième contrainte, nous posons x1+x2=4, on cherche la
zone qui satisfait la contrainte x1+x2 4. C’est la zone en gris dans La Figure 1.3b. Les
contraintes de non-négativités imposent que les solutions doivent appartenir à l’hyperoctant
positif défini dans la Figure 1.3c. La dernière étape consiste à tracer les isolines de la fonction
objectif z. Pour ce faire, il suffit de donner une valeur à z = Cst puis tracer la droite
x1– 2x2 = Cst. En variant la valeur à donner à z comme indiquer dans la Figure 1.3d, il est
possible de déterminer la direction ou la fonction objectif diminue. L’intersection des zones en
gris définis dans les Figure 1.3a, b et c donne se qu’on appelle la Région Réalisable. Elle est
caractérisée par le fait que chaque paire de points (x1, x2) satisfait toutes les contraintes du PL
défini en Eq. (1.31). En suivant la direction de diminution de la fonction objectif (direction
perpendiculaire au isolines), on peut déterminer visuellement la solution optimale qui est le
point le plus loin en cette direction (le point d’intersection des deux contraintes).

1.4.2 Un segment de solutions

Examinant cet exemple :

Min z x1 2 x2
souscontraintes
0.5 x1 x2 2 (1.32)
x1 x2 4
x1 , x2 0

La résolution graphique du PL de l’Eq. (1.32) est présenté dans la figure 1.5.

Figure 1.5 PL avec un segment de solutions optimales.

17
Les isolines de la fonction objectif ainsi que la première contrainte ont la même pente. De ce
fait, lorsqu’on cherche le point le plus loin en direction de la diminution de la fonction
objectif, touts les point situent sur segment AB ont la même valeur de la fonction objectif.
Puisque ces points satisfassent toutes les contraintes (sont inclus dans la région réalisable), ils
sont considérés comme des solutions optimales (segment de solutions). De point de vue
pratique, puisqu’il est impossible de réalisée toutes les solutions, il suffit de prendre une
solution appartenant au segment de solution et travailler avec.

1.4.3 Solution inexistante

Considérons se programme linéaire :

Min z x1 2 x2
souscontraintes
0.5 x1 x2 3 (1.33)
x1 x2 2
x1 , x2 0

En déterminant graphiquement les zones de satisfaction des contraintes du PL ci-dessus, il est

observable que se problème n’a pas une région réalisable. On dit que ce PL n’a pas de solution
réalisable.

Figure 1.6 Programme linéaire sans région réalisable.

18
1.4.4 Solution à l’infinie

Considérons se problème de maximisation :

Max z x1 2 x2
souscontraintes
0.5 x1 x2 3 (1.34)
x1 x2 2
x1 , x2 0

La région des solutions réalisable du PL ci-dessus est la zone colorée en gris illustré dans la
Figure 1. 7. En suivant la direction d’augmentation de la fonction objectif (puisque en a un
problème de maximisation), il est impossible de trouver une solution optimale. La région
réalisable n’a pas de limite en direction d’augmentation de la fonction objectif, elle étendue
vers l’infinie. Il suffit d'attribuer des valeurs à x1 et x2 suffisamment grandes toute en gardant
les contraintes satisfaites. La valeur de la fonction objectif peut être augmentée indéfiniment.
On dit que le Pl à une solution à l’infinie.

Figure 1.7 PL avec solution à l’infinie.

1.5 Résolution par la méthode Simplexe

1.5.1 Mise en forme d’un PL

Forme canonique : On dit que le PL est sous forme canonique lorsqu’on a une fonction à
maximiser sous contraintes d’inégalités de type .

19
 n
Max z cjxj
j 1

souscontraintes
n
(1.35)
aij x j bi i 1,2,..., m
j 1

xj 0 j 1,2,..., n

En général, un PL peut avoir une fonction objectif à maximiser ou à minimiser, sous

contraintes de type , et =. Quelque soit le PL, il est possible de l’écrire sous forme
canonique en adoptant les règles de conversion suivant :

1. Si on a une fonction objectif à minimiser, elle est converti à une fonction à maximiser
en la multipliant par –1 (voir l’Eq. 1.2).
n n
Min z cjxj Max z cjxj (1.36)
j 1 j 1

2. Si on a une contrainte de type , elle est multiplier par –1 pour quelle devient une
contrainte de type .
n n
aij xi bi aij xi bi (1.37)
j 1 j 1

3. Si on a une contrainte de type =, elle est décomposée en deux contraintes de type et

, puis la contrainte de type est converti aussi en utilisant la règle précédente.
n n
aij xi bi aij xi bi
n
j 1 j 1
aij xi bi n n
(1.38)
j 1
aij xi bi aij xi bi
j 1 j 1

Considérant l’exemple suivant :

Min z 3 x1 2 x2
souscontraintes
2 x1 4 x2 3
(1.40)
4 x1 7 x2 5
x1 2 x2 6
x1 , x2 0

20
La fonction objectif est à minimiser, elle doit être converti à maximiser

Min z 3x1 2 x2 Max Z 3 x1 2 x2 avec Z = –z.

La première contrainte est de type , donc il n’a rien a changer.

La deuxième contrainte est de type , elle converti en la multipliant par –1

4 x1 7 x2 5 4 x1 7 x2 5

La troisième contrainte de type =, est converti comme suivant

x1 2 x2 6 x1 2 x2 6
x1 2 x2 6
x1 2 x2 6 x1 2 x2 6

Donc, le PL de l’Eq. (1.40) s’écrit sous la forme canonique suivante :

Max Z 3x1 2 x2
souscontraintes
2 x1 4 x2 3
4 x1 7 x2 5 (1.41)
x1 2 x2 6
x1 2 x2 6
x1 , x2 0

Forme standard : le PL est dit sous forme standard lorsqu’il s’agit de maximiser une fonction
objectif sous un ensemble de contraintes d’égalité (de type =). Sa forme mathématique est la
suivante :

n
Max z cjxj
j 1

souscontraintes
n
(1.42)
aij x j bi i 1,2,..., m
j 1

xj 0 j 1,2,..., n

21
L’algorithme de résolution qu’on va présenter dans cette section, à savoir l’algorithme
Simplexe, exige que le PL soit écrit sous forme standard avec des bi positifs. Dans un cas
générale, la conversion des contraintes d’inégalités (de types et ) à des contraintes d’égalité
se fait par l’introduction des variables d’écarts.

Variable d’écart : C’est une variables non-négatives introduite dans une inégalité pour la
transformer en contrainte d’égalité. Les règles d’introduction des variables d’écarts sont :

1- Si on a une contrainte de type , nous ajoutant une variable d’écart (e1) à l’équation :
ai1 x1 ai 2 x2 ... ain xn bi ai1 x1 ai 2 x2 ... ain xn e1 bi (1.43)
2- Si on a une contrainte de type , nous soustrayant une variable d’écart (e1) à
l’équation :
ai1 x1 ai 2 x2 ... ain xn bi ai1 x1 ai 2 x2 ... ain xn e1 bi (1.44)

Considérant le PL précédant donné par l’Eq (1.40). La forme standard du PL s’écrit de la

façon suivante :

La fonction objectif est à minimiser, elle doit être converti à maximiser :

Min z 3x1 2 x2 Max Z 3 x1 2 x2 avec Z = –z.

La première contrainte est de type , donc en ajoute une variable d’écart, soit e1 :

2 x1 4 x2 3 2 x1 4 x2 e1 3

La deuxième contrainte est de type , donc en soustrait une variable d’écart, soit e2 :

4 x1 7 x2 5 4 x1 7 x2 e2 5

La troisième contrainte et de type =, on a rien à ajouter comme variable d’écart. Par contre, le
second membre de l’inégalité est négatif, donc, on multiplie la contrainte par –1 pour avoir
une bi positif :

x1 2 x2 6 x1 2 x2 6

La forme standard de PL donné par l’Eq. (1.40), s’écrit comme suit :

22
 Max Z 3x1 2 x2 0e1 0e2
sous contraintes
2 x1 4 x2 e1 3
(1.45)
4 x1 7 x2 e2 5
x1 2 x2 6
x1 , x2 , e1 , e2 0

Les variables d’écart peuvent être introduites dans la fonction objectif en imposant un
coefficient nul (zéro).

Variable sans restriction du signe : Dans certain problème, une ou plusieurs variables de
décision peuvent être sans restriction de signe, c-a-dire, elles admettent des valeurs négatives.
Or l’algorithme de Simplex ne résout que des problèmes avec des variables de décision non-
négatives. Il est possible de décomposer une variable de décision sans restriction de signe en
deux variables de décision distingues non-négatives :

xj xj xj
avec
xj maximum(0, x j ) (1.46)
xj maximum(0, x j )
xj , xj 0

Considérons maintenant le PL suivant

Min z x1 2 x2
sous contraintes
x1 4 x2 5
(1.47)
2 x1 3 x2 4
x1 0
x2 sans restriction de signe

Pour mettre le PL précédant sous forme standard, il faut suivre les étapes suivant :

1- Transformer le problème de minimisation en un problème de maximisation :

Min z x1 2 x2 Max Z x1 2 x2
2- Introduire une variable d’écart à la contrainte d’inégalité :

23
 x1 4 x2 5 x1 4 x2 e1 5
3- Rien a faire pour la deuxième contrainte, elle sous forme d’égalité.
4- La variable x2 est sans restriction de signe, donc on doit la décomposer comme
suivant : x2 x2 x2
5- Appliqué la décomposition à l’ensemble des équations du PL :

Max Z x1 2 x2 x2
sous contraintes
x1 4 x2 x2 e1 5
2 x1 3 x2 x2 4
x1 , x2 , x2 , e1 0

Après simplification, notre problème sous forme standard s’écrit :

Max Z x1 2 x2 2 x2
sous contraintes
x1 4 x2 4 x2 e1 5 (1.48)
2 x1 3x2 3 x2 4
x1 , x2 , x2 , e1 0

Forme matricielle d’un PL standard : Considérant un programme linéaire sous forme

standard :

n m
Max z ci xi 0 ei
j 1 i 1

sous containtes
m
aij x j ei bi (1.49)
j 1

avec
x j 0, j 1,2,..., n
ei 0, i 1,2,..., m

24
Il est possible d’écrire le PL standard précédant sous forme matricielle :
Max z CX
sous containtes
AX B (1.50)
avec
X 0

Tel que X est un vecteur colonne qui rassemble les variables de décision et les variables
d’écart dont la dimension est (n+m)×1 :

T
X x1 , x2 ,..., xn , e1 , e2 ,..., em (1.51)

C est un vecteur ligne des coefficients de la fonction objectif de dimension 1×(n+m) :

C c1 , c2 ,..., cn ,0,0,...,0 (1.52)

m fois

La matrice A rassemble les coefficients des contraintes de dimension m×(n+m) :

a11 a12 a13 a1n 1 0 0

a21 a22 a23 a1n 0 1 0
A (1.53)

am1 am2 am3 amn 0 0 1

m n m m

Le vecteur colonne B regroupe les seconds membres des contraintes (m×1)

T
B b1 , b2 ,..., bm (1.54)

Considérant le PL suivant qu’est la forme standard du PL donne par l’Eq. (1.31) :

Max z x1 2 x2
souscontraintes
4 x1 6 x2 e1 9 (1.55)
x1 x2 e2 4
x1 , x2 , e1 , e2 0

25
Pour écrire ce PL sous forme matricielle, on a :

T
X x1 , x2 , e1 , e2 (1.56)

C 1,2,0,0 (1.57)

4 6 1 0
A (1.58)
1 1 0 1

T
B 9,4 (1.59)

Il suffit maintenant d’introduire ces composants dans l’Eq. (1.50).

1.5.2 Bases et solutions de base d’un PL

Soit un programme linéaire standard avec à un nombre de variables à optimiser égale à

N, et un nombre de contraintes égale à M avec N M. Une solution de base pour ce système
peut être obtenue da la manière suivante :

1- On pose un nombre de variables (N – M) égale à 0 (dans certain cas, ce nombre de

variables peut être n). Ces variables sont appelées Variables Hors Base (VHB).
2- On résout le système d’équations (contraintes) pour les M variables restantes, ces
variables sont appelées Variables de Base (VB). Il est important d’avoir le nombre des
VB égale au nombre des contraintes.
3- Le vecteur des variables obtenus X, qui contient les VHB et les VB, est appelé solution
de base.

Une solution de base est admissible si toutes les variables de la solution de base sont positives
(X 0).

Si une solution de base est admissible, alors les valeurs des variables de décisions xi du
vecteur X représentent un point extrême de la région réalisable.

Considérant maintenant le PL standard donné par l’Eq. (1.55). Les variables à optimiser sont
x1 et x2 (variables de décisions) en plus de e1 et e2 (variables d’écarts). Au total, le vecteur X
est composé de 4 variables (N = 4). Le PL contient 2 contraintes (M = 2). Le nombre des

26
variables hors base qui doivent être mis égale à 0 est de N – M = 4 – 2 = 2. Le nombre des
variables de base dont leur valeurs doivent être déduite de la résolution du système des
contraintes AX = B, est de M = 2.

Prenons maintenant les contraintes seules :

4 x1 6 x2 e1 9
(1.60)
x1 x2 e2 4

Si on pose x1 = x2 = 0 comme VHB, est on les remplace dans l’Eq. (1.60)

4 0 6 0 e1 9
0 0 e2 4

Il est facile de déterminer les valeurs des VB, e1 et e2. Dans ce cas la, e1 = 9 et e2 = 4. La
solution X = [0, 0, 9, 4]T est dit solution de base admise car toutes ces composants sont non-
négatives.

Considérons maintenant x1 et e1 des VHB (x1 = e1 = 0), les valeurs des VB obtenues après
remplacement des VHB dans l’Eq. (1.60) sont x2 = 3/2 et e2 = 5/2. Le vecteur X = [0, 3/2, 0,
5/2] T est une solution de base admise aussi.

Si on prend x2 et e1 comme VHB. Les valeurs des VB serons x1 = –9/4 et e2 = 25/4. Le

vecteur X = [–9/4, 0, 0, 25/4] est une solution de base non-admise car une de ces composantes
est négative (x1 = –9/4 < 0). En variant notre sélection des variables hors base, il est possible
de déterminer l’ensemble des solutions de bases indiqué dans le Tableau 1.3.

Tableau 1.3 Liste des solutions de bases et des points extrêmes.

N° x1 x2 e1 e2 VHB VB Solution Admise Point extrême
de base (x1, x2)
1 0 0 9 4 x1, x2 e1, e2 Oui Oui (0,0)
2 0 3/2 0 5/2 x1, e1 x2, e2 Oui Oui (0,3/2)
3 0 4 –15 0 x1, e2 x2, e1 Oui Non ×
4 –9/4 0 0 25/4 x2, e1 x1, e2 Oui Non ×
5 4 0 25 0 x2, e2 x1, e1 Oui Oui (4,0)
6 3/2 5/2 0 0 e1, e2 x1, x2 Oui Oui (3/2,5/2)

27
Pour chaque solution de base admise, les valeurs des variables de décision, xi, représentent un
point extrême de la région réalisable. Par exemple, le point extrême de la solution de base X =
[0, 3/2, 0, 5/2] T est la paire (0,3/2). Le Tableau 1.3 liste tout les solutions de bases possibles,
ainsi que les points extrêmes. En générale, les points extrêmes représentent les points
d’intersection des droites représentatives des contraintes, appartenant à la région réalisable
(voir la Figure 1.8). Les points d’intersection des contraintes loin de la région réalisable ne
sont pas des points extrêmes.

Figure 1.8 Tous les points encerclés sont des points extrêmes

1.5.3 Algorithme du Simplexe

Afin de comprendre l’ensemble des étapes de l’algorithme de simplexe, nous allons le

présenter sous forme exemple à résoudre étape par étape avec explication. Considérons
maintenant cet exemple :

Min z 25 x1 15 x2
sous contraintes
2 x1 2 x2 240 (1.61)
3 x1 x2 140
x1 , x2 0

1er étape : écrire le PL sous forme standard. Dans ce cas l’Eq. (1.61) devient :

28
 Max z 25 x1 15 x2 0e1 0e2
sous contraintes
2 x1 2 x2 e1 240 (1.62)
3 x1 x2 e2 140
x1 , x2 , e1 , e2 0

2ème étape : traçage du tableau de simplexe et le remplir. Pour ce faire, on commence à

chercher une solution de base admise. La plus simple est de poser x1 = x2 = 0, puis calculer e1
et e2 à partir des contraintes d’égalité. Dans ce cas notre solution de base et X = [0, 0, 240,
140], tel que x1 et x2 sont des variables hors base, tandis que e1 et e2 sont de variable de base.
Par la suite, on dresse un tableau et on le rempli comme de la manière suivante :

1- Reporter les coefficients Cj de la fonction objectif dans la ligne en rouge.

2- Introduire les variables de base dans la colonne bleue, dans ce cas e1 et e2.
3- Recopie les coefficients Cj correspondants aux variables de base (e1 et e2) dans la
colonne orange.
4- Introduire dans la colonne marron les quantités (Q) de la solution de basse
correspondante aux variables de base, dans ce cas e1 = 240 et e2 = 140.
5- Reporter les coefficients aij des contraintes d’égalité de l’Eq. (1.62) dans le tableau
noir.

Tableau du simplexe N°0

Cj 25 15 0 0
Cj (VB) VB Qj x1 x2 e1 e2 Rt
0 e1 240 2 2 1 0
0 e2 140 3 1 0 1
Zj
C j – Zj

2ème étape : démarré la première itération. Pour ce faire, on doit calculer les Zj ainsi que les
Cj – Zj.

La première case de la ligne violète des Zj est calculer a partir de la formule suivante :

29
Zj C j (VB ) Q j (1.63)

Cette première case, généralement donne la valeur de la fonction objectif pour la solution de
base considérée. Pour le reste des cases, on utilise cette formule

Zj C j (VB ) aij (1.64)

Le résultat de calcule est présenter dans le Tableau de simplexe N°1

Tableau de simplex N°1

Cj 25 15 0 0
Cj (VB) VB Qj x1 x2 e1 e2 Rt
0 e1 240 2 2 1 0
0 e2 140 3 1 0 1
0×240+ 0×2+ 0×2+ 0×1+ 0×0+
Zj
0×140= 0 0×3 = 0 0×1= 0 0×0= 0 0×1= 0
C j – Zj

Par la suite nous calculons la différance Cj – Zj est on reporte leur valeur dans la colonne
jaune. On constate que la premier valeur des Zj n’a pas un Cj qui lui correspond, c’est pour
cela on ne la calcule pas. L’objectif ici, est de trouver la variable entrante dans la base (VE).
Le résultat de calcule des Cj – Zj est présenté dans le Tableau de simplex N°2.

Tableau de simplex N°2

Cj 25 15 0 0
Cj (VB) VB Qj x1 x2 e1 e2 Rt
0 e1 240 2 2 1 0
0 e2 140 3 1 0 1
Zj 0 0 0 0 0
C j – Zj 25–0=25 15–0= 15 0 – 0= 0 0 – 0= 0

Variable entrante (VE)

30
La variable entrante dans la base est x1 puisqu’elle a la valeur Cj – Zj la plus élevé.

La variable sortant de la base (VS), qui va être remplacé par la variable entrante (VE) est
obtenus on calculant le ratio Rt, colonne vert. Ce dernier est calculé en divisant les quantités
(Qj), sur les aij de la variable entrante.

Rt Q j / aij (VE ) (1.65)

Après calculer des Rt, la variable sortante est celle dont le ratio Rt a la valeur la plus faible.
Dans notre exemple, on voit dans le tableau de simplexe N°3 qu’e2 est la variable sortante.

Le Pivot est la valeur de l’intersection de linge de la variable sortante et la colonne de la

variable entrante. Dans ce cas le Picot = 3.

Tableau de simplexe N°3.

Cj 25 15 0 0
Cj (VB) VB Qj x1 x2 e1 e2 Rt
240/2
0 e1 240 2 2 1 0

Variable sortante (VS)

=120

e2 140 3 1 0 1 140/3
0
=46.666
Zj 0 0 0 0 0
C j – Zj 25 15 0 0

Variable entrante (VE) Pivot

Après détermination de VE, VS et Pivot, on passe à la deuxième itération.

3ème étape : enchainer avec la deuxième itération. Pour ce faire, il faut : un, dresser un
nouveau tableau de simplexe vierge, deux, remplacer la variable sortante e2 par la variable
entrante x1. Trois, recopier les coefficients Cj dans la ligne et dans la colonne avec les valeurs
correspondant aux nouveau variable de base, 0 pour e1 et 25 pour x1 (voir Tableau de simplex
N°4). Quatre, remplir le reste du tableau en suivant les règles suivantes :

31
1- Les lignes hors ligne du pivot (ou la ligne de la nouvelle variable entrante, dans ce cas
x1, voir Tableau de simplexe N°4), sont rempli en utilisant cette équation pour calculer
les quantités Qj, et les coefficients aij:
Pl Pc
NV AV
Pivot
NV : Nouvelle Valeur
AV : Ancienne Valeur (1.66)
Pl : Projection sur ligne
Pc : Projection sur colonne
Pivot : Valeur du pivot

Par exemple, pour calculer la nouvelle valeur de Q1, on l’ancienne valeur est 240 (on
rouge, voir la Figure 1.9). La projection de cette valeur sur la ligne donne 140, la
projection sur la colonne est 2, le pivot est 3. En appliquant la règle de l’Eq. (1.66), on
a : NV = 240 – ((140×2)/3) = 440/3.
Pour la case suivante (juste en bas de x1), l’ancienne valeur est 2, la projection sur la
ligne est 3, la projection sur colonne donne 2 (la valeur elle-même), le pivot est
toujours 3, l’application de la l’Eq. (1.66) donne : NV = 2 – ((3×2)/3) = 0.
La même règle est utilisée pour remplir le reste de la ligne et toute autre ligne hors
ligne du pivot s’il en a.
2- Pour la ligne du pivot, la nouvelle valeur est calculée en divisant l’ancienne valeur sur
le pivot :
NV AV / Pivot (1.67)

Figure 1.9 Schéma de calcule des nouvelle valeurs

32
Le Tableau de simplexe N°4 représente les nouvelle valeurs calcules a la base des règles
précédente.

Tableau de simplex N°4

Cj 25 15 0 0
Cj (VB) VB Qj x1 x2 e1 e2 Rt
240– 2– 2– 1– 0–
0 e1 ((140×2)/3) ((3×2)/3) ((1×2)/3) ((0×2)/3) ((1×2)/3)
=440/3 =0 =4/3 =1 =–2/3
25 x1 140/3 3/3=1 1/3 0/3=0 1/3
Zj
C j – Zj

Par la suite, les Zj ainsi que les Cj – Zj sont calculés de la même façon que la 2ème étape. Les
résultats de calcule sont présentés dans le Tableau de simplexe N°5

Tableau de simplex N°5

Cj 25 15 0 0

Variable sortante (VS)

Cj (VB) VB Qj x1 x2 e1 e2 Rt
(440/3)/(4/3)
0 e1 440/3 0 4/3 1 –2/3
= 110
(140/3)/(1/3)
25 x1 140/3 1 1/3 0 1/3
= 140
0×440/3 + 0×0 + 0×4/3 + 0×1 + 0×(–2/3)
Zj 25×140/3 25×1 25×1/3 25×0 +25×1/3
= 3500/3 = 25 = 25/3 =0 = 25/3
25 – 25 15 – 25/3 0–0= 0 – 25/3
C j – Zj
=0 = 20/3 0 = –25/3

Variable entrante (VE)

33
Après calcule des Cj – Zj , la nouvelle variable entrante est déterminée sur la base de la valeur
la plus grande, Maximum (Cj – Zj ), dans ce cas c’est x2.

En sachant VE, il est possible de designer la variable sortante en calculant le ratio Rt. Dans
notre exemple, la VS est e1.

L’intersection de la ligne VS-colonne VE donne le nouveau pivot 4/3.

3ème étape : continuation des itérations. En connaissant VS, VE et pivot, nous reprenons le
même chemin que la 2ème étape. C'est-à-dire, redessiner un nouveau tableau, remplacer VS par
VE, remplir le tableau en utilisant les mêmes régale que la 2ème étape, déterminer les nouveau
VE, VS et Pivot. Le résultat de la troisième itération est présenté dans le Tableau de simplex
N°6.

Tableau de simplex N°4

Cj 25 15 0 0
Cj
VB Qj x1 x2 e1 e2 Rt
(VB)
(440/3)/(4/3) 0/(4/3) (4/3)/(4/3) 1/(4/3) (–2/3)/(4/3)
15 x2
= 110 =0 =1 = 3/4 = –1/2
(140/3) – 1– (1/3)– 0– (1/3)– ((-
25 x1 ((440/3)×(1/3)/ (0×(1/3)/ ((4/3)×(1/3)/ (1×(1/3)/ 2/3)×(1/3)/
(4/3))= 10 (4/3))= 1 (4/3))= 0 (4/3)=-1/4 (4/3))= 1/2
(15×110)+ (15×0)+ (15×1)+ (15×3/4)+ (15×(-1/2))
Zj (25×10) (25×1) (25×0) (25×(-1/4) +(25×(1/2)
= 1900 = 25 = 15 =5 =5
25 – 25 15 – 15 0–5 0–5
C j – Zj
=0 =0 = –5 = –5

4ème étape : critère d’arrêt. Les itérations s’arrêtent lorsque tous les Cj – Zj sont inférieur ou
égale à zéro Cj – Zj 0. Dans le Tableau de simplex N°4, on voit que tous les Cj – Zj 0. Le
critère est vérifié, donc on arrêt les itérations.

34
Tableau de simplex N°4
Cj 25 15 0 0
Cj
VB Qj x1 x2 e1 e2 Rt
(VB)
15 x2 110 0 1 3/4 –1/2
25 x1 10 1 0 –1/4 1/2
Zj 1900 25 15 5 5
C j – Zj 0 0 –5 –5

La Solution La valeur de la fonction objectif

Après vérification du critère d’arrêt, nous pouvons facilement récupérer notre solution et la
valeur de la fonction objectif à partir de dernier tableau. Comme en vois ci-dessus, la solution
est x1 = 10 et x2 = 110, et la valeur optimale de la fonction objectif est Z = 1900.

Il est important de noter qu’initialement, notre PL s’agit d’un problème de minimisation (voir
l’Ea. 1.61), or que nous l’avons converti en un problème de maximisation pour le résoudre en
utilisant l’algorithme de simplexe (voir l’Eq. 1.62). Donc, pour retrouver la valeur optimale de
la fonction objectif du problème initiale, à savoir l’Eq. 1.61, il faut juste multiplier la valeur de
obtenu par l’algorithme simplexe par –1. Dans notre cas z = –1900. Pour vérifier la certitude
de la solution, il sufi de remplacer la solution dans les équations du problème : condition
satisfaite

z 25 (10) 15 (110) 1900

sous contraintes
2 (10) 2 (110) 240 (condition satisfaite)
3 (10) 1 (110) 140 (condition satisfaite)
(10 ) et (110) 0 (condition satisfaite)

35