En infinidad de aplicaciones de la industria, la economía, la estrategia militar, etc.. se presentan situaciones en las que se exige maximizar o minimizar algunas fucniones que se encuentran sujetas a determinadas limitaciones, que llamaremos restricciones.
Un problema de programación lineal en dos variables, tiene la siguiente formulación estándar:
puediendo cambiarse maximizar por minimizar, y el sentido de las desigualdades.
En un problema de programación lineal intervienen:
·La función f(x,y) = ax + by + c llamada función objetivo y que es necesario optimizar. En esa expresión xey son las variables de decisión, mientras que a, b y c son constantes.
·Las restricciones que deben ser inecuaciones lineales. Su número depende del problema en cuestión. El carácter de desigualdad viene impuesto por las limitaciones, disponibilidades o necesidades, que son: inferiores a ... ( menores: < o ); como mínimo de ... (mayores: > o ) . Tanto si se trata de maximizar como de minimizar, las desigualdades pueden darse en cualquiera de los dos sentidos.
·Al conjunto de valores de x e y que verifican todas y cada una de las restricciones se lo denomina conjunto (o región ) factible. Todo punto de ese conjunto puede ser solución del problema; todo punto no perteneciente a ese conjunto no puede ser solución. En el apartado siguiente veremos como se determina la región factible.
·La solución óptima del problema será un par de valores (x0, y0) del conjunto factible que haga que f(x,y) tome el valor máximo o mínimo.
A.Determinación de Región Factible
La solución de un problema de programación lineal, en el supuesto de que exista, debe estar en la región determinada por las distintas desigualdades. Esta recibe el nombre de región factible, y puede estar o no acotada.
Región Factible
REGION NO ACOTADA
REGION NO ACOTADA
La región factible incluye o no los lados y los vértices, según que las desigualdades sean en sentido amplio (o ) o en sentido estricto (< o >).
Si la región factible está acotada, su representación gráfica es un polígono convexo con un número de lados menor o igual que el número de restricciones.
El procedimiento para determinar la región factible es el siguiente:
1)Se resuelve cada inecuación por separado, es decir, se encuentra el semiplano de soluciones de cada una de las inecuaciones.
·Se dibuja la recta asociada a la inecuación. Esta recta divide al plano en dos regiones o semiplanos
·Para averiguar cuál es la región válida, el procedimiento práctico consiste en elegir un punto, por ejemplo, el (0,0) si la recta no pasa por el origen, y comprobar si las coordenadas satisfacen o no la inecuación. Si lo hacen, la región en la que está ese punto es aquella cuyos puntos verifican la inecuación; en caso contrario, la región válida es la otra.
2) La región factible está formada por la intersección o región común de las soluciones de todas las inecuaciones.
Como sucede con los sistemas de ecuaciones lineales, los sistemas de inecuaciones lineales pueden presentar varias opciones respecto a sus soluciones: puede no existir solución, en el caso de que exista el conjunto solución puede ser acotado o no. Ejemplo:
Dibuja la región factible asociada a las restricciones:
x+y (mayor igual) 4
y (menor igual) 4
y (mayor igual) x
Las rectas asociadas son: r : x + y = 4 ; s : y = 4 , t: y = x
Elegimos el punto O(0,0), que se encuentra en el semiplano situado por debajo de la recta. Introduciendo las coordenadas (0,0) en la inecuación x + y4, vemos que no la satisface: 0 + 0 = 0 < 4 . Por tanto, el conjunto de soluciones de la inecuación es el semiplano situado por encima de la recta r : x + y = 4 .
Procedemos como en el paso anterior. Las coordenadas (0,0) satisfacen la inecuación y4 ( 0 4) . Por tanto, el conjunto de soluciones de la inecuación es el semiplano que incluye al punto O.
La recta t asociada a la rectricción pasa por el origen, lo cual significa que si probásemos con el punto O(0,0) no llegaríamos a ninguna conclusión. Elegimos el punto (1,0) y vemos que no satisface la inecuación y x ( y = 0 < 1 = x ). Por tanto, el conjunto solución de esta inecuación es el semiplano determinado por la recta t que no incluye al punto (1,0).
La región factible está formada por los puntos que cumplen las tres restricciones, es decir, se encuentran en los tres semiplanos anteriores
B.Mètodo Grafico
Las rectas de nivel dan los puntos del plano en los que la función objetivo toma el mismo valor.
Si la función objetivo es f(x,y) = ax + by + c, la ecuación de las rectas de nivel es de la forma:
ax + by + c = 0 ax + by = k
Variando k (o p) se obtienen distintos niveles para esas rectas y, en consecuencia, distintos valores para f(x,y).
En un problema todas las rectas de nivel son paralelas, pues los coeficientes a y b de la recta ax + by = k son los que determinan su pendiente. Por tanto, si k1 es distinto de k2 , las rectas ax + by = k1 y ax + by = k2 son paralelas. Luego, trazada una cualquiera de esas rectas, las demás de obtienen por desplazamientos paralelos a ella.
Si lo que se pretende es resolver un problema de programación lineal, los únicos puntos que interesan son los de la región factible, y las únicas rectas de nivel que importan son aquellas que están en contacto con dicha región. Como el nivel aumenta (o disminuye) desplazando las rectas, el máximo (o el mínimo) de f(x,y) se alcanzará en el último (o en el primer) punto de contacto de esas rectas con la región factible.
Veamos ahora como se aplica todo esto a la resolución de un problema de programación lineal
Maximizar : Z = f(x,y) = x + y
Sujeto a: 0 x 4
0 y 4
y x /2
1) Representamos la región factible:
La recta s : x = 4 pasa por el punto (4,0) y es paralela al eje Y. Las soluciones de 0 x4 son los puntos entre el eje Y y la recta x = 4
La recta r : y = 4 pasa por el punto (0,4) y es paralela al eje X. Las soluciones de 0 y4 son los puntos entre el eje X y la recta y = 4
La recta t : y = x/2 pasa por los puntos (0,0) y (2,1) . Las soluciones de yx /2 son los puntos de su izquierda.
Resolviendo los sistemas correspondientes calculamos los vértices de la región factible:
{ y = x/2 , x = 0 } nos da el vértice O(0,0) { x = 4, y = x/2 } nos da el vértice A(4,2) { x = 4 , y = 4} nos da el vértice B(4,4) { y = 4 , x = 0 } nos da el vértice C(0,4)
2) Representamos las rectas de nivel :
En nuestro caso son rectas de la forma x + y = k . Inicialmente representamos Z = x + y = 0 . Trasladándola hacia la derecha, obtenemos las rectas : x + y = 2, x + y = 4, x + y = 8 , es decir aumenta el nivel.
3) Obtenemos la solución óptima:
Se obtiene en el punto de la región factible que hace máximo k. En nuestro caso esto ocurre en el punto B; es el último punto de contacto de esas rectas con la región factible , para el que k = 8.
Si hay dos vértices, P y Q, que se encuentran en la misma recta de nivel ,de ecuación ax +by = k .Es evidente que todos los puntos del segmento PQ son de esa recta; por tanto, en todos ellos f(x,y) vale k. Así pues, la solución óptima es cualquier punto de esa recta; en particular los vértices P y Q.
B.Método Analítico
El siguiente resultado, denominado teorema fundamental de la programación lineal, nos permite conocer otro método de solucionar un programa con dos variables.
En un programa lineal con dos variables, si existe una solución única que optimice la función objetivo, ésta se encuentra en un punto extremo (vértice) de la región factible acotada, nunca en el interior de dicha región.
Si la función objetivo toma el mismo valor óptimo en dos vértices, también toma idéntico valor en los puntos del segmento que determinan.
En el caso de que la región factible no es acotada, la función lineal objetivo no alcanza necesariamente un valor óptimo concreto, pero, si lo hace, éste se encuentra en uno de los vértices de la región
La evaluación de la función objetivo en los vértices de la región factible nos va a permitir encontrar el valor óptimo (máximo o mínimo) en alguno de ello
Ejemplo:
MaximizarZ = f(x,y) = 3x + 8y
sujeto a:4x + 5y40
2x + 5y30
x0 , y0
1) Hallar los puntos de corte de las rectas asociadas a las restricciones:
Calculamos las soluciones de cada uno de los seis sistemas de dos ecuaciones con dos incógnitas que se pueden formar con las cuatro restricciones:
{ 4x + 5y = 40 , 2x + 5y = 30}. Solución A(5,4)
{ 4x + 5y = 40 , x = 0 } Solución:B (0,8)
{ 4x + 5y = 40 , y = 0}. Solución: C(10,0)
{ 2x + 5y = 30 , x = 0} Solución: D(0,6)
{ 2x + 5y = 30 , y = 0}. Solución : E(15,0)
{ x = 0, y = 0} Solución: O(0,0)
2) Determinar los vértices de la región factible:
Los vértices de la región factible son aquellos puntos que cumplen todas las restricciones.
Si sustituimos los puntos en cada una de las desigualdades tenemos que:
B no cumple la segunda restricción 2x + 5y30 , ya que 2·0 + 5·8 = 40 . Por tanto, el punto B no es un vértice de la región factible.
E no cumple la primera restricción 4x + 5y40 , ya que 4·15 + 5·0 = 60 . Por tanto, el punto E no es un vértice de la región factible.
Los puntos A, C, D y O verifican todas las desigualdades, son los vértices de la región factible.
3) Calcular los valores de la función objetivo en los vértices:
f(A) = f(5,4) = 3·5 + 8·4 = 47
f(C) = f(10,0) = 3·10 + 8· 0 = 30
f(D) = f(0,6) = 3·0 + 8·6 = 48
f(O) = f(0,0) = 3·0 + 8·0 = 0
La solución óptima corresponde al vértice para el que la función objetivo toma el valor máximo. En este caso es el vértice D(0,6).
