The problem related to the computation of bounds on plastic deformations for structures in plastic shakedown condition (alternating plasticity) is studied. In particular, reference is made to structures discretized by finite elements constituted by elastic perfectly plastic material and subjected to a special combination of fixed and cyclic loads. The load history is known during the steady-state phase, but it is unknown during the previous transient phase; so, as a consequence, it is not possible to know the complete elastic plastic structural response. The interest is therefore focused on the computation of bounds on suitable measures of the plastic strain which characterizes just the first transient phase of the structural response, whatever the real load history is applied. A suitable structural model is introduced, useful to describe the elastic plastic behaviour of the structure in the relevant shakedown conditions. A special bounding theorem based on a perturbation method is proposed and proved. Such theorem allows us to compute bounds on any chosen measure of the relevant plastic deformation occurring at the end of the transient phase for the structure in plastic shakedown; it represents a generalization of analogous bounding theorems related to the elastic shakedown. Some numerical applications devoted to a plane steel structure are effected and discussed.