Si vous êtes ingénieur ou étudiant en ingénierie, vous savez peut-être ce que signifie optimiser.
Pour obtenir le meilleur résultat possible, il est important de trouver la meilleure façon de faire les choses.
En programmation linéaire, vous pouvez utiliser une solution de base pour trouver la meilleure solution.
Mais qu'est-ce qu'une solution de base et pourquoi est-il si important que les ingénieurs la connaissent ? Dans cet article, je parlerai de ce que sont les solutions de base, pourquoi elles sont importantes en ingénierie et comment elles peuvent être utilisées pour obtenir les meilleurs résultats dans différentes situations.
Alors attachez votre ceinture et préparez-vous à plonger dans le monde des solutions de base, où je vais percer les mystères et vous montrer à quel point cette technique peut être puissante.
Solutions de base en programmation linéaire
Définition formelle:
Une solution à un modèle de programme linéaire composé de m équations dans n variables est obtenue en résolvant m variables en fonction des variables restantes (nm) et en fixant les variables (nm) égales à zéro.
Une solution de base en programmation linéaire est un moyen de résoudre un problème de programmation linéaire qui répond à certaines exigences techniques.
En particulier, un vecteur x est une solution de base pour un polyèdre si les vecteurs {ai : xi = 0} sont linéairement indépendants.
Cela signifie que les colonnes de A qui ont des variables xi non nulles sont linéairement indépendantes.
Une solution de base avec des composants non négatifs est appelée une solution réalisable de base (BFS) (BFS).
Un BFS répond à toutes les règles qui définissent un polyèdre.
Chaque BFS est un coin du polyèdre des solutions réalisables d'un point de vue géométrique.
Pour trouver une solution de base, vous devez définir nm variables qui ne sont pas de base sur zéro et résoudre les m variables qui sont de base.
Il est possible que différentes bases conduisent à la même solution de base, ce qui signifie qu'il peut y avoir plus d'une façon de résoudre le même problème.
La méthode Simplex est un processus itératif qui passe d'un BFS au BFS suivant jusqu'à ce qu'il trouve le meilleur BFS.
Après avoir utilisé la méthode du simplexe pour trouver un BFS, nous pouvons dire si la solution est la meilleure en voyant si d'autres BFS à proximité donnent une meilleure valeur pour la fonction objectif.
S'il n'y a pas un tel BFS, alors le BFS actuel est le meilleur.
Modèle de programmation linéaire
Un modèle de programmation linéaire implique trois composants principaux : des variables de décision, une fonction objectif et des contraintes.
La fonction objectif et les contraintes doivent être des fonctions linéaires, et les variables de décision doivent être continues.
La fonction objectif est utilisée pour augmenter ou diminuer un nombre qui représente le profit, le coût, le nombre de produits fabriqués, etc.
Les contraintes sont des limites ou des restrictions sur la quantité totale d'une certaine ressource qui est nécessaire pour effectuer les tâches qui détermineront le niveau de réussite dans les variables de décision.
De plus, certains programmes linéaires exigent que toutes les variables de décision soient non négatives.
Dans les modèles de programmation linéaire, vous pouvez également utiliser des variables entières et binaires.
Les variables binaires ne peuvent avoir qu'une valeur de 0 ou 1, elles ne peuvent donc avoir qu'une valeur de 0 ou 1.
La méthode du simplexe
L'un des moyens les plus utilisés pour résoudre les problèmes de programmation linéaire est la méthode du simplexe.
Les solutions de base sont importantes dans la méthode du simplexe car elles correspondent aux points d'angle de la région réalisable, et la méthode du simplexe se déplace d'un coin à l'autre jusqu'à ce qu'une solution optimale soit trouvée.
La méthode du simplexe est un moyen rapide de trouver la meilleure réponse à un problème de programmation linéaire en utilisant les propriétés des solutions de base.
Pour utiliser la méthode du simplexe pour trouver le meilleur BFS, nous devons trouver une base B pour la matrice de contraintes A et résoudre le système Ax = b avec toutes les variables autres que la base fixée à zéro.
Les valeurs résultantes pour les variables de base forment un BFS.
S'il existe une solution optimale, alors il existe un BFS optimal.
La méthode Simplex se déplace d'un BFS à un BFS adjacent jusqu'à ce qu'il atteigne un BFS optimal en utilisant des procédures de pivot.
Comparaison entre les solutions de base et les solutions réalisables
La différence entre une solution de base et une solution réalisable est qu'une solution de base ne doit remplir aucune condition.
En particulier, il doit avoir des vecteurs linéairement indépendants et avoir des valeurs non nulles pour xi, et x doit être inférieur à 0.
D'autre part, une solution réalisable est tout point qui s'inscrit dans les limites du problème.
Mais toutes les solutions réalisables ne sont pas des solutions réalisables de base.
Les solutions réalisables de base (BFS) ne sont que celles qui correspondent aux coins du polyèdre des solutions réalisables.
Retour aux fondamentaux : Libérer la puissance des solutions de base en ingénierie
Toujours difficile à comprendre ? Je change un peu le point de vue :
Vous en avez marre d'utiliser des méthodes et des algorithmes compliqués pour résoudre des problèmes difficiles ? Souhaitez-vous qu'il y ait un moyen plus simple et plus direct de traiter vos problèmes de modèle de programme linéaire ?
Eh bien, ne vous inquiétez pas, car la réponse est ici : résolvez m variables en fonction des variables (nm) restantes et définissez les variables (nm) sur zéro.
Qui a besoin d'algorithmes qui semblent fantaisistes quand on peut revenir à l'essentiel ? Alors rangez vos calculatrices et commençons à apprendre des solutions simples.
D'accord, c'était juste une blague faite pour ressembler à une publicité télévisée.
Revenons maintenant à l'explication.
Programmation linéaire de la solution de base
Conseil : Activez le bouton de sous-titrage si vous en avez besoin. Choisissez "traduction automatique" dans le bouton des paramètres, si vous n'êtes pas familier avec la langue parlée. Vous devrez peut-être d'abord cliquer sur la langue de la vidéo avant que votre langue préférée ne soit disponible pour la traduction.
Cas d'utilisation
| Utilisé dans: | Description: |
|---|---|
| Allocation des ressources: | La solution de base peut être utilisée dans les problèmes d'allocation de ressources, où le but est de diviser des ressources limitées entre des besoins concurrents. Par exemple, une entreprise peut avoir besoin de répartir son budget entre différents départements ou projets. En utilisant des solutions de base, ils peuvent trouver la meilleure façon d'utiliser leurs ressources pour gagner le plus d'argent ou dépenser le moins possible. |
| Planification de la production : | Dans la planification de la production, la solution de base peut être utilisée pour déterminer la meilleure combinaison de produits à fabriquer afin de gagner le plus d'argent. Les entreprises peuvent trouver le meilleur mix de production qui rapporte le plus d'argent et coûte le moins en utilisant la solution de base. |
| Planification: | La solution de base peut être utilisée pour comprendre comment planifier des tâches ou des travaux afin qu'ils puissent être effectués de la manière la plus efficace. Par exemple, une entreprise peut avoir besoin de planifier les heures de travail de ses employés pour s'assurer qu'ils ont suffisamment de travailleurs lorsque les affaires sont occupées. En utilisant une solution de base, ils peuvent déterminer la meilleure façon de planifier les choses afin qu'il y ait le moins de temps d'arrêt possible et que le plus de travail possible soit effectué. |
| Gestion de la chaîne d'approvisionnement : | Dans la gestion de la chaîne d'approvisionnement, l'objectif est de s'assurer que les biens et services se déplacent aussi facilement que possible du fournisseur au client. Par exemple, une entreprise peut avoir besoin de déterminer les meilleurs itinéraires pour transporter des marchandises afin que les coûts soient réduits au minimum et que les marchandises soient livrées à temps. En utilisant des solutions de base, ils peuvent trouver le meilleur plan de gestion de la chaîne d'approvisionnement qui maintient les coûts bas et satisfait les clients. |
| Optimisation de portefeuille : | En optimisation de portefeuille, où l'objectif est de trouver la meilleure combinaison d'investissements pour gagner le plus d'argent tout en prenant le moins de risques, des solutions de base peuvent être utilisées. Par exemple, une entreprise d'investissement peut avoir besoin de trouver la meilleure combinaison d'actions, d'obligations et d'autres titres pour aider ses clients à atteindre leurs objectifs d'investissement. En utilisant une solution simple, ils peuvent trouver la meilleure façon de combiner leurs portefeuilles afin d'obtenir les meilleurs rendements tout en prenant le moins de risques. |
Conclusion
En conclusion, l'idée d'une solution de base est très importante dans le domaine de l'ingénierie et peut être utilisée de différentes manières.
En sachant ce qu'est une solution de base et ce qu'elle fait en programmation linéaire, nous pouvons améliorer les solutions, réduire les coûts et les rendre plus efficaces.
Mais il est important de se rappeler que la solution de base n'est pas une solution unique, même si c'est un outil puissant.
Pour obtenir les meilleurs résultats, chaque problème doit être soigneusement examiné et réfléchi.
En tant qu'ingénieurs, nous devons continuer à chercher comment des solutions de base et d'autres techniques d'optimisation peuvent nous aider à progresser et à proposer de nouvelles idées.
Alors, reconnaissons le pouvoir des solutions simples et continuons à repousser les limites de ce qui est possible en utilisant de nouvelles techniques et stratégies.
Liens et références
Livres:
- Programmation linéaire par Vasek Chvatal
- Modélisation et résolution de la programmation linéaire avec R par Jose M. Sallan
Partager sur…
