metodo simplex

Método Simplex
•

Construcción de la primera tabla:

Las columnas de la tabla están dispuestas de la siguiente forma: la primera columna de la tabla contiene las variables que se
encuentran en la base (o variables básicas), esto es, aquellas que toman valor para proporcionar una solución; la segunda
columna recoge los coeficientes que dichas variables básicas tienen en la función objetivo(esta columna es llamada Cb); la
tercera muestra el término independiente de cada restricción (P0); a partir de ésta aparece una columna por cada una de las
variables de decisión y holgura presentes en la función objetivo (Pj). Para tener una visión más clara de la tabla, se incluye una
fila que contiene los títulos de cada una de las columnas.
Sobre esta tabla se agregan dos nuevas filas: unade ellas, que lidera la tabla, donde aparecen los coeficientes de las variables
de la función objetivo, y una última fila que recoge el valor la función objetivo y los costes reducidos Zj - Cj.
Los costes reducidos muestran la posibilidad de mejora en la solución Z0. Por este motivo también son llamados valores
indicadores.
Se muestra a continuación el aspecto general de la tabla del métodoSimplex:
Tabla
C1

C2

...

Cn

Base

Cb

P0

P1

P2

...

Pn

P1

Cb1

b1

a11

a12

...

a1n

P2

Cb2

b2

a21

a22

...

a2n

...

...

...

...

...

...

...

Pm

Cbm

bm

am1

am2

...

amn

Z0

Z1-C1

Z2-C2

...

Zn-Cn

Z

Todos los valores incluidos en la tabla vendrán dados por el modelo delproblema salvo los valores de la fila Z (o fila
indicadora). Estos se obtienen de la siguiente forma: Zj = Σ(Cbi·Pj) para i = 1..m, donde si j = 0, P0 = bi y C0 = 0, y en caso
contrario Pj = aij.
Se observa, al realizar el método Simplex, que en esta primera tabla ocupan la base todas las variables de holgura y por ello
(todos los coeficientes de las variables de holgura son 0 en la función objetivo)el valor inicial de Z es cero.
Por este mismo motivo tampoco es necesario realizar los cálculos de los costes reducidos en la primera tabla, pudiéndose
determinar directamente como el cambio de signo de los coeficientes de cada variable en la función objetivo, esto es, -Cj.

•

Condición de parada:

Se cumple la condición de parada cuando la fila indicadora no contiene ningún valornegativo entre los costes reducidos
(cuando el objetivo es la maximización), esto es, no existe posibilidad de mejora.
1

Si no se cumple la condición de parada es necesario realizar una iteración más del algoritmo, esto es, determinar la variable
que se vuelve básica y la que deja de serlo, encontrar el elemento pivote, actualizar los valores de la tabla y comprobar si se
cumple nuevamente lacondición de parada.
Es también posible determinar que el problema no se encuentra acotado y su solución siempre resultará mejorable. En tal
caso no es necesario continuar iterando indefinidamente y se puede finalizar el algoritmo. Esta situación ocurre cuando en la
columna de la variable entrante a la base todos los valores son negativos o nulos.
•

Elección de la variable que entra a labase:

Cuando una variable se vuelve básica, es decir, entra en la base, comienza a formar parte de la solución. Observando los costes
reducidos en la fila Z, se decide que entra a la base la variable de la columna en la que éste sea el de menor valor (o de mayor
valor absoluto) entre los negativos.
•

Elección de la variable que sale de la base:

Una vez obtenida la variable entrante, sedetermina que sale de la base la variable que se encuentre en aquella fila cuyo
cociente P0/Pj sea el menor de los estrictamente positivos (teniendo en cuenta que esta operación se hará únicamente
cuando Pj sea superior a 0).
•

Elemento pivote:

El elemento pivote de la tabla queda marcado por la intersección entre la columna de la variable entrante y la fila de la
variable saliente.
•...