Optimisation combinatoire

• Introduction : Optimisation continue/combinatoire

• Notion de complexité
• Méthodes exactes
• Méthodes approchées (métaheuristiques, heuristiques)
• Problèmes classes de l’optimisation combinatoire
• Logiciel d’optimisation Cplex

SCM1
ENSATé 2023-2024
Pr DKHISSI Btissam
19/02/2024 Optimisation combinatoire 1
 Optimisation combinatoire

INTRODUCTION

19/02/2024 Optimisation combinatoire 2

L’optimisation

L’optimisation est une discipline mathématique qui, a pleinement pris son essor au cours
du XXe siècle d’une part sous la stimulation du développement des sciences de l’industrie
et de la planification, l’économie, la gestion, etc..., et des sciences appliquées aux
technologies naissantes, comme l’automatique, le traitement du signal, etc..., et d’autre
part grâce au développement de l’informatique qui a rendu efficiente ses méthodes
algorithmiques.

discipline fondamentale dans les sciences de l’ingénieur, de l’économie et de la gestion.

L’optimisation, intervient pour appliquer l’outil mathématique pour la formalisation

mathématique et la résolution.

19/02/2024 Optimisation combinatoire 3

 L’optimisation

Si D est discret (D ⊂ Zn, fini ou dénombrable), on parle d’optimisation combinatoire. Les

outils proviennent essentiellement des mathématiques discrètes (théorie des graphes).

Si D est continu, et f est continue, on parle d’optimisation continue. Les outils proviennent
essentiellement de l’analyse (calcul différentiel, convexité) et de l’algèbre linéaire.

Optimisation mixte: variables discrètes et variables continues.

19/02/2024 Optimisation combinatoire 4

Qu'est-ce-que l'optimisation combinatoire ?

• Jusqu'au 19e siècle, on s'intéressait aux Problèmes d'existence. On répondait à la

question : existe-t-il un objet ayant certaines propriétés ?

• Ensuite, on a résolu des Problèmes de dénombrement (Analyse combinatoire).

On répondait à la question : combien y a-t-il d'objets ayant certaines propriétés ?

• Enfin avec l'informatique, on traite des Problèmes combinatoires. On cherche à

déterminer un objet ayant certaines propriétés, en définissant un algorithme
calculant un coût.

19/02/2024 Optimisation combinatoire 5

 Optimisation: Terminologie

• L’ensemble D de solutions réalisables: c’est l’espace de recherche (domaine

réalisable).

• A chaque solution est associé un réel, sa qualité, calculable par une

fonction qualité / objectif / coût / ”fitness”

• On cherche la solution de meilleure qualité, appelée optimum global.

• Optimisation Multi-citères / multi-objectifs : on veut optimiser plusieurs

fonctions objectif en même temps.

19/02/2024 Optimisation combinatoire 6

 Optimisation: définitions

• Optimum globale :

x  tel que x  Ω, f(x  )  f(x)

• Optimum local :
x  tel que  x  Ω  , f(x  )  f(x)

19/02/2024 Optimisation combinatoire 7

 Exemples de problèmes combinatoires
• Problème du plus court chemin
• Problème du voyageur de commerce
• Problème de tournées de véhicules
• Problème d'affectation généralisées
• Problème de sac à dos
• Problème de bin-packing
• Problème de partition : Etant donné N nombres a1, a2, ......,an, est-il possible de
partitionner ces N nombres en deux sous-ensembles de même poids ?
Exemple : Pour l'ensemble {8, 6, 15, 37, 42 ,4},
la réponse est oui car 8 + 6 + 42 = 15 + 37+ 4 = 56.
• Problème de recouvrement
• Problème d’ordonnancement
• …

19/02/2024 Optimisation combinatoire 8

 Optimisation: Complexité

Complexité d’algorithme:

• Complexité d’un algorithme : relation entre le temps de calcul (complexité

en temps) ou la mémoire occupée (complexité en espace) et la taille des
données traitées.

• On exprime la relation par une fonction : temps = fct(taille).

Taux de croissance de cette fonction au pire cas.

Notations:
• n : taille des données (taille de l’instance)
• T(n) : nombre d’opérations élémentaires

19/02/2024 Optimisation combinatoire 9

 Optimisation: Complexité
Complexité d’algorithme: Notation de Landau ( f (n))

( f (n)) Décrit le comportement asymptotique quand n → ∞

T (n) = ( f (n)) si c n 0 tels que n  n0 , T (n)  c  f (n)

On dit que T est dominée asymptotiquement par f

19/02/2024 Optimisation combinatoire 10
 Optimisation: Complexité
Classes de complexité:

• O(1) : temps constant (pas d’augmentation du temps d’exécution quand n croit)

• O(log n) : logarithmique (augmentation très faible du temps d’exécution quand n

croit La dichotomie)

• O(n) : linéaire (augmentation linéaire du temps d’exécution quand n croit

Le parcours séquentiel des structures linéaires)
• O(n × log n) : quasi-linéaire(augmentation un peu supérieure à O(n) tris par
échanges)
• O(n2) : quadratique, polynomial (quand le paramètre n double le temps est
multipliè par 22)
• O(2n) : exponentiel (problèmes très difficiles)

19/02/2024 Optimisation combinatoire 11

Simulation du temps de calcul

19/02/2024 Optimisation combinatoire 12

 Optimisation: définitions
Principales Classes de complexité en OC:

Fonction T(n) selon le

taux d’accroissement

Fonction Polynômiale
Il existe un polynôme qui la borne n  IN , b  IN , c  IR tels que T(n)  c.n b
supérieurement

Fonction Exponentielle
Sa croissance suit une progression T(n)  c.e b.n
géométrique

19/02/2024 Optimisation combinatoire 13

Complexité d’un problème

La « complexité d’un problème » est une estimation du nombre d’instructions à exécuter pour
résoudre les instances de ce problème, cette estimation étant un ordre de grandeur par rapport à la
taille de l’instance. Il s’agit là d’une estimation dans le pire des cas dans le sens où la complexité
d’un problème est définie en considérant son instance la plus difficile.

19/02/2024 Optimisation combinatoire 14

 Les problèmes Polynomiaux

La classe P contient l’ensemble des problèmes polynomiaux, i.e., pouvant être

résolus par un algorithme de complexité polynomiale. Cette classe caractérise
l’ensemble des problèmes que l’on peut résoudre «efficacement ».

19/02/2024 Optimisation combinatoire 15

 Les problèmes Polynomiaux Non déterministes NP

la classe NP (Non deterministic Polynomial) contient l’ensemble des problèmes

polynomiaux non déterministes, i.e., pouvant être résolus par un algorithme de
complexité polynomiale pour une machine non déterministe (que l’on peut voir
comme une machine capable d’exécuter en parallèle un nombre fini d’alternatives).
Intuitivement, cela signifie que la résolution des problèmes de NP peut nécessiter
l’examen d’un grand nombre (éventuellement exponentiel) de cas, mais que l’examen
de chaque cas doit pouvoir être fait en temps polynomial.

On ne trouve pas d’algorithme polynomial pour les résoudre avec une machine
déterministe.

Remarque:
les calculs d'une machine de Turing déterministe forment une suite, ceux d'une
machine de Turing non déterministe forment un arbre, dans lequel chaque chemin
correspond à une suite de calculs possibles.

19/02/2024 Optimisation combinatoire 16

 Les problèmes Polynomiaux Non déterministes

• la classe des problèmes NP-complets : un problème de NP est NP-complet s’il

est au moins aussi difficile à résoudre que n’importe quel autre problème de
NP.
Ainsi, les problèmes NP-complets sont des problèmes combinatoires dans le
sens où leur résolution implique l’examen d’un nombre exponentiel de cas.
Cette classe des problèmes NP-complets contient un très grand nombre de
problèmes (TSP).

Exemple:
Dans le cas du problème du voyageur de commerce, l’espace de recherche croit
en (n-1)!, où n est le nombre de villes à visiter, ce qui dépasse rapidement les
capacités de calcul de n’importe quel ordinateur.
Avec seulement 50 villes, il faudra évaluer 49! trajets.
C’est l’explosion combinatoire.

19/02/2024 Optimisation combinatoire 17

 Exemple de calcul de la complexité Algorithmique

Début

K <-- 0

I <-- 1

( opérations1)

TantQue I <= N ( opérations2) Faire

R <-- R+T[I] ( opérations3)

I <-- I+1 ( opérations4)

FinTantQue

fin

Le temps d’exécution t(n) de cet algorithme en supposant que:

- N=n

- t1 est le temps d’éxécution des affectations ( opérations1)

- t2 est le temps d’éxécution de la comparaison ( opérations2)

- t3 est le temps d’éxécution de l’action ( opérations3)

- t4 est le temps d’éxécution de l’action ( opérations4)

- t1, t2, t3, t4 sont des constantes (c.à.d. ne dépendent pas de n)

s’écrit:
n
T(n) = t1 +  (t2 + t3 + t 4) + t2
i =1

19/02/2024 Optimisation combinatoire 18

 Exemple de calcul de la complexité Algorithmique

Recherche séquentielle dans un tableau

fonction avec retour booléen rechercheElement(chaine[] tab, chaine x)

entier i;
début
i 0; (1 opération)
tantque (i < tab.longueur (1 opération)) faire
si (tab[i] = x) alors (1 opération)
retourne VRAI;
finsi n fois
sinon
i++; (1 opération)
Fin tantque
retourne FAUX;
Fin

Algorithme linéaire en О(n)

Le coût des déclarations et du retour est négligeable

19/02/2024 Optimisation combinatoire 19
 Exemple de calcul de la complexité Algorithmique
tri-selection
début
pour i = 0 à n-2 faire
j=i; (1 opération)
pour k = i+1 à n-1 faire
si A[k] < A[j] alors (1 opération)
j=k; (1 opération) (n-i-1) fois Pour chaque i
finsi ; (1+2(n-i-1)+3) opérations
finpour;
Permuter (A[i] , A[j]) ; (3 opérations)
finpour;
fin
Nombre d’opérations : 4(n-1)+ 2 n −2 (n − i − 1) = 4(n − 1) + 2 n−1 i =4(n − 1) + n(n − 1) = n 2 + 3n − 4

i =0

i =1

Algorithme polynomial en О(n2)

19/02/2024 Optimisation combinatoire 20

 Exemple de calcul de la complexité Algorithmique
Recherche Dichotomique:

int rechercheDicho(int x, int tab[], int lg)

{
Debut
int fin = lg-1;
int milieu = (debut+fin)/2;
while(debut<=fin)
if (x == tab[milieu])
return milieu;
else if (x < tab[milieu])
{
fin = milieu-1; /* cherche à gauche... */
milieu = (debut+fin)/2;
}
else{ debut = milieu+1; /* x > tab[milieu] */
milieu = (debut+fin)/2; /* ... `a droite */
}
return -1; /* si on n’a rien trouvé dans le while */
}
19/02/2024 Optimisation combinatoire 21
Méthode exactes
Méthodes approchées
• Métaheuristiques
• Heuristiques

19/02/2024 Optimisation combinatoire 22

 Optimisation combinatoire

L’objectif de l’optimisation combinatoire est d’avoir un

comportement «acceptable » en pratique pour les problèmes de
recherche opérationnelle, c’est à dire, d’être capable de trouver
une solution de qualité suffisante en un temps raisonnable pour
les instances à résoudre.

19/02/2024 Optimisation combinatoire 23

Méthodes de résolution des problèmes d’optimisation combinatoire

• Les méthodes exactes qui garantissent la complétude de la résolution : c'est le cas par exemple
de SEP (séparation & évaluation progressive). Le temps de calcul nécessaire d'une telle méthode
augmente en général exponentiellement avec la taille du problème à résoudre.

• Les méthodes approchées ont l’objectif de trouver une solution de bonne qualité en un temps de
calcul raisonnable sans garantir l'optimalité de la solution obtenue. Les méthodes approchées
sont fondées principalement sur diverses heuristiques, souvent spécifiques à un type de
problème ou métaheuristiques générales.

19/02/2024 Optimisation combinatoire 24

 Méthodes d’optimisation
combinatoire

Algorithmes Méthodes
exactes approchées

Programmation Séparation et Recherche Algorithmes

linéaire évaluation locale gloutons

Recherche Recuit
Tabou simulé
Programmation Métaheuristiques
Relaxation
dynamique
Colonie de Algorithme
fourmis génétique

19/02/2024 Optimisation combinatoire 25

 Optimisation combinatoire
Algorithme glouton
Un algorithme glouton est un algorithme qui suit le principe de faire,
étape par étape, un choix optimum local, dans l'espoir d'obtenir un
résultat optimum global. Dans les cas ou l'algorithme ne fournit pas
systématiquement la solution optimale, il est appelé une heuristique
gloutonne.

19/02/2024 Optimisation combinatoire 26

 Optimisation combinatoire
Heuristique:

En optimisation combinatoire, théorie des graphes et théorie de la complexité,

une heuristique est un algorithme qui fournit rapidement (en temps polynomial)
une solution réalisable, mais pas nécessairement optimale, pour un problème
d'optimisation difficile.
Une heuristique, ou méthode approximative, est donc le contraire d'un
algorithme exact qui trouve une solution optimale pour un problème donné.
L'usage d'une heuristique est pertinente pour calculer une solution approchée
d'un problème et ainsi accélérer le processus de résolution exacte.

19/02/2024 Optimisation combinatoire 27

 Optimisation combinatoire

Métaheuristiques:
• Les métaheuristiques forment une famille d'algorithmes d'optimisation
visant à résoudre des problèmes d'optimisation difficile (souvent issus des
domaines de la recherche opérationnelle, de l'ingénierie ou de
l'intelligence artificielle) pour lesquels on ne connait pas de méthode
classique plus efficace.
Ces méthodes utilisent un haut niveau d'abstraction, leur permettant
d‘être adaptées a une large gamme de problèmes différents.

• Les métaheuristiques sont généralement des algorithmes stochastiques

itératifs, qui progressent vers un optimum global.

19/02/2024 Optimisation combinatoire 28

 Optimisation combinatoire

Définitions:
• Un voisinage d'une solution est un sous-ensemble de solutions qu'il est
possible d'atteindre par une série de transformations données.

• L'intensification (exploitation) se fonde sur l'idée d'apprentissage de

propriétés favorables: les propriétés communes souvent rencontrées dans les
meilleures solutions visitées sont mémorisées au cours de la recherche, puis
favorisées pendant la période d'intensification. Une autre manière d'appliquer
l'intensification consiste à mémoriser une liste de solutions de bonne qualité et à
retourner vers une de ces solutions. Il s’agit alors d’intensifier l’effort de
recherche vers les zones les plus « prometteuses » de l’espace des solutions.

• La diversification (exploration) cherche à diriger la recherche vers des zones

inexplorées. Sa mise en œuvre consiste souvent à pénaliser les mouvements
ayant été souvent répétés. Il s’agit alors de diversifier l’effort de recherche de
façon à être capable de découvrir de nouvelles zones contenant
(potentiellement) de meilleures solutions.

19/02/2024 Optimisation combinatoire 29

 Optimisation combinatoire

Méthodes hybrides:
Méthode composée de plusieurs méthodes se répartissant les tâches de recherche.

19/02/2024 Optimisation combinatoire 30

 Optimisation combinatoire

Méthodes exactes
1- Séparation et évaluation (Branch & Bound)
Programmation linéaire en nombres entiers (PLNE)

19/02/2024 Optimisation combinatoire 31

 Exemple

Soit le PLNE suivant:

Max z (x1 , x 2 ) = x1 + 2 x2
SC
2 x1 + x2  4
2 x1 − 3x2  0
x1 , x2  IN

Quelle est la solution optimale continue du PLNE ?

Donner la solution arrondie
La solution arrondie est elle une solution réalisable
Trouver la solution optimale entière du PLNE

19/02/2024 Optimisation combinatoire 32

Exemple 2
Max (x1+x2)
SC: x1+3x2≤15
4x1-x2≤ 8
2x1+x2≤ 9
x1,x2≥0 entiers

• Quelle est la solution optimale continue du PLNE ?

• Donner la solution arrondie
• La solution arrondie est elle une solution réalisable?
• Borner l’écart qui sépare la valeur de la solution arrondie de celle de
la solution optimale du PLNE.

19/02/2024 Optimisation combinatoire 33

Procédures par Séparation et Evaluation-Branch and Bound- (Méthodes
arborescentes)

Ces procédures permettent de déterminer par énumération

implicite, des solutions réalisables d’un problème et celle qui
optimise la fonction objectif

19/02/2024 Optimisation combinatoire 34

L’exploration des solutions réalisables du problème étudié repose sur deux principes:

• Un principe de séparation qui permet de réduire l’étude de X (l’ensemble de solutions réalisables)

à celle de sous ensembles de X de plus en plus réduit en vue d’aboutir à des problèmes simples
(Exemple: un ensemble ne contenant plus qu’un seul élément)
consiste le plus souvent en une répartition

• Un principe d’évaluation : Pour chaque sous-ensemble de X obtenue par séparation, ce principe

consiste à définir une évaluation de la fonction objectif de la valeur des solutions de ce sous
ensemble.
Déterminer une borne inférieure de la solution d’un sous-ensemble.

19/02/2024 Optimisation combinatoire 35

Le processus d’exploration des solutions est représenté par une arborescence

Rappel :
Une arborescence est un graphe qui possède un sommet particulier, la racine r telle que: tout
sommet x est relié à la racine r par un chemin et un seul allant de r à x.

19/02/2024 Optimisation combinatoire 36

La racine de l’arborescence l’ensemble des solutions réalisables du
problème
Les autres sommets les sous-ensembles de X, crées successivement
par séparation
E est séparé en E1 et E2
E= E1 E2
E

E1 E2

E3 E4 E6
E5

19/02/2024 Optimisation combinatoire 37

Exemple 1: problème de sac à dos

Max z = 15 x1 + 18 x 2 + 4 x3 + 7 x 4 + 2 x5 + x6
SC
3 x1 + 4 x 2 + x3 + 3 x 4 + x5 + x6  5
xi  0,1, 1  i  6

19/02/2024 Optimisation combinatoire 38

 Exemple 1: problème de sac à dos
Max z(x 1 , x 2 ) = 15 x1 + 18 x 2 + 4 x3 + 7 x 4 + 2 x5 + x6

SC E
3 x1 + 4 x 2 + x3 + 3 x 4 + x5 + x6  5
X1=0 X1=1

xi  0,1, 1  i  6
E1 E2
3x1 + 4 x 2 + x3 + 3x 4 + x5 + x6  5
X2=0 X2=1 X2=0 Pas de
X2=1
solution
E3 E4 E5 E6
X3=0 X3=1
X3=0 X3=1 . .
E7 E8 . .
E9 E10 . .

. . .
. . .
19/02/2024
. . .
Optimisation combinatoire 39
 Exemple 1: problème de sac à dos

Soit S0 est la borne supérieure de la solution optimale obtenue en relâchant les

contraintes d’intégrité (en remplaçant les contraintes : xi {0,1} par les contraintes
xi [0,1] )  

x1=1, x2=1/2, x3=x4=x5=x6=0 S0=24 l’ensemble des

E solutions réalisables
Z=24
X2=0 X2=1

E1 E2

Max z = 15 x1 + 4 x3 + 7 x 4 + 2 x5 + x 6 Max z = 15 x1 + 4 x3 + 7 x 4 + 2 x5 + x 6
SC
. SC .
3x + x + 3x + x + .x 5 3x + x + 3x + x . + x
1 3 4 5 6 1
1 3 4 5 6

x  0,1, 1  i  6 x  0,1, 1  i  6
i
. i
.

19/02/2024 Optimisation combinatoire 40

 Exemple 1: problème de sac à dos

S0=24 l’ensemble des

E solutions réalisables

X2=0 X2=1
S1=21 S2=23
E1 E2

Max z = 15 x1 + 4 x3 + 7 x 4 + 2 x5 + x 6 Max z = 15 x1 + 4 x3 + 7 x 4 + 2 x5 + x 6
SC
. SC .
3x + x + . 3x + x + x 5 3 x .+ x + 3 x + x + x
1 3 4 5 6 1
1 3 4 5 6

x  0,1, 1  i  6 x  0,1, 1  i  6
i
. i
.

x1=1, x2=0, x3=1, x4=1/3, x5=x6=0 x1=1/3, x2=1, x3=x4=x5=x6=0

Z=21 Z=23

19/02/2024 Optimisation combinatoire 41

 Exemple 1: problème de sac à dos
Traitement en priorité de l’ensemble ayant la meilleure évaluation

Max z = 15 x1 + 18 x 2 + 4 x3 + 7 x 4 + 2 x5 + x6
SC
3 x1 + 4 x 2 + x3 + 3 x 4 + x5 + x6  5
xi  0,1, 1  i  6
S0=24 l’ensemble des
E solutions réalisables

X2=0 X2=1
S1=21 S2=23
E1 E2

X1=1 X1=0
S2=22
E3 E4
Pas de Max z = 4 x3 + 7 x 4 + 2 x5 + x 6
solution SC
x3 + 3 x 4 + x5 + x 6  1
xi  0,1, 1  i  6

x1=0, x2=1, x3=1, x4=x5=x6=0

19/02/2024 Optimisation combinatoire Z=22 42
 Exemple 2
Exemple 1: problème de sac à dos
Traitement en priorité de l’ensemble ayant la meilleure évaluation

S0=24 l’ensemble des

E solutions réalisables

X2=0 X2=1
S1=21 S2=23
E1 E2
X1=0
S2=22
E4

x1=0, x2=1, x3=1, x4=x5=x6=0

Solution réalisable entière

au problème
19/02/2024 Optimisation combinatoire 43
 Exemple 2
Traitement en priorité de l’ensemble ayant la meilleure évaluation
S0=24 l’ensemble des
E solutions réalisables

X2=0 X2=1
S1=21 S2=23
E1 E2
X1=0
Ensemble des solutions moins S4=22
intéressantes que celles E4
contenues dans E4 car S1=21
x1=0, x2=1, x3=1, x4=x5=x6=0

Solution optimale du
problème
L
L’algorithme s’arrête

19/02/2024 Optimisation combinatoire 44

 Exemple2

Max z (x 1 , x 2 ) = 3x1 + 8 x 2
SC
x1 + 4 x 2  20
x1 + 2 x 2  11
3x1 + 2 x 2  22
x1 , x 2  IN

19/02/2024 Optimisation combinatoire 45

 Exemple2
Max z (x 1 , x 2 ) = 3x1 + 8 x 2
SC
x1 + 4 x 2  20 X1=2, x2=9/2 (solution optimale continue)
x1 + 2 x 2  11
3x1 + 2 x 2  22
x1 , x 2  IN

E0
S0=41

(2,9/2) est la solution optimale unique du programme et de coût z= 42

Toute autre solution du programme aura un coût strictement inférieure à 42

19/02/2024 Optimisation combinatoire 46

 Exemple2
Max z (x 1 , x 2 ) = 3x1 + 8 x 2
SC
x1 + 4 x 2  20
x1 + 2 x 2  11
3x1 + 2 x 2  22
x1 , x 2  IN

E0
S0=41

X2≥5 X2≤4

E1 E2

Max z (x 1 , x 2 ) = 3 x1 + 8 x 2 Max z (x 1 , x 2 ) = 3 x1 + 8 x 2
SC SC
x1 + 4 x 2  20 x1 + 4 x 2  20
x1 + 2 x 2  11 x1 + 2 x 2  11
3 x1 + 2 x 2  22 3 x1 + 2 x 2  22
x2  5 x2  4
19/02/2024 x1 , x 2  IN Optimisation combinatoire x1 , x 2  IN 47
 Exemple2
Max z (x 1 , x 2 ) = 3x1 + 8 x 2
SC
x1 + 4 x 2  20
x1 + 2 x 2  11
3x1 + 2 x 2  22
x1 , x 2  IN

E0
S0=41

X2≥5 X2≤4

E1 E2

X1=0, x2=5 (solution optimale continue) X1=3, x2=4 (solution optimale continue)
Son coût est : 40 Son coût est : 41
Solution entière Solution entière

19/02/2024 Optimisation combinatoire 48

 Exemple2
Max z (x 1 , x 2 ) = 3x1 + 8 x 2
SC
x1 + 4 x 2  20
x1 + 2 x 2  11
3x1 + 2 x 2  22
x1 , x 2  IN

E0
S0=41

X2≤4

E2
x1=3, x2=4 (solution optimale entière)
Son coût est : 41

19/02/2024 Optimisation combinatoire 49

 Exemple3

Max z = 9 x1 + 5 x 2 + 6 x3 + 4 x 4
SC
6 x1 + 3x 2 + 5 x3 + 2 x 4  10
x3 + x 4  1
- x1 + x3  0
- x2 + x4  0
x1 , x 2 , x3 , x 4  0,1

19/02/2024 Optimisation combinatoire 50

 Exemple3
x1=5/6, x2=1 x3=0, x4=1 Z=16,5
(solution optimale continue)

E0
S0=16

X1=0 X1=1

E1 E2
S1=9 S2=16
x1=0, x2=1 x3=0, x4=1 Z=9 x1=1, x2=4/5 x3=0, x4=4/5 Z=16,2
(solution optimale entière) (solution optimale continue)

9 ≤ Z* ≤ 16

19/02/2024 Optimisation combinatoire 51

 Exemple3
x1=5/6, x2=1 x3=0, x4=1 Z=16,5
(solution optimale continue)

E0
S0=16

X1=0 X1=1

E1 E2 x1=1, x2=4/5 x3=0,

S1=9 x4=4/5 Z=16,2
S2=16
x1=0, x2=1 x3=0, x4=1 Z=9
(solution optimale entière) X2=0 X2=1

E3 E4
S1=13 S2=16
x1=1, x2=0 x3=4/5, x4=0 Z=13.8 x1=1, x2=1, x3=0, x4=1/2 Z=16

19/02/2024 Optimisation combinatoire 52

 Exemple3
x1=5/6, x2=1 x3=0, x4=1 Z=16,5
(solution optimale continue)
E0
S0=16
X1=0 X1=1

E1 E2 x1=1, x2=4/5
S1=9 S2=16 x3=0, x4=4/5
Z=16,2
x1=0, x2=1 x3=0, x4=1 Z=9
X2=0 X2=1
(solution optimale entière)

E3 E4
S1=13 S2=16
x1=1, x2=0 x3=4/5, x4=0 x1=1, x2=1, x3=0, x4=1/2
Z=13.8 Z=16
X4=0 X4=1

E5 E6
S1=14 S2=16
x1=1, x2=1 x3=0, x4=0 Z=14 Pas de solutions réalisables
x1=1, x2=1 x3=0, x4=0 Z=14
solution optimale entière
19/02/2024 Optimisation combinatoire 53
 Procédures par Séparation et Evaluation-Branch and Bound-
(Dans le cas de Minimisation)

Exemple

Min z (x 1 , x 2 ) = 2 x1 + 3x 2
SC
x1 + 3x 2  5
2 x1 + x 2  6
x1 , x 2  IN

19/02/2024 Optimisation combinatoire 54

 Procédures par Séparation et Evaluation-Branch and Bound-
(Dans le cas de Minimisation)
Min z (x 1 , x 2 ) = 2 x1 + 3 x 2
X1=2.6
SC X2=4/5
x1 + 3 x 2  5 Z*= 7,6 (solution optimale continue)
2 x1 + x 2  6
x1 , x 2  IN
E0
S0=8

X1≤2 X1≥3

E1 E2
S1=10 S2=8

x1=2, x2=2 (solution optimale entière) x1=3, x2=2/3 (solution non entière)
Son coût est : 10 Son coût est : 8

19/02/2024 Optimisation combinatoire 55

 Procédures par Séparation et Evaluation-Branch and Bound-
(Dans le cas de Minimisation)
Min z (x 1 , x 2 ) = 2 x1 + 3 x 2
SC E0
x1 + 3 x 2  5
S0=8
2 x1 + x 2  6
x1 , x 2  IN

X1≤2 X1≥3

E1 E2
x1=3, x2=2/3 Z=8
S1=10 S2=8

x1=2, x2=2 Z=10 X2≤0 X2≥1

E3 E4
S3=10 S4=9
x1=3, x2=1, Z=9
x1=5, x2=0, Z=10 Solution optimale
Remarque:
X1=3 , X2=1, Z*= 9 (solution arrondie) De la solution optimale continue X1=2.6 , X2=4/5 de coût
Z*= 7,6
19/02/2024 Optimisation combinatoire 56