Calculating some inverse linear programming problems (Q1923457): Difference between revisions

For the general linear programming problem \[ \min \{cx/Ax = b,\;x \geq 0\} \] the inverse problem is expressed as \[ \min \bigl\{ |c-\widetilde c|/ \widetilde c\in F(x^0) \bigr\} \] where \(c,x \in \mathbb{R}^n\), \(b \in \mathbb{R}^m\), \(A\) is an \(m \times n\) matrix, \(x^0\) is a feasible solution, \[ F(x^0) = \bigl\{\widetilde c \in \mathbb{R}^n/ \min \{\widetilde cx/Ax=b,\;x\geq 0\} = \widetilde cx^0 \bigr\} \] and \(|\dots|\) is the \(l_1\) norm. A method for solving this inverse problem is suggested which is based on the optimality conditions for linear programming problems. For the application of the given method to inverse minimum cost flow or assignment problems is found that this method yields strongly polynomial algorithms.