3 outils importants de recherche opérationnelle
Cet article met en lumière les trois outils importants de la recherche opérationnelle. Les outils sont les suivants: 1. Programmation linéaire 2. Problèmes de transport 3. Problème d’affectation.
Recherche opérationnelle: Outil n ° 1. Programmation linéaire:
La programmation linéaire est une technique mathématique qui s'applique à presque toutes les catégories de problèmes de décision. Cette technique est appliquée pour choisir la meilleure alternative parmi un ensemble d’alternatives réalisables.
Dans LPP, la fonction objectif ainsi que les contraintes peuvent être exprimées sous forme de fonction mathématique linéaire, qui peut être utilisée pour résoudre les problèmes pratiques de planification. C'est une méthode utilisée pour étudier le comportement des systèmes.
LP s’occupe principalement de décrire l’interrelation des composants d’un système. Cette technique est conçue pour aider les gestionnaires à planifier, à prendre des décisions et à allouer les ressources. La direction a toujours tendance à tirer le meilleur parti des ressources d’une organisation. Les ressources comprennent les matières premières des machines, la main d’œuvre, l’entrepôt, le temps et l’argent.
Ces ressources peuvent être utilisées pour produire des produits de types variés: machines, pièces / composants, meubles, produits alimentaires, etc. De la même manière, des ressources peuvent être utilisées pour fournir des services tels que des calendriers d'expédition, des politiques de publicité et des décisions d'investissement.
Toutes les organisations doivent prendre une décision concernant l'affectation de leurs ressources limitées. Les directions sont donc tenues d'affecter en permanence des ressources rares pour atteindre les objectifs / buts / objectifs de l'organisation.
L'adjectif linéaire a été utilisé pour décrire une relation entre deux variables ou plus. La programmation concerne l'utilisation de certaines équations mathématiques utilisées pour obtenir la meilleure solution possible à un problème impliquant des ressources limitées / rares.
Ainsi, la programmation linéaire est utilisée pour les problèmes d'optimisation qui satisfont à la condition suivante:
(i) La fonction objectif à optimiser doit être bien définie et exprimée sous forme de fonction linéaire de variables.
(ii) Les limitations éventuelles concernant la réalisation de ces objectifs sont également exprimées en qualités linéaires / inégalités de variable.
(iii) Quelques actions alternatives sont également disponibles.
(iv) Les variables de décision sont interdépendantes et non négatives.
(v) Les ressources sont limitées.
Application de la programmation linéaire aux problèmes industriels:
(i) Établir des calendriers pour les industries de transformation des aliments et pour les raffineries de pétrole, etc.
(ii) Dans les industries du travail des métaux, il est utilisé pour le chargement en atelier et pour déterminer le choix entre l’achat et la production de diverses pièces.
(iii) Il est utilisé pour évaluer divers minerais de fer dans les industries du fer et de l'acier.
(iv) Il est utilisé pour réduire le nombre de pertes de finition dans les usines de papier.
(v) Il est utilisé pour trouver le routage optimal des messages dans un réseau de communication.
Définition de programmation linéaire:
La programmation linéaire est un outil / technique mathématique permettant de déterminer les meilleures utilisations des ressources d'une organisation. La programmation linéaire est conçue pour aider les gestionnaires à planifier et à prendre des décisions. En tant qu’outil de prise de décision, il a montré sa valeur dans différents domaines tels que la production; marketing marketing, recherche et affectation de personnel.
Détermination de la gamme de produits optimale, affectation des machines à la sélection des portefeuilles d'horaires de transport; l'emplacement de l'usine et la répartition de la main-d'œuvre, etc. sont les quelques types de problèmes qui peuvent être résolus à l'aide de la programmation linéaire.
"L'analyse des problèmes dans lesquels une fonction linéaire d'un nombre de variables doit être maximisée (ou minimisée) lorsque ces variables sont soumises à un nombre de contraintes sous la forme de linéaires en égalités.", "Samuelson et Slow
Selon Loomba, «la programmation linéaire n'est qu'un aspect de ce que l'on a appelé une approche système de la gestion où, dans tous les programmes, ils sont conçus et évalués en fonction de leurs effets ultimes sur la réalisation des objectifs de l'entreprise».
Problèmes de programmation linéaire - Méthode graphique:
Les étapes de la méthode graphique peuvent être résumées comme suit:
1. Formulez le problème de programmation linéaire.
2. Tracez les lignes de contrainte données en les considérant comme des équations.
3. Sur le graphique ci-dessus, identifiez la région de solution réalisable.
4. Localisez les points d’angle de la région de solution réalisable.
5. Calculez la valeur de la fonction objectif sur les points d’angle.
6. Choisissez maintenant le point où la fonction objectif a une valeur optimale.
Problèmes de programmation linéaire - Solution mathématique:
Bien que la méthode graphique de résolution de LPP soit une aide précieuse pour comprendre sa structure de base. La méthode a une utilité limitée dans les problèmes industriels car le nombre de variables y étant substantiellement plus grande. Par conséquent, une autre solution mathématique appelée méthode simplex est appropriée pour la résolution de LPP avec un grand nombre de variables.
Il s’agit d’une procédure itérative qui résout le LPP en un nombre fini d’étapes ou qui indique qu’il existe une solution illimitée à la méthode L.PR Simplex. Il s’agit d’une procédure algébrique permettant de résoudre des problèmes de programmation linéaire ou composée d’une série d’étapes répétitives. réaliser une solution optimale.
C'est un algorithme de programmation le plus largement utilisé. Théoriquement, cette procédure peut résoudre tout problème comportant un nombre quelconque de variables et de contraintes. Si le problème comporte plus de trois variables et trois contraintes, l'utilisation d'un ordinateur est requise. La figure 31.9 montre la représentation schématique de l'algorithme simplex.
Diverses étapes de la procédure simplex:
Les étapes de cette procédure sont énumérées ci-dessous:
1. Formulez le problème en déterminant la fonction objectif et les contraintes.
2. Convertissez les inégalités en égalités pour obtenir la forme standard en introduisant des excédents d’élasticité et des variables artificielles dans la fonction objectif.
3. Préparez la table simplex initiale.
4 .Calculez les valeurs z j (perte nette par unité) et c j - z j (contribution nette) pour cette solution.
5. Déterminez la variable d’entrée (colonne clé) en sélectionnant la colonne avec le plus négatif
(z j - c j ).
6. Déterminez la variable de départ (ligne clé) en calculant la colonne de ratio de la règle 5 et en choisissant la plus petite valeur non négative.
7. Calculez la ligne de remplacement du tableau simplex amélioré à l'aide de la règle 6.
8. Calculez les lignes restantes de la nouvelle table à l'aide de la règle 7.
9. Calculez les valeurs c j et z j pour cette solution.
10. S'il existe une valeur non négative (c j - z j ), retournez à l'étape 5.
11. S'il n'y a pas de valeurs non négatives (c j - z j ), la solution optimale a été obtenue.
Exemple 1:
Un agriculteur dispose de 1000 acres de terre sur laquelle il peut graver du maïs, du blé ou du soja. Chaque acre de maïs coûte Rs. 100 pour la préparation, nécessite 7 jours de travail et génère un bénéfice de Rs. 30 Un acre de blé coûte Rs. 120 pour préparer, requièrent 10 jours-homme de travail et rapportent un bénéfice de Rs. 40
Un acre de soja qui coûte 70 roupies à préparer nécessite 8 jours de travail et génère un bénéfice de roupies. 20 Si l'agriculteur a Rs. 100 000 pour la préparation et compte sur 8 000 journées de travail. Combien d’acres devraient être allouées à chaque culture pour maximiser les profits? (MBA du Gujarat, 1989)
Solution:
Soit x acre de terre attribuée au maïs
y acre de terre être alloué pour le blé
z acre de terre soit alloué au soja
Comme chaque acre de terre pour le maïs rapporte un bénéfice de Rs. 30, pour les rendements de blé, Rs. 40 et pour le soja Rs. 20. La formulation mathématique de la LLP est la suivante:
Max Z = 30x + 40y + 20z + 0S 1, + OS 2, + 0S 3
Sujet à
100 x + 120y + 70z ≤ 100000
7x + 10y + 8z ≤ 8000
x + y + z ≤ 1000
x, y, z ≥ 0
Convertissons les inégalités en équations en introduisant les variables de jeu S 1, S 2 et S 3 . La fonction objectif et la contrainte peuvent être écrites comme
Dans la colonne variable de base, les vecteurs correspondent aux variables S 1 (1, 0, 0), S 2, (1, 0, 1) et S 3 (0, 0, 1). La solution réalisable initiale est donnée par les variables S 1, S 2 et S 3 profit total = 0
Maintenant, Z j et C j - Z j sont calculés par les règles 1, 2 et 3. La colonne clé est déterminée avec la colonne de début marquée et le tableau II simplex est préparé comme suit.
Le tableau II ne fournit pas la solution optimale. Nous continuons ensuite à préparer le tableau III simple et à améliorer la solution comme suit:
Problème de minimisation par Big M. Méthode:
Dans l'industrie, il peut y avoir des endroits où l'objectif peut être de minimiser le coût de production ou la durée de fabrication, c'est-à-dire que la fonction de l'objectif doit être minimisée. Dans ce cas, nous pouvons procéder de la même manière qu'un problème de maximisation, simplement en multipliant par les deux côtés. de la fonction objective par-1 Dans de telles situations, la minimisation de Z sera la maximisation de (-Z).
Dans de tels cas, étant donné que les variables excédentaires prennent une valeur négative qui viole la restriction de non-négativité, pour surmonter cette difficulté, nous introduisons de nouvelles variables appelées des variables artificielles.
Nous assignons maintenant 3000 coefficient aux variables excédentaires et + M aux variables artificielles. Pour faire en sorte que les variables artificielles ne soient pas les variables de base de la solution optimale, nous leur attribuons un coût très élevé; par conséquent, M est défini comme un très grand nombre, à savoir Big M ou pénalité.
Cette méthode est illustrée à l'aide des éléments suivants:
Exemple 2:
Recherche opérationnelle: Outil n ° 2. Problèmes de transport:
Les problèmes de transport sont l’un des types de LPP dont l’objectif est de transporter des marchandises / produits en différentes quantités d’un même article / marchandise homogène vers différentes destinations, de manière à minimiser le coût de transport total dans la vie quotidienne des différents organismes de fabrication ou autres établissements. pour des raisons diverses stocker leurs produits finis ou leurs articles à divers endroits désignés comme étant des origines ou des marchandises, lorsque les utilisateurs sont transportés, les articles sont ensuite acheminés depuis les origines vers une ou plusieurs destinations. L'objectif général de ce processus est de décider d'une politique de distribution. de telle sorte que le coût total du transport soit minimal ou que le temps nécessaire au transbordement soit minimal.
Une fois que les produits finis d'origine de l'usine doivent être transportés vers les entrepôts de la manière la plus économique en cas de problèmes de transport, diverses caractéristiques de la programmation linéaire peuvent être observées ici. La disponibilité ainsi que les exigences des différents centres sont finies et constituent les problèmes de transport de ressources limitées. de la méthode simplex.
Application dans les vannes au transport de produits de plusieurs sources vers différents points de destination tels que:
(i) Unités de transport déchirées à destination. L'objectif est de minimiser les coûts de transport.
(ii) Maximiser les bénéfices en transportant les unités à destination.
Les principales étapes impliquées sont :
Étape 1:
Formulez le problème et configurez-le sous forme de matrice de transport.
Étape 2:
Obtenir la solution de base réalisable.
Étape 3:
Testez l'optimalité de la solution.
Étape 4:
Mettez à jour la solution en apportant des améliorations de réussite jusqu'à ce qu'il ne soit plus possible de réduire les coûts de transport.
Les méthodes couramment utilisées sont:
1. Méthode du coin nord-ouest.
2. Méthode la moins coûteuse.
3. Méthode d'approximation de Vogel.
Étapes impliquées dans la méthode du coin nord-ouest:
Étape 1:
Constriction d'une matrice maximale vide complétée par des lignes et des colonnes.
Étape 2:
Indiquez les totaux des lignes et des colonnes à la fin.
Étape 3:
En commençant par (11) cellule au coin nord-ouest de la matrice, allouez la quantité / nombre maximum possible en veillant à ce que l’affectation ne puisse être supérieure à la quantité requise par les entrepôts respectifs ni supérieure à la quantité disponible dans les centres de distribution.
Étape 4:
Après avoir ajusté les nombres de l'offre et de la demande dans les allocations de lignes et de colonnes respectives, passez à la première cellule de et rangée, répétez l'étape 3.
Étape 5:
Une fois que la demande de la première colonne est satisfaite, passez à la cellule suivante de la deuxième colonne et de la première ligne et passez à l’étape 3.
Étape 6:
Si pour un nombre de cellules égal, demandez-le, la prochaine allocation peut être affectée aux cellules des lignes et des colonnes suivantes.
Étape 7:
Continuez le processus jusqu'à ce que la quantité totale disponible soit entièrement allouée aux cellules selon les besoins
Exemple 3:
Résolvez le problème suivant avec NWCM pour calculer le coût de transport minimum:
Étapes de la méthode de saisie du moindre coût:
Cette méthode prend en compte le coût le plus bas et prend donc moins de temps pour résoudre le problème. Les différentes étapes sont les suivantes:
Étape 1:
Sélectionnez la cellule présentant le coût de transport le plus bas parmi toutes les lignes et les colonnes de la matrice. Allouez autant que possible pour éliminer la ligne ou la colonne qui épuise la source ou remplit complètement l'exigence. Si les deux sont satisfaits, éliminez l'un ou l'autre. Si la plus petite cellule de coût n'est pas unique, sélectionnez de manière arbitraire toute cellule présentant le coût le plus bas.
Étape 2:
Répétez la procédure pour toutes les lignes et colonnes non croisées avec la cellule de coût la plus petite suivante. Étape 3: Répétez la procédure jusqu'à ce que toutes les sources soient épuisées ou que la demande de toutes les destinations soit entièrement remplie.
Exemple 4:
Résoudre le problème suivant par la méthode du moindre coût:
Méthode d'approximation de Vogel:
Cette méthode est une méthode de pénalité ou de regrets et est préférée aux deux autres méthodes, la solution réalisable de base initiale étant optimale ou très proche de la solution optimale, ce qui permet de réduire le temps nécessaire au calcul de la solution optimale.
Dans cette méthode, la base de répartition est la pénalité de coût unitaire, c’est-à-dire que cette ligne ou cette colonne indique la pénalité de coût unitaire la plus élevée / la différence entre le coût le plus bas et le coût immédiatement supérieur est sélectionnée en premier lieu aux fins de la répartition. De cette manière, les allocations ultérieures dans les autres cellules sont également effectuées en tenant compte de la pénalité de coût unitaire la plus élevée.
La répartition est faite pour minimiser le coût de la pénalité. Les étapes suivantes sont les suivantes:
Étape 1:
Calculez la pénalité pour chaque rangée et colonne en prenant simplement la différence entre le plus petit et le plus petit coût de transport de la même rangée et colonne, c’est-à-dire que la différence indique la pénalité à payer si l’allocation n’est pas effectuée au coût minimal. critère.
Étape 2:
Sélectionnez une ligne ou une colonne avec la pénalité la plus lourde et allouez autant que possible la cellule la moins coûteuse. En cas d'égalité, une cellule d'allocation maximale possible est choisie en premier
Étape 3:
Rayer la ligne ou la colonne après avoir répondu à la demande ou épuisé l’offre, la ligne ou la colonne restante se voit attribuer une valeur de zéro. Toute ligne ou colonne dont l'offre ou la demande est nulle ne peut pas être utilisée pour des calculs ultérieurs.
Etape 4:
Répétez les étapes 1 et 3 jusqu'à ce que toutes les sources soient épuisées ou que toutes les conditions soient remplies.
Exemple 5:
Un fabricant veut expédier 8 chargements de son produit depuis les centres de production X, Y & Z vers les centres de distribution A, B et C. Le kilométrage de l'origine 0 à la destination D correspond à la matrice suivante.
Exemple 6:
Trouvez la solution optimale au problème de transport suivant en obtenant la solution initiale avec la méthode d'approximation de vogets:
Solution:
Appliquons la méthode d'approximation de vogel. Problèmes équilibrés en offre = demande = 50 unités. Appliquons la méthode de vogel comme indiqué dans le tableau ci-dessous.
Coût de transport = 2 x 15 + 9 x 15 + 20 x 10 + 4 x 5 + 18 x 5 x 475 unités.
Vérifier de manière optimale:
Le test d'optimalité peut être effectué si deux conditions sont remplies, à savoir
1. Il y a m + n - 1 attribution, dont m est le nombre de lignes, n le nombre de colonnes. Ici m + n - = 6. Mais le nombre d'attribution est cinq.
2. Ces attributions m + n-1 doivent se situer à des positions indépendantes, c'est-à-dire qu'il ne devrait pas être possible d'augmenter ou de diminuer une attribution sans modifier la position des attributions ou ne pas enfreindre les restrictions de lignes ou de colonnes.
Une règle simple pour que les allocations soient dans des positions indépendantes est qu’il est impossible de se déplacer d’une allocation à l’autre, une série d’étapes horizontales et verticales d’une cellule occupée à une autre, sans inversion directe d’itinéraire. On peut voir que, dans le présent exemple, l'allocation se situe à des positions indépendantes, aucune boucle fermée ne pouvant être formée au niveau des cellules allouées.
Par conséquent, la première condition n'est pas remplie et, par conséquent, afin de satisfaire à la première condition, nous devrons allouer une petite quantité E aux cellules vacantes ayant le coût de transport le plus bas. On peut voir que t peut être attribué à la cellule (2, 2) avec un coût de 7 unités, mais que les allocations resteront à une position indépendante, comme décrit ci-dessous dans le tableau 2.
Maintenant, le nombre d'allocations est m + n - 6 = 6 et ils occupent des postes indépendants. Écrivez la matrice des coûts dans les cellules allouées. (Tableau 3)
Matrice des coûts initiaux pour les cellules allouées. Également écrire les valeurs de u i et v j .
Le tableau 5 montre que l'évaluation de la cellule à la cellule (1, 4) est négative, c'est-à-dire -4. Par conséquent, en allouant à la cellule (1, 4) le coût de transport est encore réduit.
Écrivons les allocations originales et la nouvelle allocation proposée.
On peut voir dans le tableau 6 que si nous affectons à la cellule (1, 4) une boucle est formée comme indiqué, nous allouons 10 unités de sorte que l'attribution à la cellule (2, 4) s'annule comme indiqué ci-dessous dans le tableau 7. Nouveau table d'allocation deviendra
Coût de transport = 5X 2 + 10X 1 1 + 10X 7 + 15X 9 + 5X 4 + 18 + 5 = 435 unités.
Les coûts de transport sont passés de 475 unités à 435 unités.
Vérifier de manière optimale:
Voyons si cette solution est optimale ou non? Pour cela encore deux conditions doivent être vérifiées à savoir
Nombre d'attribution = m + n- 1 = 6 (satisfait)
Allocation à une position indépendante (satisfaite car la boucle fermée pour les cellules allouées n'est pas formée) Ecrire un coût en all alloué et les valeurs de u i et v j .
Recherche opérationnelle: outil n ° 3. Problème d’affectation:
Le problème d’affectation est un type particulier de problème de programmation linéaire qui traite de l’affectation individuelle des différentes ressources aux différentes activités.
Il le fait de telle sorte que le coût ou le temps nécessaire au processus soit minimal et que le profit ou la vente soit maximal. Bien que le problème puisse être résolu par la méthode simplex ou par la méthode de transport, le modèle d’affectation offre une approche plus simple de ces problèmes.
Dans une usine, un superviseur peut avoir six travailleurs disponibles et six emplois à licencier. Il devra décider quel travail devrait être confié à quel travailleur. Problème forme une à une base. C'est un problème de mission.
Modèle d'affectation:
Supposons qu'il y a n facilités et n emplois. Il est clair que dans ce cas, il y aura n assignations. Chaque établissement ou chaque travailleur peut effectuer chaque travail, un à la fois. Mais il devrait exister une procédure précise selon laquelle la cession devrait être effectuée de manière à maximiser le profit ou à minimiser le coût ou les délais.
Dans le tableau, Co ij est défini comme le coût lorsque le j e travail est attribué à son ouvrier. On peut noter ici qu’il s’agit d’un cas particulier de problème de transport lorsque le nombre de lignes est égal au nombre de colonnes.
Formulation mathématique:
Toute solution réalisable de base d’un problème d’affectation consiste en (2n - 1) variables dont les variables (n - 1) sont égales à zéro; n est le nombre d'emplois ou le nombre d'établissements.
En raison de cette forte dégénérescence, si nous résolvons le problème par les moyens de transport habituels, la tâche sera longue et complexe. Ainsi, une technique distincte est dérivée pour cela. Avant de passer à la méthode absolue, il est très important de formuler le problème.
Supposons que X ij est une variable définie comme
Méthode pour résoudre le problème (technique hongroise):
Considérons la fonction objectif du type de minimisation.
Les étapes suivantes sont impliquées dans la résolution de ce problème d’affectation:
1. Localisez «le plus petit élément de coût dans chaque ligne du tableau de coûts donné en commençant par la première ligne. Maintenant, ce plus petit élément est soustrait de chaque élément de cette ligne. Nous aurons donc au moins un zéro dans chaque ligne de cette nouvelle table.
2. Après avoir construit la table (comme à l'étape 1), prenez les colonnes de la table. À partir de la première colonne, localisez le plus petit élément de coût dans chaque colonne. Maintenant, soustrayez ce plus petit élément de chaque élément de cette colonne. Après avoir exécuté les étapes 1 et 2, nous obtiendrons au moins un zéro dans chaque colonne du tableau des coûts réduits.
3. Les affectations sont maintenant effectuées pour la table réduite de la manière suivante:
(i) Les lignes sont examinées successivement jusqu'à ce que la ligne avec exactement un (zéro) zéro soit trouvée. Une assignation est faite à ce zéro unique en mettant un carré □ autour de lui et dans la colonne correspondante, tous les autres zéros sont barrés (x) car ils ne seront pas utilisés pour effectuer une autre assignation dans cette colonne. L'étape est effectuée pour chaque ligne.
(ii) L'étape 3 (i) est maintenant effectuée sur les colonnes comme suit: Les colonnes sont examinées successivement jusqu'à ce qu'une colonne avec exactement un zéro soit trouvée. Désormais, l'attribution à ce zéro unique est effectuée en mettant le carré autour de celui-ci et, en même temps, tous les autres zéros des lignes correspondantes sont barrés (x). Une étape est effectuée pour chaque colonne.
(iii) Les étapes 3 (i) et 3 (ii) sont répétées jusqu'à ce que tous les zéros soient marqués ou barrés. Maintenant, si le nombre de zéros marqués ou les assignations effectuées sont égaux au nombre de lignes ou de colonnes, la solution optimale a été atteinte. Il y aura exactement une seule affectation dans chaque colonne ou des colonnes sans aucune assignation. Dans ce cas, nous allons passer à l’étape 4.
4. À ce stade, tracez le nombre minimum de lignes (horizontales et verticales) nécessaires pour couvrir tous les zéros de la matrice obtenue à l'étape 3.
La procédure suivante est adoptée:
(i) Cochez (V) toutes les lignes qui n’ont aucune affectation.
(ii) Maintenant, cochez (V) toutes ces colonnes qui ont zéro dans les lignes cochées.
(iii) Maintenant, coche toutes les lignes qui ne sont pas déjà marquées et qui ont une affectation dans les colonnes marquées.
(iv) Toutes les étapes, à savoir 4 (1), 4 (2), 4 (3) sont répétées jusqu'à ce qu'il ne soit plus possible de marquer des lignes ou des colonnes,
(v) Maintenant, tracez des lignes droites qui passent à travers toutes les lignes non marquées et les colonnes marquées. On peut aussi noter que dans une matrice nxn, toujours moins de 'n' lignes couvriront tous les zéros s'il n'y a pas de solution parmi eux.
5. À l’étape 4, si le nombre de lignes dessinées est égal à n ou au nombre de lignes, c’est la solution optimale sinon, passez à l’étape 6.
6. Sélectionnez le plus petit élément parmi tous les éléments non couverts. Maintenant, cet élément est soustrait de tous les éléments non couverts et ajouté à l'élément qui se trouve à l'intersection de deux lignes. C'est la matrice pour les nouvelles affectations.
7. Répétez la procédure à partir de l'étape (3) jusqu'à ce que le nombre d'affectations devienne égal au nombre de lignes ou au nombre de colonnes.
