CHAPITRE 6

Généralisations du
modèle d’optimisation
d’un réseau de
ravitaillement

02/28/25 Atidel HADJ-ALOUANE 1

 I
Formulation générale
basée sur les chaînes

02/28/25 Atidel HADJ-ALOUANE 2

 Introduction
 Produits acheminés vers des zones de
consommation par le biais de chaînes
d’approvisionnement incluant:
 Au moins un entrepôt (ou magasin local)
 Au plus une usine

 On suppose aussi que chaque site

d’entreposage peut accueillir plusieurs
types de capacité d’entreposage

02/28/25 Atidel HADJ-ALOUANE 3

 Options de ravitaillement
pour un réseau à deux
échelons

Schéma général du réseau à deux échelons

02/28/25 Atidel HADJ-ALOUANE 4

 Données de base
 K: ensemble des types de capacité d’entreposage. On
suppose que P peut être partitionné en sous-
ensembles mutuellement exclusifs Pk de produits
nécessitant des ressources d’entreposage différentes:
 Ex: produits conservés soit à l’intérieur (P1), à l’extérieur (P2)
ou dans des frigos (P3)  K={1,2,3}, P=P1P2 P3
 U: ensemble des sites d’usines (uU)
 W: ensemble des entrepôts (w) ou de magasins (m)
(w,m W)
 S: ensemble des sites intermédiaires du réseau
(s S=U  W)
 Dp: ensemble des zones de consommation du produit
p (d D=p Dp)
02/28/25 Atidel HADJ-ALOUANE 5
 Données de base (suite1)
 N: ensemble de tous les nœuds du réseau (n  PS D)
 I: ensemble de toutes les chaînes réalisables dans le
réseau, compte tenu des contraintes physiques de
gestion et de service.
 Ci: ensemble ordonné des nœuds de la chaîne i. Deux
types de chaîne:
 (p,w,m,d)
 (p,m,d)
 ci: coût total encouru par produit ravitaillé par la chaîne
d’approvisionnement i (à calculer plus tard)
 pi: produit associé à la chaîne i (chaque chaîne débute
par un produit source unique)
 di: zone associée à la chaîne i

02/28/25 Atidel HADJ-ALOUANE 6

 Données de base (suite2)
 as = coût fixe de l’exploitation du nœud s durant
l’année considérée
 xpd: demande annuelle du produit p par la zone d
 bks: capacité actuelle/potentielle du site s en
ressource de type k (si sU alors kP)
 Xks: flux minimal requis pour que l’on puisse utiliser
la capacité de type k au site s
 ep : taille moyenne des produits de la famille p (en
unité appropriée pour la capacité de type du sous-
ensemble Pk contenant p)
Modèle d’optimisation
02/28/25 Atidel HADJ-ALOUANE 7
 Pré-Processeur
 Formulation précédente comprend un nombre élevé
de variables:
 |S| variables Ys
 |PxSxD| variables Fi

 Pré-processeur permet d’éliminer, à priori,

 Variables et contraintes non-nécessaires
 Les solutions non réalisables par rapport aux critères de
 Service
 Fonctionnalité
 Structure organisationnelle

02/28/25 Atidel HADJ-ALOUANE 8

 Calcul des coûts ci
 Coût unitaire ci de flux de p vers d dépend
du type de la chaîne:

 p
Ci = {p,w,m,d} w m d

Coûts: ci = Tpw+ Gpw+ Hwi + Tpwm+ Gpm+ Hmi +

Tpmd

 Ci’ = {p, m,d} p m d

Coûts: ci’ = Tpm + Gpm+ Hmi’ +

Tpmd
02/28/25 Atidel HADJ-ALOUANE 9
 Coûts composants ci
 Tps = valeur moyenne unitaire des produits de la
famille p (ou des matériaux requis pour fabriquer p si
s est une usine) qui sont achetés à l’extérieur par le
nœud s:
 Prix d’achat, coût de passation de commande, coût de
transport

 Gps = coût moyen de réception, transformation et

manutention des produits p au site s

 Tpwm = Coût moyen de transport de p entre nœuds

internes w et m.
Il inclut le coût d’immobilisation des stocks en transit
et les coûts de passation de commande
02/28/25 Atidel HADJ-ALOUANE 10
 Coûts pertinents (suite1)
 Tpmd = Coût unitaire de livraison de p aux clients de la
zone d.
 Si la distance entre magasins et clients est faible, ce taux
est souvent indépendant de la distance et de la charge

 vni = valeur moyenne du produit p au nœud n lorsqu’il

provient de la chaîne i. Par ex, pour Ci={p,w,m,d}
vmi = Tpw + Gpw + Hpw + Tpwm

 rpw = taux du coût d’immobilisation des stocks du

produit p à l’entrepôt w (en $/$/année).

 ni : temps de réponse moyen lorsque le produit pi est

fourni au nœud n par la chaîne Ci
02/28/25 Atidel HADJ-ALOUANE 11
 Coûts pertinents (suite2)
 Hwi = Coût moyen d’immobilisation des
stocks requis ($/unité de flux) du produit pi
à l’entrepôt w lorsqu’il provient de la chaîne
Ci : H wi ρwi vwi rpw i

Où wi : p de produit pi livrés à

durée moyenne des stocks
Ci’={p,m,d}
l’entrepôt w par la chaîne C wi Ci={p,w,m,d}
i
mi’
Hmi’  Hmi! Hmi’ w
m mi Hwi
d Hmi
02/28/25 Atidel HADJ-ALOUANE 12
 II
Prise en compte des
économies d’échelle
II-1
Modélisation des coûts

02/28/25 Atidel HADJ-ALOUANE 13

 II-1-1
Coûts associés aux arcs du réseau

02/28/25 Atidel HADJ-ALOUANE 14

Schéma général et données
vaj
(Qj, tj)
Arc j:
Fj
(source) (destination)

 Qj = taille des cargaisons de produit sur l’arc j

 tj = temps de transit en années
 Fj = flux de produits sur l’arc j pour l’année
considérée:
Rj = Qj/Fj = intervalle de temps entre deux expéditions
successives
 vaj = valeur moyenne unitaire des produits qui
circulent sur l’arc j
02/28/25 Atidel HADJ-ALOUANE 15
 Nature des coûts
 Pour un mode de transport donné, la nature
de la fonction coût associée aux arcs dépend
de la politique de lotissement utilisée:

1. La taille des lots est prédéterminée

2. La fréquence des expéditions est prédéterminée

(par ex: une navette tous les lundi)

3. La taille des lots est optimisée à l’aide d’un

algorithme approprié.

02/28/25 Atidel HADJ-ALOUANE 16

(1) Taille des lots prédéterminée

 
Coût d’achat annuel: Cjp(Qj)/Q j Fj 
Cjp(Qj)
Prix de la
(Pour un temps
command
de réponse donné
e
)

Taille de la commande (Qj)

02/28/25 Atidel HADJ-ALOUANE 17

 (1) Taille des lots prédéterminée (suite1)
 Coût de passation de commandeKj:(Fj/Q j)
où Kj = coût fixe par commande pour les lots sur l’arc j

 Coût (C
annuel de transport :
T (Qj)/Q j)Fj
j

( CjT (Qj)  ce au chap. 3)

CjT(Qj)
Coût de transport
source-destination
(Pour un délai de
livraison donné )
Coût d’arrêt
+
coût distance
(Q j)
Taille de la cargaison
02/28/25 Atidel HADJ-ALOUANE 18
(1) Taille des lots prédéterminée (suite2)
 Coût annuel des stocks en transit:r vja tj Fj

Où r = taux du coût du capital immobilisé dans les

stocks en transit
tj Fj = stock moyen en transit durant l’année

 Coût total annuel:

[Cjp(Qj)Kj CjT (Qj)r vjatj Qj]Fj/Q j

 Linéaire en Fj

02/28/25 Atidel HADJ-ALOUANE 19

(2) Fréquence des expéditions prédéterminée
(navettes)

 Rj-1 = Fj/Qj = fréquence des expéditions

 Coût total annuel:

p
[C (RjFj)CjT(RjFj)r vjatj Rj Fj]/R j
j

Rq: coût de commande n’est plus pertinent

 Fonction coût non linéaire en Fj (peut être

linéaire par partie).
02/28/25 Atidel HADJ-ALOUANE 20
(3) Taille des lots optimisée

 Résoudre C(Qj)/ Qj 0

où C(Qj)[Cjp(Qj)Kj CjT(Qj)r vjatj Qj]Fj/Q j

 En général, des bornes sup et inf

s’appliquent à chaque cargaison

02/28/25 Atidel HADJ-ALOUANE 21

 II-1-2
Coûts associés aux nœuds du
réseau

02/28/25 Atidel HADJ-ALOUANE 22

Schéma général et données

Processus
(Q, ) Xps de demande

s
 Xps = flux total du produit p dans le nœud s
pour l’année considérée:

X ps   i  p,s  Ci Fi

02/28/25 Atidel HADJ-ALOUANE 23

 Données et variables
 Variables supplémentaires:
 Vps = valeur du flux total du produit p dans le nœud s :
Vps i  p,s   Ci
vsi Fi
 Vps/Xps = valeur moyenne du produit p circulant
dans le nœud s

 Tps = délai d’approvisionnement cumulatif du produit p

circulant dans le nœud s

T ps i  p,s   C si Fi

i

 T /Xps
ps = délai d’appro. moyen des produits p
circulant dans le nœud s
02/28/25 Atidel HADJ-ALOUANE 24
 Types de coûts
 Coûts fixes:
 (as) indépendants des flux et des niveaux de
stocks, mais doivent tenir compte des méthodes
de financement utilisées.
 Coûts d’entreposage et de production:
 indépendants du niveau des stocks
 dépendent de technologie de
 manutention, production, stockage,information
 Coûts de stockage:
 dépendants du niveau des stocks et par
conséquent des flux X de produits
02/28/25 Atidel HADJ-ALOUANE 25
Coûts d’entreposage et de production

02/28/25 Atidel HADJ-ALOUANE 26

 Coûts de stockage
 dépendent du niveau des stocks
 il faut établir une relation entre
 flux de produit (X) pour un point de stockage, et
 le niveau de stock requis, compte tenu
 des délais de livraison/production pertinents

 Utiliserquelques principes de gestion des

stocks et de prévision:
 Variation de la demande
 Erreur de prévision
 Stock de sécurité
02/28/25 Atidel HADJ-ALOUANE 27
 calcul des coûts de stockage

 Variation
de la demande en fonction de la
demande moyenne:
b
σx dμ x

 x = demande moyenne par période (flux)

 x = écart type de la demande pour une période
 d, b = paramètres estimés par régression
(log x = log d + b log x)

la valeur de b  [0.7, 0.9]

02/28/25 Atidel HADJ-ALOUANE 28
 calcul des coûts de stockage
(suite1)
 Variation de la demande en fonction du
temps : c
σx (t)t σx

 t = nombre de périodes
 x(t) = écart type de la demande pour t périodes
 x = écart type de la demande pour une période
 c = paramètre estimé par régression
(log (x(t)/ x) = c log t) c
b
σx (t)t d μ x
 par substitution:
02/28/25 Atidel HADJ-ALOUANE 29
 Calcul des coûts de stockage
(suite2)
 Stock de sécurité :
 Mesure de service:  = proportion des cycles
d’appro. sans rupture.
 k() = facteur de sécurité
 SS = stock de sécurité :
c b
SS k () σx(t) k() t d μ x

 Généralement, pour un flux moyen, X, d’une

famille de produits similaires avec un délai
d’appro. moyen  : c b
SS a  X
02/28/25 Atidel HADJ-ALOUANE 30
 Calcul des coûts de stockage
(suite3)
 Stock Cyclique moyen: SC Q/2

où Q = taille des lots de fabrication/

approvisionnement
I(X) Q/2  SS
 Stock (total) moyen :

Q(X) K0 Xb
0

 Si Q est optimisée selon la demande:

Pour la quantité économique b0=0.5

I(X) a' (c') Xb'

On aura alors :
02/28/25 Atidel HADJ-ALOUANE 31
Calcul des coûts de stockage (suite
4)

02/28/25 Atidel HADJ-ALOUANE 32

 Calcul des coûts de stockage
(suite5)
 Unbon système de planification et de
contrôle  économies d’échelle  b’ < 1
 Niveau de stock du produit p à l’entrepôt w :
cpw
 Tpw  bpw
Ipw (Xpw,Tpw) apw   X
 Xpw 
 
r  Vpw 
multiplié par le coût d’immobilisation des stocks:
pw  X pw 
 
 coûts de stockage =
 Vpw 
h pw (X pw,Vpw, T pw) r pw   I (X , T )
 X pw  pw pw pw
 
  cpw bpw cpw 1
 r pw a pw Vpw T pw X pw
02/28/25 Atidel HADJ-ALOUANE 33
 Remarques sur les coûts de
stockage
 Les coefficients sont déterminés par régression

 Hpw dépend de  donc des moyens de transport

 Si les entrepôts sont uniformes , la fonction coût

obtenue, pour un produit p, sera la même pour tout
wW

 Si W contient plusieurs types d’installation:

 entrepôts régionaux
 magasins …
il faut séparer les observations par type d’installation.

02/28/25 Atidel HADJ-ALOUANE 34

 II-1-3
Les chaînes de valeurs

02/28/25 Atidel HADJ-ALOUANE 35

 Schéma général et coûts
 Chaîne i incluant une usine u et un entrepôt w
 Coûts sur les arcs: linéaires
 Coûts sur les nœuds: non-linéaires non seulement en Fi
mais aussi en Fi’, associés aux autres chaînes Ci’ qui
acheminent le produit p par les nœuds u et w
 Soient:
 Gpu = Coût de production unitaire du produit p à l’usine
u:
Gpu gpu(X pu)/X pu

 Gpw = Coût d’entreposage unitaire de pPk à l’entrepôt

Gpw gkpw (X pw)/X pw
w:
02/28/25 Atidel HADJ-ALOUANE 36
 Schéma général (suite)
 Hpw = Coût unitaire d’immobilisation des stocks du
produit p à l’entrepôt w :
H pw hpw(X pw,Vpw, T pw)/X pw

Chaîne i p u w d

Coûts des Tpu Tpuw Tpwd

arcs
Coûts des Gpu Gpw+ Hpw
nœuds
 On va inclure dans c seulement les coûts linéaires
i
cl  Tpu Tpuw Tpwd
i

02/28/25 Atidel HADJ-ALOUANE 37

 Notion de valeur
 Valeur d’un produit pour un nœud donné = somme de tous
les coûts unitaires précédents sur la chaîne
d’approvisionnement

vui = Tpu ; vwi = vui + Gpu + Tpuw ;

vdi = vwi + Gpw + Hpw + Tpwd = cil + Gpu + Gpw + Hpw

 Gps et Hpw fonctions des variables de flux

 Hpw est aussi fonction de Vpw, donc des vwi et Fi de toutes
les chaînes fournissant le produit p à l’entrepôt w

 Expressions des vni sont très complexes

02/28/25 Atidel HADJ-ALOUANE 38
 Notion de valeur (suite)
 Coût unitaire sur toute la chaîne i est alors:

ci = vdi = cil + Gpu(F) + Gpw(F) + Hpw(F)

Où F = [Fi] : vecteur des flux

 Evaluation des coûts et valeurs se fait pour un
scénario donné
 Si F est connu  X , V et T peuvent être calculées pour
ps ps ps
chaque nœud intermédiaire s

 Pour F connu, le calcul de Xps, Vps et Tps se fait en partant

de l’échelon 2 (entrepôts W)

02/28/25 Atidel HADJ-ALOUANE 39

Approximation des coûts des
nœuds
 Approximation linéaire
 c-à-d: négliger les économies d’échelle
 on revient au modèle précédent
 perte de l’essence du problème

 Éloignement de l’optimum surtout en cas de

plusieurs échelons.
 Approximation non-linéaire:
 Estimer, a priori, les vsi en s’appuyant sur un
scénario de répartition équilibrée des flux :

Pour un scénario donné F0, on peut calculer

0 0
0 Gps et H ps
X ps, V ps, T ps, puis les
0 0
et les vsi
02/28/25 Atidel HADJ-ALOUANE 40
 Exemple
 Localisation des usines prédéterminée:
Y3=Y4= 1
 Coûts de production/entreposage
gks(X)  ks X β linéaires:
ks

ks =1,  k, s dans

 Chaque famille de produit, p, utilise un type
de capacité différent  Gps = ps pour s=u, w
 hpw concaves et indépendants des délais de
h 1w(X 1w,V1w) 10  
V1w X 0.7, w5,6
livraison (i.e. cpw = 0) X 1w 1w
h2w (X 2w,V2w) 0.4 V X 2w 1
, w5,6
X 2w
2w

02/28/25 Atidel HADJ-ALOUANE 41

 Exemple (suite1)
 Pour évaluer hpw, il faut calculer Xpw et Vpw:

X ps  i Fi et Vps  i vsi Fi

 p,s   Ci
 p,s   Ci
 Il faut trouver toutes les chaînes possibles du réseau
(voir tableau).

6
X 15  i1 Fi
6
Par ex: et V15  i1v5i Fi


 Il faut connaître les flux Fi et les valeurs vwi

 Par ex, pour la chaîne C6 = {1,4,5,9} :
On progresse échelon par échelon: 4 (usine)  5 (entrepôt)  9 (client)

02/28/25 Atidel HADJ-ALOUANE 42

 Exemple (suite2)

02/28/25 Atidel HADJ-ALOUANE 43

 Exemple (suite3)
 Pour l’exemple, on obtient ainsi:
(p,d) = (1,7) : F01 = F04 = F07 = F010 = 50,000/4 = 12,500
(p,d) = (1,8) : F02 = F05 = F08 = F011 =100,000/4 = 25,000
(p,d) = (1,9) : F03 = F06 = F09 = F012 = 50,000/4 = 12,500
(p,d) = (2,7) : F013 = F016 = F019 = F022= 20,000/4 = 5,000
(p,d) = (2,8) : F014 = F017 = F020 = F023= 30,000/4 = 7,500
(p,d) = (2,9) : F015 = F018 = F021 = F024= 60,000/4 = 15,000

Attention! Il ne faut pas dépasser les capacités disponibles aux nœuds

intermédiaires (bpw); sinon, il faut faire une ré-allocation:
 enlever l’excédent proportionnellement des chaînes qui posent problème, et
 réaffecter proportionnellement aux autres chaînes qui incluent le produit p.

02/28/25 Atidel HADJ-ALOUANE 44

Exemple (suite4 et suite 5)

02/28/25 Atidel HADJ-ALOUANE 45

 Exemple (suite6)
D’autre part, on a tout ce qu’il faut pour
calculer la partie linéaire du coût:

cl6 = T14 + G14 + T145 + G15 + T159

= 0 + 4 + 4 + 2 + 5 = 15

Enfin, la fonction objectif de ce problème:

 
minc F i    a wY w  h pw(X pw,V pw ) 
l
i
iI wW pP 
02/28/25 Atidel HADJ-ALOUANE 46
 Autre Approximation
 Approximation non-linéaire séparable du
coût des nœuds:
 En cas d’un seul échelon:
 v
wi et wi sont  les mêmes  chaîne i

 Vpw /Xpw  vpw et Tpw/Xpw  pw

 vpw et pw estimés statistiquement

bpw
h pw(X pw) K pwX pw
 Alors on a: où
cpw
Kpw r pw (vpw) a pw (pw)

 Fonction objectif non-linéaire mais séparable

02/28/25 Atidel HADJ-ALOUANE 47
 II-2
Conditions de faisabilité:
Contrainte de capacité de
stockage

02/28/25 Atidel HADJ-ALOUANE 48

 Contrainte de capacité de
stockage
 Les économies d’échelle associées aux
stocks cycliques et de sécurité ont un impact
sur
 les coûts de stockage
 l’espace d’entreposage requis
X kwYw    e F b
p i kw Yw
 contrainte pPk i   C
p,w  i

 
X kwYw  e p  x pd Z wd bkw Yw
ou pPk  dDp 
limitant le stock moyen (ou flux).
 Cette contrainte doit être remplacée par une autre
impliquant le stock
02/28/25
maximal requis
Atidel HADJ-ALOUANE 49
 Contrainte de capacité de
stockage (suite1)
 Nouvelle contrainte:
X kwYw F ( kw) bSkwYw ;  kw e p X pw
S

pPk

où, pour le type de capacité k à l’entrepôt w:

 XSkw et bSkw sont resp. le niveau min de
capacité et la capacité potentielle de l’entrepôt
exprimés en terme de besoins d’espace
 kw est le flux agrégé des produits utilisant la
capacité de type k et F(kw) est une fonction
concave donnant l’espace requis pour supporter
ce flux agrégé.
02/28/25 Atidel HADJ-ALOUANE 50
 Contrainte de capacité de
stockage (suite2)

contrainte X Y F ( kw) bSkwYw

S
 La
kw w

est non-linéaire :

On cherche X kwF  1(X kw) et bkw F  1(bSkw)

 S

 puis on revient à la contrainte:

X kwYw  e p X pd bkw Yw
pPk

02/28/25 Atidel HADJ-ALOUANE 51

 II-3
Le modèle avec économies d’
échelle (diapo 1
et 2)

02/28/25 Atidel HADJ-ALOUANE 52

 II-4
Méthodes de résolution

02/28/25 Atidel HADJ-ALOUANE 53

(1) Méthodes exactes
 Un nombre de méthodes ont été proposées pour le
problème à un seul échelon:

 Kelly, D.L. and Khumawala B.M., « Solving the staircase

cost facility location problem with decomposition
and piecewise linearisation », EJOR, 75, 1994, 41-61.
 Moon, S., « Application of generalized Benders
decomposition to a nonlinear distribution system
design problem », Naval Research Logistics, 36, 1989,
283-295.

 Pour les cas complexes: on a recours à des

méthodes d’approximation
02/28/25 Atidel HADJ-ALOUANE 54
 (2) Approximation linéaire par
partie pour le cas séparable
 Approcher une fonction de coût concave par une
fonction linéaire par partie.

Hps

Coût du
flux

Demande/période Xps

 Inconvénient: introduire plusieurs nœuds et

contraintes de choix
02/28/25
multiple
Atidel HADJ-ALOUANE 55
02/28/25 Atidel HADJ-ALOUANE
(3) Linéarisation successive
pour le cas séparable
 Souvent on est amené à utiliser des
modèles linéaires car
 Les coûts fournis par les systèmes de
comptabilité sont linéaires
 Extrapolation linéaire des données historiques
 Dans le cas séparable:
 Procéder d’une manière similaire, mais
 estimer les coûts à partir des flux fournis par le
modèle d’optimisation plutôt que des flux
historiques
 Résoudre une séquence de modèles linéaires
02/28/25 Atidel HADJ-ALOUANE 56
(3) Linéarisation successive

(suite1)
1- Commencer par le scénario réalisable équilibré F0

2- Estimer les coûts unitaires à chaque itération à

partir des flux de la solution précédente

3- Arrêt: la différence entre le coût total de deux

solutions successives est suffisamment faible.
Rq: X0  coût unitaire = c(X)/X
X=0  conserver la pente de l’itération
précédente
02/28/25 Atidel HADJ-ALOUANE 57
 (3) Linéarisation successive

(suite2)
c(X)
Coût annuel
c1

c(1)
c0 = [c(X0)/X0]

1 X0 X
Flux unitaire Flux à la 1e itération Flux initial

02/28/25 Atidel HADJ-ALOUANE 58

 (3) Linéarisation
successive (suite3)

02/28/25 Atidel HADJ-ALOUANE 59

 (3) Linéarisation successive

(suite4)
 Approximation des coûts d’immobilisation
des stocks:
hpw(X)
Coût d’immob.
Kpw (Xpw)bpw
des stocks
H(j)pw = [hpw(X(j)pw) )/ X(j)pw]

Xjpw Flux annuel X

h pw (X pw ) H (j)
pw
X pw
 i  p,w  C  pw F i
i
H (j)

02/28/25 Atidel HADJ-ALOUANE 60

(3) Linéarisation successive

(suite5)
 On applique la même approche au coût
d’entreposage :
(j) (j) βps 1
G ps (X )
ps ps

 Modèle à résoudre à chaque itération (PL avec

variables 0-1):
CT(j1) minc i F i a sY s
(j)

iI sS

 
 Sous les mêmes contraintes du modèle de la
(j)
pagec7
i
cl
i
  G (j)
pu
 G(j)
pw
H(j)
pw
uUCi wWCi
02/28/25
Où Atidel HADJ-ALOUANE 61
 Algorithme de linéarisation
successive
1. Calcul des flux initiaux et initialisation.
 Poser j=0, CT(0) = 
 Trouver un scénario de répartition équilibré F0i, iI, en
résolvant Plinit et calculer
0
X ps   i
F0
 p,s
 i  p,s  Ci

2. Linéarisation avec les flux de la solution

précédente et calcul des coûts.
 Pour chaque produit p et chaque nœud s S:

si X(j)ps > 0, calculer les coûts unitaires H(j)ps et G(j)ps

si X(j)ps = 0, conserver les coûts marginaux utilisés à
l’itération précédente
 Calculer le coût unitaire ci(j) des chaînes affectées.
02/28/25 Atidel HADJ-ALOUANE 62
 Algorithme de linéarisation
successive (suite)
3. Résoudre le PL avec variables 0-1 (MIP).
 Trouver la solution optimale Fj+1 de MIP(j), poser j=j+1 et
calculer

X (j)
ps
  F(j)
 p,s
 i  p,s  Ci  i

4. Vérifier la condition d’arrêt.


Si [CT(j-1)-CT(j)]/CT(j-1) > , retourner à l’étape (2)
 Autrement, terminer.
où  est une tolérance acceptable
02/28/25 Atidel HADJ-ALOUANE 63
 Application: exemple de la
page 41
 On estime statistiquement à partir de données
historiques :
 v
1w = 10 et v2w = 5 pour w=5 et w=6
 Dans ce cas: h1w(X1w)10v1wX 1w
0.7 0.7
100X1w w5,6

h2w(X2w)0.4v2wX 2w
1 1
2X2w w5,6
 La solution réalisable initiale trouvée en résolvant
Plinit donne:
u X1u(j) X2u(j) w X1w(j) X2w(j)
3 60000 50000 5 60000 50000
4 140000 60000 6 140000 60000

02/28/25 Atidel HADJ-ALOUANE 64

 Application: exemple de la
page 41 (suite)

 On calcule à partir de ces flux,  i, p, u, w,

d: les coûts et les valeurs:
 vui, Gp(j) , Tpuw, … (voir tableau des valeurs/coûts)

 Trouver la solution de MIP(j)

 Réitérer en utilisant les nouvelles valeurs de

X(j)ps

02/28/25 Atidel HADJ-ALOUANE 65

 Approche générale de PL
successive
 Approche plus robuste basée sur l’approximation
des fonctions non-linéaires par leurs gradients
évalués au point obtenue à l’itération précédente

 Soit Cs asYs  cps(X ps,Vps,T ps)

pP

 Approximation linéaire de Cs pour le scénario

réalisable obtenu à l’itération j, à savoir : (F(j), Y(j))

02/28/25 Atidel HADJ-ALOUANE 66

 Approche générale de PL
successive (suite1)
Cs (cps)(j)X
Cs(j)

as(j) Zone de confiance

Xjpw
as

X(j)pw
Flux agrégé Xps

Approximation par un gradient dans une zone de

confiance
02/28/25 Atidel HADJ-ALOUANE 67
 Approche générale de PL
successive (suite2)
 c    V  c  T 
(j) (j) (j)
a(j)s C(j)s  ps X
X(j)ps  c ps (j)
ps ps
(j)
ps
V T
 
pP
où C(j)
s
est la valeur de Cs au point X(j)
ps
, V (j)
ps
, T (j)
ps

 Dans le voisinage deX , V , T , la valeur de la fonction

(j) (j) (j)
ps ps ps
concave est approchée par la fonction linéaire:
Cs
 c      
~
C s a(j)
s
Ys  (j)
ps X
Xps  cps (j)
V
Vps  cps (j)
T
Tps
pP
 Pour résoudre le problème , il suffit de remplacer la fn.
objectif (logist6-52) par
où CT(j 1)  min  cj
i Fi  aj
sYs

c      
iI sS


(j) (j) (j) (j)
c c i  ps X
 vsi c ps  si c ps
i
s  S  Ci
V T
02/28/25 Atidel HADJ-ALOUANE 68
 III
Maximiser les profits au
lieu de minimiser les coûts

02/28/25 Atidel HADJ-ALOUANE 69

 Fonction profit
max   ci Fi  asYs
 R
p P d  Dp
pd (x pd)  
 i I

sS


xpd : quantité de produit p vendu dans la zone d
Rpd(xpd) : revenu total des ventes de produit p dans la zone d

 Généralement, on suppose que Rpd(xpd) est concave et

bornée avec Rpd(0)=0,
c-à-d. les revenus marginaux sont décroissants.
 Pour simplifier la présentation, on considère le modèle
linéaire (LP présenté à la page 7).
 La généralisation au cas avec économies d’échelle est
directe
02/28/25 Atidel HADJ-ALOUANE 70
 Fonction profit (suite)
 La complexité du modèle avec revenu
dépend de la nature de xpd et de Rpd(xpd)
 Si xpd est fixée de façon exogène et Rpd(xpd) est
indépendant des variables de décision du
problème  le 1e terme de la fn. profit est
constant  il suffit de minimiser les coûts.
 Sinon, xpd devient une variable de décision. On
peut introduire
X pd x pd X pd p, d
X pd
où : dictée par les objectifs de
pénétration de marché de l’entreprise
X pd
: représente la part de marché maximale
que l’entreprise peut obtenir
02/28/25 Atidel HADJ-ALOUANE 71
Cas 1: xpd variable de décision

 Complexité dépend de la nature de Rpd(xpd)

 on peut supposer que Rpd(xpd) est linéaire par

partie  introduction de variables binaires

 Autre approche: Rpd(xpd) = Ppd(xpd) xpd

 Ppd(xpd) linéaire en xpd  fonction objectif

quadratique
 Ppd(xpd) constante  modèle linéaire

02/28/25 Atidel HADJ-ALOUANE 72

Cas 2: xpd fonction du délai et prix

 xpd est une fonction du délai de livraison (ou de

la distance maximale du fournisseur) et du
prix des produits.
 Relation du type xpd = fpd(Ppd, Sd) pP, d Dp (*)
où Ppd: prix du produit
Sd : délai de livraison garantis
 On procède par analyse de sensibilité
 établir une plage des valeurs de Ppd et Sd
 pour chaque scénario, évaluer la demande avec (*) et les
revenus avec
RT    Rpd(x pd)   Ppd x pd
p P d  Dp p P d  D
p
02/28/25 Atidel HADJ-ALOUANE 73
 Cas 2: xpd fonction du délai et prix

(suite)
 trouver la solution optimale du modèle de min
des coûts en éliminant à priori toutes les chaînes
qui ne respectent pas la politique de service
considérée
 Analyser ensuite les résultats (type d’analyse

Revenusabordée au Chapitre 1 (page 70)

Coûts
RT: revenu total

Profit
CT: coût total

Temps de réponse
02/28/25 Atidel HADJ-ALOUANE 74
Cas 3: xpd dépend du fournisseur
unique
 xpd dépend du fournisseur unique choisi pour chaque
zone de consommation:
 on veut que chaque zone (marché) soit desservie par un seul
nœud s  S.
 Pour une chaîne donnée, on a : Délais de livraison =md
Prix = Ppmd

p w m d

Coûts: vdi = Tpw+ Gpw+ Hwi + Tpwm+ Gpm+ Hmi + Tpmd

 Pour toutes les chaînes i qui incluent p, m et d on peut
calculer le revenu unitaire net :
Ri = Ppmd -vdi

02/28/25 Atidel HADJ-ALOUANE 75

Cas 3: xpd dépend du fournisseur
unique
(suite1)
 Lorsque le produit p est livré à la zone d par un
fournisseur m, la demande est calculée par :
xpmd = fpd(Ppmd, md) pP, m Md, d Dp

où Md S : ensemble des nœuds qui ont un lien

direct avec la zone de consommation d

 Soit Zmd=1 si la zone d est desservie uniquement

par le nœud m Md, et 0 autrement.

02/28/25 Atidel HADJ-ALOUANE 76

Cas 3: xpd dépend du fournisseur
unique
(suite2)
 Les contraintes de demande (du modèle de base)
sont alors remplacées par :
 i  p,m,d   CFi  x pmdZ md 0
i
pP, mM d, dDp

 m M Z md 1
d
d  Dp

Z md 0,1 m M d , d  Dp
 Pour maximiser le profit, on doit aussi remplacer
la fonction économique par:
maxRi Fi  asYs
i I s S

02/28/25 Atidel HADJ-ALOUANE 77