I have the linear program

$$\begin{array}{ll} \text{minimize} & -2x-5y\\ \text{subject to} & 3x + 4y \geq 5\\ & x, y \geq 0\end{array}$$

I can solve it using Simplex algorithm, but I want to find out if there is an easier way to see whether a given linear programming problem has an optimal solution or not.

  • 1
    $\begingroup$ Do you want to determine whether a given linear program is feasible or whether it is feasible but unbounded? $\endgroup$ – Rodrigo de Azevedo May 31 '16 at 15:24

Write the linear program in maximization standard form

$$\begin{array}{ll} \text{maximize} & 2x_1 + 5 x_2\\ \text{subject to} & -3 x_1 - 4 x_2 \leq -5\\ & x_1, x_2 \geq 0\end{array}$$

The dual of this linear program is the following

$$\begin{array}{ll} \text{minimize} & -5y\\ \text{subject to} & - 3 y \geq 2\\ & - 4 y \geq 5\\ & y \geq 0\end{array}$$

From the two inequality constraints, we have $y \leq -5/4$. However, we also have the nonnegativity constraint $y \geq 0$. Hence, the dual linear program is infeasible and, therefore, the primal is either infeasible or unbounded. If one can find a solution using Simplex, then the primal is unbounded.

  • $\begingroup$ So does it mean it has feasible solution but no optimal solution? $\endgroup$ – low iq Jun 1 '16 at 5:08
  • $\begingroup$ @lowiq It means that the minimum can be as low as you want. In other words, the constraints do not constrain all that much. On the other hand, when the LP is infeasible, then the polyhedron defined by the inequalities is empty, as the constraints do constrain too much. $\endgroup$ – Rodrigo de Azevedo Jun 1 '16 at 11:03

The image shows the constraints, the feasible region and a couple of isolines $Z=\text{const}$. From bottom to top: $Z = 10, Z=0, Z=-10, Z=-20$.

graphical solution

We see that the higher the isoline, the lower its value.

The feasible region is the dark purple region in the first quadrant, which is not bounded from above.

This means there is no finite minimum to this problem.

  • 1
    $\begingroup$ How do you draw the graph you have drawn? $\endgroup$ – low iq May 31 '16 at 15:36
  • $\begingroup$ I used GeoGebra. geogebra.org/download You can enter the equations and inequalities directly. $\endgroup$ – mvw May 31 '16 at 15:38

enter image description here Your problem has no finite minimum. To see this, consider the ray $R := \{(x, 0) | x \ge 5 / 3\}$. It is clear that this ray is contained in the constraint set. However, along $R$, the objective function simplifies to $-2x$, which gets cranked to $-\infty$ as you increase $x$.

Hint: All we've done is let the point $(x, y)$ vary along an appropriately chosen boundary of the constraint set.

BTW, plotting code (in few lines of Python):

import numpy as np
import matplotlib.pyplot as plt
x = np.linspace(0, 10, num=50)
ymax = x[-1]
plt.fill_between(x, np.maximum(0., .25 * (5 - 3. * x)), ymax)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.