A search for new physics is performed based on all-hadronic events with large missing transverse momentum produced in proton-proton collisions at s=13 TeV. The data sample, corresponding to an integrated luminosity of 2.3 fb-1, was collected with the CMS detector at the CERN LHC in 2015. The data are examined in search regions of jet multiplicity, tagged bottom quark jet multiplicity, missing transverse momentum, and the scalar sum of jet transverse momenta. The observed numbers of events in all search regions are found to be consistent with the expectations from standard model processes. Exclusion limits are presented for simplified supersymmetric models of gluino pair production. Depending on the assumed gluino decay mechanism, and for a massless, weakly interacting, lightest neutralino, lower limits on the gluino mass from 1440 to 1600 GeV are obtained, significantly extending previous limits.