problemas flujo maximo

2
Prof. Luis Ulfe PROBLEMA 1.- Flujo máximo El concejo académico de la Universidad URP esta buscando una representación entre seis estudiantes que están afiliados a cuatro sociedades de honor. La representación del consejo académico incluye tres áreas: Matemáticas, Artes e Ingeniería. Cuando mucho dos estudiantes de cada área pueden estar en el consejo. La siguiente tabla muestra la membresía de los seis estudiantes de las cuatro sociedades de honor. Los estudiantes que poseen habilidades en las áreas de matemáticas, artes e ingeniería, se muestran en la siguiente tabla: Sociedad Estudiantes afiliados Área Estudiantes con habilidades 1 1,2,3 Matemáticas 1,2,4 2 1,3,5 Artes 3,4 3 3,4,5 Ingeniería 4,5,6 4 1,2,4,6 Un estudiante que posee habilidades en más de un área se debe asignar exclusivamente a un área. ¿Es posible que las cuatro sociedades de honor estén representadas en el consejo? PROBLEMA 2: Flujo Máximo Una compañía de servicios de pintado a domicilio tiene tres grupos de trabajadores a disposición para los meses de Abril y Mayo. Para estos dos meses se han firmado cinco contratos. Cada trabajo debe empezarse en ó después de varias fechas a continuación indicadas y debe completarse antes ó en las fechas acordadas para ejecutar cada uno de los contratos. Los términos de cada contrato son los siguientes: Contrato Fecha de inicio Fecha de finalización Tiempo requerido (sem) A Abril 1 Abril 28 2 B Abril 14 Mayo 12 4 C Abril 1 Mayo 26 7 D Abril 21 Mayo 26 3 E Abril 1 Mayo 26 6 La labor correspondiente a cada trabajo no necesita ejecutarse en forma continua de principio a fin. Sin embargo, resulta práctico que cada grupo trabaje en un sólo contrato durante una semana dada. Además, más de un grupo no puede trabajar en el mismo contrato durante la misma semana. Se requiere saber si es posible acabar todos los contratos antes ó en sus fechas de finalización. a) Implemente la red que representa el problema. b) Implemente el modelo de programación lineal.

Upload: slash

Post on 26-Sep-2015

25 views

Category:

Documents


0 download

DESCRIPTION

io2

TRANSCRIPT

  • Prof. Luis Ulfe

    PROBLEMA 1.- Flujo mximo El concejo acadmico de la Universidad URP esta buscando una representacin entre seis estudiantes que estn afiliados a cuatro sociedades de honor. La representacin del consejo acadmico incluye tres reas: Matemticas, Artes e Ingeniera. Cuando mucho dos estudiantes de cada rea pueden estar en el consejo.

    La siguiente tabla muestra la membresa de los seis estudiantes de las cuatro sociedades de honor.

    Los estudiantes que poseen habilidades en las reas de matemticas, artes e ingeniera, se muestran en la siguiente tabla:

    Sociedad Estudiantes

    afiliados

    rea Estudiantes con

    habilidades

    1 1,2,3 Matemticas 1,2,4

    2 1,3,5 Artes 3,4

    3 3,4,5 Ingeniera 4,5,6

    4 1,2,4,6

    Un estudiante que posee habilidades en ms de un rea se debe asignar exclusivamente a un rea. Es posible que las cuatro sociedades de honor estn representadas en el consejo?

    PROBLEMA 2: Flujo Mximo

    Una compaa de servicios de pintado a domicilio tiene tres grupos de trabajadores a disposicin para los meses de Abril y Mayo. Para estos dos meses se han firmado cinco contratos. Cada trabajo debe empezarse en despus de varias fechas a continuacin indicadas y debe completarse antes en las fechas acordadas para ejecutar cada uno de los contratos. Los trminos de cada contrato son los siguientes:

    Contrato Fecha de inicio Fecha de finalizacin Tiempo requerido (sem)

    A Abril 1 Abril 28 2 B Abril 14 Mayo 12 4

    C Abril 1 Mayo 26 7

    D Abril 21 Mayo 26 3

    E Abril 1 Mayo 26 6

    La labor correspondiente a cada trabajo no necesita ejecutarse en forma continua de principio a fin. Sin embargo, resulta prctico que cada grupo trabaje en un slo contrato durante una semana dada. Adems, ms de un grupo no puede trabajar en el mismo contrato durante la misma semana. Se requiere saber si es posible acabar todos los contratos antes en sus fechas de finalizacin.

    a) Implemente la red que representa el problema. b) Implemente el modelo de programacin lineal.

  • Prof. Luis Ulfe

    Problema 3: Flujo Mximo Considrese el proceso de produccin que se muestra abajo, el cual indica las varias rutas que puede seguir un producto en una planta, en su camino al ensamblado. El nmero en cada cuadro representa el lmite superior sobre los artculos por hora que se pueden procesar en cada estacin.

    a) Represente este problema como uno de flujo de redes, especificando nodos, arcos y capacidades.

    b) Cul es el nmero mximo de partes por hora que puede manejar la planta? c) Cules operaciones se debe tratar de mejorar?

    Problema 4: Cuatro fbricas se dedican a la produccin de cuatro tipos de juguetes. La siguiente tabla enumera los juguetes que cada fbrica puede producir.

    Fbrica Mezcla de produccin de juguetes

    1 1, 2, 3

    2 2, 3

    3 1, 4

    4 3, 4

    Todos los juguetes requieren la misma mano de obra y el mismo material por unidad. Las capacidades diarias de las cuatro fbricas son 250, 180, 300, y 100 juguetes respectivamente. Las demandas diarias para los cuatro juguetes son 200, 150, 350, y 100 unidades, respectivamente. Determine los programas de produccin de las fbricas que podrn satisfacer mejor las demandas de los cuatro juguetes.

    Problema 5:

    Durante los siguientes cuatro meses, una empresa desarrolladora de software debe completar 3 proyectos. El proyecto 1 debe completarse dentro de los tres primeros meses y requiere 8 meses hombre de trabajo. El proyecto 2 se debe completar en cuatro meses y requiere 10 meses hombre de trabajo. El proyecto 3 debe completarse al final de los dos meses y requiere 12 meses hombre de trabajo. Cada mes estn disponibles 8 trabajadores. Durante un mes, no ms de 6 trabajadores pueden desempear una sola tarea. a) Formule un problema de flujo mximo (usando grafos) que permita determinar si

    los tres proyectos se pueden completar a tiempo, hallar la solucin. (4 puntos) b) Formule el modelo de programacin lineal asociado. (2 puntos)

    6

    9

    4

    7

    4

    8

    7

    Fin

    Inicio

    1

    2