Universidad Industrial de Santander

Escuela de Matemáticas

Metodo Simplex De Dos Fases

Optimizacion

Autores:
Thomas Javier Carrillo Basto - 2200773
Diego Fernando Vargas Mora - 2201292

Abril 2023
¿En que consiste el metodo simplex de dos fases?
Recordemos brevemente las condiciones del metodo simplex que es nuestro punto de partida el cual trabaja
problemas de la siguiente forma:
Max C T X

Ax ≥ b
S.a
x≥0
De lo anterior tenemos que añadir a la restriccion ≤ una variable de holgura para el caso ≥ se va a añadir
una variable de exceso y añadimos una variable artificial y en el caso = solamente se va a añadir una variable
articial, esto con el fin de poder de obtener una solucion basica inicial. En la primera etapa del metodo se
busca tener una solucion basica factible del modelo aumentado que incluya variables artificiales osea que si An
siendo estos las variables artificales entonces r = A1 + A2 + ... + An = 0 sujeto a las restricciones del problema
de programacion lineal inicial, de esto podemos obtener dos resultados uno donde se tenga la solucion basica
factible con las restriccion dada o en lo contrario no obtenerla.

Max C ′T X ′
 ′ ′
A x ≥ b′
S.a
x′ ≥ 0
despues de hacer la primera fase se prosigue a la siguiente fase utilizando el metodo simplex basico con los
resultados de la etapa anterior encontrando la nueva funcion a minimizar sujeta a las restricciones del problema
inicial.
Min Z = r
 ′ ′
A x ≥ b′
S.a
x′ ≥ 0

Ejemplo Método Simplex de Dos Fases

Consideremos el siguiente problema de programación lineal:
Maximizar: Z = 3x1 + 4x2
Sujeto a las siguientes restricciones:

2x1 + x2 ≤ 5
x1 + 2x2 ≤ 4
x1 , x2 ≥ 0

Primera fase
Introducimos variables artificiales a1 y a2 para eliminar las restricciones:

2x1 + x2 + a1 = 5
x1 + 2x2 + a2 = 4
x1 , x2 , a1 , a2 ≥ 0

La función objetivo auxiliar es:

Z ′ = a1 + a2
Aplicamos el método Simplex para resolver el problema auxiliar. Construimos la tabla Simplex inicial:

x1 x2 a1 a2 Solución
2 1 1 0 5
1 2 0 1 4
−2 −3 0 0 0
Seleccionamos la variable de entrada x1 y la variable de salida a1 ya que tiene el valor más negativo en la
fila de la función objetivo. Aplicamos la operación de pivote para hacer que el elemento pivote sea 1:

1
 1 1 5
1 2 2 0 2
1 2 0 1 4
−2 −3 0 0 0
Realizamos operaciones elementales para hacer ceros en la columna de x1 :
1 1 5
1 2 2 0 2
3
0 2 − 21 1 3
2
0 2 −1 0 5
5 5
La solución factible básica inicial es x1 =2,
a1 = y todas las demás variables básicas son cero.
2
Continuamos iterando hasta que la función objetivo auxiliar sea cero:
2
1 0 3 − 13 7
3
0 1 − 31 2
3
1
3
8 1
0 0 3 3 8
En esta iteración, todas las variables artificiales son cero y la función objetivo auxiliar es cero. Pasamos a la
segunda fase.

Segunda fase
Eliminamos las variables artificiales y reescribimos el problema original:
Maximizar: Z = 3x1 + 4x2
Sujeto a las siguientes restricciones:

2x1 + x2 ≤ 5
x1 + 2x2 ≤ 4
x1 , x2 ≥ 0
La tabla Simplex inicial se obtiene considerando solo las variables x1 y x2 :

x1 x2 Solución
2
3 − 31 7
3
− 13 2
3
1
3
Aplicamos el método Simplex como de costumbre. Seleccionamos la variable de entrada x1 y la variable de
salida x2 ya que tiene el valor más negativo en la fila de la función objetivo. Realizamos operaciones elementales
para hacer ceros en la columna de x1 :

1 0 3
0 1 1
La solución óptima es x1 = 3, x2 = 1, y el valor máximo de Z es Z = 3(3) + 4(1) = 11.
Por lo tanto, la solución óptima del problema original es x1 = 3, x2 = 1, y Z = 11.

Ejercicio utiliazndo PHP simplex

vamos a maximizar la siguiente funcion utilizando el programa para entender su funcionamiento
Max 100x1 + 90x2


 6x1 + 4x2 ≥ 24
 20x1 + 8x2 ≤ 15


S.a 3x1 + 2x2 ≥ 5
x2 ≤ 5




x1 , x2 ≥ 0


pasandolo a su modelo aumentado tenemos lo siguiente

6x1 + 4x2 − x3 + x4 = 24





 20x1 + 8x2 + x5 = 15
S.a 3x 1 + 2x2 − x6 + x7 = 5


 x2 + x8 ≤ 5
 x ≥ 0i ∈ {1, 2, 3, 4, 5, 6, 7}

i

2
sabiendo que x3 y x6 son variables de exceso,x5 es una variable de holgura, x4 y x7 variables artificales con esto
tenemos que x4 = 24 − 6x1 − 4x2 + x3 y x7 = 15 − 3x1 − 2x2 + x6 y nuestro r = 39 − 9x1 + 6x2 + x3 + x6 y
mi nueva funcion sera la siguiente Z = 29 − 9x1 − 6x2 + x3 + x6 y construimos la siguiente tabla para aplicar
simplex

Min Z = 29 − 9x1 − 6x2 + x3 + x6

6x1 + 4x2 − x3 + x4 = 24



 20x1 + 8x2 + x5 = 160


S.a 3x1 + 2x2 − x6 + x7 = 15


 x2 + x8 ≤ 5
 x ≥ 0i ∈ {1, 2, 3, 4, 5, 6, 7}

i

Z x1 x2 x3 x4 x5 x6 x7 x8 Xb
Z 1 -9 -6 1 0 0 1 0 0 -39
s1 0 6 4 -1 1 0 0 0 0 24
s2 0 20 8 0 0 1 0 0 0 160
s3 0 3 2 0 0 0 -1 1 0 15
s4 0 0 1 0 0 0 0 0 1 5
utilizando el programa obtenemos el siguiente resultado: