Minimax linear programming problem (Q1075944): Difference between revisions

The author is concerned with the following minimax problem; \[ (MLPP)\quad \min z=\max_{1\leq j\leq n}\{c_ jx_ j\}\quad subject\quad to\quad Ax=g,\quad x\geq 0 \] where \(c_ j\geq 0\) and \(x_ j\) are scalars, x is a column vector with components \(x_ j\), g is a column vector with elements \(g_ j\geq 0\) and A is a \(m\times n\) matrix of rank m. It is known that MLPP can be transformed into a linear programming problem by introducing n additional constraints. The author notes that the additional constraints can be considered implicitly by treating them as parametric upper bounds. Following this approach two procedures are proposed, a parametric algorithm and a primal-dual algorithm. Computational results showing the convenience of using both algorithms are given.