Vous savez ce que cela signifie d'optimiser un système pour obtenir le meilleur résultat possible si vous êtes un étudiant en génie ou un ingénieur.
L'optimisation d'une solution est la clé du succès dans tous les domaines, de la construction de ponts à la création de logiciels.
L'idée d'une solution réalisable de base entre en jeu à ce stade.
C'est une idée de base en programmation linéaire qui vous permet de déterminer laquelle d'un ensemble de solutions possibles est la meilleure.
Mais pourquoi est-ce si important ? Dans cet article, je parlerai des solutions réalisables de base et de la manière dont elles peuvent être utilisées pour résoudre des problèmes d'ingénierie dans le monde réel.
Je vais parler de la façon de les trouver, de quoi ils sont faits et pourquoi ils sont importants.
Alors, que vous soyez un ingénieur expérimenté ou un étudiant débutant, venez avec nous plonger dans le monde des solutions réalisables de base et vous montrer comment utiliser la puissance de la programmation linéaire.
Comprendre la solution réalisable de base
Définition formelle:
Une solution de base à un modèle de programme linéaire dans lequel toutes les variables sont non négatives.
Une solution réalisable de base (BFS) est une idée clé de la programmation linéaire qui aide à trouver les meilleures solutions.
Un BFS est une solution avec le plus petit nombre possible de variables non nulles.
C'est un coin du polyèdre des solutions réalisables.
En d'autres termes, un BFS est une solution de base qui satisfait les contraintes non négatives et se trouve dans la région réalisable ou la zone problématique.
Trouver une solution de base optimale et réalisable
Pour trouver le meilleur BFS, nous devons procéder comme suit :
- Ecrire le programme sous forme standard pour une séquence linéaire.
- Transformez le système d'inégalités en une matrice augmentée.
- Déterminez quelles variables sont fondamentales et lesquelles ne le sont pas.
- Déterminez quelles sont les variables de base par rapport aux autres variables.
- Mettez ces expressions dans la fonction objective pour obtenir une fonction des seules variables qui ne sont pas de base.
- Trouvez une variable non fondamentale qui peut être augmentée sans briser les contraintes et qui améliorera la fonction objectif.
Cette variable est maintenant une variable de base, et l'une des autres variables de base n'est plus une variable de base.
S'il existe une solution optimale, elle doit se trouver à l'une des extrémités, ou sommets, de la région où les solutions sont possibles.
Ainsi, si un LP a une solution optimale, il a une solution optimale à un point extrême de l'ensemble des possibles.
De plus, il existe toujours un BFS optimal s'il existe une solution optimale.
Utilisation de la méthode Simplex pour trouver un BFS optimal
La méthode Simplex est un algorithme de résolution de problèmes de programmation linéaire.
Il passe d'un BFS à un BFS "adjacent" en utilisant la procédure pivot.
Dans la procédure pivot, une variable non fondamentale est choisie pour devenir une variable de base, puis le BFS actuel est utilisé pour résoudre les nouvelles variables de base.
Lorsqu'aucune variable non fondamentale ne peut être modifiée pour améliorer la fonction objectif, l'algorithme est terminé.
Pourquoi les solutions réalisables de base sont cruciales pour résoudre des problèmes d'ingénierie complexes
Toujours difficile à comprendre ? Je change un peu le point de vue :
Qui a besoin de réponses simples et réalisables de toute façon ? Il suffit de tout jeter ensemble et d'espérer pour le mieux.
Après tout, qui a besoin d'optimisation quand le chaos est tellement plus amusant ? Bienvenue dans le monde des variables non négatives, où tout n'est qu'une suggestion et où l'échec est presque certain.
Ou est-ce?
Explorons pourquoi le concept apparemment basique de solutions réalisables de base est tout sauf basique et pourquoi elles pourraient bien être la clé pour résoudre même les problèmes d'ingénierie les plus complexes.
D'accord, c'était juste une blague faite pour ressembler à une publicité télévisée.
Revenons maintenant à l'explication.
Trouver une solution de base réalisable
Une solution réalisable de base (BFS) est une solution à un problème d'optimisation linéaire qui satisfait toutes les contraintes et a le moins de variables non nulles.
Chaque BFS est un coin du polyèdre des solutions réalisables d'un point de vue géométrique.
S'il existe une meilleure solution, il doit également y avoir une meilleure première étape.
Dans cet article, nous verrons comment trouver une solution faisable de base initiale, comment trouver toutes les solutions faisables de base et comment trouver une solution faisable de base sans variables d'écart.
Trouver une solution initiale de base réalisable
Nous pouvons utiliser différentes méthodes, selon la configuration du problème, pour trouver une solution de base initiale qui fonctionne pour un problème d'optimisation linéaire.
Une façon consiste à ajouter des variables d'écart aux contraintes sur les inégalités et à mettre toutes les autres variables à zéro.
Les variables d'écart deviennent les variables de base et les autres sont des variables non fondamentales.
La méthode Simplex à deux phases est une autre façon de résoudre le problème.
Cette méthode consiste à résoudre un problème de programmation linéaire supplémentaire pour trouver une solution de base initiale réalisable.
Une fois qu'une solution faisable de base initiale a été trouvée, la méthode du simplexe peut être utilisée pour passer d'une solution faisable de base à la suivante, puis à la meilleure solution.
Trouver toutes les solutions de base réalisables
Il peut y avoir plus d'une solution de base qui fonctionne pour un programme linéaire.
Nous pouvons modifier le système en ajoutant des variables d'écart, puis utiliser le nouveau système pour trouver toutes les solutions réalisables de base pour un programme linéaire.
Ensuite, ces solutions réalisables de base sont utilisées pour trouver les solutions réalisables de base pour le problème initial.
Trouver une solution de base réalisable sans variables d'écart
Nous devons utiliser des variables d'écart pour nous débarrasser des contraintes inférieures à afin de pouvoir trouver une solution de base qui fonctionne sans variables d'écart.
Une variable d'écart est simplement la différence entre le côté droit d'une contrainte et le côté gauche.
Par exemple, pour la première contrainte, nous définissons une variable d'écart x4 = 14 - 2x1 - x2 - x3. Au regard de cette nouvelle variable, la première contrainte équivaut simplement à x4 ≥ 0, qui est une contrainte de positivité pour x4.
Lorsque nous ajoutons ces variables d'écart, nous obtenons un programme linéaire identique à celui d'origine, sauf que toutes les contraintes sont soit des équations, soit des contraintes qui indiquent que quelque chose est positif.
L'ensemble des variables de base, qui ont des valeurs autres que zéro dans la solution de base, est appelé la base.
Les variables qui ont une valeur de zéro dans la solution de base ne sont pas des variables de base.
Pour trouver la meilleure solution, nous devons trouver un vecteur x qui respecte toutes les règles et obtient la valeur la plus grande ou la plus petite pour l'objectif.
Mais trouver la meilleure solution nécessite plus d'étapes que de simplement trouver une solution qui fonctionne et n'a pas de variables d'écart.
Il n'est pas toujours possible de trouver une solution de base sans variables d'écart, en particulier pour les problèmes avec moins de contraintes.
Pour trouver une solution faisable de base, vous devez utiliser la méthode du simplexe ou un autre algorithme de programmation linéaire pour rechercher une solution qui respecte toutes les contraintes et comporte le moins de variables non nulles.
Propriétés et importance de la solution réalisable de base
Propriétés de la solution réalisable de base
Une solution réalisable de base a au plus m variables qui ne sont pas nulles et au moins nm variables qui sont nulles, où n est le nombre de variables de décision et m est le nombre de contraintes.
Un BFS est un coin du polyèdre des solutions possibles, et chaque BFS a n contraintes actives qui sont linéairement indépendantes.
S'il existe une meilleure solution, il doit également y avoir une meilleure première étape.
La chose la plus importante à propos des solutions réalisables de base est qu'elles sont les extrémités de l'ensemble des solutions convexes pour un problème de programmation linéaire.
Pour trouver la meilleure réponse, l'algorithme du simplexe passe par une série de BFS.
L'algorithme Simplex recherche toutes les solutions de base possibles de manière organisée pour trouver la meilleure.
Importance de la solution réalisable de base
Trouver une solution de base possible est important car cela aide à trouver la meilleure réponse aux problèmes de programmation linéaire.
Il donne également aux algorithmes complexes un point de départ et peut être utilisé pour déterminer si un programme linéaire est possible ou non.
Pour trouver toutes les solutions réalisables de base pour un programme linéaire, vous pouvez modifier le système en ajoutant des variables d'écart, puis utiliser le système modifié pour trouver toutes les solutions réalisables de base.
Ensuite, ces solutions réalisables de base sont utilisées pour trouver les solutions réalisables de base pour le problème initial.
Vidéo : solutions réalisables 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: | BFS peut être utilisé pour répartir des ressources limitées entre plusieurs projets afin que le maximum puisse être fait avec le minimum. Cette méthode peut être utilisée dans de nombreux domaines différents, comme le transport, l'agriculture et la finance. |
| Optimisation du Réseau : | BFS peut être utilisé pour améliorer le fonctionnement des réseaux de communication, de transport et de logistique. BFS peut aider à trouver les meilleurs itinéraires pour les biens et services, à réduire le temps et l'argent consacrés au transport, et à accélérer et à effectuer des livraisons plus précises. |
| Planification de la production : | BFS peut être utilisé pour planifier la production afin que les ressources telles que la main-d'œuvre, les matières premières et l'équipement soient utilisées de la meilleure façon possible pour en tirer le meilleur parti. BFS peut aider à réduire les coûts de production, à réduire les déchets et à améliorer l'efficacité. |
| Planification financière: | Dans la planification financière, BFS peut être utilisé pour optimiser les portefeuilles d'investissement, réduire les risques et récupérer le plus d'argent. BFS peut vous aider à trouver le meilleur moyen de répartir les actifs, de réduire les coûts de transaction et de gagner plus d'argent. |
| Gestion de la chaîne d'approvisionnement : | BFS peut être utilisé pour améliorer le flux de biens et de services des fournisseurs aux clients dans le cadre de la gestion de la chaîne d'approvisionnement. BFS peut vous aider à déterminer la meilleure quantité de stock à conserver, à raccourcir les délais et à améliorer le service client. |
Conclusion
Alors que cet aperçu des solutions réalisables de base touche à sa fin, il est clair qu'elles constituent un outil important pour tout ingénieur ou étudiant en ingénierie.
Qu'il s'agisse de trouver la meilleure façon de construire un système complexe ou de tirer le meilleur parti des ressources disponibles, les solutions de base réalisables fournissent un cadre pour obtenir le meilleur résultat possible.
Mais en plus d'être utiles, ils montrent à quel point les mathématiques peuvent être élégantes et belles.
Il est étonnant que vous puissiez résumer des problèmes compliqués à un simple ensemble d'équations, puis utiliser ces équations pour résoudre des problèmes dans le monde réel.
C'est un bon rappel que l'ingénierie consiste à résoudre des problèmes et qu'en utilisant la puissance des mathématiques, nous pouvons trouver des réponses que l'on croyait autrefois impossibles.
Ainsi, à mesure que vous en apprendrez plus sur l'ingénierie, gardez à l'esprit ce que vous avez appris sur les solutions simples qui fonctionnent et utilisez-les pour rendre le monde meilleur et plus efficace.
Liens et références
Livres:
- Programmation linéaire : fondements et extensions
- Programmation linéaire : théorie et applications
Partager sur…
