An inequality sorting algorithm for a class of linear programming problems (Q2367804): Difference between revisions

A new algorithm is proposed and investigated for the interval programming problem (1): \(\max\{b'x:c\leq Ax\leq d\}\). The authors assume that the problem is feasible and has a bounded optimal solution \(x=A^ + e+Pz\), \(A\) is an \((m\times n)\)-matrix, the rank of \(A\) is \(r\), \(r=m\). Here \(P\) is a projection operator, and \(A^ +\) is the Moore-Penrose inverse. The proposed algorithm normalizes the inequalities of (1), arranges the normalized inequalities in ascending order of the right-most transformed elements \(d_ i\), seeves out the first \(r\) linear independent inequalities, computes the solution of (1) with these \(r\) inequalities , and then checks which inequalities are not satisfied on the left-most inequality. The algorithm eliminates the unsatisfied inequalities, arranges the remaining inequalities in ascending order, and once again computes the solution of (1).