Interdicting the activities of a linear program — A parametric analysis

摘要

In this paper, we consider two interdiction problems for a linear program. These generalize the problems proposed by Fulkerson and Harding and by Golden for the shortest path problem. These problems also provide equilibrium analysis for a system in which some kind of resource can be used to change the original equilibrium. We show that these two problems can be solved simultaneously by performing parametric analysis of a linear program with bounded variables. We also consider their applications for the interdiction of flow networks. In particular, we propose an algorithm for solving the related parametric network flow problem.