Portafolio #3

 

¡Hola, bienvenid@..!

En esta entrada del blog (Investigación de Operaciones) hablaré básicamente acerca del modelo de transporte, el modelo de asignación y (PERT/CPM)

Modelo de transporte

¿Qué es?

El método de 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 ben cada uno de los orígenes, y es necesario que sea llevado a cabo uno de los n destinos posibles en una cantidad demandada dj.

La formulación de un problema de transporte, siguiendo un modelo de programación lineal será:

Donde: 

• — Z: función de costes totales que se desea minimizar.

• — cij: coste de transportar una unidad de producto desde el origen i (i=1, 2,..., m) hasta el destino j (j=1, 2,..., n).

• — xij: cantidad transportada de producto desde el origen i hasta el destino j.

• — bi: cantidad disponible de producto en cada origen i.

• — dj: cantidad demandada de producto en cada destino j.
• 
  

Los problemas de transporte pueden ser resueltos mediante el Algoritmo del Simplex. Sin embargo, dadas las peculiaridades de este problema han aparecido otros algoritmos específicos que facilitan el proceso.

Ejemplo: 

Primero se realiza la tabla que comprende el almacén, el cliente/costo, y la disponibilidad

Luego se realizan las tablas de origen(fuente) y destino(demanda)

Después se define la tabla en la cual se va a realizar la operación de transporte

Lo siguiente sería plantear la función objetivo la cual se halla de la suma producto entre la tabla #1 y la tabla que está en blanco.

Luego se procede a plantear las restricciones, las cuales constan de lo siguiente: las restricciones de la oferta salen de la suma de los valores que están horizontalmente por (fila) y las restricciones de la demanda salen de la suma de los valores que están verticalmente por (columna).

Para resolver el ejercicio se hace uso de solver, primero se debe seleccionar la celda que contiene la función objetivo, después se da click a Min(minimizar costos), luego se seleccionan las celdas que comprenden la matriz a operar, luego se ingresan las restricciones, el método de resolución es (Simplex LP) y por último damos en resolver. De la siguiente manera

Resultados: 

Modelo de asignación

¿Qué es?

El modelo de asignación es un tipo especial de problema de programación lineal en el que los asignados son recursos que se destinan a la realización de tareas. Por ejemplo, los asignados pueden ser empleados a quienes se tiene que dar trabajo. La asignación de personas a trabajos es una aplicación común del problema de asignación. Sin embargo, los asignados no tienen que ser personas. También pueden ser máquinas, vehículos o plantas, o incluso periodos a los que se asignan tareas. “La mejor persona para el puesto” es una buena descripción del modelo de asignación.

El objetivo del modelo es determinar la asignación óptima (de costo mínimo) de trabajadores a puestos.

Para que se ajuste a la definición de un problema de asignación, es necesario que este tipo de aplicaciones se formule de manera tal que se cumplan los siguientes supuestos:

1. El número de asignados es igual al número de tareas. (Este número se denota por n.)
2. A cada asignado se le asigna sólo una tarea.
3. Cada tarea debe realizarla sólo un asignado.
4. Existe un costo cij asociado con el asignado i (i 5 1, 2, . . . , n) que realiza la tarea j ( j 1, 2, . . . , n).
5. El objetivo es determinar cómo deben hacerse las n asignaciones para minimizar los costos totales.

Se puede resolver el modelo de asignación en forma directa como modelo normal de transporte. Sin embargo, el hecho de que todas las ofertas y las demandas son iguales a 1, condujo al desarrollo de un algoritmo sencillo de solución llamado método húngaro.

Método 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 König y Jenő Egerváry dos matemáticos húngaros. El algoritmo tal como se detallará a continuación está diseñado para la resolución de problemas de minimización únicamente.

Es importante resaltar que el método húngaro trabaja en una matriz de costos n*m (en este caso conocida como matriz m*m, dado que el número de filas es igual al número de columnas n = m).

Ejemplo: 

Dar click aquí para ver dos ejercicios planteados con el método de asignación

Modelo PERT/CPM

El método CPM o Ruta Crítica (equivalente a la sigla en inglés Critical Path Method) es frecuentemente utilizado en el desarrollo y control de proyectos. El objetivo principal es determinar la duración de un proyecto, entendiendo éste como una secuencia de actividades relacionadas entre si, donde cada una de las actividades tiene una duración estimada. En este sentido el principal supuesto de CPM  es que las actividades y sus tiempos de duración son conocidos, es decir, no existe incertidumbre. Este supuesto simplificador hace que esta metodología sea fácil de utilizar y en la medida que se quiera ver el impacto de la incertidumbre en la duración de un proyecto, se puede utilizar un método complementario como lo es PERT. Una ruta es una trayectoria desde el inicio hasta el final de un proyecto. En este sentido, la longitud de la ruta crítica es igual trayectoria más grande del proyecto. Cabe destacar que la duración de un proyecto es igual a la ruta crítica.

La técnica de revisión y evaluación de programas (PERT) y el método de ruta crítica (CPM) han demostrado ser extremadamente valiosos para planear, programar y controlar varios proyectos:

1. Investigación y desarrollo de nuevos productos y procesos.

2. Construcción de plantas, edificios y carreteras.

3. Mantenimiento de equipo grande y complejo.

4. Diseño e instalación de sistemas nuevos.

Los procedimientos PERT/CPM pueden ayudar a responder las siguientes preguntas:

1. ¿Cuál es el tiempo total para completar el proyecto?

2. ¿Cuáles son las fechas de inicio y terminación programadas de cada actividad específica?

3. ¿Cuáles actividades son "críticas" y deben ser completadas exactamente como se programaron para mantener el proyecto dentro del programa?

4. ¿Qué tanto se pueden demorar las actividades "no críticas" antes de que incrementen el tiempo total de terminación del proyecto?

Ejemplo: 

Dar click para ver ejemplo

En este sentido el principal supuesto de CPM es que las actividades y sus tiempos de duración son conocidos, es decir, no existe incertidumbre. Este supuesto simplificador hace que esta metodología sea fácil de utilizar y en la medida que se quiera ver el impacto de la incertidumbre en la duración de un proyecto, se puede utilizar un método complementario como lo es PERT. Una ruta es una trayectoria desde el inicio hasta el final de un proyecto. En este sentido, la longitud de la ruta crítica es igual a la la trayectoria más grande del proyecto. Cabe destacar que la duración de un proyecto es igual a la ruta crítica.