¿Cómo utilizar el método simplex para programas lineales?

Question

Creo que me falta algo importante en el algoritmo Simplex, porque no consigo que funcione.

Por lo que deduzco, hay tres pasos por iteración, dada una matriz para un programa lineal en forma estándar:

• Busque términos negativos en la fila de la función objetivo.
• Si encuentras uno, busca el pivote si lo hay.
• Tenemos que transformar el pivote en un 1 y todos los demás términos de la columna en 0 utilizando operaciones de fila.
• Repita

---

Pues bien:

$$min z = x_2-x_1 + 1$$

sujeto a

$$\begin{cases}-2x_1 + x_2 \le 2\\ x_1 - 2x_2 \le 2\\ x_1+x_2 \le 5\\ x_i \le 0 \forall i \end{cases}$$

---

Exigimos el formulario estándar. Convertimos las desigualdades en ecuaciones:

$$\begin{cases}-2x_1 + x_2 + x_3 + 0 + 0= 2\\ x_1 - 2x_2 + 0 + x_4 + 0 = 2\\ x_1+x_2 + 0 +0 + x_5= 5\\ x_i = 0 \forall i \end{cases}$$

Tenemos la siguiente matriz, donde la última fila representa la función objetivo:

$$\begin{bmatrix} -2 & 1 & 1 & 0 & 0 & 2 \\ 1 & -2 & 0 & 1 & 0 & 2 \\ 1 & 1 & 0 & 0 & 1 & 5 \\ -1 & 1 & 0 & 0 & 0 & z - 1 \end{bmatrix}$$

Procedemos con el algoritmo Simplex.

---

Primera iteración

Paso 1 : Busca términos negativos en la función objetivo. La primera columna tiene un $-1$ .

Paso 2 : Encuentra el pivote. Es el primer $1$ en la primera columna.

Paso 3 : Requerimos que el pivote sea $1$ y que el resto de la columna sea $0$ . Lo hacemos con operaciones de fila elemental:

$$\begin{bmatrix} -2 & 1 & 1 & 0 & 0 & 2 \\ [1] & -2 & 0 & 1 & 0 & 2 \\ 1 & 1 & 0 & 0 & 1 & 5 \\ -1 & 1 & 0 & 0 & 0 & z - 1 \end{bmatrix}$$

$$2r_2 + r_1$$

$$\begin{bmatrix} 0 & -3 & 1 & 2 & 0 & 6 \\ [1] & -2 & 0 & 1 & 0 & 2 \\ 1 & 1 & 0 & 0 & 1 & 5 \\ -1 & 1 & 0 & 0 & 0 & z - 1 \end{bmatrix}$$

$$r_3 + r_4$$

$$\begin{bmatrix} 0 & -3 & 1 & 2 & 0 & 6 \\ [1] & -2 & 0 & 1 & 0 & 2 \\ 1 & 1 & 0 & 0 & 1 & 5 \\ 0 & 2 & 0 & 0 & 1 & z + 4 \end{bmatrix}$$

$$-r_2 + r_3$$

$$\begin{bmatrix} 0 & -3 & 1 & 2 & 0 & 6 \\ [1] & -2 & 0 & 1 & 0 & 2 \\ 0 & 3 & 0 & -1 & 1 & 3 \\ 0 & 2 & 0 & 0 & 1 & z + 4 \end{bmatrix}$$

---

Segunda iteración

Paso 1 : Busca términos negativos en la función objetivo. No hay ninguno. El algoritmo termina.

---

... Pero sé que esto es incorrecto, porque según la respuesta del ejercicio, debería haber acabado con una matriz de la forma

$$\begin{bmatrix} 0 & 0 & 1 & 1 & 1 & 9 \\ 1 & 0 & 0 & 1/3 & 2/3 & 4 \\ 0 & 1 & 0 & -1/3 & 1/3 & 1 \\ 0 & 0 & 0 & 2/3 & 1/3 & z + 2 \end{bmatrix}$$

Y hecho tres iteraciones. Por desgracia, los detalles de esas iteraciones no se muestran, así que no estoy seguro de lo que hice mal.

Answer 1

Si yo fuera tú, cambiaría a otro libro de texto/notas para obtener instrucciones más claras. Utilizar variables con valores negativos es una fuente de desorden. Cambiaré el problema original

$\min z = x_2-x_1 + 1$ tal que

$$\begin{cases} -2x_1 + x_2 &\le 2 \\ x_1 - 2x_2 &\le 2\\ x_1 + x_2 &\le 5\\ x_i &\le 0 \forall i \tag{*} \end{cases}$$

a

$\min z = x_1-x_2 + 1$ tal que

$$\begin{cases} 2x_1 - x_2 &\le 2 \\ -x_1 + 2x_2 &\le 2\\ -x_1 - x_2 &\le 5\\ x_i &\ge 0 \forall i \end{cases}$$

Obsérvese que la tercera restricción es redundante así que lo omitiré. debido a mi pereza para simplificar el asunto.

Es fácil de resolver gráficamente

$\min z = x_1-x_2 + 1$ tal que

$$\begin{cases} 2x_1 - x_2 &\le 2 \\ -x_1 + 2x_2 &\le 2\\ x_i &\ge 0 \forall i \tag{#}. \end{cases}$$

No obstante, ya que pides una solución utilizando el método simplex, utilizaré este algoritmo. Sea $s_1$ y $s_2$ son las variables de holgura para la primera y la segunda restricción en $(\#)$ respectivamente. Por lo tanto, tenemos la siguiente tabla simplex.

$$\begin{equation*} \begin{array}{rrrrr|l} & x_1 & x_2 & s_1 & s_2 & \text{RHS} \\ \hline s_1 & 2 & -1 & 1 & 0 & 2 \\ s_2 & -1 & 2 & 0 & 1 & 2 \\ \hline z & -1 & 1 & 0 & 0 & 1 \\ \end{array} \end{equation*}$$

En la última fila, cambio $z=x_1-x_2+1$ a $z-x_1+x_2 = 1$ . El coeficiente de $z$ no se cambia nunca, así que lo omito para ahorrar tinta. Escribo el cuadro de esta manera para que se pueda leer directamente el valor de la función objetivo en la esquina inferior derecha (razón: en el $z$ de la tabla, tenemos un coeficiente cero para las variables básicas ( $s_1$ y $s_2$ ); para las variables no básicas ( $x_1$ y $x_2$ ), su valor es cero), y la solución factible básica en el RHS.

Por tus cálculos, supongo que entiendes por qué el elemento pivote tiene que ser positivo (por viabilidad de la solución básica). Como hemos supuesto que todas las variables (excepto $z$ ) es no negativo (para facilitar las cosas), todas las entradas del lado derecho (excepto la esquina inferior derecha) son no negativas.

Ahora, olvida la regla "busca términos negativos en la fila de la función objetivo" . Sólo tiene que tratar esto como operaciones de fila de pivote (necesita $\mathbf{e}_i$ y el coeficiente de las variables básicas sea cero en la fila de la función objetivo de la tabla), y recuerda que la esquina inferior derecha es el valor de la función objetivo que quieres minimizar. ¿Qué vas a hacer? Harás una operación de fila pivote para mejorar el valor de la función objetivo.

En el siguiente cuadro, sólo incluyo los elementos esenciales para ver las cosas con claridad.

$$\begin{equation*} \begin{array}{rr|l} & \text{a non-basic variable} & \text{RHS} \\ \hline \text{a basic variable} & \heartsuit > 0 & \spadesuit \ge 0 \\ \hline z & \clubsuit & \text{obj. fct. val.} \end{array} \end{equation*}$$

Después de cada operación de fila pivotante, tendrá

$$\begin{equation*} \text{new obj. fct. val.} = \text{obj. fct. val.} - \frac{\spadesuit\clubsuit}{\heartsuit} \end{equation*}$$

Ahora, está claro que

• en un problema de maximización, se necesita $\clubsuit < 0$ para que el nuevo valor de la función objetivo sea mayor que el original;
• en un problema de minimización (en este caso), se necesita $\clubsuit > 0$ para que el nuevo valor de la función objetivo sea menor que el original.

Por lo tanto, elegimos $x_2$ y $s_2$ como variables de entrada y salida respectivamente.

$$\begin{equation*} \begin{array}{rrrrr|l} & x_1 & x_2 & s_1 & s_2 & \text{RHS} \\ \hline s_1 & 2 & -1 & 1 & 0 & 2 \\ s_2 & -1 & 2^* & 0 & 1 & 2 \\ \hline z & -1 & 1 & 0 & 0 & 1 \\ \end{array} \end{equation*}$$

$$\begin{equation*} \begin{array}{rrrrr|l} & x_1 & x_2 & s_1 & s_2 & \text{RHS} \\ \hline s_1 & \frac32 & 0 & 1 & \frac12 & 3 \\ x_2 & -\frac12 & 1 & 0 & \frac12 & 1 \\ \hline z & -\frac12 & 0 & 0 & -\frac12 & 0 \\ \end{array} \end{equation*}$$

Por lo tanto, $(x_1,x_2,s_1,s_2)=(0,1,3,0)$ es una solución básica factible para $(\#)$ . Por lo tanto, la solución de $(*)$ es $(x_1,x_2) = (0,-1)$ con el valor de la función objetivo $z=0$ .

---

Puede comprobarlo utilizando un solucionador LPP. Aquí hay un ejemplo usando GNU Octave.

octave:1> c=[-1 1]'; A=[-2 1; 1 -2; 1 1]; b=[2 2 5]';
octave:2> [x_min,z_min]= glpk(c,A,b,[-inf -inf]',[0,0]',"UUU","CC")
x_min =

   0
  -1

z_min = -1

En la función objetivo c me he saltado el término $+1$ para simplificar el código. Como resultado, $(x_1,x_2)=(0,-1)$ es la solución óptima para $(*)$ .