Why is one optimal value greater than or equal to the other one here?

37 Views Asked by At

Let the first program be $$\min \frac{c^Tx + d}{e^Tx+f} \text{ subject to }\{Gx \le h, Ax = b\}$$

It can be transformed to equivalent linear program:

$$\min (c^Ty + dz) \text{ subject to } \{Gy - hz \ge 0, Ay - bz = 0, e^Ty + fz = 1, z \ge 0\}$$

If $x$ is feasible in the first one, then $y = \frac{x}{e^Tx + f}, z = \frac{1}{e^Tx + f}$ is feasible in the second one. It follows that the optimal value of the original program is greater than or equal to the optimal value of the transformed program.

Can someone explain why the optimal value of the original program is greater than or equal to the optimal value of the transformed program?