005 Optimisation de La Chaine Logistique Benqlilou 2012

OPTIMISATION DE LA CHAINE LOGISTIQUE

Prof. ChouaibBENQLILOU

[email protected]

2012-13

Dr. Chouaib BENQLILOU

Apprendre formuler un problmed'optimisation(linaire,nonlinaires,

variables continueset discrtes, ) ; dfinir une mesurede performance,

fixer les limites permiseset les contraintes respecter, prciser les

paramtresde dcision

Comprendrelesprincipaux algorithmesd'optimisation deterministiqueset

stochastiqueset leursapplicationsen gniede procdsindustriels; Choisir

le plusadapt et le configurer

Implmenterle systmesurlogiciels (GAMS,Matlab, ) et

raliseruneanalysede sensibilitsurles solutionsoptimales.



Prise de dcision optimale avec une connaissance

complte

desdcisionspossibleset

Uncritrepourcomparerentreeux(bienquantifi)

Dure des feux rouges dans une ville

Investissementvs risque modlisationstochastique

Introduction : Framework


Logiciel

Contenant des algorithmes

(detrministiquesou

stochastiques)

(Excel, Matlab, GAMS)

Chain logistique

Ordonnancement,

Formulation mathmatiquement en

quation

Fonction a minimiser/maximiser

Des contraintes (in)galit(procd)

Des variables de dcisions

s

y

n

t

a

x

e

Mise en quation

Optimisationest toujours requise

a une certaine tape de

inv

Exp.

Planification et

Scheduling

Slection optimale

des consignes RTO

Rgulateurs PID

Capteur et

actionneur

Rconciliation de

donnes

Faultdiagnosis

Conception

systeme

Chain logistique ForecastingB

ase

de

do

nn

e

s d

yn

.

Purdue


Introduction: Formulation mathmatique


Fonction objectif

linaire ou non linaires

simple ou multiple

Contraintes

linaires/non linaires

galits/ ingalits

limites suprieures/inferieurs des variables

Variables

continue ou discrtes

LP, NLP, MILP, MINLP

Variables de dcision

Configurer les paramtres du solveur

Une variable ou plusieurs

LINAIRE


Architecture de la SCM

Rseaux de diffrents

Fournisseurs

Units de production

Centres de stockage / distribution

March

Moyens de transport


Les niveaux hirarchiques de la SCM

Design dcisionstratgiques: emplacementdes unitsde production,centresde distribution,fournisseurs; choixdes technologieset optionsdedistribution.

Tactique dcisionde flux de matire: combienproduireet ou; niveaudeproductionet de stockage(planification )

Oprationnel Organisationdes ressourceshumaineset techniquelesexigencesdu client(Ordonnancement)

Quelproduit(quoi), quellequantit(combien), quelquipement(ou), quelmoment(quand) .

batching, allocation, sequence, timing

Le modle de

PURDUE partie

conomiqueDr. ChouaibBENQLILOU

Vision de la SCM

Difficultsrelativesa la prisede dcision:

chellestemporelleset gographiquesdiffrents.

ractivit devant un marche hautement variant (secteur

lectronique; DELL)

anticiples exigencesdu client(ZARA)

Coutassocia la SCdansle produit estde 10% (resp. 40%)

marchlocal(resp. marchinternational)Dr. Chouaib BENQLILOU

Flux de donnes

Coordonnesles diffrentes activits de la SC

Synchroniserles 3 flux

information

matire

financier (cash)

Satisfaction des spcifications du march

Maximiser le bnfice


Optimisation

Design: dcision stratgique (2 a 5 ans)

maximiser le bnficeannuel,cout NPV

Dterminer des units et centre de

distribution, choix des technologieset des moyens de

transport


Optimisation

Planning: dcision tactique (sur 1-24 mois)

maximiser le profit ouminimiserlesretardset le couttotal

Dterminerle niveaude productionet de stockage

Contraints,disponibilitde la matirepremire,capacitdeproduction,limitesdu stock

Donnes, demandede chaquemarch,cout de production,coutde stockageet du transport,etc.


Optimisation

Ordonnancement: dcision oprationnelle(heures

et jours)

maximiser la productionpour une priode de temps

donne,minimiserle Makespan, minimiserle retard

Dterminerle quoi,le quand,le combienet le ou

Contraints, recette du processus,donnes de la

planificationDr. Chouaib BENQLILOU

Real-time optimisation (RTO)


La conception du Contrle permet une rponse

raisonnable en boucle ferme devant des changementsde

consignes(Set-Points- SP)et desperturbations.

Ladterminationen tempsrel (on-line) de consignesoptimales(RTO)

1. Unmodleen tat stationnaire estpluttutilisquele modledynamique,tant

donnque le systmeest supposoprer en rgime permanentsauf quand les

consigneschangent.

2. Lemodleconomique maximisationdu profit oul minimisationdescouts,

Slection optimale des SP est formule comme un problme

FO) et

le modle du procd en rgime stationnaire (contraintes)



de la RTOenindustrie(contrlesuperviseur)

Optimiserlesset-pointssurunebaseconomique

du rgimestationnaire

Transfrerlesdonnes

Systmede ContrleDistribu( DCS= {PID,PLC, } )


Un procdpermetde fabriquer deux produitsE et F a partir de

deuxmatirespremiresA et Bavecunelimite

LestransformationsfaisantintervenirA et Bsont:

ProcdP1 : A+B E

ProcdP2 : A+2B F

Procd Produit Cout

opration

Prix de

vente

Max.

production

Cout

fixes

1 E 15Dh/Kg 40Dh/kg 30.000Kg/j 200Dh/j

2 F 5Dh/kg 33Dh/kg 30.000Kg/j 350Dh/j

Matire Premire Cout Disponibilit Max.

A 15Dh/kg 40.000kg/j

B 20Dh/kg 30.000kg/j



Les tapes qui devront tre considre pour rsoudre pratiquement

ETAPE1 : Identifier les variables du procds(lesvariables et desorties les plus importantes,elles sont utilisesdans la fonction objectif et les

contraintes)

La quantit de A, B, E et F [x1, x2, x3, x4]

ETAPE2 : choisiret formuler la fonctionobjectif

Ventes des produits cout de la matire premire

20035051520153340 432143 xxxxxx



ETAPE3 : i) dvelopper et construire le modle du procds(bilan matire et

nergie)et ii) des contraintesphysiques,opratoires(de stockage),de scurits

et environnementales

214

213

2xxx

xxx

300000

300000

300000

400000

4

3

2

1

x

x

x

x

ETAPE4 : simplifier le modle ainsi formuler (linarisation)

ETAPE5 : choisir adquat,le configureret estimer la

solution initiale

ETAPE6 : faire une tudede sensibilit(pour voir quelssont les paramtresles plus

importantspour trouver

Kg

re

ac/

kg

pro

du

it


Conception


Lesvariables de dcisionsontdfinit surla basede

desdegrsde libert (NV NE)

Lescontraintessontprincipalementceuxrelativesaux limitesmaxet

min des variables et ceux relatives au procd (BM, BE, )

simulateur,ANN,

Gnralementla fonctionobjectif est un compromisentre le cout

et le cout www.chempute.com;

www.chemengineer.miningco.com

conduite

Pour un fluide non compressible de viscosit et densit donnes
http://www.chempute.com/http://www.chempute.com/http://www.chempute.com/http://www.chempute.com/http://www.chempute.com/http://www.chemengineer.miningco.com/http://www.chemengineer.miningco.com/http://www.chemengineer.miningco.com/http://www.chemengineer.miningco.com/http://www.chemengineer.miningco.com/http://www.chemengineer.miningco.com/http://www.chemengineer.miningco.com/

Conception

FOpompe la de efficacite :,

3.1,

0

1

PmCC

nLDCC

ope

n

inv

Co

ntr

ain

tes

friction defacteur 046.0Re046.0

fluidedu vitesse2

massiquedebit 4

2.0

2.0

2

2

fDv

f

vD

LvfP

mvD

m

Pv,D,f,Variables

LDmC

LDCC 8.42.02.08.203.11 142.0


Conception

32

0

1

4

3

///59.0

./7.5

6.0

./1072.6

/60

/50

skgmanneDhC

annemDhC

mskgx

mkg

skgm


Planification de production (LP)

Procdde productionmulti-produit et multi-purposeoffrant une

grande flexibilit (batch) maximisation du systme

(p.e. extractionpar CO2 supercritique)

Dterminer

Quoi?

Quand?

Ou?

Comment?


Rconciliation de Donnes (QP)


racteur distMP

Courant

Fi

l/s variance

F1 10 1

F2 10.5 300

F3 5.5 2

F4 6 0.5

),(

*

4

*

3

*

2

*

2

*

1

2*

CAiteobservabil

FFF

FF

FFi i

min

s.t. Solver

Option complment atteindre solver

Menu donnes

Pondration (favoris les

variables ayant une variance

rduite)


Raffinerie A Ptrole brut # 2

Essence

Krosne

Fuel

Rsidu Raffinerie B

Ptrole brut # 3

Ptrole brut # 4

Ptrole brut # 1

x2

x3

x4

x1

x5

Q1

Q2

Q3

Q4

Diffrent type de ptrole avec divers proprits et temps de

livraison problmeLP

x1 x2 x3 x4 x5 Prix de vente

$/br

Demande max

1000 br/sem

P1 0.6 0.5 0.3 0.4 0.4 45 170

P2 0.2 0.2 0.3 03 0.1 30 85

P3 0.1 0.2 0.3 0.2 0.2 15 85

P4 0 0 0 0 0.2 60 20

Prix brut $/br 15 15 15 25 25

Cout ope $/br 5 8.5 7.5 3 2

Brut dispo

1000 br/ sem

100 100 100 200

5544332211 xaxaxaxaxaQ pppppp


5,...,1,0

0

4,..,1,

.

5544332211

454

33

22

11

cx

Q

DQ

pxaxaxaxaxaQ

Sxx

Sx

Sx

Sx

st

QcQvMax

c

p

pp

pppppp

c

pp

p

pp


Estimation de paramtre

coefficient de transfert de chaleur

activit du catalyseur

Reprsentation correct du procd sous tude


LPrsolution


LP sans contrainte 1D (dtermination de la fraction

vaporise dans une distillation flash)

Mthode de Newton 01''

1

''

1

'

1 xfxf

xfxx kk

Mthode deterministique: Une rechercheprdtermineet aucune tape

alatoire:

I. direct pas le gradient simplexe (Dantzig 1947), point intrieur(Karmarkar1984),

II. indirecte utilisantle gradient(la drive)gradientdescendant,

contraintes

Pour des problmes linaires la solution se trouve sur

la frontire

OPTIMISATION COMBINATOIRE

MILP/MINLP

ChouaibBENQLILOU


MILP / MINLP

objectifs:

faisant intervenir des variables continues et discrtes MILP / MINLP

Algorithmebranchand bound


MILP

Pour certain problme les variables de dcision prennent des valeurs

entires (p.e. nombre de compresseur, affectation des taches aux

ressources 0 ou 1, )

Rsoudre le problme en supposant est linaire puis on

arrondit les valeurs rels aux entiers les plus proches .

Enumrer toutes les solutions faisables est tout simplement

impossible (p.e. pour un systme contenant 50 variables pouvant

prendre la valeur 0 ou 1 on 250 solutions) si en plus on considre

que les variables sont entires combinatoire est

immense (NP-hard) .


MILP problme classique (knapsack)

on a n objets,chaqueobjet i a un poids wi et une

valeur vi

dterminer desobjetsa mettredansle sackpour que

le poidsnedpassepasW et pouravoir la meilleurevaleurtotale

pasou choisisest objet l' siindicant binaire variable1,0

..

max

1

1

i

i

n

i

i

i

n

i

i

y

Wwy

cs

vy


MILP problme classique (traveling salesman)

uncamionde distributioncommencesa tournea Casablanca,visiteun

ensemblede ville uneseulfoiset retournea la ville .

formuler le problme qui permetde dterminerle

coutminimal de separcours

j la a i villela de geagent voyal' siindicant binaire variable1,0;0

,1

,1

..

min

1

1

1 1

ijii

n

j

ij

n

i

ij

n

j

ij

n

i

ij

yy

iy

jy

cs

cy

i j


MILP

Formulation de dcisions logiques au moyen de variables binaires

11

J

j

jy

Si une caractristique existe la variable binaire prends la valeur 1 sinon la

valeur 0

On voudrais choisir une seule option parmi J

possibilits

myJ

j

j

1

On voudraischoisirau max m optionsparmi J

possibilits

0jk yySi k et choisi j devrasaussi

tre choisis

0,0 xUyxUnevariable binaire y pourra tre utiliserpour

forcer unevariable continuex a tre nulleavecU un

grandnombre

Dr. ChouaibBENQLILOU

Initialementles variables binairespeuventtre considrescommedes variables

continuesappartenanta [0,1] et le problmede minimisationpeut tre

rsoluscommeunLP(relaxer)

Lavaleurde la fonctionobjectif ainsirelaxer donnela borneinferieure(lower

bound)

La valeurnon-entirepourratre fixer 0 ou 1 et le problmeLPestrefait

(branch)

la meilleuresolutionnonrelaxercorrespondantea unesolutionentirefournisla

bornesuprieur(upperbound)

On coupe par optimalit //

infaisabilit //

arborescente branchand bound B&B

)05.0(1

tolerancelb

lbub

Dr. ChouaibBENQLILOU

max f = 86y1 + 4y2 + 40y3

s.c. 774y1 + 76y2 + 42y3

MILP / MINLP

algorithme:

problme MILP (resp. MINLP) et on rsout un problme LP (resp. NLP) au moyen de la mthode

adopt par exemple simplex (resp. GRG)


MILP / MINLP (SEQUENCE)

Squencede N=4 produitsdansunprocdde M=3 unitsafin deminimiserle makespan:

2 31 P1 P2 P3 P4

1 3.5 4.0 3.5 12.0

2 4.3 5.5 7.5 3.5

3 8.7 3.5 6.0 8.0

)(1 unitl' dans entre 1produit leou temps

)(M unitl' desort N produit le quand temps

10 ntinitialemeC

MakespanCNM

k unitl' dans jproduit du operation d' temps

k unitl' desort jproduit le quand temps

jk

jkC

MILP / MINLP

1- -1

NMCFO

Contraintesdetemporisation

MkNjCC kjkjkj ...2...1,,1,,

2- -1 est fait dans k (2 produits dans la memek).

3-

1...1...1,1,1, MkNjCC kjkj

MkNjCC kjkjkj ...1...1,,,1,

MILP / MINLP

Un produit devra occup une seul position dans la squence

Contraintesdesquence

4

1

, 4...1,1i

ij jX

Pour chaque position dans la squence on affecte un seul produit

Xji.

kjX kii

ijkj ,,,

4

1

,,

squence la de iposition la dans trouvese jproduit ,ijX

4

1

, 4...1,1j

ij iX

OPTIMISATION

INTRODUCTION A GAMS

ChouaibBENQLILOU


Optimisation (GAMS Tutorial)

Optimisation Code

B&B MINLP

Mthodes

exacts

Mthodes

heuristiques

(stochastiques)

GA RTSA


Quoi GAMS ?

Systemede modelisationalgebriqaues

Modelisationlineairenon-lineaireet combinatoire

Tresperformantpour les problemeslarges et complexes

Algorithmespour la resolution de: LP, NLP, MILP et MINLP:

GAMS (General algebraicmodelingsystems)

MS Excel (GRG)

Matlab (Optimisation Toolbox)


Minimiser: le coutde Transport

Souscontraintesde :Satisfairela demandeet la capacitedu stock

Un exemplesurGAMS: problem de Transport

Cout unitaire du transport

Distances

Marchs

Usine Fes Meknes Marrak. Stock

Casa 2.5 1.7 1.8 350

Tanger 2.5 1.8 1.4 600

Demande 325 300 275

Indices (or sets):

i unitsde production

j marchs

Declarer et nommerles sets

Assigner leursmemberes

Terminerchaqueinstruction par (;).


sets

i usines /Casa, Tanger/

j marches /Fes, Meknes, Marrakech/;


Donnes(or parameters):

ai stock de chaqueunit i (colis)

bj demandede chaquemarchj (colis)

cij coutde trasnportde i versj ($/case)

GAMS utilise les formats suivants

pour introduire les donnes:

Tables

Parameters

Scalar



Declarerles parametreset leur domainesa(i) and b(j)

Lesvaleurssont introduitesentreles / /

Coupleselement valeur devrons etre separespar des ou

introduitssur deslignes separes.


Parameters

d(j) demande de chaque marche /Fes325, Meknes300, Marrakech 275/

p(i) capacit de production de chaque unit /Casa 350, Tanger 600/;


Documents

005 Optimisation de La Chaine Logistique Benqlilou 2012