Linear Programming Transformations

1.1k Views Asked by At

What is the process of performing a transformation from a given problem to another linear programming problem such that the transformed problem has an optimal solution iff the initial problem has a solution. I've learned about reductions (working with complexity), and the question seems quite similar, but now that the optimal keyword is included, I know that it can't be exactly like a reduction.

For reference, here is the question that has spurred my own question:

Consider the linear inequalities $L0$ in a finite number of unknowns ${x_1,\ldots,x_n}$ given below:

$$\sum_{j=1}^{n}a_{ij}x_j \le b_i \tag{L0}$$ for $i=1,2,\ldots,m$.

Show how to transform this into a linear program $L1$ so that $L1$ has an optimum solution if and only if $L0$ has a solution. Argue the correctness of your transformation.