3 herramientas importantes de investigación de operación
Este artículo arroja luz sobre las tres herramientas importantes de la investigación de operaciones. Las herramientas son: 1. Programación lineal 2. Problemas de transporte 3. Problema de asignación.
Investigación de Operación: Herramienta # 1. Programación Lineal:
La programación lineal es una técnica matemática que se aplica a casi toda clase de problemas de decisión. Esta técnica se aplica para elegir como la mejor alternativa de un conjunto de alternativas factibles.
En LPP, la función objetiva y las restricciones se pueden expresar como una función matemática lineal, que se puede utilizar para resolver los problemas prácticos de programación. Es un método utilizado para estudiar el comportamiento de los sistemas.
LP se ocupa principalmente de describir la interrelación de los componentes de un sistema. Esta técnica está diseñada para ayudar a los gerentes en la planificación, toma de decisiones y para asignar los recursos. La administración siempre tiene la tendencia de hacer el uso más efectivo de un recurso de la organización. Los recursos incluyen maquinaria, materias primas, mano de obra, almacén, tiempo y dinero.
Estos recursos se pueden utilizar para producir productos de diversos tipos, como máquinas, partes / componentes, muebles y productos alimenticios, etc. De manera similar, los recursos se pueden utilizar para brindar servicios, como el cronograma de envío, las políticas de publicidad y las decisiones de inversión.
Todas las organizaciones tienen que tomar una decisión sobre la asignación de sus recursos limitados. Por lo tanto, se requiere que las administraciones asignen continuamente recursos escasos para alcanzar los objetivos / objetivos / metas de la organización.
El adjetivo lineal se ha utilizado para describir una relación entre dos o más variables. La programación se ocupa del uso de ciertas ecuaciones matemáticas utilizadas para obtener la mejor solución posible para un problema que involucra recursos limitados / escasos.
Por lo tanto, la programación lineal se utiliza para problemas de optimización que satisfacen la siguiente condición:
(i) La función objetivo que se va a optimizar debe estar bien definida y expresada como una función lineal de las variables.
(ii) La limitación, si alguna, con respecto al logro de estos objetivos también se expresa como cualidades lineales / desigualdades de la variable.
(iii) Algunas acciones alternativas también disponibles.
(iv) Las variables de decisión están interrelacionadas y no son negativas.
(v) Los recursos son limitados.
Aplicación de la Programación Lineal a Problemas Industriales:
(i) Desarrollar la programación para las industrias de procesamiento de alimentos y para las refinerías de petróleo, etc.
(ii) En las industrias metalúrgicas, se utiliza para cargar en el taller y para determinar la elección entre comprar y producir varias partes.
(iii) Se utiliza para evaluar diversos minerales de hierro en las industrias del hierro y el acero.
(iv) Se utiliza para reducir la cantidad de pérdidas de recorte en las fábricas de papel.
(v) Se utiliza para encontrar el enrutamiento óptimo de mensajes en la red de comunicación.
Definición de programación lineal:
La programación lineal es una herramienta / técnica matemática para determinar los mejores usos de los recursos de una organización. La programación lineal está diseñada para ayudar a los gerentes con respecto a la planificación y la toma de decisiones. Como herramienta de toma de decisiones, ha mostrado su valor en diferentes áreas como la producción; Financiamiento de marketing, investigación y asignaciones de personal.
Determinación de la combinación óptima de productos, asignación de máquinas de selección de cartera de programas de transporte; la ubicación de la planta y la asignación de mano de obra, etc. son los pocos tipos de problemas que pueden resolverse con la ayuda de la programación lineal.
"El análisis de problemas en los que una función lineal de una serie de variables se debe maximizar (o minimizar) cuando estas variables están sujetas a un número de restricciones en forma de lineales en la igualdad." Samuelson y Slow
Según Loomba, “la programación lineal es solo un aspecto de lo que se ha denominado un enfoque de sistema para la gestión en el que, en todos los programas, se diseñan y evalúan en términos de sus efectos finales en la realización de los objetivos empresariales”.
Problemas de programación lineal-Método gráfico:
Los pasos del método gráfico se pueden resumir de la siguiente manera:
1. Formular el problema de la programación lineal.
2. Grafica las líneas de restricción dadas considerándolas como ecuaciones.
3 .Desde el gráfico anterior, identifique la región de solución factible.
4. Localice los puntos de esquina de la región de solución factible.
5. Calcule el valor de la función objetivo en los puntos de esquina.
6. Ahora elija el punto donde la función objetivo tiene un valor óptimo.
Problemas de programación lineal-Solución matemática:
Aunque el método gráfico de resolver LPP es una ayuda valiosa para comprender su estructura básica. El método es de utilidad limitada en problemas industriales, ya que la cantidad de variables que ocurren allí es sustancialmente grande, por lo que otra solución matemática llamada método símplex es adecuada para resolver LPP con una gran cantidad de variables.
Es un procedimiento iterativo que resuelve LPP en un número finito de pasos o da una indicación de que existe una solución ilimitada para L.PR. El método Simplex es un procedimiento algebraico para resolver problemas de programación lineal o está compuesto por una serie de pasos repetitivos para Lograr una solución óptima.
Es un algoritmo de programación más ampliamente utilizado. En teoría, este procedimiento puede resolver cualquier problema consistente en cualquier número de variables y restricciones. Si el problema consiste en más de tres variables y tres restricciones, se requiere el uso de la computadora. La figura 31.9 muestra la representación esquemática del algoritmo simplex.
Varios pasos en el procedimiento simplex:
Los pasos de este procedimiento se enumeran a continuación:
1. Formule el problema determinando la función objetivo y las restricciones.
2. Convierta las desigualdades en igualdad para obtener la forma estándar mediante la introducción de excedentes de holgura y variables artificiales en la función objetivo.
3. Prepare la tabla simplex inicial.
4. Calcule el valor de z j (pérdida neta por unidad) y c j - z j (contribución neta) para esta solución.
5. Determine la variable que ingresa (columna clave) seleccionando la columna con la mayoría negativa
(z j - c j ).
6. Determine la variable que sale (fila clave) calculando la columna de relación de la regla 5 y eligiendo el valor no negativo más pequeño.
7. Calcule la fila de reemplazo de la tabla simplex mejorada según la regla 6.
8. Calcule las filas restantes de la nueva tabla según la regla 7.
9. Calcule el valor de c j y z j para esta solución.
10. Si hay un valor no negativo (c j - z j ), vuelva al paso 5.
11. Si no hay valores no negativos (c j - z j ), se ha obtenido la solución óptima.
Ejemplo 1:
Un agricultor tiene 1000 acres de tierra en la que puede cultivar maíz, trigo o soja, cada acre de maíz cuesta Rs. 100 para la preparación, requiere 7 días hábiles de trabajo y produce un beneficio de Rs. 30 Un acre de trigo cuesta Rs. 120 para prepararse, requieren 10 días hábiles de trabajo y producen un beneficio de Rs. 40.
Un acre de soja cuesta Rs70 para prepararse requiere 8 días de trabajo por hombre y produce un beneficio de Rs. 20 Si el agricultor tiene Rs. 100.000 para preparación y cuenta con 8000 jornadas laborales. ¿Cuántos acres se deben asignar a cada cultivo para maximizar las ganancias? (Gujarat MBA, 1989)
Solución:
Que x acre de tierra se asigne para el maíz
Y acre de tierra se asignará para el trigo
Z acre de tierra se asignará para la soja
Dado que cada acre de tierra para el maíz produce un beneficio de Rs. 30, para rendimientos de trigo Rs. 40 y para la soja Rs. 20. La formulación matemática de la LLP es
Max Z = 30x + 40y + 20z + 0S 1, + OS 2, + 0S 3
Sujeto a
100 x + 120y + 70z ≤ 100000
7x + 10y + 8z ≤ 8000
x + y + z ≤ 1000
x, y, z ≥ 0
Convirtamos las desigualdades en ecuaciones introduciendo las variables de holgura S 1, S 2 y S 3 . La función objetivo y la restricción se pueden escribir como
En la columna de variables básicas, los vectores son para la variable S 1, (1, 0, 0), S 2, (1, 0, 1) y S 3 (0, 0, 1). La solución factible inicial está dada por las variables S 1, S 2 y S 3, ambos beneficios totales = 0
Ahora Z j y C j - Z j, se calculan mediante las Reglas 1, 2 y 3. La columna de clave se determina con la columna marcada de inicio y la Tabla II de Simplex se prepara de la siguiente manera.
La Tabla II no proporciona una solución óptima. Continuamos para preparar la tabla III simple y mejorar la solución de la siguiente manera:
Problema de minimización por Big M. Método:
En la industria puede situarse donde el objetivo puede ser minimizar el costo de producción o la duración de la fabricación, es decir, la función objetivo debe minimizarse en tales casos, podemos proceder de la misma manera que un problema de maximización simplemente multiplicando por ambos lados de la función objetivo por-1 En tales situaciones, la minimización de Z será la maximización de (-Z).
En tales casos, dado que las variables excedentes toman un valor negativo que viola la restricción de no negatividad, para superar esta dificultad introducimos una nueva variable denominada como variables artificiales.
Ahora asignamos 3000 coeficientes a las variables excedentes y + M a las variables artificiales. Para hacer que las variables artificiales no sean las variables básicas en la solución óptima, les asignamos un costo muy alto, por lo que M se define como un número muy grande, es decir, Big M o penalización.
Este método se ilustra con la ayuda de lo siguiente:
Ejemplo 2:
Investigación de Operación: Herramienta # 2. Problemas de transporte:
Los problemas de transporte son uno de los tipos de LPP en los cuales el objetivo es transportar bienes / productos en diversas cantidades de un único artículo / producto homogéneo a diferentes destinos para minimizar el costo total de transporte en la vida cotidiana de las diversas organizaciones de manufactura u otros establecimientos. Para diversas consideraciones, almacenar sus productos finales o artículos en diversos lugares denominados como orígenes o artículos, cuando el suministro se debe hacer a los usuarios, los artículos se transportan desde los orígenes a uno o más destinos. El propósito general de este proceso es decidir una política de distribución. de modo que el costo total de transporte sea mínimo o el tiempo consumido en el transbordo sea mínimo.
Después de que los productos terminados de forma nativa de la planta se transporten a los almacenes de la manera más económica posible en los problemas de transporte, se pueden observar varias características de la programación lineal, tanto la disponibilidad como los requisitos de los distintos centros son limitados y constituyen los recursos limitados. del método simplex.
Aplicación en válvulas para el transporte de productos desde diversas fuentes hasta diversos puntos de destino como:
(i) Unidades de transporte desgarradas del destino. El objetivo es minimizar el costo de transporte.
(ii) Maximizar la ganancia en el transporte de las unidades a destino.
Los principales pasos involucrados son :
Paso 1:
Formular el problema y configurar en forma de matriz de transporte.
Paso 2:
Obtener la solución básica factible.
Paso 3:
Prueba de optimalidad de solución.
Etapa 4:
Actualice la solución a través de mejoras exitosas hasta que no sea posible una disminución adicional en el costo de transporte.
Los métodos más utilizados son:
1. Método de la esquina noroeste.
2. Método de menor costo.
3. Método de aproximación de Vogel.
Pasos involucrados en el método de la esquina noroeste:
Paso 1:
Restrinja una matriz máxima vacía completada con filas y columnas.
Paso 2:
Indique los totales de fila y los totales de columna al final.
Paso 3:
Comenzando con la celda (11) en el extremo noroeste de la matriz, asigne la cantidad / número máximo posible teniendo en cuenta que la asignación no puede ser más que la cantidad requerida por los almacenes respectivos ni más que la cantidad disponible en los centros de suministro.
Etapa 4:
Después de realizar el ajuste de los números de oferta y demanda en las respectivas asignaciones de filas y columnas, vaya a la primera celda de y repita el paso 3.
Paso 5:
Una vez satisfecha la demanda de la primera columna, realice la siguiente celda en la segunda columna y la primera fila y vaya al paso 3.
Paso 6:
Si para cualquier suministro de celdas es igual a la demanda, la siguiente asignación puede ser el modo en celdas en las siguientes filas y columnas.
Paso 7:
Continuar el proceso hasta que la cantidad total disponible se asigne por completo a las celdas según el requisito
Ejemplo 3:
Resuelva el siguiente problema mediante NWCM para calcular el costo mínimo de transporte:
Pasos en el método de entrada de menor costo:
Este método toma en consideración el costo más bajo y, por lo tanto, toma menos tiempo para resolver el problema, los distintos pasos son los siguientes:
Paso 1:
Seleccione la celda con el costo de transporte más bajo entre todas las filas y columnas de la matriz. Asigne tanto como sea posible para eliminar esa fila o columna que agote la fuente o complete el requisito. Si ambos son satisfactorios, elimina cualquiera de los dos. Si la celda de menor costo no es única, seleccione arbitrariamente cualquier celda con el menor costo.
Paso 2:
Repita el procedimiento para todas las filas y columnas sin cruzar con la siguiente celda de costo más pequeña. Paso 3: repita el procedimiento hasta que todas las fuentes se agoten o la demanda de todos los destinos se llene por completo.
Ejemplo 4:
Resuelva el siguiente problema por el método de menor costo:
Método de aproximación de Vogel:
Este método es un método de penalización o arrepentimiento y es preferible a los otros dos métodos, la solución factible básica inicial obtenida en forma óptima o muy cercana a la solución óptima, por lo que se reduce el tiempo necesario para calcular la solución óptima.
En este método, la base de la asignación es la penalización de costo unitario, es decir, esa fila o columna que indica la penalización de costo unitario más alta / la diferencia entre el costo más bajo y el siguiente más alto se selecciona primero para el propósito de la asignación. De esta manera, las asignaciones subsiguientes en las otras celdas también se hacen teniendo en cuenta la mayor penalización por costo unitario.
La asignación se realiza para minimizar el costo de la multa, los diferentes pasos involucrados son los siguientes:
Paso 1:
Calcule la penalización para cada fila y columna; para ello, simplemente tome la diferencia entre el costo de transporte más pequeño y el siguiente en la misma fila y columna, es decir, la diferencia indica la penalización a pagar si la asignación no se realiza al costo mínimo. criterio.
Paso 2:
Seleccione una fila o columna con la mayor penalización y asigne la mayor cantidad posible a la celda de menor costo. En caso de empate, se elige primero una celda de asignación máxima posible.
Paso 3:
Tache la fila o la columna después de satisfacer la demanda o de agotar el suministro, a la fila o columna restante se le asigna una oferta o demanda cero. Cualquier fila o columna con cero oferta o demanda no se puede utilizar para cálculos adicionales.
Pasos 4:
Repita los pasos 1 y 3 hasta que se agoten todas las fuentes o se cumplan todos los requisitos.
Ejemplo 5:
Un fabricante desea enviar 8 cargas de su producto desde los centros de producción X, Y y Z a los centros de distribución A, B y C. El kilometraje desde el origen 0 hasta el destino D es la siguiente matriz.
Ejemplo 6:
Encuentre la solución óptima para el siguiente problema de transporte al obtener una solución inicial con el método de aproximación de vogets:
Solución:
Apliquemos el método de aproximación de vogel. Problemas equilibrados como oferta = demanda = 50 unidades. Apliquemos el método de vogel como se muestra en la tabla a continuación.
Costo de transporte = 2 x 15 + 9 x 15 + 20 x 10 + 4 x 5 + 18 x 5 x 475 unidades.
Compruebe de forma óptima:
Se puede realizar la prueba de optimalidad si se cumplen dos condiciones, es decir
1. Hay m + n - 1 asignación, cuya m es el número de filas, n es el número de columnas. Aquí m + n - = 6. Pero el número de asignación es cinco.
2. Estas asignaciones de m + n-1 deben estar en posiciones independientes, es decir, no debería ser posible aumentar o disminuir ninguna asignación sin cambiar la posición de las asignaciones o violar las restricciones de fila o columna.
Una regla simple para que las asignaciones se encuentren en posiciones independientes es que es imposible viajar desde cualquier asignación, una serie de pasos horizontales y verticales de una celda ocupada a otra, sin una inversión directa de la ruta. Se puede ver que en el presente ejemplo, la asignación está en posiciones independientes ya que no se puede formar un bucle cerrado en las celdas asignadas.
Por lo tanto, no se cumple la primera condición y, por lo tanto, para satisfacer la primera condición, tendremos que asignar una pequeña cantidad E a las celdas vacías que tengan el costo de transporte más bajo. Puede verse que t puede asignarse a la celda (2, 2) que tiene un costo de 7 unidades y aún así las asignaciones permanecerán en una posición independiente como se describe a continuación en la Tabla 2.
Ahora el número de asignaciones es m + n - 6 = 6 y están en posiciones independientes. Anote la matriz de costos en las celdas asignadas. (Tabla 3)
Matriz de costo inicial para celdas asignadas. Escribe también los valores de u i y v j .
En la Tabla 5 se puede ver que la evaluación de la celda en la celda (1, 4) es negativa, es decir -4, por lo tanto, al asignar el costo de transporte a la celda (1, 4), se debe reducir aún más.
Anotemos las asignaciones originales y la nueva asignación propuesta.
Se puede ver en la Tabla 6 que si asignamos en la celda (1, 4) se forma un bucle como se muestra y asignamos 10 unidades para que la asignación en la celda (2, 4) desaparezca como se muestra a continuación en la Tabla 7. Nueva tabla de asignación se convertirá
Costo de transporte = 5X 2 + 10X 1 1 + 10X 7 + 15X 9 + 5X 4 + 18 + 5 = 435 unidades.
Es decir, el costo de transporte ha bajado de 475 unidades a 435 unidades.
Compruebe de forma óptima:
Veamos si esta solución es óptima o no? Para eso de nuevo hay que comprobar dos condiciones, es decir,
Nº de asignación = m + n- 1 = 6 (satisfecho)
Asignación en una posición independiente (se cumple ya que no se forma el bucle cerrado para las celdas asignadas) Escriba el costo en todos los valores asignados y los valores de u i y v j .
Investigación de Operación: Herramienta # 3. Problema de Asignación:
El problema de asignación es un tipo especial de problema de programación lineal que se ocupa de la asignación de los diversos recursos a las diversas actividades de forma individualizada.
Lo hace de tal manera que el costo o el tiempo involucrado en el proceso es mínimo y la ganancia o venta es máxima. Aunque el problema se puede resolver con el método símplex o con el método de transporte, el modelo de asignación proporciona un enfoque más simple para estos problemas.
En una fábrica, un supervisor puede tener seis trabajadores disponibles y seis trabajos para despedir. Tendrá que tomar una decisión sobre qué trabajo debe asignarse a cada trabajador. El problema se forma uno a uno. Este es un problema de asignación.
Modelo de asignación:
Supongamos que hay n facilidades yn puestos de trabajo. Está claro que en este caso, habrá n asignaciones. Cada instalación o dicho trabajador puede realizar cada trabajo, uno a la vez. Pero debe haber cierto procedimiento mediante el cual se debe realizar la asignación de modo que la ganancia se maximice o el costo o los tiempos se minimicen.
En la tabla, Co ij se define como el costo cuando se asigna un trabajo j a un trabajador. Se puede observar aquí que este es un caso especial de problema de transporte cuando el número de filas es igual al número de columnas.
Formulación matemática:
Cualquier solución factible básica de un problema de asignación consiste en variables (2n - 1) de las cuales las variables (n - 1) son cero; n es el número de puestos de trabajo o número de instalaciones.
Debido a esta alta degeneración, si resolvemos el problema mediante el método de transporte habitual, será un trabajo complejo y que requiere mucho tiempo. Así se deriva una técnica separada para ello. Antes de pasar al método absoluto es muy importante formular el problema.
Supongamos que X ij es una variable que se define como
Método para resolver el problema (técnica húngara):
Considere la función objetivo del tipo de minimización.
Los siguientes pasos están involucrados en la solución de este problema de asignación:
1. Localice 'el elemento de costo más pequeño en cada fila de la tabla de costos dada comenzando con la primera fila. Ahora, este elemento más pequeño se resta de cada elemento de esa fila. Por lo tanto, obtendremos al menos un cero en cada fila de esta nueva tabla.
2. Habiendo construido la tabla (como en el paso-1) toma las columnas de la tabla. A partir de la primera columna, ubique el elemento de menor costo en cada columna. Ahora resta este elemento más pequeño de cada elemento de esa columna. Habiendo realizado el paso 1 y el paso 2, obtendremos al menos un cero en cada columna en la tabla de costos reducidos.
3. Ahora, las asignaciones se realizan para la tabla reducida de la siguiente manera:
(i) Las filas se examinan sucesivamente, hasta que se encuentra la fila con exactamente un cero (uno). La asignación se realiza a este cero único colocando el cuadrado □ a su alrededor y en la columna correspondiente, todos los demás ceros están tachados (x) porque no se utilizarán para realizar ninguna otra asignación en esta columna. Paso se lleva a cabo para cada fila.
(ii) El Paso 3 (i) ahora se realiza en las columnas de la siguiente manera: Las columnas se examinan sucesivamente hasta que se encuentra una columna con exactamente un cero. Ahora, la asignación se realiza a este cero único colocando el cuadrado a su alrededor y, al mismo tiempo, todos los demás ceros en las filas correspondientes se cruzan (x) se realiza un paso para cada columna.
(iii) Los pasos 3 (i) y 3 (ii) se repiten hasta que todos los ceros estén marcados o tachados. Ahora, si el número de ceros marcados o las asignaciones realizadas son iguales al número de filas o columnas, se ha logrado una solución óptima. Habrá exactamente una sola asignación en cada columna o sin ninguna asignación. En este caso, vamos al paso 4.
4. En esta etapa, dibuje el número mínimo de líneas (horizontal y vertical) necesarias para cubrir todos los ceros en la matriz obtenida en el paso 3.
Se adopta el siguiente procedimiento:
(i) Marca de verificación (V) todas las filas que no tienen ninguna asignación.
(ii) Ahora marque (V) todas estas columnas que tienen cero en las filas marcadas con tic.
(iii) Ahora marque todas las filas que aún no están marcadas y que tienen asignación en las columnas marcadas.
(iv) Todos los pasos, es decir, 4 (1), 4 (2), 4 (3) se repiten hasta que no se puedan marcar más filas o columnas,
(v) Ahora dibuje líneas rectas que pasen por todas las filas sin marcar y las columnas marcadas. También se puede notar que en una matriz nxn, siempre menos de 'n' líneas cubrirán todos los ceros si no hay solución entre ellos.
5. En el paso 4, si el número de líneas dibujadas es igual a n o el número de filas, entonces, si no, es la solución óptima, luego vaya al paso 6.
6. Seleccione el elemento más pequeño entre todos los elementos descubiertos. Ahora, este elemento se resta de todos los elementos descubiertos y se agrega al elemento que se encuentra en la intersección de dos líneas. Esta es la matriz para tareas nuevas.
7. Repita el procedimiento desde el paso (3) hasta que el número de asignaciones sea igual al número de filas o el número de columnas.
