programacion lineal

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).
Normalizar las restricciones.
Se convierten las inecuaciones en ecuaciones agregando variables deholgura, 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 = 423·X1 + X2 + X5 = 24
Igualar la función objetivo a cero.
Z - 3·X1 - X2 - 0·X3 - 0·X4 - 0·X5 = 0
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 P0el término independiente y el resto devariables 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 se calcula 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
0
24
3
1
0
0
1
Z
 
0
-3
-2
0
0
0Condició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 enla 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 pasos de forma iterativa.
Elección de la variableentrante 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 seabá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 de la columna pivote, siempre que ambos elementos...