¿Por qué ocurre el máximo / mínimo de programación lineal en un vértice?

Question

Estoy en la escuela secundaria y me han dicho que el máximo/mínimo de una programación lineal ocurre en el vértice. Para más información, consulta el capítulo aquí. Para mayor comodidad, aquí pongo un extracto relevante:

Ahora, vemos que cada punto en la región factible cumple con todas las restricciones, y dado que hay infinitos puntos, no es evidente cómo deberíamos encontrar un punto que dé un valor máximo de la función objetivo. Para manejar esta situación, utilizamos los siguientes teoremas que son fundamentales para resolver problemas de programación lineal. Las pruebas de estos teoremas están más allá del alcance del libro.

Teorema 1 Sea R la región factible (polígono convexo) para un problema de programación lineal y sea Z = ax + by la función objetivo. Cuando Z tiene un valor óptimo (máximo o mínimo), donde las variables x e y están sujetas a restricciones descritas por desigualdades lineales, este valor óptimo debe ocurrir en un punto de esquina (vértice) de la región factible.

Teorema 2 Sea R la región factible para un problema de programación lineal, y sea Z = ax + by la función objetivo. Si R está acotada, entonces la función objetivo Z tiene tanto un valor máximo como un valor mínimo en R y cada uno de estos ocurre en un punto de esquina (vértice) de R

Busqué en Wikipedia aquí para obtener información sobre Vértices óptimos (y rayos) de poliedros:

"..entonces el valor óptimo siempre se alcanza en ... Este principio subyace al algoritmo simplex para resolver programas lineales.."

Pero no pude entenderlo. ¿Alguien puede explicar? Puede ser útil agregar que he estudiado Cálculo básico.

Answer 1

Supongamos que tu región factible se ve como se muestra a continuación:

Vamos a suponer que estamos maximizando la función objetivo $C=ax+by$

Observa que, para diferentes valores de C, obtienes diferentes líneas rectas con intercepciones en y variables pero que tendrán la misma pendiente:

Solo las líneas que atraviesan la región factible cumplen todas las restricciones dadas porque puedes encontrar valores de x, y que caigan tanto en la región factible como en la función objetivo.

A partir de la segunda imagen, es obvio que el valor máximo de $ax+by=C$ se da cuando la intersección en y de estas líneas factibles es máxima. En consecuencia, el vértice A da el valor máximo para la función objetivo.

Answer 2

Algo de álgebra lineal básica es esencial para esto. ¿Ya has estudiado un poco de eso?

Supongamos que tienes el punto $p$ dentro de tu politopo de puntos factibles dentro de $\mathbb{R}^n$, y digamos que quieres maximizar la función objetivo. La función objetivo es lineal, dada por algún $c \in \mathbb{R}^n$. Si $v \in \mathbb{R}^n$ y $c \cdot v = 0$, entonces $p+v$ tiene el mismo valor objetivo que $p$. En otras palabras, no se mejora $p$ moviéndolo en una dirección ortogonal a la función objetivo.

Si $v$ tiene alguna componente paralela a $c$, entonces $p+v$ será estrictamente mejor o estrictamente peor que $p. Por lo tanto, si eres el punto $p$ y quieres mejorar tu valor objetivo, entonces debes buscar una dirección $v$ en la cual puedas moverte que tenga alguna componente positiva paralela a $c$, es decir, $c \cdot v > 0$. Es posible que no puedas caminar exactamente en la dirección de $c$ porque una cara del politopo puede interponerse en el camino. Pero es posible que puedas caminar en una dirección con componente $c$ positiva. La única forma en que podrías quedar atascado es que, para cada dirección de mejora posible, alguna cara te bloquee. En otras palabras, para cada $v$ en el semiespacio abierto $\{v:c\cdot v > 0\}$, el punto $p+v$ se encuentra fuera del politopo factible. Esto solo puede ocurrir si ya te encuentras en un vértice, o te encuentras en una cara de soluciones óptimas paralela al hiperplano $\{v:c\cdot v = 0\}$. Si no te encuentras en un vértice, entonces mientras te quedas en el hiperplano, puedes caminar hacia un vértice sin cambiar tu valor objetivo.

En la explicación anterior, he utilizado la limitación de la región factible: Sin limitación, podría ser posible caminar en una dirección mejorando para siempre, o podría ser posible caminar a lo largo de una cara de soluciones óptimas sin llegar nunca a un vértice. También he utilizado la convexidad: Si no me encuentro en una solución óptima, siempre existirá una dirección de mejora.

Answer 3

Supongamos que no estás en un vértice de la región convexa. Si estás en el interior estricto de la región convexa, entonces puedes moverte un poco en la dirección que desees. En particular, si tu objetivo es $ax + by$, entonces puedes moverte un poco en la dirección de $(a,b)$ y obtener un valor de función objetivo más alto. De manera similar, si estás en un borde, sea $(a_1,b_1)$ un vector paralelo al borde. Entonces, el producto punto de $(a_1,b_1)$ con $(a,b)$ es mayor o igual a cero, o menor o igual a cero. En el primer caso, puedes moverte a lo largo del borde en dirección $(a_1,b_1)$ hasta alcanzar un vértice y obtener al menos una solución tan buena, y en el segundo caso, puedes moverte a lo largo del borde en dirección $(-a_1,-b_1)$ hasta alcanzar un vértice y obtendrás al menos una solución tan buena. Juntando todas las piezas, obtienes que algún vértice proporciona la solución óptima.

Answer 4

Si estamos buscando un extremo de la función $z=ax+by$, entonces generalmente tomamos primeras derivadas parciales, que son iguales a $a$ y $b respectivamente. Como estamos considerando una función lineal en un polígono, entonces el sistema

$$\left\{\begin{aligned}&\frac{\partial z}{\partial x}=0 \\ &\frac{\partial z}{\partial y}=0 \\ \end{aligned}\right.$$ no tiene soluciones (si $a, b\ne 0$) en ningún punto regular. Por lo tanto, deberíamos buscar el extremo en el borde (en casos más generales, el trozo del borde puede ser una solución)

Answer 5

Imagina que tu región factible es una caja (posiblemente en dimensiones altas). Dado que la función objetivo es lineal, interpretémosla como la dirección de la gravedad. Suelta una canica en la caja y rodará hacia una esquina, correspondiente a una solución óptima.

Para ser más sutil, la canica puede no necesariamente rodar hacia una esquina. En este caso, o la región factible es ilimitada (y la canica cae para siempre), o hay infinitas soluciones óptimas, por ejemplo, cuando toda una cara de la caja está plana en el suelo, por así decirlo (es decir, perpendicular a la dirección de la función objetivo). En este último caso, aún puedes hacer rodar la canica hacia cualquiera de las esquinas de esa cara.