programacion lineal

11
Investigación de Operaciones ____________________________________________________________________________________ Diana Cobos 8 Formulación de un Modelo de Programación Lineal Para facilitar el planteamiento del modelo matemático general de la PL considere el siguiente problema: La planta HBB fabrica 4 productos que requieren para su elaboración: materia prima de la cual hay una disponibilidad diaria de 180 libras, espacio de almacenamiento del cual se dispone de 230 pies cúbicos y un tiempo de producción de 8 horas/día. Para elaborar una unidad de cada uno de los productos se necesitan los siguientes insumos: Producto Materia prima lbs/unidad Espacio pies 3 /unidad Tasa producción unidades/hora Utilidades $/unidad. 1 2 2 15 5 2 2 2.5 30 6.5 3 1.5 2 10 5 4 1 1.5 15 5.5 La gerencia desea determinar cuántas unidades de cada producto deben fabricarse para maximizar el beneficio. Solución A partir de esta descripción cualitativa del problema se va a convertir en una forma matemática que se pueda resolver, este proceso se llama formulación del problema y tiene los siguientes pasos con sus características claves. I) Identificación de las variables de decisión. Identificar las variables de decisión y obtener sus valores proporciona la solución del problema. Como los valores de estos elementos son desconocidos se les da un símbolo. La elección de estas variables no es única y no existen reglas fijas, sin embargo se pueden formular algunas preguntas que son útiles en la identificación de un conjunto adecuado de variables de decisión.

Upload: lucxy-arrieta

Post on 13-Nov-2015

14 views

Category:

Documents


2 download

DESCRIPTION

metodo de programacion lineal

TRANSCRIPT

  • Investigacin de Operaciones

    ____________________________________________________________________________________

    Diana Cobos 8

    Formulacin de un Modelo de Programacin Lineal

    Para facilitar el planteamiento del modelo matemtico general de la PL considere

    el siguiente problema:

    La planta HBB fabrica 4 productos que requieren para su elaboracin: materia

    prima de la cual hay una disponibilidad diaria de 180 libras, espacio de

    almacenamiento del cual se dispone de 230 pies cbicos y un tiempo de

    produccin de 8 horas/da. Para elaborar una unidad de cada uno de los productos

    se necesitan los siguientes insumos:

    Producto Materia

    prima

    lbs/unidad

    Espacio

    pies3/unidad

    Tasa produccin

    unidades/hora

    Utilidades

    $/unidad.

    1 2 2 15 5

    2 2 2.5 30 6.5

    3 1.5 2 10 5

    4 1 1.5 15 5.5

    La gerencia desea determinar cuntas unidades de cada producto deben fabricarse

    para maximizar el beneficio.

    Solucin

    A partir de esta descripcin cualitativa del problema se va a convertir en una forma

    matemtica que se pueda resolver, este proceso se llama formulacin del

    problema y tiene los siguientes pasos con sus caractersticas claves.

    I) Identificacin de las variables de decisin.

    Identificar las variables de decisin y obtener sus valores proporciona la solucin

    del problema. Como los valores de estos elementos son desconocidos se les da un

    smbolo. La eleccin de estas variables no es nica y no existen reglas fijas, sin

    embargo se pueden formular algunas preguntas que son tiles en la identificacin

    de un conjunto adecuado de variables de decisin.

  • Investigacin de Operaciones

    ____________________________________________________________________________________

    Diana Cobos 9

    CARACTERSTICAS CLAVES

    Qu elementos afectan los costos y/o ganancias como objetivo global?

    Qu elementos se pueden elegir y/o controlar?

    Qu decisiones se tienen que tomar?

    Qu valores posibles constituyen una solucin para el problema?

    La respuesta a estas preguntas es fabricar cuatro tipos de productos simbolizados

    por:

    X1 = cantidad de unidades a producir del producto 1

    X2 = cantidad de unidades a producir del producto 2

    X3 = cantidad de unidades a producir del producto 3

    X4 = cantidad de unidades a producir del producto 4

    II) Identificacin de los datos del problema

    La finalidad de resolver un problema es proporcionar los valores reales para las

    variables de decisin. Para esto se requiere determinar los recursos disponibles.

    Para nuestro ejemplo:

    Cantidad de materia prima disponible (180 lbs/da)

    Cantidad de espacio disponible (230 pies3)

    Tiempo de produccin disponible (8 hrs/da).

    CARACTERSTICA CLAVE.

    La necesidad de determinar los datos del problema para lograr el objetivo al

    desarrollar el problema y verificar si se necesita informacin adicional para

    determinar las variables de decisin.

  • Investigacin de Operaciones

    ____________________________________________________________________________________

    Diana Cobos 10

    III) Identificacin de la funcin objetivo

    En esta parte se pretende expresar el objetivo organizacional en forma matemtica

    usando las variables de decisin y los datos conocidos. Se puede considerar que

    cada una de las variables de decisin tiene una funcin especifica dentro del

    contexto del objetivo general (optimizar), con el fin de obtener un nico valor. Para

    el caso:

    Maximizar las utilidades a partir de los aportes o beneficios de cada unidad

    fabricada ( por ejemplo, $5 el producto 1 (X1)), y totalizar todos los aportes para

    las respuestas de las variables de decisin.

    La funcin objetivo ser entonces:

    Maximizar Z = 5X1 + 6.5X2 + 5X3 + 5.5X4

    CARACTERSTICA CLAVE

    La funcin objetivo depende de:

    El enunciado del objetivo de manera verbal. Descomponer el objetivo en una suma, diferencia y/o producto de trminos

    individuales (combinacin lineal)

    Expresar los trminos individuales usando las variables decisorias y los datos.

    IV) Identificacin de las restricciones.

    Las restricciones son condiciones que las variables de decisin deben satisfacer

    para constituir una solucin aceptable de un problema.

    Estas pueden ser de limitaciones fsicas (horas de trabajo de una planta),

    restricciones administrativas (satisfacer una demanda de un cliente especial),

    restricciones externas que las puede dar el mercado, restricciones lgicas sobre las

    variables (respuestas enteras).

  • Investigacin de Operaciones

    ____________________________________________________________________________________

    Diana Cobos 11

    Considerando nuestro ejercicio se pueden dar restricciones por los recursos

    disponibles como son, por ejemplo, la materia prima, ya que se disponen

    nicamente 180 libras para los cuatro productos, de modo que:

    2X1 + 2X2 + 1.5X3 +X4 180,

    Adems se dispone de 230 pies3 de espacio de almacenamiento, lo que puede

    traducirse como:

    2X1 +2.5X2 + 2X3 + 1.5X4 230

    y la tasa de produccin que est expresadas en unidades por hora, por lo que

    tenemos que convertirla primero en horas por cada unidad, por ejemplo, si 15

    unidades del producto 1 se producen en una hora, una unidad en cunto tiempo se

    producir?. Entonces se tiene que las horas/ unidad de cada producto son: 1/15 =

    .067 para el producto 1, 1/30 = 0.033 para el producto 2, 1/10 = 0.1 para el

    producto 3 y 1/15 = 0.066 para el producto 4.

    De este modo la restriccin del tiempo de produccin se puede expresar como:

    1/15 X1 + 1/30 X2 +1/10 X3 + 1/15 X4 8

    Las limitaciones son lgicas cuando la respuesta de las variables de decisin debe

    ser positiva o sea la restriccin de no negatividad.

    X1 0, X2 0, X3 0, X4 0.

    CARACTERSTICA CLAVE.

    Es importante tener en cuenta las variables de decisin y los datos del problema para definir cada una de las restricciones.

    Expresarlas como una suma, diferencia o producto de cantidades individuales.

    Establecer la magnitud de la direccin, teniendo en cuenta las limitaciones formuladas.

  • Investigacin de Operaciones

    ____________________________________________________________________________________

    Diana Cobos 12

    Una vez reunidos todos estos elementos descritos se hace una formulacin

    matemtica del problema de acuerdo a :

    Maximizar: 5X1 +6.5X2 + 5X3 + 5.5X4 (ganancia)

    Sujeta a:

    2X1 + 2X2 + 1.5X3 + X4 180 (materia prima)

    2X1 + 2.5X2 +2X3 + 1.5X4 230 (espacio)

    1/15 X1 + 1/30 X2 +1/10 X3 + 1/15 X4 8 (tasa de produccin)

    Xi 0 i = 1,2,3,4

    Donde Xi representa el nmero de unidades a fabricar del producto i para

    i=1,2,3,4

  • Investigacin de Operaciones

    ____________________________________________________________________________________

    Diana Cobos 13

    Modelo general de la PL

    Del ejemplo anterior, puede inducirse el siguiente modelo matemtico general de

    la PL

    Optimizar: X0 = C1X1 + C2X2 + . . . + CnXn (0)

    Sujeta a a11X1 + a12X2 + . . . a1nXn ( , = ) b1 (1)

    a21X1 + a22X2 + . . . a2nXn ( , = ) b2 (2)

    . . . . .

    . . . . .

    . . . . .

    am11X1 + am2X2 + . . . amnXn ( , = ) bm (m)

    X1, X2, Xn 0 (*)

    Donde:

    X0 = funcin objetivo, la cual pude maximizarse o minimizarse

    Xj = variable de decisin (actividad) j = 1, 2, . . . , n

    Cj = coeficiente de la variable Xj en la funcin objetivo, o ms brevemente,

    coeficiente objetivo de Xj

    aij = consumo del recurso i por la actividad j, o alternativamente, coeficiente

    tecnolgico de Xj en la restriccin i

    bi = constante del lado derecho (generalmente recurso disponible) en la

    restriccin i llamada tambin coeficiente de recurso

  • Investigacin de Operaciones

    ____________________________________________________________________________________

    Diana Cobos 14

    El modelo matemtico general de la PL suele dividirse en: el objetivo (0), las

    restricciones tecnolgicas o estructurales [de (1) a (m)] y las condiciones tcnicas

    o de no-negatividad (*)

    EJEMPLO 1 Una fbrica de juguetes fabrica dos tipos de juguetes de madera: soldados y trenes.

    Se vende un soldado a 27 dlares y se usan 10 de dlares de materia prima. Cada

    soldado que se produce aumenta los costos variables de mano de obra y los costos

    generales en 14 dlares. Se vende un tren a 21 dlares y se usan 9 dlares de

    materia prima. Cada tren producido aumenta los costos variables de mano de obra

    y los costos generales en 10 dlares. La produccin de soldados y trenes de madera

    necesita dos tipos de trabajo especializado: carpintera y acabado. Un soldado

    requiere 2 horas de acabado y 1 hora de carpintera. Un tren requiere 1 hora de

    acabado y 1 hora de carpintera. Cada semana, la fbrica puede conseguir toda la

    materia prima que se necesita, pero solamente dispone de 100 horas de acabado y

    80 horas de carpintera. La demanda de los trenes no tiene lmite, pero se pueden

    vender a lo ms 40 soldados semanalmente. La fbrica quiere maximizar su

    ganancia semanal (ingresoscostos). Formule un modelo matemtico que se pueda utilizar para maximizar las ganancias de la fbrica.

    Tomado de: Investigacin de Operaciones, Aplicaciones y algoritmos

    Wayne L. Winston

    Grupo Editorial Iberoamrica

  • Investigacin de Operaciones

    ____________________________________________________________________________________

    Diana Cobos 15

    Solucin

    (1) Resumen de datos

    Precio de

    venta ($)

    Materia

    prima ($)

    Otros

    costos ($)

    Carpintera

    (hr)

    Acabado

    (hr)

    Demanda

    Soldados 27 10 14 1 2 a lo ms 40

    Trenes 21 9 10 1 1 ilimitada

    Disponibilidad

    de recurso

    ilimitada 80 100

    (2) Variables de decisin

    X1 = el nmero de soldados producidos cada semana

    X2 = el nmero de trenes producidos cada semana

    (3) Funcin objetivo

    Se deben expresar las ganancias y los costos semanales de la fbrica en funcin de

    las variables de decisin X1 y X2. Entonces

    Ingresos semanales = 27X1 + 21X2

    Costos semanales de materia prima = 10X1 + 9X2

    Costos semanales variables = 14X1 + 10X2

    Entonces la fbrica quiere maximizar:

    (27X1 + 21X2) (10X1 + 9X2) (14X1 + 10X2) = 3X1 + 2X2

    De modo que el objetivo de la fbrica es elegir X1 y X2 para maximizar

    3X1 + 2X2. Si representamos el valor de la funcin objetivo por X0 la funcin

    objetivo de la fbrica es:

    Maximizar X0 = 3X1 + 2X2

  • Investigacin de Operaciones

    ____________________________________________________________________________________

    Diana Cobos 16

    (4) Restricciones

    Restriccin 1. No se pueden usar ms de 100 horas de acabado por semana

    Restriccin 2. No se pueden usar ms de 80 horas de carpintera por semana.

    Restriccin 3. No se deben producir ms de 40 soldados por semana

    La restriccin 1 se puede expresar como:

    2X1 + X2 100

    La restriccin 2 es:

    X1 + X2 80

    La restriccin 3 debe expresarse como:

    X1 40

    As el modelo completo es:

    Maximizar X0 = 3X1 + 2X2

    Sujeto a 2X1 + X2 100

    X1 + X2 80

    X1 40

    X1, X2 0

  • Investigacin de Operaciones

    ____________________________________________________________________________________

    Diana Cobos 17

    EJEMPLO 2

    Una compaa que fabrica automviles de lujo y camiones lanz una campaa

    ambiciosa de publicidad por televisin y decidi comprar comerciales de 1 minuto

    en dos tipos de programas: series cmicas y juegos de ftbol. 7 millones de

    mujeres y 2 millones de hombres ven cada comercial en series cmicas. 2 millones

    de mujeres y 12 millones de hombres ven cada comercial en juegos de ftbol. Un

    comercial de 1 minuto en una serie cmica, cuesta 50 000 dlares, y un comercial

    de 1 minuto en un juego de ftbol cuesta 100 000 dlares. La compaa que por lo

    menos 20 millones de mujeres y 24 millones de hombres vieran los comerciales.

    Utilice la PL para determinar cmo la fbrica puede alcanzar sus requerimientos

    publicitarios a un costo mnimo.

    Tomado de: Investigacin de Operaciones, Aplicaciones y algoritmos

    Wayne L. Winston

    Grupo Editorial Iberoamrica

    Solucin

    (1) Resumen de datos

    Mujeres

    (millones)

    Hombres

    (millones)

    Costo del comercial

    (miles de $/min)

    Series cmicas 7 2 50

    Juegos de futbol 2 12 100

    Audiencia esperada

    (millones de personas)

    Por lo menos 28 Por lo menos 24

    (2) Variables de decisin

    X1 = Nmero de comerciales de un minuto en series cmicas

    X2 = Nmero de comerciales de un minuto en juegos de ftbol

    (3) Funcin objetivo

    La fbrica quiere minimizar el costo total de la publicidad (en miles de dlares)

    Costo total de publicidad = costo de anuncios en series cmicas + costo de los

    anuncios en juegos de ftbol.

  • Investigacin de Operaciones

    ____________________________________________________________________________________

    Diana Cobos 18

    As la funcin objetivo de la fbrica es:

    Minimizar X0 = 50X1 + 100X2

    (4) Restricciones

    Restriccin 1. Los anuncios tienen que llegar a por lo menos 28 millones de

    mujeres

    Restriccin 2. Los anuncios tienen que llegar a por lo menos 24 millones de

    hombres

    La restriccin 1 se puede expresar como:

    7X1 + 2X2 28

    La restriccin 2 es:

    2X1 + 12X2 24

    As el modelo completo es:

    Minimizar X0 = 50X1 + 100X2

    Sujeta a 7X1 + 2X2 28

    2X1 + 12X2 24

    X1, X2 0