Comprender la forma tableau del algoritmo simplex en LP

Question

Dada la siguiente tabla para un LP máximo

\begin{array}{|c|c|c|c|} \hline & \text{z} & x_1 & x_2 & x_3 & x_4 & x_5 & x_6 & \text{RHS} \\ \hline \text{z} & 1 & c_1 & 0 & c_3 & 0 & 0 & 0 & 13\\ \hline x_2 & 0 & -4 & 1 & a_1 & 0 & a_2 & 0 & \text{b}\\ \hline x_4 & 0 & -1 & 0 & -5 & 1 & -1 & 0 & 3\\ \hline x_6 & 0 & a_3 & 0 & 3 & 0 & -4 & 1 & 2\\ \hline \end{array}

Intento entender cómo funciona este cuadro.

En primer lugar, el cuadro corresponde a la solución básica dada por

$ {\bf x} = (0,b,0,3,0,6)$ Lo que significa que esto es factible, un BFS, sólo si $b \geq 0$ para los que de otro modo $(b\lt0)$ sería inviable. Si quiero que sea degenerado, entonces $ b \gt 0$ .

¿Qué condición debemos imponer a las incógnitas para que el problema sea ilimitado?

Ahora bien, si la solución actual es factible pero la función objetivo puede mejorarse sustituyendo $x_6$ como variable básica por $x_3$ ¿qué condición imponemos a las incógnitas?

Inténtalo:

En primer lugar, necesitamos $b \geq 0$ por viabilidad. Si queremos $x_3$ para salir de la base, pivotamos sobre la columna dada por el vector $(c_3, a_1, -5, 3)^T$ . Para la prueba de proporción, necesitamos encontrar $\min \{c_3/a_1, -5/3, 2/4\}$ lo que significa que $a_1 \neq 0$ para los que, de otro modo, no se puede realizar la prueba de la proporción mínima, y $c_3$ puede ser cualquier cosa. ¿Es esto correcto?

Answer 1

No debe incluir números negativos en la prueba de proporción ( $-5/3$ ), porque crear un pivote en la fila correspondiente daría una variable negativa en la base. Antes de iniciar la prueba de pivote para la columna $x_3$ primero hay que comprobar si $c_3 < 0$ . Mi prueba de relación es un poco diferente a la tuya: $\min\{b/a_1, 2/3\}$ si $a_1 > 0$ y sólo $2/3$ si $a_1 \leq 0$ . En ambos casos, la relación es finita, por lo que después de pivotar, $z$ sigue siendo finito.

Más interesante es la columna de $x_1$ . Si $c_1 < 0$ pero $a_3 \leq 0$ debe añadir $x_1$ a la base, pero no hay ningún término que deba incluirse en la prueba de proporción. Esto significa que las restricciones no limitan $x_1$ . Desde $c_1 < 0$ el valor objetivo puede hacerse arbitrariamente grande.