Brevet FR2942666A1 — publié le 20100903

Procédé de recherche d'une solution d'une optimisation d'un vecteur de variables, programme d'ordinateur associé et procédé pour réaliser des tâches réelles au moyen de ressources réelles La présente invention concerne un procédé de recherche d'une solution d'une optimisation d'un vecteur de variables, un programme d'ordinateur associé et un procédé pour réaliser des tâches réelles au moyen de ressources réelles. Il est connu de l'état de la technique un procédé de recherche d'une solution d'une optimisation d'un vecteur de variables sous respect de premier et second jeux de contraintes sur ce vecteur de variables, comprenant : - déterminer une partie de vecteurs générateurs d'une famille de vecteurs générateurs générant un ensemble, dit ensemble du second jeu de contraintes, regroupant les vecteurs de variables qui respectent le second jeu de contraintes, la partie de vecteurs générateurs générant un sous-ensemble de l'ensemble du second jeu de contraintes ; - déterminer, dans le sous-ensemble, un vecteur solution, dit vecteur solution restreint de l'optimisation du vecteur de variables sous respect du premier jeu de contraintes ; - ajouter, à la partie de vecteurs générateurs, des nouveaux vecteurs générateurs de la famille de vecteurs générateurs, dits nouveaux vecteurs générateurs à ajouter, afin d'obtenir une partie augmentée de vecteurs générateurs générant un nouveau sous-ensemble ; - déterminer, dans le nouveau sous-ensemble, un nouveau vecteur solution, dit nouveau vecteur solution restreint, de l'optimisation du vecteur de variables sous respect du premier jeu de contraintes. Il est connu de prendre comme nouveaux vecteurs générateurs à ajouter ceux ayant les meilleurs coûts réduits, c'est-à-dire généralement les coûts réduits négatifs les plus faibles dans le cas d'une minimisation pour le sous-problème. Le nombre de nouveaux vecteurs générateurs à ajouter est généralement fixé, soit de manière absolue (par exemple, on ajoute les 10 000 meilleurs ), soit de manière relative (par exemple, on ajoute les 10% meilleurs). Un problème de l'état de la technique est que, pour obtenir une convergence rapide, il faut ajouter beaucoup de nouveaux vecteurs générateurs. Or, ce nombre ne peut pas être pris trop grand, sous peine de ne plus être capable de faire les calculs. Un but de l'invention est d'améliorer le procédé de l'état de la technique pour obtenir une convergence rapide, sans nécessiter d'ajouter un trop grand nombre de nouveaux vecteurs générateurs. Ainsi, un objet de l'invention est un procédé de recherche d'une solution d'une optimisation d'un vecteur de variables, sous respect de premier et second jeux de contraintes sur ce vecteur de variables, du type comprenant : - déterminer une partie de vecteurs générateurs d'une famille de vecteurs générateurs générant un ensemble, dit ensemble du second jeu de contraintes, regroupant les vecteurs de variables qui respectent le second jeu de contraintes, la partie de vecteurs générateurs générant un sous-ensemble de l'ensemble du second jeu de contraintes ; - déterminer, dans le sous-ensemble, un vecteur solution, dit vecteur solution restreint, de l'optimisation du vecteur de variables sous respect du premier jeu de contraintes ; le procédé étant caractérisé en ce qu'il comprend : - rechercher au moins deux nouveaux vecteurs générateurs de la famille de vecteurs générateurs, dits nouveaux vecteurs générateurs disjoints, situés hors de la partie de vecteurs générateurs et ayant des supports dans leur base canonique de l'ensemble du second jeu de contraintes disjoints deux à deux ; - ajouter, à la partie de vecteurs générateurs, des nouveaux vecteurs générateurs de la famille de vecteurs générateurs, dits nouveaux vecteurs générateurs à ajouter, comprenant au moins les nouveaux vecteurs générateurs disjoints, afin d'obtenir une partie augmentée de vecteurs générateurs générant un nouveau sous-ensemble ; - déterminer, dans le nouveau sous-ensemble, un nouveau vecteur solution, dit nouveau vecteur solution restreint, de l'optimisation du vecteur de variables sous respect du premier jeu de contraintes. Selon d'autres caractéristiques de l'invention : - les nouveaux vecteurs générateurs disjoints sont déterminés à partir du vecteur solution restreint ; - les premier et second jeux de contraintes sont des premier et second jeux de contraintes linéaires ; - l'ensemble du second jeu de contraintes est un polyèdre borné non vide ayant des points extrêmes, et les points extrêmes forment la famille de vecteurs générateurs ; - les nouveaux vecteurs générateurs à ajouter sont constitués uniquement des nouveaux vecteurs générateurs disjoints ; - l'optimisation et les premier et second jeux de contraintes ont été obtenus à partir d'une modélisation de ressources réelles et de tâches réelles que ces ressources réelles sont destinées à réaliser ; - la recherche des nouveaux vecteurs générateurs disjoints comprend : déterminer une solution, dite solution duale restreinte, d'un problème dual associé, par un lien de dualité forte, à l'optimisation du vecteur de variables dans le sous-ensemble sous respect du premier jeu de contraintes ; déterminer, en tant que nouveaux vecteurs générateurs disjoints, des nouveaux vecteurs générateurs de l'ensemble du second jeu de contraintes ayant un coût réduit, calculé à partir de la solution duale restreinte, négatif lorsque l'optimisation est une minimisation, ou positif lorsque l'optimisation est une maximisation ; la recherche des nouveaux vecteurs générateurs disjoints comprend : déterminer, comme un des nouveaux vecteurs générateurs disjoints, le vecteur générateur de l'ensemble du second jeu de contraintes ayant un coût réduit, calculé à partir de la solution duale restreinte, négatif le plus petit lorsque l'optimisation est une minimisation, ou positif le plus grand lorsque l'optimisation est une maximisation ; - la recherche des nouveaux vecteurs générateurs disjoints comprend : déterminer un ensemble de nouveaux vecteurs générateurs ayant un coût réduit, calculé à partir de la solution duale restreinte, négatif lorsque l'optimisation est une minimisation, ou positif lorsque l'optimisation est une maximisation ; déterminer, comme nouveaux vecteurs générateurs disjoints, des vecteurs générateurs de l'ensemble de nouveaux vecteurs générateurs ayant des supports dans leur base canonique disjoints deux à deux et ayant les coûts réduits, calculés à partir de la solution duale restreinte, négatifs les plus petits lorsque l'optimisation est une minimisation, ou positif les plus grands lorsque l'optimisation est une maximisation ; - la détermination des vecteurs générateurs de l'ensemble de nouveaux vecteurs générateurs ayant des supports dans leur base canonique disjoints deux à deux et ayant les coûts réduits négatifs les plus petits lorsque l'optimisation est une minimisation, ou positif les plus grands lorsque l'optimisation est une maximisation, comprend : sélectionner le vecteur générateur de l'ensemble de nouveaux vecteurs générateurs ayant le coût réduit le plus petit ; de manière itérative, sélectionner le vecteur générateur de l'ensemble de nouveaux vecteurs générateurs ayant un support disjoint de chacun des nouveaux vecteurs générateurs déterminés auparavant et ayant le coût réduit négatif le plus petit lorsque l'optimisation est une minimisation, ou positif le plus grand lorsque l'optimisation est une maximisation ; - l'ensemble de nouveaux vecteurs générateurs comprend le vecteur générateur de l'ensemble du second jeu de contraintes ayant le coût réduit négatif le plus petit lorsque l'optimisation est une minimisation, ou positif le plus grand lorsque l'optimisation est une maximisation ; - la recherche des nouveaux vecteurs générateurs disjoints comprend : déterminer, en tant qu'un des nouveaux vecteurs générateurs disjoints, le vecteur générateur de l'ensemble du second jeu de contraintes ayant le coût réduit, calculé à partir de la solution duale restreinte, négatif le plus petit lorsque l'optimisation est une minimisation, ou positif le plus grand lorsque l'optimisation est une maximisation ; de manière itérative, déterminer, en tant qu'un des nouveaux vecteurs générateurs disjoints, le nouveau vecteur générateur ayant un support disjoint de chacun des nouveaux vecteurs générateurs déterminés auparavant et ayant un coût réduit, calculé à partir de la solution duale restreinte, négatif le plus petit lorsque l'optimisation est une minimisation, ou positif le plus grand lorsque l'optimisation est une maximisation ; - les étapes : rechercher des nouveaux vecteurs générateurs disjoints ; ajouter des nouveaux vecteurs à ajouter à la partie de vecteurs générateurs ; déterminer le nouveau vecteur solution restreint ; sont itérées ; - les étapes : rechercher des nouveaux vecteurs générateurs disjoints ; ajouter des nouveaux vecteurs à ajouter à la partie de vecteurs générateurs ; déterminer le nouveau vecteur solution restreint ; sont itérées tant qu'il est possible de déterminer un vecteur générateur du sous-ensemble ayant un coût réduit, calculé à partir de la solution duale restreinte, négatif lorsque l'optimisation est une minimisation, ou positif lorsque l'optimisation est une maximisation. L'invention a également pour objet un programme d'ordinateur comprenant des portions de codes qui, lorsqu'exécutées sur un ordinateur, entraînent la mise en oeuvre d'un procédé selon l'invention. L'invention a également pour objet un procédé pour réaliser des tâches réelles au moyen de ressources réelles, caractérisé en ce qu'il comprend : - la modélisation du problème consistant à réaliser les tâches réelles au moyen des ressources réelles en un problème optimisation d'un vecteur de variables, sous respect de premier et second jeux de contraintes sur ce vecteur de variables ; - la recherche d'une solution au problème optimisation du vecteur de variables, sous respect des premier et second jeux de contraintes sur ce vecteur de variables au moyen d'un procédé selon l'invention ; - la réalisation des tâches réelles au moyen des ressources réelles conformément à la solution trouvée. Les caractéristiques et avantages de l'invention seront apparents dans la description qui va suivre de deux modes de réalisation de l'invention, donnés uniquement à titre d'exemples non limitatifs. La description fait référence aux figures annexées, comprenant :, - sur la figure 1 : un schéma blocs d'un procédé, selon l'invention, de recherche d'une solution à un problème d'optimisation ; - sur la figure 2 : un schéma blocs d'une variante d'une étape de la figure 1. Dans la présente demande de brevet, la résolution d'une équation signifie aussi bien la résolution exacte pour trouver la valeur de la solution exacte de l'équation, que des résolutions approchées donnant des valeurs proches de la valeur de la solution exacte. On considère un ensemble de tâches réelles que l'on souhaite réaliser au moyen d'un ensemble de ressources réelles. Par exemple, dans le domaine du transport de voyageurs et/ou de marchandises, les ressources réelles sont des ressources humaines (agent de conduite, équipage, pilote, etc.) ou bien des ressources matérielles (locomotives, voitures, etc.). Les tâches sont alors par exemples des tournées de transport de voyageurs et/ou de marchandises. En référence à la figure 1, on va à présent décrire un premier procédé 100 pour déterminer comment utiliser les ressources réelles pour réaliser les tâches réelles. Au cours d'une étape 102, des variables sont définies à partir des ressources réelles. Le nombre et la signification des variables dépendent du problème considéré. Par exemple, si on s'intéresse à choisir des locomotives pour desservir des gares, il est possible d'associer chaque variable à une locomotive et à une gare, de sorte que cette variable prenne la valeur 1 lorsque la locomotive dessert la gare, et la valeur 0 dans le cas contraire. Dans ce cas, toutes les variables appartiennent à l'ensemble {0,1}. Cet exemple sera repris dans le reste de la description pour illustrer le procédé 100. Cependant, pour d'autres problèmes, les variables pourraient être prises dans des ensembles différents. Les variables sont regroupées dans un vecteur de variables x. Dans l'exemple décrit, x {0,1}n , n étant le nombre de variables définies. En outre, toujours à partir des ressources réelles, au cours d'une étape 104, un coût pour chaque variable est défini. Dans l'exemple décrit, un coût unitaire est défini pour chaque variable, et ces coûts unitaires sont regroupés dans un vecteur de coût c, avec ce R+n, R+ étant l'ensemble des réels positifs. Ainsi, la desserte de la gare i par la locomotive j est associée à un coût. Au cours d'une étape 106, un coût global C des variables est défini. Le coût global C est une fonction du vecteur de variables x qui tient compte des coûts précédents. Dans l'exemple décrit, le coût global C est défini comme étant la somme du coût de chaque variable. Ainsi, le coût global C est défini par C(x) =c`x . À partir des tâches réelles et des ressources réelles, au cours d'une étape 108, des premier et second jeux de contraintes sur le vecteur de variables x sont définis. Dans l'exemple décrit, les contraintes sont linéaires. Plus précisément, les contraintes sont des inégalités sur le vecteur de variables x, qui s'écrivent : Ax>_a Bx>_b avec AE Rmxn, BE Rpxn et a,bE Rn. Dans cet exemple, il y a donc m+ p contraintes. Le second jeu de contraintes Bx>_b est choisi de manière à pouvoir être résolu, dans l'exemple décrit sur l'ensemble {0,1}, par des méthodes connues. De préférence, si le domaine des variables est discret, on � relâche � ces variables sur un intervalle continu pour le premier jeu de contraintes, ce qui permet de faire des approximations. Dans l'exemple décrit, le vecteur de variables x est relâché sur Rn ou bien sur [0,1]n. Au cours d'une étape 110, le problème réel � réaliser les tâches réelles au moyen des ressources réelles � est modélisé par un problème initial (P) qui est un problème d'optimisation du vecteur de variables x, sous respect des premier et second jeux de contraintes linéaires Ax a , Bx b. Dans la présente description, un problème d'optimisation d'un vecteur de variables signifie un problème qui consiste à trouver le vecteur de variables faisant prendre à une fonction de ce vecteur de variables un extremum (maximum ou minimum). Dans l'exemple décrit, le problème d'optimisation consiste à trouver le vecteur de variables x faisant prendre à la fonction de coût globale C une valeur minimale. Le problème initial (P) s'exprime ainsi sous la forme mathématique : min cx (P) Ax a Bx b avec c,a,bE Rn, AE Rm>n et AE R'� _b est choisi. Cela ne signifie pas que les vecteurs générateurs de la famille {x.} sont connus a priori explicitement. En JEJ pratique, le nombre de vecteurs générateurs est même tellement élevé qu'il n'est pas envisageable de tous les calculer. Dans l'exemple décrit, l'ensemble X est un polyèdre borné non vide ayant des points extrêmes (appelés aussi � sommets �). Il est ainsi possible d'utiliser la décomposition de Dantzig Wolfe de sorte que l'étape 112 comprend une étape 114 de décomposition du problème suivant la décomposition de Dantzig Wolfe. Cette décomposition donne un problème, appelé problème maître (PM), exprimé sous la forme mathématique : (PM avec {x.}jEJ les points extrêmes du polyèdre X , J étant l'ensemble des indices utilisés. Dans l'exemple décrit, ce sont ces points extrêmes qui forment la famille de 15 vecteurs générateurs {xi}JEJ . La décomposition de Dantzig Wolfe présente l'avantage de réduire le nombre de contraintes, en contrepartie d'un nombre plus élevé de variables. On remarquera qu'il peut être prouvé mathématiquement que, dans ce cas, la solution du problème initial se trouve sur un des points extrêmes du polyèdre. 20 Certaines des étapes qui vont suivre sont itérées. Ainsi, l'indice k est utilisé pour distinguer les différentes itérations. Pour la première itération, comme cela est illustré sur la figure 1, on prend par exemple k égal à zéro. Au cours d'une étape 115, une partie de vecteurs générateurs de la famille de vecteurs générateurs {x.} est déterminée. La partie de vecteurs JEJ 25 générateurs génère un sous-ensemble Xk de l'ensemble X . Dans l'exemple décrit, on détermine donc un certain nombre de points extrêmes du polyèdre X . Cette détermination est réalisée au moyen de méthodes connues en soi, par exemple des méthodes basées sur le simplexe - phase I. Au cours d'une étape 116, un vecteur solution, dit vecteur solution restreint zk , du problème d'optimisation minC(x) du vecteur de variables x sous respect du premier jeu de contraintes Ax>_a est déterminé dans le sous-ensemble Xk. On remarquera que le second jeu de contraintes n'est pas pris en compte directement comme contrainte, mais est pris en compte indirectement grâce à l'ensemble dans lequel la solution est recherchée. Cette optimisation sous respect du premier jeu de contraintes, limitée au sous ensemble Xk, est appelée problème maître restreint (PMR). Dans l'exemple décrit, le problème maître restreint (PMR) s'exprime sous la forme mathématique : min 12i cx j jE Jk a (PMR jE Jk 12i =1 jE Jk 2>_0 Le problème maître restreint (PMR) est par exemple résolu au moyen du simplexe, en utilisant ou bien l'algorithme primat, ou bien l'algorithme dual. En variante, le problème maître restreint est résolu par la méthode des points intérieurs. Afin d'améliorer ce vecteur solution restreint pour se rapprocher de la solution finale, on va chercher des nouveaux vecteurs générateurs de la famille {xj}jEJ, situés hors de la partie de vecteurs générateurs {xj}jEJk, à ajouter à cette partie de vecteurs générateurs {xj } EJk . Ainsi, au cours d'une étape 118, on recherche au moins deux nouveaux vecteurs générateurs de la famille de vecteurs générateurs {xj}jEJ , dits nouveaux vecteurs générateurs disjoints .zl, zti, situés hors de la partie de vecteurs générateurs {xj}jEJk et ayant des supports dans leur base canonique disjoints deux à deux. La base canonique est constituée des vecteurs ayant une composante (c'est-à-dire une variable) égale à 1, et les autres composantes (variables) nulles. Deux vecteurs sont disjoints lorsque chacun d'eux comprend au moins une composante non nulle, alors que, dans l'autre vecteur, cette composante (variable) est nulle. Dans l'exemple décrit, l'étape 118 comprend une étape 120 au cours de laquelle on détermine une solution, dite solution duale restreinte 77k, d'un problème dual associé, par un lien de dualité forte, à l'optimisation minC(x) du vecteur de variables x dans le sous-ensemble X k sous respect du premier jeu de contraintes Axa . La solution duale restreinte 7T-k permet de calculer un coût réduit (cûTCkA)x pour chaque vecteur de variables x. L'étape 118 comprend en outre une étape 122 au cours de laquelle on détermine, en tant que nouveaux vecteurs générateurs disjoints .j, î , des nouveaux vecteurs générateurs de l'ensemble du second jeu de contraintes X ayant un coût réduit, calculé à partir de la solution duale restreinte 7Lk, négatif. Dans l'exemple décrit, l'étape 122 comprend une étape 124 au cours de laquelle on détermine un ensemble de vecteurs générateurs Y appartenant à l'ensemble du second jeu de contraintes X , ayant un coût réduit, calculé à partir de la solution duale restreinte 7L-k, négatif. De préférence, l'ensemble de vecteurs générateurs Y comprend le vecteur générateur de l'ensemble du second jeu de contraintes X ayant le coût réduit le plus petit. Le fait que le coût réduit est négatif assure que les vecteurs de l'ensemble Y sont hors de la partie de vecteurs générateurs {x; } E Jk . L'étape 122 comprend en outre une étape 126 au cours de laquelle on détermine, comme nouveaux vecteurs générateurs disjoints, des vecteurs générateurs de l'ensemble de nouveaux vecteurs générateurs ayant des supports dans leur base canonique disjoints deux à deux et ayant les coût réduits, calculés à partir de la solution duale restreinte 7L-k, les plus petits. Plus précisément, dans l'exemple décrit, l'étape 126 comprend une étape 128 au cours de laquelle on sélectionne le vecteur générateur, noté .j, de l'ensemble de vecteurs générateurs Y ayant le coût réduit le plus petit. De préférence, le nouveau vecteur générateur X1 est le vecteur générateur de l'ensemble du second jeu de contraintes X ayant le coût réduit le plus petit. Ce nouveau vecteur générateur est donc la solution de l'équation min((cùTckA)x),xE X . Cette équation est résolue par des méthodes connues en soi. Comme indiqué au début de la description, cette résolution peut se faire de manière approchée. Cependant, de préférence, cette équation est résolue de manière exacte pour au moins une itération du procédé. L'étape 126 comprend en outre une étape 130, répétée de manière itérative, au cours de laquelle on sélectionne le vecteur générateur, noté Xti , de l'ensemble de vecteurs générateurs Y ayant un support disjoint de chacun des nouveaux vecteurs générateurs déterminés auparavant Xi, On obtient ainsi les nouveaux vecteurs générateurs disjoints avec i=2, 3, ... Dans l'exemple décrit, les nouveaux vecteurs générateurs à ajouter sont uniquement constitués des nouveaux vecteurs générateurs disjoints , zti . Au cours d'une étape 132, les nouveaux vecteurs générateurs à ajouter sont ajoutés à la partie de vecteurs générateurs , afin d'obtenir une partie de vecteurs générateurs augmentee {x1}EJk+, générant un nouveau sous- ensemble Y'. Au cours d'une étape 134, un nouveau vecteur solution, dit nouveau vecteur solution restreint xk+1 de l'optimisation minC(x) du vecteur de variables x xER" sous respect du premier jeu de contraintes Ax>ù a est déterminé dans le nouveau sous-ensemble Xk+1 Dans l'exemple décrit, les étapes 118 à 134 sont alors itérées (k=k+1) tant qu'il est possible de déterminer un vecteur générateur du sous-ensemble Xk ayant un coût réduit, calculé à partir de la solution duale restreinte 7Lk, négatif. On obtient ainsi une diversification efficace grâce au fait que les nouveaux vecteurs générateurs à ajouter comprennent les nouveaux vecteurs générateurs disjoints XI, Xti . Enfin, au cours d'une étape 136, les ressources réelles sont utilisées, de la manière définie par le vecteur de variables solution obtenu à la fin des itérations, pour réaliser les tâches réelles. En référence à la figure 2, dans un second mode de réalisation, l'étape 122 comprend une étape 138 au cours de laquelle on détermine, en tant qu'un des nouveaux vecteurs générateurs disjoints zl, le vecteur générateur de l'ensemble du second jeu de contraintes X ayant le coût réduit, calculé à partir de la solution duale restreinte 7L-k, négatif ou nul le plus petit. Le nouveau vecteur xl est donc la solution de l'équation min((c ùTCkA)x), x E X . En outre, l'étape 122 comprend une étape 140, répétée de manière itérative, au cours de laquelle on détermine, en tant qu'un des nouveaux vecteurs générateurs disjoints zti , le nouveau vecteur générateur ayant un support disjoint (à nouveau dans la base canomique) de chacun des nouveaux vecteurs générateurs déterminés auparavant et ayant un coût réduit, calculé à partir de la solution duale restreinte Tck, le plus petit. Cela revient donc à résoudre, à l'itération 1 sur l'étape 140, l'équation min((c ùTCkA)x), x E X` , où Xi est égal à l'ensemble X sans les vecteurs ayant un support commun avec au moins un des nouveaux vecteurs générateurs déterminés auparavant. Ce mode de réalisation est plus lent que le premier, car il nécessite de résoudre plusieurs fois l'équation min((c ùTCkA)x), mais il donne aussi de meilleurs résultats. Dans l'exemple décrit précédent, on recherchait les coûts réduits négatifs les plus petits car l'exemple d'optimisation était une minimisation. Lorsque l'optimisation est une maximisation, on recherche les coûts réduits positifs les plus grands. REVENDICATIONS1. Procédé pour réaliser des tâches réelles au moyen de ressources réelles, caractérisé en ce qu'il comprend : - la modélisation (110) du problème consistant à réaliser les tâches réelles au moyen des ressources réelles en un problème optimisation (minC(x)) d'un vecteur de variables (x), sous respect de premier et second jeux de contraintes ( Ax a , Bx b) sur ce vecteur de variables (x) ; - la recherche (112, 115, 116, 118, 132, 134) d'une solution au problème optimisation (min C(x)) du vecteur de variables (x), sous respect des premier et second jeux de contraintes (Ax >_ a , Bx b ) sur ce vecteur de variables (x) au moyen d'un procédé comprenant : + déterminer (115, 132) une partie de vecteurs générateurs (~xJ }JEJA , ~x }JET ä ) d'une famille de vecteurs générateurs (~x1 }JE J) générant un ensemble, dit ensemble du second jeu de contraintes (X ), regroupant les vecteurs de variables (x) qui respectent le second jeu de contraintes (Bx >_ b ), la partie de vecteurs générateurs ({x.} , , ) générant un sous-ensemble (Xk Xk+1) de J jEJ J jEJ l'ensemble du second jeu de contraintes (X) ; + déterminer (116, 134), dans le sous-ensemble un vecteur solution, dit vecteur solution restreint (,xk xk+l) de l'optimisation (min C(x)) du vecteur de variables (x) sous respect du premier jeu de contraintes (Ax>_a); + rechercher (118) au moins deux nouveaux vecteurs générateurs de la famille de vecteurs générateurs ({x1 }JEJ ), dits nouveaux vecteurs générateurs disjoints (x, ), situés hors de la partie de vecteurs générateurs (Ix1 }JE~k) et ayant des supports dans leur base canonique disjoints deux à deux ; + ajouter (132), à la partie de vecteurs générateurs (~x1 }JET, ), des nouveaux vecteurs générateurs de la famille de vecteurs générateurs (}xJ}JEJ ), dits nouveaux vecteurs générateurs à ajouter, comprenant au moins les nouveauxvecteurs générateurs disjoints (z, ), afin d'obtenir une partie augmentée de vecteurs générateurs ({x~ }JEJkä ) générant un nouveau sous-ensemble (X k+' ) + déterminer (134), dans le nouveau sous-ensemble (P+�, un nouveau vecteur solution, dit nouveau vecteur solution restreint (.x'+') de l'optimisation (min C(x)) du vecteur de variables (x) sous respect du premier jeu de contraintes (Ax >_ a ), - la réalisation (136) des tâches réelles au moyen des ressources réelles conformément à la solution trouvée. (Ax>_a). 2. Procédé selon la revendication 1, caractérisé en outre en ce que les nouveaux vecteurs générateurs disjoints ( , z,) sont déterminés à partir du vecteur solution restreint (r ). 3. Procédé selon la revendication 1 ou 2, caractérisé en outre en ce que les premier et second jeux de contraintes (Ax a , Bx b ) sont des premier et second jeux de contraintes linéaires. 4. Procédé selon la revendication 3, caractérisé en outre en ce que l'ensemble du second jeu de contraintes (X) est un polyèdre borné non vide ayant des points extrêmes, et en ce que les points extrêmes forment la famille de vecteurs générateurs (}xi}JEj ). 5. Procédé selon l'une quelconque des revendications 1 à 4, caractérisé en outre en ce que, les nouveaux vecteurs générateurs à ajouter sont constitués uniquement des nouveaux vecteurs générateurs disjoints ). 6. Procédé selon l'une quelconque des revendications 1 à 5, caractérisé en outre en ce que l'optimisation (min C(x)) et les premier et second jeux de contraintes (Ax >_ a , Bx >_ b) ont été obtenus à partir d'une modélisation de ressources réelles et de tâches réelles que ces ressources réelles sont destinées à réaliser. 7. Procédé selon l'une quelconque des revendications 1 à 6, caractérisé en outre en ce que la recherche (118) des nouveaux vecteurs générateurs disjoints (x, , x,) comprend :- déterminer (120) une solution, dite solution duale restreinte (e ), d'un problème dual associé, par un lien de dualité forte, à l'optimisation (min C(x� du vecteur de variables (x) dans le sous-ensemble (xk) sous respect du premier jeu de contraintes (A(x)>_ a) ; - déterminer (122), en tant que nouveaux vecteurs générateurs disjoints (z, , ), des nouveaux vecteurs générateurs de l'ensemble du second jeu de contraintes (X) ayant un coût réduit, calculé à partir de la solution duale restreinte (7rk ), négatif lorsque l'optimisation est une minimisation, ou positif lorsque l'optimisation est une maximisation. 8. Procédé selon la revendication 7, caractérisé en outre en ce que la recherche (118) des nouveaux vecteurs générateurs disjoints ( , ) comprend : - déterminer (128, 138), comme un des nouveaux vecteurs générateurs disjoints (z, ), le vecteur générateur de l'ensemble du second jeu de contraintes (X) ayant un coût réduit, calculé à partir de la solution duale restreinte (e), négatif le plus petit lorsque l'optimisation est une minimisation, ou positif le plsu grand lorsque l'optimisation est une maximisation . 9. Procédé selon la revendication 7 ou 8, caractérisé en outre en ce que la recherche (118) des nouveaux vecteurs générateurs disjoints (x, , ) comprend : - déterminer (124) un ensemble de nouveaux vecteurs générateurs (Y ) ayant un coût réduit, calculé à partir de la solution duale restreinte (À--k ), négatif lorsque l'optimisation est une minimisation, ou positif lorsque l'optimisation est une maximisation ; - déterminer (126), comme nouveaux vecteurs générateurs disjoints, des vecteurs générateurs de l'ensemble de nouveaux vecteurs générateurs ayant des supports dans leur base canonique disjoints deux à deux et ayant les coûts réduits, calculés à partir de la solution duale restreinte (7rk ), les plus petits. 10. Procédé selon la revendication 9, caractérisé en outre en ce que la détermination (126) des vecteurs générateurs de l'ensemble de nouveaux vecteurs générateurs ayant des supports dans leur base canonique disjoints deux à deux et ayant les coût réduits négatifs les plus petits lorsque l'optimisation estune minimisation, ou positifs les plus grands lorsque l'optimisation est une maximisation, comprend : - sélectionner (128) le vecteur générateur de l'ensemble de nouveaux vecteurs générateurs (Y) ayant le coût réduit le plus petit ; - de manière itérative, sélectionner (130) le vecteur générateur de l'ensemble de nouveaux vecteurs générateurs (Y) ayant un support disjoint de chacun des nouveaux vecteurs générateurs déterminés auparavant et ayant le coût réduit le plus petit. 11. Procédé selon la revendication 9 ou 10, caractérisé en outre en ce que l'ensemble de nouveaux vecteurs générateurs (Y) comprend le vecteur générateur de l'ensemble du second jeu de contraintes (X) ayant le coût réduit le plus petit. 12. Procédé selon la revendication 7 ou 8, caractérisé en outre en ce que la recherche (118) des nouveaux vecteurs générateurs disjoints (z, , ) comprend : - déterminer (138), en tant qu'un des nouveaux vecteurs générateurs disjoints (x, ), le vecteur générateur de l'ensemble du second jeu de contraintes (X) ayant le coût réduit, calculé à partir de la solution duale restreinte (e), négatif le plus petit lorsque l'optimisation est une minimisation, ou positif le plus grand lorsque l'optimisation est une maximisation ; - de manière itérative, déterminer (140), en tant qu'un des nouveaux vecteurs générateurs disjoints (z, ), le nouveau vecteur générateur ayant un support disjoint de chacun des nouveaux vecteurs générateurs déterminés auparavant et ayant un coût réduit, calculé à partir de la solution duale restreinte (tek ), le plus petit. 13. Procédé selon l'une quelconque des revendications 1 à 12, caractérisé en outre en ce que les étapes : - rechercher (118) des nouveaux vecteurs générateurs disjoints (x, , x) ; - ajouter (132) des nouveaux vecteurs à ajouter à la partie de vecteurs générateurs (1xj}JE/A ) ; - déterminer (134) le nouveau vecteur solution restreint (.7k+1) ; sont itérées. 14. Procédé selon la revendication 13, caractérisé en outre en ce que les étapes : - rechercher (118) des nouveaux vecteurs générateurs disjoints (.x, , ) ; - ajouter (132) des nouveaux vecteurs à ajouter à la partie de vecteurs générateurs (~x1 } EJk ) J - déterminer (134) le nouveau vecteur solution restreint (zk+') ; sont itérées tant qu'il est possible de déterminer un vecteur générateur du sous-ensemble (Xk) ayant un coût réduit, calculé à partir de la solution duale restreinte (Tck ), négatif lorsque l'optimisation est une minimisation, ou positif lorsque l'optimisation est une maximisation. 15. Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce que les ressources réelles sont des ressources humaines ou bien des ressources matérielles et en ce que les tâches réelles sont des tournées de transport de voyageurs et/ou de marchandises. 16. Programme d'ordinateur comprenant des portions de codes qui, lorsqu'exécutées sur un ordinateur, entraînent la mise en oeuvre d'un procédé comprenant : - déterminer (115, 132) une partie de vecteurs générateurs (~xJ }J EJk , }xI je j,,, ) d'une famille de vecteurs générateurs (tx1 }JE,) générant un ensemble, dit ensemble du second jeu de contraintes (X ), regroupant les vecteurs de variables (x) qui respectent le second jeu de contraintes (Bx >_ b ), la partie de vecteurs générateurs (1x1 }JEJ, , ~xJ }jEjkä ) générant un sous-ensemble (Xk , Xk+') de l'ensemble du second jeu de contraintes (X) ; - déterminer (116, 134), dans le sous-ensemble (Xk un vecteur solution, dit vecteur solution restreint (zk xk+`) de l'optimisation (min C(x)) du vecteur de variables (x) sous respect du premier jeu de contraintes (Ax a) ; - rechercher (118) au moins deux nouveaux vecteurs générateurs de la famille de vecteurs générateurs (IxJ }JE/ ), dits nouveaux vecteurs générateurs disjoints (z,, ), situés hors de la partie de vecteurs générateurs (1x1 }JEJ, ) et ayant des supports dans leur base canonique disjoints deux à deux ;- ajouter (132), à la partie de vecteurs générateurs Ox, },EJk ), des nouveaux vecteurs générateurs de la famille de vecteurs générateurs (lx~ i ) dits nouveaux ,cJ vecteurs générateurs à ajouter, comprenant au moins les nouveaux vecteurs générateurs disjoints (:X,, 2, ), afin d'obtenir une partie augmentée de vecteurs générateurs (}x, } /k+I ) générant un nouveau sous-ensemble (Xk+,) ; - déterminer (134), dans le nouveau sous-ensemble (Xk+' ), un nouveau vecteur solution, dit nouveau vecteur solution restreint (.17' ), de l'optimisation (minC(x)) du vecteur de variables (x) sous respect du premier jeu de contraintes.