En qué consiste un problema
de Programación Lineal
Un problema de Programación
Lineal consiste en encontrar el máximo o el mínimo
de una función, como, por ejemplo, los beneficios
de una empresa o el coste de una dieta, teniendo en cuenta
una serie de limitaciones (restricciones) impuestas por
las condiciones materiales en las que se desarrolla nuestro
problema (número de trabajadores, cantidad mínima
diaria de calorías, etc.)
Más en concreto, un
problema de Programación Lineal presenta siempre
los siguientes elementos:
Un sistema de inecuaciones,
llamadas restricciones, impuestas por
la naturaleza del problema. El polígono convexo
formado por las soluciones del sistema recibe el nombre
de región factible.
Una función lineal de dos variables,
de la forma f(x,y)=ax+by+c, que recibe
el nombre de función objetivo. Resolver
el problema consiste en encontrar el punto, o los puntos,
de la región factible en los que f alcanza su máximo
o su mínimo.
Por ejemplo,
vamos a buscar el máximo de la función
f(x,y)=-x+y+2,
sujeta a las restricciones:
x>=0,
y>=0, 2x-3y<=0, 2x-9y<=-18.
Si observas la animación
verás que una forma de resolverlo consiste en representar
en el espacio la región factible (en el plano XY) y
la función objetivo en la forma
z=f(x,y),
y encontrar
el punto de la región factible en el que f(x,y)
es más grande (aquél en el que z
alcanza su mayor altura)
El inconveniente que presenta el método anterior es
que nos obliga a utilizar una representación en el
espacio.
Por eso, en la práctica resulta más conveniente
representar en el plano la región factible y trazar
las llamadas curvas de nivel, que, como
en un mapa, representan los puntos en los que la función
objetivo alcanza la misma altura.
Como la función objetivo
es un plano, las curvas de nivel que obtenemos son rectas,
todas ellas paralelas.
Según se va cambiando
de una recta paralela a otra el valor de f
va aumentando o disminuyendo.
Para terminar de resolver el problema,
obtener el máximo o el mínimo que estás
buscando, debes observar cómo varía la función
objetivo (en algunas ocasiones el valor de la función
objetivo aumenta cuando aumentas la ordenada en el origen
de las rectas paralelas y en otras ocurre lo contrario) y
en qué puntos las paralelas a ella "abandonan"
la región factible.
Observa las siguientes animaciones
en las que aparece un ejemplo de problema en el que la región
factible está acotada y otro en la que no lo está.
. En la primera el máximo es igual a 3, se alcanza
en un segmento y no se alcanza el mínimo. En la segunda
el máximo es 12 y se alcanza en un vértice,
mientras que el mínimo vale -3 y se alcanza en un segmento.
Región no acotada
Región acotada
En la práctica una vez que hayas representado
la región factible, te basta con representar dos paralelas
a la función objetivo, por ejemplo f(x,y)=0
y f(x,y)=1, fijarte en la dirección
de crecimiento, y observar en qué puntos las paralelas
"se salen" de la región factible.
Si la región no está acotada
los extremos a veces no existen y si existen se alcanzan en
un vértice, un segmento o una semirecta (¿por
qué?). Si la región está acotada siempre
existen los extremos y pueden alcanzarse en un vértice
o en un segmento (¿por qué?).
Ejercicio III
1.- Representa en tu cuaderno
una región factible y una función objetivo tales
que: a) alcance su máximo y su mínimo
en un vértice de la región factible. b) alcance su máximo en un segmento
y su mínimo en un vértice de la región
factible. c) no alcance su máximo y alcance
su mínimo en un vértice de la región
factible. d) alcance su máximo en un segmento
y alcance su mínimo en una semirecta.
2.- Representa en tu cuaderno
la región factible asociada a x>=0,
y>=0, 2x-3y<=0, 2x-9y<=-18
y las rectas -x+y+2=-4, -x+y+2=0 y
-x+y+2=4. ¿En qué punto de
la región factible alcanza su máximo y su mínimo
la función f(x,y)=-x+y+2?
