PHPSimplex

Optimiser les ressources avec Optimisation Linéaire



Histoire de la Recherche Opérationnelle

Au fil de l'histoire la collaboration entre les scientifiques et les militaires est fréquent à fin de prendre les meilleures décisions dans les batailles et d'essayer acquérir la victoire. Ce pour cela que beaucoup d'experts dans le domaine considèrent le début de la Recherche Opérationnelle dans le IIIe siècle av. J.-C, pendant les Guerres puniques, avec l'analyse et la solution qu'Archimède a proposé pour la défense de la ville de Syracuse, assiégée par les romains. Entre ses inventions on trouve la catapulte et un système de miroirs qui enflammait les embarcations ennemies en faisant usage des rayons de soleil.

En 1503, Léonard de Vinci a participé comme ingénieur dans la guerre contre Pise puisqu'il connaissait les techniques pour bombarder, construire des bateaux, des véhicules cuirassé, des canons, des catapultes et d'autres machines de guerre.

Croquis des inventions de Léonard de Vinci

Un autre précédent c'est l'usage de la Recherche Opérationnelle pendant la Première Guerre mondiale en Angleterre, grâce à l'étude mathématique de Frederick William Lanchester sur la puissance balistique des forces opposantes. En plus, il a développé, à partir d'un système d'équations différentielles, la Loi quadratique de Lanchester, avec laquelle c'était possible de déterminer le dénouement d'une bataille militaire en fonction de la force numérique relative et la capacité relative de feu des combattants.

Thomas Alva Edison a aussi employé la Recherche Opérationnelle pour contribuer dans la lutte anti-sous-marine, en développant des techniques afin que les vaisseaux puissent éviter et détruire les sous-marins ennemis avec une protection anti-torpille.

Du point de vue mathématique, dans les XVIIe et XVIIIe siècles, Newton, Leibnitz, Bernoulli et Lagrange, ont travaillé pour obtenir le maximum et le minimum conditionnés de certaines fonctions. Le mathématicien français Jean Baptiste-Joseph Fourier a ébauché les méthodes de l'actuelle optimisation linéaire. Dans les dernières années du XVIIIe siècle, Gaspar Monge a établi les précédents de la méthode graphique grâce au développement de la Géométrie Descriptive.

A la fin du XIXe siècle, Frederik Winslow Taylor a réalisé une étude qui a permis maximiser le rendement des mineurs, dans laquelle la seule variable significative c'était le poids combiné de la pelle et sa charge. De cette manière, on a créé des pelles par rapport aux différents types de matérielles qu'on allait utiliser avec.

Janos Von Neumann a publié en 1928 la "Théorie des jeux", qui a fournie des fondements mathématiques à l'optimisation linéaire. Ultérieurement, en 1947, il a aperçu la similitude entre les problèmes de l'optimisation linéaire et la théorie des matrices qu'il avait développés.

En 1939, le mathématicien Russe Leonid Vitálievich Kantoróvich et le Hollandais Tjalling Charles Koopmans ont créé la théorie mathématicienne nommée "Optimisation Linéaire", ce pour cela qu'ils ont reçu le prix Nobel d'économie.

En 1945, George Joseph Stigler a posé le problème du régime (ou problème de la diète), à la suite du souci de l'armée américaine pour assurer les requêtes nourrissantes essentielles pour ses troupes au moindre cout possible. Il s'agissait de déterminer la quantité entre 77 aliments diverses qu'un homme de taille moyenne, d'environ 70Kg, devrait ingérer par jour, de sorte que les besoins minimaux de nutriments soient pareilles aux conseillés par le Conseil National de Recherche Nord-Américain. Le problème a été résolu manuellement utilisant une méthode heuristique qui examinait 510 possibilités différentes de combinaison d'aliments, et dont la solution ne différait que quelques centimes de la solution fournie plus tard par la méthode du Simplexe.

Pendant les années 1941 et 1942, Kantorovich et Koopmans ont analysé de manière indépendante le problème du transport pour la première fois. Ce type de problèmes étaient connus comme le problème de Koopmans-Kantorovich. Pour la solution, ils ont employé des méthodes géométriques liés avec le théorème de Minkowski.

On croit que Charles Babbage est le père de la Recherche Opérationnelle en raison de ses recherches sur les coûts du transport et de tri du courrier réalisé pour la Uniform Penny Post en Angleterre en 1840.

Néanmoins, la Recherche Opérationnelle n'était pas considérée comme une science que jusqu'à la Seconde Guerre mondiale, pendant la bataille d'Angleterre. La Luftwaffe, armée de l'air allemande, soumettait ce pays à une forte poursuite dû à la réduite capacité aérienne britannique à cause de la politique de désarmement, bien qu'expérimentée dans le combat. Le gouvernement britannique, à fin de trouver une méthode pour défendre son pays, a convoqué des scientifiques de diverses disciplines pour résoudre le problème et profiter aux radars d'invention récents qu'ils disposaient. Grâce à son travail de localisation optimal des antennes et à l'amélioration de la distribution des signaux, ils ont doublé l'effectivité du système de défense aérienne et ils ont évité que l'île tombe entre les mains de l'Allemagne nazi.

Aussi en 1942, l'U-Bootswaffe allemande avec sa flotte de sous-marins U-Boot initia un blocus contre la Grande Bretagne en attaquant des convois de bateaux transportant d'approvisionnement des Etats-Unis et en empêchant leur destination. Le groupe de Recherche d'opérations de Lutte anti-sous-marine des Etats-Unis (ASWORG, Anti-Submarine Warfare Operations Research Group, en anglais) effectua des représentations mathématiques de ces convois, compte tenu une série de contraintes et de conditions imposées pour la réalité, comme la vitesse maximale de déplacement des navires, la quantité d'approvisionnement qu'ils doivent transporter et le combustible nécessaire pour y arriver. Ils misent aussi en place ces modèles sur les U-Boots: la taille de sa flotte, la portée des sous-marins, ses torpilles, etc. Sur la base de cette information ils furent capables de modeler la guerre navale, et de déterminer s'il était mieux de convois composés d'un grand groupe de navires pour le transport escortés par beaucoup de destroyers, ou bien, une stratégie des groupes plus petits et difficiles de localiser par l'ennemi, et même la manière de causer plus de dommage aux sous-marins U-Boot. Quand la marine américaine mit en pratique cette stratégie, la quantité des bateaux coulés diminua alors que la destruction des sous-marins allemands augmenta (passant de trente à 250 par an en 1943 et 1944).

Convoi de ravitaillement à destination de la Grande-Bretagne

Après remarquer la portée de cette nouvelle discipline, l'Angleterre a créé d'autres groupes de la même nature pour obtenir des résultats optimaux dans les conflits. De la même façon, les Etats-Unis en se joignant à la Guerre en 1942, ont commencé à appliquer militairement des techniques de recherche opérationnelle, et quelques années plus tard, en 1947, ont formé un groupe de travail dédié à améliorer les procès de planification à grande échelle: le projet SCOOP (Scientific Computation Of Optimum Programs). Dans ce groupe, on trouvait à George Bernard Dantzig, qui a développé en 1947 l'algorithme de la méthode du Simplexe.

Durant la Guerre froide, l'ancienne Union soviétique (URSS), refusant le plan Marshall, a voulu contrôler les communications terrestres, aussi comme les routes fluviales, de Berlin. Afin d'éviter la reddition de la ville, et sa soumission pour faire partie de la zone communiste allemande, l'Angleterre et les Etats-Unis ont décidé d'approvisionner la ville, bien grâce à convois escorté (ce que peut aboutir à nouveaux affrontements), bien avec un pont aérien, en rompant ou en évitant, en tout cas, le blocus de Berlin. Ils ont opté pour la deuxième option, en ouvrant le Luftbrücke (pont aérienne) le 25 Juin de 1948. Le groupe SCOOP avait aussi participé dans ce problème, en Décembre de cette année on avait réussi d'approvisionner 4500 tonnes par jour, et après l'investigation de la Recherche Opérationnelle on a optimisé l'approvisionnement jusqu'aux 8000 ou 9000 tonnes par jour en Mars 1949. C'était le même chiffre que si on aurait transporté par terre, ce pour cela que les soviétiques ont levé le blocus le 12 mai 1949.

Après la Seconde Guerre mondiale, on a déterminé d'organiser les ressources des Etats-Unis (énergie, armement, et tous types de distribution) grâce aux exemples d'optimisation, résolus par l'Optimisation linéaire.

Au même temps que la doctrine de la Recherche Opérationnelle, on a développé aussi les techniques de computation, lesquelles ont fortement réduit le temps de résolution sur les problèmes.

Le premier résultat a été obtenu en 1952, avec un ordinateur SEAC du National Bureau of Standars pour obtenir la solution d'un problème. Le succès dans le temps de résolution a été tellement encourageant qu'elle a été immédiatement utilisée pour tous les types de problèmes militaires, telle que la gestion des fonds monétaires pour la logistique et l'armement, déterminer la hauteur optimal dans laquelle les avions devraient voler pour localiser les sous-marins ennemis, et même, la profondeur dans laquelle on devait envoyer les charges pour atteindre les sous-marins ennemis à l'effet de produire le maximum de pertes. Tout cela se traduise par une augmentation cinq fois plus dans la efficience de la force aérienne.

Pendant les années 50 et 60, l'intérêt et le développement de la Recherche Opérationnelle a agrandi dans la suite de l'application sur le commerce et l'industrie. Un exemple c'est le problème de calcul du projet optimal de transport de sable de la construction aux travaux d'édification à Moscou, où il y avait 10 points d'origine et 230 de destination. Pour la résolution ils ont fait usage d'un ordinateur Strena dans le mois de juin de 1958, et après 10 jours de travail, il a fourni une réduction du 11% de coûts par rapport aux coûts originaux prévus.

Auparavant on avait déjà posé ces problèmes dans une discipline connu comme Analyse d'Entreprise, qui n'avaient pas des méthodes si effectifs que celles de la Seconde Guerre mondiale (par exemple la méthode du Simplexe). Les applications pas de guerre de la Recherche Opérationnelle s'étendent par tous les cadres, avec des problèmes de l'alimentation, élevage, distribution de culture dans l'agriculture, transport de marchandise, localisation, distribution du personnelle, problèmes de réseaux, de files d'attente, de graphes, etc.

A titre d'exemple on peut observer les suivants cas réels de l'usage de la Recherche Opérationnelle et le bénéfice rapporté.

Copyright ©2006-2016 PHPSimplex. Tous droits réservés.
Suivez-nous sur Twitter
X

PHPSimplex
Version 0.81

Copyright ©2006-2016. Tous droits réservés.

Développé par:
Daniel Izquierdo Granja
Juan José Ruiz Ruiz

Traduction en langue anglais par:
Luciano Miguel Tobaria

Traduction en langue française par:
Ester Rute Ruiz