PARTIE 1 

: PROGRAMMATION LINEAIRE ET ALGORITHME DE SIMPLEXE

Les problèmes de programmation linéaire consistent généralement à déterminer l’allocation

optimale d’un ensemble de ressources (main d’œuvre, machines, matériaux, capitaux, …)
pour atteindre un objectif (maximisation d’un résultat, minimisation d’un coût) en fonction
de contrainte pesant sur ces ressources, …).

I. CONSTRUCTION D’UN PROGRAMME DE RESOLUTION GRAPHIQUE

La formulaire d’un programme linéaire doit respecter 3 phases :

- La détection du problème à traiter et l’identification des variables ;
- La formulation de la fonction objectif (la fonction à optimiser) ;
- La formulation des contraintes
Pratiquons cette approche par le biais d’un exemple.

1. Détermination d’un programme de fabrication à 2 variables.

Une usine est spécialisée dans la production de 2 types de pièces p1 et p2. Ces pièces
doivent être travailler dans 2 ateliers successifs A1 et A2. Techniquement, en ce qui
concerne la ressource temps de travail et sa consommation, la situation se présente comme
suit (en heures de travail effectif) :

A1 A2
P1 3 6
P2 4 3
Total hebdomadaire 160 180
disponible dans chaque
atelier

Comme les pièces ne sont livrés qu’au tout début de la semaine suivante, le stockage des
pièces produite est nécessaire. L’aire disponible est de 400m 2. Les pièces ne peuvent être
empilés et requiert par unité 5m2 et 4m2 respectivement pour P1 et P2.
On pense pouvoir écouler sur le marché chaque semaine 40 P1 et 35 P2. La marge
bénéficiaire unitaire prévu est de 1200f pour P1 et 1000f pour P2. Quelle production de
chaque type de pièces faut-il réaliser pour maximiser la marge (bénéfice) hebdomadaire de
l’usine.
 a) Détermination du problème et identification des variables

Il faut déterminer le programme de fabrication qui maximise la marge hebdomadaire de

l’usine. Les 2 variables pertinente au problème sont :
X1=quantité de P1 à fabriquer
X2= quantité de P2 à fabriquer
On peut les appeler indifféremment variables principales, d’activités ou réel

b) Formulation de la fonction objectif

Elle traduit l’objectif poursuivi par l’entreprise. Ici il s’agit de maximiser la marge bénéficiaire
hebdomadaire, d’où :

Z=1200 X1 + 1000 X2

c) Formulation des contraintes

 Contrainte de temps de travail :

- Pour A1 : 3 X1 + 4 X2 < 160
- Pour A2 : 6 X1 + 3 X2 < 180
-
 Contrainte d’espace
- 5 X1 + 4 X2 < 400

 Contrainte de marché :
- X1 <= 40
- X2 <= 35

 Contrainte logique :
- X1 > 0
- X2 >0

Taff : {

Définir 

a- Variables d’activités
b- Contraintes

Le programme de fabrication sous la forme canonique (avec des inéquations) est donc le
suivant :
 MaxZ=(1200 X1 + 1000 X2)

Contraintes :

3 X1 + 4 X2 < 160
6 X1 + 3 X2 < 180
5 X1 + 4 X2 < 400
X1 <= 40
X2 <= 35
X1 > 0
X2 >0

2. Résolution graphique

Quand le problème ne comprend que 2 variables principales (3 au maximum), la résolution

graphique est possible. La procédure à suivre est la suivante :

a- Réaliser un repère orthogonal dont les axes correspondent aux variables x1 et x2.
b- Tracer la région des solutions réalisables délimitées par toutes les contraintes au problème
posé :
- Si cette région représente un ensemble convexe ouvert, alors pour un problème de
maximisation ou de minimisation, il peut exister une solution optimale qui se situe à l’un des
points extrêmes de la région. Mais, si cette région est un ensemble convexe fermé, alors il
existe toujours une solution optimale ;
- Si cette région représente un ensemble non convexe, aucune solution n’existe à cause de
l’incompatibilité du système de contrainte

Rappel : un ensemble convexe est un ensemble de points qui a la propriété suivante : tout
segment de droite reliant deux points dans l’ensemble est aussi entièrement dans l’ensemble.
Un point extrême est un sommet d’un ensemble convexe.

Ensemble convexe fermé Ensemble convexe ouvert

c- Trouver tous les points extrêmes de l’ensemble convexe

d- Déterminer en utilisant la fonction-objectif, quel point extrême donne la solution optimale
 45

40

35

30

25

20

15

10

0
0 10 20 30 40 50 60

x 1=40

Nous obtenons une région de solution réalisable OABCD qui forme un ensemble convexe
fermé. Une solution optimale existe et se situe à l’un des points extrêmes.

Coordonnées des points extrêmes

 Les coordonnées du point O sont : x1=0 et x2=0

 Les coordonnées du point A sont solution du système

3x1+4x2=160 3x1+ (4*35) =160

X2=35 x2=35

e- Évaluation de la fonction objectif à chacun des points obtenues

Points solutions Coordonnées Z=1200x1 + 1000x2

Données x1 Données x2
O 0 0 0
A 0 55 35000
B 20/3 35 43000
C 16 28 47200
D 30 0 36
000
La solution optimale se situe donc au point C de coordonnées x1=16 et x2=28. Par conséquent,
l’usine devra fabriquer 16 pièces p1 et 28 pièces p2 pour réaliser une marge hebdomadaire
maximum de 47200fr (en tenant compte de toutes les contraintes)

Remarque : Nous voyons sur le graphique que la contrainte (3) : 5X1 + 4 X2 <= 400 se situe en dehors
de la région des solutions réalisables. On dit qu’elle est redondante. En effet, cette contrainte est
dépassée par les contraintes (4) et (5). Cela signifie que si ces 2 contraintes sont respectées, la
contrainte redondante est nécessairement satisfaite. Elle s’avère donc inutile et peut être éliminé de
la résolution du programme.

Si nous prenons les valeurs extrêmes de x 1 et x2 permises par les contraintes (4) et (5) et que nous les
appliquons à la contrainte (3), nous obtenons : (5*40) + (4*35) = 340 < 400

Dans le cadre de ce programme, la contrainte (3) sera toujours vérifiée ou plus clairement, la
capacité de stockage sera toujours satisfaisante donc elle n’est pas contraignante par rapport au
possibilité d’écoulement des produits sur le marché. Par la suite, après avoir posé le programme sous
la forme canonique, il faudra toujours vérifié qu’il n’y a pas de contrainte redondante afin d’alléger le
programme de base.

Propriétés

Tout programme linéaire peut admettre aucune solution optimale, ou une unique solution
optimale ou plus d’une solution optimale.

Exemple1 : Problème sans solution réalisable

Mx(Z=3x1 + 2x2)

3x1 + x2 <=8 (1)

X1 >=5 (2)

X2 <=10 (3)

X1, x2 >=0

L’intersection des 3 inégalités n’existe pas, il n’y a donc pas de solutions réalisable. Aucune valeur de
x1 et x2 ne peut satisfaire simultanément les 4 contraintes

Exemple2 : Problème à solutions multiples

Mx(Z=x2 - x1)

3x1 + x2 <= -2 (1)

X1 – X2 <= 2 (2)
X1 + x2 <= 5 (3)

X1, x2 >=0

La région des solutions réalisables OABCD est un ensemble convexe fermé. Donc il existe une
solution optimale situé à l’un des points extrêmes. Les coordonnées du points C est solution du
système :

X1 – X2 = 2

X1 + X2 = 5

2X1=7 => X1= (7/2)

(7/2) – X2=2 => - X2 = 2- (7/2) => x2= 3/2

Points solutions Coordonnées Z=X2 – X1

Données x1 Données x2
O 0 0 0
A 0 2 2
B 1 4 3
C 7/2 3/2 -2
D 2 0 -2

Il existe donc 2 solutions optimale situé l’une au point C et l’autre au point D.

Soit Z la fonction objectif du problème de fabrication des pièces P1 et P2. La droite Z=0 d’équation
1200X1 + 1000X2 =0 ; soit X2= est appelé la courbe de la fonction objectif Z. On dit aussi que Z=0
est un isoprofit, c’est-à-dire que tous les points situés sur cette droite procure le même profit ( ici
égale à zéro).

Il y a autant d’isoprofit qu’il y a de valeurs de Z. En effet, pour chaque valeur de Z, nous obtenons une
droite et toutes ces droites sont parallèles puisque la pente de ces droites a=-1,2 est indépendante
de la valeur de Z.

Ici la solution optimale est celle qui correspond à la droite, parallèles à Z=0, la plus éloignée de
l’origine (car on cherche à maximiser Z) tout en ayant un point commun avec la région des solutions
réalisables. Il est évident que pour un problème de minimisation de Z, on essaie de se rapprocher le
plus possible de l’origine tout en ayant au moins un point commun avec la région des solutions
réalisables. Dans ce cas, la droite de la fonction objectif isocoût.
Exemple 3 : Problème avec solution non bornée

Min (Z= -2x1+3x2)

X1 ≤ 5

2x1 – 3x2 ≤ 6

X1,x2 ≥ 0

Valeur des Y
10

0
0 1 2 3 4 5 6 7 8 9 10

-2

-4

La région des solutions réalisables (délimité par des droites de couleur bleu) est un ensemble
convexe ouvert, il existe donc des solutions réalisables. Par exemple, le point A(3,0) est une solution
réalisables. Cependant, il n’existe pas de solution optimale. En effet, on peut augmenter indéfiniment
la valeur de la fonction objectif dans la direction des flèches indiqués sur le graphique. On dit dans ce
cas que la solution est non bornée.

3. Analyse de sensibilité

Une analyse de sensibilité se ramène à la recherche des intervalles de variation possible des
paramètres du programme linéaire sans que la solution optimale ne soit modifiée.

Questions :

- De combien peut-on faire varier le profit engendré par la vente d’une pièce P1 dans le
problème de fabrication des pièces P1 et P2, sans changer la solution optimale ?
 Soit λ la variation de profil engendré par la vente d’une pièces P1. La fonction objectif est égale à
(1200+ λ )X1+ 1000x2. La solution demeure optimale si la pente de la fonction objectif reste
toujours comprise entre les pentes des contraintes 1 et 2. Ce qui est équivalent à dire :

A. ALGORITHME DU SIMPLEXE

La méthode du simplexe est une technique algébrique qui permet de trouver la solution d’un
programme linéaire d’une façon ordonnée et précise ceci quelques soit le nombre de variables
d’activités. C’est une méthode itérative, c’est-à-dire que le même principe sera répété plusieurs fois
jusqu’à la solution optimale (si celle-ci existe). Nous l’expliquerons à l’aide de l’exemple suivant :

Une usine va produire P1, P2, P3 dans 2 ateliers successifs A1 et A2 selon les caractéristiques
techniques et économique suivantes :

A1 A2 Charges Prix de vente

variables
P1 30 unités à 40 unités à 13F 18F
l’heure l’heure
P2 30 unités à 20 unités à 14F 20F
l’heure l’heure
P3 20 unités à 30 unités à 11F 15F
l’heure l’heure
Total d’heures 8 7
disponibles par jour

L’approvisionnement en matières premières et fournitures diverses est suffisant pour la

fabrication de 250 produits par jour. On estime que le marché peut absorber journalièrement au
maximum 90 P1, 60 P2 et 70 P3. Les charges de structures globales sont estimées à 500F par jour de
fabrication.

Déterminé le programme de fabrication quotidien optimum (on raisonnera en minutes en ce

qui concerne les contraintes techniques de fabrication).

1- Présentation du programme sous la forme canonique

a- Détection du problème et identification des variables

Il s’agit de trouver le programme de fabrication qui maximise le résultat journalier de l’usine en

tenant compte de toutes les contraintes :

Résultats journalier= (Marge sur coût variable) – (Charge de la structure)

Nous avons les variables d’activités suivantes :

X1= qté de P1 à fabriquer par jour

X2= qté de P2 à fabriquer par jour

X3= qté de P3 à fabriquer par jour

 b- Formulation de la fonction objectif

Les marges sur coût variables unitaire sont respectivement :(18-13)=5F pour P1

(20-14)=6F pour P2 et (15-14)=4F pour P3

Par conséquent la fonction objectif est : Z= 5 X1 + 6 X2 + 4 X3

c- Formulation des contraintes

Contrainte de temps

 Pour A1 : 2 x1 + 2 x2 +3 x3 ≤480

 Pour A2 : 1.5 X1 + 3 X2 + 2 X3 ≤ 420

Contraintes d’approvisionnement

 X1 + x2 + x3 ≤ 250

Contraintes de marché

 X1 ≤ 90
 X2 ≤60
 X3 ≤70

Non négativité x1 ≥0, X2≥0, X3≥0

La contrainte d’approvisionnement est dépassée par les contraintes de marché. En effet, même si
nous arrivons à vendre le maximum de produit, nous aurons toujours suffisamment
d’approvisionnement pour satisfaire cette demande :

90 + 60 + 70= 220 < 250

Cette contrainte est donc redondante et peut être éliminé du programme de base qui devient :

Max (Z= 5 x1 + 6X2 + 4X3)

2X1 + 2X2 + 3X3 ≤480

1.5X1 + 3X2 + 2X3 ≤420

X1 ≤90

X2 ≤60

X3 ≤70

X1, x2, x3 ≥0

2- Présentation du programme sous la forme standard

La forme standard se caractérise par le fait que toutes les inéquations correspondantes aux
contraintes sont transformées en équations. La transformation s’effectue par l’introduction d’une
autre catégorie de variable : les variables d’écart (e1). Il y a une variable d’écart par contrainte.
Chaque variable d’écart est donc attachée à sa contrainte et prend un sens uniquement par rapport à
celle-ci. La condition de non négativité s’applique à chaque variables d’écart. Le coefficient de la
variable d’écart dans la contrainte où elle est introduite dépend du sens de l’inégalité initiale :

- S’il s’agit d’une contrainte inférieure ou égale (≤), la variable d’écart introduite dans le
membre de gauche a comme coefficient (+1) : la variable d’écart représente ce qu’il faut
ajouter au membre de gauche pour égaliser le membre de droite
- Dans le cas d’une contrainte supérieure ou égale (≥), le coefficient de la variable d’écart est (-
1) : la variable d’écart représente dans ce cas ce qu’il retrancher au membre de gauche pour
retrouver le membre de droite.

Ici le programme de base devient :

Max(Z=5x1+ 6x2+ 4x3 + 0 e1 + 0 e2 + 0 e3 + 0 e4 + 0 e5 )

2X1 + 2X2 + 3X3 = 480

1.5X1 + 3X2 + 2X3 = 420

X1 + e3 = 90

X2 + e4 = 60

X3 + e5 = 70

X1, x2, x3 , e1, e2, e3, e4, e5 ≥0

Ces variables d’écarts n’ont pas de marge sur coût variable unitaire car ce ne sont pas des variables
d’activités. Leurs coefficients dans la fonction objectif sont tous nuls. Par contre, elles ont un sens
dans le cadre de leur contraintes respectives.

e1= temps de travail (en minutes) encore disponible dans A1

e2= temps de travail (en minutes) encore disponible dans A2

e3= complément de P1 pouvant être écoulé sur le marché

e4= complément de P2 pouvant être écoulé sur le marché

e5= complément de P3 pouvant être écoulé sur le marché

3- Application de l’algorithme du SIMPLEXE et disposition pratique des calculs sous forme de

tableau

Chaque tableau représente une solution de base. Pour un problème de maximisation, le tableau
initial représente la situation de départ pour laquelle il n’y a aucune production  : x1=x2=x3=0, ce qui
donne Z=0

a- Le tableau initial P1
 T1 X1 X2 X3 E1 E2 E3 E4 E5 R
E1 2 2 3 1 0 0 0 0 480
E2 1.5 3 2 0 1 0 0 0 420
E3 1 0 0 0 0 1 0 0 90
E4 0 1 0 0 0 0 1 0 60
E5 0 0 1 0 0 0 0 1 70
Δ 5 6 4 0 0 0 0 0 0
(Valeur
de Z)

La structure du tableau T1 est la suivante :

- La partie centrale reproduis la matrice des coefficients techniques (x1 à e5 en horizontal et

E1 à a5 en vertical)
- La colonne R est celle des seconds membres des contraintes : les ressources
- La ligne Δ donne les taux marginaux de substitution (TMS)
- La case située en bas, à droite, donne la valeur de Z pour la solution de base (ici Z=0)
- Les variables en base (e1, e2, e3, e4, e5) ont toutes les vecteurs colonnes unités dans la
matrice des coefficients technique (c’est une des caractéristiques des variables en bases).

Un taux marginal de substitution (TMS) représente la différence entre l’apport marginal d’une
variable hors base et l’apport de l’équivalent en produit en base. Pour cette solution de base :

TMS de x1 = 5 – [ (2*0)+(0*1.5)+(0*1)+(0*0)+(0*0) ]=5

Nous pouvons bien sûr vérifier que les variables en base ont toute un TMS nul

TMS de e2= 0 – [ (0*0)+(1*0)+ (0*0)+ (0*0)+ (0*0) ] =0