Chapter at a Glance
1. Linear Programming Problems – Problems which concern with finding the minimum or maximum value of a linear function Z (called objective function)of several variables (say x and y), subject to certain conditions that the variables are non-negative and satisfy a set of linear inequalities (called linear constraints)are known as linear programming problems.
2. Objective Function – A linear function z = ax + by, where a and b are constants, and z has to be maximised or minimised according to a given set of conditions, is called a linear objective function.
3. Decision Variables – In the objective function z = ax + by, the variables x, yare said to be decision variables.
4. Linear Constraints – The restrictions in the form of linear inequalities interms of decision variables of the linear programming problem are called constraints. The condition x >= 0, y >= 0 are known as non–negative restrictions.
Note: Note that in linear constrains, each inquality contains either >= or <= sign only (Not > or <)
5. Feasible Region – The common region determined by drawing the graphs of all the constraints including non–negative constraints x,y >= 0 of linear programming problem is known as feasible region (or solution region)
6. Feasible Solution – Each points within and on the boundary of the feasible region represents feasible solution of constraints.
7. Optimal Solution – Any point in the feasible region that gives the optimal value(maximum or minimum) of the objective function is called an optimal solution.
8. Theorem 1 Let R be the feasible region for a linear programming problem and let Z = ax + by be the objective function. When Z has an optimal value(maximum or minimum), then optimal value (maximum or minimum value) of Z must occur at a corner point of the feasible region.
9. Theorem 2 Let R be the feasible region for a linear programming problem, and let Z = ax + by be the objective function. If R is bounded then the objective function Z has both maximum and minimum value on R and each of the seoccurs at a corner point of R.
10. To solve the LPP –
(i) First of all identify the objective functions which is actually a function whose value is to be maximise or minimise. Then identify the decision variables, which are actually the variables in term of which objective function can be expressed. Name these variables as x and y. Now write the objective function in terms of x and y. After that write the constraits in terms of x and y.
(ii) Draw the graph of each linear constraints. The non-negative linear constraints x > = 0 and y>= 0 combinely represent the first quadrant including the non-negative parts of x and y-axis of xoy-plane. To draw the graph of each of the other linear constraints, convert each of the linear in equation (or inequality) into its corresponding linear equation by changing the sign ‘³’ or ‘£’ into ‘=’. Take a corresponding linear equation and draw its graph, which will be always a straight line.
If the linear equation constaints a constant terms it is better to convert the linear equation in intercept from which intersect the x-axis at a i.e., (a, 0) an y-axis at b i.e., (0, b). After joining these two points (a, 0) and (0, b), you will get the line.
Now take a point which is in either side of the line (i.e., not on the line). If the line does not pass through the origin O(0, 0), then for convinience, we generally take the origin. Now put the coordinates of this point in the linear inequation of which corresponding linear equation is taken. If the coordinates satisfy the linear inequation, then the half plane on that side of the line (drawn) in which the point whose coordinates are put into the inequation including the line (drawn) is the graph of the inequation under consideration. If the coordinates of the point considered do not satisfies the inequation considered then the half plane on the other side of the line including the line itself is the graph of the inequality considered. Draw the graph of other remaining inequality of the constraint in the same way. Indentify the common region of the graph of all the inequality of the constraints. This common region is the feasible region.
(iii) Find the coordinates of the corners of the feasible region.
(iv) Put the coordinates of each corner point of the feasible region in the objective function and find the value of the objective function.
The coordinates of the corner point(s) which maximize or minimize the objective function are the point of optimal solution of the given problem.
Related Articles: