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

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 c_j) 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 x_j =0 j=1, p

x_j j=p+1, q

x_j =0 j=q+1, n

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

max (ou min) z= c₁ x₁ + c₂ x₂ +...c_n x_n

a₁₁ x₁ + a₁₂ x₂ +...+a_1n x_n =b₁

a₂₁x+a₂₂x₂+...+a_2nx_n=b₂ s.c.q a_m1 x₁ + a_m2 x₂+...a_mn x_n =b_m

x₁, x₂, ...,x_n=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 a_ij sont aussi entiers, et donc on peut se limiter à des constantes b_j entières.

Max (ou min) z =

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

x_j=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 :

X_j=0, 1

est évidemment équivalente à :

X_j=0 et X_j =1 et X_j 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 c^Tx

s.c. x F

§ On partitionne F en une collection finie de sous-ensembles F₁,...,F_k.

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

min c^Tx s.

ce problème sera appelé F_i également.

F

Représentation

F_K

F₁

F₂

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

§ 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

F₁

F₂

F_K

.......

F₂₂

F₂₁

F_2m

F₂₁₂

F_21n

F₂₁₁

.......

Bornement :

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

min c^Tx

s.c. x F_i

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

b(F_i) =min_{x Fi} c^Tx

§ 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.