14/12/2005 OFFRE ET DEMANDE DE SERVICE AVEC RESSOURCES LIMITEES Projet de Recherche Opérationnelle – IFIPS Info 5 Promotion 2006 – [email protected] Galante

14/12/2005

OFFRE ET DEMANDE DE SERVICE AVEC RESSOURCES LIMITEES

Projet de Recherche Opérationnelle – IFIPS Info 5

Promotion 2006 – [email protected]

Galante – Lefebvre – Rellier – Rey

2Projet de Recherche Opérationnelle – IFIPS Informatique 5ème Année14/12/2005

Plan de la Présentation

Présentation du Problème

Modèle Mathématiques et Simplifications

Méthodes de Voisinage

Méthodes de Relaxation

Modèle UML et Stratégie d’Intégration

Interfaces

Sorties et Résultats

Démonstration


Présentation du Problème

Contexte

Définitions

Objectif


PARIS

SEPT

ROUEN

VOLVIC

LYON

LILLE

C=100

C=200C=600

C=150

C=420

C=740

C=2500

PARIS

SEPT

ROUEN

VOLVIC

LYON

LILLE

PARIS

SEPT

ROUEN

VOLVIC

LYON

LILLE

C=100

C=200C=600

C=150

C=420

C=740

C=2500

Le principe

Les clients(Segments)

Demandes

Fournisseurs

Le Réseau + Offres

Contexte

Définitions

Objectif


Le principe

Qui et Quoi

Définitions

Objectif


Le principe

Qui et Quoi

Définitions

Objectif

Satisfaire les demandes des clients

En

Modifiant la répartition des flux sur le réseau

Pour

Optimiser les Profits

OBJECTIF DU PROJET


Modèle Mathématique et Simplifications

Modèle Initial

Modèle Linéarisé

Simplification

Modèle Simplifié

Modèle Final

Modèle Initial

qsf

ac

skdts

TPTP

qfTts

TR

cqsf

oqsf

faf s qa

oqsf

kff q

ks

cqsf

oqsf

f s q

cqsf

cqf

oqsf

oqf

oqf

f s q

oqsf

oqf

T

cqsf

oqsf

oqsf

oqf

,,0,

,:..

,,min

,0:..

,max

,,,,

:,,

:,,,,

,,,,,,,

,

,,,,

,,,,

,,,



Modèle Initial

Modèle Linéarisé

Simplification

Modèle Simplifié

Modèle Final

Modèle Linéarisé En modifiant la fonction de minimisation de la

dépense des clients par la méthode de Karush-Kuhn-Tucker on obtient:

0,,

,,0

,,0

0

,,

,,

,

,0:..

,max

,,,,

)(

,,,,

)(

,,,,

,,

,,

)(

,,

)(

:,,

:,,,,

,

,,,, ,,,

c

qsf

o

qsfa

fk

s

c

qsf

c

qsf

fa

fk

sa

o

qsf

o

qsf

s q

o

qsfaa

o

qsf

fk

s

fa

o

qsf

fk

sa

faf s qa

o

qsf

kff q

s

k

c

qsf

o

qsf

o

qf

f s q

o

qsf

o

qfT

qsf

qsf

ac

qsf

qsf

ac

skd

qfTts

TRoqsf

oqf

1,0,

1

0

0

1

0

0

1

0

0

33

33

)(

,,

33,,

22

22

)(

,,

22,,

,1,1

,1,1,,

,1,1

xx

fk

s

c

qsf

c

qsf

fa

fk

sa

o

qsf

o

qsf

aa

s qaa

o

qsfa

aaa

N

M

N

M

a

aNc

aM



Modèle Initial

Modèle Linéarisé

Simplification

Modèle Simplifié

Modèle Final

Simplification de la Demande Les concurrents ont déjà pris leur par de marché. Les flux concurrents sont donc des constantes. Reste alors une demande à satisfaire.

Rapport QoS attendu et QoS proposée Les clients ont besoin de satisfaire leur demande. Peu importe le prix proposé ils l’acceptent.



Modèle Initial

Modèle Linéarisé

Simplification

Modèle Simplifié

Modèle Final

Modèle Simplifié

0

:/

,min

0:/

,max

,,

,,

,,

,,,

,

,,,

o

qsf

f s qa

o

qsf

f s q

k

s

o

qsf

f s q

o

qsf

o

qf

o

qf

f s q

o

qsf

o

qf

c

dr

ts

TP

Tts

TR



Modèle Initial

Modèle Linéarisé

Simplification

Modèle Simplifié

Modèle Final

Modèle Final : Obtenu par application de la méthode de Karush-

Kuhn-Tucker dur le modèle simplifié.

oqsf

fks

aa

a

fksa

oqsf

oqsf

f s q

oqsfaa

ao

qsf

f s qa

oqsf

f s q

ks

oqsf

oqf

f s q

oqsf

oqf

c

c

dr

T

ts

TR

,,)(

)(,,,,

,,

,,

,,

,,

,

,,,

0

0

0,

0

:/

,max

1,0,:

1

0

0

1

0

0

,,

,2,2

,2,2)(

,,

,2,2,,

,1,1

,1,1,,

,1,1

ixix

ii

faii

fksa

oqsf

iio

qsf

aa

s qaa

oqsfa

aaa

i

i

iN

iM

a

aNc

aM



Le VNS



Principe VNS

Résultats VNS

Principe RS

Résultats RS

Principe adapté à notre modèle, échange de Flux :

Pour un même Marché Pour un même Client

Raisons : L’échange de flux semble la solution la plus

optimale dans le cas de l’optimisation d’allocation de ressources.

Echange pour un même marché et même client : respect des demandes.



Comparaison des profits obtenus

Comparatif des profits sur l'ensemble des exemples

0

50 000

100 000

150 000

200 000

250 000

1 1b 21 22 31 32

Exemples

Pro

fits Profit Initial

Profit 2Opt

Profit 3Opt

Principe VNS

Résultats VNS

Principe RS

Résultats RS



Le Recuit Simulé



Principe VNS

Résultats VNS

Principe RS

Résultats RS

Echange de Flux simple basé sur le VNS.

Gestion de la température Température initiale élevée, implique un réglage

de la température. Température initiale faible, aucun règlage de

température.



Évolution de la TempératureEvolution de la température avec règlage et température initiale

élevée

0

100 000

200 000

300 000

400 000

500 000

600 000

1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31

Nombre d'Itérations

Tem

pér

atu

re

Exemple

Evolution de la température sans règlage et température initiale élevée

0

100 000

200 000

300 000

400 000

500 000

600 000

1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31


Tem

pér

atu

re

Exemple

Evolution de la température avec règlage et température initiale faible

0

500

1 000

1 500

2 000

2 500

1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31


Tem

pér

atu

re

Exemple

Evolution de la température sans règlage et température initiale faible

0

500

1 000

1 500

2 000

2 500

1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31


Tem

pér

atu

re

Exemple

Principe VNS

Résultats VNS

Principe RS

Résultats RS



Comparaison des profits obtenus

Comparatif des profits sur l'ensemble des exemples avec temperature initiale faible

0

50 000

100 000

150 000

200 000

250 000

1 1b 21 22 31 32

Exemples

Pro

fits Profit Initial

Profit sans règlage de temp

Profit avec règlage de temp

Comparatif des profits sur l'ensemble des exemples avec temperature initiale élévée

0

50 000

100 000

150 000

200 000

250 000

1 1b 21 22 31 32

Exemples

Pro

fits Profit Initial

Profit sans règlage de temp

Profit avec règlage de temp

Principe VNS

Résultats VNS

Principe RS

Résultats RS



Optimum

Bornes supérieures



La relaxation

Semi-Définie Positive



Matrice des variables binairesMatrices des variables binaires

Matrice complète

Contraintes du problème

Comparaison avec les méthodes de voisinage

1

..

..

..

...

.

.

.

1

,2,2,1,1

,22,2,2,2,2,1

,2,2,22,2,2,1

,1,1,2,1,22

,1

,1,1,2,1,2,1,1

,2,1

,2,1

,1,1

2,1

iiaa

iiiiia

iiiiia

aaiaia

aaiaiaa

ia

ia

aa

a

t

Y

x

xXY



Matrice complèteMatrices des variables binaires

Matrice complète



)(

,

fks

a

oqf

Y

Z



Contraintes du problèmeMatrices des variables binaires

Matrice complète



faii

fksa

oqsf

fa

fksa

oqsf

iio

qsf

f s qaa

oqsfa

f s q

oqsfa

aaa

oqsf

fks

aa

f s qa

oqsf

f s q

ks

oqsf

izN

z

izM

azNc

azc

azM

z

zc

dr

08

07

06

05

04

03

02

01

0

,2,2)(

,,

)(,,

,2,2,,

,1,1,,

,,

,1,1

,,)(

,,

,,



Contraintes du problèmeMatrices des variables binaires

Matrice complète



8

7

6

5

4

3

2

1

)(

,

z

z

z

z

z

z

z

z

Y

Z

fks

a

oqf




Matrices des variables binaires

Matrice complète



Comparatif SDP vs Recuit et VNS

0

50 000

100 000

150 000

200 000

250 000

300 000

1 2 3 4 5 6

Exemples

Pro

fits

Initial

Recuit Simulé

VNS

SDP



Temps d’exécutionMatrices des variables binaires

Matrice complète



Temps d'exécution du SDP

0

10

20

30

40

50

60

158 158 401 402 586 586

Exemples

Tem

ps

d'é

xécu

tio

n

Temps d'éxécution



La relaxation

Lagrangienne



Contrainte relâchéeContrainte relâchée

ParticularitéDu problème

Fonction de Lagrange

Dual Lagrangien

Fonction duale

faf s qa

oqsf

faf s qa

oqsf

ac

ac

:,,

:,,

,0

,



Deux solutions de départ

Paris Nancy

Phi = 200

Capacité : 300

Contrainte relâchée



Dual Lagrangien

Fonction duale

Paris Nancy

Phi = 500

Capacité : 300



Particularité du problème

Problème de maximisation

Max f(x)




Dual Lagrangien

Fonction duale





Max f(x)

Passage en minimisation

Max f(x) = -Min –f(x)




Dual Lagrangien

Fonction duale





Max f(x)

Passage en minimisation

Max f(x) = -Min –f(x)

Relaxation sur : Min –f(x)




Dual Lagrangien

Fonction duale



Fonction de LagrangeContrainte relâchée



Dual Lagrangien

Fonction duale

faf s qa

oqsf

f s q

oqsf

oqsf

c

R

L

:,,

,,

,,

.

),(



Dual LagrangienContrainte relâchée



Dual Lagrangien

Fonction duale

0,

),(

max

,,

oqsfL



Fonction Duale

S : contraintes non relâchées




Dual Lagrangien

Fonction duale ),,(min

)(

,,,),( ,,,

oqsf

oqf

STTL

oqsf

oqf



Comparaison avec la SDPContrainte relâchée



Dual Lagrangien

Fonction duale

f * < Lagrange < SDP



Modèle UML

Intégration

Modèle UML simplifié



Modèle UML

Intégration

Stratégie d’intégration par une démarche ascendante

ALGORITHME-----

AlgoVNSAlgoRS

AlgoSDPAlgoRL

REALISATION----

QUALITEPROPOSITION

FLUX

COMMERCIALE------

MARCHEARC

CLIENT------

DEMANDESEGMENT

PHYSIQUE-----

SOMMETARC

GRAPHE-----

GRAPHE

PARSER XML-----

PARSEUR

SORTIE XML SORTIE GRAPHE INTERFACE


Interfaces

Importer

Identifier 1

Identifier 2

Choisir

Optimiser

Comparer

Enregistrer


Interfaces

Importer

Identifier 1

Identifier 2

Choisir

Optimiser

Comparer

Enregistrer


Interfaces

Importer

Identifier 1

Identifier 2

Choisir

Optimiser

Comparer

Enregistrer


Interfaces

Importer

Identifier 1

Identifier 2

Choisir

Optimiser

Comparer

Enregistrer

Méthodes d’optimisation


Interfaces

Importer

Identifier 1

Identifier 2

Choisir

Optimiser

Comparer

Enregistrer



Importer

Identifier 1

Identifier 2

Choisir

Optimiser

Comparer

Enregistrer

OPTIMISATIONOPTIMISATION



Importer

Identifier 1

Identifier 2

Choisir

Optimiser

Comparer

Enregistrer



Importer

Identifier 1

Identifier 2

Choisir

Optimiser

Comparer

Enregistrer


Conclusion

Projet intéressant

Mise en application de la théorie

Difficultés d’appréhension du problème

Manque de temps


Démonstration

Documents

14/12/2005 OFFRE ET DEMANDE DE SERVICE AVEC RESSOURCES LIMITEES Projet de Recherche Opérationnelle – IFIPS Info 5 Promotion 2006 – [email protected] Galante