Explique simplement la méthode simplex de la programmation linéaire

FONTE ZOOM:

Dans les optimisation linéaire traite de l'allocation optimale des ressources rares à différents usages. Avec des ressources limitées, il peut, par exemple, à la capacité de la machine ou les dimensions de marchandises. L'optimum est défini comme mathématique, souvent déterminée par la méthode simplex.

Modélisation des programmes linéaires

Dans la modélisation de programmes linéaires faut d'abord différents paramètres, tels. Comme les temps de traitement des pièces ou des capacités de la machine sont déterminés. Par la suite, une fonction objectif est définie qui doit être maximisé, sous réserve de certaines contraintes. Dans la fonction objectif est souvent la fonction de profit que la maximisation des bénéfices nets pour les entreprises est un objectif clé. Les contraintes sont décrits par la rareté des ressources. Ensuite, vous pouvez résoudre le problème en utilisant la méthode simplex.

  • Particulièrement facile à apprendre la procédure pour créer des modèles linéaires lorsque vous obtenez un exemple simple, supposons que vous avez trois machines M1, M2 et M3 sur lesquels les deux produits qui seront fabriqués P1 et P2. Les machines ont des capacités différentes, ainsi que le traitement d'un produit particulier à la machine prend différentes longueurs et a terminé la touche finale d'un autre des profits élevés.
  • WANTED est maintenant le bénéfice maximiser programme de production, de sorte que le programme de production, dans lequel le plus grand profit.

Exemple avec des valeurs numériques et Introduction à la méthode simplex

Dans l'étape suivante, vous devez valeurs numériques spécifiques pour la modélisation de votre problème. Supposons que vous engagez pour le traitement de P1 sur M1 2 heures à 3 heures, et M2 à M3 4 heures. Pour P2 chute sur M1 4 heures à 5 heures, et M2 à M3 3 heures. Les capacités de la machine sont pour M1 500 heures pour M2 et M3 300 heures 600 heures. Les bénéfices pour le fini des produits finis P1 soient € 3 / unité pour les produits finis de fabrication P2 4 € / pièce.

  1. Il est préférable de trouver une table avec trois lignes et trois colonnes, que vous devriez également laisser la place pour les rubriques de lignes ou colonnes. Dans le champ "la colonne 1 et de la ligne 1" est, par exemple, le temps de traitement de P1 à M1, dans le champ "la colonne 2 et de la ligne du temps 3 'de traitement de P2 à M3. Dans la colonne 3 sont les capacités de la machine des trois machines.
  2. Maintenant, vous avez deux variables x1, x2 définir qui correspondent aux quantités de P1 et P2 production.
  3. Ainsi, vous obtenez les contraintes 2x1 + 4x2≤ 500, 3x1 + 5x2 ≤ 300 et 4x1 + 3x2 ≤ 600e Il ya chaque inégalités que la capacité n'a pas besoin d'être pleinement exploitées.
  4. La fonction objectif à maximiser est G = 3x1 + 4x2 -> max.
  5. Se appliquent également lorsque les volumes de production, positivité de x1, x2≥ 0. Vous voyez, toutes les équations sont des équations linéaires. Considérez ceci ensemble, de sorte que vous avez un problème d'optimisation linéaire.

L'optimisation non-linéaire et l'application de la méthode simplex

L'idée de la solution d'un programme linéaire est que les inégalités sont transformées par l'introduction de «variables d'écart" dans les équations et le problème d'optimisation modifié est résolu que LGS. La méthode du simplex est donc l'algorithme de Gauss pour résoudre LGS très similaire.

  1. Par exemple, un aéronef doit être chargé par trois domaines G1, G2, G3 avec la plus grande valeur de charge totale possible. Ceux-ci ont un espace de 1, 0,2 ou 6 dm3, ont un poids de 1, 0, 4 et 8 kg et une valeur de 10, 3 et 50 euros. Comment est l'avion idéal chargé lorsque la soute est 2000dm3 et il peut transporter un maximum de 3000 kg cargaison?
  2. Ils définissent x1, x2, x3 en tant que quantités de marchandises G1, G2, G3.
  3. Maintenant, vous pouvez configurer les contraintes avec variables d'écart comme suit: x1 + 8x3 + 0,4x2 + x4 = 3000 et x1 + 6x3 + 0,2x2 + x5 = 2000. La fonction objectif est G = 10x1 + 3x2 + 50X3 -> max. Cet ensemble, ni, en apportant toutes les variables d'un côté.
  4. Réglez ensuite le tableau du simplexe. Il dispose de 3 lignes et 7 colonnes. Sur le côté gauche vous prenez dans les colonnes x1, x2, x3, x4, x5 et G de l'actualité. Sur le côté droit est b, la seule colonne. Ci-après sont les quantités optimales de biens et de la valeur totale maximale de charge. La troisième ligne est la ligne de but. ,
  5. Maintenant procéder comme dans l'application de la méthode de Gauss pour résoudre un LGS. En rangée opérations changent dans la première étape Ligne 1 ou Ligne 2 envoyé à ajouter ainsi et à une ligne différente, laissant seulement un 1 dans "Ligne 1 + 1 colonne" et un 0 à la «Ligne 2 + 1 colonne" se produit. Par conséquent, les valeurs de la ligne de visée changent automatiquement.
  6. Dans ce cas, vous pourriez multiplier exemple, la ligne 2 par -1 et d'ajouter à la ligne 1 et la ligne 2 Multiplier par 10 et ajouter ajouter à la ligne 3.
  7. Dans la deuxième étape, prendre la colonne de droite 2 et créé par transformation en "Ligne 2 + 2 colonne« a 0 et puis dans "la ligne 1 et la colonne 2« un 1. Ce est à son tour d'être observé comme un changement dans la ligne de cible.
  8. Les étapes de transformation seraient, par exemple, la ligne 1 multiplié par -1 et ajouter à la ligne 2 et multiplier la ligne 1 par 5 et ajouter à la ligne 3.
  9. Sur le côté droit du panneau que vous pouvez maintenant lire les solutions. Il en résulte un niveau de charge total de € 25 000, sera transporté 5 000 unités de bonnes 1, 1000 unités de bonne 2 et aucune unité de bonne. 3

Notez que dans la résolution du tableau du simplexe ne donne qu'une solution optimale si il n'y a que des nombres positifs dans la ligne de cible sur la gauche après la dernière étape de déformation. Le système que vous avez intériorisé après 2-3 d'autres exemples et peut résoudre ces tâches ludique à l'avenir.

VOIR AUSSI:
  1.  
  2.  
  3.  
Sans commentaires

Laisser un commentaire

Code De Sécurité