This paper discusses the plastic limit analysis of a truss with some deficient structural components for evaluating redundancy of the truss. Given the upper bound for the number of deficient members, we consider uncertainty in the locations of deficient members. In other words, the set of deficient members is not specified in advance. Then we attempt to find the worst scenario of deficiency, in which the limit load factor attains the minimum value. It is shown that this optimization problem can be formulated as a mixed integer linear programming problem, which can be solved with an algorithm with guaranteed global convergence.