A modified Markov Chain Monte Carlo (MCMC) searching procedure was developed to search for an optimal set of decision variables and optimal feed rate trajectories for recombinant α-amylase expression by Bacillus subtilis ATCC 6051a. The bacterium also synthesizes proteases as undesirable products in fed-batch culture that need to be minimized. To maximize α-amylase productivity, a 14th-order fed-batch model was optimized by integrating Pontryagin’s maximum principle with the Luedeking-Piret equation. The number of iterations and simulations of the proposed searching procedure were statistically examined for accuracy and acceptability of the results. It can be concluded that the proposed searching procedure increased the parameter selection opportunity near the tail ends of redefined triangular distribution. By applying a modified MCMC searching procedure with 1,500 iterations, the predicted α-amylase productivity was improved by 18% in comparison with near-optimum experimental results. This productivity was 3.5% higher than predicted by conventional MCMC optimization.