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
Pmax = 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 .
