WOW !! MUCH LOVE ! SO WORLD PEACE !
Fond bitcoin pour l'amélioration du site: 1memzGeKS7CB3ECNkzSn2qHwxU6NZoJ8o
  Dogecoin (tips/pourboires): DCLoo9Dd4qECqpMLurdgGnaoqbftj16Nvp


Home | Publier un mémoire | Une page au hasard

 > 

L'utilisation de la programmation mathématique pour la résolution d'un problème « car-sequencing »

( Télécharger le fichier original )
par Attafi Meriem & Zghidi Imen
FSEGS -  2008
  

précédent sommaire suivant

Bitcoin is a swarm of cyber hornets serving the goddess of wisdom, feeding on the fire of truth, exponentially growing ever smarter, faster, and stronger behind a wall of encrypted energy

3.2 Les algorithmes exactes :

3.2.1 Programmation linéaire :

a)Modélisation :

L'objectif de la méthode de programmation linéaire est minimiser ou (maximiser) une fonction linéaire de n variables réelles non négatives (les coefficients sont notées cj) sur un ensemble de même inégalités linéaires.

Max (ou min) z =

i = 1,....., r

i= r+1,....., s

i= s+1,....., m

S.c.q xj =0 j=1, p

xj j=p+1, q

xj =0 j=q+1, n

§ La forme standard d'un problème linéaire est comme la suivante :

max (ou min) z= c1 x1 + c2 x2 +...cn xn

a11 x1 + a12 x2 +...+a1n xn =b1

a21x+a22x2+...+a2nxn=b2 s.c.q am1 x1 + am2 x2+...amn xn =bm

x1, x2, ...,xn=0

3.2.2 Programmation linéaire en nombre entier : 

Dans la programmation linéaire en nombre entier PLNE chaque variable est restreinte aux valeurs entières, en général les coefficients aij sont aussi entiers, et donc on peut se limiter à des constantes bj entières.

Max (ou min) z =

S .c i=1,...,n

xj=0 , entier j=1,...,n

Les variables binaires peuvent se voir comme des variables entières soumises à la contrainte d'appartenir à l'intervalle [0 ,1].En effet, la contrainte :

Xj=0, 1

est évidemment équivalente à :

Xj=0 et Xj =1 et Xj entier

Plusieurs problèmes d'ordonnancement, tel que notre problème de « car -sequencing », peuvent être formulées sous la forme de programmation linéaire en nombre entier PLNE.

3.2.3 Méthode de séparation et d'évaluation ( branch&bound):

La méthode de branch and bound consiste à énumérer des solutions d'une manière intelligente en ce sens que, en utilisant certaines propriétés du problème en question, cette technique arrive à éliminer des solutions partielles qui ne mènent pas à la solution que l'on recherche.

De ce fait, on arrive souvent à obtenir la solution recherchée en des temps raisonnables .Bien entendu, dans le pire de cas on retombe toujours sur l'élimination explicite de toutes les solutions du problème

Idée :

§ Diviser pour conquérir.

§ Utilisation de bornes sur le coût optimal pour éviter d'explorer certaines parties de l'ensemble des solutions admissibles.

Branchement

Soit F l'ensemble des solutions admissibles d'un problème :

min cTx

s.c. x F

§ On partitionne F en une collection finie de sous-ensembles F1,...,Fk.

§ On résout séparément les problèmes :

min cTx s.

ce problème sera appelé Fi également.

F

Représentation

FK

F1

F2

....... ..........

§ A priori, les sous-problèmes peuvent être aussi difficiles que le problème original.

§ Dans ce cas, on applique le même système.

§ On partitionne le/les sous-problèmes.

F

F1

F2

FK

.......

F22

F21

F2m

F212

F21n

F211

.......

Bornement :

§ On suppose que pour chaque sous-problème :

min cTx

s.c. x Fi

on peut calculer efficacement une borne inférieure b(Fi) sur le coût optimal, i.e.

b(Fi) =minx Fi cTx

§ Typiquement, on utilise la relaxation linéaire pour obtenir cette borne.

Les règles de séparation et évaluation :

1) On dit qu'un sommet de l'arbre qu'il est inutile de séparer est stérilisé, il y a plusieurs possibilités pour cela :

§ Le sommet est associé à une solution réalisable candidate (séparer ne l'améliorera pas).

§ Le sommet est associé à un sous - problème non -réalisable.

§ La valeur z optimale du sous-problème associée est inférieure (pour un problème max) à la borne inférieure courante.

2) Un sous -problème peut être éliminé directement si :

§ Le sous- problème est réalisable.

§ La borne inférieure courante est supérieure à la valeur z du sous-problème.

précédent sommaire suivant






Bitcoin is a swarm of cyber hornets serving the goddess of wisdom, feeding on the fire of truth, exponentially growing ever smarter, faster, and stronger behind a wall of encrypted energy








"Entre deux mots il faut choisir le moindre"   Paul Valery