A linear programming problem can be defined as the task of maximizing or minimizing a linear function subject to some linear constraints. The constraints can be equalities or inequalities.

What Is It?

Linear programming is a kind of optimization problem where we attempt to maximize (or minimize) an objective function (or linear function) of the decision variables satisfying some linear constraints. Decision variables can be tuned for getting the optimal solution, they are the variable of interest here. Objective function defines the criterion for selecting the best values of the decision variables. Values obtained by the decision variables must satisfy the set of constraints (as there can be more than one constraints).

An Example

Let’s go through an example to get a better idea of what actually linear programming (or linear program) is.

Maximize the value

Base Equation

among all the vectors condition

satisfying the constraints

c3

c4

c5

c6

As this linear program is in two-dimensional space, we can visualise it easily and get a idea of it. Plotting the constrtaint c3 (which is a line in two-dimensional space) we get

Plot 1

Fig. 1 Plot for the equation c3

Fig. 1 shows the set c7 is the half-plane lying below the line c3, similarly, each of the remaining equations defines a half-plane. If we plot all the four constraints in a graph and consider the region where all the 4 constraints overlap, we get a convex polygon (also called as solution space):

Plot 2

Fig. 2 Plot for all the four constraints. The line in red show the edges of the polygon and the black dots show the vertices of the polygon formed by overlapping sections from all the four constraints

Once we have the convex polygon, then the question that arises is, which part of this polygon maximizes the value of Base Equation? For this, let us consider the equation Base Equation. At Cond 1 we get a line passing through the origin as shown in Fig. 3 in black. As we keep on increasing K we have many points that lie on the line and in the solution space (shown by the section of line in green in Fig. 3), all these points are feasible solutions as they satisfy all the constraints but are not the optimal solution (as they don’t attend the max value). The value of K for which we have only one feasible solution is the line which has the optimal value for this problem and hence it is the solution (shown in blue in Fig. 3). Now if we keep on increasing K there will be no value for which all the constraints are satisfied (shown in red in Fig. 3), so, there is only one unique solution in this case. This shows that a linear program may have a single optimal solution, or infinitely many optimal solutions, or none at all.

Plot 3

Fig. 3 Plot showing various values of K for finding the optimal solution

In our previous example, if we update the constraints to:

c3

c4

c5

c6

The graph in this case is:

Plot 4

Fig. 4 Plot when inequalities in all the four constraints is reversed

As can be seen in Fig. 4, there is no region in the graphs where the half-planes formed by all the four constraints overlap. So, this is a linear program which has no feasible solution, and hence no optimal solution. Such a program is called infeasible.

There can be a case where there are feasible solutions but no optimal solution. In our original example, if we remove the first constraint, and reverse the inequality of the second constraint. We have the updated constraints as:

c4

c5

c6

The graph in this case is:

Plot 5 Fig. 5 Plot showing a case when the linear program is unbounded. Arrows point in the direction of all the feasible solutions

As can be seen in Fig. 5, the region where the half-planes formed by all the three constraints overlap starts from the bold black lines in Fig. 5, and extends up to infinity in the direction pointed by the arrows in Fig. 5. In this case, the objective function can attain arbitrarily large numbers, such a linear program is called to be unbounded. In summary, we have seen that a linear program can have one or infinitely many optimal solutions, but it can also be infeasible and unbounded.

Conclusion

The example we chose to solve in this post consisted of only two variables, this made it easy to solve the linear program graphically. However, it will be difficult to even construct a picture of a linear program with four variables. Linear program in practice often has several thousand variables, rather than two or four. This illustration was useful for understanding the procedures and notions of linear programming, but using this method for solving a linear program is not feasible. There are various methods for solving them which we will discuss in future posts.

References

  • J Matousek and B. Gartner, “Understanding and Using Linear Programming”, Springer, 2007
  • Optimization Methods taught by Prof C.V. Jawahar at IIIT Hyderabad