Programme Linéaire en nombres entiers
(PLNE)
Dans cette partie, on ne considérera que des
programmes linéaires en nombres entiers.
(c-à-d les variables xi sont des entiers positifs ou nuls)
Approche intuitive immédiate :
§ On relaxe les variables ( les considérer entant que
réels)
§ On arrondi la solution.
En général, cela ne marche pas !
[Link] ENSA de Tanger 1
Contre exemple
max 3 x1 + 13 x2
sc.
2 x1 + 9 x2 ≤ 40
11 x1 – 8 x2 ≤ 82
x1, x2 ≥ 0
x1, x2 entiers
[Link] ENSA de Tanger 2
[Link]ère
x*=(2,4)!!
2x1+9x2=40
11x1-8x2 = 82
Voisins non x*continu=(9.2,2.4)
admissibles
[Link] ENSA de Tanger 3
Méthode par séparation et évaluation :
(Branch and Bound)
§ Soit un programme linéaire en nombres entiers
suivant :
Max z= c.x
s.c.
Ax <= b
X entier positif ou nul
[Link] ENSA de Tanger 4
Relaxation
§ On considère sa relaxation linéaire :
§ Max z = c.x
§ s.c.
Ax <= b
x≥0
x réel
[Link] ENSA de Tanger 5
On calcule à chaque étape:
Ø le coût optimal de la relaxation linéaire.
Ø Si la solution de la relaxation est entière, pas
besoin de partitionner le sous-problème.
Sinon, on choisit un x*i non entier, et on crée deux
sous-problèmes en ajoutant les contraintes
xi ≤ [x*i ] et xi ≥ [x*i ] +1
[Link] ENSA de Tanger 6
Séparation
§ On partitionne F en un une collection finie de sous-ensembles
F1,…,Fk.
§ On résout séparément les problèmes
Max z = c.x
s.c. x ∈ Fi
§ A priori, les sous-problèmes peuvent être aussi difficiles que le
problème original. Dans ce cas, on applique le même système et
on partitionne le/les sous-problèmes.
§ On obtient l’arborescence suivante :
[Link] ENSA de Tanger 7
F
F1 F2 Fk
F21 F22 F2m
F211 F212 F21n
[Link] ENSA de Tanger 8
Exemple 1:
§ Soit le problème F suivant :
max z = - x1 + 2x2
S.C
-4x1 + 6x2 ≤ 9
x1 + x2 ≤ 4
x1, x2 ≥ 0
x1, x2 entiers
[Link] ENSA de Tanger 9
En appliquant la méthode de Branch and Bound on
obtient l’arborescence suivante :
F x* = (1.5,2.5) , z = 3.5
x2 ≥ 3 x2 ≤ 2
F1 Non adm. F2 x* = (0.75,2) , z = 3.25
x1 ≥ 1 x1 ≤ 0
F21 F22
x* = (1,2) , z = 3 x* = (0,1.5) , z = 3
[Link] ENSA de Tanger 10
Remarque:
Ø Le nombre de manières de choisir un sous-
ensemble de n éléments est 2n !.
Ø Si n est grand, il est impossible de considérer
toutes les possibilités (210 = 1024 !!).
Ø Un algorithme efficace devrait obtenir la solution
optimale en examinant un très petit nombre de
solutions.
[Link] ENSA de Tanger 11
Exemple 2 : Investissement
§ Une société dispose de 1 400 000 $ à
investir. Les experts proposent 4
investissements possibles:
Coût Bénéfice Rendement
Inv. 1 500 000 1 600 000 3.20
Inv. 2 700 000 2 200 000 3.14
Inv. 3 400 000 1 200 000 3.00
Inv. 4 300 000 800 000 2.67
[Link] ENSA de Tanger 12
Modélisation : C’est un PLNE à variables binaires
§ Variables de décision : xi, i=1,…,4
§ xi = 1 si investissement i est choisi
§ xi = 0 sinon
§ Objectif : maximiser bénéfice
max 16 x1 + 22 x2 + 12 x3 + 8 x4
§ Contrainte : budget d’investissement
5 x1 + 7 x2 + 4 x3 + 3 x4 ≤ 14
[Link] ENSA de Tanger 13
Voici l’arborescence du problème :
(Solution optimale F1212: (0,1,1,1) de max 42 00000)
F
x3=1 x3=0
F1 F2 x4=1
x2=1
x2=0
x4=0
F11 F12 F22
x1=0 F21 x2=1
x1=1
x2=0
x4=0 F121 F222
x4=1 F122 F221
F1211
F1212 F2222
F2221
[Link] ENSA de Tanger 14
Autre application : Problème du sac à dos
§ Un campeur part en randonnée dans la montagne.
§ Il ne peut emporter dans son sac à dos qu’un poids limité à
P.
§ Chaque article i qu’il peut potentiellement emporter pèse
pi et lui procure une utilité ui pour sa randonnée.
§
§ Question :
§ Quels articles emporter pour maximiser son utilité sans
dépasser la limite de poids ?
[Link] ENSA de Tanger 15
C’est aussi un PLNE à variables binaires
Variables de décision
§ xi = 1 si Jo emporte l’article i
§ xi = 0 sinon
max u1x1+u2x2+…+unxn
§ s.c.
p1x1+p2x2+… +pnxn ≤ P
x1,…,xn ∈ {0,1}
[Link] ENSA de Tanger 16
Application:
En utilisant Matlab, donner l’arborescence du problème du sac à
dos ci dessous.
Retrouver la solution par la fonction prédéfinie « bintprog »
max z = 10 x1 + 8x2+5x3
s.c. 6x1 + 5x2 +4x3 ≤ 9
x1, x2, x3 dans {0,1}
[Link] ENSA de Tanger 17
