Asignación y transporte

[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:

1. Inicio: Comenzar en la celda de la esquina superior izquierda.

1. 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).

1. Actualizar la oferta y demanda: Reducir la oferta y la demanda en función de la cantidad asignada.

1. 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.

1. 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).

...