Table des matières

I PROGRAMMATIONS LINEAIRES 3

1 Modélisation de la programmation linéaire 4

1.1 Modélisation d’un problème de maximisation . . . . . . . . . . . . . . . . . . 4

1.1.1 Construction du modèle linéaire . . . . . . . . . . . . . . . . . . . . . 5

1.2 Formes générales d’un programme linéaire . . . . . . . . . . . . . . . . . . . 6

1.2.1 Forme canonique pure . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.2.2 Forme canonique mixte . . . . . . . . . . . . . . . . . . . . . . . . . . 7

1.2.3 Forme standard . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

2 Méthodes de résolution du programme linéaire 12

2.1 Méthode graphique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

2.1.1 Quelques rappels de géométrie . . . . . . . . . . . . . . . . . . . . . . 12

2.1.2 Propriétes fondamentales de la programmation linéaire . . . . . . . . 16

2.2 Méthode algébrique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

2.2.1 Méthode de base réalisable . . . . . . . . . . . . . . . . . . . . . . . . 16

2.2.2 Méthode de programme de base . . . . . . . . . . . . . . . . . . . . . 23

2.2.3 Méthode du simplexe . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

2.2.4 Méthode de Simplexe- Cas particuliers . . . . . . . . . . . . . . . . . 36

2.2.5 Méthode du GRAND M . . . . . . . . . . . . . . . . . . . . . . . . . 39

3 DUALITE EN PROGRAMMATION LINEAIRE 43

3.1 Construction du modèle dual . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

1
Université Félix Houphouet-Boigny U.F.R - SSMT

3.2 Programme linéaire : Primal . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

3.3 Programme linéaire : Dual . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

3.3.1 Les caractéristiques du programme linéaire dual . . . . . . . . . . . . 45

3.3.2 Règle de dualité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

3.3.3 Théorème des écarts complémentaires . . . . . . . . . . . . . . . . . . 47

Dr. AKPATA Edouard 2

 Première partie

PROGRAMMATIONS LINEAIRES

3
Chapitre 1

Modélisation de la programmation

linéaire

1.1 Modélisation d’un problème de maximisation

Illustrons ce paragraphe par un exemple

Enoncé du problème

Exemple 1.1.1. Une entreprise fabrique deux produits A et B en utilisant une machine m

et deux matières premières p et q. On dispose chaque jour de 8 h de machine, de 10 kg de

p et de 36 kg de q.

On suppose que :

La production d’une unité de A nécessite 2 kg de p et 9 kg de q et utilise la machine

m durant 1 h.

La production d’une unité de B nécessite 2 kg de p et 4 kg de q et utilise la machine

m durant 2 h.

Les pro…ts réalisés sont de 50 000 F CF A par unité de A et 60 000 F CA par unité de B.

L’objectif que poursuit l’netreprise est de maximiser le pro…t qu’elle pourra tirer par jour

de ces deux produits en utilisant au mieux ses ressourses.

Le tableau suivant résume les données a¤ectées à ce problème de production :

4
CHAPITRE 1. MODÉLISATION DE LA PROGRAMMATION LINÉAIRE

A B Disponibilites

m 1h 2h 8h

p 2 kg 2 kg 10 kg

q 9 kg 4 kg 36 kg

Pr of it 50 000 F CF A 60 000 F CF A

1.1.1 Construction du modèle linéaire

Variables de décision

Soient x1 , la quantité du produit A à fabriquer et x2 , celle du produit B à fabriquer.

Alors x1 et x2 , sont appelés valeurs de décision

Fonction objectif ou économique

Quel pro…t l’entreprise retirera-t-elle de la vente de ses produits ?

Il s’agit d’additionner les béné…ces à tirer de chacun de ces deux produits.

Soit F ( x1 ; x2 ) = 50 000 x1 + 60 000 x2 .

La fonction F ( x1 ; x2 ) est appelé f onction objectif ou economique.

Comme l’entreprise cherche à rendre F ( x1 ; x2 ) aussi grand que possible, alors on

a:

M aximiser F ( x1 ; x2 )

Alors

M ax F ( x1 ; x2 ) = 50 000 x1 + 60 000 x2

Contraintes relatives aux problèmes posés

Contraintes sur la machine m

x 1 + 2 x2 6 8

Contraintes relatives aux matières premières p

5
Université Félix Houphouet-Boigny U.F.R - SSMT

2 x1 + 2 x2 10

Contraintes relatives aux matières premières q

9 x1 + 4x2 36

Contraintes de positivité

Elles assurent que la solution ne comporte pas des valeurs négatives.

x1 0 et x2 > 0

Ainsi, le problème est posé de la manière suivante :

M ax F (x1 ; x2 ) = 50000 x1 + 60000 x2 :

8 sous contraintes (s.c.)

>
>
>
> x1 + 2 x2 8
>
>
>
>
< 2 x1 + 2 x2 10
>
>
>
> 9 x1 + 4 x2 36
>
>
>
>
: x1 > 0; x2 > 0

Problème fondamental de la pogrammation linéaire (P L)

Le problème de la PL consiste à étudier les methodes de recherche de la valeur maxi-

male ou minimale d’une fonction linéaire (objectif ou économique) en présence de certaines

contraintes linéaires.

1.2 Formes générales d’un programme linéaire

Le programme linéaire admet 3 formes.

1.2.1 Forme canonique pure

Un programme linéaire est dit sous sa fprme canonique pure s’il s’ecrit sous la forme

max F (x1 ; x2 ; ::::; xn ) = c1 x1 + c2 x2 + ::: + cn xn ( )

Pn
= cj xj (1)
j

Dr. AKPATA Edouard 6

CHAPITRE 1. MODÉLISATION DE LA PROGRAMMATION LINÉAIRE

s.c.

8 i = 1; :::; m; ai2 + ai2 x2 + :::: + ain xn bi (2)

8j = 1:::; n ; xj > 0 (3)

où (1) est appelé fonction objectif

(2) est appelé m contraintes linéaires

(3) est appelé contraintes de positivité.

Forme matricielle de la forme canonique pure

Vecteurs : x = (x1 ; x2 ; :::; xn )T 2 Rn

c = (c1; c2 ; :::; cn )T 2 Rn

b = (b1 ; b2 ; :::; bn )T 2 Rn

Matrices : matrice A de type (m; n)

0 1
B a11 a12 :::: a1n C
A=@ A = (aij )
am1 am2 :::amn

Alors ( ) devient

max F (x) = cT x
x

8 s.c.
>
< Ax 6 b
forme matricielle du programme linéaire
>
: X > 0

1.2.2 Forme canonique mixte

La forme canomique mixte du programme linéaire s’écrit :

max F (x) = cT x
x
8
> P
n
>
> 8i 2 l1 ; aij xj = ai1 x1 + ai2 x2 + ::::: + ain xn 6 bi
>
>
>
>
j
>
> P
n
< 8i 2 l2 ; aij xj = bj
s.c. j
>
>
>
> 8j 2 J1 ; xj > 0
>
>
>
>
>
: 8j 2 J ;
2 xj est de signe quelconque

7
Université Félix Houphouet-Boigny U.F.R - SSMT

où L = l1 U l2 : ensemble des indices des contraintes ; card(L) = m

J = J1 U J2 : ensemble des indices des variables ; card(J) = n

1.2.3 Forme standard

La forme standard d’un programme s’écrit :

max F (x) = cT x
x 8
>
< Ax = b
>
: x>0

Variable d’écart

A…n de ramener les contraintes d’inégalités à celle des égalités, on introduit des variables

appellées variables d’écart.

Ces variables sont aussi non négatives. La variable d’écart d’une contrainte représente la

quantité disponible non utilisée.

La variable d’écart est l’écart entre la disponibilité et le besoin.

Soit :

a11 x1 + a12 x2 + a13 x3 + ::::a1n xn 6 b1 ; il su¢ t d’ajouter une certaine grandeur

positive e1 pour obtenir

l’égalité : a11 x1 + a12 x2 + a13 x3 + :::: + a1n xn + e1 = b1

Alors e1 est appellée variable d’écart.

Transformation d’un problème linéaire de la forme canonique pure à la forme

standart et vice versa

A l’aide des variables d’écart,un programme linéaire peut être transformé de la forme

canonique pure à la forme standard.

Ax 6 b () Ax + x0 = b où x = (x1 ; x2 ; x3 ; :::; xn ) et x0 = (e1 ; e2 ; e3 ; :::; em )

et x0 est appelé variables d’écart.

Dr. AKPATA Edouard 8

CHAPITRE 1. MODÉLISATION DE LA PROGRAMMATION LINÉAIRE

A x 6 b () A x + x0 = b
X
() (A j I) X0
=b
eX
A x 6 b () A e + b; où

e = A j I et X
A e= X
X0

La matrice A est de type (m; n)

e est de type (m; n + m)
La matrice A
e 2 Rn+m
X 2 Rn () X

Remarque 1.2.1. : Le nombre de variables d’écart est égal à m ; c’est-à-dire le nombre de

contraintes.

Exemple 1.2.1. : Soit le programme linéaire suivant :

M axF (x) = 3 x1 x2 + x3

8 s.c.
>
> 2x1 x2 6 5
>
>
<
> x1 3 x3 > 2
>
>
>
: x ;x ;x > 0
1 2 3

Transformer le P.L sous la forme standard.

Solution :

M axF (x) = 3 x1 x2 + x3
8
>
> 2 x1 x2 + e1 = 5
>
>
<
s.c. x1 3 x3 e2 = 2 ; Le nombre de variables d’écart = nombre de
>
>
>
>
: x ;x ;x ;e ;e > 0
1 2 3 1 2
contraintes.

De la même manière,on peut obtenir la forme canonique pure de la forme standard.

On a :

9
Université Félix Houphouet-Boigny U.F.R - SSMT

8 8
>
< Ax>b >
< Ax6b
A x = b () ()
>
: Ax6b >
: Ax6 b

8
>
< Ax6b
A x = b ()
>
: Ax6 b

() A
A
x6 b
b

e x6B
A x = b () A e =
e où A A
et f
B= b
:
A b

e est une matrice de type (2 m; n) et f

A B 2 R2m

Exemple 1.2.2. :

Soit le programme linéaire suivant :

min F (x)
8 = 3 x1 2 x2 + 4 x3 + x4
>
>
>
> x1 3 x2 + 6
>
>
>
>
< 3 x2 + 2 x4 = 10
s.c.
>
>
>
> x4 = 2
>
>
>
>
: x 1 ; x2 ; x3 ; x 4 > 0

Transformateur P.L sous forme canonique pure

Solution :

min F (x) = 3 x1 2 x2 + 4 x3 + x4
0 1 0 1
B 1 3 0 0 C B 6 C
B C B C
Soit A=B B 0 3 0 2 C B
C etb = B 10
C
C
@ A @ A
0 0 0 1 2
8 8
>
< Ax6b >
< Ax6b
A x = b () ()
>
: Ax>b >
: Ax6 b

8
>
< Ax6b
Ax = b ()
>
: Ax6 b
Ax = b () A
A
x6 b
b

Dr. AKPATA Edouard 10

CHAPITRE 1. MODÉLISATION DE LA PROGRAMMATION LINÉAIRE

0 1 0 1
B 1 3 0 0 C0 1 B 6 C
B C B C
B 0 3 0 2 C B 10 C
B CB x1 C B C
B CB C B C
B CB B
C B C
B 0 0 0 1 C C B 2 C
B CB x2 C
() B CB C6B C
B CB C B C
B 1 3 0 0 CB x3 C B 6 C
B CB C B C
B C@ A B C
B 0 3 0 2 C x4 B 10 C
B C B C
@ A @ A
0 0 0 1 2
8
>
>
>
> x1 3x2 6 6
>
>
>
>
>
> 3x2 + 2x4 6 10
>
>
>
>
>
< x4 6 2
()
>
>
>
> x1 + 3x2 6 6
>
>
>
>
>
> 3x2 2x4 6 10
>
>
>
>
>
: x4 6 2

min F (x) = 3x1 2x2 + 4x3 + x4

8
>
> x1 3x2 6 6
>
>
>
>
>
>
>
> 3x2 + 2x4 6 10
>
>
>
>
>
> x4 6 2
>
>
<
s.c.
> x1 + 3x2 6 6
>
>
>
>
>
>
> 3x2 2x4 6 10
>
>
>
>
>
>
> x4 6 2
>
>
>
: x ;x ;x ;x > o
1 2 3 4

11
 Interprétation économique

• xj : nombre de produits finis de type j fabriqués.

• aij : quantité de matière première de type i nécessaire

pour fabriquer un produit de type j.

• bi : quantité de matière première de type i disponible.

• cj : bénéfice réalisé par produit fini de type j.

Chapitre 2

Méthodes de résolution du

programme linéaire

Il existe deux méthodes de résolution du programme linéaire : Méthode graphique et

méthode algébrique

2.1 Méthode graphique

La représentation graphique est une des techniques de résolution de programme linéaire.

Illustrons cette methode par un programme linéaire à deux variables x1 et x2 .

Soit : MaxF (x1 ; x2 ) = a0 x1 + b0 x2

8
>
> a1 x 1 + b 1 x 2 6 c 1
>
>
<
s.c.
> a2 x 1 + b 2 x 2 6 c 2
>
>
>
: x 1 ; x2 > 0

2.1.1 Quelques rappels de géométrie

Construction de la région réalisable

Soit : (Mi ) : ai x1 + bi x2 = ci

La droite (Mi ) partage le plan en deux démi-plans (P1 ) et (P2 )d’équation :

(P1 ) : ai x1 + bi x2 > ci

12
CHAPITRE 2. MÉTHODES DE RÉSOLUTION DU PROGRAMME LINÉAIRE

(P2 ) : ai x1 + bi x2 6 ci

Chaque contrainte détermine l’un des deux démi-plans (P1 ) et (P2 ) que l’on trouvera en

véri…ant si un point particulier est contenu dans l’un des deux démi-plans (P1 ) et (P2 ).

L’intersection de tous les démi-plans correspondant aux contraintes constitue l’ensemble

des points réalisables : ce sont les solutions communes à toutes les contraintes.

Cet ensemble est appelé domaine ou région réalisable (R) : Il peut être borné, ou non

borné ou vide.

La recherche d’une solution optimale.

La région réasilable (R) contient un nombre in…ni de solutions réalisables. Il reste à

repérer parmi ces solutions réalisables celles qui donnent à F (x1 ; x2 ) une valeur constante p

arbitrairement choisi. Ainsi on obtient la droite :

(DP ) : a0 x1 + b0 x2 = p:

Cette droite (DP ) est appelée droite d’iso-valeur de la fonction F . Elle représente les

points du plan qui donnent à F la valeur P .

Intéressons nous donc à la famille des droites (DP ) avec P paramè[Link] sont toutes les
a0
droites parallèles de pente : b0
(b0 6= 0)
a0 P
(DP ) : x2 = b0
x1 + b0
; (b0 6= 0)
P
Posons yp = b0
qui est l’ordonnée à l’origine de la droite (DP ).

P1
yp1 = b0

P2
yp2 = b0

B 1er cas : Si b0 0; alors p 1 p 2 () yp1 yp2

Si b0 0; alors maximiser F revient à maximiser P et donc maximiser yp :

Conséquence :

Le maximum de F est obtenu pour la droite ayant au moins un point commun avec la

région réalisable et ayant une ordonnée à l’origine la plus élevée possible.

13
Université Félix Houphouet-Boigny U.F.R - SSMT

a0 0 et b0 0 (voir la Fig. 1). Le point B est le point optimal.

a0 0 et b0 0 (voir la Fig. 2). Le point B est le point optimal.

Exemple 2.1.1. : Déterminer le point maximum et la valeur maximale de F dans les pro-

grammes linéaires suivants :

a. M axF (x1 ; x2 )8
= 5x1 + 8x2
>
>
>
> x1 + x2 6 13
>
>
>
>
< 5x1 + 2x2 6 50
s.c.
>
>
>
> 4x1 + 5x2 6 60
>
>
>
>
: x1 > 0 et x2 > 0

b. M axF (x; y) = 8 x + 2y
>
>
>
> x+y 61
>
>
>
>
< 2x y 6 3
s.c.
>
>
>
> 5x 3y 6 10
>
>
>
>
: x; y > 0

Dr. AKPATA Edouard 14

 2

n(ao,bo)
1

Fig. 1 : ao>0 ; bo>0 est le point optimal

B
A
n(ao,bo)

Fig. 2 : ao<0 ; bo>0 est le point optimal

CHAPITRE 2. MÉTHODES DE RÉSOLUTION DU PROGRAMME LINÉAIRE

B 2e cas : Si b0 0; alors p1 p 2 () yp1 yp2

Si b < 0, alors maximiser F , revient à maximiser p et par conséquent minimiser yp

Conséquence:

Le maximum de F est obtenu pour la droite ayant au moins un point commun avec la

région réalisable et ayant une ordonnée à l’origine la plus basse possible.

a0 0 et b0 0 (voir la Fig. 3). Le point B est le point optimal.

a0 0 et b0 0 (voir la Fig. 4). Le point B est le point optimal.

Conclusion:

Tous les points sur une même droite assurent la même valeur pour F . Quand on passe

d’une droite à une autre, les

0 valeurs
1 de F varient : ils augmentent si on se déplace dans le
! B a0 C
sens du vecteur normal n @ A aux droites iso-valeurs : d’où la signi…cation de la ‡èche
b0
indiquant le sens des F croissants.

Remarque 2.1.1. La méthode graphique est conseillée si le nombre de variable de décision

est égal à deux.

15
 2

A
B

n(ao,bo)

Fig. 3 : ao>0 ; bo<0 est le point optimal

B
1
n(ao,bo)

Fig. 4 : ao<0 ; bo<0 est le point optimal

Université Félix Houphouet-Boigny U.F.R - SSMT

2.1.2 Propriétes fondamentales de la programmation linéaire

Proposition 2.1.1. 1 : L’ensemble des points extrêmes (sommets) du domaine de réalisation

(R) correspondant à l’ensemble des solutions de base réalisables

Proposition 2.1.2. 2 : Si (R) 6= ? ; alors il exite au moins un sommet.

Proposition 2.1.3. 3 : Si une fonction linéaire atteint son maximum ou minimum sur (R),

alors cet optimum a lieu en un sommet de (R) :

2.2 Méthode algébrique

2.2.1 Méthode de base réalisable

Solution réalisable

On considère un programme linéaire sous forme standard (A x = b) :On suppose que la

matrice A est de type (m; n) :

On suppose que le rang de A; rg (A) = m , où m 6 n:

Rappels

Le système A x = b admet toujours de solutions.

Si m n, alors le système A x = b admet une in…nité de solutions.

Si m = n, alors le système A x = b admet une solution unique :

A x = b () x = A 1 b:

Dé…nition 2.2.1. On appelle solution réalisable, tout vecteur x qui satisfait les contraintes

du P:L tel que A x = b et x > 0:

Solution de base

Dé…nition 2.2.2. Soit J C f1; 2; 3; :::ng un ensemble d’indices avec card (J) = m tel que

les colonnes Aj ; j 2 J de A soient linéairement indépendantes ; autrement dit,la matrice

Dr. AKPATA Edouard 16

CHAPITRE 2. MÉTHODES DE RÉSOLUTION DU PROGRAMME LINÉAIRE

carrée B formée des colonnes Aj ; j 2 J est inversible.

Les bases de A sont les matrices carrées d’ordre m inversibles extraites de A dont les

colonnes sont Aj ; j 2 J:

L’ensemble J des indices est appelé support de x et on note sup p (x) :

Les variables(XB = X j ; j 2 J) sont appellées variables de base.

Les variables(XH = X j ; j 2
= J) sont appellées les variables hors-base.

Dé…nition 2.2.3. (solution0de base1)

B XB C
On dit que la solution X = @ Aest une solution de base associée à la base B si XH = 0:
XH
0 1
B XB C
Autrement dit si : X = @ A:
O Rn m

Dé…nition 2.2.4. (solution de base0réalisable)

1
B XB C
On dit que la solution de base X = @ A ; (XH = 0) est réalisable si les variables de base
XH
0 1
B XB C
sont positives ou nulles ; autrement dit si X = @ A ; avec XB > 0;Par extension, la
O Rn m
base B est dite réalisable.
0 S’il existe
1 au moins une variable de base nulle, alors la solution
B XB C
de base réalisable X = @ A est dite dégénérée.
O Rn m

Dé…nition 2.2.5. (solutions de base adjacentes)

On appelle solutions de base adjacentes, deux solutions de base dont les variables de base

sont les mêmes sauf une qui est de base dans la première et hors base dans la seconde.

Exemple 2.2.1. x = (x1 ; x2 ; x3 ; x4 ; x5 ) = (0; 0; 4; 12; 6)

y = (x1 ; x2 ; x3 ; x4 ; x5 ) = (0; 6; 4; 0; 5) x et y sont des solutions de bases adjacentes

Contre exemple :

x = (x1 ; x2 ; x3 ; x4 ; x5 ) = (0; 0; 4; 12; 18)

y = (x1 ; x2 ; x3 ; x4 ; x5 ) = (2; 6; 2; 0; 0)

17
Université Félix Houphouet-Boigny U.F.R - SSMT

x et y sont des solutions de bases non adjacentes puisqu’elles di¤èrent par plus d’une

variable hors base

Formulation du programme linéaire en fonction de la solution de base

Soit le programme linéaire suivant :

T
max F (x)
8= c x
>
< Ax = b
s:c:
>
: x>0
où A est une matrice de type (m;
0 n) telle
1 que rg(A) = m
B xB C
En posant A = (B j H) et x = @ A, alors on a :
xH
0 1
B xB C
Ax = b () (B j H) @ A=b
xH
Ax = b () BxB + HxH = b

T
F (x) =
0c X 1
B cB C
En posant c = @ A on a :
cH
0 1
B XB C
F (x) = (cB j cH ) @ A
XH
F (x) = cB XB + cH XH

Alors le P.L. devient :

max F (x) = cB XB + cH XH
8
>
< B XB + H XH = b
s.c.
>
: xB > 0; xH > 0

Expression de XB

B XB + H XH = b () XB = B 1 b B 1 HXH

Dr. AKPATA Edouard 18

CHAPITRE 2. MÉTHODES DE RÉSOLUTION DU PROGRAMME LINÉAIRE

Expression de F (x)

F (x) = cB XB + cH XH

= cB (B 1 b B 1 H XH ) + cH XH

= cB B 1 b cB B 1
H XH + cH XH

F (x) = cB B 1 b + (cH cB B 1
H) XH

=) F (x) = cB B 1 b + (cH cB B 1
H) XH

En posant : c H = cH cB B 1 H; on a :

F (x) = cB B 1 b + c H XH

Cas particulier : XB est une solution de base () XH = 0:

8
>
< XB = B 1 b
Alors :
>
: F (x) = cB B 1 b

Si XB est une solution de base réalisable , alors : XH = 0 et XB 0

d’où : XB = B 1 b 0

Théorème 2.2.1. Si c H = cH cB B 1 H 0, alors la solution de base réalisable

correspondante XB 0, (XH = 0) est une solution optimale du programme linéaire .

Ainsi :

max F (x) = F = cB B 1 b qui est la valeur maximale et XB = X = B 1 b qui est la

solution optimale.

Exemple 2.2.2. Soit le programme linéaire suivant :

maxF (x) = x1 + 2x2

8
> x +x
> 6
>
> 1 2
<
s.c. x2 3
>
>
>
>
: x 0 ; x2 0
1

19
Université Félix Houphouet-Boigny U.F.R - SSMT

Solution

Forme standard du programme linéaire

maxF (x) = x1 + 2x2

8 s.c.
>
> x1 + x2 + e1 = 6
>
>
<
> x2 + e2 = 3
>
>
>
: x ;x ;e ;e
1 2 1 2 0

Soit A la matrice associée au système des contraintes

0 1
B 1 1 1 0 C
A=@ A
0 1 0 1

card(J) = 2

Enumérons les di¤erents ensembles d’indice x = (x1 ; x2 ; e1 ; e2 )

J1 = f1; 2g ; J2 = f1; 3g ; J3 = f1; 4g ; J4 = f2; 3g ; J5 = f2; 4g ; J6 = f3; 4g

4 3 2 1
Nombre d’ensemble Ji : C42 = (4 2)!2!
=6

Déterminons les bases

0 associées
1 à Ji

B 1 1 C
J1 = f1; 2g =) B1 = @ A =) det(B1 ) = 1 6= 0 =) B1 est une basse
0 1
0 1
B 1 1 C
J2 = f1; 3g =) B2 = @ A =) det(B2 ) = 0 =) B2 n’est pas une base ;
0 0
0 1
B 1 0 C
J3 = f1; 4g =) B3 = @ A =) det(B3 ) = 1 6= 0 =) B3 est une basse ;
0 1
0 1
B 1 1 C
J4 = f2; 3g =) B4 = @ A =) det(B4 ) = 1 6= 0 B4 est une base ;
1 0
0 1
B 1 0 C
J5 = f2; 4g =) B5 = @ A =) det(B5 ) = 1 6= 0 =) B5 est une basse ;
1 1

Dr. AKPATA Edouard 20

CHAPITRE 2. MÉTHODES DE RÉSOLUTION DU PROGRAMME LINÉAIRE

0 1
B 1 0 C
J6 = f3; 4g =) B6 = @ A =) det(B6 ) = 1 6= 0 B6 est une base.
0 1

Déterminons les solutions de bases réalisables.

0 10 1 0 1
B 1 1 CB 6 C B 3 C
1. J1 = f1; 2g =) XB1 = B1 1 b = @ A@ A = @ A 0
0 1 3 3
=) XB1 est une solution de base réalisable ; autrement dit X1 = (3; 3; 0; 0) est une

solution de base réalisable.

0 10 1 0 1
B 0 1 CB 6 C B 3 C
2. J2 = f1; 3g =) XB2 = B2 1 b = @ A@ A = @ A ni positif ni
0 1 3 3
négatif

=) X2 = f 3; 0; 3; 0g est une solution de base non réalisable.

0 10 1 0 1
B 1 0 CB 6 C B 6 C
3. J3 = f1; 4g =) XB3 = B3 1 b = @ A@ A = @ A 0
0 1 3 3

=) X3 = (6; 0; 0; 3) est une solution de base réalisable.

0 10 1 0 1
B 1 1 CB 6 C B 3 C
4. J4 = f2; 3g =) XB4 = B4 1 b = @ A@ A = @ A ni positif ni
1 0 3 6
négatif

=) X4 = f 0; 3; 3; 0g est une solution de base non réalisable.

0 10 1 0 1
B 1 0 CB 6 C B 6 C
5. J5 = f2; 4g =) XB5 = B5 1 b = @ A@ A = @ A
1 1 3 3

=) X5 = (0; 6; 0; 3) est une solution de base non réalisable.

0 10 1 0 1
B 1 0 CB 6 C B 6 C
6. J6 = f3; 4g =) XB6 = B6 1 b = @ A@ A = @ A 0
0 1 3 3

=) X6 = (0; 0; 6; 3) est une solution de base réalisable.

On obtient 3 solutions de base réalisables : X1 = (3; 3; 0; 0) ; X3 = (6; 0; 0; 3) ;

X6 = (0; 0; 6; 3)

21
Université Félix Houphouet-Boigny U.F.R - SSMT

Déterminons la solution optimale éventuelle.

F (x) = x1 + 2 x2 + 0 e1 + 0 e2
0 1 0 1 0 1
B 3 C B 0 C B 0 C
1. J1 = f1; 2g =) XB1 = @ A ; XH1 = @ A ; cB1 = (1 2) ; cH1 = @ A et
3 0 0
0 1
B 1 0 C
H1 = @ A
0 1
0 1 0 10 1 0 1
B 0 C B 1 1 CB 1 0 C B 1 1 C
c H1 = cH1 cB1 B1 1 H1 = @ A (1 2) @ A@ A= (1 2) @ A
0 0 1 0 1 0 1

0 1
B 1 C
c H1 =@ A 0 () X1 = (3; 3; 0; 0) est une solution optimale.
1
0 1 0 1
B 6 C B 0 C
2. J3 = f1; 4g =) XB3 = @ A ; XH3 = @ A ; cB3 = (1 0) ; cH3 = (2 0)
3 0
0 10 1
B 1 0 CB 1 1 C
c H3 = cH3 cB3 B3 1 H3 = (2 0) (1 0) @ A@ A
0 1 1 0
0 1
B 1 1 C
= (2 0) (1 0) @ A
1 0
= (2 0) (1 1)

=) c H3 = (1 1) ni positif ; ni négatif

=) X3 est une solution non optimale.

0 1 0 1
B 6 C B 0 C
3. J6 = f3; 4g =) XB6 = @ A ; XH6 = @ A ; cB6 = (0 0) ; cH6 = (1 2)
3 0
0 1
B 1 1 C
et H6 = @ A
0 1

Dr. AKPATA Edouard 22

CHAPITRE 2. MÉTHODES DE RÉSOLUTION DU PROGRAMME LINÉAIRE

0 10 1
B 1 0 CB 1 1 C
c H6 = (1 2)
(0 0) @ A@ A = (1 2) 0
0 1 0 1
=) X6 est une solution non optimale.

x1 = x = (3; 3; 0; 0) est la solution optimale

max F (x) = F = 3 + 2 3=9

2.2.2 Méthode de programme de base

Dé…nition 2.2.6. On appelle programme de base l’identi…cation des variables, la donnée de

la fonction objectif et celle du système d’inéquation linéaire correspondant au contraintes.

Dé…nition 2.2.7. Un processus de base est dit optimale si tous les coe¢ cients des variables

hors programme dans l’expression de la fonction objectif sont négatifs ou nuls.

Illustrons cette méthode par l’exemple suivant

max F (x1 ; x2 ) = 5 x1 + 8 x2
8
>
>
>
> x1 + x2 6 13
>
>
>
>
< 5 x1 + 2 x2 6 50
s.c.
>
>
>
> 4 x1 + 5 x2 6 60
>
>
>
>
: x1 > 0; x2 > 0

La forme standard du programme linéaire est la suivante :

max8F (x1 ; x2 ) = 5 x1 + 8 x2
>
>
>
> x1 + x2 + x3 = 13
>
>
>
>
< 5 x1 + 2 x2 + x4 = 50
s.c.
>
>
>
> 4 x1 + 5 x2 + x5 = 60
>
>
>
>
: xj > 0

Programme initial

Pour déterminer le programme initial, on pose habituellement à zéro, les variables prin-

cipales du modèle ; x1 = 0 et x2 = 0

23
Université Félix Houphouet-Boigny U.F.R - SSMT

Alors le système devient :

Variables dans le programme Variables hors programme

en fonction de
xj 6= 0 j = 3; 4; 5 xj = 0; x1 = x2 = 0

8
>
> x3 = 13 x1 x2
>
>
<
On a : x4 = 50 5 x1 2 x2
>
>
>
>
: x = 60 4 x1 5 x2
5

x3 ; x4 ; x5 sont les variables dans le programme

x1 ; x2 sont ls variables hors programme.

Alors on a : x1 = 0; x2 = 0; x3 = 13; x4 = 50; x5 = 60

La valeur de F (x1 ; x2 ) = 5:0 + 8:0 = 0

On obtient le premier programme de base

Programme de base N 1

x1 = 0

x2 = 0

x3 = 13

x4 = 50

x5 = 60

F (x) = 0

Remarque 2.2.1. Dans le programme de base initial, on exprime toujours les variables

d’écart en fonction des variables de décision.

Révision du programme initial

On doit chercher à ameliorer la valeur de la fonction objectif en introduisant l’une des

varibles de décision (hors programme) x1 ou x2 dans le programme de base et en sortant une

variable actuellement dans le programme de base.

Dr. AKPATA Edouard 24

CHAPITRE 2. MÉTHODES DE RÉSOLUTION DU PROGRAMME LINÉAIRE

Le choix de la variable (actuellement hors programme) à introduire dans le programme

s’e¤ectue à l’aide d’un critère qui permet d’ameliorer le plus rapidement possible la valeur

de la fonction objectif.

Critère d’entrée d’une variable dans le programme de base

F (x) = 5 x1 + 8 x2

On choisit la variable dont les coe¢ cients sont positifs et ayant le plus grand coe¢ cient.

Alors on choisit x2 car 8 5 ; autrement dit la variable x2 est une variable dans le

programme.

Donc : variable entrante: x2

Détermination de la variable x2
8 8
>
> x3 = 13 x1 x2 >
> x3 > 0
>
> >
>
< <
x4 = 50 5 x1 2 x2 ( ) ; x4 > 0
>
> >
>
>
> >
>
: x = 60 4 x 5 x2 : x > 0
5 1 5

8
>
> 13 x2 > 0
>
>
<
()
> 50 2 x2 > 0 ; car x1 = 0
>
>
>
: 60 5 x > 0
2

8
>
> x2 6 13
>
>
<
()
> x2 6 25
>
>
>
: x 6 12
2

Pour s’assurer que toutes les contraintes sont respectées en même temps : on choisit de

ces valeurs la plus petite possible

x2 = 12

Pour x2 = 12; on trouve x5 = 0

Donc variable sortante : x5 = 0

25
Université Félix Houphouet-Boigny U.F.R - SSMT

Du système ( ) on a :

x1 = 0; x2 = 12; x5 = 0; x3 = 1; x4 = 26

Ainsi, on obtient :

Programme de base N 2

x1 = 0

x2 = 12

x3 = 1 x1 ; x5 sont des variables hors programme

x4 = 26 x2 ; x3 ; x4 sont des variables dans le programme

x5 = 0

F (x) = 96

F (0; 12; 1; 26; 0) = 8 12 = 96

Pour s’asssurer que la valeur maximale de F est atteinte ou non, il faut exprimer cette

fonction F (x) en fonction des variables hors programme : x1 et x5

Du système ( ) ; on a :
8
>
> x3 = 13 x1 x2
>
>
<
x4 = 50 5 x1 2 x2 et F (x) = 5 x1 + 8 x2
>
>
>
>
: x = 60 4 x1 5 x2
5

4 1
x5 = 60 4x1 5x2 = x2 = 12 5
x1 5
x5
32 8
F (x) = 5x1 + 96 5
x1 5
x5
7 8
F (x) = 96 5
x1 5
x5

On remarque que tous les coe¢ cients des variables hors programme dans la fonction

objectif sont négatifs.

Alors la valeur maximale est atteinte et la solution optimale est :

x = (0; 12; 1; 26; 0)

F = 96

Dr. AKPATA Edouard 26

CHAPITRE 2. MÉTHODES DE RÉSOLUTION DU PROGRAMME LINÉAIRE

Exercices

a. max F (x1 x2 ) = 3x1 + 3x2

x1 ; x2
8
>
> x1 + 4x2 6 12
>
>
<
s.c.
> 2x1 + x2 6 10
>
>
>
: x ;x > 0
1 2

b. max F (x1 x2 ) = 100x1 + 120x2

x1 ; x2
8
>
> x1 + 3x2 6 2400
>
>
<
s.c.
> 2x1 + 2x2 6 2600
>
>
>
: x 1 ; x2 > 0

Remarque 2.2.2. Si les variables dans la fonction objectif sont de coe¢ cients positifs égaux

alors on choisit celle qui a le plus petit indice.

a. max F (x1 ; x2 ) = x1 + 2x2

x1 ; x2
8
>
> x1 + x2 6 6
>
>
<
s.c.
> x2 6 3
>
>
>
: x ;x > 0
1 2

Solution

a. max F (x1 ; x2 ) = 3 x1 + 3x2

x1 ; x2

8
>
> x1 + 4 x2 6 12
>
>
<
> 2 x1 + x2 6 10
>
>
>
: x > 0; x > 0
1 2

La forme standard du programme linéaire

8
>
> x1 + 4 x2 + x3 = 12
>
>
<
2 x1 + x2 + x4 = 10 (1)
>
>
>
>
: x ;x ;x ;x > 0
1 2 3 3

27
Université Félix Houphouet-Boigny U.F.R - SSMT

x1 et x2 sont les variables hors base et x3 ; x4 sont les variables dans le programme de

base.
8
>
< x3 = 12 x1 4 x2
De (1) on a :
>
: x4 = 10 2 x1 x4

8
>
< x3 = 12
Or x1 = x2 = 0 ()
>
: x4 = 10

D’où le programme N 1

x1 = 0

x2 = 0

x3 = 12

x4 = 10

F (x) = 0

Améliorons la valeur de la fonction objectif :

F (x1 ; x2 ) = 3 x1 + 3x2

La variable entrante est x1 () x2 = 0

Déterminons la valeur maximale de x1

8 8 8
>
< x3 > 0 >
< 12 >
< x1 6 12
x1 > 0
() () () X1 = 5
>
: x4 > 0 >
: 10 >
: x1 6 5
2 x1 > 0

Déterminons la variable sortante

pour x1 = 5; x2 = 0 () x4 = 0 () x4 est la variable sortante

D’où le programme de base N 2

Dr. AKPATA Edouard 28

CHAPITRE 2. MÉTHODES DE RÉSOLUTION DU PROGRAMME LINÉAIRE

x1 = 5

x2 = 0

x3 = 7

x4 = 0

F (5; 0; 7; 0) = 15

Déterminons la variable F (x2 ; x4 )

F (x1 ; x2 ) = 3 x1 + 3x2

De (1), on a : 2 x1 + x2 + x4 = 10
1 1
2 x1 = 10 x2 x4 () x1 = 5 2
x2 2
x4
1 1
=) F (x2 ; x4 ) = 3 5 2
x2 2
x4 + 3 x2
3 3
= 15 2
x2 2
x4 + 3 + 3 x2
3 3
F (x2 ; x4 ) = 15 + 2
x2 2
x4

3
La variable x2 a pour coe¢ cient 2
0 =) la valeur de F (x2 ; x4 ) peut être ameliorée.

=) x2 est la variable entrante

Déterminons alors sa valeur maximale

Exprimons x1 et x3 en fonction de x2 et x4
8
>
< x1 = 5 1 1
2
x2 2
x4
De (1) on a :
>
: x3 = 12 x1 4 x2

8
>
< x1 = 5 1 1
2
x2 2
x4
>
: x3 = 12 1 1
5+ 2
x2 + 2
x4 4 x2

8
>
< x1 = 5 1 1
2
x2 2
x4
>
: x3 = 7 7 1
2
x2 + 2
x4

8 8
>
< x1 > 0 >
< 5 1
2
x2 > 0
Or () , car x4 = 0
>
: x3 > 0 >
: 7 7
2
x2 > 0

29
Université Félix Houphouet-Boigny U.F.R - SSMT

8
>
< x2 6 10
() x2 = 2
>
: x2 6 2

Pour x2 = 2 () x3 = 0 donc x3 est la variable sortante x2 = 2; x4 = 0; x3 = 0

et x1 = 4

D’où le programme de base N 3

Programme de base N 3

x1 = 4

x2 = 2

x3 = 0

x4 = 0

F (4; 2; 0; 0) = 18

Déterminons F (x3 ; x4 )

3 3
F (x2 ; x4 ) = 15 + 2
x2 2
x4

7 1
De (2) on a : x3 = 7 2
x2 + 2
x4
2 1
x2 7
x3 + 7
x4

3 2 1 3
F (x3 ; x4 ) = 15 + 2
2 7
x3 + 7
x4 2
x4

3 9
F (x3 ; x4 ) = 18 x3 x4
7 7

On remarque que tous les coe¢ cients des variables x3 et x4 sont négatifs donc la valeur

maximale de la fonction objectif est atteinte.

=) x = (4; 2; 0; 0) est la solution optimale

et F = 18 est la valeur de la fonction objectif.

Dr. AKPATA Edouard 30

CHAPITRE 2. MÉTHODES DE RÉSOLUTION DU PROGRAMME LINÉAIRE

2.2.3 Méthode du simplexe

Algorithme du simpexe

On considère le programme linéaire suivant :

max F (x1 ; x2 ; : : : ; xn ) = c1 x1 +c2 x2 + +cn xn ; où x = (x1 ; x2 ; : : : ; xn )

x

8
>
> a11 x1 + a12 x2 + + a1n xn b1
>
>
>
>
>
>
>
> a21 x1 + a22 x2 + + a2n xn b2
>
<
s.c.
>
>
>
>
>
> am1 x1 + am2 x2 + + amn xn bm
>
>
>
>
>
: x
1 0; x2 0; : : : xn 0;

Forme standard

max F (x1 ; x2 ; : : : ; xn ) = c1 x1 +c2 x2 + +cn xn +0e1 +0e2 + +0em

x

8
>
> a11 x1 + a12 x2 + + a1n xn + e1 = b1
>
>
>
>
>
>
>
> a21 x1 + a22 x2 + + a2n xn + e2 = b2
>
<
s.c. ;
>
>
>
>
>
> am1 x1 + am2 x2 + + amn xn + em = bm
>
>
>
>
>
: x
1 0; x2 0; : : : xn 0; ei 0

où e1 ; e2 ; : : : : : : em sont les m variables d’écart du problème.

Etape 0 : On forme le tableau initial

B x1 x2 ::: xn e1 e2 ::: em

e1 a11 a12 ::: a1n 1 0 0 b1

e2 a21 a22 ::: a2n 0 1 0 b2

.. .. .. .. .. .. .. .. .. ..
. . . . . . . . . .

em am1 am2 ::: amn 0 0 ::: 1 bm

c1 c2 ::: cn 0 0 ::: 0 0

31
Université Félix Houphouet-Boigny U.F.R - SSMT

La base initiale de l’espace-colonne sera f e1 ; e2 ; : : : : : : : : : ; em g ;

Les autres variables seront égales à 0 ; ce qui correspond au point de départ

x = (0; 0; : : : ; 0).

Etape 1 : On doit choisir la collone de pivot

Pour cela, on choisit l’indice j tel que : cj = max f ci = ci > 0 g :

Si aucun choix n’est possible, alors la solution optimale est atteinte et l’algo

rithme se termine.

Sinon, on passe à l’étape suivante.

Pour un problème de minimisation, on modi…e le critère en choisissant l’indice

j tel que : cj = min f ci = ci < 0 g :

Etape 2 : On doit choisir la ligne de pivot

Pour cela, on choisit l’indice i en utilisant le critère du quotient :

bi bk
= min = akj > 0; k = 1; 2; : : : : : : ; m , où j est la colonne de pi
aij akj
vot de l’étape 1.

Ainsi la ligne de pivot est la k eme ligne et le pivot est le coe¢ cient akj situé à

l’intersection de la ligne k et de la colonne j.

On rend unitaire le pivot akj en divisant la ligne de pivot par ce pivot.

On applique la procédure d’élimination de Gauss-Jordan ou la méthode du rectangle

autour du pivot (déjà unitaire) ; autrement dit, on annule tous les éléments de la

colonne

de pivot par rapport au pivot unitaire.

Si tous les coe¢ cients cij sont négatifs ou nuls, alors l’algorithme se termine. Ainsi

la valeur maximale de la fonction objectif et la solution optimale sont atteintes.

Sinon, on retourne à l’étape 1.

Remarque 2.2.3. 1. La valeur maximale de la fonction objectif est l’opposée de la valeur

qui se trouve à l’intersection de la ligne des coe¢ cients cij et de la colonne des constantes

Dr. AKPATA Edouard 32

CHAPITRE 2. MÉTHODES DE RÉSOLUTION DU PROGRAMME LINÉAIRE

bi du second membre.

2. Lorsque la ligne de pivot croise une colonne en 0, alors on conserve cette colonne ;

3. La variable se trouvant sur la colonne de pivot devient la variable entrante ;

4. La variable se trouvant sur la ligne de pivot devient la variable sortante.

Résolvons le programme linéaire suivant

max F (x1 ; x2 ) = 3 x1 + 3x2

8
>
> x1 + 4 x2 6 12
>
>
<
s.c.
> 2 x1 + x2 6 10
>
>
>
: x ;x > 0
1 2

La forme standard du P.L est la suivante :

max F (x1 ; x2 ) = 3 x1 + 3x2

8
>
> x1 + 4 x2 + e1 = 12
>
>
<
s.c. 2 x1 + x2 + e2 = 10
>
>
>
>
: x ;x ;e ;e > 0
1 2 1 2

Etape 0

Ecrivons le système de contraintes et la fonction objectif dans un tableau :

B x1 x2 e1 e2 s:m:

e1 1 4 1 0 12

e2 2 1 0 1 10

3 3 0 0 0

Déterminons la colonne et la ligne du pivot.

Colonne du pivot

Il faut déterminer le plus grand coe¢ cient positif des variables de la fonction objectif.

Les deux variables x1 et x2 ayant le même coe¢ cient,alors le coe¢ cient de la variable

x1 sera choisi :

33
Université Félix Houphouet-Boigny U.F.R - SSMT

On remarque que le coe¢ cient 3 appartient à la 1ère colonne de la matrice. Ainsi la

première colonne est dite colonne du pivot.

Ligne du pivot

Il faut diviser les éléments de la dernière colonne de la matrice par les éléments corres-

pondants de la colonne de pivot : on trouve les rapports : 12 et 5.

On choisit la plus petite valeur des rapports et qui appartient à une des lignes de la

matrice.

5 étant la plus petite valeur et qui appartient à la 2e ligne de la matrice, alors cette ligne

est appelée ligne du pivot.

L’intersection de la ligne du pivot et de la colonne du pivot nous fournit l’élément du

pivot.

Donc 2 est l’élément du pivot.

Une fois l’élément du pivot trouvé, il faut le rendre unitaire

B x1 x2 e1 e2 s:m: rapport

e1 1 4 1 0 12 12 1 = 12

e2 2 1 0 1 10 10 2=5

3 3 0 0 0
1 2
e1 0 7/2 1 7 7 =2
2 7
1 1
x1 1 0 5 5 2 = 10
2 2
3 3
0 0 15
2 2
2 1
x2 0 1 2
7 7
1 4
x1 1 0 4
7 7
3 9
0 0 18
7 7

On remarque que tous les coe¢ cients de la dernière ligne ne sont pas négatifs. Alors la

valeur de la fonction objectif peut être améliorée.

Déterminons la colonne du pivot.

Dr. AKPATA Edouard 34

CHAPITRE 2. MÉTHODES DE RÉSOLUTION DU PROGRAMME LINÉAIRE

3 3
2
0 et 2
est sur la 2e colonne alors cette colonne est la colonne du pivot.

Déterminons la ligne du pivot

La ligne du pivot est la première ligne de la matrice. Ainsi l’élément du pivot est
7
:
2
Rendons le unitaire

Annulons tous les éléments de la colonne du pivot par rapport à ce pivot.

On remarque que tous les éléments de la dernière ligne de la matrice sont négatifs. Donc

la valuer maximale de la fonction objectif est atteinte. (voir le tableau)

La solution optimale x est :

x = (4; 2; 0; 0) et la valeur maximale de la fonction objectif est F : F = 18.

Démarche à suivre pour la méthode du simplexe

La méthode du simplexe est une recherche systématique de programme de base

(points sommets) jusqu’à l’obtention du programme optimal :

Pour cela il s’agit de :

1: Structurer le problème sous forme d’un système d’équations linéaires en introdui-

sant les variables d’écart requis ainsi que la fonction objectif.

2: Déterminer la colonne (sauf la dernière) dont l’élément de la dernière ligne à la

plus grande valeur positive :c’est la colonne du pivot.

3: Déterminer la ligne du pivot en faisant le rapport des éléments correspondant de

la colonne du pivot.

La ligne du pivot étant celle donnant le plus petit rapport positif.

4: Rendre le pivot unitaire c’est-à-dire l’élément égal à 1 appartenant à l’intersection

de la colonne du pivot.

5: Annuler tous les termes de la colonne du pivot par rapport à ce pivot.

6: Repéter les 5 premières étapes jusqu’à ce que tous les éléments de la dernière ligne

35
Université Félix Houphouet-Boigny U.F.R - SSMT

soient non positifs.

7: 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.

La valeur maximale de la fonction objectif (plus exactement sont opposé) est donnée

dans la dernière ligne, dernière colonne.

Exemple 2.2.3. Maximiser la fonction objectif dans le programme linéaire suivant :

F (x1 ; x2 ) = 6 x1 + 4 x2
8
>
>
>
> 3 x1 + 9 x2 6 81
>
>
>
>
< 4 x1 + 5 x2 6 55
s.c.
>
>
>
> 2 x1 + x2 6 20
>
>
>
>
: x 1 ; x2 > 0

2.2.4 Méthode de Simplexe- Cas particuliers

1. Les coe¢ cents de la fonction objectif sont égaux

Le choix de la colonne de pivot pose problème si certains coe¢ cients de la fonction

objectif sont égaux.

Pour faire le meilleur choix de la colonne de pivot, on procède de la manière suivante :

- On détermine les pivots possibles en identi…ant les lignes de pivot éventuelles.

- On détermine la meileure colonne de pivot en choisissant le pivot correspondant au

plus grand des rapports identi…ant les pivots éventuels.

max F (x; y) = 12 x + 12 y

Dr. AKPATA Edouard 36

CHAPITRE 2. MÉTHODES DE RÉSOLUTION DU PROGRAMME LINÉAIRE

8
>
> x+y 67
>
>
<
s.c.
> 2 x+y 69
>
>
>
: x > 0; y > 0

Forme standard

max F (x; y) = 12 x + 12 y
8
>
> x + y + e1 = 7
>
>
<
s.c. 2 x + y + e2 = 9
>
>
>
>
: x > 0; y > 0; e > 0; e > 0
1 2

Alors on obtient le tableau suivant :

x y e1 e2 S:m: R

e1 1 1 1 0 7 7=1 7=1

e2 2 1 0 1 9 9=2 9=1

F (x; y) 12 12 0 0 0

En choisissant la colonne de x; le pivot éventuel est 2.

En prenat la colonne de y, le pivot éventuel est 1:

Ainsi les rapports identi…ants les pivots éventuels sont : 9=2 et 7=1

Pour choisir le pivot, on prend le plus grand des 2 rapports ; c’est-à-dire : 7=1

Alors le pivot est 1 et la colonne de pivot est celle de y.

2. Egalité des plus petits rapports positifs

Le choix de la ligne de pivot pose problème si les plus petits rapports positifs sont égaux.

Pour faire le bon choix de la ligne de pivot, on procède de la manière suivante :

On détermine le rapport de la somme des éléments de chaque ligne de pivot

éventuelle par le pivot éventuel.

On choisit la ligne de pivot correspondant au plus grand des rapports calculés

37
Université Félix Houphouet-Boigny U.F.R - SSMT

ci-dessus.

M ax F (x; y) = 8 x + 5 y
8
>
> x+y 67
>
>
<
s.c.
> 2 x + y 6 14
>
>
>
: x > 0; y > 0

Forme standard

M ax F (x; y) = 8 x + 5 y

8
>
> x + y + e1 = 7
>
>
<
s.c. 2 x + y + e2 = 14
>
>
>
>
: x > 0; y > 0; e > 0; e > 0
1 2

On obtient le tableau suivant :

Base x y e1 e2 S:m R

e1 1 1 1 0 7 7=1 = 7

e2 2 1 0 1 14 14=2 = 7

F (x; y) 8 5 0 0 0

8 5 0 () La colonne de pivot est celle de X

On remarque que les deux rapports sont égaux à 7.

En calculant les rapporst, on obtient :

1ere ligne de pivot éventuelle :

1 + 1 + 1 + 0 = 3; 3=1 pivot =3

2e ligne de pivot éventuelle :

2 + 1 + 0 + 1 = 4; 4=2 pivot =2

On choisit la ligne de pivot correspondant au plus grand des 2 rapports : 3=1 et 4=2

Donc la ligne de pivot est celle de e1 :

Dr. AKPATA Edouard 38

CHAPITRE 2. MÉTHODES DE RÉSOLUTION DU PROGRAMME LINÉAIRE

2.2.5 Méthode du GRAND M

Variables arti…cielles

La méthode du grand M consiste à :

1: Introduire des variables dites arti…cielles ai (i = 1; :::; p) dans les contraintes qui

posent un problème pour la réalisation de la base initiale.

Les variables arti…cielles interviennent exclusivement dans les contraintes égalités ou in-

égalités tournées dans le sens supérieur ou égal à le second membre étant positif et ceci

indépendamment de la nature de l’objectif : recherche d’un maximum ou d’un minimum.

P
2: Remplacer la fonction objectif par : M ax F (x) = ct x M m ai ou
P
M in F (x) = ct x + M m ai, où M est une constante positive assez grande.

3: En pratique, on n’est pas obligé de donner une valeur à M .

4: Chaque fois que M est comparé à un nombre, il sera toujours considéré comme

plus grand ;

5: Si la méthode de simplexe se termine avec une solution (x ; a ) telle que

a = (a1 ; a2 ; :::; ap ) = 0 ,alors x est une solution optimale du problème de départ.

6: Si la méthode du simplexe se termine avec une solution (x ; a ) telle que a 6= 0

(c’est-à-dire qu’au moins une variable arti…cielle est encore dans la base dans le

tableau optimal) alors le problème est non réalisable.

Exemple 2.2.4. Soit le problème suivant :

M in F (x) = x1 + x2
8
>
> 7 x1 + 5 x2 > 40
>
>
<
s.c.
> x1 + 4 x2 > 9
>
>
>
: x > 0; x > 0
1 2

39
Université Félix Houphouet-Boigny U.F.R - SSMT

Forme standard :

M in F (x) = x1 + x2 + 0 e1 + 0 e2 + M a1 + M a2
8
>
> 7 x1 + 5 x2 e1 + a1 = 40
>
>
<
s.c. x1 + 4 x2 e2 + a2 = 9
>
>
>
>
: xj > 0; e2 > 0; a1 > 0

Exprimons F (x) en fonction de M

8
>
< a1 = 40 7 x1 5 x2 + e1
>
: a2 = 9 x1 4 x2 + e2

En posant x1 = x2 = e1 = e2 = 0; on a :
8
>
< a1 = 40
() F (M ) = 40 M + 9 M = 49 M:
>
: a2 = 9

et

F (x) = x1 + x2 + M (40 7 x1 5 x2 + e1 ) + M (9 x1 4 x2 + e2 )

F (x) = (1 7M M ) x1 + (1 5M 4 M ) x2 + M e1 + M e2 + 49 M:

Ainsi, on obtient le tableau suivant :

Base x1 x2 e1 e2 a1 a2 S:m R

a1 7 5 1 0 1 0 40 40=5 = 8

a2 1 4 0 1 0 1 9 9=4 = 2; 5

F 1 8M 1 9M M M 0 0 49 M

1 9M 1 8M 0; alors la colonne de pivot est celle de x2 :

( A vous de continuer l’exercice ! ! !)

Exercise 1. (Solutions multiples)

M ax F (x) = x1 x2

Dr. AKPATA Edouard 40

CHAPITRE 2. MÉTHODES DE RÉSOLUTION DU PROGRAMME LINÉAIRE

8
>
>
>
> 2 x1 x2 > 4
>
>
>
>
< x1 x2 6 4
s.c.
>
>
>
> x1 + x2 6 10
>
>
>
>
: x1 0; x2 0

Exercise 2. (Solution impossible)

8min (F ) = x1 + x2 + M a
>
>
>
> 2 x1 x2 > 2
>
>
>
>
< x1 2 x2 6 8
s.c.
>
>
>
> x1 + x2 6 5
>
>
>
>
: x1 > 0; x2 0

Forme standard
8
>
>
>
> 2 x1 + x2 + e1 = 2
>
>
>
>
< x1 + 2 x2 e2 + a = 8
>
>
>
> x1 + x2 + e3 = 5
>
>
>
>
: x1 ; x2 ; e1 ; e2 ; a 0

(On trouve que a = 1 () Solution impossible)

Exercise 3. (Solution non bornée)

M ax F (x) = 10 x1 + 14 x2
8
>
>
>
> x1 + x2 > 12
>
>
>
>
< x1 > 8
s.c.
>
>
>
> x2 6 6
>
>
>
>
: xj > 0

Forme standard

41
Université Félix Houphouet-Boigny U.F.R - SSMT

M ax F (x) = 10 x1 + 14 x2 + M a1 + M a2
8
>
>
>
> x1 + x2 e1 + a1 = 12
>
>
>
>
< x1 e2 + a2 = 8
s.c.
>
>
>
> x2 + e3 = 6
>
>
>
>
: xj > 0; e1 > 0; a1 > 0

Dr. AKPATA Edouard 42

Chapitre 3

DUALITE EN PROGRAMMATION

LINEAIRE

Introduction :
La dualité est notion essentielle en programmation linéaire. A un programme linéaire

donné appelé primal est associé un programme linéaire appelé dual qui ne sera dé…ni qu’à

l’aide des donnés du primal.

3.1 Construction du modèle dual

Exemple 3.1.1. Une usine fabrique deux types de jouets en bois : des soldats et trains. Les

donnés de ce problème sont représentées dans le tableau suivant :

Menuiserie/h Finition/h Pro…t

1 soldat 1 2 3 u.m.

1 train 1 1 2 u.m.

Par semaine, l’usine dispose de toutes les matières premières nécéssairs à la fabrication

et ne dispose que 100h de …nition et 80h de menuiserie. La demande des trains et des soldats

est illimitée.

43
Université Félix Houphouet-Boigny U.F.R - SSMT

Déterminer le plan de production qui maximise le pro…t de l’usine.

Supposons qu’un client voudrait achéter la totalité des réssources disponibles.

Les réssources disponibles étant les atéliers de ménuiserie et de …nition. Alors le Directeur

de l’usine acceptera-t-il cette proposition si le prix o¤ert par le client lui apporte le même

pro…t provenant de la vente des jouets ?.

Ainsi, nous allons modéliser le premier problème sans la proposition du client.

Soient x1 et x2 le nombre de soldats et de trains respectivement à fabriquer.

Alors F (x1 ; x2 ) = 3 x1 + 2 x2
8
>
> 2 x1 + x2 100 (…nition)
>
>
<
Les contraintes : x1 + x2 80 (menuiserie)
>
>
>
>
: x 0; x2 0
1

Avec la proposition du client, on dispose :

y1 : Le prix d’une heure de menuiserie

y2 : Le prix d’une heure de …nition

La disponibilité des ressources est : 80h de menuiserie et 100h de …nition.

Le client va chercher à minimiser les frais d’achat des ressources.

M in w (y1 ; y2 ) = 80 y1 + 100 y2 sous les contraintes que lesprix satisfont la

direction de l’usine.

Les contraintes seront déduits de la manière suivante :

Pour le jouet soldat :

La fabrication de chaque soldat nécessite 1h de menuiserie et 2h de …nition ;

ce qui veut dire que le revenu engendré par la vente de ces ressources est : y1 + 2 y2

Sachant que le pro…t engendré par la fabrication et la vente d’un soldat est 3 u:m:

D’où : :

Dr. AKPATA Edouard 44

CHAPITRE 3. DUALITE EN PROGRAMMATION LINEAIRE

y1 + 2 y2 3:

De même pour le jouet train :

y1 + y2 2

Le prix de vente des ressources sont bien sûr positifs : y1 > 0; y2 > 0:

Alors on obtient les deux problèmes :

3.2 Programme linéaire : Primal

Direction de l’usine

M ax F (x1 ; x2 ) = 3 x1 + 2 x2
8
>
> x1 + x2 6 80
>
>
<
s.c.
> 2 x1 + x2 6 100
>
>
>
: x > 0; ; x > 0
1 2

3.3 Programme linéaire : Dual

Proposition du client :

min w (y1 ; y2 ) = 80 y1 + 100 y2

8
>
> y1 + 2 y2 > 3
>
>
<
s.c.
> y1 + 2 y2 > 2
>
>
>
: y ; y >0
1 2

3.3.1 Les caractéristiques du programme linéaire dual

La dualité est caractérisée par les règles suivantes :

1: Le sens de l’optimisation est inversé.

La maximisation ( resp. minimisation) dans le primal devient une minimisation ( resp.

maximisation) dans le dual.

45
Université Félix Houphouet-Boigny U.F.R - SSMT

2: Les coe¢ cients de la fonction objectif du primal deviennent les seconds membres

des contraintes du dual.

Les seconds membres des contraintes du primal deviennent les coe¢ cients de la fonction

bjectif du dual.

3: Les signes dans les inégalités des contraintes ou dans la contrainte de la positivité

des variables de décision suivent des règles précises de transformation (voir le tableau )

4: Comme le problème dual du dual est le problème primal initial , alors il convient

de parler d’une paire de problèmes de programmation liés par la dualité.

3.3.2 Règle de dualité

M aximisation devient M inimisation

Nombre de contraintes Nombre de variables

Nombre de variables Nombre de contraintes

Signes des contraintes Si gnes des variables principales

= quelconque

Signes des variables de decision Signes des contraintes

quelconque =

1:

Primal : Dual :

M a F (x1 ; x2 ) = x1 + 3 x2 min W (y1 ; y2 ; y3 ) = 14 y1 + 12 y2 + 12 y3

8 8
>
> x1 + x2 6 14 >
> y1 2 y2 + 2 y3 > 1
>
> >
>
< <
s.c.
> 2 x1 + 3 x2 6 12 s.c.
> y1 + 3 y2 y3 > 3
>
> >
>
>
: >
: y > 0; y > 0; y > 0
x1 ; x2 > 0 1 2 3

Dr. AKPATA Edouard 46

CHAPITRE 3. DUALITE EN PROGRAMMATION LINEAIRE

2.

Primal Dual

min F (x1 ; x82 ) = 60 x1 + 90 x2 M ax W (y1 ; y2 ; y3 ) = 25 y1 + 60 y2 + 15 y3

>
> 8
>
> 20 x1 + 5 x2 > 25
>
> >
> 20 y1 + 30 y2 + y3 6 60
>
> >
>
< 30 x1 + 20 x2 > 60 <
s.c.
>
s.c.
> 5 y1 + 20 y2 + 10 y3 6 90
>
> 5 x1 + 10 x2 > 15 >
>
>
> >
: y > 0; y > 0; y > 0
>
> 1 2 3
>
: x1 > 0; x2 > 0

3.3.3 Théorème des écarts complémentaires

Ce théorème permet de retrouver une solution d’un problème à partir de la solution de

l’autre.

Notons x la solution optimale du primal et y la solution optimale du dual.

1: Si xi > 0, alors la ieme contrainte du dual est saturee:

2: Si la ieme contrainte du primal n’est pas saturee, alors yi = 0:

3: Si yi > 0, alors la ieme contrainte du primal est saturee:

4: Si la ieme contrainte du dual n’est pas saturee, alors xi = 0:

Exemple

M ax F (x1 ; x2 ) = 15 x1 +25 x2 M in W (x1 ; x2 ) = 96 y1 +40 y2 +238 y3

8
>
> 8
>
> x1 + 3 x2 6 96
>
> >
> y1 + y2 + 7 y3 > 15
>
> >
>
< x1 + x2 6 40 <
s.c.
>
s.c.
> 3 y1 + y2 + 4 y3 > 25
>
> 7 x1 + 4 x2 6 238 >
>
>
> >
: y > 0; y > 0; y > 0
>
> 1 2 3
>
: x1 > 0; x2 > 0
Primal Dual

Solution optimale du primal : x = (12; 28) =) x1 = 12; x2 = 28

47
Université Félix Houphouet-Boigny U.F.R - SSMT

En remplaçant la solution dans le primal ; on constate que :

7:12 + 28:4 6 238 =) la 3e contrainte n’est pas saturée =) y3 = 0;

x1 0 =) y1 + y2 + 7 y3 = 15;

x2 0 =) 3 y1 + y2 + 4 y3 = 258 8
8 >
> y1 + y2 = 15 >
> y1 = 5
> >
> >
>
< y1 + y2 + 7 y3 = 15 < <
Donc on a : =) 3 y1 + y2 = 25 =) y2 = 10
>
: 3 y1 + y2 + 4 y3 = 25 >
> >
>
>
> >
>
: y3 = 0 : y =0
3

Exercise 4.

On considère le problème linéaire primal suivant :

M in F (x; x2 ; x3 ) = 2 x1 + 5 x2 + 3 x3
8
>
> x1 > 10
>
>
>
>
>
>
>
>
> x2 > 15
<
s.c.
> x1 + 2 x2 + x3 > 60
>
>
>
>
>
>
> 2 x1 + x2 + 2 x3 > 95
>
>
>
: x ;x ;x > 0
1 2 3

1. Donner le dual du programme primal.

2. Résoudre le problème dual par le simplexe.

3. Déduire la solution optimale du programme primal.

Dr. AKPATA Edouard 48

A RETENIR SUR LA CONSRUCTION DU PRIMAL A DUAL

OPTIMALITE POUR LE PRIMAL-DUAL

Max F MinZ
Variables xj 0 Contrainte j est une inégalité " "
Variables xj 0 Contrainte j est une inégalité " "
Variables xj sans signe Contrainte j est une égalité " = "
Contrainte i est une inégalité " " Variable yi 0
Contrainte i est une inégalité " " Variable yi 0
Contrainte i est une égalité " = " Variable yi sans signe

Le tableau ci-dessus peut être expliqué par les deux tableaux suivants:

PRIMAL DUAL
Max F ! MinZ
Variables xj 0 ! Contrainte j est une inégalité " "
Variables xj 0 ! Contrainte j est une inégalité " "
Variables xj sans signe ! Contrainte j est une égalité " = "
Contrainte i est une inégalité " " ! Variable yi 0
Contrainte i est une inégalité " " ! Variable yi 0
Contrainte i est une égalité " = " ! Variable yi sans signe

PRIMAL DUAL
MinZ ! Max F
Variable xi 0 ! Contrainte i est une inégalité " "
Variable xi 0 ! Contrainte i est une inégalité " "
Variable xi sans signe ! Contrainte i est une égalité " = "
Contrainte j est une inégalité " " ! Variables yj 0
Contrainte j est une inégalité " " ! Variables yj 0
Contrainte j est une égalité " = " ! Variables yj sans signe

THEROEME DES ECARTS COMPLEMENTAIRES

PRIMAL DUAL
eme
xi > 0 =) La i contrainte est saturée
A une contrainte i non saturée =) Variables yi = 0
A une contrainte i saturée =) Variables yi 6= 0