Resource allocation among competing activities: A lexicographic minimax approach (Q1092812)

The minmax linear programming problem \[ \min_{x}\max_{j}a_ j[d_ j-x_ j)/d_ j] \] subject to \[ \sum^{n}_{j=1}a_{ij}x_ j\leq b_ i,\quad i=1,2,...,m,\quad 0\leq x_ j\leq d_ j \] is examined and a fast non-simplex algorithm developed which requires at most \(2n(m+1)\) divisions and multiplications. Then the idea of a lexicographic minmax algorithm for solving the original problem with the objective function \[ lex\min_{x}\{\max_{j}a_ j[(d_ j-x_ j)/d_ j] \] is proposed that improves the result from the point of view of the vector of weighted deviations. The proposed algorithms promise to be effective for a given class of large scale resource allocation and production planning problems.