Minimax linear programming problem |
| |
Authors: | R.K Ahuja |
| |
Affiliation: | Industrial and Management Engineering Programme, Indian Institute of Technology, Kanpur 208016, India |
| |
Abstract: | In this paper, we consider the following minimax linear programming problem: min z = max1 ≤ j ≤ n{CjXj}, subject to Ax = g, x ≥ 0. It is well known that this problem can be transformed into a linear program by introducing n additional constraints. We note that these additional constraints can be considered implicitly by treating them as parametric upper bounds. Based on this approach we develop two algorithms: a parametric algorithm and a primal—dual algorithm. The parametric algorithm solves a linear programming problem with parametric upper bounds and the primal—dual algorithm solves a sequence of related dual feasible linear programming problems. Computation results are also presented, which indicate that both the algorithms are substantially faster than the simplex algorithm applied to the enlarged linear programming problem. |
| |
Keywords: | linear programming linear constraints parametric analysis |
本文献已被 ScienceDirect 等数据库收录! |
|