Parameterizing an Activity Vector in Linear Programming

1 December 1971

journal article
Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research

Vol. 19 (7) , 1632-1646
https://doi.org/10.1287/opre.19.7.1632

Abstract

This paper presents an algorithm that will parameterize an activity vector for a linear programming problem in the following manner. Assume that an optimum feasible basis for a parametric linear programming problem has been obtained for the low-bound value of the parameter θ, set to zero. The algorithm then determines a sequence of critical values θ¹, …, θ^k, …, θ^T, where θ^k ≧ θ^k−1, and a series of bases B¹, …, B^k, …, B^T, in such a way that B^k is optimum feasible for θ^k ≦ θ ≦ θ^k+1 for 1 ≦ k ≦ T − 1 and B^T is either optimum feasible for all θ^T ≦ θ ≦ γ or unbounded or infeasible for 0 ≦ θ − θ^T ≦ ϵ, where ϵ is an arbitrarily small positive number. The essence of the algorithm consists of a series of simple transformations from one optimum feasible basis to another. The algorithm is illustrated with a numerical example.

Keywords

This publication has 0 references indexed in Scilit: