Programación Lineal-Teo Coronado

Método analítico

o Método de los vértices

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 ellos.

Veámoslo con un ejemplo:

Maximizar	Z = f(x,y) = 3x + 8y
sujeto a:	4x + 5y 40
	2x + 5y 30
	x 0 , y 0

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 + 5y 30 , 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 + 5y 40 , 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).

Este método es el menos utilizado de los tres que veremos