Resolución de un programa lineal con el algoritmo simplex, matriz no de rango completo

Question

Tengo esa matriz llamada A:

\begin{bmatrix} 1 & 3 &1&0&0 \\ -2&-2&0&1&0 \\ 2&4&0&0&1 \end{bmatrix}

Necesito resolver el LP : $$ \min: -x_1 - x_2$$ y $$Ax = ( 2,2,4)^T$$

Esta matriz no es de rango completo. Entonces la única manera de resolver ese problema es crear un problema equivalente con una matriz de rango completo? Aquí por ejemplo :

$$ \min \{ (c,-c) (x^+,x^-)^T : \begin{bmatrix} A & -A \\ -I& 0 \\ 0& -I \end{bmatrix} (x^+,x^-)^T \leq (b, 0,0)^T \} $$

pero no sé cómo resolver un problema con $x^+$ y $x^-$ . ¿Tiene un ejemplo?

Así que mi pregunta es cómo resolver tal problema, y si usted recomendaría mi método, cómo lo utilizas, especialmente en lo que se refiere a la $x^+$ parte.

También he hecho esa pregunta en informática, pero no estaba seguro de si es una pregunta de informática o de matemáticas. (cf. https://cs.stackexchange.com/questions/111189/solving-a-linear-program-with-simplex-algorithm-matrix-not-full-rank )

Answer 1

Claro, puedes hacer el algoritmo simplex en él. Después de dividir sus variables en sus partes no positivas y no negativas, se obtiene el siguiente cuadro simplex: \begin{array}{cccccccccc|c} \fbox{1} & 3 &1&0&0&-1&-3&-1&0&0&2\\ -2&-2&0&1&0&2&2&0&-1&0&2\\ 2&4&0&0&1&-2&-4&0&0&-1&4\\ \hline -1&-1&0&0&0&1&1&0&0&0&0 \end{array} Esto es en forma canónica factible con variables básicas $\ x_3^+,x_4^+\ $ y $\ x_5^+\ $ Así que tienes razón en eso. Sin embargo, como hay entradas negativas en la fila del objetivo, sabes que la solución básica no es óptima. Para proceder con el algoritmo simplex Puedes elegir pivotar sobre la primera o la segunda columna, y una fila apropiada. Si usted elige la primera fila y la primera columna, el nuevo tableau es: \begin{array}{cccccccccc|c} 1 & 3 &1&0&0&-1&-3&-1&0&0&2\\ 0&4&2&1&0&0&-4&-2&-1&0&6\\ 0&-2&-2&0&1&0&\fbox{2}&2&0&-1&0\\ \hline 0&2&1&0&0&0&-2&-1&0&0&2 \end{array} Ahora, al pivotar sobre la tercera fila y la séptima columna se obtiene el siguiente cuadro: \begin{array}{cccccccccc|c} 1 & 0 &-2&0&\frac{3}{2}&-1&0&2&0&-\frac{3}{2}&2\\ 0&0&-2&1&2&0&0&2&-1&-2&6\\ 0&-1&-1&0&\frac{1}{2}&0&1&1&0&-\frac{1}{2}&0\\ \hline 0&0&-1&0&1&0&0&1&0&-1&2 \end{array} Dado que todas las entradas de la décima columna de este cuadro son negativas, esto indica que existen soluciones factibles que pueden hacer que el objetivo sea arbitrariamente pequeño. En efecto, si se toma $\ x_5^-\ $ para ser la única variable no básica con un valor distinto de cero, el cuadro le dice que los siguientes valores para las variables básicas \begin{eqnarray} x_1^+&=& 2+\frac{3x_5^-}{2}\\ x_4^+&=& 6+2x_5^-\\ x_2^-&=&\frac{x_5^-}{2} \end{eqnarray} le dará una solución factible para cualquier valor de $\ x_5^-\ $ . Pero el objetivo tiene valor $\ -x_1^+ + x_2^- = -2-x_5^- \ $ que puede hacerse arbitrariamente pequeño eligiendo $\ x_5^-\ $ suficientemente grande.

En términos de las variables originales, lo que esto dice es que $\ x_1=2-\frac{3x_5}{2}\ $ , $\ x_2=\frac{x_5}{2}\ $ , $\ x_3=0\ $ y $\ x_4=6-2x_5\ $ es una solución factible para cualquier valor de $\ x_5\ $ que se puede comprobar fácilmente sustituyendo estos valores en la ecuación $$ \begin{bmatrix} 1& 3 &1&0&0\\ -2&-2&0&1&0\\ 2&4&0&0&1 \end{bmatrix}\begin{bmatrix}x_1\\ x_2\\ x_3\\ x_4\\ x_5\end{bmatrix}=\begin{bmatrix}2\\2\\4\end{bmatrix}\ ,$$ y el objetivo $-x_1-x_2 = -2 + x_5\ $ puede hacerse arbitrariamente pequeño eligiendo $\ x_5\ $ suficientemente pequeño.

Explicación de la edición: La discusión que sigue -en particular el hecho de que los precios sombra deben ser no negativos- me alertó del hecho de que originalmente había utilizado la convención inversa a la habitual para los signos de las entradas en la fila del objetivo. Aunque esto no afectaba a la corrección de la solución, podría haber sido confuso para cualquiera que no fuera consciente de las ecuaciones representadas por el cuadro. Por lo tanto, ahora he invertido todos los signos de esa fila, y de las condiciones requeridas para la optimalidad, de modo que el procedimiento sigue ahora la convención más estándar.