Linear Programming, Solution of Linear Programming Problems

Get unlimited access to the best preparation resource for IAS : Get complete video lectures from top expert with unlimited validity: cover entire syllabus, expected topics, in full detail- anytime and anywhere & ask your doubts to top experts.

Download PDF of This Page (Size: 193K)

Solution of Linear Programming Problems

  • In the previous section we have seen the problems in which the number of relations are not equal to the number of variables and many of the relations are in the form of inequation (i.e., or ) to maximise (or minimise) a linear function of the variables subject to such conditions.

  • Now the question is how one can find a solution for such problems?

  • To answer this questions, let us consider the system of equations and inequations (or inequalities).

The system of equations and inequations

The System of Equations and Inequations

The system of equations and inequations

  • We know that represents a region lying towards the right of y-axis including the y-axis.

  • Similarly, the region represented by, lies above the x-axis including the x-axis.

  • The question arises: what region will be represented by and simultaneously.

The Graph of x≥0, y≥0

The Graph of X≥0, Y≥0

The Graph of x≥0, y≥0

  • Obviously, the region given by , will consist of those points which are common to both and . It is the first quadrant of the plane.

  • Next, we consider the graph of the equation. For this, first we draw the line and then find the region satisfying.

  • Usually we choose and calculate the corresponding value of and choose and calculate the corresponding value of to obtain two sets of values (This method fails, if the line is parallel to either of the axes or passes through the origin. In that case, we choose any arbitrary value for x and choose y so as to satisfy the equation).

  • Plotting the points and and joining them by a straight line, we obtain the graph of the line as given in the Fig. below.

Plotting the points (0,4) and (8,0)

Plotting the Points (0,4) and (8,0)

Plotting the points (0,4) and (8,0)

  • We have already seen that and represents the first quadrant. The graph given by lies towards that side of the line in which the origin is situated because any point in this region will satisfy the inequality.

  • Hence the shaded region in the Fig. represents and simultaneously.

Represents x≥0,y≥0 and x+2y≤8

Represents X≥0,Y≥0 and X+2y≤8

Represents x≥0,y≥0 and x+2y≤8

  • Similarly, if we have to consider the regions bounded by and , then it will lie in the first quadrant and on that side of the line in which the origin is not located.

  • The graph is shown by the shaded region, in Fig.

The graph is shown by the shaded region

The Graph is Shown by the Shaded Region

The graph is shown by the shaded region

The shaded region in which all the given constraints are satisfied is called the feasible region.

Feasible Solution:

A set of values of the variables of a linear programming problem which satisfies the set of constraints and the non-negative restrictions is called a feasible solution of the problem.

Optimal Solution:

A feasible solution of a linear programming problem which optimises its objective functions is called the optimal solution of the problem.

In order to find a graphical solution of the linear programming problem, following steps be employed.

Step 1: Formulate the linear programming problem.

Step 2: Graph the constraints (inequalities), by the method discussed above.

Step 3: Identify the feasible region which satisfies all the constraints simultaneously. For less than or equal to’ constraints the region is generally below the lines and ‘for greater than or equal to’ constraints, the region is above the lines.

Step 4: Locate the solution points on the feasible region. These points always occur at the vertex of the feasible region.

Step 5: Evaluate the objective function at each of the vertex (corner point)

Step 6: Identify the optimum value of the objective function.

Example:

Minimise the quantity subject to the constraints

Solution:

The objective function to be minimised is subject to the constraints

First of all we draw the graphs of these inequalities, which is as follows:

The graphs of these inequalities

The Graphs of These Inequalities

The graphs of these inequalities

As we have discussed earlier that the region satisfied by and is the first quadrant and the region satisfied by the line along with , will be on that side of the line in which the origin is not located.

Hence, the shaded region is our feasible solution because every point in this region satisfies all the constraints.

Now, we have to find optimal solution. The vertex of the feasible region are and .

The value of at

The value of at

Take any other point in the feasible region say etc. We see that the value of is minimum at.

Developed by: