What is Linear Programming?
In here, the variables are non-negative and satisfy a set of linear inequalities (called linear constraints) and the problems have the goal to find the optimal value (maximum or minimum) of a linear function of several variables (called objective function) with respect to the conditions. Variables are sometimes called decision variables and are non-negative in nature.
Feasible region (or solution region) is referred to the common region represented by all the boundaries including the non-negative boundaries x ≥ 0, y ≥ 0.
In an objective function, the optimal solution of any point in the feasible region gives the optimal value (maximum or minimum).
Theorems of Linear Programming
There are theorems which will help in solving problems of linear programming and they are:
- Let P be the feasible region and let S = ax + by be the objective function. The optimal value must occur at a corner point of the feasible region when S has an optimal value and the variables x and y are subject to boundaries described by linear inequalities.
- Let P be the feasible region and let S = ax + by be the objective function. If P is constrained, then the objective function S has both minimum and maximum value of P and each of these occurs at a corner point (vertex) of P
Corner Point Method
This method has some steps such as :
- The feasible region of the linear programming problem is to be found and its corner points (vertices) should be determined.
- The objective function Z = ax + by at each corner point should be evaluated. Let’s assume that M and m respectively be the largest and smallest values at these points
- M and m respectively are the maximum and minimum values of the objective function if the feasible region is bounded
When the feasible region is not bounded then,
- The objective function has no maximum value unless Z is the maximum value of the objective function if the open half plane determined by ax + by > Z doesn’t have any point in common with the feasible region.
- The function has no minimum value unless S is the minimum value of the objective function if the open half plane determined by ax + by < S which doesn’t have any point in common with the feasible region.
- Assuming that there is no shortage of the other ingredients used in making the cakes, the cake requires 300g of flour and 35g of fat, and another kind of cake requires 200g of flour and 60g of fat. Find the maximum number of cakes which can be made from 10kg of flour and 2 kg of fat.