"Their budget" clearly refers back to the Army. If you wish to consider "Army" to be singular, then you would have to change the possessive adjective for budget to be "its budget." The change has nothing to do with the part about the soldiers. Since the sentence is about a policy (i.e. a general statement about what they Army used to do but then changed), it would not be appropriate to change the sentence to use "the soldier." The previous, but changed, policy clearly applied to multiple people, not just to a single soldier.
Student or Learner