6.
Solution de problèmes entiers
6.1 Problème d’affectation de lignes aériennes
a) Formulation du problème :
Choix des variables :
x1 = nombre d’avions affectés par jour sur la ligne OM ;
x2 = nombre d’avions affectés par jour sur la ligne OT.
Objectif :
min z = 4x1 + 3x2
Expression des contraintes :
satisfaire la demande :
150x1 ≥ 500 (1)
150x2 ≥ 200 (2)
respecter le nombre d’avions :
x1 + x2 ≤ 6 (3)
caractère entier des variables :
x1 , x2 ≥ 0 et entiers
b) Résolution : Pas 0 : résoudre la relaxation linéaire :
6. Solution de problèmes entiers
6.1 Problème d’affectation de lignes aériennes
min z = 4x1 + 3x2
x1 ≥ 3, 33 (1)
x2 ≥ 1, 33 (2)
s.c.q.
x +x2 ≤ 6 (3)
(3) x2 1
(1)
x1 , x2 ≥ 0
6
5
z = 4x 1 + 3x2 = 12
3
z = 4x 1 + 3x2 = 6
2
(2)
P0
1
1 2 3 4 5 6 x1
6. Solution de problèmes entiers
6.1 Problème d’affectation de lignes aériennes
Pas 1 : choix d’une variable non entière : x1 = 3, 33 avec :
1 : x1 ≤ 3
Région ○ 2 : x1 ≥ 4
Région ○
x2
z = 4x 1 + 3x2 = 12 1 2
2
(2)
P0 P2
1
1 2 3 4 5 6 x1
(3)
(1)
4
1 : impossible
Solution ○ 2 : P2 =
Solution ○ 4, , z2 = 20
3
6. Solution de problèmes entiers
6.1 Problème d’affectation de lignes aériennes
Arbre de branch and bound :
z 0 = 17, 333
x 1 = 3, 333
x 2 = 1, 333
x1 3 x1 4
impossible
z 2 = 20
impossible
x1 = 4
x2 = 1, 333
2 reste
Pas 2 : choix d’un noeud à diviser : seul le noeud ○
Pas 1 : choix d’une variable non entière : x2 = 1, 33 avec :
3 : x2 ≤ 1
Région ○ 4 : x2 ≥ 2
Région ○
6. Solution de problèmes entiers
6.1 Problème d’affectation de lignes aériennes
x2
z = 4x 1 + 3x2 = 12
1 2
4
3
4 P4
2
(2)
P0 P2
1
3
1 2 3 4 5 6 x1
(3)
(1)
3 :
Région ○ x2 ≤ 1 système impossible
4 :
Région ○ x2 ≥ 2 solution = (4, 2) , z = 22
6. Solution de problèmes entiers
6.1 Problème d’affectation de lignes aériennes
c) Arbre de branch and bound :
z 0 = 17, 333
x 1 = 3, 333
x 2 = 1, 333
x1 3 x1 4
impossible
z 2 = 20
impossible
x1 = 4
x2 = 1, 333
x2 1 x2 2
impossible entiers
z 4 = 22
impossible x1 = 4
x2 = 2
6. Solution de problèmes entiers
6.2 Méthode de branch and bound
a) Résoudre la relaxation linéaire :
x2
z = 5x 1 + 4x2 = 40
(3)
8
max z = 5x1 + 4x2
(2) 7
x1 + x2 ≤ 5 (1)
10x1 + 6x2 ≤ 45 (2)
z = 5x 1 + 4x2 = 20
s.c.q.
6 x ≥0 (3)
1
x2 ≥ 0 (4)
5
2
P0
1
(4)
1 2 3 4 5 6 7 8 x1
(1)
6. Solution de problèmes entiers
6.2 Méthode de branch and bound
La solution optimale du problème linéaire est à l’intersection des
contraintes :
(
x1 + x2 = 5 (1)
10x1 + 6x2 = 45 (2)
(
6x1 + 6x2 = 30 (1)
⇔
10x1 + 6x2 = 45 (2)
(
4x1 = 15 (2) − (1)
⇔
x2 = 5 − x1 (10 )
et vaut donc :
15 20 15 5
x∗1 = = 3, 75 x∗2 = 5 − x1 = − = = 1, 25
4 4 4 4
L’objectif vaut :
zP∗ L = 5x∗1 + 4x∗2 = 23, 75
6. Solution de problèmes entiers
6.2 Méthode de branch and bound
b) Méthode de branch and bound :
Pas 0. Résoudre la relaxation initiale :
x1 = 3, 75 x2 = 1, 25 z = 23, 75
Pas 1. Choisir une variable non entière pour brancher : x1
Soit x1 ≤ 3 1 : x1 = 3, x2 = 2, z1 = 23
Région ○
5
Soit x1 ≥ 4 2 : x1 = 4, x2 = , z2 = 23, 33
Région ○
x2 6
(2)
5
z 1 2
4
3
P1
2
P0
1
1
P2
1 2 3 4 5 6 x1
6. Solution de problèmes entiers
6.2 Méthode de branch and bound
z0 = 23,75
x 1 = 3,75
x 2 = 1,25
x1 3 x1 4
z1 = 23 z2 = 23,33
x1 = 3 x1 = 4
x2 = 2 x 2 = 0,833
Pas 2. Choisir un noeud pour le branchement : le
Noeud ○2 (au Noeud ○ 1 la solution est entière).
Pas 1. Choisir une variable non entière pour brancher :
3 : x1 = 4, 5 x2 = 0, z3 = 22, 5
Soit x2 ≤ 0 Région ○
4 : Impossible
Soit x2 ≥ 1 Région ○
6. Solution de problèmes entiers
6.2 Méthode de branch and bound
x2
(2)
5
1 2
4
3
z
P1
2 4
P0
1
1
P2
1 2 3 4 P3 5 6 x1
3 (1)
Stop : on peut couper le Noeud ○3 : sa solution est moins
1
bonne que celle entière du Nœud ○.
Solution optimale : x∗1 = 3, x∗2 = 2, zP∗ N E = 23.
6. Solution de problèmes entiers
6.2 Méthode de branch and bound
c) Arbre de branch and bound :
z0 = 23,75
x 1 = 3,75
x 2 = 1,25
x1 3 x1 4
z1 = 23 z2 = 23,33
x1 = 3 x1 = 4
x2 = 2 x 2 = 0,833
x2 0 x2 1
z3 = 22,5
x 1 = 4,5 impossible
x2 = 0
6. Solution de problèmes entiers
6.3 Méthode de branch and bound
a) Résoudre la relaxation linéaire :
(2)
x2
(1)
6
(3)
min z = x1 + 2x2
4
−2x1 + 2x2 ≥ 1 (1)
P0
x1 + x2 ≥ 6, 5 (2)
3
z =4
z s.c.q.
x2 ≤ 6 (3)
z =2 2 x1 , x2 ≥ 0
1 2 3 4 5 6 x1
0 : x1 = 3, x2 = 3, 5 z0 = 10
Nœud ○
6. Solution de problèmes entiers
6.3 Méthode de branch and bound
b) Méthode de Branch and Bound :
Pas 1. Choisir une variable non entière pour brancher : x2 :
1 :
Soit x2 ≤ 3 : Nœud ○ problème non réalisable
2 :
Soit x2 ≥ 4 : Nœud ○ x1 = 2, 5; x2 = 4; z2 = 10, 5
(2)
x2 (1)
(3)
5
2
4
P2
3 P0
z =4
1
z =2 2
1 2 3 4 5 6 x1
6. Solution de problèmes entiers
6.3 Méthode de branch and bound
Pas 2. Choix du nœud à diviser : diviser
2 car le nœud ○
le nœud ○ 1 donne un problème non réalisable.
z0 = 10
x1 = 3
x 2 = 3, 5
x2 3 x2 4
z2 = 10,5
impossible x 1 = 2, 5
x2 = 4
Pas 1. Choix d’une variable pour brancher : x1 :
3 : z3 = 11 x1 = 2; x2 = 4, 5
Soit x1 ≤ 2 : Nœud ○
4 : z4 = 11 x1 = 3; x2 = 4
Soit x1 ≥ 3 : Nœud ○
6. Solution de problèmes entiers
6.3 Méthode de branch and bound
(2)
x2 (1)
z 6
(3)
5
P3
2
P4
4
P2
P0
z =4 3
1
2
z =2 3 4
1 2 3 4 5 6 x1
Critère d’arrêt :
Au Nœud ○ 4 , on a une solution entière : couper la branche.
Nœud ○,3 z3 = 11 est dominée par z4 : couper la branche.
Solution optimale du problème en nombres entiers :
x∗1 = 3, x∗2 = 4, zP∗ N E = 11
6. Solution de problèmes entiers
6.3 Méthode de branch and bound
c) Arbre de branch and bound :
z0 = 10
x1 = 3
x 2 = 3, 5
x2 3 x2 4
z2 = 10,5
impossible x 1 = 2, 5
x2 = 4
x1 2 x1 3
z3 = 11 z4 = 11
x1 = 2 x1 = 3
x 2 = 4,5 x2 = 4
