Recherche oprationnelle et applications

Bernard Fortz
2012-2013

Table des matires

I

Introduction la recherche oprationnelle

Quelques exemples de modles mathmatiques

Tour dhorizon des techniques de recherche oprationnelle

II
3

Applications de la programmation linaire

.
.
.
.
.
.
.
.

6
6
6
8
10
10
12
16
17

Dualit
4.1 Le problme dual . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2 Relations primal/dual . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.3 Interprtation conomique de la dualit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

19
19
20
21

Solveurs et langages de modlisation

23

III

Dfinition, exemples et mthode de rsolution

3.1 Notions de bases . . . . . . . . . . . . . . . . . . . . . . .
3.2 Exemples de modles linaires . . . . . . . . . . . . . . . .
3.3 Forme standard et forme canonique dun programme linaire
3.4 Rsolution de programmes linaires . . . . . . . . . . . . .
3.4.1 Rsolution graphique . . . . . . . . . . . . . . . . .
3.4.2 La mthode du simplexe . . . . . . . . . . . . . . .
3.4.3 La mthode des deux phases . . . . . . . . . . . . .
3.4.4 Cas particuliers . . . . . . . . . . . . . . . . . . . .

6
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

Programmation en nombres entiers et optimisation combinatoire

27

Dfinitions et exemples

27

Complexit des problmes et efficacit des algorithmes

30

Problmes polynomiaux
8.1 Le problme daffectation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8.2 Modle de transport . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

31
31
32

Mthodes de Branch-and-Bound
9.1 Branch-and-Bound pour les problmes en nombres entiers . . . . . . . . . . . . . . . . . . . . .
9.2 Branch-and-bound pour le voyageur de commerce . . . . . . . . . . . . . . . . . . . . . . . . . .
9.3 Branch-and-bound pour les contraintes disjonctives . . . . . . . . . . . . . . . . . . . . . . . . .

39
39
41
42

10 Mthodes heuristiques
10.1 Introduction . . . . . . . . .
10.2 Heuristiques de construction
10.3 Recherche locale . . . . . .
10.4 Mta-heuristiques . . . . . .
10.5 Algorithmes gntiques . . .

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

47
47
47
49
50
52

Rfrences
Hamdy A. Taha, Operations Research, an introduction, Prentice-Hall
Marc Pirlot, Mtaheuristiques pour loptimisation combinatoire : un aperu gnral, Chapitre 1, dans Optimisation approche en recherche oprationnelle, sous la direction de Jacques Teghem et Marc Pirlot, Hermes
Science.

Premire partie

Introduction la recherche oprationnelle

1

Quelques exemples de modles mathmatiques

Un premier problme
Exemple 1 (Achat de billets davion).
Un homme daffaires doit effectuer 5 voyages entre Fayetteville (FYV) Denver (DEN), en partant le lundi de
FYV et revenant le mercredi de DEN FYV.
Billet aller-retour : $400.
Rduction de 20 % si un weekend est inclus.
Aller simple : 75 % du prix aller-retour.
Question
Comment acheter les billets pour les 5 semaines ( prix minimum) ?
Aide la dcision
Problme daide la dcision
1. Quelles sont les alternatives possibles ?
2. Quelles sont les restrictions cette dcision ?
3. Quel est lobjectif utilis pour valuer les alternatives ?
Restrictions
FYV-DEN le lundi et DEN-FYV le mercredi de la mme semaine.
Evaluation des alternatives
Alternatives
Acheter 5 FYV-DEN-FYV normaux. 5 x $400 = $2000
Acheter un FYV-DEN, 4 DEN-FYV-DEN comprenant un weekend et un DEN-FYV. 0.75 x $400 + 4 x 0.8 x
$400 + 0.75 x $400 = $1880
Acheter un FYV-DEN-FYV pour le lundi de la premire semaine et le mercredi de la dernire semaine, et 4
DEN-FYV-DEN comprenant un weekend pour les autres voyages. 5 x 0.8 x 400 =1600
La troisime alternative est la meilleure.
Modle de recherche oprationnelle
Ingrdients principaux
Alternatives (variables, inconnues du problme).
Restrictions (contraintes).
Fonction objectif optimiser (minimiser ou maximiser).
Dfinition 1 (Solution admissible). Une solution admissible est un ensemble de valeurs donnes aux variables qui
satisfait toutes les contraintes.
Dfinition 2 (Solution optimale). Une solution optimale est une solution admissible qui optimise la fonction
objectif.
Dfinition 3 (Modle de recherche oprationnelle). Maximiser ou minimiser (fonction objectif) Sujet { contraintes
}
Variables : continues (relles), entires, boolennes (0/1), . . .
Objectif : linaire / non-linaire, concave / convexe, . . .

Contraintes : linaire / non-linaire, concave / convexe, galits / ingalits, . . .

Paramtres : connus avec certitude (modles dterministes) / incertains (modles stochastiques)
Exemple 2 (Maximisation de la surface dun rectangle). Supposons que lon veut plier un fil de fer de longueur L
en rectangle de manire maximiser la surface du rectangle.
l

Formulation
max
s.t.

A = lw
l + w = L2

Solution


2
A = L2 w w = Lw
2 w
L
dA
dw = 2 2w = 0
Solution optimale : w = l = L4
Mthodes de rsolution
Dans lexemple, solution analytique au problme.
La plupart des problmes pratiques sont trop grands ou trop complexes pour tre rsolus analytiquement.
Mthodes itratives
Dplacement de solution en solution pour atteindre loptimum (mthodes exactes) ou une "bonne" solution
(heuristiques).
Importance des algorithmes et des solutions informatiques.

Tour dhorizon des techniques de recherche oprationnelle

Recherche oprationnelle
La recherche oprationnelle est une technique daide la dcision.
Etapes pratiques
1. Dfinition du problme
2. Construction dun modle
3. Solution du modle
4. Validation du modle
5. Implmentation de la solution
Mthodologie
Les tapes les plus importantes sont la dfinition du problme (suppose un dialogue avec le dcideur) et la
construction du modle (prendre conscience des hypothses simplificatrices et de leur impact).
La phase de validation doit permettre de remettre en cause la validit du modle.
Une approche globale ncessite donc un aller-retour constant entre le modle et les attentes du dcideur.
Techniques principales
Programmation linaire
Programmation en nombres entiers
Optimisation dans les rseaux
4

Programmation non linaire

"Optimisation" multi-critres
Programmation dynamique
Modles stochastiques
Simulation

Deuxime partie

Applications de la programmation linaire

3
3.1

Dfinition, exemples et mthode de rsolution

Notions de bases

Programmation linaire
Dfinition 4 (Programme linaire). Modle mathmatique dans lequel la fonction objectif et les contraintes sont
linaires en les variables.
Applications
Optimisation de lusage de ressources limites dans les domaines militaire, industriel, agricole, conomique, ...
Existence dalgorithmes trs efficaces pour rsoudre des problmes de trs grande taille (simplexe, points intrieurs)

3.2

Exemples de modles linaires

Exemple 3 (Production de peinture). Une socit produit de la peinture dintrieur et dextrieur partir de deux
produits de base M1 et M2.
Donnes

M1
M2
Profit par tonne

Quantit utilise
par tonne
Extrieure
Intrieure
6
4
1
2
5
4

Quantit disponible
par jour
24
6

Contraintes supplmentaires
Demande maximum en peinture dintrieur : 2 tonnes / jour.
La production en peinture dintrieur ne dpasser que dune tonne celle dextrieur.
Formulation (Production de peinture)
Alternatives (variables, inconnues du problme)
x1

= tonnes de peinture dextrieur

produites par jour

x2

= tonnes de peinture
dintrieur produites par jour

Fonction objectif optimiser

max z = 5x1 + 4x2
Restrictions (contraintes)

6x1 + 4x2

24

x1 + 2x2

x2

x2 x1

x1 , x2

Solutions et mthodes de rsolution

Solution admissible : satisfait toutes les contraintes.
x1 = 3, x2 = 1 ( z = 19)
Nous voulons trouver la solution (admissible) optimale.
Infinit de solutions admissibles !
Mthodes pour trouver loptimum
Mthode graphique
Simplexe
( Ellipsoide, points intrieurs )
Exemple 4 (Diet problem). On dsire dterminer la composition, cot minimal, dun aliment pour btail qui
est obtenu en mlangeant au plus trois produits bruts : orge et arachide.
La quantit ncessaire par portion est de 400g.
Laliment ainsi fabriqu devra comporter au moins 30% de protines et au plus 5% de fibres.
Donnes
Quantit par gramme daliment
Aliment
Protines Fibres
Orge
0.09
0.02
Arachide
0.60
0.06

Cot
(EUR / kg)
1.5
4.5

Formulation (Diet problem)

Variables
x1

= grammes dorge par portion

x2

= grammes darachide par portion

Objectif
min z = 0.0015x1 + 0.0045x2
Contraintes
Quantit totale : x1 + x2 400
Protines : 0.09x1 + 0.6x2 0.3(x1 + x2 )
Fibres : 0.02x1 + 0.06x2 0.05(x1 + x2 )
Non-ngativit : x1 , x2 0

3.3

Forme standard et forme canonique dun programme linaire

Forme standard
Dfinition 5 (Forme standard). Un programme linaire est sous forme standard lorsque toutes ses contraintes sont
des galits et toutes ses variables sont non-ngatives.
Reprsentation matricielle
max

cT x

s.c.

Ax = b
x0

n variables, m contraintes, m < n, c, x Rn ,

b Rm ,

A Rmn .

Forme canonique
Dfinition 6 (Forme canonique). Un programme linaire est sous forme canonique lorsque toutes ses contraintes
sont des ingalits et toutes ses variables sont non-ngatives.
Reprsentation matricielle
max
s.t.

cT x
Ax b
x0

n variables, m contraintes, c, x Rn ,

b Rm ,

A Rmn .

Thorme 1 (Equivalence des formes standard et canonique). Tout programme linaire peut scrire sous forme
standard et sous forme canonique.
Dmonstration.
Une containte dingalit aT x b peut tre transforme en galit par lintroduction dune variable dcart :
aT x + s = b,
s 0.
Une contrainte dgalit aT x = b peut tre remplace par deux ingalits :
aT x b
aT x b
aT x b aT x b.
min cT x = max cT x.
Variable x non restreinte : substitution par deux variables (partie positive et ngative)
x = x+ x
x+ , x 0.
Il existe toujours une solution optimale telle que x+ = 0 ou x = 0.

Forme standard du problme de production de peinture

max z = 5x1 + 4x2
s.c.6x1 + 4x2

24

x1 + 2x2

x2

x2 x1

x1 , x2

Forme standard
max z =
s.c.

5x1 +4x2
6x1 +4x2 +s1
= 24
x1 +2x2
+s2
= 6
x2
+s3
= 2
x1 +x2
+s4 = 1
x1 , x2 , s1 , s2 , s3 , s4 0

Forme matricielle
max
s.t.

cT x
Ax = b
x0

c=

5
4
0
0
0
0

,x =

x1
x2
s1
s2
s3
s4

,A =

6
1
0
1

4 1 0 0 0

2 0 1 0 0
,b =

1 0 0 1 0
1 0 0 0 1

24
6

2
1

Variables pouvant prendre des valeurs ngatives

Exemple 5 (Vente de hamburgers).
Un fast-food vend des hamburgers et des cheeseburgers. Un hamburger utilise 125 g. de viande alors quun
cheeseburger nen utilise que 100 g.
Le fast-food dmarre chaque journe avec 10 kg de viande mais peut commander de la viande supplmentaire
avec un cot additionnel de 2 EUR par kg pour la livraison.
Le profit est de 0.02 EUR pour un hamburger et 0.015 EUR pour un cheeseburger.
La demande ne dpasse pas 900 sandwiches / jour, et les surplus de viande sont donns au Restos du Coeur.
Combien le fast-food doit-il produire de sandwiches de chaque type par jour ?
Variables
x1 = nombre de hamburgers / jour x2 = nombre de cheeseburgers / jour
Contraintes
Commande de viande supplmentaire :
125x1 + 100x2 + x3 = 10000,

x3 non restreint

Le cot pour la viande supplmentaire apparat seulement si x3 < 0.

9

 Substitution de x3 par 2 variables non-ngatives :

x3 = x+
3 x3 , x3 , x3 0

125x1 + 100x2 + x+
3 x3 = 10000

Borne suprieure sur les ventes : x1 + x2 900.

Modle complet
max z =
s.c.

0.02x1 + 0.015x2 0.002x

3

125x1 + 100x2 + x+
3 x3

x1 + x2

x1 , x2 , x+
3 , x3

= 10000
900
0

Remarque : Il existe une solution optimale telle que x+

3 = 0 ou x3 = 0.

3.4

Rsolution de programmes linaires

3.4.1

Rsolution graphique

Reprsentation graphique
(5)

(1)

(4)

(2)

(3)
(6)

Production de peinture
max z = 5x1 + 4x2
sous les contraintes :
6x1 + 4x2

24

(1)

x1 + 2x2

(2)

x2

(3)

x2 x1

(4)

x1

(5)

x2

(6)

10

Gomtrie des solutions

D
E

z=10

Ensemble des solutions admissibles

Polydre (ABCDEF)
Courbes de niveaux de lobjectif
Ensemble de solutions ayant un profit (valeur de lobjectif) donn : intersection entre une droite et le polydre.
Amlioration de la solution
Recherche dune direction dans laquelle le profit z augmente.
Rsolution graphique (Production de peinture)

z=21
C
B

D
E

Recherche de la solution optimale

La droite mobile doit garder une intersection avec lensemble des solutions admissibles.
Solution optimale : x1 = 3, x2 = 1.5 (E)
La solution optimale est un sommet du polydre.
Cette observation est la base de lalgorithme du simplexe.

11

Rsolution graphique (Diet problem)

Diet problem
min z = 0.0015x1 + 0.0045x2
sous les contraintes
x1 + x2

400

0.21x1 0.30x2

0.03x1 0.01x2

x1

x2

Solution optimale
x1 =

3.4.2

4000
' 235.3
17

x2 =

2800
' 164.7
17

z=

186
' 1.094
170

La mthode du simplexe

Ides de base
Solution optimale : sommet (point extrme).
Ide fondamentale du simplexe : dplacement de sommet en sommet adjacent de manire amliorer la fonction
objectif.
Transformation des ingalits en galits : forme standard du programme linaire - systme de m quations
n inconnues (m < n).
Identification algbrique des sommets : correspondance avec les bases dun systme dquations.
Solutions de base
Systme de m quations linaires n inconnues (m < n) : infinit de solutions.
Si on fixe zro n m variables : systme de m quations m inconnues possdant une solution unique (si la
matrice est inversible). Cest une solution de base.
Dfinition 7 (Solution de base). Une solution de base dun programme linaire est la solution unique du systme
de m quations m inconnues obtenu en fixant zro n m variables (pourvu que la matrice du systme soit
inversible).
Les variables fixes zro sont appeles variables hors base et les autres variables en base.

12

Exemple 6 (Production de peinture). Prenons B = {s1 , s2 , s3 , s4 }.

z
s1
s2
s3
s4

= 0 +5x1
= 24 6x1
= 6 x1
= 2
= 1 +x1

+4x2
4x2
2x2
x2
x2

Si x1 = x2 = 0, alors s1 = 24, s2 = 6, s3 = 2, s4 = 1. Toutes ces valeurs sont non-ngatives et la solution est

ralisable.
Dfinition 8 (Solution de base ralisable). Une solution de base telle que toutes les variables prennent des valeurs
non-ngatives est appele solution de base ralisable.
Gomtrie des solutions de base

D
E

B
A

Prenons B = {s1 , s2 , s3 , s4 } x1 = x2 = 0, s1 = 24, s2 = 6, s3 = 2, s4 = 1.

Cette solution de base ralisable correspond au sommet (0, 0).
Base
Solution Objectif
Sommet
{s1 , s2 , s3 , s4 }
(0, 0)
0
A
{x1 , s2 , s3 , s4 }
(4, 0)
20
F
{s1 , x1 , s3 , s4 }
(6, 0)

Non ralisable
{x1 , x2 , s3 , s4 } (3, 1.5)
21
E
Thorme 2. Toute solution de base ralisable correspond un sommet du polydre.
Dtermination de la solution de base optimale
n!
Nombre maximum de solutions de base : m!(nm)!
Algorithme "bte et mchant" : numration de toutes les bases.
Mthode du simplexe : partir dune solution de base admissible et passer une solution de base voisine qui
amliore la valeur de lobjectif.
Solution voisine : changement dune variable en base.
3 etapes :
1. Dtermination de la variable entrante.
2. Dtermination de la variable sortante.
3. Pivotage.
Lalgorithme du simplexe
Variable entrante
z
s1
s2
s3
s4

= 0 +5x1
= 24 6x1
= 6 x1
= 2
= 1 +x1

+4x2
4x2
2x2
x2
x2

Si x1 (ou x2 ) augmente (entre en base), la valeur de la fonction objectif z augmente.

Quelle est la valeur maximale de x1 ?
13

 Contraintes : les autres variables doivent rester positives.

Variable sortante
s1
s2
s3
s4

=
=
=
=

24 6x1
6 x1
2
1 +x1

0
0
0
0

Pivotage
Si x1 = 4, alors s1 = 0.
x1 entre en base, s1 sort de la base.
Substitution :

x1 4
x1 6
20
x1 1

toujours!
toujours!

x1 4

2
1
x1 = 4 s1 x2
6
3

Nouveau systme :
z
x1
s2
s3
s4

=
=
=
=
=

56 s1
16 s1
+ 16 s1

20
4
2
2
5

+ 32 x2
32 x2
34 x2
x2
35 x2

16 s1

Equations du simplexe
B = indices des variables en base, N = indices des variables hors base.
Notation :
X
ck xk
z=z+
kN

xl = bl

alk xk

lB

kN

ck : profit marginal ou cot rduit.

Rgles de pivotage
Variable entrante
Choisir la variable k hors base avec le profit marginal maximum (max z) ou le cot rduit minimum (min z).
max z

k = arg max ci

min z

k = arg min ci

iN

iN

Si ck 0 (max) ou ck 0 (min) pour tout k N , solution optimale, STOP.

z= 0
s1 = 24
s2 = 6
s3 = 2
s4 = 1

+5x1 +4x2
6x1 4x2
x1 2x2
x2
+x1 x2

Variable sortante
Choisir la variable l en base telle que
l = arg

min

jB:ajk >0

Si alk 0 pour tout l B, problme non born, STOP.

14

bj
ajk

z= 0
s1 = 24
s2 = 6
s3 = 2
s4 = 1

+5x1 +4x2
6x1 4x2
x1 2x2
x2
+x1 x2

Pivotage

lj
i=l
0
a
lk
aij =
a
a

aij ik lj i 6= l
alk

l
i=l
0
alk
bi =
a b

bi ik l i =
6 l
alk

z = 0 +5x1 +4x2
s1 = 24 6x1 4x2
s2 = 6

x1 2x2

s3 = 2

x2

s4 = 1

+x1 x2

z = 20 56 s1 + 32 x2
x1 = 4

16 s1

32 x2

4
s2 = 2 + 16 s1 x2
3
s3 = 2
x2
s4 = 5

16 s1

15

35 x2

z = 21 34 s1 12 s2
x1 = 3 41 s1 + 12 s2
x2 =
s3 =
s4 =

3
2
1
2
5
2

+ 81 s1 34 s2
81 s1 + 34 s2
83 s1 + 54 s2

Prsentation en tableau
Prsentation compacte pour effectuer les calculs sans rpter les systmes dquations.
Itration 1
Var. en base
z
s1
s2
s3
s4

z
1
0
0
0
0

x1
5
6
1
0
1

x2
4
4
2
1
1

Var. en base
z
x1
s2
s3
s4

z
1
0
0
0
0

x1
0
1
0
0
0

x2

Var. en base
z
x1
x2
s3
s4

z
1
0
0
0
0

x1
0
1
0
0
0

s1
0
1
0
0
0

s2
0
0
1
0
0

s3
0
0
0
1
0

s4
0
0
0
0
1

Solution
0
24
6
2
1

s1
56

s2
0
0
1
0
0

s3
0
0
0
1
0

s4
0
0
0
0
1

Solution
20
4
2
2
5

s2
12
12

s3
0
0
0
1
0

s4
0
0
0
0
1

Solution
21
3

Itration 2

2
3
2
3
4
3

1
6
61

5
3

1
6

x2
0
0
1
0
0

s1
34

Itration 3

3.4.3

1
4
18
1
8
3
8

3
4
34
54

3
2
1
2
5
2

La mthode des deux phases

Solution initiale artificielle

Une solution de base admissible nest pas toujours connue a priori.
Certains problmes nadmettent pas de solution admissible, donc il est impossible de trouver une base de dpart.
La mthode des deux phases va permettre de dterminer une base admissible ou prouver que le problme est
impossible.
Exemple 7 (Mthode des 2 phases).
min z = 4x1
s.c.
3x1
4x1
x1
x1 ,
Introduction des variables dcart
min z = 4x1
s.c.
3x1
4x1
x1
x1 ,

+x2
+x2
+3x2
+2x2
x2 ,

16

+x2
+x2
+3x2
+2x2
x2

x3
x3 ,

+x4
x4

3
6
4

=
=
=
0

3
6
4

 Pas de base admissible "triviale".

On voudrait voir apparatre une matrice identit.
Introduction de variables artificielles.
Introduction des variables artificielles
min z = 4x1
min r =
min r = 7x1
s.c.
3x1
4x1
x1
x1 ,

+x2
R1
4x2
+x2
+3x2
+2x2
x2 ,

+R2

+x3
+R1
x3

+R2

x3 ,

R1 ,

R2 ,

+x4
x4

=
=
=
0

+9
3
6
4

R1 , R2 et x4 peuvent tre utilises comme base de dpart admissible.

Base pour le systme de dpart si R1 = R2 = 0 (hors base).
Rcrire lobjectif en fonction des variables hors base !
3.4.4

Cas particuliers

Solutions optimales multiples

Si la fonction objectif est parallle une contrainte active pour la solution optimale, la mme valeur de lobjectif
peut tre prise par plusieurs solutions admissibles.
Il y a une infinit de solutions optimales dans ce cas (toutes les combinaisons convexes de sommets optimaux).
Cela se traduit par un profit marginal nul pour une ou plusieurs variables hors base.
Exemple 8 (Solutions optimales multiples).
max
s.c.

z=

2x1
x1
x1
x1 ,

+4x2
+2x2
+x2
x2

5
4

Var. en base

x1

x2

s1

s2

Solution

s1
s2

0
0

1
1

2
1

1
0

0
1

5
4

10

x2
s2

0
0

1
2
1
2

1
0

1
2
12

0
1

5
2
3
2

10

x2
x1

0
0

0
1

1
0

1
1

1
2

1
3

Solution optimale :
x1 =
x2 =

0 + 3(1 )

= 3 3
3
5
2 + 1(1 ) = 1 + 2

(0 1)

Problmes non borns

Certains problmes sont non borns dans une direction donne.
Si cette direction est une direction damlioration de la fonction objectif, celle-ci peut prendre une valeur arbitrairement grande !

17

Exemple 9 (Problmes non borns).

max z =
s.c.

2x1
x1
2x1
x1 ,

+x2
x2

x2

1
4

Var. en base

x1

x2

s1

s2

Solution

s1
s2

0
0

1
2

1
0

1
0

0
1

1
4

Tous les coefficients (sauf le profit maginal) dans la colonne de x2 sont ngatifs ou nuls.
Cela signifie que toutes les contraintes de non-ngativit sont satisfaites quelle que soit la valeur de x2 .
Lobjectif peut donc augmenter indfiniment.
Problmes impossibles
Le systme de contraintes peut navoir aucune solution.
Gnralement, provient dune mauvaise formulation du problme.
Exemple 10 (Problmes impossibles).
max
s.c.

z=

3x1
2x1
3x1
x1 ,

+2x2
+x2
+4x2
x2

18

2
12

4
4.1

Dualit
Le problme dual

Problme primal et problme dual

Problme primal
max

cT x

s.c.

Ax = b
x0

n variables, m contraintes, m < n, c, x Rn ,

b Rm ,

A Rmn .

Problme dual
min

bT y

s.c.

AT y c
(y non restreint)

m variables, n contraintes, m < n, c Rn ,

b, y Rm ,

A Rmn .

Exemple 11 (Problme primal et dual - forme standard).

Problme primal :
max
s.c.

z=

x1
2x1
3x1
x1 ,

+x2
+x2
x2
x2

= 5 (y1 )
= 6 (y2 )
0

min w = 5y1
s.c
2y1
y1

+6y2
+3y2
y2

1
1

Problme dual :
(x1 )
(x2 )

Proprits et rgles de construction du dual

Thorme 3. Le problme dual du problme dual est le problme primal.
Rgles de construction
Problme max
Contrainte

=
Variable
0
non restreinte

Problme min
Variable
0
non restreinte
Contrainte

Exemple 12 (Problme primal et dual - forme gnrale).

Problme primal :
max
s.c.

z=

5x1
x1
2x1
x1 ,

+12x2
+2x2
x2
x2 ,

19

+4x3
+x3
+3x3
x3

10
=8
0

(y1 )
(y2 )

Problme dual :
min w =
s.c

4.2

10y1
y1
2y1
y1
y1

+8y2
+2y2
y2
+3y2

5
12
4
0

(x1 )
(x2 )
(x3 )

Relations primal/dual

Thorme 4 (Dualit faible). Considrons la paire primale-duale :

max

cT x

s.c.

Ax = b
x0

bT y

min

s.c. AT y c

Si x est une solution admissible du primal et y une solution admissible du dual, alors
cT x bT y
Sil y a galit, alors x est une solution optimale du primal et y une solution optimale du dual.
Thorme 5 (Dualit forte). Considrons la paire primale-duale :
max

cT x

s.c.

Ax = b
x0

min
bT y
s.c. AT y c

Si le primal et le dual admettent tous les deux une solution admissible, ils ont tous deux une solution optimale
finie et la mme valeur objectif optimale.
Si le primal (dual) est non born, le dual (primal) nadmet pas de solution admissible.
Thorme 6 (Complmentarit). Considrons la paire primale-duale :
max

cT x

s.c.

Ax = b
x0

min

bT y

s.c. AT y c

20

Si x est une solution optimale du primal et y une solution optimale du dual, alors
xi (aTi y ci ) = 0.
o ai est la i-me colonne de A.
En dautres termes :
xi > 0
aTi y > ci

aTi y = ci ,
xi = 0.

Exemple 13 (Rsolution du dual par les rgles de complmentarit).

Primal (P ) :
max z = 5x1 +12x2 +4x3
s.c.
x1
+2x2
+x3 10
2x1
x2
+3x3 = 8
x1 ,
x2 ,
x3
0

(y1 )
(y2 )

Dual (D) :
min w =
s.c

10y1
y1
2y1
y1
y1

+8y2
+2y2
y2
+3y2

5
12
4
0

(x1 )
(x2 )
(x3 )

Solution optimale de (P ) :


26 12
, ,0
(x1 , x2 , x3 ) =
5 5
274
z=
5

x1 > 0

y1 + 2y2 = 5

x2 > 0

2y1 y2 = 12

Solution optimale de (D) :



29 2
,
(y1 , y2 ) =
5
5
274
w=
5

4.3

Interprtation conomique de la dualit

La forme canonique dun programme linaire peut tre interprte comme un problme dallocation de ressources.
Paire primale-duale :
cT x

max

s.c. Ax b
x0

bT y

min
s.c.

A yc
y0

21

 Donnes :
cj : profit par unit dactivit j.
bi : disponibilit de la ressource i.
aij : consommation de la ressource i par unit dactivit j.
Variables :
xj : niveau de lactivit j.
yi : valeur dune unit de la ressource i.
Interprtation de la dualit faible
zw:

profit valeur des ressources

Interprtation de la dualit forte

Le profit maximal est atteint si les ressources ont t exploites compltement, i.e. jusqu puisement de leur
valeur.
Exemple 14 (Dualit dans le problme de production de peinture).
max z =
s.c

5x1
6x1
x1
x1
x1 ,

min w =

24y1
6y1
4y1
y1 ,

+6y2
+y2
+2y2
y2 ,

+4x2
+4x2
+2x2
x2
+x2
x2
+2y3
+y3
y3 ,

24
6
2
1
0
+y4
y4
+y4
y4

5
4
0

x1 = 3, x2 = 1.5, z = 21
y1 = 0.75, y2 = 0.5, y3 = y4 = 0, w = 21
Le profit augmente de 0.75 par augmentation dune tonne de M1 et de 0.5 par tonne de M2. (Localement. Dans
quelles limites ? Voir analyse de sensibilit)
Les "ressources" 3 et 4 sont abondantes, augmenter ces ressources napporte aucun profit supplmentaire.

22

Solveurs et langages de modlisation

Exemple 15 (Production de jouets).

Une socit de jouets produit des trains, des camions et des voitures, en utilisant 3 machines.
Les disponibilits quotidiennes des 3 machines sont 430, 460 et 420 minutes, et les profits par train, camion et
voiture sont respectivement EUR 3, EUR 2 et EUR 5.
Les temps ncessaires sur chaque machine sont :
Machine Train Camion Voiture
1
1
2
1
2
3
0
2
1
4
0
3
Primal
max z = 3x1
s.c.

+2x2
x1
3x1
x1
x1 ,

+5x3
+2x2

+x3
+2x3

+4x2
x2 ,

x3

430
460
420
0

x1 = 0
x2 = 100
x3 = 230
z = 1350
Dual
min w = 430y1
s.c.
y1
2y1
y1
y1 ,

+460y2
+3y2

+420y3
+y3
+4y3

+2y2
y2 ,

y3

3
2
5
0

y1 = 1
y2 = 2
y3 = 0

Var. en base
z
x2
x3
s3

z
1
0
0
0

x1
4
14
3
2

x2
0
1
0
0

x3
0
0
1
0

s1
1
1
2

s2
2
14

0
2

1
2

s3
0
0
0
1

Solution
1350
100
230
20

Base : B = {x2 , x3 , s3 }.
Solveurs
Logiciels pour rsoudre des programmes linaires :
Indpendants :
Commerciaux : CPLEX (www.ilog.com), XPRESS-MP (www.dash.co.uk), . . .
Gratuits : PCx, lpsolve, glpk, . . .
Tableurs : La plupart des tableurs intgrent un outil de rsolution de programmes linaires (Excel, Gnumeric,
. . .)
Langages de modlisation (ampl, GNU MathProg, mpl, OPL studio, mosel, . . .) : langages de haut niveau
permettant la sparation modle/donnes, se chargeant de linterface avec un solveur.
23

NAME
ROWS
L R0001
L R0002
L R0003
N R0004
COLUMNS
C0001
C0001
C0001
C0001
C0002
C0002
C0002
C0003
C0003
C0003
RHS
B
B
B
ENDATA

toys

R0001
R0002
R0003
R0004
R0001
R0003
R0004
R0001
R0002
R0004

1
3
1
3
2
4
2
1
2
5

R0001
R0002
R0003

430
460
420

F IGURE 1 Exemple de production de jouets au format MPS

Solveurs indpendants
Avantages
Puissance, efficacit
Intgrables dans des applications via des librairies
Dsavantages
Formats de fichiers (MPS)
Pas de sparation modle / donnes
R-utilisation difficile des modles
Solveurs intgrs aux tableurs
Avantages
Disponibles sur (quasi) tous les ordinateurs
Interface facile dutilisation
Prsentation des donnes / rsultats
Dsavantages
Difficult dimplmenter de grands modles
Sparation modle / donnes difficile
Solveurs moins efficaces (en gnral)
Langages de modlisation
Avantages
Sparation modle / donnes
R-utilisabilit des modles
Indpendance modle / solveur

24

#
# Data definition
#
set Toys;
param nMachines;
set Machines := 1..nMachines;
param profit {Toys};
param time {Machines,Toys};
param avail {Machines};
#
# Variables
#
var prod {Toys} >= 0;
#
# Objective
#
maximize total_profit:
sum{t in Toys} profit[t]*prod[t];
#
# Constraints
#
subject to machine_usage {m in Machines}:
sum{t in Toys} time[m,t] * prod[t] <= avail[m];

F IGURE 2 Exemple de production de jouets au format AMPL (modle)

Dsavantages
Apprentissage du langage
Prix des versions commerciales
Limitation en taille des versions dessai gratuites
Moindre efficacit (actuellement) des solveurs gratuits

25

#
# Data
#
data;
set Toys := Trains, Trucks, Cars ;
param nMachines := 3;
param profit :=
Trains 3
Trucks 2
Cars 5 ;
param
1 1 2
2 3 0
3 1 4

time :
1
2
0 ;

Trains Trucks Cars :=

param avail :=
1 430
2 460
3 420 ;
end;
F IGURE 3 Exemple de production de jouets au format AMPL (donnes)

26

Troisime partie

Programmation en nombres entiers et optimisation

combinatoire
6

Dfinitions et exemples

Programmation en nombres entiers

Programmes linaires dans lesquels certaines (ou toutes les) variables sont restreintes des valeurs entires.
Si seulement une partie des variables doivent tre entires, on parle de programme mixte (MILP).
Optimisation combinatoire : choix dune solution optimale parmi un ensemble fini dalternatives. Peuvent gnralement se formuler comme des programmes en nombres entiers.
Problmes trs difficiles en pratique, mais solveurs de plus en plus performants.
Exemple 16 (Slection de projets). 5 projets doivent tre valus sur 3 ans. Etant donn le cot de chaque projet
pour chaque anne et le profit obtenu par lxcution dun projet, dcider quels projets xcuter sans dpasser le
budget disponible pour chaque anne.
Cot par anne
1
2
3
5
1
8
4
7
10
3
9
2
7
4
1
8
6
10
25 25
25

Projet
1
2
3
4
5
Budget
Variables


xj =

1
0

Profit
20
40
20
15
30

si le projet j est slectionn,

sinon.

Formulation
max z =
s.c.

20x1
5x1
x1
8x1
x1 ,

+40x2
+4x2
+7x2
+10x2
x2 ,

+20x3
+3x3
+9x3
+2x3
x3 ,

+15x4
+7x4
+4x4
+x4
x4 ,

+30x5
+8x5
+6x5
+10x5
x5

25
25
25
{0, 1}

Exemple 17 (Problme avec cots fixes).

3 compagnies de tlphone offrent des tarifs diffrents pour les communications longue distance.
Compagnie Abonnement Prix / minute
1
16
0.25
2
25
0.21
3
18
0.22
Trouver le plan dabonnement optimal pour 200 minutes de communication / mois.
Variables
xi : minutes de communication avec la compagnie i.

1 si un abonnement est pris auprs de la compagnie i,
yi =
0 sinon.
Formulation

27

min z = 0.25x1
s.c.
x1
x1

+0.21x2
+x2

+0.22x3
+x3

x2
x1 ,
y1 ,

x3
x3
y3

x2 ,
y2 ,

+16y1 + 25y2 + 18y3

= 200
200y1
200y2
200y3
0
{0, 1}

Exemple 18 (Voyageur de commerce).

Un reprsentant doit visiter n villes une et une seule fois, et revenir sa ville de dpart, en minimisant le cot
total du trajet.
Le problme revient trouver un tour de cot minimum passant une et une seule fois par chacun des noeuds
dun graphe. Le cot dutilisation de larc (i, j) est cij .
Variables
xij =

si larc (i, j) appartient

au tour optimal,
sinon.

Contraintes
n
X
j=1
n
X

xij = 1

i = 1, . . . , n

xij = 1

j = 1, . . . , n

i=1

Problme : apparition possible de sous-tours

xij |S| 1,

=
6 S 6= {1, . . . , n}.

i,jS

Formulation
min z =

s.c.

n X
n
X

cij xij

i=1 j=1
n
X
j=1
n
X

xij = 1

i = 1, . . . , n

xij = 1

j = 1, . . . , n

i=1

xij |S| 1

=
6 S 6= {1, . . . , n}

i,jS

xij {0, 1}

i = 1, . . . , n, j = 1, . . . , n

28

Exemple 19 (Problme de couverture). Le dpartement de scurit dun campus veut installer des tlphones
durgence. Chaque rue doit tre servie par un tlphone, le but tant de minimiser le nombre de tlphones
installer (installation aux carrefours).
1

Formulation
min z =
s.c.

x1
x1

+x2
+x2
x2

+x3

+x4

+x5

+x6

+x5
x6

x1

+x7
x7

+x8

+x6
+x6

x2
x2

+x4
x4
x3

x2 ,

+x8

+x3
x4

x1 ,

+x7

x3 ,

x4 ,

+x7
+x5
x5
x5 ,

x6 ,

x7 ,

+x8
x8

1
1
1
1
1
1
1
1
1
1
1
{0, 1}

Contraintes disjonctives
Dans un programme linaire, toutes les contraintes doivent tre satisfaites simultanment.
Parfois, il est ncessaire de modliser le fait quune contrainte parmi un ensemble doit tre satisfaite. Si les
contraintes de lensemble sont mutuellement incompatibles, on parle de contraintes disjonctives.
Exemple 20 (Contraintes disjonctives).
Une machine est utilise pour 3 tches diffrentes. Pour chaque tches i, une dure pi et une date limite di sont
donnes, ainsi quune pnalit par jour de retard.
Tche Dure Limite Pnalit
1
5
25
19
2
20
22
12
3
15
35
34
Comment arranger les tches sur la machine pour minimiser la pnalit totale ?
Variables : xi : temps de fin de la tche i (xi pi ).
Deux tches i et j ne peuvent tre xcutes simultanment, donc
xi xj + pi ou xj xi + pj .
Pour introduire ces contraintes disjonctives, nous faisons appel des variables binaires auxiliaires :

1 si i prcde j
yij =
0 si j prcde i
29

xi xj + M yij pi
xj xi + M (1 yij ) pj
Contrainte de date limite : introduction dune variable dcart non restreinte xi + si = di .
Une pnalit apparat uniquement si si < 0.
Remplacement par deux variables non ngatives reprsentant les parties positive et ngative.

xi + s+
i si = di

s+
i , si 0

Objectif : min z = 19s

1 + 12s2 + 34s3

Formulation
min z =
s.c.

19s
1
+M y12
M y12

x1 x2
x1 +x2
x1
x3
x1
+x3
x2 x3
x2 +x3

x1
+s+
1 s1
x2
x3

x1 , x2 , x3 , s+
1 , s1 ,
x1
x2
x3
y12 ,

+12s
2

+34s
3

+M y13

M y13

+M y23
M y23
=

+s+

s
=
2
2

+s+

s
3
3 =

s+
,
s
,
s
,
s

2
2
3
3

y13 ,
y23

5
20 M
5
15 M
20
15 M
25
22
35
0
5
20
15
{0, 1}

Complexit des problmes et efficacit des algorithmes

Problmes faciles et difficiles

La thorie de la complexit sattache classifier les problmes selon leur difficult.
Un problme est facile sil existe un algorithme efficace pour le rsoudre.
Exemples de problmes faciles : programmation linaire, affectation, plus courts chemins, . . .
Un problme est difficile sil appartient la classe des problmes NP-complets, pour lesquels il est peu probable
de trouver un jour un algorithme efficace.
Exemple de problmes difficiles : programmes en nombres entiers, voyageur de commerce, . . .
Algorithmes efficaces et explosion combinatoire
Lefficacit dun algorithme est mesure par lordre de grandeur du nombre doprations lmentaires quil
effectue en fonction de la taille des donnes.
Un algorithme sera efficace si le nombre doprations lmentaires est polynomial (i.e. born suprieurement
par un polynme) en la taille de problme.
n
1
2
3
5
10
20
50
100

ln n + 1 n
1.000
1
1.301
2
1.477
3
1.699
5
2.000
10
2.301
20
2.699
50
3.000
100

n2
1
4
9
25
100
400
2500
10000
30

n3
1
8
27
125
1000
8000
125000
1000000

2n
2
4
8
32
1024
1048576
1.12 1015
1.27 1030

 Autre perspective : supposons que trois ordinateurs M1 , M2 et M3 effectuent respectivement 10000, 20000 et
40000 oprations par seconde. oprations par seconde.
Quelle taille maximum de problme n peut on rsoudre en une minute par des algorithmes effectuant respectivemet n, n2 , n3 et 2n oprations ?
Ordinateur
M1
M2
M3

8
8.1

n
600000
1200000
2400000

n2
775
1095
1549

n3
84
106
134

2n
19
20
21

Problmes polynomiaux
Le problme daffectation

Le problme daffectation
Exemple de problme combinatoire pour lequel il existe un algorithme efficace.
La meilleure personne pour chaque tche.
n personnes doivent effectuer n tches.
Un cot cij est associ laffectation de la personne i la tche j.
Formulation du problme daffectation

min z =

s.c.

n X
n
X

cij xij

i=1 j=1
n
X
j=1
n
X

xij = 1

i = 1, . . . , n

xij = 1

j = 1, . . . , n

i=1

xij {0, 1}

i = 1, . . . , n, j = 1, . . . , n

Proprit : la relaxation linaire du problme est toujours entire.

Algorithme : mthode hongroise.
Exemple 21 (Problme daffectation). Un pre propose 3 travaux ses enfants : tondre la pelouse, peindre le
garage et laver la voiture. Il demande chaque enfant combien il voudrait tre pay pour chaque travail.
John
Karen
Terri

Tondre
15
9
10

Peindre
10
15
12

Laver
9
10
8

Mthode hongroise
Slectionner le prix minimum dans chaque ligne.
Tondre Peindre Laver
John
15
10
9
9
Karen
9
15
10
9
Terri
10
12
8
8
Soustraire ce prix de chaque ligne et slectionner le prix minimum dans chaque colonne.
Tondre Peindre Laver
John
6
1
0
9
Karen
0
6
1
9
Terri
2
4
0
8
0
1
0
Soustraire ce prix de chaque colonne.
31

Tondre Peindre Laver

6
0
0
9
0
5
1
9
2
3
0
8
0
1
0
Les "0" en bleu donnent une affectation admissible optimale.
Loptimalit est assure par la valeur des variables duales (en rouge).
Nombre doprations : O(n2 ).
Il arrive que les valeurs nulles du tableau ne permettent pas de trouver de solution admissible.
0 3 2 2 1
1 4 6 3
2 0 0 2 7
9 7 10 9
0 1 4 3 4
4 5 11 7
3 2 0 0 5
8 7 8 5
0 0 3 0
Slectionner un nombre minimum de lignes et colonnes couvrant tous les 0.
0 3 2 2 1
2 0 0 2 7
0 1 4 3 4
3 2 0 0 5
0 0 3 0
Slectionner le plus petit lment non couvert, le soustraire tous les lments non couverts et lajouter aux
intersections.
0 2 1 1 2
3 0 0 2 7
0 0 3 2 5
4 2 0 0 5
-1 0 3 0
Rpter jusqu trouver une solution admissible.
John
Karen
Terri

8.2

Modle de transport

Un produit doit tre transport de sources (usines) vers des destinations (dpts, clients).
Objectif : dterminer la quantit envoye de chaque source chaque destination en minimisant les cots de
transport. Les cots sont proportionnels aux quantits transportes.
Contraintes doffre limite aux sources et de demande satisfaire au destinations.

Sources

a1

Destinations

a2

am

cm n xm n

Exemple 22 (Modle de transport).

32

b1

b2

bn

 Une firme automobile a trois usines Los Angeles, Detroit et New Orleans, et deux centres de distribution
Denver et Miami.
Les capacits des trois usines sont de 1000, 1500 et 1200 respectivement, et les demandes aux centres de
distribution sont de 2300 et 1400 voitures.
Cots :
Denver Miami
Los Angeles
80
215
Detroit
100
108
102
68
New Orleans
Formulation
min z = 80x11 +215x12 +100x21 +108x22 +102x31 +68x32
s.c.
(Los Angeles) x11
+x12
= 1000
(Detroit)
x21
+x22
= 1500
(N ew Orleans)
x31
+x32 = 1200
(Denver) x11
+x21
+x31
= 2300
(M iami)
x12
+x22
+x32 = 1400
x11 ,
x12 ,
x21 ,
x22 ,
x31 ,
x32 0
Reprsentation tableau

New Orleans

Denver
80
1000
100
1300
102

Demande

2300

Los Angeles
Detroit

Miami
215

Offre
1000

108
200
68
1200
1400

1500

Miami
215

Offre
1000

108

1300

68
1200
0
200
1400

1200

1200

Problmes non balancs

Si loffre nest pas gale la demande : modle non balanc.
Introduction dune source ou destination artificielle.

New Orleans

Denver
80
1000
100
1300
102

Artif.

Demande

2300

Los Angeles
Detroit

200

Variantes
Le modle de transport nest pas limit au transport de produits entre des sources et destinations gographiques.
Exemple 23 (Modle de production).
Une socit fabrique des sacs dos, pour lesquels la demande arrive de mars juin et est de 100, 200, 180 et
300 units, respectivement.
La production pour ces mois est de 50, 180, 280 et 270, respectivement.
La demande peut tre satisfaite
1. par la production du mois courant ($40 / sac) ;
33

2. par la production dun mois prcdent (+ $0.5 / sac / mois pour le stockage) ;
3. par la production dun mois suivant (+ $2 / sac / mois de pnalit de retard).
Correspondances avec le modle de transport
Transport
Source i
Destination j
Offre la source i
Demande la destination j
Cot de transport de i j

Production - stocks
Priode de production i
Priode de demande j
Capacit de production la priode i
Demande pour la priode j
Cot unitaire (production + stock + pnalit)
pour une production en priode i pour la priode j

Exemple 24 (Maintenance dquipements).

Une scierie prpare diffrents types de bois sur base dun plan hebdomadaire.
Pour satisfaire la demande, dpendant du type de bois, la scierie utilise un nombre donn de lames.
Pour satisfaire la demande, deux possibilits :
acheter une lame ($12) ;
faire aiguiser la lame (service express : $6 en une nuit, sinon $3 en 2 jours).
Demande :
Lun Mar Mer Jeu Ven Sam Dim
24
12
14
20
18
14
22
Modle de transport
8 sources : achat de nouvelles lames (offre = demande totale), 7 jours de la semaine (offre = nombre de lames
utilises).
8 destinations : 7 jours de la semaine (demande = nombre de lames utilises) + surplus de lames non achetes /
aiguises (demande = nombre total de lames).
Lun
Achat
12
Lun 10000
Mar 10000
Mer 10000
Jeu
10000
Ven
10000
Sam 10000
Dim 10000
Demande 24

Mar
12
6
10000
10000
10000
10000
10000
10000
12

Mer
12
6
6
10000
10000
10000
10000
10000
14

Jeu
12
3
6
6
10000
10000
10000
10000
20

Ven Sam Dim Surplus Offre

12
12
12
0
124
3
3
3
0
24
3
3
3
0
12
6
3
3
0
14
6
6
3
0
20
10000 6
6
0
18
10000 10000 6
0
14
10000 10000 10000
0
22
18
14
22
124

Algorithme pour le problme de transport

Bas sur lalgorithme du simplexe en tenant compte de la structure du problme.
1. Dtermination dune solution de base admissible.
2. Dtermination de la variable entrant en base.
3. Dtermination de la variable sortant de base.
Exemple 25 (Algorithme pour le problme de transport).

34

1
10

2
2

3
20

4
11

Offre
15

12

20

25

14

16

18

10

Demande

15

15

15

Dtermination dune solution de base admissible

Heuristiques "gloutonnes", pas besoin de mthode des deux phases.
Variantes :
1. Coin Nord-Ouest
2. Mthode des moindres cots
3. Approximation de Vogel (VAM)
Coin Nord-Ouest
Partir du coin suprieur gauche du tableau.
1. allouer le plus possible la cellule courante et ajuster loffre et la demande ;
2. se dplacer dune cellule vers la droite (demande nulle) ou le bas (offre nulle) ;
3. rpter jusquau moment o toute loffre est alloue.
Exemple 26 (Coin Nord-Ouest).

1
10
5
12

Demande

2
2
10
7
5
14

3
20

4
11

Offre
15

9
15
16

20
5
18
10
15

25

5 15 15
Cot : 520

10

Moindres cots
Slectionner la cellule de cot minimum.
1. allouer le plus possible la cellule courante et ajuster loffre et la demande ;
2. slectionner la cellule de cot minimum ayant une demande et une offre non nulles ;
3. rpter jusquau moment o toute loffre est alloue.
Exemple 27 (Moindres cots).
1

1
10

12

3
Demande

2
2
15
7

3
20

4
11

Offre
15

9
15
16

20
10
18
5
15

25

4 14
5
5 15 15
Cot : 475

Approximation de Vogel (VAM)

35

10

1. pour chaque ligne (colonne) avec une offre (demande) non-nulle, calculer une pnalit gale la diffrence
entre les deux cots les plus petits dans la ligne (colonne) ;
2. slectionner la ligne ou colonne avec la pnalit maximale et slectionner la cellule de cot minimum dans
la ligne ou colonne ;
3. allouer le plus possible la cellule courante ;
4. lorsquil ne reste quune ligne ou colonne : moindre cots.
Exemple 28 (VAM).
1

1
10

12

2
2
15
7

3
20

4
11

Offre
15

9
15
16

20
10
18
5
15

25

4 14
5
5 15 15
Cot : 475

Demande

10

Formulation

min z =

s.c.

(ui )

m X
n
X

cij xij

i=1 j=1
n
X
j=1
m
X

(vj )

xij = ai

i = 1, . . . , m

xij = bj

j = 1, . . . , n

i=1

xij 0

i = 1, . . . , m, j = 1, . . . , n

Problme dual

max w =

m
X
i=1

s.c.

ai ui +

n
X

bj vj

j=1

ui + vj cij

i = 1, . . . , m, j = 1, . . . , n

Adaptation du simplexe
Critre doptimalit :
ui + vj cij 0
Complmentarit :
xij > 0 ui + vj cij = 0
Trois tapes :

1. dtermination des variables duales (multiplicateurs) ;

2. vrification du critre doptimalit et dtermination de la variable entrante ;

3. dtermination de la variable sortante pour prserver ladmissibilit et pivotage.
Dtermination des variables duales
1. m + n 1 quations m + n inconnues : fixer u1 = 0.
36

2. Rsoudre rcursivement le systme

ui + vj cij = 0 pour tout xij > 0.
Exemple 29 (Dtermination des variables duales).

1
10
5
12

2
2
10
7
5
14

Demande

15

u1 + v1 = 10
u1 + v2 = 2
u2 + v2 = 7
u2 + v3 = 9
u2 + v4 = 20
u3 + v4 = 18

3
20

4
11

Offre
15

9
15
16

25

15

20
5
18
10
15

10

u1 = 0
v1 = 10
v2 = 2
u2 = 5
v3 = 4
v4 = 15
u3 = 3

Vrification du critre doptimalit et dtermination de la variable entrante

1
0
2
5
3
3
Demande

1
10
5
12

10

3
4

2
2
10
7
5
14

9
5

3
20

4
11

-16
9
15
16
-9

15

-9
15

15

Offre
15

4
20
5
18
10
15

25
10

Dtermination de la variable sortante pour prserver ladmissibilit et pivotage

Objectifs :

1. loffre et la demande doivent continuer tre satisfaites ;

2. les quantits transportes doivent rester positives.

Mthode :

1. construction dun cycle parcourant des variables en base en partant de et revenant la variable
entrante ;

2. dplacement le long de lignes et colonnes en alternant ajout et retrait dune mme quantit.

1
0
2
5
3
3
Demande

1
10
5
12
4
5

10

3
+
9

2
2
10
7
5
14

2
+

3
20

9
15
16

4
11

-16

-9
15

-9
15

=5

37

20
5
18
10
15

15

Offre
15

4
+

25

10

1
0
2
5
3
3
Demande

1
10

2
2
15
7
0
14

-9
12
-6
4
5
5

3
20

9
15
16

4
11

-16

-9

-9

15

15

20
10
18
5
15

15
+
4

Offre
15
25
10

= 10
1
0
2
5
3
7
Demande

-3

1
10

2
2
5
7
10
14

-13
12
-10
4
5
5

3
20

-16
9
15
16

11

Offre
15
25

-4

-5
15

4
11
10
20

-5
15

18
5
15

10

Extension du modle de transport : il est parfois ncessaire (ou moins cher) dutiliser des noeuds intermdiaires
pour le transport.
Deux usines P 1 et P 2 servent 3 vendeurs D1, D2 et D3, via deux centres de transit T 1 et T 2.
D1
800
8
3
5
1000
P1
T1
6
4
D2
900
7
4

2
1200

P2

3
T2

9
D3

500

Transformation en problme de transport

3 types de noeuds :
Noeuds doffre purs : arcs sortants uniquement. offre = offre originale
Noeuds de demande purs : arcs entrants uniquement. demande = demande originale
Noeuds de transbordement : arcs entrants et sortants. offre/demande = offre/demande originale + buffer
Les noeuds de transbordement sont la fois sources et destinations pour le problme de transport.
Buffer : quantit ncessaire pour transporter toute la demande travers le noeud de transbordement.
Dans notre exemple : B = 2200.

P1
P2
T1
T2
D1
D2
Demande

T1
3
2
0
M
M
M
2200

T2
4
5
7
0
M
M
2200

D1
M
M
8
M
0
M
3000

38

D2
M
M
6
4
5
0
3100

D3
M
M
M
9
M
3
500

Offre
1000
1200
2200
2200
2200
2200

9
9.1

Mthodes de Branch-and-Bound
Branch-and-Bound pour les problmes en nombres entiers

Les mthodes de branch-and-bound sont des mthodes bases sur une numration "intelligente" des solutions
admissibles dun problme doptimisation combinatoire.
Ide : prouver loptimalit dune solution en partitionant lespace des solutions.
"Diviser pour rgner"
Application la programmation linaire en nombres entiers : utilise toute la puissance de la programmation
linaire pour dterminer de bonnes bornes.
On appelle relaxation linaire dun programme linaire en nombres entiers le programme linaire obtenu en
supprimant les contraintes dintgralit sur les variables.
Programme en nombres entiers
(P )

max cT x
s.c.
Ax b
x 0, entier.

Relaxation linaire
(LP )

max cT x
s.c.
Ax b
x 0.

Proprits de la relaxation linaire

La valeur de la solution optimale de LP est une borne suprieure sur la valeur de la solution optimale de P .
La valeur dune solution admissible de P fournit une borne infrieure sur la valeur de la solution optimale de
P.
Si la solution optimale de LP est entire (donc admissible pour P ), elle est galement la solution optimale de
P.
Branchement
Si la solution de LP nest pas entire, soit xi une variable prenant une valeur fractionnaire xi dans la solution
optimale de LP .
Le problme peut tre divis en deux sous-problmes en imposant
xi bxi c

xi bxi c + 1

ou

o bxi c est le plus grand entier infrieur xi .

La solution optimale de P est la meilleure des solutions optimales des deux problmes
(P1 )

max cT x
s.c.
Ax b
xi bxi c
x 0, entier.

(P2 )

max
s.c.

cT x
Ax b
xi bxi c + 1
x 0, entier.

Exemple 30 (Branch-and-Bound).
max z =
s.c.

5x1
x1
10x1
x1 ,

+4x2
+x2
+6x2
x2

5
45
0, entiers.

(LP ) x1 = 3.75, x2 = 1.25

z = 23.75

39

(LP )

x1 = 3.75, x2 = 1.25
z = 23.75

x1 3

(LP1 )

x1 = 3, x2 = 2

x1 4

(LP2 )

...

z = 23

La solution de LP1 est une solution admissible de P et donc z = 23 est une borne infrieure sur la valeur de la
solution optimale de P .
Le noeud correspondant peut tre limin vu quune solution entire optimale satisfaisant x1 3 a t trouve
(solution de P1 ).

La valeur de la solution de LP , z = 23.75 est une borne suprieure sur la valeur de la solution optimale de P .

40

 Vu que tout les coefficients sont entiers, on peut en dduire que la valeur de la solution optimale de P est
infrieure ou gale 23.
La solution de P1 est donc optimale pour P .
Rgles de branchement
Il ny a pas de rgle gnrale pour le choix de la variable de branchement et de la branche examiner en premier.
Ce choix peut avoir un impact important sur le nombre de noeuds examiner dans larbre de branch-and-bound.
Exemple : branchement dabord du ct .
(LP )

x1 = 3.75, x2 = 1.25
z = 23.75

x1 3

(LP1 )

x1 4

(LP2 )

x1 = 3, x2 = 2

x1 = 4, x2 = 0.83
z = 23.33

z = 23

x2 0

(LP3 )

x2 1

x1 = 4.5, x2 = 0

(LP4 )

Pas de solution

z = 22.5

x1 4

(LP5 )

x1 5

x1 = 4, x2 = 0

(LP6 )

Pas de solution

z = 20

9.2

Branch-and-bound pour le voyageur de commerce

Formulation (rappel)
min z =

s.c.

n
n X
X

cij xij

i=1 j=1
n
X
j=1
n
X

xij = 1

i = 1, . . . , n

xij = 1

j = 1, . . . , n

i=1

xij |S| 1

=
6 S 6= {1, . . . , n}

i,jS

xij {0, 1}

i = 1, . . . , n, j = 1, . . . , n

Si on retire les contraintes dlimination de sous-tours, on obtient le problme daffectation.

Cette relaxation a une solution entire qui peut tre obtenue par exemple avec la mthode hongroise.
Le branchement est effectu de manire liminer les sous-tours.
La valeur de la solution optimale du problme daffectation (AP) est une borne infrieure sur la valeur de la
solution optimale du TSP.
Le cot dun tour fournit une borne suprieure sur la valeur de la solution optimale.
Si la solution optimale de AP est un tour (i.e. sans sous-tour), elle est galement la solution optimale du TSP.
Si un sous-tour apparat :
xi1 i2 = xi2 i3 = xi3 i4 = = xik1 ik = xik i1 = 1.
Dans une solution admissible, un de ces arcs doit tre absent, donc
xi1 i2 = 0 ou xi2 i3 = 0 ou . . . ou xik1 ik = 0 ou xik i1 = 0.
Chacune de ces conditions va correspondre une branche de larbre de branch-and-bound.

41

Exemple 31 (Voyageur de commerce).

9
6
8
9

1
2
3
4
5

2
8

40
4
10

3
2
20

2
6

4
10
9
7

5
3
7
5
5

Solution du problme daffectation

4
[153][24]

z = 28

[153][24] z = 28
x31 = 0

x15 = 0
x53 = 0

[15342] z = 29

[13][254] z = 28

[13][254]

z = 28

x31 = 0
x31 = 0
[15342] z = 29

[15243] z = 30

9.3

x13 = 0

x13 = 0

[135][24] z = 29

[12543] z = 32

Branch-and-bound pour les contraintes disjonctives

On peut utiliser une approche classique pour les problmes en nombres entiers en introduisant des variables
supplmentaires (voir formulation en dbut de partie).
On peut galement prendre comme relaxation le problme sans les contraintes disjonctives, et brancher sur les
contraintes non satisfaites.
Exemple 32 (Contraintes disjonctives).
Une machine est utilise pour 3 tches diffrentes. Pour chaque tches i, une dure pi et une date limite di sont
donnes, ainsi quune pnalit par jour de retard.
Tche Dure Limite Pnalit
1
5
25
19
2
20
22
12
15
35
34
3
Comment arranger les tches sur la machine pour minimiser la pnalit totale ?
Relaxation du problme

42

min z =
s.c.

19s
+12s
+34s
1
2
3
+

x1
+s1 s1

x2
+s+
2 s2

x3
+s+
3 s3
+

x1 , x2 , x3 , s1 , s1 , s2 , s2 , s3 , s3
x1
x2
x3

=
=
=

25
22
35
0
5
20
15

Branchement sur xi xj + pi ou xj xi + pj .
Solution de la relaxation : ordonnancement au plus tt.
Noeud 0

z=0

22

Relaxation : 0
Noeuds examiner :

25

35

Borne sup. : +.

1 : x1 x2 5
2 : x2 x1 20

Noeud 1

1 : x1 x2 5

Noeud 1 :

z=0

22

Relaxation : 0
Noeuds examiner :

25

35

Borne sup. : +.

2 : x2 x1
3 : x1 x2
x2 x3
4 : x1 x2
x3 x2

20
5
20
5
15

Noeud 3

3 : x1 x2 5
x2 x3 20

Noeud 3 :

z = 441

22

Relaxation : 441

25

Borne sup. : 441

43

35

Noeuds examiner :

2 : x2 x1 20
4 : x1 x2 5
x3 x2 15

Noeud 4

4 : x1 x2 5
x3 x2 15

Noeud 4 :

z=0

22

Relaxation : 0
Noeuds examiner :

25

35

Borne sup. : 441

2 : x2 x1
5 : x1 x2
x3 x2
x1 x3
6 : x1 x2
x3 x2
x3 x1

20
5
15
5
5
15
15

Noeud 5

5 : x1 x2 5
x3 x2 15
x1 x3 5

Noeud 5 :

z = 285

22

Relaxation : 285
Noeuds examiner :

25

Borne sup. : 285

2 : x2 x1
6 : x1 x2
x3 x2
x3 x1

20
5
15
15

Noeud 6

6 : x1 x2 5
x3 x2 15
x3 x1 15

44

35

Noeud 6 :

z = 170

22

Relaxation : 170

25

35

Borne sup. : 170

Noeuds examiner :
2 : x2 x1 20
Noeud 2

2 : x2 x1 20

Noeud 2 :

z = 36

22

Relaxation : 36
Noeuds examiner :

25

35

Borne sup. : 170

7 : x2 x1
x2 x3
8 : x2 x1
x3 x2

20
20
20
15

Noeud 7

7 : x2 x1 20
x2 x3 20

Noeud 7 :

z = 156

22

Relaxation : 156
Noeuds examiner :

25

Borne sup. : 170

8 : x2 x1
x3 x2
9 : x2 x1
x2 x3
x1 x3
10 : x2 x1
x2 x3
x3 x1

Noeud 9

45

20
15
20
20
5
20
20
15

35

9 : x2 x1 20
x2 x3 20
x1 x3 5

Noeud 9 :

z = 216

22

Relaxation : 216
Noeuds examiner :

25

35

Borne sup. : 170

8 : x2 x1
x3 x2
10 : x2 x1
x2 x3
x3 x1

20
15
20
20
15

Noeud 10

10 : x2 x1 20
x2 x3 20
x3 x1 15

Noeud 10 :

z = 216

22

Relaxation : 216
Noeuds examiner :

25

35

Borne sup. : 170

8 : x2 x1 20
x3 x2 15

Noeud 8

8 : x2 x1 20
x3 x2 15

Noeud 8 :

z = 206

22

Relaxation : 206

25

Borne sup. : 170

Solution optimale : 170 Ordre des tches : 2, 1, 3 (noeud 6)

46

35

10
10.1

Mthodes heuristiques
Introduction

La plupart des problmes pratiques sont NP-complets.

Ncessit de trouver des bonnes solutions rapidement.
Heuristiques ou algorithmes dapproximation.
Raisons de choisir une heuristique
Une solution doit tre trouve rapidement (secondes / minutes).
Instance trop grande ou complique : impossible formuler comme un problme en nombre entiers de taille
raisonnable.
Impossibilit pour le Branch-and-Bound de trouver une (bonne) solution admissible.
Pour certaines classes de problmes : trouver des solutions admissibles est facile (structure du problme) mais
une approche gnraliste de programmation en nombres entiers nest pas efficace.
Questions se poser...
Doit-on accepter nimporte quelle solution, ou doit-on se demander a posteriori quelle distance de loptimalit
on se trouve ?
Peut-on garantir a priori que lheuristique va produire une solution  (ou %) de loptimal ?
Peut-on dire a priori que, pour la classe de problmes considre, lheuristique va produire en moyenne une
solution % de loptimal ?
Contexte gnral
Problme doptimisation combinatoire
min
s.c.

F (x)
x X.

avec F une fonction valeur relles dfinie sur X,

X lensemble des solutions admissibles.
Hypothse
X de trop grande taille pour permettre lnumration.

10.2

Heuristiques de construction

Objectif : construire une (bonne) solution admissible.

Se basent sur la structure du problme pour gnrer une solution.
Gnralement : mthodes gloutonnes. Construisent la solution en ajoutant lment par lment, choix dfinitifs
(pas de retour en arrire).
Dfaut : mthodes aveugles, un mauvais choix fait en cours de construction ne peut pas tre dfait.
Exemples :
problme de transport (coin nord-ouest, moindre cots, VAM)
voyageur de commerce (plus proche voisin, meilleure insertion)
heuristique gloutonne pour le problme de sac--dos.
Voyageur de commerce : plus proche voisin
partir dun sommet quelconque, par exemple le sommet 1
tant quil reste des sommets libres faire :
connecter le dernier sommet atteint au sommet libre le plus proche
relier le dernier sommet au sommet 1
Exemple 33 (Voyageur de commerce).

47

1
2
3
4
5

9
6
8
9

2
8

40
4
10

3
2
20

2
6

4
10
9
7

5
3
7
5
5

Tour : 1 3 5 4 2 1
Cot : 29
Remarque : si dmarrage du noeud 2 :
Tour : 2 5 3 1 4 2
Cot : 33
Voyageur de commerce : meilleure insertion
partir dun cycle rduit une boucle sur le sommet 1 (par exemple)
tant quil y a des sommets libres faire :
pour tous les sommets libres j, chercher la position dinsertion entre 2 sommets i, k du cycle minimisant
M = cij + cjk cik
insrer le sommet qui minimise laccroissement du cot
Exemple 34 (Voyageur de commerce).
1
2
3
4
5

9
6
8
9

2
8

40
4
10

3
2
20

2
6

4
10
9
7

5
3
7
5
5

1. 1 1, k = 3, M = 8
2. 1 3 1, k = 5, M = 7
3. 1 5 3 1, k = 4, M = 5
4. 1 5 4 3 1, k = 2, M = 10
5. 1 5 2 4 3 1, cot : 30.
Le problme de sac--dos
Le problme de sac--dos revient dcider quels objets mettre dans un contenant ayant une capacit donne W
de manire maximiser le profit total des objets choisis.
Chaque objet a un profit pi 0 et un poids wi 0.
Problme de sac--dos
n
P

z = max

p j xj

j=1

s.c.

n
P

wj xj W

j=1

xj {0, 1}

j = 1, . . . , n

Heuristique gloutonne pour le problme de sac--dos

Ide de base : Les objets les plus intressants sont ceux qui ont un petit poids pour un grand profit, i.e. un rapport
pi
wi grand.
Heuristique gloutonne pour le problme de sac--dos
1. Ordonner les objets par ordre dcroissant de

pi
wi

ordre i1 , . . . , in .

2. S = .
48

3. Pour t = 1, . . . , n faire :
Si w(S) + wit W , alors S := S {it }. 1
Analyse de lheuristique
Rsolution de la relaxation linaire
1. Ordonner les objets par ordre dcroissant de

pi
wi

ordre i1 , . . . , in .

2. S = , t = 1.
3. Tant que w(S) + wit W :
S := S {it }.
4. Complter la capacit avec la fraction ncessaire de lobjet it .
Soit S la solution de lheuristique gloutonne, zLP la valeur de la relaxation linaire et p0 = maxi=1,...,n pi .
Considrons z = max{p(S), p0 }.

p(S) + p0
zLP
zOP T
z = max{p(S), p0 }

2
2
2

10.3

Recherche locale

Heuristiques de construction : utiles pour trouver une premire solution admissible, mais souvent de mauvaise
qualit.
Ide : essayer damliorer cette solution en tenant compte de la structure du problme.
Etant donn une solution, dfinition dune notion de voisinage de cette solution.
Mthode de descente : recherche du meilleur voisin jusquau moment o aucune amlioration nest possible.
Pour toute solution x X, on dfinit V (x) X comme tant lensemble des solutions voisines de x (x
/
V (x)).
Algorithme de descente
Initialisation : x0 X solution initiale.
Etape n : soit xn X la solution courante ;
slectionner x V (xn ) ;
si F (x ) F (xn ) :
xn+1 := x ; passer ltape n + 1.
sinon xn meilleure solution trouve ; stop.
En gnral (si pas trop long), choix du meilleur lment du voisinage.
Voyageur de commerce : k-opt
Voisins dun tour : tous les tours qui peuvent sobtenir en retirant k artes et en reconnectant de la meilleurs
manire possible.
Exemple 35 (2-opt).

1. Notation : w(S) :=

iS

wi

49

10.4

Mta-heuristiques

Inconvnient principal des algorithmes de descente : sarrte, le plus souvent, dans un optimum local et non
dans un optimum global.
Ide gnrale des mta-heuristiques : autoriser une dtrioration temporaire de lobjectif, permettant ainsi de
quitter des minimums locaux tout en maintenant en gnral une pression favorisant les solutions qui amliorent l objectif.
Caractristiques des mta-heuristiques
plus simples et plus rapides mettre en oeuvre quand lexigence de qualit de la solution nest pas trop importante ;
plus souples dans les problmes rels (contraintes non formules ds le dpart) ;
sadaptent plus facilement des contraintes additionnelles venant du terrain ;
fournissent des solutions et des bornes qui peuvent tre utiles dans des mthodes exactes.
Le recuit simul (simulated annealing)
Ide de base provient de lopration de recuit (annealing), courante en sidrurgie et dans lindustrie du verre.
Recuit en sidrurgie
Aprs avoir fait subir des dformations au mtal, on rchauffe celui-ci une certaine temprature, de manire
faire disparatre les tensions internes causes par les dformations, puis on laisse refroidir lentement.
Lnergie fournie par le rchauffement permet aux atomes de se dplacer lgrement et le refroidissement lent fige
peu peu le systme dans une structure dnergie minimale.
Application du recuit simul loptimisation
Modification de lheuristique de descente :
au lieu de ne permettre que des mouvements (des changements de solution courante) qui diminuent lnergie
(la fonction objectif), on autorise des augmentations, mme importantes, de lnergie au dbut de lexcution
de lalgorithme ;
puis, mesure que le temps passe, on autorise ces augmentations de plus en plus rarement (la temprature
baisse).
Finalement, le systme gle dans un tat dnergie minimale.
Recuit simul
Initialisation : x0 X solution initiale, F := F (x0 ).
Etape n : soit xn X la solution courante ;
tirer au sort une solution x V (xn ) ;
si F (x ) F (xn ) : xn+1 := x ;
si F (x ) < F : F := F (x )
sinon, tirer un nombre q au hasard entre O et 1 ;
si q p : xn+1 := x ;
sinon : xn+1 := xn ;
si la rgle darrt nest pas satisfaite,
passer ltape n + 1 ;
sinon, stop.
Paramtres du recuit simul
La probabilit p est gnralement une fonction p(T, F ) dpendant dun paramtre T (temprature), et de la
dgradation de lobjectif F = F (x ) F (xn ) rsultant du remplacement de xn par x comme solution
courante.
Analogie avec les systmes physiques (distribution de Boltzmann) :
p(T, F ) = e

F
T

Evolution de la temprature : diminue toutes les L itrations.

Tk = Tk1 = k T0 .
50

 T0 choisi par simulation de sorte quau dbut de lexcution de lalgorithme, des solutions moins bonnes que
la solution courante soient aisment acceptes. En gnral, on fixe un taux dacceptation initial moyen des
solutions plus mauvaises que la solution courante.
Exemple : taux fix 50%, valuer par simulation la dtrioration moyenne < F > de F (en partant dune
solution initiale fixe).
< F >
( p = 0.5)
TO =
ln 2
La longueur L du palier de temprature doit tre dtermine en tenant compte de la taille des voisinages ; elle
devrait augmenter avec la taille du problme.
En pratique, la dtermination de L est exprimentale.
Le paramtre de dcroissance gomtrique de la temprature est fix, le plus souvent, aux alentours de 0.9 ou
0.95.
Critre darrt : nombre maximal ditrations ou systme est gel : e.g. si la fonction F a diminu de moins
de 0.1 % pendant cent paliers conscutifs.
Quelques observations sur le recuit simul
Voyageur de commerce : pas concurrentiel par rapport dautres approches.
En gnral : amliore les solutions dune descente pure, mais trs coteux en temps calcul.
Rsultat thorique : sous certaines conditions, converge avec probabilit 1 vers une solution optimale.
Rsultat asymptotique (nombre ditrations tendant linfini), peu de pertinence en pratique.
Recherche tabou
Emprunte certains de ses concepts lintelligence artificielle (notion et utilisation de mmoire).
Variante de la recherche locale.
Partant de la solution courante xn ltape n, on calcule la meilleure solution x dans un sous-voisinage V de
V (xn ). Cette solution devient la nouvelle solution courante xn+1 , quelle soit meilleure ou moins bonne que la
prcdente.
Caractre non monotone pour viter de rester coinc dans des minimums locaux.
MAIS ncessit dun mcanisme qui vite le cyclage.
Listes tabou
Pour viter le cyclage, on dfinit une ou plusieurs listes, les listes tabou, qui gardent en mmoire les dernires
solutions rencontres ou des caractristiques de celles-ci.
Le sous-voisinage V de V (xn ) exclut ds lors les solutions rencontres rcemment ou les solutions ayant des
caractristiques communes avec celles-ci.
Exemple 36 (Voyageur de commerce).
Villes : {A, B, C, D, E}
Voisinage : 2-change (change de deux villes dans lordre des visites)
Liste tabou : positions changes dans le cycle.
Solutions visites :
xn = (A, B, C, D, E)
xn+1 = (A, D, C, B, E)

((2, 4) devient tabou)

xn+2 = (B, D, C, A, E)

((1, 4) devient tabou)

xn+3 = (B, C, D, A, E)

((2, 3) devient tabou)

xn+4 = (B, C, D, E, A)

((4, 5) devient tabou)

xn+4 xn mais OK si xn+5 peut tre 6= xn+1 .

Si la liste est de longueur 4, les solutions
(B, E, D, C, A), (E, C, D, B, A), (B, D, C, E, A), (B, C, D, A, E)
sont exclues pour xn+5 .

51

Critres daspiration
Puisque les listes tabou cartent des solutions non rencontres, on peut envisager de ngliger le statut tabou de
certaines solutions si un avantage suffisant en rsulte.
Ceci est implment laide de critres daspiration. Par exemple, on acceptera pour xn+1 une solution x tabou
si x donne la fonction objectif F une valeur meilleure que toutes celles obtenues jusqu prsent.
Recherche tabou
Initialisation : x0 X solution initiale, F := F (x0 ), k = longueur de la liste tabou..
Etape n : soit xn X la solution courante ;
slectionner, dans un sous-voisinage V de V (xn ), la meilleure solution x qui soit :
non tabou ou
tabou, mais satisfaisant un critre daspiration ;
xn+1 := x ;
si F (x ) < F : F := F (x )
mettre jour la liste tabou ;
si la rgle darrt nest pas satisfaite,
passer ltape n + 1 ;
sinon, stop.
Stratgies avances de la recherche tabou
Succession de phases dintensification et de phases de diversification de la recherche.
Pnalits ou bonifications introduites dans la fonction objectif pour favoriser ou dfavoriser certains types de
solutions.
Adaptation de lensemble des solutions candidates V .
Oscillation stratgique.

10.5

Algorithmes gntiques

Conus par Holland (1975) comme un modle de systme adaptatif complexe capable de simuler, notamment,
lvolution des espces.
Presque immdiatement aprs, appliqus loptimisation de fonctions de variables relles. Par la suite, de trs
nombreux problmes doptimisation combinatoire ont t traits.
Se distinguent du recuit et de la recherche tabou par le fait quils traitent et font voluer une population de
solutions.
Au cours dune itration, les solutions de la population courante interagissent pour fournir la gnration suivante
(mtaphore de la reproduction sexue).
Description dun algorithme gntique de base
Les solutions sont codes de manire approprie. Un codage lmentaire pour un problme de programmation
mathmatique en variables binaires est un vecteur x de 0 et de 1, o chaque composante xj , j = 1, . . . , N
reprsente la valeur prise par une variable.
Pour le problme du voyageur de commerce, un codage plus usuel sera une liste ordonne des noms (ou labels)
des N villes.
Un vecteur codant une solution est souvent appel chromosome et ses coordonnes ou sites sont appels gnes.
Le choix dun codage appropri est trs important pour lefficacit des oprateurs qui seront appliqus pour
faire voluer les solutions.
Population initiale de solutions X (0) (taille constante au cours de lvolution).
Fonction dvaluation des solutions : en gnral, croissante avec la qualit de la solution (fitness function,
mesurant la sant de lindividu solution).
Dans un problme de maximisation (respectivement, de minimisation), ce peut tre la fonction objectif (respectivement, loppos de la fonction objectif).
Pour des raisons defficacit de lalgorithme, on peut tre amen choisir la fonction dvaluation de manire
plus sophistique, mais elle sera toujours croissante (respectivement, dcroissante) en la valeur de lobjectif
dans un problme de maximisation (respectivement, de minimisation).

52

Algorithme gntique
Initialisation : X (0) X, population initiale.
Etape n : X (n) X, population courante ;
slectionner dans X (n) un ensemble de paires de solutions de haute qualit ;
appliquer chacune des paires de solutions slectionnes un oprateur de croisement qui produit une ou
plusieurs solutions enfants ;
remplacer une partie de X (n) forme de solutions de basse qualit par des solutions enfants de haute
qualit ;
appliquer un oprateur de mutation aux solutions ainsi obtenues ; les solutions ventuellement mutes
constituent la population X (n+1) ;
si la rgle darrt nest pas satisfaite,
passer ltape n + 1 ;
sinon, stop.
Slection
La slection - aussi bien celle des individus de haute qualit que celle des individus de basse qualit comporte gnralement un aspect alatoire.
Chaque individu xi se voit attribuer une probabilit pi dtre choisi dautant plus grande que son valuation est
haute (basse, dans le cas dune slection de mauvais individus).
On tire un nombre r au hasard (uniformment) entre 0 et 1. Lindividu k est choisi tel que :
k1
X

pi < r

i=1

k
X

pi

i=1

La procdure est itre jusqu ce que lon ait choisi un nombre fix dindividus.
Croisement
Soit deux solutions x et y slectionnes parmi les solutions de haute qualit. Un oprateur de croisement (crossover)
fabrique une ou deux nouvelles solutions x0 , y 0 en combinant x et y.
Exemple 37 (Two-point crossover).
x et y vecteurs 0-1 ;
slectionner alatoirement deux positions dans les vecteurs et permuter les squences de 0 et de l figurant entre
ces deux positions dans les deux vecteurs.
Pour les vecteurs :
x = 0 1 1 0 1 1 0 0
y = 1 1 0 0 1 0 1 O
si les positions aprs 2 et aprs 5 sont choisies, on obtient :
x0
y0

= 0 1
= 1 1

0
1

0
0

1
1

1
0

0
1

0
O

Mutation
Une mutation est une perturbation introduite pour modifier une solution individuelle, par exemple la transformation dun 0 en un 1 ou inversment dans un vecteur binaire.
En gnral, loprateur de mutation est appliqu parcimonieusement : on dcide de muter une solution avec
une probabilit assez faible (de lordre de quelques centimes, tout au plus).
Un but possible de la mutation est dintroduire un lment de diversification, dinnovation comme dans la
thorie darwinienne de lvolution des espces.
Remarques finales
La recherche tabou peut tre trs efficace, mais implmentation et ajustement des paramtres difficiles, forts
dpendants de la structure du problme.
Les algorithmes gntiques sont efficaces si la structure du problme est bien exploite.
Mthodes hybrides trs efficaces (exemple : recherche locale utilise comme oprateur de mutation).
53