Download Rapport final

A.2 Formalisation sous forme de programme linéaire en nombres entiers
du p-median problem
Dans cette seconde annexe, nous décrivons la formalisation sous forme de programme linéaire en
nombres entiers du p-median problem (décrit en Section 3.2) proposée dans Revelle et Swain (1970).
Dans un premier temps, nous détaillons les données et les variables de décision du modèle. Le
programme linéaire complet est ensuite exposé.
Les données nécessaires au modèle sont les suivantes :
Les deux groupes de variables de décision suivants interagissent dans le modèle :
Fort des données et des variables de décision présentées auparavant, Revelle et Swain (1970)
propose la formalisation [PMP] suivante. [PMP] est un programme linéaire en nombres entiers
modélisant le p-median problem.
[PMP] vise à réduire les coûts, pondérés par les demandes, d'affectation des clients aux localisations
sélectionnées (6). Chaque client est rattaché à une unique localisation (7) et la localisation concernée
doit être sélectionnée (8). (9) assure pour sa part qu'exactement p localisations sont sélectionnées.
(10) et (11) définissent enfin les domaines de définition des variables de décision.
La formalisation du Uncapacitated Facility Location Problem (et par extension du Capacitated Facility
Location Problem) découle de [PMP]. La modélisation du UFLP est obtenue en ôtant de [PMP] les
contraintes (9) et en ajoutant un terme tenant compte des coûts fixes à la fonction objectif (6).
39