Université A.

MIRA de Béjaia
Faculté des Sciences Exactes
Département d’Informatique

Module : Techniques d’Optimisation

Dr TARI Abdelkamel
Maître de Conférences Habilité
Directeur du Laboratoire de Recherche LIMED

Février 2014
 Programme du module
• Introduction à l’Optimisation Combinatoire
• Problème de flôt maximum
• Programmation linéaire en nombres entiers
• Programmation Booléenne
• Parcours Hamiltonien et Eulerien dans un
graphe

Février 2013
 Quelques informations utiles
• Pré requis du module:
– Théorie des graphes
– Programmation Linéaire
• Ouvrages recommandés:
– Cote: 511.5/12- Claude Berge. Graphes et
Hypergraphes
– Cote: 003/23-Roseaux. Exercices corrigés
– Cote: 003/19-Roseaux. Exercices corrigés
• Site du groupe: e-learning de l’université (à construire):
[email protected]
• Mot de passe: bejaia2014
Techniques d'Optimisation Février 2014
 Définition de la RO
• Operations Research (OR) is a discipline that deals with
application of advanced analytical methods to help make
better decisions. (Wikipédia).
• Advanced analytical methods include mathematical logic,
graph, network analysis, Petri net, queuing theory, simulation
etc.
• Concevoir et implémenter des approches pour résoudre des
problématiques liées à des domaines diverses (informatique,
médecine, économie, finance, militaire etc.) jusqu’à
satisfaction du (des) décideur (s).

Techniques d'Optimisation
4
Méthodologie d’approche
1- Analyse du système dans
lequel le problème est posé
(Approche CATWOE)

2- Identifier les facteurs

(Contrôlables et non contrôlables) et
les objectifs

3- Construire le modèle (Graphe,

Réseaux de Pétri, Mathématiques,
Simulation etc.)

4) Elaborer une approche de résolution

(exacte ou approchée)

5- Concevoir et implémenter les

algorithmes de l’approche de résolution

Techniques d'Optimisation
5
 Formulation d’un problème
• Objectifs du système (minimisation de coût,
minimisation de l’énergie dans les réseaux de
capteurs, etc.)
• Facteurs contrôlables: Variables de décisions
• Facteurs non contrôlables: Contraintes et ceux
imposés par l’environnement
• Exemple voyageur de commerce:
Objectif: Minimiser la longueur totale parcourue
Contraintes: Cycle Hamiltonien (pas de cycles
parasites), les distances entre les sommets.
Techniques d'Optimisation F
6
 Modélisation d’un problème
• Un modèle est une représentation d’une
réalité.
• Forme d’un modèle: Mathématique (linéaire
et non linéaire), graphe (toutes ses topologies:
arbre, arborescence, biparti etc.), réseau
(toutes ses formes: Transport, Pétri, Automate
à états finis etc.), simulation, théorie des jeux
etc.
• Traduire les objectifs et contraintes en termes
de variables de décision
Techniques d'Optimisation
7
 Exemple de Modélisation
On associe au problème un réseau R=(X, U, l)
Où: X: l’ensemble des villes, U les liens entre ces villes et l:
la longueur entre ces villes
• Variables de décision: xij = 1 si l’arc (i, j) est emprunté et 0
sinon n n
Min Z    lij xij
i 1 j 1
n
 xij  1 i  1,..., n
j 1
n
 xij  1 j  1,..., n
i 1
xij  (1, 0)
8
Techniques d'Optimisation
 Problème d’Optimisation Combinatoire
• Un (POC) consiste à chercher le minimum S* d’une
application  le plus souvent à valeurs entières ou
réelles sur un ensemble fini S
Trouver s*  S

 *
 f ( s )  Min f ( s )
 sS
• Un problème d’existence (PE ) consiste à chercher
sS
• PE équivalent à un POC

Techniques d'Optimisation 9
 Approches de résolution (1/2)
• Méthodes exactes:
– Programmation linéaire (Simplexe et ses variantes)
– Programmation non linéaire avec ou sans
contraintes (relaxation de Lagrange, Khun Tecker
– Programmation en nombres entiers et bivalentes
(Branch and Bound)
– Arbre recouvrant (Algorithme Glouton: Kruskal)
– Cheminement (Algorithme Glouton:Djikstra,
Bellman, Ford)
– Flôt (Ford et Fulkerson)
– Etc…
Techniques d'Optimisation 10
 Approches de résolution (2/2)
• Méthodes approchées
– Heuristiques (recherche locale)
• Algorithmes de construction (plus proche voisin, plus
proche insertion, meilleure insertion)
- Métaheuristiques (recherche globale)
- Algorithmes génétiques
- Recherche Taboo
- Recuit simulé
- Colonies de fournies etc.

Techniques d'Optimisation 11
 Classification naïve de problèmes
- Problème facile ou problème difficile

• Si le problème est "facile": Trouver un algorithme

efficace.

• Si le problème est « difficile» et de "grande taille":

Chercher une solution approchée et garantir
l’efficacité de cette solution.

Techniques d'Optimisation 12
 Quelques Applications(1/3)
• Parcours d’un graphe (existence de chaîne, chemin,
cycle et circuit)
• Programmation linéaire (recherche d’une solution de
base réalisable optimale parmi toutes les solutions de
bases réalisables)
• Problèmes de routage dans les réseaux (ad-hoc, capteurs,
DTN etc.): entre deux noeuds particuliers (facile), entre
n’importe quel couple de nœud du réseau (difficile).
• Découverte sémantique de services web: Pour une
requête d’un utilisateur, il s’agit de trouver un service (atomique
ou virtuel) parmi un nombre important de services celui qui
satisfait cette requête .

Techniques d'Optimisation 13
 Quelques applications (2/3)
• Emplois du temps : Planifier n cours en un minimum de
temps, certains cours ne pouvant avoir lieu en parallèle
(partage des ressources: classe ou prof).

• Localisation d’entrepôts: Combien faut-il créer

d'entrepôts et où faut-il les installer de façon à satisfaire tous
les clients avec un coût total minimal? Application réelle:
Algérie Télecom où les entrepôts sont les stations de
téléphonie

• Etc.

Techniques d'Optimisation
14
 Quelques Applications (3/3)
• Optimisation des tournées de véhicules dans les
problèmes de distribution, organisation des centres
logistiques.
• Bin packing: Comment mettre les objets dans les Boîtes en
utilisant le moins possible de Boîtes? Problèmes de
chargement en conteneurs des bateaux, problème de
stockage de l’information sur des supports
• Voyageur de commerce, postier chinois
• Ordonnancement d’ateliers : Ordonnancer les passages
sur les machines(Facile: Aspect temporel, difficile: aspect
ressources
• Etc.
Techniques d'Optimisation 15
 La théorie des Graphes (TG)
 TG(Vocabulaire, théorèmes,
algorithmes,…) a été développée
depuis le 20ème siècle par Claude Berge

 TG est un outil puissant de

modélisation conduisant à des
solutions efficaces.
Claude BERGE

Modéliser une situation à l'aide d'un

graphe revient à identifier l’ensemble
X des sommets (nœuds) et à
caractériser l’ensemble U des arêtes
Techniques d'Optimisation
(arcs). 16
 Définitions et terminologies
• L’ordre d’un graphe est égal au nombre de ses sommets.
L’ordre du graphe G est égal à 4.
• On dit que deux sommets sont adjacents s’ils sont reliés
par une arête (arcs).
• Une arête (arc) est incidente à un sommet si ce dernier
est une de ses deux extrémités.
• Deux arêtes (arcs) sont adjacentes si au moins une de
leurs extrémités est commune.
• Un graphe est dit simple si chaque couple de sommets
est relié par au plus une arête (arc).
• Un graphe est complet si chaque sommet est adjacent à
tous les autres, c'est a dire si toutes les arêtes possibles
existent (sauf les boucles).
Techniques d'Optimisation 17
 Concepts et résultats
• Un sommet est isolé s’il n’est adjacent à aucun autre sommet.
Un graphe est nul s’il n’a aucune arête, c’est un ensemble de
sommets isolés.
• Le degré d’un sommet x, dG(x), est le nombre d’arêtes (arcs) qui
lui sont incidentes (intérieurement et extérieurement dans le cas
orienté).
• La somme des degrés des sommets est paire.
• Le nombre d’arêtes d’un graphe est égal à la somme des
degrés des sommets divisée par deux.
• Le nombre de sommets de degré impair d’un graphe non
orienté est donc toujours pair.
• Dans un graphe simple d’ordre n on a: dG(x)≤(n-1) xX
• Le diamètre d’un graphe est la plus grande distance entre deux
sommets
Techniques d'Optimisation 18
Quelques structures d’un graphe (1/3)
• Sous graphe, graphe partiel et sous graphe partiel
• Parcours (chaîne, cycle, chemin, circuit) Hamiltonien
(élémentaire) et Eulerien (simple) d’un graphe
• Cycle et cocycle engendré par une partie A de X
• Arbre et co-arbre
– Construction d’un arbre recouvrant
– Problème de l’arbre de poids minimum
(Algorithme de Kruskal) (problème Facile)
– Problème de la recherche arborescente
(Problème difficile)
– Problèmes de cheminiment (facile et difficile)
Techniques d'Optimisation 19
 Quelques structures d’un graphe (2/3)
• Une clique est un sous-ensemble de sommets qui induit un
sous graphe complet et symétrique.
• Une clique d’ordre n sommets possède n(n-1)/2 arêtes
• On note Kn l’ensemble des cliques d’ordre n d’un graphe G.
• Une clique C est dite maximale s’il n’existe pas une autre
clique C’ qui la contient. On note G l’ensemble des cliques
maximales de G
• Le problème de la recherche d’une clique maximale de
cardinalité maximale est un POC difficile.
• Applications:
• Réseaux sociaux: Rechercher une communauté d’individus tous en
relation
• Biologie l’interaction entre gènes, métabolites ou protéines

Techniques d'Optimisation 20
 Quelques structures d’un graphe (3/3)
• Un couplage C est un ensemble d’arêtes 2 à 2 non
adjacentes.
– Recherche d’un couplage de cardinalité maximale
• Un stable S est un ensemble de sommets 2 à 2 non
adjacents.
– Recherche d’un stable de cardinalitémaximale
• Un transversal T est un ensemble de sommets tel que
chaque arête de G a au moins une extrémité dans T.
– Recherche d’un Transversal de cardinalité minimale

Techniques d'Optimisation 21
 Exemple
• Soit le graphe non orienté suivant:

2 7

1 3 6 8

4 5
Déterminer un couplage maximal, un transversal
minimal, un stable maximal et une clique maximale.
Techniques d'Optimisation 22
 Complexité Algorithmique (1/6)
• Développée en 1970 pour répondre à la question d’existence
d’algorithme polynomiale pour une classe de problème dit
difficile.
• La complexité temporelle ( CPU time ou temps d’exécution )
dépend de la machine , des langages de programmation , du
compilation utilisé ( version , gestion du compilateur, etc.) et
des données.
• La complexité spéciale ( espace mémoire) dépend de la
machine et de la taille des données .
 Solution:
Calcul du nombre d’opérations élémentaires de
l’algorithme à évaluer (adition, soustraction,
multiplication, division, comparaison etc.)

Techniques d'Optimisation 23
 Complexité algorithmique ( 2/6)
• Combien de temps / d’espace faut-il pour résoudre un
problème?
• La complexité dépend uniquement du problème et pas d’un
algorithme particulier qui permet de le résoudre.
• La complexité d’un algorithme A est une fonction CA(n) donnant
le nombre d’opérations caractéristiques exécutées par A, dans
le pire des cas, par une donnée de taille n.
– La taille d’une donnée est la quantité mémoire (en bits) nécessaire pour
la stocker
– Dans les graphes, la taille des données est exprimée par le nombre de
sommets n et/ou le nombre d’arcs m.
• En théorie, la complexité est mesurée par le nombre de
déplacements effectués par la tête de Lecture/Ecriture de la
machine de Turing (Lecture obligatoire: PDF machine de Turing)

Techniques d'Optimisation 24
 Complexité Algorithmique (3/6)
• Quelques exemples d’instructions élémentaires:
– Ecrire un caractère à l’écran
– Lire un caractère dans un fichier
– Affecter une valeur atomique (caractère, entier, réel etc.) à
une variable
– Réaliser une opération élémentaire (adition, multiplication,
etc.) sur des valeurs atomiques
– Etc.
• Un algorithme dont la complexité est une fonction polynôme
en n est dit polynômial. Sinon, il est dit exponentiel.
• Une complexité exponentielle peut être une vraie fonction
exponentielle (en, 2n) au sens mathématique mais aussi
d’autres fonctions comme nlogn, n!, nn , etc.

Techniques d'Optimisation 25
 Complexité algorithmique (4/6)
• Soient  et g deux fonctions de R R, on dit que  est
d’ordre inferieure ou égale à g ou d’ordre au plus g, si on
peut trouver un réel xO et un réel positif c tel que:
 x ≥ xO  ( x ) ≤ ( g (xO)). On écrit  = O ( g ) que l’on
prononce Grand O de g .
Exemple: Considérons deux algorithmes A1 et A2 pour un
problème de taille n avec : CA1 ( n ) = 0,5 n2 et CA2 ( n ) = 5n .

• Soient deux fonctions  et g deux fonctions de R R.

– Si lim n (f/g )= c, avec c> 0 alors  et g sont de même
ordre (on note =O(g) et g=O(f)  f=  (g)).
– Si lim n (f/g )= 0 alors f=O(g).
– Si lim n (f/g )= +  alors g=O(f).
Techniques d'Optimisation 26
 Complexité algorithmique ( 5/6)
• Un problème est dit décidable si et seulement s’il existe un
algorithme qui permet de le résoudre. A l’inverse, tout
problème n’ayant pas d’algorithme pour sa résolution est
qualifié d’indécidable.
• Exemples de complexité:
– Complexité constante : CA(n) = O(1): Le nombre d’opérations est
indépendant de la taille des données à traiter.
– Complexité logarithmique : CA(n)= O (log(n)): Lorsque l’algorithme
morcèle un problème complexe en plusieurs sous problèmes de sorte
que la résolution d’un seul de ces sous problèmes conduit à la solution
du problème initial.
– Complexité linéaire : CA(n) = O(n.log(n)): L’algorithme divise le
problème en sous problèmes plus petits qui sont résolus de manières
indépendantes. Dans ce cas, la résolution des sous problèmes mène à
la solution du problème global.
Techniques d'Optimisation 27
 Complexité Algorithmique (6/6)

• Complexité quadratique : CA(n)= O(n2) ; l’algorithme envisage toutes les

paires de données parmi les n entrées (exemple, deux boucles
imbriquées).

• Complexité cubique : CA(n)= O(n3)  etc.

• Complexité exponentielle : CA(n)= O(2n). Dans ce cas, il n’existe aucune

garanti que la solution s’obtienne en un temps raisonnable.

Techniques d'Optimisation 28
 Machine de Turing
- Automate abstrait composé des éléments suivants:
- Une bande infinie, décomposée en cellules où sont stockés des
caractères (issus d’un ensemble fini).
- Une tête de lecture/écriture qui effectue les opérations suivantes:
- Lecture et modification du caractère stocké dans la cellule correspondant
à la position courante de la tête (le caractère courant)
- Déplacement d’une cellule vers la gauche ou vers la droite (modifier la
position courante)
- Un ensemble fini d’états internes
- Une table de transitions où on associe à chacun de ses couples un
triplet: (état interne[nouveau], caractère[nouveau], déplacement)
pour indiquer les nouvelles valeurs de chaque (état interne, caractère
courant) ainsi que le déplacement de la tête de lecture/écriture

….. 0 1 1 0 1
…..

Techniques d'Optimisation 29
 Fonctionnement d’une Machine de Turing
• Cas déterministe: On fournit à la machine le problème initial
selon un certain encodage sur les cases 0 a n de la bande de la
machine de Turing, et la machine effectue son calcul. Il s’agit
de savoir si on peut garantir que la machine va au bout d'un
certain temps répondre par VRAI ou FAUX sur la nature de
problème.
• Cas non déterministe: Une fois que le problème a été écrit, à
rajouter des cases magiques, par exemple, avant la case 0, qui
encode une solution devinée du problème. La machine vérifie
que les cases magiques fournissent bien une solution au
problème, et répond par VRAI ou FAUX. La question est de
savoir si, étant donne un problème ayant une solution, il
existe au moins une affectation des cases magiques qui
atteste de l'existence de cette solution en un temps
déterminé. Techniques d'Optimisation 30
Artifices pour le calcul de la complexité (1/2)
• Appel séquentiel
f(…)
{
g(…); Coût(f(…))= Coût(g(…)) + Coût(h(…))
h(…);
}
.
• Appel conditionnel
f(…)
{
if (…)
g(…) Coût(f(…))= Max(Coût(g(…); coût(h(…))
else
h(…)
} Techniques d'Optimisation 31
 Artifices pour le calcul de la complexité (1/2)
• Appel itératif
f(…, int n)
{ Coût (f(…, n))= n. Coût(g(…))
for (i=1; i<n; i++)
g(…);
}
.
Attention lorsque l’appel à la fonction g(…) dépend de l’indice de
la boucle, nous devons compter les différents appels
Coût (f(…, n))=

Techniques d'Optimisation 32
 Quelques Exemples
Exemple: Tri d’un tableau de n entiers en total désordre.
Algorithme naïf : Parcourir le tableau en sélectionnant le plus petit
entier, et inverser sa position avec le 1er entier du tableau. Il faut
faire n comparaisons pour déterminer seulement le plus petit
entier ! il faut faire n fois cette opération pour avoir ainsi le
tableau trié. O(n²)!!!
• Calcul d’un minimum dans un tableau de n éléments O(n)
Int Min(int*T, intn)
{
int m=T[0]
for (int i=1; i<n; i++)
if (T(i)<m)
m=T(i)
return m;
} Techniques d'Optimisation 33
 Quelques exemples
• Recherche séquentielle (x, S, n)
i:=1
tant que ((i<n) et (S[i]x)) faire
i:=i+1
renvoyer (S[i]=x)
fin tant que
• Tri à bulle (fonction tri(S, n))
pour i:=n à 2 faire
pour j:=1 à i-1 faire
si (S[j] > S[j+1] alors
permuter S[j] et S[j+1] dans S
finsi
fin pour
fin pour Techniques d'Optimisation 34
 Classification de problèmes (1/2)
• On distingue deux classes de problèmes:
– Classe P: Tous les problèmes résolus par des
algorithmes dont la complexité est polynomiale
O(p(n)) où p(n) est un polynôme de degré n (n1).
– Classe NP: Tous les problèmes dont on ne connait
pas d’algorithme de complexité polynomiale et
qui une instance de ce problème est vérifiable
polynomialement.
• La classe NP contient la classe P et la classe NP
complet.
Techniques d'Optimisation
35
 Classification de problèmes (2/2)
• On dit qu’un problème d’existence A de la classe NP est NP
complet si tous les autres problèmes de NP sont
polynomialement transformables en A
• Conjecture P  NP.
• Théorème de COOK: Le problème de satisfiabilité SAT est NP-
complet
• Le problème SAT est très important en théorie de la
complexité et a de nombreuses applications:
• Planification classique
• Model Checking
• Diagnostic
• Configuration d'un ordinateur ou de son  système d’exploitation

Techniques d'Optimisation
36
 Problème de satisfiabilité SAT (1/2)
• Soient x1, …, xn n variables booléennes. Un littéral est soit une
variable, soit la négation d’une variable. (x1, x2 sont des
littéraux
• Une clause est une disjonction de littéraux (littéraux reliés par
le connecteur OU). (C= x1  x2  x3 est une clause)
• La longueur d’une clause correspond au nombre de ses
littéraux. La clause C est de longueur 3.
• Une forme normale conjonctive F est une formule logique
sous forme d’une conjonction de clauses.
– Exemple: F = (x1  x2  x3 )  (x1  x4)  (x2 x3 x4)

•  F est satisfaisable s'il est possible d’affecter une valeur

logique booléenne à chacune de ses variables de telle
manière que cette formule soit vraie.
Techniques d'Optimisation
37
 Problème de satisfiabilité SAT (2/2)
• Le problème k-SAT correspond au cas particulier du problème
SAT dans le cas où les clauses ont toutes une même longueur
fixée égale à k.
• Le 3-SAT est le problème SAT avec des clauses toutes de
longueur 3.
• Le problème SAT est NP-complet.
• k-SAT est NP-complet pour k  3.
• 2-SAT, Horn-SAT sont polynomiaux.
• max-SAT et max-SAT pondéré sont NP-difficiles

Techniques d'Optimisation
38