El documento describe el método de programación lineal de transporte. Este método asigna productos de un conjunto de orígenes a un conjunto de destinos de manera que se optimice el costo total. El documento explica la formulación matemática del modelo, incluyendo la función objetivo de minimizar costos y las restricciones de oferta y demanda. También describe métodos como el de la esquina noroeste y el de costo mínimo para resolver problemas de transporte.
0 calificaciones0% encontró este documento útil (0 votos)
84 vistas34 páginas
El documento describe el método de programación lineal de transporte. Este método asigna productos de un conjunto de orígenes a un conjunto de destinos de manera que se optimice el costo total. El documento explica la formulación matemática del modelo, incluyendo la función objetivo de minimizar costos y las restricciones de oferta y demanda. También describe métodos como el de la esquina noroeste y el de costo mínimo para resolver problemas de transporte.
El documento describe el método de programación lineal de transporte. Este método asigna productos de un conjunto de orígenes a un conjunto de destinos de manera que se optimice el costo total. El documento explica la formulación matemática del modelo, incluyendo la función objetivo de minimizar costos y las restricciones de oferta y demanda. También describe métodos como el de la esquina noroeste y el de costo mínimo para resolver problemas de transporte.
El documento describe el método de programación lineal de transporte. Este método asigna productos de un conjunto de orígenes a un conjunto de destinos de manera que se optimice el costo total. El documento explica la formulación matemática del modelo, incluyendo la función objetivo de minimizar costos y las restricciones de oferta y demanda. También describe métodos como el de la esquina noroeste y el de costo mínimo para resolver problemas de transporte.
Descargue como PDF, TXT o lea en línea desde Scribd
Descargar como pdf o txt
Está en la página 1/ 34
Investigación de operaciones I
Filiberto De La Rosa Anhuaman.
Programación lineal Transporte • El método del transporte es una aplicación singular de la programación lineal cuyo objetivo es determinar el esquema de transporte que minimice el coste total de este, conocidos los costes unitarios desde el origen i hasta el destino j. Además, se sabe que el producto está disponible en una determinada cantidad bi en cada uno de los m orígenes, y es necesario que sea llevado a cada uno de los n destinos posibles en una cantidad demandada. • Es un método de programación lineal para la asignación de artículos de un conjunto de origines a un conjunto de destinos de tal manera que se optimice la función objetivo. Programación lineal Transporte • Esta técnica es particularmente usada en organizaciones que producen el mismo producto en numerosas plantas y que envía sus productos a diferentes destinos (Centros de distribución, almacenes). También se aplica en distribución, análisis de localización de plantas y programación de la producción. • Para que un problema pueda ser solucionado por el método de transporte, este debe reunir tres condiciones: • La función objetivo y las restricciones deben de ser lineales. Los artículos deben de ser uniformes e intercambiables, los coeficientes de todas las variables en la ecuación deben de ser 0 o 1. Programación lineal Transporte • La suma de las capacidades de las fuentes debe ser igual a la suma de los requerimientos de los destinos, si alguna desigualdad existe una variable de holgura deberá ser añadida. • X11 C11 1 1 • O1 X12 C21 D1 • X21 C31 C12 • O2 2 X22 C22 2 D2 • X31 C32 • O3 3 X32 Formulación del modelo de Programación Lineal • Función objetivo minimizar costos • Mini Z = X11C11+X12C12+X21C21+X22C22+X31C31+X32C32 • Restricciones de oferta • X11+X12<=O1 • X21+X22<=O2 • X31+X32<=O3 • Demanda • X11+X21+X31= D1 • X12+X22+X32 = D2 Método de la Esquina Noroeste • La regla de la esquina noroeste muestra como obtener una rápida solución inicial. Esta no toma en consideración el costo de enviar una unidad de un centro de distribución a un centro de consumo. • Se obtiene realizando una asignación que no considera costos o beneficios. Inicia en la celda superior izquierda (esquina noroeste) de la tabla. • Asignar a esta celda la cantidad menor entre lo requerido y lo disponible (menor cantidad entre restricciones de esa fila y esa columna). Reste la cantidad asignada de lo disponible en la capacidad y lo requerido (restricción de la fila y la columna respectivamente), y elimine la fila o la columna que quede a nivel cero en su restricción. • Repetir el paso 1. Ejemplo: • Una empresa dispone de cuatro plantas para producir gel antibacterial y satisfacer las necesidades de cuatro hospitales, las plantas pueden satisfacer 15, 10, 40 y 23 litros de gel antibacterial respectivamente, las necesidades de los cuatro hospitales al día son: 30, 15, 22 y 21 litros de gel, los costos asociados al envió de gel entre cada planta y cada hospital son los registrados en la siguiente tabla: Solución: Hospital 1 Hospital 2 Hospital 3 Hospital 4 Oferta Planta 1 6 15 2 X 1 X 4 X 15 0 Planta 2 3 10 5 X 7 X 1 X 10 0 Planta 3 4 5 3 15 2 20 8 X 40 35 20 0 Planta 4 5 X 2 X 4 2 2 21 23 21 0 Demanda 30 15 15 0 22 2 21 88 5 0 0 0 88
FO = 6(15)+3(10)+4(5)+3(15)+2(20)+4(2)+2(21) = 275 Ejemplo: • Resolver el siguiente problema de transporte:
T1 T2 T3 T4 Oferta A 2 5 4 1 20 B 8 6 4 2 20 C 2 1 6 5 20 D 10 3 2 4 20 Demanda 25 15 25 10 Método de Costo Mínimo • Método de costo mínimo: Es un algoritmo que tiene el objetivo de desarrollar la resolución de problemas relacionados con el transporte o distribución proyectando mejores resultados que otros métodos, como es el caso de la esquina noreste. Esto se debe, a que puede enfocarse en diversas rutas menores, que su vez presentan costos menores. • El diagrama de flujo de este tipo de algoritmo, suele ser mucho más sencillo que otros, ya que simplemente se relaciona con la asignación de todas las cantidades posibles de unidades que se encuentran sujetas a todas las restricciones de demandas y ofertas, es decir, a todas las celdas de menor costo de toda la matriz hasta llegar al final del método. Ejemplo: • La compañía Su Ray Corporación transporta grano desde tres silos hasta tres molinos, la oferta en camionadas y la demanda también en camionadas se resume en el modelo de transporte de la tabla junto con los costos unitarios de transporte por camionada en las distintas rutas. • Los costos unitarios de transporte Cij que se observan en las celdas están en miles de soles. • Determinar el costo mínimo de transporte para llevar del origen al destino. Solución: 1 2 3 4 oferta 1 10 2 10 11 15 2 12 7 9 20 25 3 4 14 16 18 10 Demanda 5 15 15 15
Costo mínimo= 5(4)+15(2)+15(9)+0(11)+10(20)+5(18) = 475 mil soles.
Ejercicio: • Hallar el costo mínimo de transporte de Maíz del origen al destino:
Avicola 1 Avicola 2 Avicola 3 Avicola 4 Oferta
Fundo 1 10 0 20 11 15 Fundo 2 12 7 9 20 25 Fundo 3 0 14 16 18 5 Demanda 5 15 15 10 Método de Vogel • El método de aproximación de Vogel es un método heurístico de resolución de problemas de transporte capaz de alcanzar una solución básica no artificial de inicio, este modelo requiere de la realización de un número generalmente mayor de iteraciones que los demás métodos heurísticos existentes con este fin, sin embargo produce mejores resultados iniciales que los mismos. • El método consiste en la realización de un algoritmo que consta de 3 pasos fundamentales: • Determinar para cada fila y columna una medida de penalización restando los dos costos menores en filas y columnas. Procedimiento: • Escoger la fila o columna con la mayor penalización, es decir que de la resta realizada en el "Paso 1" se debe escoger el número mayor. En caso de haber empate, se debe escoger arbitrariamente (a juicio personal). • De la fila o columna de mayor penalización determinada en el paso anterior debemos de escoger la celda con el menor costo, y en esta asignar la mayor cantidad posible de unidades. Una vez se realiza este paso una oferta o demanda quedará satisfecha por ende se tachará la fila o columna, en caso de empate solo se tachará 1, la restante quedará con oferta o demanda igual a cero (0). Ejemplo: Determinar el costo mínimo por el método de vogel Solución: 1 2 3 4 oferta Penal 1 Penal 2 Penal 3 1 10 2 15 20 11 0 15 0 10-2=8 11-2=9 20-11=9 2 12 7 9 15 20 10 25 10 0 9-7=2 9-7=2 20-9=11 3 4 5 14 16 18 5 10 5 0 14-4=10 16-14=2 18-16=2 Demanda 5 0 15 0 15 0 15 10 Penal 1 10-4=6 7-2=5 16-9=7 18-11=7 Penal 2 - 7-2=5 16-9=7 18-11=7 Penal 3 - - 16-9=7 18-11=7
Costo mínimo= 5(4)+15(2)+15(9)+0(11)+10(20)+5(18)= 475 miles de soles
Ejercicio: • Una compañía tiene fabricas ubicadas en A, B, C, D que proveen a los almacenes ubicados en E, F, G, H, I las capacidades mensuales de las fabricas son de 200, 225, 175 y 350 respectivamente, las necesidades mensuales de los almacenes son 130, 110, 140, 260 y 190 respectivamente. Los costos de embarque son los siguientes:
E F G H I A 14 19 32 9 21 B 15 10 18 7 11 C 26 12 13 18 16 D 11 22 14 14 18 Método de Russell • Esta metodología es comparable a la de Vogel en cuanto a la aproximación de la solución óptima que ambos métodos generan, solo que este método es menos común que el anterior debido a que requiere mayores cálculos. • Consiste en asignar o distribuir diferentes cantidades de objetos desde unos orígenes hacía unos destinos buscando hacerlo de una manera óptima, es decir a un costo mínimo ( o bien con una utilidad máxima). Procedimiento: • Esta metodología es comparable a la de Vogel en cuanto a la aproximación de la solución óptima que ambos métodos generan, solo que este método es menos común que el anterior debido a que requiere mayor cantidad de trabajo. Consiste en calcular antes de cada asignación la cantidad Cij para cada casilla libre disponible, de acuerdo con la siguiente ecuación: • CIJ = ΑI + ΒJ - CIJ. • Donde: • Cij = coeficiente de la casilla del reglon i, columna j. Procedimiento: • Ai = costo mayor de las casillas del reglon i. Bj = costo mayor de las casillas de la columna j. Cij = costo de la casilla del reglon i , columna j. • De aquí se ira asignando aquella casilla que tenga el valor mas elevado de Cij. • El procedimiento por pasos es el siguiente: • Se calcula Cij para el total de las casillas vacías dela tabla de transporte. Procedimiento: • En la casilla que haya tenido el mayor valor de Cij. hacer la máxima asignación posible. Esto agotara la oferta del reglón y/o la demanda de la columna. En caso de haber varias casillas empatadas con el máximo valor de Cij, se selecciona al azar una de ellas. • Se repite el procedimiento para calcular Cij de las casillas que aun están vacías y asignar la que resulte con el valor máximo hasta terminar las asignaciones de la tabla completa. Ejemplo: • Una compañía tiene 3 fábricas ubicadas en A, B y C, las cuales proveen a los almacenes que están ubicados en D, E, F y G. La capacidad de producción de las fábricas son de 2500, 2200 y 2000 unidades mensuales respectivamente, mientras que las capacidades de los almacenes es de 1000, 1200 , 1100 y 3400 unidades respectivamente. El costo de envió de una unidad desde cada una de las fábricas a cada una de los almacenes se presenta en el siguiente cuadro (en $). Solución: Fabricas D E F G Oferta A 15 X 18 X 21 0 2500 B 10 1000 13 X 20 0 2200 1200 C 12 X 11 1200 21 0 2000 800 Demanda 1000 0 1200 0 1100 3400 6700
Fabricas D E F G Oferta A 15 X 18 X 21 X 0 2500 2500 0 B 10 1000 13 X 20 1100 0 100 2200 1200 1100 0 C 12 X 11 1200 21 X 0 800 2000 800 0 Demanda 1000 0 1200 0 1100 0 3400 100 0 6700
IC13 21 IC14 21 IC23 21 IC24 20
Costo Total = 1000(10)+ 1200((11) +1100(20)+2500(0)+100(0)+800(0) = $45200
Ejercicio: Distribuidor 1 2 3 Oferta 1 2 5 6 35 2 5 10 7 55 3 9 6 4 20 Demanda 30 45 35 110 Método de optimización de asignación Húngaro • El método húngaro es un método de optimización de problemas de asignación, conocido como tal gracias a que los primeros aportes al método clásico definitivo fueron de Dénes Konig y Jeno Egerváry dos matemáticos húngaros.
• Este método utiliza la propiedad de reducción de matrices para reducir la
matriz original de costo, hasta que los costos C i j asociados con la asignación óptima, sean cero y todos los otros costos sean no negativos. • El método húngaro es un algoritmo que se utiliza en problemas de asignación cuando se quiere minimizar el costo. Es decir, se usa para encontrar el costo mínimo al asignar varias personas a diversas actividades basadas en el menor costo. Se debe asignar cada actividad a una persona diferente. Procedimiento: • El método húngaro consta de cuatro pasos. Los primeros dos pasos se ejecutan una sola vez, mientras que los pasos 3 y 4 se repiten hasta encontrar una asignación óptima. • Se considera como dato de entrada a una matriz cuadrada del orden n por n, la cual debe contener solamente elementos no negativos. • Para un problema dado, si el número de filas de la matriz no es igual al número de columnas se debe agregar una fila ficticia o una columna ficticia, dependiendo del caso. Los costos de asignación para esas celdas ficticias siempre se asignan como cero. Procedimiento: • Para cada fila de la matriz se selecciona el elemento con el valor más bajo y se lo resta de cada elemento en esa fila. • De manera similar, se selecciona para cada columna el elemento con el valor más bajo y se lo resta de cada elemento en esa columna. • Se deben cubrir todos los ceros en la matriz resultante del paso 2 usando un número mínimo de líneas horizontales y verticales, ya sea por filas o columnas. • Si se requiere un total de n líneas para cubrir todos los ceros, siendo n igual al tamaño n por n de la matriz, se tendrá una asignación óptima entre los ceros y por tanto el algoritmo se detiene. Procedimiento: • De lo contrario, si se requieren menos de n líneas para cubrir todos los ceros en la matriz, se continúa. • Se selecciona el menor elemento de la matriz (llamado k) que no esté cubierto por una de las líneas realizadas en el paso anterior. • e resta el valor de k de todos los elementos que no están cubiertos por líneas. Posteriormente se suma el valor de k a todos los elementos que están cubiertos por la intersección de dos líneas. • Los elementos que están cubiertos por una sola línea se dejan tal como están. Después de realizar este paso, se regresa al paso anterior. Ejemplo: • Consideremos una empresa financiera donde existen cuatro agencias sucursales (A1, A2, A3, A4) que deben recibir depósitos por cuatro clientes (D1, D2, D3, D4). Se debe asignar un deposito por agencias. • La siguiente matriz muestra la distancia en km de depositar un cliente a una determinada agencia. El objetivo que se persigue es minimizar el recorrido. A1 A2 A3 A4 D1 230 200 210 240 D2 190 210 200 200 D3 200 180 240 220 D4 220 180 210 230 Solución: Menor de la fila:
A1 A2 A3 A4 D1 30 0 0 30 Se tachan la máxima cantidad de ceros con la mínima cantidad de líneas: D2 0 20 0 0 D3 20 0 50 30 El mínimo es 20 de los sin D4 40 0 20 40 tachar, se restan y a los interceptos se suman 20
