Duda genérica sobre el método Simplex

Question

Supongamos que estamos trabajando en una LPP de la siguiente forma:

\begin{equation*} \begin{split} \min \quad &z = f(x) \\[.15cm] s.a. \quad &Ax \leqslant b \\[.15cm] &x \geqslant 0 \end{split} \end{equation*} ¿Existe algún tipo de restricción si trabajamos con un vector $b$ que tiene componentes negativos? Quiero decir, ¿está bien proceder como de costumbre cuando estamos trabajando con un negativo $b$ ¿Vector? En caso negativo, ¿cómo procederíamos en este supuesto?

Gracias de antemano por cualquier ayuda.

Answer 1

El método simplex se complica cuando $b$ tiene componentes negativos.

En general, la lógica del método es la siguiente: se empieza por una solución básica factible (bfs) y luego se pasa a una bfs adyacente pero mejor, hasta encontrar la solución óptima. El principal problema es: ¿por dónde empezar?

Si $b \ge 0$ la respuesta es fácil. Se empieza en el punto $x=0$ . (Esto es siempre un bfs; en el tableau, corresponde a hacer que todas las variables de holgura sean variables básicas).

Si $b$ tiene algunos componentes negativos, entonces $x=0$ ya no es factible. En ese caso, ni siquiera sabemos si el sistema de desigualdades $Ax \le b \land x \ge 0$ ¡tiene alguna solución! Encontrar un punto de partida para el método simplex es un problema tan difícil como encontrar después una solución óptima.

La solución habitual es una de varias métodos simplex bifásicos . Aquí, empezamos creando un programa lineal auxiliar a partir del original. Se garantiza que el LP auxiliar tiene un bfs inicial. Cuando se resuelve de forma óptima, el resultado nos dará un bfs para el LP original (y entonces procedemos a partir de ahí), o mostrará que el LP original es inviable.