Chapitre 3 Méthodes exactes de résolution des problèmes ... · Elles peuvent pallier le manque d'algorithmes polynomiaux pour des problèmes de taille moyenne. Pour des problèmes

UNIVERSIT

E SAAD DAHLAB D

E BLIDA

Chapitre 3 : Méthodes exactes de résolution des problèmes combinatoires NP-difficiles.

Chapitre 3

Méthodes exactes de résolution des problèmes combinatoires NP-difficiles

1. Introduction aux méthodes par séparation et évaluation

Les méthodes arborescentes (Branch and Bound Methods) sont des méthodes exactes

d'optimisation qui pratiquent une énumération intelligente de l'espace des solutions. Il s'agit

d'énumération complètes améliorées. Elles partagent l'espace des solutions en sous ensembles

de plus en plus petits, la plupart étant éliminés par des calculs de bornes avant d'être construits

explicitement. Appliquées à des problèmes NP-difficiles, ces méthodes restent bien sur

exponentielles, mais leur complexité en moyenne est bien plus faible que pour une

énumération complète. Elles peuvent pallier le manque d'algorithmes polynomiaux pour des

problèmes de taille moyenne. Pour des problèmes difficiles de grande taille, leur durée

d'exécution est très grande et il faut se retourner vers des heuristiques ou solutions

approchées.

Pour un POC, on peut inventer plusieurs méthodes arborescentes. Cependant elles auront trois

composantes communes : • Une règle de séparation de l'ensemble des solutions

• une fonction d'évaluation des ensembles de solutions

• une stratégie d'exploration

Le premier exemple développé de procédure par séparation est l'algorithme proposé en 1960

par LAND et DOIG pour les programmes mixtes.

En 1963, Little et al. utilisent une PS pour résoudre le problème du voyageur de commerce et

eut un grand retentissement. Il sera exposé dans la suite, dans le paragraphe des exemples.

On explore l'ensemble des solutions réalisables Ω en de sous ensembles de plus en plus petits

de façon à isoler une solution optimale dans l'un de ses sous ensembles.

Pour représenter cette exploration, on construit une arborescence dont le sommet de base

correspond à l'ensemble Ω et dont les autres sommets correspondent à des sous ensembles de

Ω. Pour définir l'exploration, nous devons définir une règle de séparation et une règle pour se

déplacer dans l'arborescence. Il faut définir pour chaque sous ensemble, un minorant appelé

" évaluation par défaut". Cela impose de savoir calculer rapidement une " bonne" évaluation

par défaut. Une itération consiste à choisir une feuille de l'arborescence, nœuds ou sommets

non encore séparés. Quand un sommet ne peut fournir de meilleurs solutions, il est dit tué ou

élagué. La recherche se termine quand tous les nœuds ont été tués. Les sommets sont

numérotés dans l'ordre de leur création.

UNIVERSIT

E SAAD DAHLAB D

E BLIDA

28

Toute technique de séparation est valable, à condition qu'aucune solution ne soit perdue.

La fonction d'évaluation empêche en pratique que l'arborescence soit construite en entier.

2. Principe des méthodes par séparation et évaluation

Soit ( S, f ) la donnée d'un POC.

Définitions 1 :

- On dit qu'on sait évaluer le sous ensemble S'⊂ S, si on sait déterminer un réel g(S') tel que

g(S') ≤ f(s) ∀s ∈ S' ( respectivement g(S') ≥ f(s) ∀s ∈ S' ).

- Une évaluation g(S') de S' est dite exacte s'il existe s0∈S' tel que g(S') = f(s0).

- Une évaluation h(S') de S' est dite meilleure qu'une évaluation g(S') de S' si h(S') > g(S')

( resp. h(S') < g(S')).

- Si g(S') est une évaluation exacte, il ne peut exister une évaluation meilleure.

Définition 2 : Un sous ensemble S'⊂ S, ensemble de solutions d'un POC est dit " stérile " si

on connaît une solution s0∈ S tel que f(s0) ≤ g(S') ( resp. f(s0) ≥ g(S') )

S'⊂ S peut être stérilisé dans deux cas,

• On est sur que S' ne peut contenir de solutions optimales ( S' = ∅ ou ∃ s0 ∈ S, f(s0) < g(S'))

•on dispose d'une évaluation exacte de S'.

Définition 3 :

Un sous ensemble S'⊂ S est dit "séparé" en S'1 , S'2,…, S'k si S' = S'1 ∪ S'2 ∪…∪ S'k

avec S'i ⊂ S' ∀ i = 1, …, k.

La séparation n'est pas propre si et seulement si ∃ k / S'k = ∅

Théorème 1 : Soit S = UF'S'S

∈alors si tous les éléments de la famille F sont stériles on a soit :

• Aucun ensemble S' n'a une évaluation exacte et S = ∅,

• la meilleure évaluation exacte des ensembles S' correspond à une solution optimale.

Module: Procédures PSE, PLNE, programmation dynamique et Métaheuristiques, dispensé par le Dr. DERBALA Ali.

UNIVERSIT

E SAAD DAHLAB D

E BLIDA

Chapitre 3 : Méthodes exactes de résolution des problèmes combinatoires NP-difficiles. 29

P. Bertier et B. Roy ont donné en 1964 une première axiomatique des procédures par

séparation applicable à des problèmes combinatoires.

3. Schéma général des méthodes par séparation et évaluation dites SE

s désignera la meilleure solution connue (non forcément optimale) et v = f( s ).

Si s est encore indéterminée on posera v = + ∞ ( resp. pour le max on pose v = - ∞ )

F une famille de sous-ensembles de S recouvrant S.

3.1. Procédure d'initialisation

Si on ne connaît pas de solution réalisable s , indéterminée et v = + ∞. La famille F contient

l'unique élément S. S est déclaré non stérile. Aller à la procédure de choix.

3.2. Procédure de choix

a) si tous les éléments de F sont stériles, s est solution optimale. Si s est indéterminée, le

problème posé n'a pas de solutions et S = ∅.

b) Sinon choisir S' ∈F, non stérile.

b1) si S' n'a pas été évalué, aller à la procédure évaluation 3.

b2) si S' a été évalué, aller à la procédure séparation 4.

3.3. Procédure d'évaluation

Calculer g(S') l'évaluation de S.

a) si g(S') ≥ v alors S' est déclaré stérile. Aller à la procédure choix 2.

b) Si g(S') < v et si l'évaluation est exacte ( g(S') = f(s'), s'∈ S' ) alors poser s = s' et v = g(S')

= f(s'). S' est déclaré stérile. Aller à la procédure choix 2.

c) Si on n'est pas dans le cas a) ou b) aller à la procédure de choix 2.

3.4. Procédure de séparation

Séparer S' en créant les sous-ensemble S'1 , S'2,…, S'k où S' = S'1 ∪ S'2 ∪…∪ S'k.

Les S'i ne sont pas déclarés stériles. Posons F = ( F \ S') ∪ S'1, S'2,…, S'k et aller à la

procédure du choix 2.

UNIVERSIT

E SAAD DAHLAB D

E BLIDA

30

Remarques :

Dans le cas général, l'algorithme de ce schéma est fini si S'i ⊂ S', ∀ i = 1, …, k.

Les stratégies possibles pour la procédure du choix 2 sont les suivantes,

a) sélectionner S' dont l'évaluation est la plus faible ( resp. la plus grande ).

b) Sélectionner S' le plus récemment crée, cette manière de faire correspond à une

exploration dite " profondeur d'abord ". La famille F fonctionne comme une pile, le

dernier arrivé est le premier servi.

c) Sélectionner S' le plus anciennement crée, elle correspond à une exploration " largeur

d'abord ". F est géré comme une pile FIFO.

d) On pratique on combine a), b) et c).

Les deux méthodes d'exploration les plus employées sont : les procédures par séparation et

évaluation progressive. Elles séparent le sommet de l'arborescence d'évaluation minimale.

Cela revient à faire une exploration en " largeur d'abord". Elles sont en général assez lourdes

mais intéressantes, lorsque le problème est peu contraint et que l'on sait trouver de bonnes

solutions réalisables.

Les procédures par séparation et évaluation séquentielle. Elles séparent le sommet de

l'arborescence le plus proche du dernier sommet séparé. Cela revient à faire une exploration

en " profondeur d'abord" ( backtracking). Elles sont en général plus faciles à mettre en œuvre

et donc plus souvent utilisées.

4. Exemples d'application des PSE

Exemple 1. un problème d'ordonnancement à une seule machine

De nombreux problèmes d'ordonnancement classés NP-difficiles peuvent être résolus par des

procédures par séparation et évaluation. Nous présentons des problèmes d'ordonnancement à

une seule machine et un job shop.

Un atelier comporte une seule machine toujours disponible. "n " tâches doivent y être

exécutées les unes à la suite des autres. Elles sont toutes disponibles dès l'instant zéro. La

tâche i dure pi unités de temps et doit être terminée avant l'instant di, sinon il faut payer une

pénalité de retard wi par unité de temps de retard. Il s'agit de trouver le meilleur ordre de

passage des tâches sur la machine de manière à minimiser la somme des pénalités de retard à

payer.

Ensemble des solutions réalisables S0 est formé des n! permutations possibles des n tâches.

La séparation se fera sur la tâche que l'on fixe en dernier, puis en avant dernier, …


UNIVERSIT

E SAAD DAHLAB D

E BLIDA


Pour le calcul des bornes ou minorant, on prend en considération la somme des pénalités des

tâches placées en queue. L'élimination des sous ensembles se fera sur le sommet ayant le plus

petit minorant. Le problème suivant est à 1 machine et 3 tâches.

Tâche 1 Tâche 2 Tâche 3

pi

di

wi

2

3

4

4

5

2

1

5

3

Etape 0 : initialisation

≥ b0 = 0

≥ b1 = 8 ≥ b2 = 0 ≥ b3 = 3

≥ b4 = 4 ≥ b5 = 4

Fig 1. Schéma récapitulatifs des séparations.

On a séparé par rapport à une tâche placée en dernière position.

Pour calculer b1, quelque soit la séquence ( 2, 3, 1 ) ou ( 3, 2, 1), la tâche 1 ne peut

commencer son exécution qu'à la date p2 + p3 = 5. Elle sera en retard de 2 unités.

Le coût de retard sera d'au moins 2 x 4 = 8 d'où b1 = 8.

Ainsi de suite b2 = 0 car la tâche 2 ne sera pas en retard si elle est placée la dernière.

Si la tâche 3 est placée a dernière, elle sera en retard de 1 unité, b3 = 3 x 1 = 3.

On sépare par rapport au sommet de b2. On trouve que pour les séquences ( 1, 3, 2) ou

( 3, 1, 2 ) les pénalités sont respectivement de 4 unités.

S0

….. …. 1 ….. …. 3…... …. 2

….. 1 2….. 3 2

UNIVERSIT

E SAAD DAHLAB D

E BLIDA

32

Il faut encore séparer le sommet où la tâche 3 est placée la dernière. On trouve 2 sous

ensembles de coût 8 et 18. D'où (1,3,2) et (3,1,2) sont optimaux.

Exemple 2. Affectation

Un problème d'affectation est spécifié par la donnée d'une matrice D : n x n dont dij représente

le coût d'affectation du ième ouvrier à la jième tâche. Il s'agit de trouver une affectation de

chaque ouvrier à chaque tâche de coût total minimum.

Une manière d'énumérer sans répétition l'ensemble des affectations possibles est de

décomposer par étape.

A la première étape, on affecte l'ouvrier n°1 à l'une des n tâches

A la seconde étape, on affecte l'ouvrier n°2 à l'une des (n-1) tâches restantes.

…………….

A la nième étape, on affecte l'ouvrier n°n à la dernière tâche restante.

Il y a n! affectations possibles.

Soit la matrice des coûts d'affectation

TâchesOuvriers

a b c d

1 8 3 1 5

2 11 7 1 6

3 7 8 6 8

4 11 6 4 9

Etape 0 : Aucun ouvrier n'est affecté à aucune tâche

Au lieu d'énumérer toutes les affectations possibles qui sont au nombre de 4! = 24 et de

choisir celle de coût minimum, la procédure SEP permet d'éviter toute l'énumération.

Une observation de bon sens nous permet d'accélérer de manière importante la résolution de

cet exemple. Chaque tâche devant être affectée à un ouvrier, il en coûtera au moins 7 pour que

la tâche "a" soit assurée, au moins 3 pour que la tâche "b" le soit et au moins 1 et 5 pour que

les tâches "c" et "d" le soient respectivement. La somme des minimum de chaque colonne de

la matrice D, égale à 7 + 3 + 1 + 5 = 16, constitue un minorant du coût de toute affectation

réalisable. On ne peut trouver une affectation dont le coût soit égal à cette borne inférieure,

l'ouvrier 4 ne sera pas affecté.


UNIVERSIT

E SAAD DAHLAB D

E BLIDA


Etape 1 : l'ouvrier 1 est affecté à la tâche "a".

Séparons l'ensemble des 24 affectations possibles en distinguant suivant la tâche assignée à

l'ouvrier 1 et cherchons un minorant du coût des affectations dans chacun des quatre groupes

ainsi constitués.

Si l'ouvrier 1 effectue la tâche "a" cela coûte d11 = 8 et il faudra trouver une affectation de

coût minimum de l'ensemble des ouvriers 2, 3, 4 à l'ensemble des tâches b, c, d.

C'est un problème analogue au précédant avec une matrice

TâchesOuvriers

b c d

2 7 1 6

3 8 6 8

4 6 4 9

En prenant encore le minimum de chaque colonne on a un minorant de 6 + 1 + 6 = 13 pour

cette affectation de 3 x 3. Donc, toute affectation pour laquelle l'ouvrier 1 effectue la tâche "a"

aura un coût au moins égal à 13 + 8 = 21.

On calcule de la même manière les minorants des coûts des trois autres affectations.

Etape 0 : aucun ouvrier n'est affecté 16

Etape 1: l'ouvrier 1 est affecté à la tâche 21 17 20 19

Etape 0 : aucun ouvrier n'est affecté 16

Etape 1: l'ouvrier 1 est affecté à la tâche 17

On sépare le nœud B de coût minimum 17. 26 19 20

Ω

A B C D

B

Ω

B-A B-C B-D

UNIVERSIT

E SAAD DAHLAB D

E BLIDA

34

Etape 2 : l'ouvrier 2 est affecté à la tâche

Si on sépare le nœud les deux solutions seront BC AD ou BCDA de coûts

respectifs 3 + 1 + 7 + 9 = 20 et 3 + 1 + 8 + 11 = 23.

Ainsi pour le groupe correspondant à l'affectation de l'ouvrier 1 à la tâche D, on a calculer un

minorant sur la matrice

Tâches

Ouvriers

A B C

2 11 7 1

3 7 8 6

4 11 6 4

Le minorant est égale à 7 + 6 + 1 = 14 correspondant à une affectation réalisable

L'affectation des ouvriers aux tâches D-C-A-B est de coût total d14 + 14 = 19 est une

affectation sera l'affectation de coût minimum.

L'arborescence construite est la suivante :

16

21 17 20 19

26 19 20 19

20 23 19

B-C

A B C D

Ω

BA BC BD

BCAD BCDA DCAB

DC


UNIVERSIT

E SAAD DAHLAB D

E BLIDA


Exemple 3. Résolution d'un PLNE à variables bivalentes

Par une méthode par séparation et évaluation, résoudre le problème de partition suivant :

Min z = 3 x1 + 7 x2 + 5 x3 + 8 x4 + 10 x5 + 4 x6 + 6 x7 + 9 x8

x1 + x2 = 1

x3 + x4 + x5 = 1

x5 + x6 + x7 = 1

x7 + x8 = 1

x2 + x4 + x6 = 1

xi ∈ 0, 1 , i = 1, …, 8.

La résolution se fait en plusieurs étapes.

Etape1. Evaluation par défaut: On peut réduire la fonction économique en lui soustrayant

une combinaison linéaire des contraintes.

On peut soustraire trois fois la première contrainte, d'où :

z = 3 + 4x2 + 5 x3 + 8 x4 + 10 x5 + 4 x6 + 6 x7 + 9 x8

puis cinq fois la seconde contrainte, d'où

z = 8 + 4 x2 + 3 x4 + 5 x5 + 4 x6 + 6 x7 + 9 x8

puis quatre fois la troisième contrainte, d'où :

z = 12 + 4 x2 + 3 x4 + x5 + 2 x6 + 9 x8

enfin, deux fois la quatrième contrainte, d'où :

z = 14 + 4 x2 + 3 x4 + x5 + 7 x8

Puisque les xi, i = 1, …, 9, doivent être positifs, cela entraîne que toute solution réalisable du

problème donné a une valeur au moins égale à 14.

On associera donc au problème donné une évaluation par défaut égale à 14.

Etape 2. Séparation en deux problèmes

Nous devons choisir une variable xio et séparer l'ensemble des solutions réalisables en deux

sous ensembles, l'un dans tel que xio = 0, l'autre avec xio = 1.

Considérons alors les variables dont le coût dans la fonction objectif réduite est nul; soient x1,

x3, x6 et x7. Si on prend x1 = 0, on devra prendre x2 = 1, pour que la première contrainte soit

vérifiée. On augmentera donc l'évaluation par défaut du problème donné du coût de x2 dans la

fonction économique réduite, c-a-d quatre.

UNIVERSIT

E SAAD DAHLAB D

E BLIDA

36

Ce nombre que nous affecterons à x1 représentera la pénalisation de la fonction économique si

on ne choisit pas x1= 1; on l'appellera " pénalité" associée au chois de x1 = 0.

Si on prend x3 = 0, on devra prendre x4 = 1 ou x5 = 1 pour que la seconde contrainte soit

vérifiée. La pénalité associée au choix de x3 = 0 sera donc égale au minimum des coûts de x4

et x5 dans la fonction économique réduite, c-a-d min (3,1) = 1.

De la même façon, on déduit que la pénalité associée au choix de x6 = 0 sera le minimum des

coûts de x2 et x4, c-a-d min(4,3) = 3, et la pénalité associée au choix de x7 = 0 sera le coût de

x8, c-a-d 7.

On séparera alors l'ensemble des solutions réalisables en deux sous ensembles, l'un dans

lequel on pense qu'il existera la ( ou les ) solutions(s), l'autre qui a peu de chances de contenir

de bonnes solutions. Pour séparer les solutions, on choisira alors la variable de coût nul qui a

la pénalité maximale, c-a-d ici x7. En effet, toute solution réalisable avec x7 = 0 aura alors une

valeur au moins égale à 14 + 7 = 21.

Arborescente : Si S est l'ensemble des solutions réalisables du problème donné, on séparera S

en deux sous ensembles, l'un tel que x7 = 1, l'autre tel que x7 = 0. On représentera ces

ensembles par les sommets d'une arborescence;

Représente l'ensemble des solutions réalisables

L'ensemble des solutions tel que x7 = 1,

L'ensemble des solutions tel que x7 = 0,

14 14

14 + 7

sera le père de et de

Au dessous de chaque sommet de l'arborescence, on a représenté l'évaluation par défaut de

l'ensemble des solutions réalisables correspondant à ce sommet. Le principe de la méthode est

de recommencer sur le sommet ce qui a été fait sur le sommet

S

7

7

S 7

7

77S

7 S


UNIVERSIT

E SAAD DAHLAB D

E BLIDA


Etape 3. Implications

Plaçons nous au sommet , c-a-d faisons x7 = 1 dans le problème donné. Les contraintes 3

et 4 entrainent alors x5 = x6 = x8 = 0.

Le problème initial devient, en éliminant x5, x6, x7 et x8.

Min z = 14 + 4 x2 + 3 x4

x1 + x2 = 1

x3 + x4 = 1

x2 + x4 = 1

xi ∈ 0, 1 , i = 1, …, 4.

La réduction de la fonction objectif peut alors se faire comme à l'étape 1;

On trouve z = 17 + x2, en soustrayant trois fois la troisième contrainte.

Le sommet implique alors le sommet avec 17 comme évaluation par

défaut.

14 14 17

21

Etape 4. Sommet terminal et optimalité

On cherche alors à séparer le sommet ; on calcule alors les pénalités associées

aux variables x1, x3 et x4 comme à l'étape 2. On trouve p1 = 1, p3 = 0, p4 = 1.

On séparera alors le sommet sur la variable x1 par exemple.

Alors x1 = 1 entraîne x2 = 0, x4 = 1 et x3 = 0.

Ce dernier sommet est terminal puisqu'il ne contient qu'une seule solution

réalisable ( 1, 0, 0, 1, 0, 0, 1, 0 ).

14 14 17 17 17

21 17 +1=18

Nous avons donc déterminé une solution réalisable au sommet terminal de valeur 17.

7

7 8 ,6 ,5

S 7

7

8 ,6 ,5

8 ,6 ,5

4 ,3 ,2

S 7

7

8 ,6 ,5

1

1 4 ,3 ,2

38

En chemin, nous avons laissé deux sous ensembles représentés par les sommets et

. Or, chacun de ces sous ensembles a une évaluation par défaut plus grande que 17.

La solution réalisable trouvée est donc optimale.

Remarque: Trois notions ont été fondamentalement dans l'exploration.

- La notion de séparation qui est à la base de la méthode.

- La notion d'évaluation par défaut qui a permis, lorsque l'on a connu une solution réalisable

de valeur 17, d'affirmer qu'il n'existe pas de meilleurs solutions dans les sous ensembles

ayant une évaluation par défaut plus grande que 17.

Le critère de séparation, lié ici à la notion de pénalité, a permis de définir sur quelle variable

devait se faire la séparation.

Exemple 4. ( Algorithme de Little, Murty, Sweeney et Karel, 1963, pour résoudre un

problème de circuit hamiltonien ou du problème du voyageur de commerce, PVC )

Un autocar de ramassage scolaire doit, tous les matins, partant de l’école située en A, charger

des élèves en B, C, D, E et F. Ayant chronométré la durée de chacun des trajets entre les

différents points d’arrêt, on cherche le trajet hamiltonien de durée minimum dans un graphe

valué. On donne la matrice D = ( dij ) des durées des trajets ( i, j) ( non symétrique à cause

peut être des sens uniques ).

∞+∞+

∞+∞+

∞+∞+

2

2

3

4

3

9

2

6

1

1

8

4

5

6

2

16

8

5

4

2

18

10

8

6

1

18

12

10

8

6

F

EDC

B

A

F E D C B A

a. Recherche d’une évaluation par défaut

Toutes les méthodes peuvent commencer par une phase de réduction de la matrice des

distances ( phase d'initialisation). Le voyageur de commerce doit quitter une fois et une seule

fois la ville i; dans le meilleur des cas pour se rendre à la ville la plus proche j0 telle que

d(i, j0) = )j,i(dij

min≠

et dans les autres cas pour ce rendre en une ville quelconque j1 à la

distance d(i, j0) + (d(i, j1) - d(i, j0)) où ce qui est entre parenthèse est positive et la seule qui

varie avec le choix de j1; on peut donc décompter la distance d(i, j0) une fois en début de

l'algorithme, puis travailler sur les distances réduites d'(i, j1) = d(i, j1) - d(i, j0)).

7

1


UNIVERSIT

E SAAD DAHLAB D

E BLIDA

UNIVERSIT

E SAAD DAHLAB D

E BLIDA


De même le voyageur de commerce doit arriver une fois et une seule fois à la ville j; dans le

meilleur des cas il vient de la ville la plus proche i0 telle que d(i0, j) = )j,i(dji

min≠

et dans les

autres cas d'une ville quelconque i1 à la distance d(i0, j) + (d(i1, j) - d(i0, j)) où

d(i1, j) - d(i0, j) ≥ 0. On peut donc décompter la distance d(i0, j) une fois en début de

l'algorithme, puis travailler sur les distances réduites d"(i1, j) = d(i1, j) - d(i0, j). En fin de

réduction il y a obligatoirement au moins une distance nulle par ligne et une distance nulle par

colonne. d(i,j) est la nouvelle distance réduite de i à j pour simplifier la notation.

La somme des réductions effectuées sur la matrice des distances notée b0, est la distance

minimale parcourue quelque soit la séquence des villes retenues et décomptées à priori.

a.1. Ensemble des solutions candidates

On travaille sur des sous ensembles d'arcs retenus ou interdits dans le circuit partiel en

construction: la solution sera réalisable lorsqu'on aura retenu une suite de "n " arcs qui

constitue un seul circuit élémentaires. Dans A0 les sous ensembles d'arcs retenus ou interdits

sont vides; la matrice des distances est la matrice réduite de la phase d'initialisation.

a.2. Séparation

Un sous ensemble Ai est défini par un ensemble d'arcs retenus ou interdits et par la matrice

réduite des distances ( où les distances des arcs interdits sont infinies et où la ligne i et la

colonne j ne figurent plus si l'arc (i,j) a été retenu).

On partitionne Ai en A'i et A"i où dans l'un, l'arc (u, v) ( de distance réduite nulle) a été

ajouté à la liste des arcs retenus et dans l'autre à la liste des arcs interdits dans toute solution

constituant un circuit hamiltonien. On obtient des bornes b'i et b"i en ajoutant à bi le coût de

réduction de la nouvelle matrice des distances modifiée. Dans la nouvelle matrice D'i obtenue

en supprimant la ligne u et la colonne v et où on a mis à la valeur infinie la distance de v à u

( pour ne pas fermer un sous-circuit de deux arcs).

a.3. Choix des arcs à retenir

Pour pouvoir programmer les séparations, il faut préciser comment on choist l'arcs (u,v) parmi

tous les arcs qui ont une distance réduite nulle. Little a introduit la notion de " plus grand

regret", les choix étant faits de telle sorte que l'écart entre b'i et b"i soit le plus grand possible

si bien après avoir exploré A'i de meilleure borne on ait pu avoir la chance de trouver une

UNIVERSIT

E SAAD DAHLAB D

E BLIDA

40

solution réalisable meilleure que b"i ce qui évitera l'exploration de A"i. Pour cette raison, on

sépare à partir des arcs de distances nulles: leur sélection coûte 0 et si on a la chance que les

réductions de la matrice des distances ne fait pas augmenter la borne, alors b'i = bi valeur

minimale que peut prendre cette borne après la séparation. Au contraire, si on ne prend pas

(u,v), on souhaite que le coût de la réduction correspondante soit maximal pour que b"i soit le

plus grand possible après séparation. On calcule le "regret" de l'arc (u,v) dans la matrice

réduite D, par la formule regret(u,v) = )v,i(dui

min≠

+ )j,u(dvj

min≠

. Il est la somme de la

distance minimale sur la ligne u et sur la colonne v lorsqu'on interdit l'arc (u,v), ce sera le coût

de la réduction de A"i. Après le calcul des regrets de tous les arcs de distance nulle, on affecte

la séparation par l'arc de plus grand regret.

a.4. Elimination de sous ensembles

Ai est vide de solutions réalisables si un sous ensemble des arcs retenus constitue un circuit de

moins de "n" arcs. Ai est réduit à une seule solution réalisable s'il y a exactement " n" arcs

retenus qui ne ferment pas de sous-circuits dont le nombre d'arcs est inférieur à n.

On considère la matrice des coûts T0 =

8

223

1

1

2

2

3

4

3

9

2

6

1

1

8

4

5

6

2

16

8

5

4

2

18

10

8

6

1

18

12

10

8

6

F

EDC

B

A

F E D C B A

∞+∞+

∞+∞+

∞+∞+

1. Réduction de la matrice en soustrayant le minimum de chaque ligne, On obtient la matrice

T1 =

∞+∞+

∞+∞+

∞+∞+

0

0

0

3

2

1

0

3

0

0

0

2

2

5

1

8

6

3

3

1

10

8

6

3

0

10

10

8

5

5

F

EDC

B

A

F E D C B A

. La somme de 1 + 1 + 3 + 2+2+8 = 17, le

minimum de chaque ligne représente le coût des sorties des villes A, B, C, D, E et F.


UNIVERSIT

E SAAD DAHLAB D

E BLIDA


Réduction de la matrice en soustrayant le minimum de chaque colonne. On détermine la

valeur minimale de chaque colonne de T1,

0 0 0 1 0 5

0

0

0

3

2

1

0

3

0

0

0

2

2

5

1

8

6

3

3

1

10

8

6

3

0

10

10

8

5

5

F

EDC

B

A

F E D C B A

∞+∞+

∞+∞+

∞+∞+

.

T2 =

∞+∞+

∞+∞+

∞+∞+

0

0

0

3

2

1

0

3

0

0

0

2

2

5

1

7

5

2

2

0

10

8

6

3

0

5

5

3

0

0

. Le minimum de chaque colonne représente le

coût des entrées des villes A, B, C, D, E et F. Il est de 5 + 0 + 1 + 0 + 0 + 0 = 6.

Le coût des entrées et sorties des villes A, B, C, D, E et F est de 17 + 6 = 23.

Quelque soit une tournée T, v(T) ≥ 23.

b. Résolution par l'algorithme de Little

a. Calcul des regrets: on sépare suivant l'arc qui a le plus grand regret, calculé

par la formule regret(u,v) = )v,i(dui

min≠

+ )j,u(dvj

min≠

. De la matrice T2, l'arc AB, son regret

est 0 + 3 = 3. On peut déterminer les regrets à chaque arc de valeur 0. Il est indiqué en indice

On obtient

∞∞

∞∞

∞

∞

200000

3

2

1

00

30000

20

2

2

5

1

7

5

2

220

10

8

6

3

30

5

5

30000

F

EDC

B

A

FEDCBA

. L'arc AC son regret est 0 + 2 = 2.

L'arc AB a le plus grand regret.

b. séparation de l'ensemble A0 de toutes les solutions du problème de borne b0 = 23 en deux

sous ensembles : A1 où on choisit l'arc ( A, B ) et A2 où on interdit l'arc ( A B ) et qui aura

UNIVERSIT

E SAAD DAHLAB D

E BLIDA

42

comme borne b2 = b0 + regret( AB) = 23 + 3 =26. Pour calculer la borne de A1 on construit

la matrice M1 qui lui est associée:

- en supprimant la ligne A sur laquelle on ne peut plus faire d'autres choix.

- en supprimant la colonne B sur laquelle on ne peut faire d'autres choix.

- en rendant infinie la case ( B, A ) pour éviter de fermer le sous-circuit (A ,B ,A ).

Puis on réduit si nécessaire la matrice M1 de manière à avoir au nouveau un "0" par ligne et

par colonne , ce qui permet d'ajuster le minorant b1

M1 =

0 0 0 2 0

0

00

0

0

1

0

0

2

7

5

5

50023

0320

3052

F

ED

C

BF E D CA

∞+∞+

∞+∞+

∞+

. M'1 =

∞+∞+

∞+∞+

∞+

120

30

2

5

3

5

50000003

003230

30052

F

ED

C

B

F E D CA

.

b1 = 23 + 2 = 25.

c. on choisit d'utiliser une P S E P

A1 est le sous ensemble de meilleure borne : On a calculé sur M'1 les regrets de ses zéros de

manière à le séparer. Le plus grand regret est de C pour l'arc (C, A ). On sépare l'ensemble

A1 de borne b1= 25 en deux sous ensembles A3 où on choisit l'arc ( C,A ) ( en plus de l'arc

(A, B) ) et A4 où on interdit l'arc (C, A )( mais où on conserve (A,B))et qui aura comme

borne b4 = b1 + regret (C,A ) = 25+ 3 = 28.

Pour construire la borne de A3 , on construit la matrice M3 qui lui est associée : en

supprimant la ligne C et la colonne A sur lesquelles on ne plus faire d'autres choix.

On devrait rendre infinie la case en position (1, 3) mais elle n'appartient pas à la partie

restante de la matrice M'1 . On réduit si nécessaire la matrice obtenue M3 de manière à avoir à

nouveau un 0 par ligne et par colonne, ce qui permet d'ajuster le minorant b3.

M3 =

0 0 0 0

0

0

0

0

13052023000000

300500

F

E

D

BF E D C

∞+∞+

∞+ . b3 = 25 + 0 = 25.

d. A3 est le sous ensemble de meilleur borne : on a calculé sur M3 ses regrets. Le plus grand

est de 3 pour l'arc FD. On sépare l'ensemble A3 de borne b3 = 25 en deux sous ensembles A5


UNIVERSIT

E SAAD DAHLAB D

E BLIDA


où on choisit l'arc FD ( en plus des arcs CA et AB ) et A6 où on interdit l'arc ( F D ) ( mais on

conserve CA et AB ) et qui aura une borne b6 = b3 + regret(FD) = 25 + 3 = 28.

Pour calculer la borne de A5 on construit la matrice M5 qui lui est associée:

- en supprimant la ligne F et la colonne D en rendant infinie la case DF pour éviter de

fermer le sous circuit ( FDF).

Puis on réduit si nécessaire la matrice obtenue de M5 afin d'ajuster b5.

M5 =

∞+∞+

6030000

30000

E

D

BF E C

. b5 =25.

e. A5 est le sous ensemble de meilleure borne; le plus grand regret est de 6 pour l'arc EF. On

sépare l'ensemble A5 de borne b5 = 25 en deux sous ensembles A7 où on choisit l'arc EF ( en

plus des arcs CA, AB et FD) et A8 où on interdit l'arc EF ( mais on conserve CA, AB et FD)

avec la borne b8 = b5 + regret (EF) = 25 + 6 = 31.

Pour calculer la borne de A7, on construit la matrice M7 en supprimant la ligne E, la colonne F

et on réduit si nécessaire la matrice obtenue. M7 =

00000000

D

BE C

.

f. A7 est le sous ensemble de meilleure borne 25; le plus grand regret est zéro pour l'arc BC

par exemple. On sépare A7 de borne b7 = 25 en deux sous ensembles A9 où on choisit l'arc BC

( en plus des arcs (CA, AB, EF, FD)) et A10 où on interdit l'arc BC ( mais on conserve CA,

AB, EF, FD) avec la borne b10 = b7 + regret(BC) = 25.

Si l'on examine A9, on s'aperçoit qu'il contient un sous-circuit (CABC), il est donc vide de

solutions réalisables et on l'élimine de la recherche.

g. A10 est alors le sous-ensemble de meilleure borne. Pour le séparer il faut connaître les

regrets de ses zéros et donc construire la matrice M10 qui lui est associée; on l'obtient à partir

de M7 en mettant simplement l'infini dans la case interdite BC et on la réduit si nécessaire.

M10 =

∞+

000000

D

BE C

.

h. La borne de A10 est de 25. On sépare A10 en A11 qui contient les arcs ( CA, AB, BE, EF et

FD) et A12 qui contient les arcs (CA, AB, EF et FD mais pas BE).

UNIVERSIT

E SAAD DAHLAB D

E BLIDA

44

Ces deux sous ensembles ont pour regret 0 et A11 ne contient qu'une seule solution réalisable

qui consiste à compléter le circuit hamiltonien par DC ( seule case à coût nul et à regret infini

de M11 ).

On a obtenu la solution réalisable CABEFDC de coût 25, alors que toutes les bornes des sous

ensembles non séparés et non éliminés sont toutes supérieures où égale à 25. Cette solution

est optimale. On ne sait pas si l'optimum est unique, c'est laissé pour l'étudiant de déterminer

d'autres solutions optimales.

Remarque: on devrait aussi rendre infinie la case BC car elle ferme le sous-circuit CABC

mais cela complique la programmation de cette méthode en demandant de tester en

permanence les sous-circuits " succeptibles" d'être fermés. Nous nous contenterons de tester

ici les sous circuits effectivement fermés ce qui est moins couteux mais conduit à quelques

séparations de plus.

Exemple 5. L'algorithme de Eastman

a. ensemble de solutions candidates

Pour l'obtenir, on compare le problème Π du voyageur de commerce avec le problème Π' de

l'affectation simple à coût minimal.

Π' ) Etant donné une matrice carrée de coûts ( que l'on peut noter d(i,j), choisir exactement

une case par ligne et une case par colonne de telle sorte que la somme des coûts soit minimal)

Π ) Etant donné une matrice carrée donnée de distances, choisir exactement une case par ligne

( car le voyageur quitte une fois et une seule fois une ville i) et une case par colonne ( car le

voyageur arrive une fois et une seule fois dans la ville j) de telle sorte que la somme des

distances soit minimale et que l'ensemble des cases retenues constituent un seul circuit de "n"

arcs. Le problème du voyageur de commerce contient une contrainte supplémentaire. Toute

solution du voyageur de commerce est une solution réalisable pour le pro0blème de l'affectation

simple à coût minimal, mais la réciproque est fausse: L'ensemble des solutions réalisables de

l'affectation contient les solutions du voyageur de commerce et la meilleure solution pour

l'affectation est au moins aussi bonne que la meilleure solution du PVC, sa valeur est donc un

minorant pour le PVC. A0 contient une solution du problème d'affectation et b0 sa borne est

calculée selon au moins la méthode vue en cours.


UNIVERSIT

E SAAD DAHLAB D

E BLIDA


Séparation

Pour évaluer la borne bi, on applique la méthode vue en cours. Si la solution fournie est une

solution du PVC ( elle constitue un seul circuit passant par tous les points), alors c'est une

solution optimale de Ai que l'on cesse de séparer. Si au contraire, cette solution n'est pas une

solution du PVC, alors les arcs qui la compose constitue un sous ensemble de sous-circuits

indépendants dont le nombre d'arcs est strictement plus petit que "n", solution réalisable pour

l'affectation, mais pas pour le PVC. On cherche à séparer de telle sorte que cette solution

disparaisse sans supprimer d'autres solutions réalisables; pour cela, on considère les sous-

circuits de cette solution, on retient un des plus petits en nombre d'arcs ( de manière à séparer

en un plus petit nombre de sous ensembles) : i1, i2,…, ip, i1 ( p < n) et on sépare l'ensemble Ai

en p sous ensembles Ak1, Ak2, …, Akp tel que Akj est l'ensemble des solutions de Ai qui ne

contiennent pas l'arc (ij, ij+1). La séparation est dite par "recouvrement": on ne retrouve plus

les solutions de l'affectation simple qui contiennent le circuit " ouvert" mais une solution qui

ne contient aucun arc du circuit ouvert se retrouve dans les sous-ensembles obtenus.

Exemple 6. Algorithme de l'arbre de recouvrement minimal

a. Ensemble des solutions réalisables

On suppose que le graphe des distances est symétrique, graphe orienté. On compare le

problème du PVC, Π, avec celui de la recherche de la plus courte chaîne hamiltonienne dans

un graphe Π ' et le problème Π " de la recherche de l'arbre de recouvrement minimal dans un

graphe.

Lien entre les meilleures solutions de Π et les meilleures solutions de Π '

Supposons, arbitrairement, que le voyageur de commerce parte de la ville i0 et y revienne en

fin de circuit et considérons le sous-graphe G' obtenu à partir du graphe G en supprimant le

point i0. Toute solution de Π est constituée d'une arête liant i0 à un point i1 de G', d'une chaîne

hamiltonienne passant par les points de G' et se terminant en un point in-1 et d'une arête liant

in-1 à i0. Pour obtenir un minorant aux solutions du problème Π, il faut chercher la meilleure

solution de Π ' et lui ajouter la distance des deux plus petites arêtes allant de i0 à G ' (

minorant de i1, i2,…, in-1.

Si les deux plus petites arêtes ainsi définies complètent la chaîne hamiltonienne minimale de

G' de manière à former un cycle hamiltonien de G, alors celui-ci est minimal.

UNIVERSIT

E SAAD DAHLAB D

E BLIDA

46

Liens entre les meilleurs solutions de Π ' et celle de Π "

Une chaîne hamiltonienne est un graphe partiel connexe er sans cycles de n -1 sommets tel

qu'il existe un point origine et un point extrémité où le degré est de 1 alors que tous les autres

points sont de degré 2, alors qu'un arbre de recouvrement est un graphe partiel connexe et

sans cycles de n-1 sommets. Toute chaîne hamiltonienne est un arbre de recouvrement, la

réciproque étant fausse. Le poids du plus petit arbre de recouvrement est un minorant pour la

valeur de la plus petite chaîne hamiltonienne. On travaille sur les arbres de recouvrement de

G' que l'on complète par les deux arêtes les plus petites i0 à G' de manière à obtenir des

minorants pour le problème Π.

Séparation

Comme dans l'algorithme de Eastman, on utilise une technique de recouvrement et on

est amené à interdire des arêtes de manière à ne plus retrouver de solutions minimales mais

irréalisables. A la fin du calcul du minorant de l'ensemble Ak, on a obtenu un arbre de

recouvrement minimal de G' ( par un des algorithmes de Prim, Kruskal ou de Sollin), on

complète par les deux arêtes de i0 à G', on obtient un graphe partiel connexe de " n" arêtes

dont on examine les degrés: s'ils sont tous égaux à 2; On a obtenu la solution optimale de Ak;

sinon, il existe au moins un point de degré supérieur à 2 dont une des arêtes au moins doit

disparaître pour obtenir une solution réalisable. On choisit le point j de degré maximal "p"

dans le sous graphe partiel qui contient les arêtes (ju1) (ju2),…, (jup) et on sépare Ak en p sous

ensembles Av1, …, Avp où on interdit l'arête ( j, uw) dans le sous-ensemble Anw, ce qui revient

pour ce sous ensemble, soit à interdire une arête allant de i0 à G', soit à modifier G' par

suppression d'une arête.

Elimination

Suit les règles usuelles des PSE.

Exemple 7. un problème du job shop

Pour réaliser la fabrication de trois pièces, on dispose de leur gamme de fabrication.

La pièce i demande qi opérations et la jième opération de la pièce i occupe τij unités de temps

de la machine Mij. Les durées d'usinage sont très longues par rapport aux durées de transport

et de réglage et on négligera ces dernières. Cette méthode ne permet de résoudre que des

problèmes de taille raisonnable. Le problème qui consiste à placer les opérations sur les

machines de telle sorte que :


UNIVERSIT

E SAAD DAHLAB D

E BLIDA


L’opération j du produit i soit terminée avant le début j+1.

Une machine ne traite qu’une seule opération à la fois

On minimise la durée totale ( l’opération qui se termine la dernière se termine le plus tôt

possible)

Les gammes sont fournies dans le tableau suivant:

n° opération 1 2 3 4

Pièce 1

Durées

Machines

3

(1)

1

(2)

2

(3)

1

(3)

Pièce 2

Durées

Machines

1

(2)

2

(1)

1

(3)

3

(2)

Pièce 3

Durées

Machines

2

(3)

1

(2)

./.

./.

./.

./.

Les bornes minorantes sont calculées par relaxation en ignorant, initialement, les contraintes

dues au fait qu'une machine ne peut effectuer qu'une seule et unique opération à la fois.

Ces contraintes seront intégrées progressivement au fur et à mesure des séparations jusqu'à

l'obtention de solutions réalisables qui seront optimales pour le sous-ensemble de solutions

auquel elles appartiennent. En fin d'exploration, la meilleure solution réalisable trouvée sera

optimale. L'ensemble des solutions candidates A0 est l'ensemble de tous les ordres possibles

de toutes les opérations à exécuter sur les différentes machines.

Pour trouver un minorant à la meilleure solution possible de cet ensemble, on ignore les

contraintes dues aux machines en faisant comme si on avait autant d'exemplaires de chaque

machine que nécessaire pour réaliser la solution "au plus tôt" pour chaque pièce, ce qui donne

l'ordonnancement non réalisable suivant représenté sur un diagramme où chaque ligne

correspond à une pièce et chaque case à la j-ème opération de la tâche i sur la machine (k).

1 2 3 4 5 6 7 8 9 10 11 12

Pièce 1

UNIVERSIT

E SAAD DAHLAB D

E BLIDA

48

1,1(1) 1,2(2) 1,3(3) 1,4(3)

Pièce 2

2,1(2) 2,2(1) 2,3(3) 2,4(2)

Pièce 3

3,1(3) 3,2(2)

Fig 2. Diagramme " pièces " calé au plus tôt correspondant au sous ensemble A0.

La plus longue gamme ayant une durée totale de sept (7 ) unités de temps, 7 est un minorant

pour la durée totale pour l'ensemble des solutions du problème d'où b0 = 7. La solution ci

dessus serait optimale si elle était réalisable. Elle comporte des conflits sur l'utilisation des

machines. A l'instant 1, un conflit survient entre 1,1 (1) ( la première opération du produit un )

et 2,2(1) ( la deuxième opération du produit deux ) sur l'utilisation de la machine 1.

Nous devons séparer l'ensemble de solutions A0 en deux sous ensembles de solutions de telle

sorte que toute solution réalisable se retrouve obligatoirement dans l'un des deux et que les

solutions non réalisables qui contenaient ce premier conflit ne s'y retrouvent plus.

Pour cela, on partitionne A0 en deux sous ensembles complémentaires. A1 où 1,1(1) est placée

sur la machine 1 avant 2,2 et A2 où 2,2 est placée sur la machine 1 avant 1,1. Avant de séparer

A1 ou A2 , nous allons calculer les nouvelles bornes les concern ants de manière à pouvoir

appliquer une procédure par séparation et évaluation progressive en séparant toujours le sous

ensemble de meilleur borne. Placer 1,1 avant 2,2 revient à déplacer le début de 2,2 de 2 unités

et donc à déplacer la fin du produit deux de 7 à 9 unités. D'où b1 = 9. Placer 2,2 avant 1,1

revient à déplacer le début de 1,1 de 3 unités et donc de déplacer la fin du produit un de 7 à 10

unités. D'où b2 = 10. La meilleure borne est fournie par A1 que nous allons séparer en

cherchant le premier conflit-machine sur son diagramme pièces calé au plus tôt.

1 2 3 4 5 6 7 8 9 10 11 12

Pièce 1

1,1(1) 1,2(2) 1,3(3) 1,4(3)

Pièce 2

2,1(2) ///////////////////// 2,2(1) 2,3(3) 2,4(2)

Pièce 3

3,1(3) 3,2(2)



UNIVERSIT

E SAAD DAHLAB D

E BLIDA


Ici, le diagramme de A2 n'est pas représenté. Un conflit survient à l'instant 5 entre 1,3(3) et

2,3(3) pour l'utilisation de la machine 3. A1 sera séparé en deux sous ensembles A3, où 1,3 (3)

est placée avant 2,3(3) et A4, où 2,3(3) est placée avant 2, 3(3). Placer 1,3(3) avant 2,3(3)

revient à déplacer 2,3(3) d'une unité de temps et donc de déplacer la fin du produit 2 de

l'instant 9 à 10. Placer 2,3(3) avant 1,3(3) revient à déplacer 1,3(3) de deux unités de temps et

donc de déplacer la fin du produit 1 de l'instant 7 à 9.

1 2 3 4 5 6 7 8 9 10 11 12

Pièce 1

1,1(1) 1,2(2) /////////////////// 1,3(3) 1,4(3)

Pièce 2

2,1(2) ///////////////////// 2,2(1) 2,3(3) 2,4(2)

Pièce 3

3,1(3) 3,2(2)


Ce diagramme ne comporte plus de conflit pour l'utilisation des machines. C'est une solution

réalisable pour le problème posé, comme sa durée totale est strictement inférieure à toutes les

bornes des sous ensembles que nous n'avons pas encore séparés.

C'est l'unique solution optimale parmi les solutions calées au plus tôt.

Remarque : Si on programme cette méthode, on n'utilise pas les diagrammes " pièces " mais

les dates au plus tôt de toutes les opérations sur le graphe potentiel-tâche comportant les

contraintes de précédence dues aux gammes puis celles ajoutées progressivement à chaque

séparation pour tenir compte des conflits dus aux machines.

La borne étant la date au plus tôt de la tâche fictive de fin de réalisation.

≥ b0 = 7

≥b1= 9 ≥ b2 = 10

≥b3=10 ≥ b4 = 9

Fig 5. Arborescence des séparations.

A0

A2

L'opération2,2(1) > 1,1(1)

A1

L'opération1,1(1) > 2,2(1)

A4

1,1(1) > 2,2(1) et 2,3(3) > 1,3(3)

A3

1,1(1) > 2,2(1) et 1,3(3) > 2,3(3)

UNIVERSIT

E SAAD DAHLAB D

E BLIDA

50

Exemple 8.

Résoudre le problème de sac à dos binaire suivant, à l’aide de la méthode de séparation et

d’évaluation présentée au cours :

Max z = 13 x1 + 16 x2 + 7 x3 + 4 x4

6 x1 + 8 x2 + 4 x3 + 3 x4 ≤ 12

x1, x2, x3 et x4 ∈ 0, 1

Evaluation. Pour la phase d'évaluation, on va résoudre la relaxation linéaire du problème, du

problème linéaire obtenu en remplaçant les contraintes xi ∈ 0, 1 ∀ i, par 0 ≤ xi ≤ 1, ∀ i.

Pour résoudre cette relaxation, on va appliquer un algorithme glouton : les objets sont à

chargés par ordre croissant du rapport ρi = qualité/ poids = ci / ai.

Objet i 1 2 3 4

Utilité ci

Poids ai

13 16 7 4

6 8 4 3

ρi = ci / ai. 2.16 2 1.75 1.3

Les objets sont à considérer dans l'ordre donné 1, 2 , 3 et 4.

Séparation. Si la relaxation linéaire n'est pas entière, on crée deux sous-problèmes en posant,

dans l'un, xj = 1 et, dans l'autre, xj = 0 où xj est la variable fractionnaire dans la solution de la

relaxation linéaire.

Initialisation. L'arbre d'énumération ne contient que la racine A0 représentant le problème

initial. −∞=z .

Première itération. On évalue une borne supérieure 0z pour A0 :

X1 = 1, x2 = 6/8, x3 = 0, x4 = 0 et 0z = 25.

La solution n'est pas entière et 0z > z . On sépare A0 en créant deux sous problèmes avec

respectivement, x2 = 1 et x2 = 0.

z = - ∞

A2 oùx 2 = 0

A1 oùx 2 =1

A1


UNIVERSIT

E SAAD DAHLAB D

E BLIDA


Deuxième itération. On traite le sommet ou nœud actif A1, et on évalue une borne

supérieure 1z pour ce dernier : x2 = 1 (fixé), x1 = 4/6, 1z = 24.6.

La solution n'est pas entière et 1z > z , on sépare A1 en branchant sur x1.

z = - ∞

Troisième itération. On traite le sommet actif A3. On a x1 = x2 = 1, mais a1 + a2 = 14 > 12=b.

L'ensemble A3 est vide, et le sommet est sondé.

Quatrième itération. On traite le sommet actif A4, et on évalue sa borne supérieure 4z ,

x1 = 0, x2 = 1, x3 = 1, 4z = 23.

La solution est entière et 4z > z . On met à jour z= 23. Le nœud A4 est sondé.

Cinquième itération. On traite le sommet actif A2, et on évalue sa borne supérieure 2z .

x1 = 1, x2 = 0, x3 = 1, x4 = 2/3, 2z = 22.6.

La solution n'est pas entière mais 2z ≤ z , le sommet est ainsi sondé.

La solution optimale est de prendre les objets 2 et 3 pour une valeur de 23.

Exercices.

1. Donner les circuits hamiltoniens de valeur totale minimale pour les graphes valorisés dans

les tableaux suivants:

∞+∞+

∞+∞+

∞+

0

23

16

3

5

2

2

022007

00021

01143

;

∞+∞+

∞+∞+

∞+

6

5

4

11

6

8

3

89 937

2 683

9725

;

∞+∞+

∞+∞+

∞+∞+

2

64

006

6

20

1

45

0

02

23023

61035

60450

A2 oùx 2 = 0

A1 oùx 2 =1

A0

A3 oùx1 =1

A4 oùx1 =0

52

2. Formuler et résoudre par une procédure par séparation et évaluation le problème de sac à

dos avec les données numériques suivantes

Aliments k 1 2 3 4

Prix ck 20 30 40 50

Poids pk 10 15 30 40

Le budget disponible est b = 60.


UNIVERSIT

E SAAD DAHLAB D

E BLIDA

Documents

Chapitre 3 Méthodes exactes de résolution des problèmes ... · Elles peuvent pallier le manque d'algorithmes polynomiaux pour des problèmes de taille moyenne. Pour des problèmes