Recherche opérationnelle
Le problème de transport
- Présentation du cours
- Qu'est-ce que la recherche opérationnelle
- Modéliser un problème de décision
- Le programme linéaire et ses formes
- La résolution graphique
- Le simplexe, la méthode
- Le simplexe, les cas particuliers
- La dualité
- L'analyse de sensibilité
- Le problème de transport
- Le problème d'affectation
- Les graphes, vocabulaire et représentation
- Le plus court chemin
- Le flot maximal
- L'ordonnancement de projet
- La programmation en nombres entiers
- Gestion des stocks et files d'attente
Recherche opérationnelle
Chapitre 8 : Le problème de transport
Un programme particulier
L’énoncé général
Le problème
m origines de capacités a_i, n destinations de besoins b_j, un coût unitaire c_{ij} par liaison.
\min \; \sum_i \sum_j c_{ij}x_{ij} \quad\text{sous}\quad \sum_j x_{ij} = a_i, \quad \sum_i x_{ij} = b_j, \quad x_{ij} \geq 0
Ce qui le rend spécial
Tous les coefficients de la matrice valent 0 ou 1, et chaque variable apparaît dans exactement deux contraintes.
Cette structure a une conséquence remarquable : si les a_i et les b_j sont entiers, la solution optimale l’est aussi, sans qu’on ait rien imposé.
L’exemple du cours
Trois usines, trois dépôts
| D_1 | D_2 | D_3 | Offre | |
|---|---|---|---|---|
| U_1 | 8 | 6 | 10 | 30 |
| U_2 | 9 | 7 | 4 | 45 |
| U_3 | 3 | 4 | 9 | 25 |
| Demande | 20 | 50 | 30 | 100 |
Le problème est équilibré
\sum_i a_i = \sum_j b_j = 100
S’il ne l’était pas, on ajouterait une origine ou une destination fictive, à coût nul, pour absorber la différence.
Trouver une première solution
Le coin nord-ouest
La méthode la plus simple
Partir de la case en haut à gauche, y mettre le maximum possible, rayer la ligne ou la colonne saturée, recommencer.
Le résultat
x_{11} = 20, x_{12} = 10, x_{22} = 40, x_{23} = 5, x_{33} = 25.
C = 20(8) + 10(6) + 40(7) + 5(4) + 25(9) = 745
Son défaut, évident
Elle ne regarde jamais les coûts. Elle est rapide, elle donne une solution réalisable — et elle est mauvaise.
On s’en sert quand on a l’intention d’améliorer ensuite.
Le moindre coût
La méthode raisonnable
Remplir d’abord la case la moins chère, au maximum possible, rayer, recommencer.
Le déroulement
c_{31}=3 : x_{31} = 20. Puis c_{23}=4 : x_{23} = 30. Puis c_{32}=4 : x_{32} = 5.
Reste D_2 à 45 : x_{12} = 30 et x_{22} = 15.
C = 20(3) + 30(4) + 5(4) + 30(6) + 15(7) = \mathbf{485}
L’écart
745 contre 485 : 35 % d’économie, pour une méthode à peine plus longue.
Le choix de la solution initiale n’est pas un détail : il décide du nombre d’itérations qui suivront.
Vérifier l’optimalité
La méthode des potentiels
MODI
On cherche des nombres u_i et v_j tels que, pour toute case occupée,
u_i + v_j = c_{ij}
On pose u_1 = 0 pour lever l’indétermination, et l’on propage.
Sur notre solution
Cases occupées : (1,2), (2,2), (2,3), (3,1), (3,2).
u_1 = 0,\; v_2 = 6,\; u_2 = 1,\; v_3 = 3,\; u_3 = -2,\; v_1 = 5
Le test des cases vides
Le coût marginal
Pour chaque case vide : \Delta_{ij} = c_{ij} - (u_i + v_j)
Si tous les \Delta_{ij} \geq 0, la solution est optimale.
Les quatre cases vides
| Case | c_{ij} | u_i + v_j | \Delta_{ij} |
|---|---|---|---|
| (1,1) | 8 | 5 | +3 |
| (1,3) | 10 | 3 | +7 |
| (2,1) | 9 | 6 | +3 |
| (3,3) | 9 | 1 | +8 |
Ce que le test conclut
Intuition
Tous positifs : la solution du moindre coût était déjà optimale, et son coût de 485 est le minimum.
Utiliser une case vide coûterait au mieux 3 de plus par unité transportée.
Le plan optimal
Si un delta était négatif
Le cycle d’amélioration
On entre dans la case de \Delta le plus négatif, et l’on construit le cycle unique qui la relie aux cases occupées, en alternant + et -.
On transfère la plus petite quantité marquée -, ce qui vide une case et en remplit une autre.
Pourquoi un cycle, et un seul
Chaque ligne et chaque colonne doivent conserver leur total : on ne peut ajouter quelque part sans retrancher ailleurs sur la même ligne, puis compenser sur la colonne.
Le cycle est la plus petite correction qui préserve les marges.
La dégénérescence
Ce qu’il faut compter
Le nombre de cases occupées
Une solution de base d’un problème de transport en compte exactement
m + n - 1 \qquad\text{ici}\qquad 3 + 3 - 1 = 5
S’il y en a moins
Une ligne et une colonne se sont saturées en même temps. On place alors un zéro fictif dans une case vide bien choisie, pour rétablir le compte.
Sans ce zéro, la propagation des potentiels s’arrête en chemin.
Ce qu’il faut retenir
Le résumé du chapitre
Six points
- Le problème de transport est un programme linéaire de structure entière : la solution l’est aussi.
- Un problème déséquilibré s’équilibre par une origine ou destination fictive.
- Coin nord-ouest : rapide et mauvais — 745 ici.
- Moindre coût : à peine plus long, 485 — soit 35\,\% de moins.
- MODI teste l’optimalité par \Delta_{ij} = c_{ij} - (u_i + v_j) \geq 0.
- Une base compte m + n - 1 cases : en dessous, il faut un zéro fictif.
La suite
Le chapitre 9 traite le cas extrême du transport : toutes les offres et toutes les demandes valent un. C’est le problème d’affectation, et il a une méthode à lui.
Ressources du chapitre
- Diapositives
- Polycopié du chapitre
- Exercices corrigés
- Application interactive
- — Vidéo
- QCM (bientôt)