On Relaxation of Infeasibility of Linear Programming Constraints

Abstract

In an optimization of a real system planning or design, when a prescribed set of constraints is found infeasible, it needs to be modified somehow. This paper presents a method for making an in feasible set of linear programming constraints feasible. Infeasibility is detected in phase I of the two-phase simplex procedure. Numerical data in the final simplex tableau of phase I are used for relaxing in feasibility. The relaxation is carried out by modifying some upper or lower bounds of the constraints. A sufficient condition for the relaxation is derived. The method allows a wide variety of modifications of the constraints. Thus, it could effectively be used in a practical linear programming design.