Condiciones de optimalidad y direcciones en el método Simplex

Question

Estoy tratando de entender las condiciones de optimalidad en Simplex -method, más en el chat aquí -- más concretamente los términos como "coste reducido" es decir $\bar{c}_j=c_j-\bf{c}'_B \bf{B}^{-1} \bf{A}_j$ y el "dirección factible" (p.83 1 ). Estoy atascado en este punto de la página 83:

"Dado que nos interesan las soluciones factibles, necesitamos $\bf A (\bf x + \theta \bf d)=\bf b$ y puesto que $\bf x$ es factible, también tenemos $\bf A \bf x=\bf b$ . Por lo tanto, para que las restricciones de igualdad se cumplan para $\theta>0$ necesitamos $\bf A \bf d=\bf 0$ . Recordemos ahora que $d_j=1$ y que $d_i=0$ para todos los demás índices no básicos $i$ . Entonces,

$$\bf{0}=\bf{A}\bf{d}=\sum_{i=1}^n \bf{A}_i d_i=\sum_{i=1}^m \bf{A}_{B(i)}d_{B(i)}+A_j=\bf{B}\bf{d}_B +\bf{A}_j$$

o imagen aquí .

Preguntas

1. " $d_j=1$ para variables básicas". significa que todas las variables básicas se desplazarán la misma cantidad en la dirección $\bf d$ ¿verdad?

2. La frase " $d_i=0$ para todos los demás índices no básicos $i$ " significa que no nos moveremos en absoluto en la dirección de las variables no básicas, hace ¿no?

Referencias

1 Introducción a la optimización lineal, Bertsimas, 1997

Answer 1

Bertsimas ofrece algunas intuiciones sobre lo que es una "dirección factible". Si quiere permanecer dentro de $P$ a partir de $x$ en la dirección $d$ (dado que $x$ es factible) entonces querrá asegurarse de que puede encontrar un $\theta$ tal que $x + \theta d$ sigue dentro $P$ . Gráficamente, esto significa que $d$ es una dirección factible (partiendo de $x$ ) si puede moverse al menos un poco en la dirección de $d$ a partir de $x$ y permanecer dentro de la región factible $P$ .

Para responder a tus preguntas, tienes que fijarte bien en lo que dice Bertsimas en la página 83. En primer lugar, recuerda que para una solución básica factible en el caso de que $x\geq 0$ que todas las variables no básicas son cero. Bertsimas quiere moverse en una dirección particular $d$ y elige la dirección $d$ donde $d_j=1$ para exactamente una coordenada no básica correspondiente a la variable no básica $x_j$ y $d_j$ =0 para todas las demás coordenadas correspondientes al resto de variables no básicas. Puedes pensar en esto como un movimiento a lo largo de la $x_j$ eje en sentido positivo partiendo de un "origen no básico" donde $x_i=0$ para todos los no básicos $i$ . Para visualizarlo, imaginemos un ejemplo de desplazamiento a lo largo del $x$ -eje desde (0,0,0) si estuvieras en $\mathbb{R}^3$ con ejes $x$ , $y$ y $z$ .

Moviéndose en esta dirección concreta, es muy fácil determinar los valores del $d$ coordenadas correspondientes a las variables básicas. Resulta útil pensar en $x_B$ y $d_B$ como funciones de las variables no básicas. En particular, para su elección de $d$ se obtiene una solución de forma cerrada para $d_B$ que denomina $j$ a dirección básica.

Bertsimas define el coste reducido en la definición 3.2. Intuitivamente, $c_j$ es el coste por unidad de aumento de $x_j$ y $-c_B'B^{-1}A_j$ es el coste del cambio en las variables básicas que surge de aplicar la condición de que $Ax=b$ . El coste reducido de la variable no básica $x_j$ es simplemente $c_j -c_B'B^{-1}A_j$ .

Espero que esto ayude.

Answer 2

La diferencia clave entre las diferentes implementaciones simplex es cómo calculan el $B^{-1}A_j$ . En el Simplex ingenuo, calculan $B^{-1}$ una y otra vez, tiempo-complejidad algo así como $O(m^3)$ . En el simplex revisado, se actualiza directamente el $B^{-1}$ sin recalcular las cosas.

Ahora las variables básicas y no básicas son comunes con todos los métodos. Tienes más variables que ecuaciones. Así que no puedes calcular la inversa. Esto significa que tienes que decidir qué variable tomar en la base para que tengas una matriz cuadrada $B$ para calcular $B^{-1}$ .

Cuando se tiene una variable en la base, se marca por definición con $d_i=1$ y cuando no esté lo marcas con $d_i=0$ donde el $d_i=-B^{-1}A_j$ así que

$$\bar{c}_j=c_j-\bf{c'}_B \bf{B^{-1}} A_j$$

donde $$\bar c_j=c_j+\bf{c_B'}\bf{d_j}$$

para que te muevas en la dirección $\bf{d_j}$ hasta que el coste sea óptimo. En los problemas de forma estándar, te mueves siempre por los lados aka variables activas. Cuando has llegado al óptimo, cambias la base de nuevo hasta que tengas un nuevo óptimo -- en problemas convexos, es suficiente encontrar el óptimo local lo que significa que repites esto hasta que tu función de coste no disminuya más, en problemas convexos el óptimo local es el óptimo global -- la premisa clave detrás de la optimización lineal.

La condición de optimalidad es la condición de coste reducido. Cuando los costes reducidos son positivos, se tiene el óptimo.

Respuestas a sus preguntas

'" $d_j=1$ para variables básicas" significa que todas las variables básicas se desplazarán la misma cantidad en la dirección $d$ ¿verdad?

No, puede ser, pero no siempre es cierto. Si tuvieras la misma cantidad de ecuaciones y variables, obtendrías un punto. Ahora tienes más variables que ecuaciones. Esto significa que debes poner algunas variables a ceros, no básicas, para obtener el $B^{-1}$ . Puedes moverte a lo largo de las direcciones factibles determinadas por los vectores básicos, pero te mueves de uno en uno. Así es como yo lo entiendo: te mueves de un punto extremo a otro a lo largo de una dirección cada vez. Por supuesto, puede haber algunos métodos en los que elijas alguna dirección heurística, pero los métodos Simplex básicos van de un punto extremo a otro hasta el óptimo. Fíjese en $\bar c_j=c_j+\bf{c_B'}\bf{d_j}$ que el cambio de dirección está determinado por los costes reducidos y la base por lo que las variables de base afectan al movimiento.

La frase " $d_i=0$ para todos los demás índices no básicos i" significa que no nos moveremos en absoluto en la dirección de las variables no básicas, ¿verdad?'

Sí. Fíjate que esta situación es diferente a la situación cuando las vuelves a poner en la base. Cuando tienes las variables en la base, te mueves a lo largo de su factible direcciones.