: straight_ruler: Introduction

C'est le premier matériel d'étude pour apprendre l'optimisation mathématique pour la première fois. À partir de maintenant, apprenons l'optimisation mathématique à chaque session.

** Optimisation mathématique **

On dirait qu'il est difficile de l'entendre pour la première fois, mais ce n'est pas suffisant pour le tenir. "Eh bien, cette façon de penser, résolvez-le comme ça ~" Apprenons-le. Si vous apprenez de nouvelles connaissances en tant qu'ingénieur, vous pouvez les appliquer dans d'autres domaines et il doit y avoir du mérite. Au fait, si ça devient un boulot avec ça, je me demande si ça va être une bouchée!?

: straight_ruler: Matériel pédagogique

Dans cet article, nous allons procéder en regardant les exercices du texte de référence «Série de résolution de problèmes avec Python: Comment créer un modèle d'optimisation à l'aide d'une bibliothèque d'analyse de données» pour les modèles d'optimisation mathématique. Les détails du texte sont ci-dessous.

■ Texte de référence "Série de résolution de problèmes par Python: Comment créer un modèle d'optimisation à l'aide d'une bibliothèque d'analyse de données" Tsutomu Saito [Auteur] / Modern Science Company [Édition]

: straight_ruler: Qu'est-ce que l'optimisation mathématique?

Je citerai le texte de référence. L'optimisation est un moyen de résoudre les problèmes suivants.

: one: Je veux connaître l'itinéraire le plus court pour me rendre au bureau depuis la gare la plus proche de chez moi. : two: Je veux maximiser la valeur totale des produits que je mets dans mon sac à dos. : trois: Je veux minimiser le coût du transport des matières premières de l'entrepôt à l'usine.

De plus, il existe les différences suivantes entre l'optimisation et l'apprentissage automatique.

** Apprentissage automatique ** Connaître l'avenir en pointant vers le passé optimisation Déterminez l'avenir en pointant vers le modèle

Qu'est-ce qu'un modèle? Après cela, j'expliquerai le modèle.

: straight_ruler: modèle optimisé

Un modèle est une forme dans laquelle un problème réel peut être remplacé par une formule mathématique pour calculer une sorte de solution. Lorsque vous recherchez l'itinéraire le plus court, envisagez une formule mathématique qui exprime l'itinéraire de recherche et utilisez-la comme modèle. De plus, le problème du rembourrage du sac à dos est calqué sur une formule mathématique qui exprime l'état du rembourrage.

Après avoir construit le modèle, la tâche suivante consiste à obtenir la réponse à l'aide du logiciel de l'ordinateur appelé solveur.

Il existe des solveurs payants et gratuits. Ici, nous utilisons le gratuit ** CBC ** (Coin Or branch and Cut) comme solveur. Nous utilisons également ** OR-Tools ** fourni par Google, qui est une bibliothèque dédiée à la résolution de l'optimisation des combinaisons.

Cet OR-Tools est écrit en Python. Veuillez vous référer à ce qui suit pour OR-Tools.

■ L'outil gratuit de Google "OR-Tools" https://developers.google.com/optimization

: straight_ruler: composants du modèle et contraintes

Il existe trois composants pour créer un modèle:

① ** Variable ** Un conteneur numérique qui peut prendre différentes valeurs sur le modèle. Objet auquel la formule est appliquée. ② ** Fonction objectif ** Un index pour trouver une bonne solution. La solution est obtenue en l'exprimant comme une fonction à l'aide d'une formule mathématique utilisant des variables et en calculant de sorte que la fonction soit le maximum ou le minimum. ③ ** Contraintes ** Conditions à observer sous forme de combinaison de variables et de formules.

Les contraintes sont écrites de l'une des manières suivantes. Vous pouvez spécifier plusieurs conditions, mais toutes doivent être respectées. Formule ≧ Formule Formule = Formule Formule ≤ Formule

Ici, ≠ <> ne peut pas être utilisé.

Le modèle est appelé un modèle mathématique car il est exprimé à l'aide de formules mathématiques. De plus, on dit de formuler l'expression d'un modèle en utilisant strictement uniquement des formules mathématiques.

: straight_ruler: Type d'optimisation

Il existe trois types de problèmes d'optimisation:

: one: Problème d'optimisation linéaire 　(LP：Linear programming Problem) Seules des variables continues peuvent être utilisées. La fonction et les contraintes objectives doivent être des expressions linéaires. Le problème est facile à résoudre. Même les problèmes avec des milliers de contraintes ont été résolus. : deux: problème d'optimisation d'entiers mixtes 　(MIP：Mixed Integer programming Problem) Des variables continues et discrètes peuvent être utilisées. La fonction et les contraintes objectives doivent être des expressions linéaires. Fondamentalement, ce n'est pas facile à résoudre. Il est facile de résoudre si le nombre de variables et de contraintes est petit. : trois: Problème d'optimisation général Il n'y a pas de restrictions sur les variables, les fonctions objectives ou les contraintes. Dans la recherche, il est traité comme une classification appelée problème de programmation non linéaire (PNL). Il peut être résolu dans certains cas, mais c'est fondamentalement difficile.

Une variable continue est une variable qui prend une valeur réelle. Les variables discrètes, en revanche, sont des variables qui ne peuvent prendre que des valeurs discrètes, telles que des entiers.

: straight_ruler: à la fin

La prochaine fois, je parlerai du deuxième problème typique. J'espère que vous pourrez le lire.

Pour cet article, l'auteur est également un débutant en optimisation. Je pense qu'il y a des malentendus et des erreurs d'impression partout, alors n'hésitez pas à nous envoyer vos opinions et suggestions.

[PYTHON] [Partie 1] Qu'est-ce que l'optimisation? - Matériel d'étude pour l'apprentissage de l'optimisation mathématique