Linear Programming Problem
A linear programming (LP) problem is an optimization problem in which the objective function and all the constraints are expressed as linear functions. Even if just one of them is not a linear function, this problem is not an LP problem. A
linear function is expressed by f(xt ,x2, ■ ■ ■) = axX +a2x2 -----, where aua2,---
are constants.
Figure 11.1 shows the appearance of linear functions. In Fig. 11.1(a), there are two decision variables. The objective function and constraints are depicted by lines. In Fig. 11.1(b), there are three decision variables. The objective function and decision variables are depicted by the planes. Figure 11.2 shows an example
Figure 11.1: Linear programming problem.
Figure 11.2: Example of non-linear programming problem.
of a non-linear programming (NLP) problem, which is not an LP problem; the objective function and constraints 2 and 3 are linear functions, but constraint 1 is not a linear function. Therefore, this problem is not an LP problem.
In general, an LP problem that minimizes an objective function is represented by the following formula.
Equations (11.1 f)-( 11.1 i) provide the ranges of the decision variables. Equations (11.1 f)-( 11.1 i) are not necessary for the LP problem; inclusion of (11.1 f)-( 11.1 i) makes easy to handle the LP problem in a consistent manner. Equations (ll.la)-(l l.li) are called a canonical form of an LP problem with minimization.
An LP problem that maximizes an objective function is represented in the following.
Equations (11.2a)-( 11.2i) are called a canonical form of an LP problem with maximization.
Figure 11.3 shows terminology for an LP problem with two decision variables. A boundary is a constraint that expresses the upper or lower bound of an inequality or equality. The feasible region is an area delineated by the boundaries. A corner point is an intersection of the boundaries.
The concept of LP is explained by an example. For this purpose, we consider an objective function, constraints, and two decision variables that are expressed by xi, and X2, which are mentioned in the following.
To solve an LP problem, the graphical method includes two major steps, which are (i) to determine the solution space that defines the feasible solution and (ii) to determine the optimal solution from the feasible region. Note that the set of values of the variable X[,X2, *3, ....x,„ which satisfies all the constraints, and the non-negative conditions are called the feasible solution of the LP problem. Since the two decision variable xi and X2 are non-negative, the first quadrant of xy-coordinate plane is only one considered. For each constraint, we draw a line.
Figure 11.3: Nomenclature in LP problem.
Figure 11.4: Constraints and corner points of feasible region in LP problem.
Corresponding to each constant, we obtain a shaded region. The intersection of all these shaded regions is the feasible region or feasible solution of the LP.
The above LP problem, mentioned in (11.3a)-(l 1.3e), is solved by the graphical method. We draw straight lines for equations Л| + Юль = 20 and 2x +x2 = 6, and determine the feasible region by considering constraints, as shown in Fig. 11.4. Note that every point in the shaded region is a feasible solution of the above LP problem.
The optimal solution to an LP problem, if it exists, is found by the corner point method, which includes the following steps (i) find the feasible region of the LP problem, (ii) find the co-ordinates of each corner point of the feasible region; these co-ordinates can be obtained by solving the multiple equations provided by constraints, (iii) at each corner point, compute the value of the objective function, (iv) identify the corner point at which the value of the objective function is maximum or minimum depending on the LP problem.
Since the objective function of the above LP problem is to maximize, the optimal solution is obtained at x = 2.10 and x2 = 1.78; the optimal value for objective function is 11.05.
If the number of decision variables and the number of constraints becomes large, the complexity of obtaining all the corner points and their corresponding values of the objective function is significant. This makes the computation times so long that the solution can not be obtained in a practical time. To solve this issue, a more efficient way of finding the optimum solution for an LP problem, called the simplex method, was invented by Dantzig. The detailed information about the simplex method can be found in [257].
