Module : Management des Opérations et de Production
Niveau : 3ème année
I. Solution de l’exemple 1 (problème de transport)
200
D 40
160 120
A 80 G
200 200
100 200
B E
S P
300 100
80 100 100
300
360 160
H
C F
𝑥0 𝑥1 𝑥2 𝑥3 𝑥4
𝑽∗ (𝒙𝒌 ) = 𝒎𝒊𝒏{𝑽∗𝒌−𝟏 (𝒙𝒌−𝟏 ) + 𝑽𝒌 (𝒙𝒌−𝟏 , 𝒙𝒌 )}
𝒙𝟎 ∈ {𝑺}
𝒙𝟏 ∈ {𝑨, 𝑩, 𝑪}
𝑉1∗ (𝑥1 ) = 𝑚𝑖𝑛{𝑉0∗ (𝑥0 ) + 𝑉1 (𝑥0 , 𝑥1 )}
𝑉1∗ (𝐴) = 𝑚𝑖𝑛{𝑉0∗ (𝑆) + 𝑉1 (𝑆 , 𝐴)} = 𝑚𝑖𝑛{0 + 200} = 200 (𝑆 − 𝐴)
𝑉1∗ (𝐵) = 𝑚𝑖𝑛{𝑉0∗ (𝑆) + 𝑉1 (𝑆 , 𝐵)} = 𝑚𝑖𝑛{0 + 100} = 100 (𝑆 − 𝐵)
𝑉1∗ (𝐶 ) = 𝑚𝑖𝑛{𝑉0∗ (𝑆) + 𝑉1 (𝑆 , 𝐶 )} = 𝑚𝑖𝑛{0 + 80} = 80 (𝑆 − 𝐶)
𝒙𝟐 ∈ {𝑫, 𝑬, 𝑭}
𝑉2∗ (𝑥2 ) = 𝑚𝑖𝑛{𝑉1∗ (𝑥1 ) + 𝑉2 (𝑥1 , 𝑥2 )}
𝑉2∗ (𝐷) = 𝑚𝑖𝑛{𝑉1∗ (𝐴) + 𝑉2 (𝐴 , 𝐷) ; 𝑽∗𝟏 (𝑩) + 𝑽𝟐 (𝑩 , 𝑫)}
= 𝑚𝑖𝑛{ 200 + 200 ; 𝟏𝟎𝟎 + 𝟏𝟔𝟎} = 𝟐𝟔𝟎 (S-B-D)
𝑉2∗ (𝐸 ) = 𝑚𝑖𝑛{𝑽∗𝟏 (𝑩) + 𝑽𝟐 (𝑩 , 𝑬) ; 𝑉1∗ (𝐶 ) + 𝑉2 (𝐶 , 𝐸 )}
= 𝑚𝑖𝑛{ 𝟏𝟎𝟎 + 𝟐𝟎𝟎 ; 80 + 300} = 𝟑𝟎𝟎 (𝑆 − 𝐵 − 𝐸)
𝑉2∗ (𝐹 ) = 𝑚𝑖𝑛{𝑽𝟏∗ (𝑨) + 𝑽𝟐 (𝑨 , 𝑭) ; 𝑉1∗ (𝐵) + 𝑉2 (𝐵 , 𝐹 ) ; 𝑉1∗ (𝐶 ) + 𝑉2 (𝐶 , 𝐹 ) }
= 𝑚𝑖𝑛{ 𝟐𝟎𝟎 + 𝟏𝟎𝟎 ; 100 + 300 ; 80 + 360} = 𝟑𝟎𝟎
(𝑆 − 𝐵 − 𝐹)
1
𝒙𝟑 ∈ {𝑮, 𝑯}
𝑉3 𝑥3 = 𝑚𝑖𝑛{𝑉2∗ (𝑥2 ) +
∗( )
𝑉3 (𝑥2 , 𝑥3 )}
𝑉3∗ (𝐺 ) = 𝑚𝑖𝑛{𝑽∗𝟐 (𝑫) + 𝑽𝟑 (𝑫 , 𝑮) ; 𝑉2∗ (𝐸 ) + 𝑉3 (𝐸 , 𝐺 )}
= 𝑚𝑖𝑛{ 𝟐𝟔𝟎 + 𝟒𝟎 ; 300 + 80} = 𝟑𝟎𝟎 (𝑺 − 𝑩 − 𝑫 − 𝑮)
𝑉3∗ (𝐻) = 𝑚𝑖𝑛{𝑽∗𝟐 (𝑫) + 𝑽𝟑 (𝑫 , 𝑯) ; 𝑉2∗ (𝐸 ) + 𝑉3 (𝐸 , 𝐻) ; 𝑉2∗ (𝐹 ) + 𝑉3 (𝐹 , 𝐻) }
= 𝑚𝑖𝑛{ 𝟐𝟔𝟎 + 𝟏𝟐𝟎 ; 300 + 100 ; 300 + 160}
= 𝟑𝟖𝟎 (𝑺 − 𝑩 − 𝑫 − 𝑯)
𝒙𝟒 ∈ {𝑷}
𝑉4∗ (𝑃) = 𝑚𝑖𝑛{𝑉3∗ (𝐺 ) + 𝑉4 (𝐺 , 𝑃) ; 𝑽𝟑∗ (𝑯) + 𝑽𝟒 (𝑯 , 𝑷)}
= 𝑚𝑖𝑛{ 300 + 200 ; 𝟑𝟖𝟎 + 𝟏𝟎𝟎} = 𝟒𝟖𝟎 (𝑺 − 𝑩 − 𝑫 − 𝑯 − 𝑷)
Le chemin optimal est S-B-D-H-P avec un coût de 480 um
II. Solution de l’exemple 2 (problème de sac à dos)
Les objets A B C
Poids (𝒘𝒊 ) 1 3 2
Utilité (𝒖𝒊 ) 30 80 65
Solution :
𝑤𝑔 représente la variation de la capacité du sac à dos
Toujours pour la première ligne du tableau de solution, on utilise la fonction suivante :
𝟎 𝒔𝒊 𝒘𝒈 < 𝒘𝒊
𝑩(𝑨,𝒘) = {
𝒖𝑨 𝒔𝒊 𝒘𝒈 ≥ 𝒘𝒊
0 𝑠𝑖 𝑤𝑔 < 1
⇒ 𝐵(𝐴,𝑤) {
30 𝑠𝑖 𝑤𝑔 ≥ 1
Pour les autres lignes, on utilise la fonction suivante pour remplir le tableau :
𝑩(𝒌−𝟏 , 𝒘𝒈 ) 𝒔𝒊 𝒘𝒈 < 𝒘𝒊
𝑩(𝒌,𝒘) = {
𝑴𝒂𝒙 [𝑩(𝒌−𝟏 , 𝒘𝒈 ) , 𝑩(𝒌−𝟏 ,𝒘𝒈 −𝒘𝒊 ) + 𝒖𝒊 ] 𝒔𝒊 𝒘𝒈 ≥ 𝒘𝒊
2
𝐵(𝐴 , 𝑤𝑔) 𝑠𝑖 𝑤𝑔 < 3
𝐵(𝐵,𝑤) = {
𝑀𝑎𝑥 [𝐵(𝐴 , 𝑤𝑔 ) , 𝐵(𝐴 ,𝑤𝑔−3) + 80] 𝑠𝑖 𝑤𝑔 ≥ 3
𝑩(𝑩,𝟑) = 𝑀𝑎𝑥[𝐵(𝐴 ,3) , 𝑩(𝑨 , 𝟑−𝟑) + 𝟖𝟎] = 𝑚𝑎𝑥[30 , 𝟎 + 𝟖𝟎] = 𝟖𝟎
𝐵(𝐵,4) = 𝑀𝑎𝑥[𝐵(𝐴 ,4) , 𝐵(𝐴 , 4−3) + 80] = 𝑚𝑎𝑥[30 , 30 + 80] = 110
{ 𝐵(𝐵,5) = 𝑀𝑎𝑥[𝐵(𝐴 ,5) , 𝐵(𝐴 , 5−3) + 80] = 𝑚𝑎𝑥[30 , 30 + 80] = 110
𝐵(𝐵 , 𝑤𝑔 ) 𝑠𝑖 𝑤𝑔 < 2
𝐵(𝐶,𝑤) = {
𝑀𝑎𝑥 [𝐵(𝐵 , 𝑤𝑔 ) , 𝐵(𝐵 ,𝑤𝑔−2) + 65] 𝑠𝑖 𝑤𝑔 ≥ 2
𝐵(𝐶,2) = 𝑀𝑎𝑥[𝐵(𝐵 ,2) , 𝐵(𝐵 , 2−2) + 65] = 𝑚𝑎𝑥[30 , 0 + 65] = 65
𝐵(𝐶,3) = 𝑀𝑎𝑥[𝐵(𝐵 ,3) , 𝐵(𝐵 , 3−2) + 65] = 𝑚𝑎𝑥[80 , 30 + 65] = 95
𝐵(𝐶,4) = 𝑀𝑎𝑥[𝐵(𝐵 ,4) , 𝐵(𝐵 , 4−2) + 65] = 𝑚𝑎𝑥[110 , 30 + 65] = 110
{𝑩(𝑪,𝟓) = 𝑀𝑎𝑥[𝐵(𝐵 ,5) , 𝑩(𝑩 , 𝟓−𝟐) + 𝟔𝟓] = 𝑚𝑎𝑥[110 , 𝟖𝟎 + 𝟔𝟓] = 𝟏𝟒𝟓
Tableau de solution :
𝒘𝒈
0 1 2 3 4 5
Les objets
L’objet A 0 30 30 30 30 30
Les objets A et B 0 30 30 80 110 110
Les objets A+B+C 0 30 65 95 110 145
- D'après la dernière ligne, l’utilité optimale est 145 c'est-à-dire d’après l’ajout de l’objet C.
- L’utilité optimale 145 est obtenue d’après le choix de 𝑩(𝑩 , 𝟓−𝟐) + 𝟔𝟓, entre 𝐵(𝐵 ,5) 𝑒𝑡 𝐵(𝐵 , 3) + 65,
- 𝐵(𝐵 , 3) est égal dans le tableau 80. On a obtenu cette utilité d’après le choix de 𝑩(𝑨 , 𝟑−𝟑) + 𝟖𝟎 entre
𝐵(𝐴 ,3) 𝑒𝑡 𝐵(𝐴 , 0) + 80
3
Comment choisir les objets ?
- L’utilité de 145 est obtenue d’après l’ajout de l’objet C. Le poids de cet objet =2<5 donc on choisit
l’objet C
- L’utilité de 80 est obtenue d’après l’ajout de l’objet B. Le poids de cet objet =3<5 donc on choisit les
objets B et C car la somme de ses poids est 3+2=5
- On ne peut pas ajouter l’objet A parce que cela va dépasser la capacité maximale W=5
- Maintenant si on calcule l’utilité totale des objets B et C, on trouve 80+65=145
les objets acceptés le poids l’utilité
l’objet B 3 80
l’objet C 2 65
la somme ∑ 𝑤𝑖 = 5 ∑ 𝑢𝑖 = 145
