Asignación y transporte
Christian LunaDocumentos de Investigación2 de Diciembre de 2024
6.757 Palabras (28 Páginas)113 Visitas
[pic 1][pic 2]
Unidad 3: asignación y transporte
[pic 3]
[pic 4]
Instituto Tecnológico Superior de Huauchinango[pic 5]
31/10/2024
INSTITUTO TECNOLÓGICO SUPERIOR DE HUAUCHINANGO
MATERIA: investigación de operaciones
CATEDRATICO: MTRo. Villa barrera victor
CARRERA: LIC. INGENIERÍA EN ADMINISTRACIÓN
4° SEMESTRE
ALUMNO:
LUNA MORALES CHRISTIAN
Contenido
DEFINICIÓN DEL PROBLEMA DE TRANSPORTE 4
DEFINICIÓN DEL PROBLEMA DE ASIGNACIÓN 4
MÉTODO DE ESQUINA NOROESTE 5
PASOS MÉTODO DE ESQUINA NOROESTE 7
EJEMPLO DEL MÉTODO ESQUINA NOROESTE 7
MÉTODO DE COSTO MÍNIMO 11
CARACTERÍSTICAS DEL MÉTODO DEL COSTO MÍNIMO 11
PASOS DEL MÉTODO DEL COSTO MÍNIMO 12
APLICACIONES 13
VENTAJAS Y DESVENTAJAS DEL MÉTODO DEL COSTO MÍNIMO 13
VENTAJAS 13
DESVENTAJAS 14
EJEMPLO DEL MÉTODO DEL COSTO MÍNIMO 15
EXPLICACIÓN DEL MÉTODO 16
MÉTODO DE APROXIMACIÓN DE VOGEL 17
PASOS DEL MÉTODO DE APROXIMACIÓN DE VOGEL 18
VENTAJAS DEL MÉTODO DE APROXIMACIÓN DE VOGEL 19
DESVENTAJAS DEL MÉTODO DE APROXIMACIÓN DE VOGEL 19
COMPARACIÓN CON OTROS MÉTODOS DE TRANSPORTE 20
APLICACIONES DEL MÉTODO DE APROXIMACIÓN DE VOGEL 21
EJEMPLO PRÁCTICO DEL MÉTODO DE APROXIMACIÓN DE VOGEL 21
CÁLCULO DE PENALIZACIONES 22
SELECCIÓN DE LA MAYOR PENALIZACIÓN 22
ASIGNACIÓN DE UNIDADES 22
REPETICIÓN DEL PROCESO 23
MÉTODO DE ASIGNACIÓN 23
CARACTERÍSTICAS DEL MÉTODO DE ASIGNACIÓN 23
EJEMPLO DEL MÉTODO HÚNGARO DE ASIGNACIÓN 24
BIBLIOGRAFÍA 28
DEFINICIÓN DEL PROBLEMA DE TRANSPORTE
El problema de transporte es un tipo de problema de optimización lineal cuyo objetivo es determinar el modo más rentable de transportar bienes o recursos de varios puntos de origen a varios destinos. Cada origen tiene una cierta capacidad de oferta, y cada destino tiene una demanda específica.
El objetivo principal del problema de transporte es minimizar el costo total de envío, cumpliendo con la oferta y demanda de cada origen y destino, respectivamente. Los elementos clave son:
- Oferta: Cantidad de productos disponible en cada origen.
- Demanda: Cantidad de productos requerida en cada destino.
- Costos de transporte: Costo de enviar una unidad de producto desde un origen específico a un destino específico.
Este problema se representa generalmente en una tabla donde las filas indican los orígenes, las columnas los destinos y cada celda contiene el costo unitario de transporte desde un origen a un destino.
DEFINICIÓN DEL PROBLEMA DE ASIGNACIÓN
El problema de asignación es un caso especial del problema de transporte en el que tanto las ofertas como las demandas son iguales a uno. En este caso, se trata de asignar un conjunto de recursos (como trabajadores, máquinas o vehículos) a un conjunto de tareas o actividades de forma que el costo total de la asignación se minimice o la eficiencia se maximice.
El problema de asignación tiene características especiales:
- Se asegura que cada recurso sea asignado a una y solo una tarea.
- Las soluciones suelen buscar minimizar el costo total de asignación o maximizar la productividad.
Para resolver el problema de asignación, se suele utilizar el Método Húngaro, que es una técnica matemática eficiente que encuentra la solución óptima en un número finito de pasos, evitando un proceso iterativo de prueba y error.
El problema de asignación es un problema fundamental de optimización combinatoria. En su forma más general, el problema es el siguiente:
- La instancia del problema tiene una serie de agentes y varias tareas. Cualquier agente puede ser asignado para realizar cualquier tarea, incurriendo en algunos Costo que puede variar dependiendo de la asignación de agente-tarea. Es necesario realizar tantas tareas como sea posible asignando a la mayoría de un agente a cada tarea y en la mayoría de una tarea a cada agente, de tal manera que el costo total de la asignación se minimiza.
Alternativamente, describiendo el problema usando la teoría de grafos:
- El problema de asignación consiste en encontrar, en un gráfico bipartito ponderado, una combinación de un tamaño dado, en el que la suma de pesos de los bordes es mínima.
Si los números de agentes y tareas son iguales, entonces el problema se denomina asignación equilibrada. De lo contrario, se denomina asignación desequilibrada. Si el costo total de la asignación de todas las tareas es igual a la suma de los costos de cada agente (o la suma de los costos de cada tarea, que es lo mismo en este caso), entonces el problema se llama asignación lineal. Comúnmente, cuando se habla del problema de asignación sin ninguna calificación adicional, entonces se quiere decir problema de asignación balanceada lineal.
MÉTODO DE ESQUINA NOROESTE
El Método de Esquina Noroeste es una técnica inicial para obtener una solución factible en el problema de transporte. La estrategia comienza desde la esquina superior izquierda (noroeste) de la tabla de costos y procede asignando la mayor cantidad posible a cada celda de acuerdo con las
restricciones de oferta y demanda. El procedimiento es el siguiente:
- Inicio: Comenzar en la celda de la esquina superior izquierda.
- Asignación de recursos: Asignar la cantidad máxima posible a la celda (es decir, el mínimo entre la oferta del origen y la demanda del destino).
- Actualizar la oferta y demanda: Reducir la oferta y la demanda en función de la cantidad asignada.
- Movimiento: Si la demanda de un destino se cumple, avanzar a la celda siguiente en la columna; si la oferta de un origen se cumple, avanzar a la siguiente celda en la fila.
- Repetir: Continuar el proceso hasta que todas las demandas y ofertas sean satisfechas.
Este método es rápido y sencillo, pero no garantiza una solución óptima ya que no toma en cuenta los costos de transporte en cada paso.
El Método de la Esquina Noroeste (o esquina superior izquierda) es una heurística que se aplica a una estructura especial de problemas de Programación Lineal llamada Modelo de Transporte, la cual permite asegurar que exista una solución básica factible inicial (no artificial). Otros métodos para la obtención de una solución básica de inicio son el Método de Costo Mínimo y Método de Aproximación de Vogel. En general, el Método de Vogel produce la mejor solución básica de inicio y el de la Esquina Noroeste la peor, sin embargo, el Método de la Esquina Noroeste implica el mínimo de cálculos.
El Método de la Esquina Noroeste comienza en la celda (ruta) correspondiente a la esquina noroeste, o superior izquierda, de la tabla (variable [pic 6]). A continuación una descripción de los pasos:
PASOS MÉTODO DE ESQUINA NOROESTE
- Paso 1: Asignar todo lo posible a la celda seleccionada y ajustar las cantidades asociadas de oferta y demanda restando la cantidad asignada.
- Paso 2: Salir de la fila o la columna cuando se alcance oferta o demanda cero, y tacharlo, para indicar que no se pueden hacer más asignaciones a esa fila o columna. Si una fila y una columna dan cero al mismo tiempo, tachar sólo uno (la fila o columna) y dejar una oferta (demanda) cero en la fila (columna) que no se tachó.
- Paso 3: Si queda exactamente una fila o columna sin tachar, detenerse. En caso contrario, avanzar a la celda de la derecha si se acaba de tachar una columna, o a la de abajo si se tachó un reglón. Seguir con el Paso 1.
EJEMPLO DEL MÉTODO ESQUINA NOROESTE
Para ilustrar la aplicación del Método de la Esquina Noroeste consideremos el siguiente problema balanceado de transporte que considera 3 silos productos (oferta) que satisfacen las necesidades de 4 molinos (demanda). El algoritmo de transporte se basa en la hipótesis que el modelo está balanceado, es decir, que la demanda total es igual a la oferta total (si el modelo no está balanceado siempre se podrá aumentar con una fuente ficticia o un destino ficticio para restaurar el equilibrio o balance).
...