Encontrar todas las soluciones básicas factibles en un programa lineal

Question

Dadas las siguientes restricciones

\begin{equation} \begin{split} x_1 &+&x_2&+&x_3&+&x_4&\le 10 \\ x_1&-&x_2&&&&&\le0\\ x_1&&&-&x_3&&&\le 2\\ x_1&+&x_2&&&-&x_4&\le 3\\ x_i&&&&&&&\in\mathbb{R}_{\ge 0} \end{split} \end{equation}

Quiero encontrar todas las soluciones básicas viables. Son los puntos extremos de los poliedros convexos inducidos por estas restricciones. Sin embargo, para resolver este sistema introducimos tantas variables de holgura como desigualdades tengamos. Esto nos lleva a

\begin{equation} \begin{split} x_1 &+&x_2&+&x_3&+&x_4&+&s_1&&&&&&&&= 10 \\ x_1&-&x_2&&&&&&&&+&s_2&&&&&=0\\ x_1&&&-&x_3&&&&&&&&+&s_3&&&= 2\\ x_1&+&x_2&&&-&x_4&&&&&&&&+&s_4&= 3\\ \hat{x}_i&&&&&&&&&&&&&&&&\in\mathbb{R}_{\ge 0} \end{split} \end{equation}

Ahora, una solución básica factible sería $$\hat{x}\equiv (x_1,x_2,x_3,x_4\;|\;s_1,s_2s_3,s_4)=(0,0,0,0\;|\;10,0,2,3)^T$$ Sin embargo,

1. ¿Cómo puedo encontrar todas las soluciones básicas factibles a partir de esta solución básica factible inicial?
2. Estas soluciones básicas factibles son soluciones básicas factibles para el sistema modificado. ¿Cómo puedo obtener soluciones básicas factibles para el problema original?

Answer 1

(Tengo algunas dudas de que esta respuesta sea correcta, pero la dejo aquí para el debate).

1. Con variables reales es probable que tengas un número infinito de soluciones básicas factibles.

2. La solución que muestras es una solución básica factible para el problema original, con todas las variables iguales a cero. Para obtener una solución factible para su problema original, con las variables del problema no nulas: Haga la fase II de Simplex durante algunas veces. En el primer paso se toma una variable del problema como variable básica. A continuación, después de otro las otras variables. Probablemente su solución óptima tiene algunas variables de problema nulas.

¿Por qué quiere tener todas las soluciones básicas viables?

Answer 2

Las soluciones básicas factibles de lo que llamas "problema original" son exactamente las mismas que las soluciones básicas factibles del sistema modificado: al añadir variables de holgura no cambias el conjunto de soluciones; sólo lo incrustas en un espacio de mayor dimensión.

El problema de encontrar todas las soluciones básicas factibles de un poliedro se llama Problema de enumeración de vértices . Para encontrar todos los vértices, puede obtener primero uno arbitrario, llamándolo solución raíz, y luego construir un árbol de soluciones buscando sus vecinos, los vecinos de sus vecinos, etc. Cada vez que obtenga una solución vecina, tendrá que comprobar si se trata de una solución ya obtenida, en cuyo caso abandonará la rama correspondiente.

Avis y Fukuda adaptaron el Algoritmo Criss-Cross para que dicha búsqueda fuera especialmente eficiente. También informan que su búsqueda toma un tiempo polinomialmente acotado, por lo que su problema podría tener mucho menos factible soluciones básicas que todas sus ${8\choose4}$ arbitrario soluciones básicas.