4.9 Les pro grammes de tran sport
151
© Dunod – Toute reproduction non autorisée est un délit.
a) On observe que la somme des demandes (ici 73) est égale à la somme des dis po -
ni bi li tés.
On note m le nombre d’ori gines et n celui des des ti nations.
b) Soient a i les quan ti tés dis po nibles, b j les quan ti tés deman dées, c ij les coûts de
tran sport ; la solu tion du pro blème revient à trou ver les valeurs numé riques des mn
nombres non néga tifs x ij qui repré sente la quan tité livrée depuis l’ori gine i à la des -
ti nation j, tels que :
a
m
i51
a i 5 a
n
j51
b j : offre 5 demande
(4.1)
toute ori gine i livre entiè re ment sa quan tité dis po nible a i :
a
n
j51
x ij 5 a i 1 i 5 1, 2, c , m 2
(4.2)
à toute des ti nation j est livrée toute sa demande b j :
a
m
i 51
x ij 5 b j ( j 5 1, 2, c , n)
(4.3)
et que la fonc tion éco no mique (coût glo bal du tran sport) :
a
m
i 51
a
n
j51
c ij # x ij 5 z
(4.4)
soit mini male.
Nous ver rons plus tard que ce type de pro blème appar tient à la classe des pro -
grammes linéaires, mais il n’est pas néces saire de lui appli quer les méthodes géné -
rales de la pro gram ma tion mathéma tique : ce que nous nous gar de rons de faire,
même si l’on peut inter préter les méthodes par ti cu lières qui vont suivre en termes de
pro gram ma tion mathéma tique.
Consi dé ra tions pré li mi naires
Pour résoudre un tel pro blème, on peut tout d’abord d’obte nir une solu tion admissible,
c-à-d conforme aux rela tions (4.1), (4.2) et (4.3) sans se pré oc cu per de la fonc tion éco -
no mique (4.4). Pour qu’une telle solu tion soit uti li sable pour la suite de l’algo rithme,
il convient qu’elle ne soit pas dégénérée, c’est- à-dire qu’elle com porte exac te ment :
n # m 2 1 n 1 m 2 12 5 1 n 2 12 # 1 m 2 12
variables nulles
1
, et donc m 1 n 2 1 variables positives.
Nous ver rons d’ailleurs que, sur le graphe biparti asso cié à une solu tion, seule une
solu tion de base, c’est- à-dire répon dant à la condi tion ci- dessus, four nit un arbre.
Il existe une méthode extrê mement facile pour en obte nir une ; mal heu reu se ment
elle n’a pas de but éco no mique, alors que nous serons ensuite confron tés à un pro -
1. Il y a n # m inconnues, liées par n 1 m rela tions ; mais ces n 1 m rela tions ne sont pas indé pen
dantes, puisque la somme des seconds membres des n pre mières est la même que la somme des
seconds membres des m autres, il y a au plus n 1 m 2 1 rela tions indé pen dantes. Il doit donc y
avoir, dans une solu tion admissible, au moins n # m 2 (n 1 m 2 1) variables nulles.
151
© Dunod – Toute reproduction non autorisée est un délit.
a) On observe que la somme des demandes (ici 73) est égale à la somme des dis po -
ni bi li tés.
On note m le nombre d’ori gines et n celui des des ti nations.
b) Soient a i les quan ti tés dis po nibles, b j les quan ti tés deman dées, c ij les coûts de
tran sport ; la solu tion du pro blème revient à trou ver les valeurs numé riques des mn
nombres non néga tifs x ij qui repré sente la quan tité livrée depuis l’ori gine i à la des -
ti nation j, tels que :
a
m
i51
a i 5 a
n
j51
b j : offre 5 demande
(4.1)
toute ori gine i livre entiè re ment sa quan tité dis po nible a i :
a
n
j51
x ij 5 a i 1 i 5 1, 2, c , m 2
(4.2)
à toute des ti nation j est livrée toute sa demande b j :
a
m
i 51
x ij 5 b j ( j 5 1, 2, c , n)
(4.3)
et que la fonc tion éco no mique (coût glo bal du tran sport) :
a
m
i 51
a
n
j51
c ij # x ij 5 z
(4.4)
soit mini male.
Nous ver rons plus tard que ce type de pro blème appar tient à la classe des pro -
grammes linéaires, mais il n’est pas néces saire de lui appli quer les méthodes géné -
rales de la pro gram ma tion mathéma tique : ce que nous nous gar de rons de faire,
même si l’on peut inter préter les méthodes par ti cu lières qui vont suivre en termes de
pro gram ma tion mathéma tique.
Consi dé ra tions pré li mi naires
Pour résoudre un tel pro blème, on peut tout d’abord d’obte nir une solu tion admissible,
c-à-d conforme aux rela tions (4.1), (4.2) et (4.3) sans se pré oc cu per de la fonc tion éco -
no mique (4.4). Pour qu’une telle solu tion soit uti li sable pour la suite de l’algo rithme,
il convient qu’elle ne soit pas dégénérée, c’est- à-dire qu’elle com porte exac te ment :
n # m 2 1 n 1 m 2 12 5 1 n 2 12 # 1 m 2 12
variables nulles
1
, et donc m 1 n 2 1 variables positives.
Nous ver rons d’ailleurs que, sur le graphe biparti asso cié à une solu tion, seule une
solu tion de base, c’est- à-dire répon dant à la condi tion ci- dessus, four nit un arbre.
Il existe une méthode extrê mement facile pour en obte nir une ; mal heu reu se ment
elle n’a pas de but éco no mique, alors que nous serons ensuite confron tés à un pro -
1. Il y a n # m inconnues, liées par n 1 m rela tions ; mais ces n 1 m rela tions ne sont pas indé pen
dantes, puisque la somme des seconds membres des n pre mières est la même que la somme des
seconds membres des m autres, il y a au plus n 1 m 2 1 rela tions indé pen dantes. Il doit donc y
avoir, dans une solu tion admissible, au moins n # m 2 (n 1 m 2 1) variables nulles.