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.