PROGRAMACIÓN LINEAL - OPTIMIZACIÓN LINEAL

PROGRAMACIÓN LINEAL

OPTIMIZACIÓN LINEAL (ENFOQUE GEOMÉTRICO)

En un problema de programación lineal se requiere encontrar el máximo o mínimo de alguna expresión  algebraica cuando las variables de ésta expresión están sujetas a un número de desigualdades lineales. El ejemplo simple 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 requiere 5 horas  de ensamblado y 2 horas de acabado, mientras que cada artículo del tipo Y requiere 3 horas de ensamblado y 4 horas 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ículos de cada tipo que deberían fabricarse a la semana con objeto  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.

	ENSAMBLADO	ACABADO	UTILIDAD
X	5	2	200
Y	3	4	160
DISPONIBILIDAD	105	70

Suponga que la empresa produce x artículos del tipo X a la semana 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 solo se pueden disponer de 105 horas, debemos tener que 5x + 3y ≤ 105.

De manera similar, se requieren 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 del 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 restablecer el problema en los términos siguientes:

Encuentre los valores x y y que maximizan 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    

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. 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 solo intervienen dos variables, con frecuencia es útil un enfoque geométrico.   
     

Consideremos las desigualdades vistas. El conjunto de puntos (x,y) que satisface todas las desigualdades aparece sombreado en la figura 1. 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 afuera de esta región sombreada.

FIGURA 1

Por ejemplo, consideremos el punto x=12, y=14, el cual está fuera de la región factible. A fin de producir  12 artículos de tipo X  y 14 artículos del tipo Y  se requerirán          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, si sobrepasa aquellas disponibles en el departamento de acabado; de modo que no está dentro del programa de producción posible.

Consideremos ahora el conjunto de valores x y y que conducen a alguna utilidad fija. Por ejemplo, dado a P el valor 4000, advertimos que x y y deben satisfacer la ecuación.

                                   200x + 160y=4000

Todos los valores de x y y que satisfacen esta ecuación producen una utilidad de $4000 a la semana. Esta es la ecuación de una línea recta que corta el eje x  en el punto (20,0) y al eje y  en el punto (0,25), como se aprecia en la figura 2. Parte de esta línea pasa por la  región de soluciones factibles. Debido a esto, concluimos que le es posible a la empresa lograr una utilidad de 4000 dólares a la semana. Puede realizar esto eligiendo cualquier valor de  (x,y) situados en los segmentos AB  que aparece en la figura 2.

FIGURA 2

Por otra parte consideremos P=6000. Los valores correspondientes de x y y deben satisfacer 200x + 160y=6000, que otra vez es la ecuación de una  línea recta, esta vez corta a los ejes de coordenadas en los puntos (30,0) y (0.37.5). Esta línea recta no pasa por la región sombreada de soluciones factibles (véase la figura 2) y por ello no es posible a la empresa obtener una utilidad tan grande como $6000 a la semana. La utilidad máxima posible debe estar en algún lugar entre $4.000 y $ 6.000 a la semana.

El conjunto de puntos (x,y) que conducen a una utilidad dada P satisfacen la ecuación 200x + 160y=P. esta ecuación, para P fija, tiene como grafico una línea recta en el plano xy llamada línea de utilidad constante  o curva de indiferencia . Las dos líneas que aparecen en la figura 2  son líneas de utilidad constante que corresponden a los valores P=4000 y P=6000.

La ecuación de una línea de utilidad constante puede escribirse de la forma

                           160y = P – 200x

O bien      y = -   5 x  +    P   

                             4         160

Por tanto la línea tiene pendiente  -5/4  y ordenada al origen P/160. Es una propiedad importante que la pendiente de cualquier línea  de utilidad constante es la misma sin importar  el valor de P.  Esto significa que todas las líneas de utilidad constante son paralelas entre sí. A medida que el valor de P se incrementa, la línea de utilidad  máxima correspondiente se aparta del origen (la ordenada al origen aumenta), siempre con la misma pendiente.

A fin de obtener la utilidad máxima, debemos alejar la línea de utilidad constante del origen  hasta que solo toque el extremo de la región de soluciones  factibles.

Es claro por la figura 2 que la línea de utilidad máxima es la que pasa por la esquina C situada en la frontera de la  solución factible. Los valores de x y y en C dan los  volúmenes de producción de los dos productos X y Y que conducen a la utilidad máxima.

El punto C es la intersección de las dos líneas  rectas que acotan la región factible. Sus coordenadas se obtienen resolviendo las ecuaciones de estas dos líneas, 5x + 3y = 105 y      2x + 4y = 70. Resolviendo estas ecuaciones, encontramos que x=15 y y=10. Por consiguiente, la utilidad máxima es cuando la empresa produce 15 artículos del tipo X y 10 artículos del tipo Y a la semana. La utilidad semanal máxima está dada por

P_max   =  200x + 460y

            = 200(15) + 160(10)

            = 4600

La utilidad máxima es por tanto $4.600.

El procedimiento usado  en la resolución de este problema también puede emplearse cuando ocurre un número mayor de desigualdades.

Bibliografía: MATEMATICAS  APLICADAS A LA ADMINISTRACION Y A LA ECONOMIA / Jagdish C.  Arya/Robin W, Lardner / Prentice Hall / tercera edición .