3.5 Quelques problèmes classiques d'optimisation
combinatoire 28
-Page 28-
3.5 Quelques problèmes classiques d'optimisation
combinatoire
3.5.1 Problème de transport
Le problème de transport est un problème facile
de l'optimisation,il consiste à déterminer la façon la
plus efficace de transporter des quantités de marchandises depuis un
ensemble de sources vers un ensemble de destinations.
Le problème de transport peut être
formulé de la manière suivante : supposons que nous ayons m
sources et n destinations. Chaque source i dispose d'une
quantité d'offre ai à transporter,et chaque destination
j a une quantité de demande bj à satisfaire. Le
coût de transporter une unité de marchandise de la source i
à la destination j est cij. Nous
devons déterminer le plan de transport qui minimise le coût total
tout en satisfaisant les contraintes d'offre et de demande.
3.5.1.1 Formulation mathématique du
problème
· Les variables de décision:
xij est la quantité à
transportée de la source i ; i = {1, . . . , m}
à la destination j ; j = {1,...,n}
· Les contraintes:
1. La disponibilité: la
quantité de marchandise provenant de la source i doit
être égale à la quantité d'offre ai
disponible à cette source.
2. La demande: la quantité de
marchandise livrée à la destination j doit être
égale à la quantité de demande bj à
satisfaire à cette destination.
· La fonction objectif: Minimiser le
coût total de transport, représenté par la somme des
coûts de transport unitaires cij multiplié par
la quantité de marchandise transportée xij pour chaque
paire source-destination.
· Le modèle mathématique:
Le problème de transport est donné par le programme
linéaire (PL) (3.1) :
3.5 Quelques problèmes classiques d'optimisation
combinatoire 29
?
????????????????? ?
??????????????????
m i=1
cijxij
Xn j=1
xij = ai,
Minimiser Z =
sous contraintes :
Xn
j=1 m
i=1
?i = {1,...,m}
(3.1)
xij = bj, ?j = {1, ... , n}
xij = 0, ?i = {1, ... , m} et ?j = {1, ... , n}
xij ? N, ?i = {1, ... , m} et ?j = {1, ... , n}
à la destination j, ai est la quantité d'offre
disponible à la source i et bj est la quantité de demande
à satisfaire à la destination j.
3.5.2 Problème d'affectation
Le problème d'affectation est un cas particulier du
problème de transport dans lequel chaque source est affectée
à une seule destination, il consiste à établir des liens
entre les éléments de deux ensembles distincts, de telle sorte
à minimiser le coût total de l'affectation en respectant des
contraintes d'unicité de lien pour chaque élément.
Étant donnée n tâches et n agents.Une
affectation consiste à affecter la tâche i; i = {1, ... , n}
à l'agent j ; j = {1, ... , n} de sorte que :
· chaque agent j ait une et une seule tâche à
effectuer à la fois.
· chaque tâche i est attribuée à un
seul agent au même temps.
Le coût d'affectation d'une tâche i un agent j est :
Cij.
Le problème d'affectation consiste à trouver une
affectation de coût minimum.
| 
