Solución óptima para un problema de programación Lineal

Question

Si tenemos un posible espacio para un determinado LPP (problema de programación lineal), ¿cómo es que su solución óptima se encuentra en uno de los puntos de vértice de la gráfica de la solución? (Estoy aquí de que se trate sólo con aquellos LPP que tienen una solución gráfica con más de una esquina/punto final.)

Me pidieron que tomar esto como un lema en la clase, pero tengo curiosidad acerca de la prueba. Cualquier ayuda es sinceramente apreciada.

Answer 1

Es una instancia especial de la general es el siguiente teorema:

El máximo de una función convexa $f$ en un compacto conjunto convexo $S$ se alcanza en un punto extremo de $S$.

Un punto extremo de un conjunto convexo $S$ es un punto en $S$ que no se encuentran en cualquier segmento de línea que une dos puntos de $S$. En su caso, el "rincón de los puntos de la gráfica de la solución" son los únicos puntos extremos de la región factible. Es fácil ver que la región factible de un LPP es convexa. No siempre es compacto, y algunos LPP, de hecho, no tienen ninguna solución, a pesar de tener un vacío de la región factible. El lineal de la función objetivo es claramente convexo. Si está minimizada, en lugar de maximizada, esto puede ser reformulada como la maximización de la negativa de la función objetivo.

Me gusta bastante el citado teorema, porque pone de manifiesto que la optimización puede conducir a problemas de resultados para una gran clase de situaciones (porque la solución en la frontera de la región factible, será factible en virtud de las perturbaciones, por lo que no es una solución sólida). Es también similar a la de bang-bang principio en un control óptimo.

Answer 2

En dos dimensiones el caso de la optimización lineal (programación lineal) se especifica como sigue: Encontrar los valores de $(x, y)$ de manera tal que el objetivo de la función $$g(x, y) = a x + b y \;\;\; (Eq. 1)$$ se maximiza (o minimiza) sujeto a las desigualdades lineales $$a_1 x + b_1 y + c_1 \ge 0 \;\; (or \le 0) $$ $$a_2 x + b_2 y + c_2 \ge 0 \;\; (or \le 0) $$ $$ ... $$

Cada una de estas desigualdades lineales define una mitad del plano delimitada por la línea obtenida mediante la sustitución de la desigualdad por la igualdad. La solución de $(x, y)$ que maximiza la función objetivo debe estar en la intersección de todos estos halfplanes que es, obviamente, un polígono convexo. Este polígono se llama región factible. El valor de la función objetivo en un punto de $(x, y)$ de la región factible, ser $m$ $$g(x, y) = a x + b y = m \;\;\; (Eq. 2)$$ El valor de $m$ de la meta de la función obviamente no lo cambio cuando nos movemos $(x, y$) en la línea definido por (Eq. 2). Pero el valor de $g()$ será mayor cuando aumenta la $m$. Esto lleva a una nueva línea que es paralela a (E. p. 2). Podemos hacer esto tan largo como la línea que contiene al menos un punto de la región factible. Llegamos a la conclusión de que el máximo de la función objetivo se alcanza en un punto extremo de la región factible, que - por un polígono convexo es un vértice (o un borde cuando el objetivo de la línea es paralela a la restricción de la línea que va a través de la extrema vértice).

Answer 3

Jiri la respuesta que da la explicación intuitiva. Formalmente, el hecho de que la solución óptima se encuentra en un punto extremo, es una consecuencia del teorema de representación de poliedros y el hecho de que la región factible de un problema de programación lineal es un poliedro.

La representación teorema dice que un poliedro es convexo de la suma de sus vértices además de la combinación lineal no negativa de su extrema direcciones. Más formalmente, si $S$ es un poliedro, $\{{\bf v}_1, {\bf v}_2, \ldots, {\bf v}_k\}$ es el conjunto de puntos extremos de $S$, e $\{{\bf d}_1, {\bf d}_2, \ldots, {\bf d}_m\}$ es el conjunto de los extremos de las direcciones de las $S$ ${\bf x} \in S$ si y sólo si ${\bf x} = \sum_{i=1}^k \alpha_i {\bf v}_i + \sum_{i=1}^m \beta_i {\bf d}_i$, $\sum_{i=1}^k \alpha_i = 1$ y $\alpha_i, \beta_i \geq 0$.

Entonces tenemos

Teorema: Si $S$ es la región factible de algún problema de programación lineal con función objetivo $z = {\bf c}^T {\bf x}$ 1) $z$ alcanza su valor óptimo en algún vértice de $S$, 2) el problema de programación lineal es inviable, o 3) el problema de programación lineal es ilimitado.

Prueba: en Primer lugar, asumir, sin pérdida de generalidad, que el LP quiere maximizar $z$. Si el LP es inviable, a continuación, $S$ está vacía. De lo contrario, existe al menos un punto de ${\bf x} \in S$. Si $S$ tiene una desenfrenada extrema dirección ${\bf d}_i$ tal que ${\bf c}^T {\bf d}_i > 0$, el LP es ilimitado, como podemos hacer que el valor de ${\bf c}^T \left(\sum_{i=1}^k \alpha_i {\bf v}_i + \beta_i {\bf d}_i\right)$ tan grande como se desee mediante el aumento de $\beta_i$. Supongamos, entonces, que el ${\bf c}^T {\bf d}_i \leq 0$ por cada $i$. Deje ${\bf v}^*$ ser el vértice con el mayor valor de la función objetivo. Entonces, para ${\bf x} \in S$, $${\bf c}^T {\bf x} = {\bf c}^T \left(\sum_{i=1}^k \alpha_i {\bf v}_i + \sum_{i=1}^m \beta_i {\bf d}_i \right) = \sum_{i=1}^k \alpha_i ({\bf c}^T {\bf v}_i) + \sum_{i=1}^m \beta_i ({\bf c}^T {\bf d}_i) \leq \sum_{i=1}^k \alpha_i ({\bf c}^T {\bf v}^*) = {\bf c}^T {\bf v}^*.$$ Thus $z$ must attain its optimal value at ${\bf v}^*$.