OPTIMIZACION LINEAL

un problema de programación lineal se requiere encontrar el valor máximo o mínimo de alguna expresión algebraica, cuando las variables de esta expresión están sujetas a varias desigualdades lineales.

El ejemplo sencillo siguiente es típico de tales problemas.

EJEMPLO 1 (Utilidad máxima)

Una compañía fabrica dos productos, X y Y. Cada uno de estos productos requiere cierto tiempo en la línea de ensamblado y otro tiempo más en el departamento de acabado. Cada artículo del tipo X necesita 5 horas

de ensamblado y 2 horas de acabado; mientras que cada artículo del tipo Y

requiere 3 horas en ensamblado y 4 de acabado.

En cualquier semana, la empresa dispone de 105 horas en la línea de ensamblado y 70 horas en el departamento de acabado. La empresa puede vender todos los artículos que produce y obtener una utilidad de $200 por cada artículo de X y $160 por cada artículo de Y. Calcule el número de artículo de cada tipo que deberían fabricarse a la semana con el objetivo de maximizar la utilidad total.  

Solución

Por lo regular, es conveniente al manejar problemas de este tipo resumir

la información en una tabla. En la tabla 1 aparece la información del ejemplo 1.

	EMSAMBLE	ACABADO	UTILIDAD
x	5	2	200
y	3	4	160
disponibilidad	105	70

Suponga que la empresa produce x artículos de tipo X y y artículos del tipo Y a la

semana. Entonces, el tiempo necesario en la línea de ensamblado será de 5x horas en el caso del producto X y 3y horas para el producto Y, o (5x + 3y) horas en total.

Dado que sólo se puede disponer de 105 horas, debemos tener que

5x + 3y ´_ 105.

De manera similar, se requieren de 2x horas en el departamento de acabado

por cada x artículos del producto X y 4y por cada y artículos del producto Y.

El número total de horas, 2x +4y, no pueden exceder las 70 de que se dispone, de modo que tenemos la segunda condición, 2x +4y _ 70.

Cada artículo del tipo X genera una utilidad de $200, de modo que x artículos

producen 200x dólares de utilidad. En forma análoga, y artículos de tipo Y producen 160y dólares de utilidad. Así, la utilidad semanal total P (en dólares) está dada por:

P =200x + 160y

Por consiguiente, podemos reestablecer el problema en los términos siguientes:

encuentre los valores de x y y que maximicen la cantidad

                                  P=200x +160y

cuando x y y están sujetas a las condiciones

5x +3y _ 105, 2x +4y _ 70, x _0 y y _ 0 (1)

(Observe las condiciones de que x y y no deben ser negativas.

 Éstas se agregan por razones de completez).

Este ejemplo es un problema característico de programación lineal. Tenemos

una expresión P =200x + 160y, que es lineal en las variables x y y, y deseamos encontrar el valor máximo de P cuando x y y satisfacen las desigualdades (1). Un problema más general podría incluir más de dos variables y un número mayor de desigualdades que las cuatro de este ejemplo; pero de cualquier manera este ejemplo es bastante representativo de los problemas del área de programación lineal.

Al analizar cualquier problema de programación lineal, en especial cuando

sólo intervienen dos variables, con frecuencia es útil un enfoque geométrico. Consideremos

las desigualdades (1). El conjunto de puntos (x, y) que satisfacen todas

las desigualdades aparece sombreado en la figura 7. Esta región sombreada representa

el conjunto de soluciones factibles, esto es, el conjunto de valores de x y y que

la empresa puede adoptar. No se puede tomar cualquier punto (x, y) situado afuerade esta región sombreada.

Por ejemplo, consideremos el punto x = 12, y = 14, el cual está fuera de la región

factible. Con la finalidad de producir 12 artículos del tipo X y 14 artículos del Y

se requerirían 12(5)+ 14(3) =102 horas en la línea de ensamblado y 12(2) +

14(4) = 80 horas en el departamento de acabado. Si bien esto no excedería las horas disponibles en la línea de ensamblado, sí sobrepasa aquellas disponibles en el departamento de acabado; de modo que no está dentro del programa de producción posible.