Embutido

Ejemplo (parte 1): método Simplex
Resolver mediante el método simplex el siguiente problema:
Maximizar
Z = f(x,y) = 3x + 2y
sujeto a:
2x + y ≤ 18
 
2x + 3y ≤ 42
 
3x + y ≤ 24
 
x ≥ 0 , y ≥ 0
Se consideran las siguientes fases:
1. Realizar un cambio de variables y normalizar el signo de los términos independientes.
Se realiza un cambio en la nomenclatura de las variables.Estableciéndose la correspondencia siguiente:
x pasa a ser X1
y pasa a ser X2
Como los términos independientes de todas las restricciones son positivos no es necesario hacer nada. En caso contrario habría que multiplicar por "-1" en ambos lados de la inecuación (teniendo en cuenta que esta operación también afecta al tipo de restricción).
2. Normalizar las restricciones.
Se convierten las inecuacionesen ecuaciones agregando variables de holgura, exceso y artificiales según la tabla siguiente:
Tipo de desigualdad
Tipo de variable que aparece
≥
- exceso + artificial
=
+ artificial
≤
+ holgura
En este caso se introduce una variable de holgura (X3, X4 y X5) en cada una de las restricciones del tipo ≤, para convertirlas en igualdades, resultando el sistema de ecuaciones lineales:
2·X1 +X2 + X3 = 18
2·X1 + 3·X2 + X4 = 42
3·X1 + X2 + X5 = 24
3. Igualar la función objetivo a cero.
Z - 3·X1 - X2 - 0·X3 - 0·X4 - 0·X5 = 0
4. Escribir la tabla inicial del método Simplex.
La tabla inicial del método Simplex está compuesta por todos los coeficientes de las variables de decisión del problema original y las de holgura, exceso y artificiales agregadas en el paso 2 (en las columnas,siendo P0 el término independiente y el resto de variables Pi coinciden con Xi), y las restricciones (en las filas). La columna Cb contiene los coeficientes de las variables que se encuentran en la base.
La primera fila está formada por los coeficientes de la función objetivo, mientras que la última fila contiene el valor la función objetivo y los costes reducidos Zj - Cj.
La última fila secalcula como sigue: Zj = Σ(Cbi·Pj) para i = 1..m, donde si j = 0, P0 = bi y C0 = 0, y en caso contrario Pj = aij. Aunque al tratarse de la primera tabla del método Simplex y ser todos los Cb nulos se puede simplificar el cálculo, y por esta vez disponer Zj = -Cj.
Tabla I . Iteración nº 1



3
2
0
0
0
Base
Cb
P0
P1
P2
P3
P4
P5
P3
0
18
2
1
1
0
0
P4
0
42
2
3
0
1
0
P5
024
3
1
0
0
1
Z

0
-3
-2
0
0
0

5. Condición de parada.
Si el objetivo es la maximización, cuando en la última fila (fila indicadora) no existe ningún valor negativo entre los costes reducidos (columnas P1 en adelante) se alcanza la condición de parada.
En tal caso se llega al final del algoritmo ya que no existe posibilidad de mejora. El valor de Z (columna P0) es la soluciónóptima del problema.
Otro caso posible es que en la columna de la variable entrante a la base todos los valores son negativos o nulos. Esto indica que el problema no se encuentra acotado y su solución siempre resultará mejorable. Ante esta situación no es necesario continuar iterando indefinidamente y también se puede dar por finalizado el algoritmo.
De no ser así, se ejecutan los siguientes pasosde forma iterativa.
6. Elección de la variable entrante y saliente de la base.
Se determina en primer lugar la variable que entra en la base. Para ello se escoge la columna cuyo valor en la fila Z sea el menor de entre todos los negativos. En este caso sería la variable X1 (P1) de coeficiente -3.
Si existiesen dos o más coeficientes iguales que cumplan la condición anterior (caso de empate),entonces se optará por aquella variable que sea básica.
La columna de la variable que entra en la base se llama columna pivote (en color verde).
Una vez obtenida la variable que entra en la base, se procede a determina cual será la variable que sale de la misma. La decisión se toma en base a un sencillo cálculo: dividir cada término independiente (columna P0) entre el elemento correspondiente...