L'optimisation vous aide à trouver le meilleur résultat qui apporte des bénéfices, réduit les coûts ou définit un paramètre qui provoque des échecs de processus métier.
Ce processus est aussi appelé programmation mathématique. Il résout le problème de la détermination de la répartition des ressources limitées nécessaires pour atteindre l'objectif fixé par le responsable du problème d'optimisation. Parmi toutes les options possibles, il est souhaitable de trouver celle qui maximise (ou réduit) le paramètre de contrôle, par exemple, le profit ou le coût. Les modèles d'optimisation sont également appelés prescriptifs ou normatifs car ils cherchent à trouver une stratégie réalisable pour l'entreprise.
Histoire du développement
La programmation linéaire (LP) fonctionne avec une classe de problèmes d'optimisation où toutes les contraintes sont linéaires.
Présenter un bref historique du développement de LP:
- En 1762, Lagrange résout des problèmes d'optimisation simples avec des contraintes d'égalité.
- En 1820, Gauss décidesystème linéaire d'équations utilisant l'élimination.
- En 1866, Wilhelm Jordan a perfectionné la méthode consistant à trouver les erreurs des moindres carrés comme critère d'ajustement. Cela s'appelle maintenant la méthode de Gauss-Jordan.
- L'ordinateur numérique est apparu en 1945.
- Dantzig a inventé les méthodes du simplexe en 1947.
- En 1968, Fiacco et McCormick ont introduit la méthode Inside Point.
- En 1984, Karmarkar a appliqué la méthode intérieure pour résoudre des programmes linéaires, en y ajoutant son analyse innovante.
LP s'est avéré être un outil extrêmement puissant à la fois pour modéliser des problèmes du monde réel et en tant que théorie mathématique largement appliquée. Cependant, de nombreux problèmes d'optimisation intéressants ne sont pas linéaires.
Que faire dans ce cas ? L'étude de tels problèmes implique un mélange varié d'algèbre linéaire, de calcul multivarié, d'analyse numérique et de méthodes de calcul. Les scientifiques développent des algorithmes de calcul, notamment des méthodes de points intérieurs pour la programmation linéaire, la géométrie, l'analyse d'ensembles et de fonctions convexes et l'étude de problèmes spécialement structurés tels que la programmation quadratique.
L'optimisation non linéaire fournit une compréhension fondamentale de l'analyse mathématique et est largement utilisée dans divers domaines tels que l'ingénierie, l'analyse de régression, la gestion des ressources, l'exploration géophysique et l'économie.
Classification des problèmes d'optimisation
Une étape importante dansLe processus d'optimisation est la classification des modèles, puisque leurs algorithmes de résolution sont adaptés à un type particulier.
1. Problèmes d'optimisation discrète et continue. Certains modèles n'ont de sens que si les variables prennent des valeurs à partir d'un sous-ensemble discret d'entiers. D'autres contiennent des données qui peuvent prendre n'importe quelle valeur réelle. Ils sont généralement plus faciles à résoudre. Les améliorations apportées aux algorithmes, combinées aux progrès de la technologie informatique, ont considérablement augmenté la taille et la complexité d'un problème d'optimisation de programmation linéaire.
2. Optimisation illimitée et limitée. Une autre différence importante concerne les tâches où il n'y a pas de contrainte sur les variables. Cela peut aller de simples estimateurs à des systèmes d'égalités et d'inégalités qui modélisent des relations complexes entre des données. Ces problèmes d'optimisation peuvent être classés en fonction de la nature des fonctions (linéaire et non linéaire, convexe et lisse, différentiable et non différentiable).
3. Missions de faisabilité. Leur objectif est de trouver des valeurs de variables qui satisfont aux contraintes du modèle sans objectif d'optimisation spécifique.
4. Missions de complémentarité. Ils sont largement utilisés en technologie et en économie. Le but est de trouver une solution qui satisfasse les conditions de complémentarité. En pratique, les tâches à plusieurs objectifs sont souvent reformulées en tâches à objectif unique.
5. Optimisation déterministe versus stochastique. L'optimisation déterministe suppose que les données pourles devoirs sont tout à fait exacts. Cependant, sur de nombreuses questions d'actualité, ils ne peuvent pas être connus pour un certain nombre de raisons.
Le premier concerne une simple erreur de mesure. La deuxième raison est plus fondamentale. Cela réside dans le fait que certaines données représentent des informations sur l'avenir, par exemple, la demande d'un produit ou le prix pour une période future. Lors de l'optimisation dans des conditions d'optimisation stochastique, l'incertitude est incluse dans le modèle.
Composants principaux
La fonction objectif est celle qui doit être minimisée ou maximisée. La plupart des types de problèmes d'optimisation ont une fonction objectif. Sinon, ils peuvent souvent être reformulés pour fonctionner.
Deux exceptions à cette règle:
1. Tâche de recherche cible. Dans la plupart des applications métier, le responsable souhaite atteindre un objectif précis tout en respectant les contraintes du modèle. L'utilisateur ne souhaite pas particulièrement optimiser quelque chose, cela n'a donc aucun sens de définir une fonction objectif. Ce type est communément appelé problème de satisfaisabilité.
2. Beaucoup de fonctionnalités objectives. Souvent, un utilisateur souhaite optimiser plusieurs objectifs différents à la fois. Ils sont généralement incompatibles. Les variables qui optimisent un objectif peuvent ne pas être les meilleures pour d'autres.
Types de composants:
- Une entrée contrôlée est un ensemble de variables de décision qui affectent la valeur d'une fonction objectif. Dans une tâche de production, les variables peuvent inclure la répartition des différentes ressources disponibles ou le travail nécessaire pourchaque action.
- Les contraintes sont des relations entre les variables de décision et les paramètres. Pour un problème de production, cela n'a pas de sens de passer beaucoup de temps sur une activité, alors limitez toutes les variables "temporaires".
- Solutions possibles et optimales. La valeur de la décision pour les variables, sous laquelle toutes les contraintes sont satisfaites, est dite satisfaisable. La plupart des algorithmes le trouvent d'abord, puis essaient de l'améliorer. Enfin, ils changent de variables pour passer d'une solution réalisable à une autre. Ce processus est répété jusqu'à ce que la fonction objectif atteigne son maximum ou son minimum. Ce résultat est appelé la solution optimale.
Les algorithmes de problèmes d'optimisation développés pour les programmes mathématiques suivants sont largement utilisés:
- Convexe.
- Séparable.
- Quadratique.
- Géométrique.
Solutions linéaires Google
L'optimisation ou la programmation linéaire est le nom donné au processus informatique de résolution optimale d'un problème. Il est modélisé comme un ensemble de relations linéaires qui surviennent dans de nombreuses disciplines scientifiques et d'ingénierie.
Google propose trois façons de résoudre les problèmes d'optimisation linéaire:
- Bibliothèque open source Glop.
- Module complémentaire d'optimisation linéaire pour Google Sheets.
- Service d'optimisation linéaire dans Google Apps Script.
Glop est intégré à Googlesolveur linéaire. Il est disponible en open source. Vous pouvez accéder à Glop via le wrapper de solveur linéaire OR-Tools, qui est un wrapper pour Glop.
Le module d'optimisation linéaire pour Google Sheets vous permet d'effectuer une déclaration linéaire du problème d'optimisation en saisissant des données dans une feuille de calcul.
Programmation quadratique
La plate-forme Premium Solver utilise une version étendue LP/Quadratic de la méthode Simplex avec des limites de traitement des problèmes LP et QP allant jusqu'à 2000 variables de décision.
SQP Solver pour les problèmes à grande échelle utilise une implémentation moderne de la méthode des ensembles actifs avec parcimonie pour résoudre les problèmes de programmation quadratique (QP). Le moteur XPRESS Solver utilise une extension naturelle de la méthode "Interior Point" ou Newton Barrier pour résoudre les problèmes QP.
MOSEK Solver applique les méthodes intégrées "Inside Point" et auto-dual. Ceci est particulièrement efficace pour les problèmes QP faiblement couplés. Il peut également résoudre les problèmes de contrainte quadratique d'échelle (QCP) et de programmation du cône du second ordre (SOCP).
Calculs multi-opérations
Ils sont utilisés avec succès avec l'utilisation des fonctionnalités de Microsoft Office, par exemple, en résolvant des problèmes d'optimisation dans Excel.
Dans le tableau ci-dessus, les symboles sont:
- K1 - K6 - clients qui doivent fournir des marchandises.
- S1 - S6 sont des sites de production potentiels qui pourraient être construits pour cela. Peut être créé1, 2, 3, 4, 5 ou les 6 emplacements.
Il y a des coûts fixes pour chaque installation listée dans la colonne I (Fix).
Si l'emplacement ne change rien, il ne comptera pas. Ensuite, il n'y aura pas de frais fixes.
Identifiez les emplacements potentiels pour obtenir le coût le plus bas.
Dans ces conditions, la localisation est établie ou non. Ces deux états sont: "TRUE - FALSE" ou "1 - 0". Il y a six états pour six emplacements, par exemple, 000001 est défini uniquement sur le sixième, 111111 est défini sur tous.
Dans le système de numération binaire, il y a exactement 63 options différentes de 000001 (1) à 111111 (63).
L2-L64 devrait maintenant se lire {=OPÉRATION MULTIPLE (K1)}, ce sont les résultats de toutes les solutions alternatives. Alors la valeur minimale est=Min (L) et l' alternative correspondante est INDEX (K).
CPLEX Programmation d'entiers
Parfois, une relation linéaire ne suffit pas pour aller au cœur d'un problème commercial. Cela est particulièrement vrai lorsque les décisions impliquent des choix discrets, comme l'ouverture ou non d'un entrepôt à un certain endroit. Dans ces situations, la programmation en nombres entiers doit être utilisée.
Si le problème implique à la fois des choix discrets et continus, c'est un programme mixte en nombres entiers. Il peut avoir des problèmes quadratiques linéaires et convexes et les mêmes contraintes de second ordre.
Les programmes entiers sont beaucoup plus complexes que les programmes linéaires, mais ils ont des applications commerciales importantes. LogicielLe logiciel CPLEX utilise des méthodes mathématiques complexes pour résoudre des problèmes de nombres entiers. Ses méthodes impliquent la recherche systématique de combinaisons possibles de variables discrètes à l'aide de relaxations logicielles linéaires ou quadratiques pour calculer des bornes sur la valeur de la solution optimale.
Ils utilisent également LP et d'autres méthodes de résolution de problèmes d'optimisation pour calculer les contraintes.
Solveur Microsoft Excel standard
Cette technologie utilise l'implémentation de base de la méthode Simplex principale pour résoudre les problèmes LP. Il est limité à 200 variables. "Premium Solver" utilise une méthode simplex primaire améliorée avec des bornes double face pour les variables. La plate-forme Premium Solver utilise une version étendue du LP/Quadratic Simplex Solver pour résoudre un problème d'optimisation avec jusqu'à 2000 variables de décision.
La LP à grande échelle pour la plate-forme Premium Solver applique une implémentation de pointe de la méthode simple et double simplexe, qui utilise la parcimonie dans le modèle LP pour gagner du temps et de la mémoire, des stratégies avancées pour la mise à jour et matrices de refactorisation, tarification et rotations multiples et partielles, et pour surmonter la dégénérescence. Ce moteur est disponible en trois versions (capable de gérer jusqu'à 8 000, 32 000 ou un nombre illimité de variables et de limites).
MOSEK Solver inclut le simplexe primaire et double, une méthode qui exploite également la parcimonie et utilise des stratégies avancées pour la mise à jour des matrices et la "refactorisation". Il résout des problèmes de taille illimitée, a ététesté sur des problèmes de programmation linéaire avec des millions de variables de décision.
Exemple étape par étape dans EXCEL
Pour définir le modèle de problème d'optimisation dans Excel, procédez comme suit:
- Organisez les données du problème dans une feuille de calcul sous une forme logique.
- Sélectionnez une cellule pour stocker chaque variable.
- Créer dans la cellule une formule pour calculer le modèle mathématique cible du problème d'optimisation.
- Créer des formules pour calculer le côté gauche de chaque contrainte.
- Utilisez des boîtes de dialogue dans Excel pour indiquer au Solveur les variables de décision, les cibles, les contraintes et les limites souhaitées sur ces paramètres.
- Lancez "Solver" pour trouver la solution optimale.
- Créer une feuille Excel.
- Organisez les données du problème dans Excel où la formule de la fonction objectif et de la contrainte est calculée.
Dans le tableau ci-dessus, les cellules B4, C4, D4 et E4 ont été réservées pour représenter les variables de décision X 1, X 2, X 3 et X 4. Exemples de décision:
- Le modèle de gamme de produits (bénéfice de 450 $, 1 150 $, 800 $ et 400 $ par produit) a été saisi dans les cellules B5, C5, D5 et E5, respectivement. Cela permet de calculer la cible en F5=B5B4 + C5C4 + D5D4 + E5E4 ou F5:=SOMMEPROD (B5: E5, B4: E4).
- En B8, entrez la quantité de ressources nécessaires pour fabriquer chaque type de produit.
- Formule pour F8:=SUMPRODUCT(B8:E8, $B$4:$E$4).
- Copier ceciformule en F9. Les signes dollar dans $B$4:$E$4 indiquent que cette plage de cellules reste constante.
- Dans G8, entrez la quantité disponible de ressources de chaque type, correspondant aux valeurs des restrictions à droite. Cela vous permet de les exprimer comme ceci: F11<=G8: G11.
- Cela équivaut à quatre limites F8<=G8, F9 <=G9, F10 <=G10 et F11=0
Champs d'application pratique de la méthode
L'optimisation linéaire a de nombreuses applications pratiques comme exemple de problème d'optimisation:
Une entreprise peut fabriquer plusieurs produits avec une marge de contribution connue. La production d'une unité de chaque article nécessite une quantité connue de ressources limitées. La tâche consiste à créer un programme de production pour déterminer quelle quantité de chaque produit doit être produite afin que le profit de l'entreprise soit maximisé sans violer les contraintes de ressources.
Les problèmes de mélange sont la solution aux problèmes d'optimisation liés à la combinaison d'ingrédients dans le produit final. Un exemple en est le problème de l'alimentation étudié par George Danzig en 1947. Un certain nombre de matières premières sont indiquées, comme l'avoine, le porc et l'huile de tournesol, ainsi que leur contenu nutritionnel, comme les protéines, les matières grasses, la vitamine A, et leur prix au kilogramme. L'enjeu est de mixer un ou plusieurs produits finis à partir de matières premières au moindre coût tout en respectant les limites minimales et maximales de leur valeur nutritionnelle.
Une application classique d'un problème d'optimisation linéaire consiste à déterminer le routage pour les besoinsle trafic dans les réseaux de télécommunications ou de transport. Dans le même temps, les flux doivent être acheminés via le réseau de manière à ce que toutes les exigences de trafic soient satisfaites sans violer les conditions de bande passante.
En théorie mathématique, l'optimisation linéaire peut être utilisée pour calculer des stratégies optimales dans des jeux à somme nulle pour deux personnes. Dans ce cas, la distribution de probabilité pour chaque participant est calculée, qui est le coefficient de mélange aléatoire de ses stratégies.
Aucun processus commercial réussi dans le monde n'est possible sans optimisation. De nombreux algorithmes d'optimisation sont disponibles. Certaines méthodes ne conviennent que pour certains types de problèmes. Il est important de pouvoir reconnaître leurs caractéristiques et de sélectionner la méthode de résolution appropriée.
