Organización

Organización

2. Conceptos
3. Organización del sector de la construcción
4. Gráficos y diagramas aplicados
5. Investigación operativa
6. Programación lineal
7. Teoría de los grafos
8. Ordenación de grafos
9. Programación por grafos, generalidades
10. Cálculo de tiempos en PERT y CPM
11. Holguras en PERT y CPM
12. Cálculo de tiempos y holguras en ROY
13. Probabilidad de los plazos en PERT
14. Nivelación de recursos
15. Relación Costo-Tiempo
16. Organización general de obras
17. Documentos de la organización
18. Seguridad e higiene (seguridad y salud laboral)
19. Estudio y plan de seguridad
20. Etapas de la obra
21. Programación general de obras
22. Estudio del tiempo
23. Estudio de las actividades
24. La empresa constructora
25. Control general
26. Control técnico y programación
27. Control económico y financiero
28. Control administrativo
29. Formularios de control

TEMA I: GENERALIDADES

LECCIÓN PRIMERA

INTRODUCCION.-

1.1. ANTECEDENTES HISTÓRICOS DE LA ORGANIZACIÓN.

La organización existe desde siempre y considerada como ciencia desde finales del siglo pasado y principios del actual.

XIII (1240) WALTER OF HENLEY

Vigilancia.

Selección – Adiestramiento: de los trabajadores.

Rendimiento mínimo: trabajo a desarrollar en un periodo de tiempo.

Recursos apropiados.

Estos puntos venían expresados en una carta que un padre le dejo a su hijo para que cuidara la finca.

XV (1452 – 1519) LEONARDO DA VINCI

Primer testimonio escrito sobre medición del trabajo.

La medición la hizo mediante la descomposición del trabajo en partes.

XVIII (1760) PERRONET

Aparece por primera vez descrito un ciclo completo de producción.

Ciclo completo de fabricación de alfileres.

XIX (1800) FUNDICION DE BOULTON WAT

Decoración (del centro de trabajo).

Obsequios navideños (como incentivo al trabajador).

Viviendas (por empresa al servicio del trabajador cerca del centro de trabajo).

XIX (1832) CHARLES BABBAGE

División del trabajo en fases.

Bonificaciones, se maneja el concepto de la incentivación por primera vez. (Actualmente el tope de incentivación rentable "tiempo/ calidad" es de 1/3, aunque esta cifra es orientativa. Esta cifra sale de la demostración de que un trabajador incentivado incrementa su rendimiento en 1/3 aproximadamente.

Cronometraje, se usan por primera vez aparatos de medida del tiempo. (A principios del siglo XX, se grabo por primera vez a un trabajador en su puesto de trabajo para corregir sus defectos).

Hoy en día esta prohibido.

DURANTE EL SIGLO XIX

Salarios e incentivos.

Participación de beneficios (ventajas e inconvenientes: esto no da siempre el resultado buscado).

XIX – XX (1856 – 1915) FREDERICK WINSLOW TAYLOR

"Padre de la organización científica del trabajo".

Comenzó a estudiar rendimientos y tiempos.

Distintos métodos de trabajo.

Estudio de las dimensiones de la pala de carga de minera y otros materiales.

XX FRANK BUNKER GILBRETH Y LILLIAN MOLLER

Son contemporáneos de Taylor.

Aportación de criterios psicológicos al estudio del trabajo.

El estudio del movimiento lo realizaron descomponiéndolo en movimientos elementales, ayudándose de filmaciones e incorporando el cronómetro al campo de visión.

1.2. OBJETIVOS DE UNA ORGANIZACIÓN.-

Podemos analizarlo entorno a la productividad y al nivel de vida.

Nivel de vida: cambia con el tiempo y es un índice que mide el grado de bienestar de una empresa, sociedad, …

PRODUCTIVIDAD – NIVEL DE VIDA

NIVEL DE VIDA

PRODUCCION

PRODUCTIVIDAD = ——————–

RECURSOS

Al aumentar la productividad conseguimos ser más competitivos en el mercado con lo que conseguimos aumentar el nivel de vida.

"Para aumentar la productividad tenemos conseguir mayor producción con menos recursos".

1.3. PRINCIPIOS BASICOS DE UNA ORGANIZACIÓN.-

ESTUDIO DEL TIEMPO

METODOS DE TRABAJO.

CONTROL.

DIVISION DE TRABAJO (especialización: cada uno trabaja en lo que esta más capacitado).

ESTIMULACION (incentivos).

DISMINUCION DE RESPONSABILIDADES (como consecuencia de la especialización).

LECCIÓN SEGUNDA

CONCEPTOS.-

2.1. DEFINICIÓN DE PLANIFICACIÓN, ORGANIZACIÓN, PROGRAMACIÓN, EJECUCIÓN, CONTROL Y GESTIÓN DE OBRAS.

Planificación: "Es el hecho de hacer el plan o proyecto de una acción".

Planificar es el conjunto de organización, planificación, ejecución y gestión.

Organización: "Es la acción de establecer o reformar una cosa, sujetando a reglas el número, orden, armonía y dependencia de las partes que la componen o han de componerla".

Programación: "Es la acción de coordinar en el tiempo y en el espacio las distintas partes que intervienen y son necesarias para la realización de la obra, fijando la interdependencia entre ellos".

Ejecución: "La acción de poner por obra una cosa".

Es la acción de materializar lo que estamos programando.

Control: "Inspección, fiscalización, intervención".

Gestión: "Es la acción y efecto de administrar".

2.2. TIPOS DE ORGANIZACIÓN.

Todas las empresas tienen un organigrama de funcionamiento distinto, hay tantos tipos de organización como empresas.

ORGANIZACIÓN REGLAMENTARIA

Reglamentos rígidos y preestablecidos. Es una organización que obedece a unos reglamentos rígidos establecidos de antemano de forma que esos reglamentos condicionan la forma de actuación. Tiene una ventaja importante que es la de dar la misma respuesta ante problemas iguales planteados en sitios distintos. Su inconveniente es que es un tipo de organización lento, torpe, difícil de adaptarse a situaciones nuevas, etc. Ejemplo: el Estado.

ORGANIZACIÓN LINEAL

Línea perfectamente establecida y clara en la transmisión de ordenes, actuaciones, obligaciones y responsabilidades. Ventajas: la rapidez, las ordenes se ejecutan con muchas celeridad. Inconvenientes: en los altos mandos de esa línea va a haber personas con un alto grado de responsabilidad de forma individual, teniendo que ser muy especializadas. Ejemplo: el ejercito.

Dentro de la obra la organización es lineal.

ORGANIZACIÓN FUNCIONAL

Aparición de asesores o consejeros. Es una organización similar a la lineal pero para adaptarse a situaciones no tan graves ni tan límites. La modifica buscando grupos de asesoramiento en los altos cargos. La empresa constructora va a tener algo de los tres tipos de organización, variando las proporciones de un tipo o de otro.

2.3. VENTAJAS Y PROBLEMAS QUE PRESENTA UNA ORGANIZACIÓN DE OBRAS.

VENTAJAS:

Económicas, temporales, de orden, ….

PROBLEMAS:

Unidad de producción: Cada unidad es diferente. La unidad a producir es siempre distinta, no hay dos obras iguales.

Emplazamiento: Diferente. No se hacen dos obras en el mismo sitio.

Consideraciones climáticas: Trabajo intemperie.

Formación del personal: Personal con escasa cualificación profesional.

Proyecto: Incompleto y sujeto a continuos cambios. El proyecto no suele tener un nivel de definición suficiente a la hora de comenzar la obra y se encuentra sujeto a continuos cambios.

Conclusión

LECCIÓN TERCERA

ORGANIZACIÓN DEL SECTOR DE LA CONSTRUCCIÓN.-

3.1. AGENTES QUE INTERVIENEN EN LA CONSTRUCCIÓN.

Promotor: Concibe, pone en marcha todo el proceso. Es la persona o empresa que tiene una necesidad constructiva y tiene capacidad económica para realizarla.

Proyectista: Técnico competente, resuelve aspectos técnicos y de diseño.

Contratista: Contrata la ejecución de la obra.

Constructor: Ejecución material del proyecto.

Dirección facultativa: Asesores técnicos.

Arquitecto/s + Aparejador/es (en el caso de edificación).

Normalmente el contratista y el constructor son la misma persona.

En el año 1986 salió un decreto que obligaba a realizar un estudio de seguridad en obras cuyo presupuesto fuese igual o superior a los cien millones de pesetas. En el año 1990 otro decreto definía la competencia de este estudio de seguridad asignándosela a un aparejador o a un arquitecto técnico y dicho técnico se añadirá a la dirección facultativa de la obra con competencia es la seguridad de la obra y capacidad para la paralización de la obra.

Un individuo que posea las dos titulaciones de arquitecto y aparejador o arquitecto técnico no podrá ejercer la dirección facultativa de ambas titulaciones en la misma obra.

El arquitecto puede ser promotor, proyectista, director de obra, contratista y constructor de la misma obra mientras el aparejador puede ser todo menos proyectista (aunque puede realizar proyectos de reforma siempre y cuando no toque elementos estructurales).

ORGANIGRAMA GENERAL

 Para ver el gráfico seleccione la opción "Descargar" del menú superior

 POSIBLE ORGANIGRAMA , OBRAS OFICIALES

  Para ver el gráfico seleccione la opción "Descargar" del menú superior

3.2. INTERVENCIÓN DEL ARQUITECTO TÉCNICO EN EL PROCESO CONSTRUCTIVO.

Promotor

Proyectista: "puede actuar como colaborador en la realización del proyecto pero nunca firmándolo o desarrollándolo por solitario, aunque puede desarrollar proyectos en los que no halla que modificar ni tocar elementos estructurales".

Dirección facultativa

Contratista

Constructor

3.3. CARACTERÍSTICAS DEL SECTOR.

LECCIÓN CUARTA

GRÁFICOS Y DIAGRAMAS APLICADOS.-

4.1. CONCEPTOS GENERALES SOBRE GRÁFICOS.

Es un gran medio de comunicación, basado en el poder y rapidez de captación del ojo.

Es conveniente utilizar un método gráfico que sea capaz de transmitir una gran información, en lugar de darlo todo por escrito ya que es más engorroso.

Condiciones para que cumpla lo mejor posible su función de instrumento de información:

4.1.1. INFORMACION debe ser de clasificarse, relacionarse, …

Se debe de poder representar gráficamente.

4.1.2. CENTRAR LA ATENCIÓN en la información a trasmitir.

4.1.3. CLARIDAD Y SENCILLEZ sin acumular información.

4.1.4. COMBINACIÓN DE GRÁFICOS cuidadosa para no deformar o falsear la información.

4.1.5. LEYENDA mínima, necesaria, clara y simple.

4.1.6. ILUSTRATIVO del texto a que acompaña.

4.1.7. ADECUADO elección apropiada del gráfico.

4.2. GRÁFICOS SIMPLES.

4.2.1. ORGANIGRAMA

  Para ver el gráfico seleccione la opción "Descargar" del menú superior

El organigrama relaciona elementos de un conjunto como puede ser la estructura de organización de una empresa.

Siempre puede establecer una gerarquización cuando se emplea en una estructura empresarial.

4.2.2. PLANES DE CLASIFICACIÓN

GRÁFICOS

  Para ver el gráfico seleccione la opción "Descargar" del menú superior

SIMPLES ESPECIALES ESPECIFICOS

  Para ver el gráfico seleccione la opción "Descargar" del menú superior

Los planes de clasificación sirven para establecer la clasificación de un conjunto.

4.2.3. GRÁFICO SAGITAL

  Para ver el gráfico seleccione la opción "Descargar" del menú superior

Los gráficos sagitales relacionan elementos de dos conjuntos.

4.2.4. HISTOGRAMA

 Para ver el gráfico seleccione la opción "Descargar" del menú superior

El histograma es un gráfico de coordenadas cartesianas y la relación que existe entre los elementos de los dos conjuntos viene dada por el área del rectángulo.

4.2.5. CUADRO DE DOBLE ENTRADA

El cuadro de doble entrada es una matriz que define un conjunto por filas y otro por columnas.

4.2.6. GRÁFICOS LINEALES

En gráficas lineales se establece la relación entre los elementos de ascisas con las ordenadas por la longitud de la barra.

4.2.7. GRÁFICAS DE SUPERFICIE

Las gráficas de superficie son aquellas en las que la superficie o área en cuestión representa la totalidad del conjunto y luego esta la dividimos en los porcentajes correspondientes a cada fracción. Es aconsejable indicar el porcentaje que le pertenece a cada fracción.

TIPOLOGIA :

4.2.7.1. RECTANGULAR un rectángulo representa el conjunto y se divide a este en porcentaje.

4.2.7.2. SEMICIRCULAR el área del semicírculo representa el 100 % del conjunto y se divide en porcentajes.

4.2.7.3. CIRCULAR el área del circulo representa el 100 % del conjunto y se divide en porcentajes.

4.2.8. GRÁFICAS DE VOLUMEN

   Para ver el gráfico seleccione la opción "Descargar" del menú superior

  En gráficas de volumen su relación viene dada por el volumen de la figura geométrica.

4.2.9. SERIES TEMPORALES

En las series temporales una de las variables evoluciona o varía en función del tiempo, pueden ser o no representados en ejes cartesianos.

4.3. GRÁFICAS ESPECIALES.

4.3.1. GRÁFICAS LOGARÍTMICAS / SEMILOGARÍTMICAS

Las gráficas logarítmicas / semilogarítmicas son gráficos cartesianos que relacionan elementos de dos conjuntos a través de sus ejes, los dos conjuntos crecen de forma exponencial y se representan sobre los ejes en la escala logarítmica de los números naturales.

Cuanto mayor es un número menor es su logaritmo por lo tanto podemos representar números muy altos.

Los gráficos semilogarítmicos utilizan en un eje una escala normal y sobre el otro eje la serie logarítmica de los números naturales.

4.3.2. GRÁFICOS MULTIDIMENSIONALES

El gráfico multidimensional es un gráfico que es capaz de relacionar muchas variables de un mismo conjunto, son interesantes hasta dieciséis variables.

4.3.3. GRÁFICO POLAR

El gráfico polar es un gráfico en el que mediante la distancia al centro y el ángulo que forma a un radio fijo nos relaciona los dos conjuntos, es similar al de las series temporales.

Se emplean cuando las variables evolucionan a través del tiempo de una forma acumulable al origen.

 Para ver el gráfico seleccione la opción "Descargar" del menú superior

4.3.4. SOCIOGRAMA

El sociograma es un cuadro de doble entrada con una aplicación muy especifica.

En las filas se representan aspectos o características sociológicas y en las columnas se representa la escala de valores o baremo.

NIVEL ÓPTIMO *

NIVEL CANDIDATO 1 *

NIVEL CANDIDATO 2 *

NIVEL CANDIDATO 3 *

4.4. GRÁFICOS ESPECIFICOS EN CONSTRUCCIÓN.

En construcción se pueden emplear todos los gráficos expuestos en los apartados anteriores aunque los de este apartado 4.4. son más específicos.

4.4.1. DIAGRAMA DE GANTT

Es un diagrama de tipo lineal en el que las barras se dibujan en horizontal indicándose las actividades de un proyecto, los tiempos de comienzo de cada uno de ellos y su duración.

No es ningún método de programación, solo transmite la información que con otros métodos hemos realizado.

El diagrama de Gantt sirve para llevar un control temporal de la obra.

Para ver el gráfico seleccione la opción ¨Bajar trabajo¨ del menú superior

4.4.2. DIAGRAMA DE ETAPAS

Es una variante del diagrama de Gantt, en este diagrama de etapas para cada actividad se indican varias barras correspondientes a las etapas en que se haya dividido la actividad o la obra, se usa poco ya que es difícil dividir la obra en etapas claramente diferenciadas.

4.4.3. DIAGRAMA DE ESCALONES

Es un diagrama en el que existen dos dimensiones, indicando en horizontal el tiempo y en vertical los costos de cada una de las actividades.

Habitualmente se dibuja de abajo a arriba para trabajar con la zona positiva del eje Y.

Forma de medir el tiempo:

1. Tiempo aritmético:

1.1. Día: 1º, 2º, …

1.2. Semana: 1ª, 2ª, … 1 semana ® 5 días.

2. Tiempo calendario:

2.1 Días: día del calendario (18 de Marzo).

2.2. Semana: máximo de 5 días (dura menos si hay fiestas).

2.3. Meses

LECCIÓN QUINTA

INVESTIGACIÓN OPERATIVA.-

5.1. INTRODUCCIÓN.

Nace y se desarrolla en el contexto militar (Segunda Guerra Mundial), y luego pasa a aplicarse en la industria. Tiene gran aplicación en política, medicina, cualquier rama de las ciencias, etc.

La investigación operativa consiste fundamentalmente en la aplicación de métodos y técnicas matemáticas a la hora de tomar decisiones, podrá resolver cualquier problema cuyos objetivos y condicionantes puedan traducirse a expresiones matemáticas.

Antes de la investigación operativa la decisión se tomaba de forma intuitiva y por una sola persona, ahora también se toma individualmente pero hay asesoramiento por equipos multidisciplinares para tomar la decisión.

5.2. MODELOS MATEMÁTICOS DE LA INVESTIGACIÓN OPERATIVA.

La investigación operativa utiliza tres modelos:

5.2.1. Determinísticos: Parten de datos establecidos y fijados de antemano y en consecuencia nos conducen a resultados ciertos.

5.2.2. Probabilísticos: Parten de datos estadísticos y nos conducen a resultados probables.

5.2.3. Simulación: Reproducen o simulan mediante maquetas, programas de ordenador, etc. el objeto a estudiar y al someterlo a las acciones a las que va a estar expuesto vemos cuales son sus respuestas y en función de esto modificamos aquello.

La simulación se puede determinar de forma física o matemáticamente.

5.3. CAMPOS DE ACTUACIÓN DE LA INVESTIGACIÓN OPERATIVA.

Desde el punto de vista que nos interesa actúa en dos frentes:

5.3.1. Proyecto:

5.3.1.1. Diseño del proyecto.

5.3.1.2. Vida probable de los componentes.

5.3.1.3. Normalización o estandarización de elementos.

5.3.2. Producción:

5.3.2.1. Productos a fabricar, tipos y cantidad.

5.3.2.2. Planificación y programación.

5.3.2.3. Disposición en planta.

5.3.2.4. Mantenimiento.

5.4. MÉTODOS UTILIZADOS EN LA ORGANIZACIÓN Y PROGRAMACIÓN DE OBRAS.

5.4.1. PROGRAMACIÓN MATEMÁTICA:

5.4.1.1. Programación lineal:

5.4.1.1.1. Gráfico.

5.4.1.1.2. Matricial.

5.4.1.1.3. Simplex.

5.4.1.2. Problema de asignación.

5.4.1.3. Problema del transporte.

5.4.1.4. Programación no lineal.

5.4.1.5. Otras programaciones.

5.4.2. TEORÍA DE LOS GRAFOS:

5.4.2.1. CPM.

5.4.2.2. PERT.

5.4.2.3. PERT – CPM / COSTOS.

5.4.2.4. ROY.

LECCIÓN SEXTA

PROGRAMACIÓN LINEAL.-

6.1. PROGRAMACIÓN LINEAL.

Es una parte de la investigación operativa que la podremos aplicar cuando el problema que tratamos se puede traducir a expresiones matemáticas de tipo lineal y que las limitaciones o restricciones que tenga el sistema productivo se pueda también traducir en expresiones matemáticas de tipo lineal.

Un problema de programación lineal tendrá la siguiente forma:

Función Objetivo: Es una expresión matemática lineal que representa el objetivo del problema. Es la expresión que tendremos que maximizar o minimizar.

Función Objetivo:

(Max. ó Min.) Z = c1x1 + c2x2 + … + cnxn

Ecuaciones o Inecuaciones de Restricción: Expresiones matemáticas, ecuaciones o inecuaciones de tipo lineal que representan las limitaciones del problema.

a11x1 + a12x2 + … + a1nxn £ b1

a21x1 + a22x2 + … + a2nxn ³ b2

a31x1 + a32x2 + … + a3nxn £ b3

………………………………

am1x1 + am2x2 + … + amnxn = bm

Aunque el problema no lo diga llevara las restricciones:

x1³ 0; x2 ³ 0; … ; xn ³ 0

Las variables no tomaran valores negativos.

Conceptos propios de la programación Lineal:

Solución Posible: Es cualquier conjunto de valores de la variable que satisface el sistema de ecuaciones de la restricción.

Solución Posible Básica: Es aquella solución posible en la que ninguna variable toma valores negativos.

Solución Básica Posible Degenerada: Solución básica posible en la que al menos una variable toma el valor cero.

Solución Óptima: Es aquella solución básica posible que optimiza a la función objetivo.

6.2. MÉTODO GRÁFICO.

Solo resuelve problemas de dos variables.

El punto A maximiza la función objetivo y el punto B la minimiza.

Para ver el gráfico seleccione la opción "Descargar" del menú superior

El método gráfico va a utilizar el plano y un sistema de ejes cartesianos sobre el que se representan cada una de las ecuaciones de restricción. Para ello llevaremos cada inecuación al caso límite de ser una igualdad, cualquier punto de esa recta satisface a esa ecuación. Como sabemos a que punto de la recta satisfacer si para ³ ó £ , para ello comprobamos con un punto conocido el (0,0) y si satisface para £ los puntos estarán de la recta hacia el origen y hacemos lo mismo con todas las restricciones quedándonos un polígono de manera que cualquier punto de ese polígono cumple todas las restricciones y además es básica.

Cualquier punto que este fuera del polígono no puede ser solución del problema ya que incumple alguna restricción o todas.

Ahora vamos a ver cual es la solución óptima, ningún punto del polígono interior puede ser la solución óptima ya que siempre encontraremos otro que maximice o minimice mas la función. La solución óptima del problema se obtiene de las líneas perimetrales del polígono, pero existe siempre otro punto que maximice o minimice más la función, por lo tanto la solución óptima del problema se tiene que encontrar en un vértice.

Para obtener cual es el vértice que de la solución óptima igualaremos a cero la función objetivo y se le hace pasar por el origen, trazando una paralela a la recta así obtenida y llevándola hasta el último vértice ese es el punto que optimiza la función y el punto más cercano es el que minimiza la función.

Casos Particulares:

En este primer caso la solución óptima serán todos los puntos comprendidos entre A y B, pertenecientes a la recta r.

Aunque nos quedaríamos con A ó B para maximizar y con el (0,0) para minimizar la función objetivo.

Para ver el gráfico seleccione la opción "Descargar" del menú superior

 En este caso en el que no nos cierra el polígono, solo consideramos los vértices A, B, y C y nos quedaríamos con el último por el que pase la recta que se forma con la función objetivo para maximizar y el primero para minimizar.

Para ver el gráfico seleccione la opción "Descargar" del menú superior

En este próximo caso particular el punto (0,0) minimiza la función y como esto no es lógico nos indica que falta alguna restricción.

Para ver el gráfico seleccione la opción "Descargar" del menú superior

No existe polígono de posibles soluciones luego el problema no tiene solución.

Para ver el gráfico seleccione la opción "Descargar" del menú superior

6.3. PREPARACIÓN PARA LOS METODOS MATRICIAL Y SIMPLEX.

Este método no tiene limitación en cuanto al número de variables. Hace lo mismo que el método gráfico pero en Rn.

La forma del problema sería la siguiente:

Función objetivo:

(Max. ó Min.) Z = c1x1 + c2x2 + … + cnxn

Restricciones:

a11x1 + a12x2 + … + a1nxn £ b1

a21x1 + a22x2 + … + a2nxn ³ b2

a31x1 + a32x2 + … + a3nxn £ b3

………………………………

am1x1 + am2x2 + … + amnxn = bm

Procedimiento:

Primer paso variables de holgura, son variables ficticias que se introducen en las restricciones para convertirlo en un sistema de ecuaciones. Pasan a la función objetivo con coeficiente cero.

(Max. ó Min.) Z = c1x1 + c2x2 + … + cnxn + 0xn+1 + 0xn+2 + … + 0xn+m

a11x1 + a12x2 + … + a1nxn + xn+1 = b1

a21x1 + a22x2 + … + a2nxn – xn+2 = b2

a31x1 + a32x2 + … + a3nxn – xn+3 = b3

………………………………

am1x1 + am2x2 + … + amnxn + xn+m = bm

Segundo paso variables de penalización, son variables ficticias que se introducen en el sistema de ecuaciones de restricción en todas aquellas ecuaciones en las que no exista una variable única (que este en esa ecuación y no en ninguna otra) y que además tenga el mismo signo que el termino independiente.

Las variables de penalización pasan a la función objetivo con coeficiente – M si se trata de maximizar y con + M en el caso de que se este minimizando, siendo M un valor que tiende a infinito pero sin llegar a serlo.

(Max. ó Min.) Z = c1x1 + c2x2 + … + cnxn + 0xn+1 + … + 0xn+m ± Mxn+m+1 ± … ± M x n+2m

a11x1 + a12x2 + … + a1nxn + xn+1 + xn+m+1 = b1 xn+m+1 = 0

a21x1 + a22x2 + … + a2nxn – xn+2 + xn+m+2 = b2 en nuestro caso

a31x1 + a32x2 + … + a3nxn – xn+3 + xn+m+3 = b3

………………………………

am1x1 + am2x2 + … + amnxn + xn+m + x n+2m = bm xn+m = 0

en nuestro caso

6.4. PROBLEMA DE ASIGNACIÓN.

Es un problema de programación lineal que tiene una manera especial de resolverse.

Consiste en buscar la relación entre dos conjuntos de forma que el rendimiento de dicha relación sea el optimo posible.

En nuestro caso uno de los conjuntos serán personas y el otro de los conjuntos serán puestos de trabajo, maquinas, etc. y habremos de buscar la asignación en la que cada persona de el rendimiento optimo.

x (x1, x2, …, xn) 1er conjunto

y (y1, y2, …, yn) 2º conjunto

El método de asignación se basa en establecer una asignación de tipo biyectivo o biunivoco entre ambos conjuntos.

aij es el rendimiento que cada uno de los elementos del 1er conjunto tiene con cada uno de los elementos del 2º conjunto y vamos a formar una matriz de rendimientos.

y1 y2 y3 … y1n a11 ® rendimiento que obtiene el 1er elemento

x1 a11 a12 a13 … a1n del 1er conjunto al relacionarse con el 1er

x2 a21 a22 a23 … a2n elemento del 2º conjunto

x3 a31 a32 a33 … a3n

……………………….

Xn an1 an2 an3 … ann

 La relación que buscamos lo que hará será maximizar o minimizar la asignación.

En el segundo conjunto no tiene porque ser igual que el primero ya que podemos tener más candidatos que puestos y en eses caso creamos un puesto de trabajo ficticio (para que la matriz siga siendo cuadrada) y asignar un rendimiento igual y constante para todas las personas en ese puesto de trabajo y el más desfavorable posible.

y1 y2 y3 … y1n yn+1

x1 a11 a12 a13 … a1n 0

x2 a21 a22 a23 … a2n 0

x3 a31 a32 a33 … a3n 0

…………………………………………..

xn an1 an2 an3 … ann0

xn+1 a(n+1)1 a(n+1)2 a(n+1)3 … a(n+1)n0

  yn+1 ® no existe en realidad, es ficticio y representa el stock. La columna yn+1 = 0 si se esta maximizando en el caso de estar minimizando se le pone a todos los elementos de la columna yn+1 el mismo valor pero ligeramente superior al mayor valor que haya en la matriz de rendimientos.

Teorema fundamental de la asignación: Si a todos los elementos de una fila o de una columna de una matriz de rendimientos se le suma o se le resta una cantidad constante la asignación optima no varia.

Algoritmo Húngaro: (Anexo II del librillo de practicas), el algoritmo Húngaro esta destinado para minimizar si tenemos que maximizar tendremos previamente que darle la vuelta a la matriz restándole el mayor elemento de toda la matriz a cada uno de los elementos de la misma de manera que el elemento que era más pequeño pasara a ser el más grande y a la inversa.

El Algoritmo Húngaro se debe a D. König y E. E Egervóry.

Cuando hay que pasar de maximizar a minimizar en lugar de operar con el mayor de toda la matriz podemos ir tomando el mayor de cada fila o columna e ir restándole todos los elementos de esa fila o columna con lo cual conseguiremos de camino obtener por lo menos un cero como mínimo en cada fila o columna. Si en alguna columna no hubiera ceros le quitamos el mayor a la columna.

6.5. PROBLEMA DEL TRANSPORTE

Es un problema similar al de la asignación con la diferencia de que no se asignan elementos de un conjunto a otro sino cantidades de producto que normalmente vienen representadas por costos de transporte.

A diferencia del problema de asignación la matriz no tiene por que ser cuadrada, pueden existir mas destinos que orígenes, también pueden no coincidir las cantidades que se fabrican o almacenan con los pedidos que se reciben pudiendo estos ser menores o iguales, en ese caso deberá crearse un mercado ficticio que absorba esa producción en exceso.

En la matriz de rendimientos los elementos aij indicaran en este caso los costos o relación directa, nos aparecerán unos elementos Cj que indicaran las cantidades a almacenar o fabricar, otros elementos Bj que indicaran las necesidades de los destinos y otros elementos Zij que indicaran las cantidades enviadas de cada origen a cada destino.

y1 y2 y3 … ym

x1 a11z11 a12z12 a13z13 … a1mz1m c1

x2 a21z21 a22z22 a23z23 … a2nz2m c2

x3 a31z31 a32z32 a33z33 … a3nz3m c3

…………………………………………

Xn an1zn1 an2zn2 an3zn3 … annznm cn

b1 b2 b3 bm

  Si S cj ³ S bj tiene solución el sistema

Si S cj < S bj no tiene solución el sistema.

EJEMPLOS DE ASIGNACIÓN

1) min. 1 2 3 1 2 3 1 2 3 SOLUCIÓN

A 3 2 1 A 2 1 0 A 2 0 0 A ® 2

B 4 5 7 B 0 1 3 B 0 0 3 B ® 1

C 6 5 2 C 4 3 0 C 4 2 0 C ® 3

MARCO TACHO

2) min. 1 2 3 1 2 3 1 2 3

A 3 7 1 A 2 6 0 A 2 5 0 *

B 4 5 7 B 0 1 3 B 0 0 3

C 6 5 2 C 4 3 0 C 4 2 0 *

*

1 2 3 SOLUCIÓN.1:

A 0 3 0 A ® 1 = 3

B 0 0 5 B ® 2 = 5

C 2 0 0 C ® 3 = 2

10 =

1 2 3 SOLUCIÓN.2:

A 0 3 0 A ® 3 = 1

B 0 0 5 B ® 1 = 4

C 2 0 0 C ® 2 = 5

10

EJEMPLO DE TRANSPORTE

MIN. 1 2 3

A 25 28 17 10 CAPACIDADES = S C = 30

B 20 29 15 12

C 22 27 15 8

10 11 9

NECESIDADES = S N = 30 

1 2 3 1 2 3

A 8 11 0 10 A 3 010 0 10, 0

B 5 14 0 12 B 010 3 0112, 2, 1*

C 7 12 0 8 C 2 1 08 8, 0 *

10 11 9 10 11 9

0 1 1

0

* *

SOLUCIONES:

1 2 3 A – 2 – 10

A 4 010 1 10, 0 B – 1 – 10

B 010 2 0212, 2, 0 B – 3 – 2

C 2 01 07 8, 7, 0 C – 2 – 1

10 11 9 C – 3 – 7

0 1 7

0 0

  TEMA II: SISTEMAS DE PROGRAMACIÓN POR GRAFOS

LECCIÓN SEPTIMA

TEORÍA DE LOS GRAFOS.-

7.1. INTRODUCCIÓN.

Es la base de todos los sistemas de programación que estudiaremos: PERT, CPM y ROY.

7.2. CONCEPTOS Y DEFINICIONES.

Grafo: Es el conjunto de elementos entre los que existen ligaduras orientadas.

Suponemos un conjunto x = {A, B, C, D, E, F} y una relación G = (x, T) de manera que:

TA = {B, C, D}

TB = {A}

TC = {B, D, F}

TD = {D, E}

TE = {0}

TF = {0}

Lo representamos mediante un diagrama sagital.

Para ver el gráfico seleccione la opción "Descargar" del menú superior

Cuadro de doble entrada.

Definiciones:

Vértice: Elemento de un conjunto que constituye un grafo.

Arco: Par de elementos entre los que existe relación teniendo en cuenta la orientación, es decir que exista relación orientada: (A, B); (A, C); (B, A); …

Camino: Es una sucesión de arcos adyacentes que nos permiten pasar de un vértice a otro: (A, C, D, E).

Circuito: Es un camino en el que el vértice inicial y final coinciden: (A, C, B, A); (A, B, A).

Bucle: Es un arco en el que el vértice origen y final coinciden: (D)

Arista: Relación entre dos vértices sin atender a la orientación: (C, A); (A, C).

Cadena: Sucesión de aristas adyacentes: (F, C, B, A).

Longitud de un camino o circuito: Se mide por el número de arcos que constituyen el camino o circuito.

Grafo conexo: Entre todo par de vértices podemos establecer al menos una cadena.

A Grafo no conexo ya que E no se relaciona

con nadie y nadie se relaciona con él.

Para ver el gráfico seleccione la opción "Descargar" del menú superior

Grafo fuertemente conexo: Es aquel que entre cualquier par de vértices podemos establecer al menos un camino.

Grafo sin circuitos: Es aquel que no tiene circuitos.

A nosotros nos interesan los grafos sin circuitos y conexos.

7.3. RELACIÓN DE ORDEN ESTRICTO EN UN GRAFO CONEXO SIN CIRCUITOS.

Si un grafo es conexo y sin circuitos se puede establecer una relación de orden si cumple las siguientes propiedades:

1. Antisimétrica: A se relaciona con B entonces B no puede preceder a A.

A y B son vértices del grafo

A < B Þ B no puede preceder a A.

< no significa menor sino sentido, dirección.

2. Transitiva: A precede a B y B precede a C entonces A precede a C.

A < B

A < C

B < C

LECCIÓN OCTAVA

ORDENACIÓN DE GRAFOS.-

8.1. INTRODUCCIÓN.

Necesidad de ordenar.

8.2. DESCOMPOSICIÓN DE UN GRAFO CONEXO SIN CIRCUITOS EN NIVELES.

Establecimiento convencional de niveles

Situar los vértices de manera que ningún vértice de un determinado nivel precede a un vértice situado en un nivel anterior. (A su izquierda) Entre los vértices de un mismo nivel no existirá relación.

Pasos a seguir:

1. Sumamos por filas el número de veces que cada vértice precede a otro.

2. Vértices situados en el último nivel son aquellos que no preceden nunca a nadie.

3. Restamos a cada elemento el número de veces que precedía a los situados en el último nivel.

4. Así sucesivamente hasta que todos los vértices tengan asignado un nivel.

Ejemplo:

V IV III II I

Nota.- En este tipo de ejercicios no es conveniente hacer diagramas de tipo sagital ya que resultarían muy confusos de interpretar.

8.3. CONSIDERACIONES PARA EL DIBUJO DE GRAFOS.

1. Las precedencias serán inmediatas.

2. La longitud del arco no representa nada.

3. Evitar longitudes de arcos desproporcionadas.

4. Evitar el trazado de arcos curvos.

5. Evitar el cruce entre arcos.

6. Evitar ángulos pequeños entre arcos.

7. Dos arcos distintos no podrán tener el mismo vértice inicial y final.