Método analítico de evaluación en los vértices

▶ Reproducir en la pizarra
1

Fundamento y justificación del método algebraico

El método analítico de evaluación en los vértices (también denominado método de los puntos extremos) es el procedimiento algebraico canónico para resolver problemas de programación lineal en dos variables sin necesidad de depender de la apreciación visual del trazado gráfico.

Su validez descansa en el Teorema Fundamental de la Programación Lineal: dado que la región factible \(\mathcal{R}\) es un conjunto convexo y la función objetivo \(z(x, y) = ax + by\) es lineal y continua, los valores extremos absolutos (máximo y mínimo) se alcanzan necesariamente en la frontera del recinto, y de manera obligatoria en al menos uno de sus vértices.

2

Protocolo operativo canónico en cuatro pasos

1. Determinación analítica de todos los vértices: Resolver los sistemas lineales \(2 \times 2\) formados por las combinaciones de pares de rectas frontera que delimitan la región, verificando la factibilidad de cada punto de corte hallado.

2. Tabulación y sustitución directa: Sustituir de manera ordenada las coordenadas cartesianas \((x_i; y_i)\) de cada vértice en la expresión algebraica de la función objetivo \(z(x, y)\)

3. Comparación numérica: Identificar el mayor de los valores obtenidos (máximo absoluto) o el menor de ellos (mínimo absoluto).

4

Emisión de la

Conclusión

Interpretar la solución óptima indicando tanto el valor numérico óptimo alcanzado como el punto o puntos donde se produce.

3

Garantía y unicidad de la solución

- Si el valor óptimo aparece en un único vértice, la solución óptima es estrictamente única.

- Si el valor óptimo coincide exactamente en dos vértices adyacentes distintos, el problema presenta infinitas soluciones óptimas distribuidas a lo largo del segmento que une ambos vértices.

Ejemplo 1: Maximización en un cuadrilátero factible con cuatro vértices
Explicación

Calculamos sistemáticamente el valor de la función objetivo en los cuatro vértices de un cuadrilátero.

Maximizar la función objetivo \(z(x, y) = 40x + 30y\) en la región factible cuyos vértices calculados son \(A = (0; 0)\), \(B = (5; 0)\), \(C = (4; 3)\) y \(D = (0; 6)\)

PASO 1

Tabulamos los vértices del polígono convexo:

Disponemos de los cuatro puntos extremos:

$$A(0; 0), B(5; 0), C(4; 3), D(0; 6)$$
PASO 2

Evaluamos la función objetivo en cada vértice:

$$z(A) = z(0, 0) = 40(0) + 30(0) = 0$$
$$z(B) = z(5, 0) = 40(5) + 30(0) = 200$$
$$z(C) = z(4, 3) = 40(4) + 30(3) = 160 + 90 = 250$$
$$z(D) = z(0, 6) = 40(0) + 30(6) = 180$$
PASO 3

Comparamos los valores obtenidos:

$$0 < 180 < 200 < 250$$

El valor numérico más alto es 250.

Conclusión

La solución óptima es única y se alcanza en el vértice \(C = (4; 3)\), proporcionando un valor máximo de \(z = 250\)

Ejemplo 2: Minimización de costes en una región poligonal cerrada
Explicación

Determinamos el coste mínimo evaluando los vértices de un pentágono factible.

Minimizar la función de coste \(C(x, y) = 5x + 8y\) en el recinto delimitado por los vértices \(A = (2; 6)\), \(B = (7; 2)\), \(C = (8; 5)\), \(D = (5; 8)\) y \(E = (3; 8)\)

PASO 1

Evaluamos la función objetivo en los cinco vértices candidatos:

$$C(A) = C(2, 6) = 5(2) + 8(6) = 10 + 48 = 58$$
$$C(B) = C(7, 2) = 5(7) + 8(2) = 35 + 16 = 51$$
$$C(C) = C(8, 5) = 5(8) + 8(5) = 40 + 40 = 80$$
$$C(D) = C(5, 8) = 5(5) + 8(8) = 25 + 64 = 89$$
$$C(E) = C(3, 8) = 5(3) + 8(8) = 15 + 64 = 79$$
PASO 2

Comparamos los valores calculados para localizar el mínimo absoluto:

$$51 < 58 < 79 < 80 < 89$$

El menor valor de coste registrado es 51.

Conclusión

El coste mínimo es de 51 unidades (\(C = 51\)) y se alcanza de forma única en el punto \(B = (7; 2)\)

Ejemplo 3: Resolución completa: desde el sistema hasta la tabla de vértices
Explicación

Resolvemos un problema completo de programación lineal hallando los vértices y evaluando la función.

Maximizar \(z(x, y) = 2x + 3y\) sujeta a las restricciones:

$$\begin{cases} x + y \le 8 \\ 2x + y \le 10 \\ x \ge 0, \quad y \ge 0 \end{cases}$$
PASO 1

Hallamos los vértices resolviendo las inter

secciones correspondientes:

Vértice en el origen:

$$O = (0; 0)$$

Corte de \(2x + y = 10\) con el eje \(X\) (\(y = 0\)):

$$x = 5 \implies A = (5; 0)$$

Corte de \(x + y = 8\) con el eje \(Y\) (\(x = 0\)):

$$y = 8 \implies B = (0; 8)$$

Inter

sección entre las dos rectas frontera secantes:

$$\begin{cases} x + y = 8 \\ 2x + y = 10 \end{cases} \implies (2x + y) - (x + y) = 10 - 8 \implies x = 2 \implies y = 6 \implies C = (2; 6)$$
PASO 2

Evaluamos la función objetivo en los cuatro vértices reales:

$$z(O) = z(0, 0) = 2(0) + 3(0) = 0$$
$$z(A) = z(5, 0) = 2(5) + 3(0) = 10$$
$$z(B) = z(0, 8) = 2(0) + 3(8) = 24$$
$$z(C) = z(2, 6) = 2(2) + 3(6) = 4 + 18 = 22$$
PASO 3

Comparamos los valores: \(0 < 10 < 22 < 24\). El máximo es 24.

Conclusión

La solución óptima es el vértice \(B = (0; 8)\), alcanzando un valor máximo de \(z = 24\)

Ejemplo 4: Detección de coincidencia de valor en dos vértices consecutivos
Explicación

Identificamos analíticamente la presencia de un empate en el valor óptimo de dos vértices.

Maximizar la función objetivo \(z(x, y) = 3x + 3y\) en el polígono cuyos vértices son \(A = (1; 1)\), \(B = (6; 1)\), \(C = (4; 5)\) y \(D = (1; 5)\)

PASO 1

Evaluamos la función objetivo en los cuatro vértices:

$$z(A) = 3(1) + 3(1) = 6$$
$$z(B) = 3(6) + 3(1) = 18 + 3 = 21$$
$$z(C) = 3(4) + 3(5) = 12 + 15 = 27$$
$$z(D) = 3(1) + 3(5) = 3 + 15 = 18$$

Observemos que si modificamos ligeramente la función a \(z'(x, y) = 4x + 4y\), en los vértices del lado horizontal superior entre \((1; 5)\) y \((4; 5)\):

Para una función paralela a un lado, por ejemplo \(z''(x, y) = 2x + y\) en un segmento donde ambos puntos arrojen igual valor:

Si dos vértices contiguos \(V_1\) y \(V_2\) arrojan exactamente el mismo valor máximo \(z^*\), cualquier combinación convexa \(P = \lambda V_1 + (1-\lambda)V_2\) con \(\lambda \in [0; 1]\) satisface \(z(P) = z^*\)

Conclusión

En el problema evaluado, el máximo estricto es 27 en el vértice \(C = (4; 5)\). En caso de empate entre dos vértices adyacentes, la solución se extiende a todos los puntos de la arista frontera común.

Ejemplo 5: Optimización con coeficientes negativos en la función objetivo
Explicación

Evaluamos vértices cuando la función objetivo contiene términos con signos negativos.

Maximizar \(z(x, y) = 10x - 4y\) sobre el triángulo factible con vértices en \(A = (2; 1)\), \(B = (5; 2)\) y \(C = (3; 6)\)

PASO 1

Evaluamos la función objetivo en cada vértice considerando el signo negativo:

$$z(A) = z(2, 1) = 10(2) - 4(1) = 20 - 4 = 16$$
$$z(B) = z(5, 2) = 10(5) - 4(2) = 50 - 8 = 42$$
$$z(C) = z(3, 6) = 10(3) - 4(6) = 30 - 24 = 6$$
PASO 2

Comparamos los valores numéricos resultantes:

$$6 < 16 < 42$$

El valor máximo absoluto es 42 y el mínimo absoluto es 6.

Conclusión

La función alcanza su máximo absoluto en el vértice \(B = (5; 2)\) con un valor de 42 (\(z_{\max} = 42\)), y su mínimo en el vértice \(C = (3; 6)\) con un valor de 6 (\(z_{\min} = 6\)).