Programmation linéaire

• Quelques exemples
• Formalisation
• Résolution de problèmes par voie graphique
• Résolution de problèmes par méthode du simplexe
 Problème de production (pb1)
• Un fabricant produit deux types de yaourts à la fraise A et B à partir de
Fraise, de Lait et de Sucre. Chaque yaourt doit respecter les proportions
suivantes de matières premières.

• Les matières premières sont en quantité limitée : 800 kilos de Fraises, 700
kilos de Lait et 300 kilos de sucre. La vente des yaourts A rapportent 4 DA
par kilo et les yaourts B 5 DA.
 Problème de planification (pb2)
• Planifier la production d’articles à moindre coût pour les 4 prochains
mois.
• Production maximale normale : 1200 articles / mois Production
maximale en heure sup : 400 articles / mois Surcoût heures sup : 7 DA
/ article Stockage : 3 DA / article / mois
 Comment résoudre de tels problèmes?
 Généralement pour résoudre ce type de problèmes on approche sur trois
étapes principales :

1. La modélisation du problème sous forme d’équations (inéquations)

linéaires ;

2. La formulation d’une fonction objective ;

3. La détermination de l’optimum à l’aide d’une approche propre à la

programmation linéaire.
 Modélisation
Modéliser un problème en Recherche Opérationnelle consiste à
identifier :
- Les variables (inconnues)
- Les contraintes
- L’objectif à atteindre (optimisation)
Dans un problème de programmation linéaire, les contraintes et
l'objectif sont des fonctions linéaires.
 corderons de l’importance à ces définitions parce qu’elles sont in-
dispensables pour la com préhension des dém arches de r
dispensables pour la compréhension des démarches de résolution de
problèmPréliminaires: Inéquation
n: problèmes es de program m ation
Une inéquation linéaire est
de programmation une expressionlinéaire
linéaire.
linéaire.
de la forme :
: Une inéqu at ion lin éaire est une expression de la form
: Une inéquat ion alinéaire est une expression de la forme :
1 x 1 ` a2 x 2 ` a3 x 3 ` ¨ ¨¨ ` an x n ď b
a1 x 1 ` a 2 x 2 ` a 3 x 3 ` ¨ ¨ ¨ ` a n x n ď b
a 1 x 1 ` a 2 x 2 ` a3 x 3 ` ¨ ¨ ¨ ` an x n ď b
où x i sont les variables (ou inconnues), les ai sont les coefficients
où x i sont les variables (ou inconnues), les ai sont les
oùdes
x i variables, b est une(ou
sont les variables constante et n les
inconnues), est alei sont
nombre d’inconnues.
les coefficient s
des variables, b est une const ant e et n est le nombre d
des variables, b est une const ant e et n est le nombre d’inconnues.
:e: Une
Une expression
expressionde la
deforme :
la forme :
: Une expression de la forme :
a 1 x a
1 `
1 x a12 `x 2 `a2ax32x 3` ` a¨ 3¨¨x`3 `an x¨n¨ ě¨ `b an x n ě b
a x ` a x ` a x ` ¨¨¨ ` a x ě b
1 1 2 2 3 3 n n

est également une inéquat ion linéaire à n inconnues. Ce

est également une inéquat ion linéaire à n inconnues. Cependant , en en
est également une inéquation linéaire à n inconnues. Cependant,
mult ipliant les deux t ermes de l’inéquat ion par un nom
multipliant
mult ipliant leslesdeux
deuxt ermes
termesdede l’inéquation
l’inéquat ion parpar
un un nombre
nombre négat
négat if, if,
 Modélisation : Problème de production
(pb1)
Variables : x1 et x2 sont les quantités des produits A et B fabriqués (x1,x2 ∈R).

Fonction objectif à maximiser : La fonction objectif Z correspond au

bénéfice total: Z=4x1+5x2. On cherche donc max Z=4x1+5x2.

Contraintes :
Disponibilité de chacune des ressources:

2x1 + x2 ≤ 800
x1 + 2x2 ≤ 700
x2 ≤ 300
 Préliminaires:
e d’inéquat Système d’inéquations
ions linéaires
linéaires
it ion: On appelle syst èm e de m inéquat ions linéaires à n inconnues
un syst ème de la forme :
$
’’ a11 x 1 ` a12 x 2 ` a13 x 3 ` ¨ ¨ ¨ ` a1n x n ď b1
’’
’& a21 x 1 ` a22 x 2 ` a23 x 3 ` ¨ ¨ ¨ ` a2n x n ď b2
a31 x 1 ` a32 x 2 ` a33 x 3 ` ¨ ¨ ¨ ` a3n x n ď b3
’’ ..
’’ .
’%
am 1 x 1 ` am 2 x 2 ` am 3 x 3 ` ¨ ¨ ¨ ` am n x n ď bm
où x j est une variable dans la colonne j , aij est le coefficient de la
variable x j sur la ligne i, bi est la const ante de la ligne i, n est le
nombre d’inconnues et m est le nombre d’inéquat ions.
 Modélisation Formelle
Formellement, on peut définir un problème comme suit :

Où aij, bi et cj sont des constantes connues et les contraintes xj ≥ 0, j = 1,...,n sont

appelées contraintes de non négativité.
 Problème de production (pb1)
• Un fabricant produit deux types de yaourts à la fraise A et B à partir de
Fraise, de Lait et de Sucre. Chaque yaourt doit respecter les proportions
suivantes de matières premières.

• Les matières premières sont en quantité limitée : 800 kilos de Fraises, 700
kilos de Lait et 300 kilos de sucre. La vente des yaourts A rapportent 4 DA
par kilo et les yaourts B 5 DA.
 Exemple 1: Formalisation(pb1)

xi : quantité (en kg) de yaourts du type i = 1, 2 correspond aux produits A,B

respectivement.
 Exemple 2: Problème de fabrication (pb3)
On considère le cas d’un fabricant d’automobiles qui propose deux modèles à
la vente, des grosses voitures et des petites voitures. Les voitures de ce
fabricant sont tellement à la mode qu’il est certain de vendre tout ce qu’il
parvient à produire, au moins au prix catalogue actuel de 1,6 million de dinars
pour les grosses voitures, et 1.0 million de dinars pour les petites voitures.
Son problème vient de l'approvisionnement limité de deux matières
premières. La construction d'une petite voiture nécessite l'emploi d'une unité
de caoutchouc et d'une unité d’acier, tandis que celle d'une grosse voiture
nécessite une unité de caoutchouc, mais deux unités d'acier. Sachant que son
stock de caoutchouc est de 400 unités et son stock d'acier de 600 unités, la
question est combien doit-il produire de petites et de grosses voitures au
moyen de ces stocks afin de maximiser son chiffre d'affaires ?
 Modélisation : Problème de production
(pb3)
Variables : x1 et x2 sont les quantités des voitures petites et grosses fabriqués
(x1,x2 ∈R).
Fonction objectif à maximiser : La fonction objectif Z correspond au
bénéfice total: Z=1.6x1+1.0x2. On cherche donc max Z=1.6x1+1.0x2.

Contraintes :
Disponibilité de chacune des ressources:

x1 + x2 ≤ 400
2x1 + x2 ≤ 600
Positivité des variables: x1 , x2 ≥ 0.
 Exemple 2 : Formalisation (pb3)
• Le problème se traduit alors sous la forme suivante :
 Exemple 3: Problème de production (pb4)
La direction d’une usine de meubles a constaté qu’il y a des temps morts dans
chacun des départements de l’usine. Pour remédier à cette situation, elle
décide d’utiliser ces temps morts pour fabriquer deux nouveaux modèles de
bureaux, x1 et x2. Les temps de réalisation pour chacun de ces modèles dans les
ateliers de sciage, d’assemblage et de sablage ainsi que les temps libres dans
chacun de ces ateliers sont donnés dans le tableau ci-dessous.
Ces temps représentent le nombre d’heures
nécessaires à un homme pour effectuer le
travail. Les profits que la compagnie peut
réaliser pour chacun de ces modèles sont de
3000 DA pour x1 et de 2000 DA pour x2. La
direction désire déterminer combien de
bureaux de chaque modèle elle doit fabriquer
 Modélisation : Problème de production
(pb4)
Variables : x1 et x2 sont les quantités des deux modèles de bureaux fabriqués
(x1,x2 ∈R).
Fonction objectif à maximiser : La fonction objectif Z correspond au
bénéfice total: Z=3000x1+2000x2. On cherche donc max Z=3000x1+2000x2.

Contraintes :
Disponibilité de chacune des ressources:

x1 + 2x2 ≤ 20
2x1 + x2 ≤ 22
x1 + x2 ≤ 12
 Exemple 3 : Formalisation (pb4)
• Le problème se traduit alors sous la forme suivante:
 Comment résoudre de tels problèmes?
 Généralement pour résoudre ce type de problèmes on approche sur trois
étapes principales :

1. La modélisation du problème sous forme d’équations (inéquations)

linéaires ;

2. La formulation d’une fonction objective ;

3. La détermination de l’optimum à l’aide d’une approche propre à la

programmation linéaire.
 Approches programmation linéaire

Résolution par la
Résolution par Résolution par la
méthode du
voie graphique dualité
simplexe
Résolution de problèmes par
voie graphique
Résolution de problèmes par voie
graphique
• La résolution graphique de problèmes de programmation linéaire ne
peut concerner que des problèmes avec deux et trois variables
(même ce dernier cas est à éviter), où le processus de résolution
s’applique en deux étapes :

a). la représentation du domaine des solutions réalisables,

b). trouver une solution optimale.
 exprimer une inéquat ion linéaire sous la forme :

Préliminaires:
a1 x 1 ` a2 xSolution
2 ` a3 x 3 ` ¨ ¨d’une inéquation
¨ ` an x n ď b
linéaire (1)
et nous ut iliserons cet t e forme dans t outes les définit ions.

n: On appellera solut ion d’une inéquat ion linéaire à n inconnues

de la forme :

a1 x 1 ` a2 x 2 ` a 3 x 3 ` ¨ ¨ ¨ ` a n x n ď b

tout n-t uplet : pk 1 ; k 2 ; k 3 ; . . . ; k n q pour lequel :

a1 k 1 ` a2 k 2 ` a3 k 3 ` ¨ ¨ ¨ ` an k n ď b est une inégalit é vraie.

1: Ainsi le couple p´ 2 ; 3q est une solut ion de l’inéquation 2x 1 ` 3x 2 ď 9

 1
Préliminaires: 2xSolution
` 3x ă 9 d’une inéquation
1 2

´ 1 linéaire
1 2 (2)
3 4 5 x 1

´ 1
REMARQUE
ions: Pour dét erminer l’ensemble-solution d’une inéquat ion linéaire à
deux inconnues, on commence par t racer la droit e-front ière, puis
à l’aide d’un couple, on dét ermine par subst it ut ion de quel côt é de
la front ière sont les couples qui sat isfont à l’inéquat ion. Lorsque l’in-
équat ion ne comport e qu’une inégalit é st rict e < ou > la frontière
ne fait pas part ie de l’ensemble-solut ion de l’inéquat ion.

ple 2: Représent er l’ensemble-solut ion de l’inéquat ion x 1 ` 2x 2 ă 5 :

 Préliminaires:
tout n-t uplet : pk 1 ; k 2 ; k 3Solution d’une
; . . . ; k n q pour lequel : inéquation

alinéaire [Exemple deux variables] (1)

1 k 1 ` a2 k 2 ` a3 k 3 ` ¨ ¨ ¨ ` an k n ď b est une inégalité vraie.

e 1: Ainsi le couple
ÉSOLUTION p´ 2 ; 3q est D’INÉQUATIONS
DE SYSTÈMES une solut ion de l’inéquat ion 2x
À 2 OU 1 ` 3x 2 ď 9
3 VARIABLES
puisque : 2 ¨ p´ 2q` 3 ¨ 3 ď 9 est une inégalit é vraie.

Ce n’est pas la seule solution de cet t e inéquat ion ; les couples p0 ; 0q,
5
p1 ; 2q, p3 ; 1q sont également des solut ions.
L’ensemble des solutions de cett e inéquat ion est un demi-plan dans
le syst ème d’axes Ox 1 x 2 . La front ière de ce demi-plan est la droit e
2x 1 ` 3x 2 “ 9
x2

3
p1 ; 2q, p3 ; 1q sont également des solut ions.
Préliminaires:
L’ensemble des solutionsSolution d’une
de cet t e inéquat ion est inéquation
un demi-plan dans
le syst ème d’axes Ox 1 x 2 . La front ière de ce demi-plan est la droit e
2x 1 linéaire
` 3x 2 “ 9 [Exemple deux variables] (2)
x2

3
2x 1 ` 3x 2 ą 9
2

1
2x 1 ` 3x 2 ă 9

´ 1 1 2 3 4 5 x1
´ 1
 Préliminaires: Solution d’une inéquation
LUT ION DE SYST ÈMES D’INÉQUAT IONS À 2 OU 3 VARIABLES 7
linéaire [Exemple trois variables]
Lorsque l’inéquat ion comport e t rois inconnues, la front ière est un
plan. Ainsi la front ière de l’inéquat ion :

a1 x 1 ` a 2 x 2 ` a 3 x 3 ď b
; 0q
CHAP
est un plan coupant les axes IT point
aux RE 2.s RÉSOLUTION
représent ant leDE SYSTÈMES
t riplet :

pb{a1 ; 0 ; 0q; p0 ; b{a2 ; 0q; p0 ; 0 ; b{a3 q

x3
Lorsque l’inéquat ion
En effet : p0 ; 0 ; b{a 3 q plan. Ainsi la front iè

p0 ; b{a 2 ; 0q
est un plan coupant
x2
Lorsqu’on représent e un t el plan, il est d’usage de représent er les
t race s du plan sur les plans du syst ème d’axes. On ne donne enpb{a1
fait qu’une part ie du plan puisque
pb{a 1 ; 0celui-ci
; 0q s’ét end à l’infini.
x1
 plus représent
l’espace er l’ensemble-solut
en deux demi-espaces. ion graphiquement
L’un ; cependant
de ces demi-espaces en ,union
les
définit
avec laions seront t oujours posées à part ir d’une
des systèmes d’inéqua-
tions
Domaine des solutions réalisables (1)
front ière forme
à ninconnues.
inconnues.
l’ensemble-solut ion inéquat ion linéaire
à t rois
REMARQUE
it ion: L’ensemble-solution d’une inéquat ion de la forme :
Lorsque l’inéquation comporte plus de t rois inconnues, on ne peut
plus représent era1l’ensemble-solut
x 1 ` a2 x 2 ` a3 x 3ion
` ¨graphiquement
¨ ¨ ` an x n ď b ; cependant , les
définit ions seront t oujours posées à part ir des syst èmes d’inéqua-
t ions
est à n inconnues.
appelé dem i-espace ferm é.

it ion: Si
L’ensemble-solut
l’inéquat ion estiondéfinie
d’une par inéquat
uneion de laé forme
inégalit st rict e: (< ), le demi-
espace est dit ouvert . La front ière de ce demi-espace est l’ensemble-
a1 x 1 ` linéaire
solut ion de l’équation a2 x 2 ` :a3 x 3 ` ¨ ¨ ¨ ` an x n ď b

est appelé demai-espace

x
1 1 ` a x
2 2
ferm
` a é.
3 x 3 ` ¨ ¨ ¨ ` an x n “ b

Si l’inéquat
Cet ion estiondéfinie
ensemble-solut par une
est appelé un hyperplan rict e n(<
inégalit é st de . ), le demi-
OLUTION DE SYSTÈMES D’INÉQUATIONS À 2 OU 3 VARIABLES 9
Domaine des solutions réalisables (2)
t ion: Un n-t uplet pk 1 ; k 2 ; k 3 ; . . . ; k n q est une solut ion d’un syst èm e
de m inéquat ions à n inconnues s’il est solut ion de chacune
des inéquat ions du syst ème, c’est -à-dire si chacune des inégalit és
suivant es est vérifiée :
$
’’ a11 k 1 ` a12 k 2 ` a13 k 3 ` ¨ ¨ ¨ ` a1n k n ď b1
’’
’& a21 k 1 ` a22 k 2 ` a23 k 3 ` ¨ ¨ ¨ ` a2n k n ď b2
a31 k 1 ` a32 k 2 ` a33 k 3 ` ¨ ¨ ¨ ` a3n k n ď b3
’’ ..
’’ .
’%
am 1 k 1 ` am 2 k 2 ` am 3 k 3 ` ¨ ¨ ¨ ` am n k n ď bm
L’ensemble-solut ion d’un système d’inéquat ions linéaires est l’in-
t ersection des ensembles-solutions de chacune des inéquat ions du
syst ème.
 ’’ x 1 ` x 2 ` 2x 3 ď 8
& convexe.
x 1 ` 2x 2 ` x 3 ď 8
e) b)
’’ Domaine
L’intersection
2x 1 ` x 2 ` xdedes solutions
deux
3 ď 8
réalisables
ou de plusieurs (3) est
ensembles convexes
% un
où ensemble convexe.
[Ensembles
x i ě 0 pour i “ 1; 2; 3 convexes]
REMARQUE
ns: L’ensemble-solution d’un système d’inéquations linéaires à 2 (ou 3)
inconnues forme un polygone (ou un polyèdre) convexe.
es convexes
on: On dit qu’un ensemble de points est convexe si pour tout e paire
de point s P et Q de l’ensemble, le segment de droit e joignant P et
Q est entièrement contenu dans l’ensemble.
ttion:
ion: On
On dit
dit qu’un ensemble de
qu’un ensemble de point
pointss est
est convexe
convexe sisi pour
pour ttoute
out e paire
paire
de point s P et Q de l’ensemble, le segment de droit e joignant P et
Q
Domaine
de point s P et Q de des solutions
l’ensemble, réalisables
le segment (4)
de droit e joignant P et
Q est
est ent
ent ièrement
ièrement cont enu
cont enu dans
dans l’ensemble.
[Ensembles convexes] (Exemple)
l’ensemble.

Le
Le troisième
troisième ensemble n’est pas
ensemble n’est pas convexe,
convexe, car
car on
on peut
peut trouver
trouver deux
deux
point
point ss P
P et
et QQ dans l’ensemble, ttel
dans l’ensemble, el que
que le
le segment
segment joignant
joignant ces
cesdeux
deux
point
point ss n’est
n’est pas entièrement
pas ent contenu
ièrement cont enu dans
dans l’ensemble.
l’ensemble.
 La solution graphique

La solution optimale (s’il en existe une) se trouve sur la frontière de la

région réalisable (un ensemble convexe)

Quand il en existe, il existe toujours une solution optimale sur un

sommet (point extrême)de la région réalisable)

Il suffit d’examiner les points extrêmes de la région réalisable (la PL est

un problème d’optimisation combinatoire)
Problème de production (pb1) : Résolution
graphique
• Un fabricant produit deux types de yaourts à la fraise A et B à partir de
Fraise, de Lait et de Sucre. Chaque yaourt doit respecter les proportions
suivantes de matières premières.

• Les matières premières sont en quantité limitée : 800 kilos de Fraises, 700
kilos de Lait et 300 kilos de sucre. La vente des yaourts A rapportent 4 DA
par kilo et les yaourts B 5 DA.
 Modélisation : Problème de production
(pb1)
Variables : x1 et x2 sont les quantités des produits A et B fabriqués (x1,x2 ∈R).

Fonction objectif à maximiser : La fonction objectif Z correspond au

bénéfice total: Z=4x1+5x2. On cherche donc max Z=4x1+5x2.

Contraintes :
Disponibilité de chacune des ressources:

2x1 + x2 ≤ 800
x1 + 2x2 ≤ 700
x2 ≤ 300
 Formalisation(pb1)

xi : quantité (en kg) de yaourts du type i = 1, 2 correspond aux produits A,B

respectivement.
Problème de production (pb1): Solution
graphique(1)

Région réalisable :
Ensemble des solutions réalisables.
Problème de production (pb1) : Solution
graphique(2)

Dessiner la droite avec une pente -4/5 et dont

2x 1
l’ordonnée à l’origine est p/5.
+x 2
=8
00 x2=300

x1 +2
x2 =7
00
Problème de production (pb1) : Solution
graphique(3)

2x 1
+x 2
=8
00 x2=300

x1 +2
x2 =7
00

Glisser la droite vers le haut

Problème de production (pb1) : Solution
graphique(4)
4x

2x 1
1+
5x

+x 2
2=
22

=80
00 x2=300

0
La solution optimale
(300,200)
x1 +
2x
2 =7
00
Problème de fabrication (pb3) (Exemple2):
Résolution graphique
On considère le cas d’un fabricant d’automobiles qui propose deux modèles à
la vente, des grosses voitures et des petites voitures. Les voitures de ce
fabricant sont tellement à la mode qu’il est certain de vendre tout ce qu’il
parvient à produire, au moins au prix catalogue actuel de 1,6 million de dinars
pour les grosses voitures, et 1.0 million de dinars pour les petites voitures.
Son problème vient de l'approvisionnement limité de deux matières
premières. La construction d'une petite voiture nécessite l'emploi d'une unité
de caoutchouc et d'une unité d’acier, tandis que celle d'une grosse voiture
nécessite une unité de caoutchouc, mais deux unités d'acier. Sachant que son
stock de caoutchouc est de 400 unités et son stock d'acier de 600 unités, la
question est combien doit-il produire de petites et de grosses voitures au
moyen de ces stocks afin de maximiser son chiffre d'affaires ?
 Modélisation : Problème de production
(pb3)
Variables : x1 et x2 sont les quantités des voitures petites et grosses fabriqués
(x1,x2 ∈R).
Fonction objectif à maximiser : La fonction objectif Z correspond au
bénéfice total: Z=1.6x1+1.0x2. On cherche donc max Z=1.6x1+1.0x2.

Contraintes :
Disponibilité de chacune des ressources :
x1 + x2 ≤ 400
2x1 + x2 ≤ 600
Positivité des variables: x1 , x2 ≥ 0.
 Formalisation (pb3)
• Le problème se traduit alors sous la forme canonique suivante :
Problème de fabrication(pb3) : Solution graphique

2x 1
+x 2
x1 +

=6
x2 =

0
40

0
0 La solution optimale

(200,200) 1.6x1+x2=520
 Exemple 3: Problème de production (pb4)
La direction d’une usine de meubles a constaté qu’il y a des temps morts dans
chacun des départements de l’usine. Pour remédier à cette situation, elle
décide d’utiliser ces temps morts pour fabriquer deux nouveaux modèles de
bureaux, x1 et x2. Les temps de réalisation pour chacun de ces modèles dans les
ateliers de sciage, d’assemblage et de sablage ainsi que les temps libres dans
chacun de ces ateliers sont donnés dans le tableau ci-dessous.
Ces temps représentent le nombre d’heures
nécessaires à un homme pour effectuer le
travail. Les profits que la compagnie peut
réaliser pour chacun de ces modèles sont de
3000 DA pour x1 et de 2000 DA pour x2. La
direction désire déterminer combien de
bureaux de chaque modèle elle doit fabriquer
 Modélisation : Problème de production
(pb4)
Variables : x1 et x2 sont les quantités des deux modèles de bureaux fabriqués
(x1,x2 ∈R).
Fonction objectif à maximiser : La fonction objectif Z correspond au
bénéfice total: Z=3000x1+2000x2. On cherche donc max Z=3000x1+2000x2.

Contraintes :
Disponibilité de chacune des ressources :
x1 + 2x2 ≤ 20
2x1 + x2 ≤ 22
x1 + x2 ≤ 12
Positivité des variables: x1 , x2 ≥ 0.
 Exemple 3 : Formalisation (pb4)
• Le problème se traduit alors sous la forme canonique suivante:
Problème de fabrication(pb4) : Solution graphique

2x 1
+x 2
=2
x1

2
+x
2 =1 La solution optimale
2
x1+2x2=20

(10,2)
 Exemple 3: Problème de production (pb5)
Une usine fabrique 2 produits P1 et P2 nécessitant des ressources
d’équipement, de main d’oeuvre et de matières premières disponibles en
quantité limitée.

P1 et P2 rapportent à la vente 6 dinars et 4 dinars par unité.

Quelles quantités (non entières) de produits P1 et P2 doit produire l’usine
pour maximiser le bénéfice total venant de la vente des 2 produits ?
 Modélisation : Problème de production
(pb5)
Variables : x1 et x2 sont les quantités des produits P1 et P2 fabriqués (x1,x2 ∈R).

Fonction objectif à maximiser : La fonction objectif Z correspond au

bénéfice total: Z=6x1+4x2. On cherche donc max Z=6x1 +4x2 .

Contraintes :
Disponibilité de chacune des ressources :
3x1 + 9x2 ≤ 81
4x1 + 5x2 ≤ 55
2x1 + x2 ≤ 20
Positivité des variables: x1 , x2 ≥ 0.
Problème de fabrication(pb5) : Solution graphique

2x 1
4x La solution optimale

+x 2
1 +5
x

=20
2 =5
5

3x +

(8
1 9x

.3
2 =81

33
,4
.3
33
)
Exemple 3: Problème de composition (pb6)
L’intendant d’un lycée doit composer un menu qui doit contenir un
minimum d’ éléments nutritifs et qui doit être le moins coûteux possible.
On se limite à une situation simple, deux denrées alimentaires
principales D1, D2 et trois éléments nutritifs, les vitamines V, les calories
C et les protéines P. Le tableau suivant indique le nombre d’éléments
nutritifs par unité d’aliment :
Le menu doit comporter au minimum 5 unités de V,
4 unités de C, 6 unités de P. Les coûts unitaires sont
20 DA pour D1, 25 DA pour D2. Un menu contenant
x1 unités de D1, x2 unités de D2.
 Modélisation : Problème de composition
(pb6)
Variables : x1 et x2 sont les quantités des unités de D1 et D2 (x1,x2 ∈R).

Fonction objectif à maximiser : La fonction objectif Z correspond au coût

total: Z=20x1+25x2. On cherche donc min Z=20x1 +25x2 .

Contraintes :
Disponibilité de chacune des ressources :
x1 + 5x2 ≥ 5
x1 + 2x2 ≥ 4
3x1 + x2 ≥ 6
Positivité des variables: x1 , x2 ≥ 0.
Problème de composition (pb6) : Solution
graphique

La solution optimale
(1.6,1.2)
Z=20x1+25x2=62
Résolution de problèmes à trois variables
(pb7) par voie graphique [Exemple]

Un marchand de légumes prépare trois types de paquets de légumes P1,

P2 et P3 dont les ingrédients de base sont les carottes, les courgettes et
les poireaux. Pour préparer ces mélanges comme des paquets, il reçoit
hebdomadairement 24000gr de carottes, 12000gr de courgettes et
12000gr de poireaux. Les quantités utilisées pour chaque type de paquet
et le profit réalisé sont données dans le tableau suivant :
Résolution de problèmes à trois variables
(pb7) par voie graphique [Exemple]

Sachant que le commerçant peut écouler tous les paquets de

légumes qu’il peut préparer chaque semaine, trouver combien il
doit en préparer de chaque type de paquets de légumes de telle
sorte qu’il arrive à maximiser son profit.
 Modélisation : Problème à trois variables
(pb7)
Variables : x1, x2 et x3 sont les quantités des trois légume carotte, courgette et
les poireau (x1,x2,x3∈R).
Fonction objectif à maximiser : La fonction objectif Z correspond au
bénéfice total: Z=2x1+1.5x2+x3. On cherche donc max Z=2x1+1.5x2+x3.
Contraintes :
Disponibilité de chacune des ressources :
3x1 + 3x2+ 2x3 ≤ 240
x1 + x2+ 2x3 ≤ 120
x1 + x2 ≤ 120
Positivité des variables: x1 , x2, x3 ≥ 0.
 x3
120 1

10 x2
1010 120

x1 120 x 1 120
nomique.

x3 x3

plan :
60 2x 1 ` 1,5x 2 ` x 3 “ 60 60
50 50
x1
50
30 30
10 10 10 10
x2
10 40 50 100 10 4
 x3

60 60
50
x1 x1
50
30 (20,60,0)
10 10
x2 x2
100 10 40 50 100
• Éviter la résolution graphique pour trois variables?

• Une grande perte de temps ou un algorithme naïf

sera plus performant.
Résolution de problèmes par
La méthode du simplexe
 R em arque:

Un peu d’histoire

[G. Dantzig, 1947]

• Algorithme de résolution de programmes linéaires;

• Facile à comprendre et à implanter; G e orge D ant zig

( 1914-2005)

• Efficace en pratique, même pour un nombre important de variables

et de contraintes;
 Introduction
• Cet algorithme permet de déterminer la solution optimale, si elle
existe, d’un problème de programmation linéaire à n variables.

• Le principe de la méthode est de transformer les contraintes qui sont

des inéquations en équations en ajoutant des variables positives que
l’on appelle variables d’écart. Puis on transforme ce système
d’équations linéaires jusqu’à trouver la solution optimale.

• Il est fortement recommander lorsque le nombre de variables est plus

que deux.
 Les étapes de la méthode
• Première étape  : Mise sous forme standard du problème

• Deuxième étape : Application de l’algorithme du simplexe

 Mise sous forme standard du problème(1)
Définition
• Un problème de programmation linéaire est dit sous forme standard
s’il vérifie les conditions suivantes :
• Les variables du problème doivent toutes être positives.
• Les contraintes sont des contraintes d’égalité.
• Le type d’optimisation doit être une recherche de maximum.
 Mise sous forme standard du problème(2)
Transformation des variables
D’abord, il faut transformer une inéquation linéaire ayant un signe :
a) ≤ ou < en une équation linéaire en additionnant une variable
d’écart non négative ;
b) ≥ ou > en une équation linéaire en retranchant une variable d’écart.
c) on remplace chaque variable xi sans restriction de signe par la
différence de deux variables positives: xi=xi+- xi- avec xi+≥0 et xi- ≥ 0.
d) Si une variable xi est négative, effectuer le changement de variable
xi = −xi.
Exemple
 Mise sous forme standard du problème(3)
Transformation des variables
• Si le type d’optimisation est une recherche de minimum pour la
fonction objective Z, on procède à un changement de fonction
objective en considérant –Z (qui est toujours une fonction linéaire des
variables).
• On a la propriété Min(Z) = - Max(-Z).
 Exemple: Mise sous forme standard
Forme canonique du programme Le problème est mis sous forme
linéaire : standard:
 Constitution du tableau
• Quand le problème est mis sous forme standard, on peut appliquer
l’algorithme du simplexe. Les différentes équations linéaires sont
placées dans un tableau. Chaque équation est une ligne du tableau, la
dernière ligne est réservée pour la fonction objective.

• Les colonnes correspondent aux variables du problème. A droite du

tableau la dernière colonne contient les seconds membres (bi) des
équations.
 Application de l’algorithme du simplexe

• Les calculs qui sont effectués sont des calculs sur les lignes du tableau.

• On suppose que toutes les variables d’écart ont un coefficient 1.

• On recherche un maximum de la fonction objective.

Tableau du simplexe [exemple] (pb1)

 
Variables   𝑥 1 𝑥 2 𝑒1 𝑒2 𝑒 3 𝑏𝑖

( 𝑒1
𝑒2
𝑒3
𝑐𝑖
2 1
1 2
0 1
4 5
1
0
0
0
0
1
0
0
0 800
0 700
1 300
0 0
)
 Principe de l’algorithme
• A chaque étape de l’algorithme, on choisit une variable hors base que
l’on appelle variable entrante et une variable en base que l’on appelle
variable sortante afin d’améliorer la solution précédente.

• Puis on transforme le tableau pour le remettre sous sa forme

standard. En effet, les colonnes des variables en base ne doivent avoir
qu’un seul 1 et des 0 ailleurs.

• Cette transformation se fait par combinaison linéaire des lignes.

 Choix de la variable entrante et sortante
• On choisit celle dont le ci est strictement positif et le plus grand
possible.
• Si tous les ci sont négatifs ou nuls, l’optimum est atteint. L’algorithme
s’arrête
• Après avoir choisi la variable entrante, on calcule pour chaque ligne
représentant une contrainte, le ratio qui est le rapport entre les bi de
et le coefficient sur la colonne de la variable entrante.
• La variable sortante est celle dont le ratio est le plus petit strictement
positif.
 Transformation du tableau
• Après le choix de la variable entrante et de la variable sortante, on
transforme le tableau.

• L’intersection de la colonne de la variable entrante et de la ligne de la

variable sortante s’appelle le pivot.

• Il faut transformer le tableau par combinaisons linéaires sur les lignes

pour faire apparaître un 1 sur le pivot et des 0 ailleurs sur la colonne
de la nouvelle variable en base.
 Fin de l’algorithme
• L’optimum est atteint lorsque tous les ci sont négatifs. Les variables
hors base sont nulles. Les valeurs des variables en base se lisent
directement sur le tableau puisque leur coefficient est 1 et que les
autres variables qui ont un coefficient non nuls sur la même ligne
sont hors base.
• La valeur de l’optimum est l’opposé de la valeur qui figure sur la ligne
de la fonction économique à l’avant dernière colonne. On vérifiera
cette valeur en remplaçant les valeurs des variables dans la fonction
économique.
 Simplex: Exemple (pb8)
• L’entreprise Simco fabrique différents modèles d’appareils électro-
ménagers. Le programme actuel de fabrication est de 500 unités du
modèle Elec-100 et 400 unités du modèle Elec-200. Le vice-président
de la fabrication veut déterminer si les contributions aux bénéfices de
l’entreprise peuvent être augmentées en modifiant le programme
actuel de fabrication. Il possède l’information suivante sur le nombre
d’heures requises pour fabriquer chaque modèle, ainsi que le temps
disponible à chaque atelier.
La forme canonique
La forme standard
La représentation en tableau: Matrice du
programme de base no1
Matrice du programme de base no2(1)
Matrice du programme de base no2(2)
Matrice du programme de base no2(3)
 2 fois la deuxième à la troisième et finalement 120 fois la deuxième
Matrice du programme de base no2(4)
à la dernière :
¨ ˛
L 1 ´ 4L 2 Ñ L 1 3 ´ 4{3 4 ´ 4 1´ 0 0´ 4{3 0´ 0 4’200´ 3’200
˚ 1/ 3 1 0 1/ 3 0 800 ‹
˚ ‹
L 3 ´ 2L 2 Ñ L 3 ˝ 2 ´ 2{3 2 ´ 2 0´ 0 0´ 2{3 1´ 0 2’600´ 1’600 ‚
L 4 ´ 120L 2 Ñ L 4 100´ 40 120´ 120 0´ 0 0 ´ 40 0´ 0 0 ´ 120 ¨800
Matrice du programme de base no2(5)
À nouveau, effectuons le rapport de la dernière colonne avec celle
de x 1 Matrice
: du programme de base no3(1)

¨ Ó Ó ˛
5/ 3 0 1 -4/ 3 0 1’000 1’000/ (5/ 3) = 600
˚ 1/ 3 1 0 1/ 3 0 800 ‹ 800/ (1/ 3) = 2’400
˚ ‹
˝ 4/ 3 0 0 -2/ 3 1 1’000 ‚ 1’000/ (4/ 3) = 750
60 0 0 -40 0 -96’000

Le plus petit rapport étant sur la première ligne, notre pivot sera
Matrice du programme de base no3(2)
EffectuonsMatrice
à nouveaudulesprogramme
opérations surde
les base
lignes no3(3)
afin d’annuler les
re
autres éléments de la 1 colonne :

¨ ˛
1 0 3/ 5 -4/ 5 0 600
L 2 ´ 1{3L 1 Ñ L 2 ˚˚ 0 1 -1/ 5 3/ 5 0 600 ‹‹
L 3 ´ 4{3L 1 Ñ L 3 ˝ 0 0 -4/ 5 2/ 5 1 200 ‚
L 4 ´ 60L 1 Ñ L 4 0 0 -36 8 0 -132’000

Après retranscription en système d’équations :

Matrice du programme de base no4(1)
Matrice du programme de base no4(2)
Effectuons à nouveau les opérations sur les lignes afin d’annuler les
e
autres éléments de la 4 colonne : de base no4(3)
Matrice du programme

¨ ˛
L 1 ` 4{5L 3 Ñ L 1 1 0 -1 0 2 1’000
L 2 ´ 3{5L 3 Ñ L 2 ˚˚ 0 1 1 0 -3/ 2 300 ‹‹
˝ 0 0 -2 1 5/ 2 500 ‚
L 4 ´ 8L 3 Ñ L 4 0 0 -20 0 -20 -136’000

Il n’y a plus de coefficients positifs sur la dernière ligne de la

 2

1
Solution
2x 1 ` 3x 2 ă 9
Exe rc ic e s ´1 1 2 3 4 5 x1 17

´ 1donc le quintuplet :
La solution optimale est
La solution optimale est donc le quintuple :
Pour déterminer l’ensemble-solution (x1 ;x2 ;x3 ;x4 ;x5 ) = (1000; d’une inéquation linéaire à
300;0;500;0)
deux
q u i c o rinconnues,
r e s p o n d a` u n b on
e´ n e´ ficommence
c e m a x i m u m dpar
e 1 3 6tracer
0 0 0 e n plar o ddroite-frontière,
u i s a n t 1 0 0 0 u n i t e´ s d e puis
E le c -1 0 0 ,
à300
l’aide
unitésd’un couple,aveconundétermine
de Elec-200 temps mort depar 500substitution
heures à l’atelierde de quel côté de
vérification.
 Résumé(1)
En résumé, pour résoudre matriciellement un problème de maximisation,
les étapes sont :

1) Déterminer la colonne (sauf la dernière) dont l’élément de la dernière

ligne a la plus grande valeur positive. C’est la colonne du pivot.

2) Déterminer la ligne du pivot en faisant le rapport des éléments de la

dernière colonne sur les éléments correspondants de la colonne du pivot.
La ligne du pivot étant celle donnant le plus petit rapport non négatif.

3) Rendre le pivot unitaire.

 Résumé(2)

4) Annuler tous les termes de la colonne du pivot.

5) Répéter les quatre premières étapes jusqu’à ce que tous les éléments de
la dernière ligne soient non positifs.

6) Les colonnes ne contenant qu’un seul élément non nul sont celles
correspondant aux variables dans le programme ; la valeur de ces
variables est donnée dans la dernière colonne, les variables hors
programme étant nulles.

7) La valeur maximale de la fonction économique (plus exactement son

opposé) est donnée dans la dernière ligne, dernière colonne.