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

4.3 Exemple numérique :

Supposons qu'on a 4 voitures de différentes couleurs placées dans un ordre, l'ordre d'assemblage est de 1, 2, 3,4 :

Les voitures 1 et 3 sont rouges R

Les voitures 2et 4 sont noires N.

ce problème peut être formulé sous la forme de programmation linéaire en nombre entier PLNE :

min c12+c13+c14+c23+c24+c34

subject to

x11+x12+x13+x14=1

x21+x22+x23+x24=1

x31+x32+x33+x34=1

x41+x42+x43+x44=1

x11+x21+x31+x41=1

x12+x22+x32+x42=1

x13+x23+x33+x43=1

x14+x24+x34+x44=1

x11+x12=1

x21+x22+x23=1

x32+x33+x34=1

x43+x44=1

c11=0

c22=0

c33=0

c44=0

x11+x22-c12<=1

x22+x33-c23<=1

x33+x44-c34<=1

x12+x21-c12<=1

x12+x23-c12<=1

x22+x13-c12<=1

x14+x23-c12<=1

x13+x24-c12<=1

x32+x21-c23<=1

x32+x23-c23<=1

x34+x23-c23<=1

x33+x24-c23<=1

x22+x31-c23<=1

x32+x41-c34<=1

x32+x43-c34<=1

x42+x33-c34<=1

x34+x43-c34<=1

x31+x42-c34<=1

end

int x11 int x21 int x31 int x41 int c11 int c22 int c34

int x12 int x22 int x 32 int x42 int c12 int c23 int c 44

int x13 int x23 int x33 int x43 int c13 int c 24

int x14 int x24 int x34 int x44 int c14 int c 33

On résout ce problème à l'aide du logiciel Lindo.voici la sortie Lindo 

OBJECTIVE FUNCTION VALUE

1) 1.000000

VARIABLE VALUE REDUCED COST

X11 1.000000 0.000000

X12 0.000000 0.000000

X13 0.000000 0.000000

X14 0.000000 0.000000

X21 0.000000 0.000000

X22 0.000000 0.000000

X23 1.000000 0.000000

X24 0.000000 0.000000

X31 0.000000 0.000000

X32 1.000000 0.000000

X33 0.000000 0.000000

X34 0.000000 0.000000

X41 0.000000 0.000000

X42 0.000000 0.000000

X43 0.000000 0.000000

X44 1.000000 0.000000

C11 0.000000 0.000000

C12 0.000000 1.000000

C13 0.000000 1.000000

C14 0.000000 1.000000

2 0.000000 0.000000

3 1.000000 1.000000

4 0.000000 1.000000

C33 0.000000 0.000000

C34 0.000000 1.000000

C44 0.000000 0.000000

La permutation optimale de ces voitures est RRNN d'où on obtient seulement un changement du couleur au lieu de trois.

En effet, on a x₁₁=1 ce qui implique que la première voiture rouge reste a la même position 1.

X₂₃ =1 ce qui implique que la voiture noire numéro 2 est placée a la position 3.

X₃₂=1 signifie que la voiture rouge numéro 3 est placée a la position 2.

X₄₄=1 signifie que la voiture noire numéro 4 reste a la même position 4.

C₂₃=1 ce qui implique que la couleur de la voiture numéro 2(rouge) est différent de la couleur de la voiture numéro 3(noire).

c₁₁, c₁₂,c₁₃,c₁₄,c_22,c₂₄,c₄₄.c₃₄.c₃₃ sont nuls d'où il ya un seul changement du couleur.