IFT 1575 Automne 2024

Devoir 3
Modèles de recherche opérationnelle

Karim Ndoye
Matricule : 20289824

Partie : Questions à développement

Question 1 : Centres de partage de vélos
Modèle de programmation linéaire en nombres entiers :
— Variables de décision : xi ∈ {0, 1} : Indique si un centre de partage de vélos est installé dans l’arron-
dissement i (1 s’il est installé, 0 sinon).
— Paramètres : dij : Temps de déplacement moyen entre l’arrondissement i et le site j (en minutes).
Matrice des temps :
1 2 3 4 5 6
1 0 10 20 30 30 20
2 10 0 25 35 20 10
3 20 25 0 15 30 20
4 30 35 15 0 15 25
5 30 20 30 15 0 14
6 20 10 20 25 14 0
— Contraintes : Chaque arrondissement doit avoir un centre accessible en moins de 15 minutes :
X
xj ≥ 1, ∀i ∈ {1, 2, 3, 4, 5, 6}
j:dij ≤15

— Fonction objectif : Minimiser le nombre total de centres de partage installés :

6
X
min xj
j=1

Modèle complet :
6
X
Minimiser xj
j=1

Sous contraintes :
x1 + x2 ≥ 1 (pour i = 1)
x1 + x2 + x6 ≥ 1 (pour i = 2)
x3 + x4 ≥ 1 (pour i = 3)
x3 + x4 + x5 ≥ 1 (pour i = 4)
x5 + x6 ≥ 1 (pour i = 5)
x2 + x6 ≥ 1 (pour i = 6)
xj ∈ {0, 1}, ∀j
—

1
Question 2 : Épicerie Locale
Modélisation comme problème de flot à coût minimal
Graphe représentant le problème :

10 15 8
F1 Dépôt A

35
10 20 12

F2 B
25

Modèle en programmation linéaire :

— Variables de décision : xij : Nombre de lots transportés entre i et j, où i, j sont des nœuds du graphe.
— Fonction objectif : Minimiser le coût total de transport :
X
min cij xij
(i,j)

Où cij est le coût unitaire de transport entre i et j.

— Contraintes :
1. Capacités des fermes : X X
xF 1,j ≤ 300, xF 2,j ≤ 500
j j

2. Satisfaction des demandes :

X X
xi,A = 200, xi,B = 400
i i

Justification : Chaque supermarché doit recevoir exactement le nombre de lots demandé.

3. Conservation du flot au dépôt :
X X
xi,D = xD,j
i j

Justification : Le dépôt ne stocke pas de produits ; tout ce qui entre doit en sortir.
4. Non-négativité :
xij ≥ 0 ∀(i, j)

2
Question 3 : Hôpital et médecins
Modélisation comme problème d’affectation
Graphe représentant le problème :

6
P1 M1

P2 M2
4
3 7
5
9

P3 M3
2

P4

Modèle en programmation linéaire :

— Variables de décision : xij : 1 si le patient i est assigné au médecin j, 0 sinon.
— Fonction objectif : Minimiser la durée totale de traitement :
X
min cij xij
i,j

Où cij est la durée estimée de traitement pour le patient i par le médecin j.
— Contraintes :
1. Chaque patient est assigné à un médecin :
X
xij = 1, ∀i
j

2. Chaque médecin traite un patient : X

xij = 1, ∀j
i

3
 3. Non-négativité et binarité :
xij ∈ {0, 1}, ∀(i, j)
4. Respect des compatibilités : Par exemple, x2,1 = 0 (le médecin M 1 ne peut pas traiter le patient
P 2).

Partie (b) : Résolution avec l’algorithme Hongrois

Nous résolvons le problème d’affectation à l’aide de l’algorithme Hongrois. Voici les étapes :

Matrice initiale : La matrice des durées de traitement (cij ) est donnée comme suit :

M1 M2 M3
P1 6 8 7
P2 − 4 5
P3 3 9 2
P4 5 6 8
Le symbole − indique que M 1 ne peut pas traiter P 2 (c21 = ∞).

Étape 1 : Réduction des lignes Pour chaque ligne, on soustrait le minimum de cette ligne à tous les
éléments de la ligne.

M1 M2 M3
P1 0 2 1
P2 − 0 1
P3 1 7 0
P4 0 1 3

Étape 2 : Réduction des colonnes Pour chaque colonne, on soustrait le minimum de cette colonne à tous
les éléments de la colonne.

M1 M2 M3
P1 0 2 1
P2 − 0 1
P3 1 7 0
P4 0 1 3
(Ici, la matrice reste identique car les colonnes M 1, M 2, et M 3 contiennent déjà un zéro.)

Étape 3 : Attribution initiale - On sélectionne les zéros non couverts (le moins possible par ligne ou
colonne). - Les attributions sont : - P 1 → M 1, - P 2 → M 2, - P 3 → M 3.

Résultat final : La solution optimale est donnée par les affectations suivantes : - P 1 traité par M 1 (6 heures),
- P 2 traité par M 2 (4 heures), - P 3 traité par M 3 (2 heures), - P 4 non traité (pas inclus dans cette phase car
il y a plus de patients que de médecins disponibles).
La durée totale minimale est :
6 + 4 + 2 = 12 heures.