1

Programmation linéaire en nombres entiers

Algorithme de la subdivision successive(«Branch and Bound

Algorithm»)

2

Introduction

Stratégie :

"couper en 2" la région réalisable, recouper en 2 chaque partie dela région réalisable susceptible de contenir la soln optimale etainsi de suite.

Ce processus se poursuit jusqu’à ce qu’on trouve la soln optimaleou une soln sous-optimale satisfaisante ou bien que l’on détectel’absence de solns.

Variantes :

la façon de couper en 2 la région réalisable,

le choix de la partie de la région réalisable à examiner en premier,

la façon de s’assurer qu’un morceau ne contient pas la soln

optimale afin de pouvoir éliminer ce morceau.

3

Exemple décrivant l’algorithme de subdivision successive

(P0)

Le simplexe nous donne comme soln optimale de (P0) :x = 3.5, y = 10/3 et z0

max = 145/6.

4

5

Quelle coupe peut-on effectuer dans l'ensemble des solns réalisablesde (P0) qui n'ôte aucun point entier de cet ensemble?

La soln optimale de (PE) doit vérifier soit y ≤ 3, soit y ≥ 4.

Formons les 2 problèmes issus de (P0) :

(P1)

(P2)

simplexe

x = 18/5,y = 3,z1

max = 24.

x = 5/2,y = 4,z2

max = 20,5.

6

Puisque z1max > z2

max on choisit de travailler avec (P1) pour l’instant.

Si la soln optimale de (PE) vérifie les contraintes de (P1), elle vérifieraaussi soit x 3 ou x 4. Formons 2 nouveaux problèmes issus de (P1):

(P3)

(P4)

redondantredondant

x = 3,y = 3,z3

max = 21.

x = 4,y = 5/3,z4

max = 70/3.

7

Puisque z4max > z3

max on choisit de travailler avec (P4) pour l’instant :soit y 1 ou y 2.

8

(P5)

(P6)

redondant

Pas de solnsréalisables

x = 4.2,y = 1,z5

max = 23.

9

10

À partir de (P5), on peut construire les 2 problèmes suivants :

(P7)

(P8)

x = 4,y = 1,z7

max = 22.

Pas de solnsréalisables.

simplexe

11

(P7) possède une solution optimale entière réalisable pour (PE).

Pour savoir si elle est optimale, il faut examiner les problèmes quenous avons laissés de côté en créant des coupes.

(P8) et (P6) : on peut les négliger (pas de solns réalisables).

(P3) : on peut le négliger car z7max = 22 > 21 = z3

max.

(P2) : on peut le négliger car z7max = 22 > 20.5 zmax.

L’ajout de coupes à (P2) ne peut donner de solnsoù la fonction objective est plus grande que 20,5.

Donc, x = 4, y = 1 et zmax = 22 est la soln optimale de (PE).

12

13

Cas particulier : Quelques variables ne sont pas entières etles autres le sont.

Il suffit de ne pas introduire de coupes sur les variables nonastreintes à être entières.

Exemple : Le problème précédent où x n’est pas astreinte àêtre entière.

Dans l’arborescence précédente, on voit que (P1) et (P2)nous donnent 2 solns réalisables et donc que la soln optimaleserait dans ce cas :

x = 18 / 5, y = 3 et zmax = 24.

14

Énoncé de l’algorithme de subdivision successive

(0) Construire une banque de problèmes qui ne renferme initialementque le problème suivant : Max z = ctx

A x = b (P0)x 0

k 1;zk = -; (renferme une borne inférieure de la valeur optimale

de l’objectif z)

(1) Si la banque de problèmes est vide, terminer les calculs, i.e.rechercher la meilleure soln réalisable rencontrée dont la valeur del’objectif est égale à la borne inférieure.Cette soln réalisable est alors optimale.

Autrement, enlever un programme linéaire de la banque etaller à (2).

15

(2) Résoudre le programme choisi. Si la valeur de l’objectif est au plus zk,

zk+1 zk, k k +1, aller à (1).Autrement, aller à (3).

(3) Si la soln optimale obtenue du programme linéaire satisfait lescontraintes d'intégralité,

noter-le *,zk+1 valeur optimale de l’objectif de ce programme,faire k k + 1,aller à (1).

Autrement, aller à (4).

(4) Choisir une variable xj n’ayant pas une valeur entière (xj = br).

Ajouter 2 programmes linéaires à la banque issus de celui de (1) :

1e problème : xj [br] est ajoutée.2ième problème : xj [br] + 1 est ajoutée.

Faire zk+1 zk, k k +1, aller à (1).

16

Choix d’un programme dans la banque :

Résoudre l’un des 2 programmes que l’on vient d’ajouter à la banqueou le dernier à être introduit qui n’est pas encore résolu.

En passant d’un nœud à son fils dans l’arbre, on a le même problèmeà résoudre avec seulement une contrainte en plus.

Il s’agit d’utiliser l’algorithme dual du simplexe.

Borne supérieure sur la valeur de l’objectif :

La résolution du programme continu à chaque nœud de l’arbre nousfournit une borne supérieure sur la valeur de l’objectif de la meilleuresoln possible dans cette branche.