JOSE EDUARDO TORRES VEGA
Coronel EP ( R )
Diplomado en Ciencia y Tecnología
Ingeniero Electrónico CIP
Maestro en Administración
Experto en Logística
Diplomado en Seguridad y Salud Ocupacional
Docente Universitario a nivel pre grado y post grado
Consultor en Servicios de Telecomunicaciones
Estudios Teóricos de Radiaciones No Ionizantes
PRESENTADO POR:
FACULTAD DE INGENIERÍA INDUSTRIAL Y MECÁNICA
SEMANA 1
El problema de transporte. Solución básica inicial: Método de la Esquina Nor-oeste,
Método de costo mínimo, Método de Vogel. Desarrollo del modelo.
SEMANA 2
Solución óptima del problema de transporte. Prueba de Optimalidad: Método de
distribución Modificada (MODI). Desarrollo de problemas.
SEMANA 3
Casos especiales. Problema de maximización y degeneración. Desarrollo de problemas.
SEMANA 4
El problema de transbordo. Desarrollo de la solución. PRÁCTICA CALIFICADA 1
SEMANA 5
El problema de asignación. El Método Húngaro. Desarrollo de problemas.
SEMANA 6
Teoría de redes: Definiciones. Problema de flujo máximo: Algoritmo de Ford y Fulkerson.
Teorema de Mínimo corte-Máximo flujo. Desarrollo de problemas.
SEMANA 7
Problema del camino más corto. Algoritmo Dijkstra. Problema de conexión mínima.
Algoritmo de Krustral. Desarrollo de problemas. PRÁCTICA CALIFICADA 2
SEMANA 8
Problema de Flujo máximo a costo mínimo. Algoritmo de Busacker y Gowen. Desarrollo de
problemas.
ESCUELA DE INGENIERÍA INDUSTRIAL
SEMANA 9
Programación de proyectos. Desarrollo de PERT/CPM: conceptos, actividad y evento.
Presentación gráfica. Construcción de la red. problemas. PRÁCTICA CALIFICADA 3
SEMANA 10
Ruta crítica - Caso determinístico: Cálculo del tiempo más próximo y más lejano.
Tiempos de holgura, Ruta crítica. Control: Presentación del proceso PERT/CPM. Ruta
crítica - Caso probabilístico. Cálculos de sensibilidad. Diagrama de tiempo, Diagrama de
nivelación de recursos. Desarrollo de problemas.
SEMANA 11
Optimización de programas. Desarrollo de problemas.
SEMANA 12
Software MS Project. PRÁCTICA CALIFICADA 4
SEMANA 13
Programación dinámica: Conceptos, Elementos, Principio de Optimalidad.
SEMANA 14
Formulación de modelos con programación dinámica.
Problemas de Programación Dinámica: Ruta más corta, problema de reemplazo,
asignación de recursos, producción, inventarios. Desarrollo de problemas.
SEMANA 15
EXAMEN FINAL
ESCUELA DE INGENIERÍA INDUSTRIAL
SUMARIO
BIBLIOGRAFÍA
1. EL PROBLEMA DE LA ASIGNACIÓN
2. EL METODO HUNGARO
EL PROBLEMA DE LA ASIGNACIÓN
WINSTON, WAYNE Investigación de operaciones. Editorial: THOMSON.
HANDY TAHA. Investigación de operaciones. Ediciones Alfa Omega, (1991).
HILLER – LIEBERMAN. Introducción a la investigación de Operaciones. Mc Graw
Hill, (1990).
FACULTAD DE INGENIERÍA INDUSTRIAL Y MECÁNICA
ES UN TIPO ESPECIAL DE PROBLEMA DE PROGRAMACIÓN LINEAL EN EL QUE LOS ASIGNADOS SON RECURSOS DESTINADOS A LA REALIZACIÓN DE TAREAS
EJ.
EMPLEADOS A TRABAJO
MÁQUINAS A TAREAS
PERÍODOS A TAREAS
SUPOSICIONES DE UN PROBLEMA DE ASIGNACIÓN:
o El número de asignados es igual al número de tareas (se denota por n). (esto puede variar)
o Cada asignado se asigna exactamente a una tarea.
o Cada tarea debe realizarla exactamente un asignado.
o Existe un costo cij asociado con el asignado i (i=1,2,…,n).
o El objetivo es determinar cómo deben hacerse las asignaciones para minimizar los costos totales.
PROBLEMA DE ASIGNACIÓN
FACULTAD DE INGENIERÍA INDUSTRIAL Y MECÁNICA
REPRESENTACIÓN DE RED PARA EL PROBLEMA GENERAL
S1 [1]
S2 [1]
Sm [1]
D1 [1]
D2 [1]
Dm [1]
c11
c12
c1n
c21 c22
c2n
cm1 cm2
cmn
FACULTAD DE INGENIERÍA INDUSTRIAL Y MECÁNICA
FORMULACIÓN
Siendo un caso especial de P.L, su formulación contendrá:
I. Función Objetivo :MINIMIZACIÓN
II. Las restricciones se darán por filas y columnas, con la cantidad de 1 ( Sólo se podrá ASIGNAR un solo trabajador a un empleo, y un solo empleo se podrá ASIGNAR a un solo empleado).
III. Las variables son SIEMPRE POSITIVAS,
IV. Xij= El empleado a i al empleo j
FACULTAD DE INGENIERÍA INDUSTRIAL Y MECÁNICA
PLANTEAMIENTO MATEMÁTICO MODELO GENERAL
).y todapara binarias, (y para,0
,,...,2,1 para1
,,...,2,1 para1
a sujeta
min
1
1
1 1
jixjix
njx
mix
xcZ
ijij
m
j
ij
n
j
ij
ij
m
i
n
j
ij
FACULTAD DE INGENIERÍA INDUSTRIAL Y MECÁNICA
Caso Fowle Marketing Research
1 2 3
1. Terry 10 15 9
2. Carla 9 18 5
3. Roberto 6 14 3
Jefe de
Proyecto
Cliente
Tiempos estimados de terminación del
proyecto (días)
FACULTAD DE INGENIERÍA INDUSTRIAL Y MECÁNICA
J1 [1]
J2 [1]
J3 [1]
C1 [1]
[1]
[1]
C2
C3
18
3
Jefes de Proyecto
Nodos de Origen
Clientes
Nodos de Destino Asignaciones
Posibles
Arcos
FACULTAD DE INGENIERÍA INDUSTRIAL Y MECÁNICA
Variables de decisión
así es no si
cliente al proyecto de jefe el asigna se si
0
1 jixij
Sea Z tiempo total para concluir el trabajo
)4,3,2,1;3,2,1(0
1
1
1
1
1
1
3146518991510
332313
322212
312111
333231
232221
131211
333231232221131211
jix
xxx
xxx
xxx
xxx
xxx
xxx
xxxxxxxxxZ
ij
nesrestriccio las a Sujeta
Max
FACULTAD DE INGENIERÍA INDUSTRIAL Y MECÁNICA
1 2 3
1. Terry 0 1 0 1 = 1
2. Carla 0 0 1 1 = 1
3. Roberto 1 0 0 1 = 1
1 1 1
= = = Costo 26
1 1 1
Asignaciones
Jefe de
Proyecto
Cliente
FACULTAD DE INGENIERÍA INDUSTRIAL Y MECÁNICA
El entrenador de un equipo de natación debe asignar competidores para la prueba de 200 metros de relevo combinado que irán a las Olimpiadas Juveniles. Como muchos de sus mejores nadadores son rápidos en más de un estilo, no es fácil decidir qué nadador asignar cada uno de los cuatro estilos. Los cinco mejores nadadores y sus mejores tiempos (en segundos) en cada estilo son los siguientes:
Problema Natación (Asignación)
Carlos Cristy David Antony José
Dorso 37.7 32.9 33.8 37 35.4
Pecho 43.4 33.1 42.2 34.7 41.8
Mariposa 33.3 28.5 38.9 30.4 33.6
Libre 29.2 26.4 29.6 28.5 31.1
Tiempo de Nado
FACULTAD DE INGENIERÍA INDUSTRIAL Y MECÁNICA
Carlos Cristy David Antony José
Dorso 0 0 1 0 0 1 = 1
Pecho 0 0 0 1 0 1 = 1
Mariposa 0 1 0 0 0 1 = 1
Libre 1 0 0 0 0 1 = 1
1 1 1 1 0
<= <= <= <= <=
1 1 1 1 1
TIEMPO Min.
Tiempo de Nado
126.2
FACULTAD DE INGENIERÍA INDUSTRIAL Y MECÁNICA
Electrónica Ballston
Existen 5 diferentes proyectos eléctricos sobre 5 líneas de producción que necesitan ser inspeccionadas.
El tiempo para realizar una buena inspección de un área depende de la línea de producción y del área de inspección.
La gerencia desea asignar diferentes áreas de inspección a inspectores de productos tal que el tiempo total utilizado sea mínimo.
Datos
Tiempo de inspección en minutos para la línea de ensamble de cada área de inspección.
Area de InspecciónA B C D E
1 10 4 6 10 12 Linea 2 11 7 7 9 14Ensamble 3 13 8 12 14 15
4 14 16 13 17 175 19 17 11 20 19
FACULTAD DE INGENIERÍA INDUSTRIAL Y MECÁNICA
RED QUE REPRESENTA EL PROBLEMA
1
2
3
4
5
Línea de ensamble Área de Inspección
A
B
C
D
E
S1=1
S2=1
S3=1
S4=1
S5=1
D1=1
D2=1
D3=1
D4=1
D5=1
Supuestos restricciones
o El número de trabajadores es igual al número de empleos.
o Dado a que el problema esta balanceado, cada trabajador es asignado sólo una vez y cada trabajo tiene exactamente un solo trabajador.
o Para un problema desbalanceado se debe agregar un trabajador “ficticio” (en el caso de que existan más trabajos que trabajadores) o un empleo “ficticio” (en el caso de que existan más trabajadores que trabajos), quedando así el problema balanceado.
FACULTAD DE INGENIERÍA INDUSTRIAL Y MECÁNICA
ES UN MÉTODO DE OPTIMIZACIÓN DE PROBLEMAS DE ASIGNACIÓN. EL ALGORITMO ESTÁ DISEÑADO PARA LA RESOLUCIÓN DE PROBLEMAS DE MINIMIZACION ÚNICAMENTE; PARA SER EMPLEADO EN PROBLEMAS DE MAXIMIZACION REQUIERE DE UN PAZO ADICIONAL: 1. ALGORITMO HÚNGARO, PASO 1
TRABAJA EN UNA MATRIZ DE COSTOS (MATRIZ M*M), EN DONDE EL NÚMERO DE FILAS ES IGUAL AL NÚMERO DE COLUMNAS; UNA VEZ CONSTRUIDA ESTA SE DEBE ENCONTRAR EL ELEMENTO MÁS PEQUEÑO EN CADA FILA DE LA MATRIZ.
2. ALGORITMO HÚNGARO, PASO 2 UNA VEZ SE CUMPLE EL PROCEDIMIENTO ANTERIOR SE DEBE CONSTRUIR UNA NUEVA MATRIZ M*M, EN LA CUAL SE CONSIGNARÁN LOS VALORES RESULTANTES DE LA DIFERENCIA ENTRE CADA COSTO Y EL VALOR MÍNIMO DE LA FILA A LA CUAL CADA COSTO CORRESPONDE (VALOR MÍNIMO HALLADO EN EL PRIMER PASO).
3. ALGORITMO HÚNGARO, PASO 3 SE HALLA EL VALOR MÍNIMO DE CADA COLUMNA, CON LA DIFERENCIA QUE ESTE SE HALLA DE LA MATRIZ RESULTANTE EN EL SEGUNDO PASO, LUEGO SE CONSTRUIRÁ UNA NUEVA MATRIZ EN LA CUAL SE CONSIGNARÁN LOS VALORES RESULTANTES DE LA DIFERENCIA ENTRE CADA COSTO Y EL VALOR MÍNIMO DE LA COLUMNA A LA CUAL CADA COSTO CORRESPONDE (MATRIZ DE COSTOS REDUCIDOS).
EL MÉTODO HÚNGARO
FACULTAD DE INGENIERÍA INDUSTRIAL Y MECÁNICA
4. ALGORITMO HÚNGARO, PASO 4 SE DEBEN DE TRAZAR LÍNEAS HORIZONTALES O VERTICALES O AMBAS (ÚNICAMENTE DE ESOS TIPOS) CON EL OBJETIVO DE CUBRIR TODOS LOS CEROS DE LA MATRIZ DE COSTOS REDUCIDOS CON EL MENOR NÚMERO DE LÍNEAS POSIBLES, SI EL NÚMERO DE LINEAS ES IGUAL AL NÚMERO DE FILAS O COLUMNAS SE HA LOGRADO OBTENER LA SOLUCIÓN ÓPTIMA (LA MEJOR ASIGNACIÓN SEGÚN EL CONTEXTO DE OPTIMIZACIÓN), SI EL NÚMERO DE LÍNEAS ES INFERIOR AL NÚMERO DE FILAS O COLUMNAS SE DEBE DE PROCEDER CON EL PASO 5.
5. ALGORITMO HÚNGARO, PASO 5 ENCONTRAR EL MENOR ELEMENTO DE AQUELLOS VALORES QUE NO SE ENCUENTRAN CUBIERTOS POR LAS LINEAS DEL PASO 4 Y RESTARLO DEL RESTANTE DE ELEMENTOS QUE NO SE ENCUENTRAN CUBIERTOS POR LAS LÍNEAS; A CONTINUACIÓN ESTE MISMO VALOR SE SUMARÁ A LOS VALORES QUE SE ENCUENTREN EN LAS INTERSECCIONES DE LAS LINEAS HORIZONTALES Y VERTICALES, UNA VEZ FINALIZADO ESTE PASO SE DEBE VOLVER AL PASO 4.
FACULTAD DE INGENIERÍA INDUSTRIAL Y MECÁNICA
EL PROBLEMA LA COMPAÑÍA DE MANUFACTURA "JIMÉNEZ Y ASOCIADOS" DESEA REALIZAR UNA JORNADA DE MANTENIMIENTO PREVENTIVO A SUS TRES MÁQUINAS PRINCIPALES A, B Y C. EL TIEMPO QUE DEMANDA REALIZAR EL MANTENIMIENTO DE CADA MÁQUINA ES DE 1 DÍA, SIN EMBARGO LA JORNADA DE MANTENIMIENTO NO PUEDE DURAR MÁS DE UN DÍA, TENIENDO EN CUENTA QUE LA COMPAÑÍA CUENTA CON TRES PROVEEDORES DE SERVICIOS DE MANTENIMIENTO DEBE DE ASIGNARSE UN EQUIPO DE MANTENIMIENTO A CADA MÁQUINA PARA PODER CUMPLIR CON LA REALIZACIÓN DEL MANTENIMIENTO PREVENTIVO. TENIENDO EN CUENTA QUE SEGÚN EL GRADO DE ESPECIALIZACIÓN DE CADA EQUIPO PRESTADOR DE SERVICIOS DE MANTENIMIENTO EL COSTO DE LA TAREA VARÍA PARA CADA MÁQUINA EN PARTICULAR, DEBE DE ASIGNARSE EL EQUIPO CORRECTO A LA MÁQUINA INDICADA CON EL OBJETIVO DE MINIMIZAR EL COSTO TOTAL DE LA JORNADA. LOS COSTOS ASOCIADOS SE PUEDEN OBSERVAR EN LA SIGUIENTE TABLA:
FACULTAD DE INGENIERÍA INDUSTRIAL Y MECÁNICA
PASO 1 SE DETERMINA EL MENOR ELEMENTO DE CADA FILA
PASO 2 SE CONSTRUYE UNA NUEVA MATRIZ CON LAS DIFERENCIAS ENTRE LOS VALORES DE LA MATRIZ ORIGINAL Y EL MENOR ELEMENTO DE LA FILA A LA CUAL CORRESPONDE.
FACULTAD DE INGENIERÍA INDUSTRIAL Y MECÁNICA
PASO 3 EN LA MATRIZ CONSTRUIDA SE PROCEDE A EFECTUAR EL PASO 1 ESTA VEZ EN RELACIÓN A LAS COLUMNAS, ESCOGIENDO EL MENOR ELEMENTO DE CADA COLUMNA. SE CONSTRUYE UNA NUEVA MATRIZ CON LA DIFERENCIA ENTRE LOS VALORES DE LA MATRIZ 2 Y EL ELEMENTO MENOR DE LA COLUMNA A LA CUAL CORRESPONDE CADA VALOR.
FACULTAD DE INGENIERÍA INDUSTRIAL Y MECÁNICA
PASO 4 SE TRAZA LA MENOR CANTIDAD DE COMBINACIONES DE LÍNEAS HORIZONTALES Y VERTICALES CON EL OBJETIVO DE CUBRIR TODOS LOS CEROS DE LA MATRIZ DE COSTOS REDUCIDOS.
SE OBSERVA QUE EL MENOR NÚMERO DE LÍNEAS HORIZONTALES Y/O VERTICALES NECESARIAS PARA CUBRIR LOS CEROS DE LA MATRIZ DE COSTOS REDUCIDOS ES IGUAL A 2, POR ENDE AL SER MENOR QUE EL NÚMERO DE FILAS O COLUMNAS ES NECESARIO RECURRIR AL PASO 5.
PASO 5 EN ESTE PASO SELECCIONAMOS EL MENOR ELEMENTO DE LOS ELEMENTOS NO SUBRAYADOS.
FACULTAD DE INGENIERÍA INDUSTRIAL Y MECÁNICA
SE PROCEDE A RESTAR DE LOS ELEMENTOS NO SUBRAYADOS Y A ADICIONARSE A LOS ELEMENTOS UBICADOS EN LAS INTERSECCIONES DE LAS LÍNEAS (INTERSECCIÓN EN (3)).
FACULTAD DE INGENIERÍA INDUSTRIAL Y MECÁNICA
EFECTUANDO EL PASO 4.
SE OBSERVA LA NECESIDAD DE TRAZAR TRES LÍNEAS (LA MISMA CANTIDAD DE FILAS O COLUMNAS DE LA MATRIZ) PARA CUBRIR LOS CEROS ENTONCES SE DETERMINA QUE SE HA LLEGADO A LAS ASIGNACIONES ÓPTIMAS.
FACULTAD DE INGENIERÍA INDUSTRIAL Y MECÁNICA
POR ENDE LA ASIGNACIÓN QUE REPRESENTA EL MENOR COSTO PARA LA JORNADA DE MANTENIMIENTO PREVENTIVO DETERMINA QUE: EL EQUIPO 1 REALICE EL MANTENIMIENTO DE LA
MÁQUINA 1 EL EQUIPO 2 REALICE EL MANTENIMIENTO DE LA
MÁQUINA 3 EL EQUIPO 3 REALICE EL MANTENIMIENTO DE LA
MÁQUINA 2 JORNADA QUE TENDRÁ UN COSTO TOTAL DE 17 UNIDADES MONETARIAS.
FACULTAD DE INGENIERÍA INDUSTRIAL Y MECÁNICA
Problema:
El profesor Michell ha terminado 4 capítulos de su libro y esta pensando en pedir ayuda para terminarlo. El ha elegido a 4 secretarias que podrían tipear cada uno de los capítulos. El costo asociado refleja la velocidad de la secretaria y la exactitud con la que realiza el trabajo. Además los capítulos difieren en la cantidad de hojas y en la complejidad. ¿Qué puede hacer el profesor si conoce la siguiente tabla:
Capítulos
Secretaría 13 14 15 16
Juana 96 99 105 108
María 116 109 107 96
Jackeline 120 102 113 111
Edith 114 105 118 115
FACULTAD DE INGENIERÍA INDUSTRIAL Y MECÁNICA
Restricciones del Método
* Solo problemas de minimización.
* Número de personas a asignar m es igual al número de lugares m.
* Todas las asignaciones son posibles
* Una asignación por persona y una persona por asignación
Matriz de Costos Capítulos
Secretaría 13 14 15 16
Juana 96 99 105 108
María 116 109 107 96
Jackeline 120 102 113 111
Edith 11 105 118 115
FACULTAD DE INGENIERÍA INDUSTRIAL Y MECÁNICA
Restar el Menor valor de cada fila Capítulos
Secretaría 13 14 15 16
Juana 0 3 9 12
María 20 13 11 0
Jackeline 18 0 11 9
Edith 9 0 13 10
Restar el menor valor de cada columna en la matriz anterior
Capítulos
Secretaría 13 14 15 16
Juana 0 3 0 12
María 20 13 2 0
Jackeline 18 0 2 9
Edith 9 0 4 10
FACULTAD DE INGENIERÍA INDUSTRIAL Y MECÁNICA
Trazar el mínimo número de líneas que cubran los ceros de la matriz obtenida en el punto anterior.
Capítulos
Secretaría 13 14 15 16
Juana 0 3 0 12
María 20 13 2 0
Jackeline 18 0 2 9
Edith 9 0 4 10
Si el número de líneas es igual al número de filas se ha determinado la solución óptima, sino es así, se tiene que identificar el menor valor no rayado y restarlo a los demás números no rayados y sumar esta diferencia en las intersecciones.
Pare este caso corresponde al valor 2 FACULTAD DE INGENIERÍA INDUSTRIAL Y MECÁNICA
Capítulos
Secretaría 13 14 15 16
Juana 0 5 0 14
María 18 13 0 0
Jackeline 16 0 0 9
Edith 7 0 2 10
Las asignaciones corresponde a los valores donde existen 0 Juana Cap. 13
María Cap. 16
Jackeline Cap. 15
Edith Cap. 14
*Costo Asignación: 96 + 96 +113 +105 =410
FACULTAD DE INGENIERÍA INDUSTRIAL Y MECÁNICA
Ejemplo:
Un padre desea ASIGNAR a sus tres hijos tres tareas para este fin de semana, para ello ha ideado la siguiente tabla para DETERMINAR quien de ellos realizará cada trabajo, al MINIMO COSTO TOTAL
Qué tarea realizará cada hijo
Cuál es el costo total de dichos trabajos
HIJO/ TAREAS
PODAR LAVAR (AUTO)
PINTAR (CASA)
MARIO 20 15 30
JULIO 28 22 50
JANET 28 25 55
HIJO / TAREAS
PODAR LAVAR PINTAR OFERTA
MARIO 20X11 15X12 30X13 1
JULIO 28X21 22X22 50X23 1
JANET 28X31 25X32 55X33 1
DEMANDA 1 1 1 3
FACULTAD DE INGENIERÍA INDUSTRIAL Y MECÁNICA
I. MIN(CT)= 20X11+15X12+30X13+28X21+22X22+50X23+28X31+ 25X32 + 55X33.
II. RESTRICIONES
X11 +X12+X13 <=1
X21+X22+X23 <=|
X31+X32+X33 <=1
III. POR LA DEMANDA :
X11 +X21 +X31 = 1 X12+X22+X32 =1 X13 +X23 +X33 =1
IV. CNN
Vij >=0, i =1,2,3 J = 1,2,3,
FACULTAD DE INGENIERÍA INDUSTRIAL Y MECÁNICA