Scribd Logo
Cargar

¡Te damos la bienvenida a Scribd!

  • 29 vistas

    Programación Lineal - Formulación y Solución Gráfica

    Cargado por

    Carlos Vásquez
    1) Se presentan dos ejemplos de problemas de programación lineal con múltiples restricciones y variables de decisión. 2) En ambos casos se identifican las variables, restricciones, función objetivo y se formulan los modelos matemáticos correspondientes. 3) La solución implica representar gráficamente la región factible definida por las restricciones y estudiar en ella el comportamiento de la función objetivo.

    Copyright:

    © All Rights Reserved
    Descargue como PDF, TXT o lea en línea desde Scribd

    Programación Lineal - Formulación y Solución Gráfica

    Cargado por

    Carlos Vásquez
    29 vistas21 páginas
    1) Se presentan dos ejemplos de problemas de programación lineal con múltiples restricciones y variables de decisión. 2) En ambos casos se identifican las variables, restricciones, función objetivo y se formulan los modelos matemáticos correspondientes. 3) La solución implica representar gráficamente la región factible definida por las restricciones y estudiar en ella el comportamiento de la función objetivo.

    Título original

    2. Programación Lineal - Formulación y Solución Gráfica

    Derechos de autor

    © © All Rights Reserved

    Formatos disponibles

    PDF, TXT o lea en línea desde Scribd

    ¿Le pareció útil este documento?

    ¿Este contenido es inapropiado?

    1) Se presentan dos ejemplos de problemas de programación lineal con múltiples restricciones y variables de decisión. 2) En ambos casos se identifican las variables, restricciones, función objetivo y se formulan los modelos matemáticos correspondientes. 3) La solución implica representar gráficamente la región factible definida por las restricciones y estudiar en ella el comportamiento de la función objetivo.

    Copyright:

    © All Rights Reserved
    Descargue como PDF, TXT o lea en línea desde Scribd
    Descargar como pdf o txt
    29 vistas21 páginas

    Programación Lineal - Formulación y Solución Gráfica

    Cargado por

    Carlos Vásquez
    1) Se presentan dos ejemplos de problemas de programación lineal con múltiples restricciones y variables de decisión. 2) En ambos casos se identifican las variables, restricciones, función objetivo y se formulan los modelos matemáticos correspondientes. 3) La solución implica representar gráficamente la región factible definida por las restricciones y estudiar en ella el comportamiento de la función objetivo.

    Copyright:

    © All Rights Reserved
    Descargue como PDF, TXT o lea en línea desde Scribd
    Descargar como pdf o txt
    de 21

    FORMULACIÓN Y SOLUCIÓN GRÁFICA

    La Programación Lineal (P.L.) es una herramienta determinística, es decir,


    todos los parámetros del modelo se suponen conocidos con certeza.
    En la vida real, es raro encontrar un problema donde prevalezca una
    verdadera certeza respecto a los datos. La técnica de P.L. compensa esta
    deficiencia

    Formulación en un Problema Lineal


    A través de la descripción de un problema, nuestros objetivos serán:
    1. Identificar los elementos (variables, costes, etc.) que intervienen en el
    problema.
    2. Encontrar una formulación adecuada para dicho modelo.
    3. Resolver el modelo, es decir, hallar el valor óptimo del problema y una
    solución asociada a dicho valor (aunque en ocasiones esto último
    puede ser irrelevante).

    Un problema de programación lineal (problema lineal, PL) es un problema


    en el que se pretende optimizar una función (función objetivo) lineal en el
    conjunto de variables que intervienen (variables de decisión), cumpliendo
    unos ciertos requerimientos (restricciones) también lineales.
    Ejemplo
    Un veterinario aconseja a un granjero dedicado a la cría de pollos una dieta
    mínima para la alimentación de las aves consistente en 3 unidades de hierro y
    4 unidades de vitaminas.
    El granjero tiene la posibilidad de mezclar tres alimentos distintos: maíz, harina
    de pescado y pienso sintético.
    Cada kilo de maíz proporciona 2.5 unidades de hierro y 1 unidad de vitaminas,
    cada kilo de harina de pescado da 3 unidades de hierro y 3 unidades de
    vitaminas y cada kilo de producto sintético 1 unidad de hierro y 2 unidades de
    vitaminas
    El granjero se pregunta por la composición de la dieta que, satisfaciendo las
    necesidades alimenticias, minimice el coste total. Los precios por kilo de maíz,
    harina y pienso sintético son, respectivamente, 0.3, 0.5 y 0.2 euros

    Solución: Antes de formular propiamente el problema, podemos aglutinar los


    datos del problema en la siguiente tabla:
    formulación
    Identificar las variables de decisión:
    x1 = “kilos de maíz”,
    x2 = “kilos de harina”,
    x3 = “kilos de pienso”.
    Restricciones
    Para que se cumplan las necesidades de hierro, debe satisfacerse que
    2.5x1 + 3x2 + x3 ≥ 3.
    Para alcanzar los requerimientos de vitaminas se ha de imponer que
    x1 + 3x2 + 2x3 ≥ 4.
    Función Objetivo
    La función a minimizar es
    0.3x1 + 0.5x2 + 0.2x3.
    No Negatividad
    Las variables x1, x2 y x3 deben ser todas positivas:
    x1, x2, x3 ≥ 0.
    Ejemplo

    Una empresa de compuestos químicos puede elaborar dos productos, A y B,


    a partir de la combinación de tres tipos de elementos: hierro, plomo y estaño.
    Dada la siguiente tabla de requerimientos y beneficios, formula el modelo
    que maximiza el beneficio de la producción.

    Solución:

    Formulación:
    Identificar las variables de decisión:
    x1 = “kilos de producto A”,
    x2 = “kilos de producto B”.
    Restricciones
    Para no agotar los recursos de hierro, debe satisfacerse:
    7x1 + 4x2 ≤ 56.
    Como no se puede exceder la cantidad de plomo disponible:
    3x1 + 5x2 ≤ 45.
    Tampoco es posible gastar más del estaño que se tiene:
    4x1 + 3x2 ≤ 48.
    Función Objetivo
    La función a maximizar es
    Z = 10x1 + 8x2.
    No Negatividad
    Sólo es posible fabricar una cantidad positiva de kilos de producto:
    x1, x2 ≥ 0.
    Ejemplo
    Una institución financiera se encuentra en el proceso de formular su política
    de préstamos. Para ese fin se asigna un total de $ 12 millones. La tabla que
    sigue señala los tipos de préstamos, la tasa de interés que cobra y la
    posibilidad que los clientes no cubran sus pagos, irrecuperables o incobrables.

    Tipo de Tasa Pr. de Se supone que los pagos que no se


    Préstamo de Incobrables cobren son irrecuperables y, por lo
    interés tanto, no producen ingresos por
    Personal 0.14 0.1 concepto de interés.
    La competencia con otras
    Automóvil 0.13 0.07
    instituciones financieras requiere
    Casa 0.12 0.03 que el banco asigne cuando menos
    Agrícola 0.125 0.05 el 40% de los fondos totales a
    préstamos agrícolas y comerciales.
    Comercial 0.1 0.02

    Los préstamos para casas deben ser iguales cuando menos al 50% de los
    préstamos personales, para automóvil y para casa.
    El banco tiene una política que especifica que la relación global de pagos
    irrecuperables no puede ser superior a 0.04
    Formule el modelo de Programación
    Formulación: Tipo de Tasa Pr. de
    variables de decisión: Préstamo de Incobrables Pr. de cobro
    interés
    x1 = “P. Personales”,
    Personal 0.14 0.1 0.9
    x2 = “P. Automóvil”,
    x3 = “P. Casa”, Automóvil 0.13 0.07 0.93
    x4 = “P. Agrícolas”, Casa 0.12 0.03 0.97
    x5 = “P. Comerciales”,
    Agrícola 0.125 0.05 0.95
    Comercial 0.1 0.02 0.98

    Función Objetivo :

    El objetivo es maximizar el rendimiento neto, la diferencia entre el ingreso por


    intereses y la pérdida por deudas impagables. El ingreso por intereses se
    acumula sobre los préstamos al corriente.
    Por ejemplo, cuando se pierde 10%(0.1) de préstamos personales por deuda
    impagable, el banco recibirá intereses sobre 90% (0.9) del préstamo; es decir,
    recibirá un interés de 14% sobre 0.9x1 del préstamo original x1. El razonamiento
    es válido para los cuatro tipos restantes de préstamos. Por lo tanto,
    Restricciones
    1. Los fondos totales no deben exceder de $12 (millones):
    x1 + x2 + x3 + x4 + x5 ≤ 12
    2. Los préstamos agrícolas y comerciales deben ser iguales a por lo menos el
    40% de todos los préstamos: x4 + x5 ≥ 0.4(x1 + x2 + x3 + x4 + x5)

    0.4x1 + 0.4x2 + 0.4x3 - 0.6 x4 - 0.6 x5 ≤ 0

    3. Los préstamos para casa deben ser iguales a por lo menos 50% de los
    préstamos personales, para automóvil y para casa:
    x3 ≥ 0.5(x1 + x2 + x3)
    0.5x1 + 0.5x2 - 0.5x3 ≤ 0

    4. Las deudas impagables no deben exceder 4%(0.04) de todos los préstamos:


    0.1x1 + 0.07x2 + 0.03x3 + 0.05x4 + 0.02x5 ≤ 0.04(x1 + x2 + x3 + x4 + x5)

    0.06x1 + 0.03x2 - 0.01x3 + 0.01x4 - 0.02x5 ≤ 0


    5. No negatividad:
    x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0, x5 ≥ 0
    IDENTIFICACION DE ESPACIOS FACTIBLES Y
    DIRECCIONES DE FUNCION OBJETIVO

    Determine el espacio factible de las siguientes restricciones dado que x1, x2 ≥ 0.

    a) - 3x1 + x2 ≥ 6 Graficamos la recta -3x1 + x2 = 6


    x2
    si x1 = 0 ; x2 = 6 si x2=0 ; x1 = -2
    6
    Probamos un punto cualquiera. (0,0)
    -3(0) + 0 ≥ 6 0 ≥ 6 Falso
    x1
    -2

    b) 10x1 - 5x2 ≤ 5 Graficamos la recta 10x1 - 5x2 = 5


    si x1 = 0 ; x2 = -1 si x2=0 ; x1 = 1/2
    x2

    Probamos un punto cualquiera. (0,0)


    10(0) -5(0) ≤ 5 0 ≤ 5 verdadero
    1/2 x1

    -1
    Maximizar z = x1 + x2

    Cuando z = 4 4 = x1 + x2 Si x1= 0 x2 = 4 ; Si x2 =0 x1= 4

    Cuando z = 6 6 = x1 + x2 Si x1= 0 x2 = 6 ; Si x2 =0 x1= 6


    x2
    6
    4

    4 6 x1

    Minimizar z = -x1 - 2x2


    Resolución gráfica de problemas lineales

    Si el problema lineal tiene únicamente dos variables, entonces puede


    resolverse representando gráficamente la región factible y estudiando la
    función objetivo.
    Para ello, consideramos un gráfico en el plano R2 que toma las dos variables
    x1 ^ x2 como ejes.
    A continuación, se va delimitando la región factible P dibujando las
    restricciones del problema:
    una igualdad (x1 + x2 = 3) representa una recta, mientras que una
    desigualdad (x1+x2 ≤ 3) da lugar a un semiplano cerrado.
    Observemos que si, como es bastante habitual, se tiene la restricción de No
    negatividad, es decir x1, x2 ≥ 0, entonces la región factible estará contenida
    en el cuadrante superior derecho del plano.
    Ejemplo

    Solución:
    Para resolver el problema, debemos comenzar por delimitar la región factible.
    Para ello, vamos dibujando las desigualdades una a una. Como cada recta
    establece un semiplano, irá eliminando soluciones. Una vez dibujadas todas
    las rectas, la intersección de los semiespacios es la región factible de nuestro
    problema.
    Comenzamos con las dos restricciones de positividad: x1, x2 ≥ 0. De este
    modo, ya tenemos restringido el espacio de soluciones al cuadrante superior
    derecho.
    A continuación consideramos la recta x1 + x2 ≤ 7.
    Al dibujar la siguiente recta, 3x1 + 4x2 ≤ 24, vemos ya como una región que
    era factible queda cortada:

    x2> 0

    x1> 0
    Realizamos el mismo procedimiento para x2 ≤ 5:

    Y para −6x1 + x2 ≤ 1:

    De modo que la región factible es la que vemos:


    Una vez establecido cuál es el poliedro, dibujamos diferentes rectas de
    nivel. En este caso, como estamos maximizando, vemos que debemos
    desplazarnos hacia el lado derecho del eje OX1.
    En concreto, vemos que la recta de nivel de valor máximo que intersecta
    con el poliedro es la que tiene valor 35.

    En consecuencia, este problema tiene valor óptimo z* = 35 y se alcanza en


    el punto óptimo (x*1, x*2) = (7, 0). (Se igualan las rectas X1 + X2 =7 con la
    recta X1 = 0)
    Ejemplo
    Si en el ejemplo anterior el objetivo fuese maximizar la función z= −x1 + 2x2,
    la región factible no variaría (no se modifican las restricciones), pero al
    dibujar la recta veríamos que la solución óptimo es distinta:

    Si z= 2, entonces 2= -x1 + 2x2


    Z= 4
    si x1= 0, x2= 1 (0,1)
    Z= 2
    si x2= 0, x1= -2 (-2,0)

    Si z= 4, entonces 4= -x1 + 2x2


    si x1= 0, x2= 2 (0,2)
    si x2= 0, x1= -4 (-4,0)

    -4 -2

    Para encontrar los valores óptimos igualamos la recta X2 = 5 con la recta


    −6x1 + x2 =1
    Ejemplo: Resolver gráficamente el siguiente problema

    Z=

    También podría gustarte