Metodo Simplex Y Dual

METODO SIMPLEX

El método Simplex es un procedimiento iterativo que permite mejorar la solución de la función objetivo en cada paso. El proceso concluye cuando no es posible continuar mejorando dicho valor, es decir, se ha alcanzado la solución óptima (el mayor o menor valor posible, según el caso, para el que se satisfacen todas las restricciones).

El método Simplex se basa en la siguiente propiedad: si la función objetivo Z no toma su valor máximo en el vértice A, entonces existe una arista que parte de A y a lo largo de la cual el valor de Z aumenta.

Será necesario tener en cuenta que el método Simplex únicamente trabaja con restricciones del problema cuyas inecuaciones sean del tipo "≤" (menor o igual) y sus coeficientes independientes sean mayores o iguales a 0. Por tanto habrá que estandarizar las restricciones para que cumplan estos requisitos antes de iniciar el algoritmo del 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: una de 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étodo Simplex:

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

Z Z0 Z1-C1 Z2-C2 ... Zn-Cn

Todos los valores incluidos en la tabla vendrán dados por el modelo del problema 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 valor negativo entre los costes reducidos (cuando el objetivo es la maximización), esto es, no existe posibilidad de mejora.

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 la condició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 la base:

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, se determina 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.

Actualización de la tabla:

Las filas correspondientes a la función objetivo y a los títulos permanecerán inalteradas en la nueva tabla. El resto de valores deberán calcularse como se explica a continuación:

En la fila del elemento pivote cada nuevo elemento se calcula como:

Nuevo Elemento Fila Pivote = Anterior Elemento Fila Pivote / Pivote.

En el resto de las filas cada elemento se calcula:

Nuevo Elemento Fila = Anterior Elemento Fila - (Anterior Elemento Fila en Columna Pivote * Nuevo Elemento Fila Pivote).

De esta forma se consigue que todos los elementos de la columna de la variable entrante sean nulos salvo el de la fila de la variable saliente cuyo valor será 1. (Es análogo a utilizar el método de Gauss-Jordan para resolver sistemas de ecuaciones lineales).

Método de las Dos Fases

El método de las Dos Fases se utiliza cuando aparecen variables artificiales en la forma canónica o estándar del problema. La primera fase trata de resolver el problema auxiliar Z' de minimizar la suma de las variables artificiales y conseguir que sea cero (con objeto de evitar incongruencias matemáticas). Una vez resuelto este primer problema, y siempre y cuando el resultado sea el esperado, se reorganiza la tabla resultante para utilizarla en la segunda fase sobre el problema original.

En caso contrario el problema no es factible, es decir, no tiene solución y no será necesario continuar con la segunda fase.

FASE 1

Esta primera fase es muy similar al método Simplex, con la excepción de la construcción de la primera tabla, además de la necesidad de estudiar el resultado obtenido para determinar si se desarrolla la segunda fase.

En tal caso, la última tabla de esta fase

...