Álgebra Del método símplex

4.3 Álgebra del método símplex

Paso inicial

El método símplex puede comenzar en cualquier solución factible en un vértice (solución básica factible), de manera que se escoge una que sea conveniente. Antes de tomar en cuenta las variables de holgura, esta elección es el origen (con todas las variables originales iguales a cero) o (x_1,x_2) = (0,0) para el ejemplo. En consecuencia, después de introducir las variables de holgura, las variables originales son variables no básicas y las variables de holgura son las variables básicas de la solución básica factible inicial. Esta elección se muestra en el siguiente sistema de ecuaciones en el que las variables básicas se escribieron en negritas:

x_1 + x_3 =4

〖2x〗_2 + x_4 =12

〖3x〗_1+〖2x〗_2 +x_5 =18

Cuando las variables no básicas son iguales a cero, el resto de la solución se lee como si no existieran: entonces, x_3=4,x_4=12 y x_5=18, de ahí que la solución básica factible inicial resulta igual a (0, 0, 4, 12, 18).

Nótese que la razón por la que esta solución se puede leer e inmediato es porque cada ecuación tiene sólo una variable básica, que tiene coeficiente +1, y que esta variable básica no aparece en ninguna otra ecuación. Pronto se verá que cuando el conjunto de variables básicas cambia, el método símplex utiliza un procedimiento algebraico (el de eliminación de Gauss) para poner las ecuaciones en esta forma tan conveniente para leer igual todas las soluciones factibles básicas subsecuentes. Esta forma se llama la forma apropiada de eliminación gaussiana.

Paso iterativo

En cada iteración el método símplex se mueve de la solución factible básica actual a una solución factible básica adyacente mejor. Este movimiento consiste en convertir una variable no básica (llamada variable básica entrante) en variable básica, y al mismo tiempo convertir una variable básica (llamada variable básica que sale) en variable no básica, y en identificar la nueva solución básica factible.

Pregunta 1. ¿Cuál es el criterio para seleccionar la variable básica entrante?

Los candidatos para la variable básica entrante son las n variables no básicas actuales. La que se elija, cambiará su estado de no básica a básica, por lo que su valor amentará de cero a algún valor positivo y las otras se mantendrán en nivel cero. Como se requiere que la nueva solución básica factible sea mejor (un valor más grande de Z) que la actual, es necesario que la tasa de cambio e Z al aumentar el valor de la variable básica entrante sea positivo. Usando la ecuación (0) para expresar Z sólo en términos de las variables no básicas, el coeficiente de cada una es las tasa a la que Z cambiaría si se incrementara el valor de esa variable. Se elige como variable básica entrante la que tiene el coeficiente positivo mayor, ya que es la que hace que Z se incremente a la tasa más rápida.

Como aclaración, los dos candidatos para variable básica entrante en el ejemplo son variables no básicas actuales x_1 y x_2. Como la función objetivo ya está escrita sólo en términos de estas variables, puede analizarse tal como está:

Z= 〖3x〗_1+ 〖5x〗_2

Ambas variables tienen coeficientes positivos, así que al aumentar cualquiera de ellas, el valor de Z aumenta pero con tasas distintas de tres y cinco por cada unidad de aumento en la variable. Como 3 < 5, la elección para la variable básica entrante es x_2. Así, se incrementará el valor de x_2 y el de x_1 se dejará en cero.

Pregunta 2. ¿Cómo se identifica la variable básica que sale?

Ignorando las variables de holgura, aumentar el valor de x_2 mientras que el de x_1 se mantiene en cero significa un movimiento hacia arriba por el eje x_2 en la figura 4.1. La solución factible en el vértice adyacente, (0, 6), se alcanza al detener el movimiento en la primera línea de restricción que se encuentra (〖2x〗_2=12). Ahí se debe detener aunque existe otra solución en un vértice en (0, 9), ya que seguir más arriba significa obtener una solución no factible que viola la restricción 〖2x〗_2≤12.

Para el problema en forma aumentada, las soluciones factibles deben satisfacer tanto el sistema de ecuaciones de restricciones funcionales como las restricciones de no negatividad sobre todas las variables (variables originales y de holgura). Al aumentar el valor de x_2 mientras se mantiene el de x_1 igual a cero (no básica), una o todas las variables básicas actuales (x_3,x_4,x_5) deben cambiar sus valores para mantener satisfecho el sistema de ecuaciones. Algunas de estas variables decrecerán al crecer x_2. La solución básica factible adyacente se alcanza cuando la primera variable básica (variable básica que sale) llega a cero. Ahí se debe detener para evitar la no factibilidad. Entonces, una vez elegida la variable básica entrante, la variable básica que sale no es cuestión de elección. Debe ser la variable básica actual cuya restricción de ni variable básica entrante, como se ilustra enseguida.

En el ejemplo, las posibilidades para la variable básica que sale son las variables básicas actuales x_3,x_4,x_5. Los cálculos para identificar cuál debe ser la variable básica que sale se resumen en la tabla 4.1. Como x_1 es una variable no básica, x_1=0 en la segunda columna de la tabla 4.1. La tercera columna indica que: 1) x_3 sigue siendo no negativa (= 4), sin importar cuánto aumente x_2; 2) x_4 = 0 si x_2=6; y 3) x_5=0 si x_2=9. Así, los números calculados de la tercera columna sin las cotas superiores para x_2 antes de que la variable básica correspondiente en la primera columna se vuelva negativa. Como x_4 (la variable de holgura para la restricción 〖2x〗_2≤12) impone la menor cota superior sobre x_2, la variable básica que sale es x_4, de manera que x_4=0 (no básica) y x_2=6 (básica) en la nueva solución factible.

Pregunta 3. ¿Cómo puede identificarse la nueva solución básica factible en una forma conveniente?

Después de identificar las variables básicas entrante y saliente (incluyendo el nuevo valor de la variable básica entrante), todo lo que se necesita hacer para identificar la nueva solución básica factible es encontrar los nuevos valores de las variables básicas restantes. Estos valores podrían obtenerse directamente

...