2.5 Evaluation du trafic
Une autre étude sur le trafic routier, qui est celle
de son évaluation s'avère être indispensable si nous
voulons étudier l'affluence des automobiles. Et cela se fera en fonction
de certains critères qui ont été jugés pertinents
après les analyses. Apres le comptage des objets sur l'image, certains
paramètres seront connus, à savoir :
o Le nombre de véhicule qui ont été
recensé, correspond au nombre des objets sur l'image, après
l'application du technique de comptage ;
o La surface de la route ;
o La surface de tous les véhicules
détectés, se trouvant dans la circulation.
De ceux-ci va se dégager un programme linéaire
qui modélise le comportement de la circulation en un coin
donné.
2.5.1 Programme Linéaire
En optimisation mathématique, un problème
d'optimisation linéaire vise à minimiser, maximiser une fonction
linéaire sur un polyèdre convexe. La fonction que l'on minimise,
maximise ainsi que les contraintes sont décrites par des programmes
linéaires, d'où le nom donné à ces
problèmes. L'optimisation linéaire est la discipline qui
étudie ces problèmes et qui est également
désignée sous le nom de programmation linéaire, terme
introduit par George Dantzig vers 1947.
La programmation linéaire est par définition un
programme qui consiste à trouver n
variables X1, X2 , ..., X?? qui optimise
la quantité ? C?? X ??
?? ??=1 (1*) , et qui satisfont à l'ensemble des
contraintes que voici :
a11 X1 + a12 X2 + ? +
a13 X3 = ??1
a21 X1 + a22
X2 + ?+ a23 X3 = ??2
...
(2*) a??1 X1 + a??2 X2 + ?+
a??3 X3 = ????
...
a??1 X1 + a??2 X2 + ? +
a??3 X3 = ????
???? X1 = 0;X2 =
0;X3 = 0 (3*)
Page | 21
La quantité (1*) est la fonction
économique qu'il nous est demandé d'optimiser.
Les contraintes (2*) sont appelées les contraintes
liées car elles lient des variables, elles peuvent aussi se mettre sous
la forme =bi ; (i = 1,2,..., n).
Les contraintes (3*) sont appelées les contraintes libres
de non négativité.
Les variablesX1, X2 , ..., X?? sont
appelées pour le moment les variables de décisions mais plus loin
elles seront appelées les variables structurelles des
décisions.
Les C?? sont appelés les coefficients
économiques.
Il sera question de trouver les variables X1,
X2 , ..., X?? qui respectent l'ensemble des contraintes
et qui optimisent la fonction économique, et cette démarche passe
par certaine méthode spécialisée dans le résolution
d'un programme linéaire. Nous dans notre cas, nous allons parler de la
méthode graphique qui, elle aussi peut être utilisée pour
la résolution de programme linaire.
2.5.1.1 Méthode Graphique
Nous cherchons à modéliser un problème
pratique par un programme linéaire. Dans la démarche visant
à résoudre ce programme, étant donné que nous
n'aurons qu'à représenter deux variables, la méthode
graphique semble être l'une des premières méthodes
utilisées à ce sujet.
Système d'axes
Une des conditions de la réussite de notre
représentation graphique est le choix d'un système d'axes. Un
mauvais choix peut rendre une représentation non claire et
imprécise.
|
Grace aux contraintes de non-négativité des
variables de décision, nous nous intéressons seulement au cadran
positif, région communément appelé « la
région des solutions possibles
du problème »
|
|
Représentation graphique des
contraintes
Parmi les solutions possibles d'un problème, il y aura
ceux qui vont satisfaire après l'application de la méthode toutes
les contraintes du programme, appelés solutions réalisables, et
ceux qui vont satisfaire une partie ou aucune de ces contraintes,
appelés solutions non réalisables. Une représentation
graphique des inégalités nous permettra de déterminer
l'ensemble des solutions réalisables.
Résolution graphique du Programme
linéaire
Cette méthode se base sur les théorèmes
fondamentaux du programme linéaire que voici : o Théorème
2 (de Weyl)
Page | 22
Dans ????, tout système d'équation ou
d'inéquation linéaire détermine un ensemble convexe qui
est :
soit ensemble vide : c'est à dire les contraintes sont
contradictoire ;
Optimiser (z=????X??
+ ??2X2)
{X?? = ?? ,X2 = ??
X2= 2X?? + ?? X2 = X??
L'ensemble des solutions réalisables est vide ; Aucun
point de ??2 ne satisfait les 2 contraintes ; cela signifie que les
contraintes sont contradictoires ou incompatibles.
soit un polyèdre convexe ; Optimiser
(z=????X?? +
??2X2)
{X?? = 2 X?? + X2 = ?? -X??+ X2= ?? X?? =
?? , X2 = ??
|
|
|
L'ensemble des contraintes détermine un
polyèdre convexe de n=5 sommets (L'ensemble des SBR est un
polyèdre convexe)
soit un ensemble convexe non borné : c'est à dire
la solution optimale est infinie.
Optimiser (z=????X??
+ ??2X2)
{X?? - X2 = ?? -2X?? + X2 = ?? X?? = ??
,X2 = ??
|
|
|
L'ensemble des SBR est un ensemble convexe non
borné.
o Théorème 3 (THEOREME D'OPTIMALITE)
Dans un P.L dont l'ensemble des SBR est un polyèdre
convexe, l'optimum est nécessairement atteint en un sommet du
polyèdre convexe ; ce qui voudrait dire que la fonction
économique z atteindra son optimum (max ou min) nécessairement en
un sommet.
o Théorème 6 (THÉORÈME
D'INDÉPENDANCE LINÉAIRE DES VECTEURS DE BASE)
Ce théorème stipule qu'il y a une
identité entre la solution de base réalisable et la notion de
sommet du polyèdre convexe engendré par les contraintes. En
d'autres termes, un sommet du polyèdre convexe engendré par les
contraintes est une solution de base réalisable.
Page | 23
Grace à la méthode graphique nous serons en
mesure de résoudre notre programme linéaire, d'y ressortir la
solution optimal. Au regard de notre travail qui porte sur le robot roulage
intelligent amélioré, il sera question de trouver un
modèle mathématique qui exprime son comportement.
| 
