 |
Introduction |
| |
The mathematical models which tells to optimise (minimize or maximise) the objective function Z subject to certain condition on the variables is called a Linear programming problem (LPP). |
| |
During World War II, the military managements in the U.K and the USA engaged a team of scientists to study the limited military resources and form a plan of action or programme to utilise them in the most effective manner. This was done under the name 'Operation Research' (OR) because the team was dealing with research on military operation. |
|
Linear Programming Problems (LPP) |
| |
The standard form of the linear programming problem is used to develop the procedure for solving a general programming problem. |
| |
A general LPP is of the form
Max (or min) Z = c1x1 + c2x2 + … +cnxn
x1, x2, ....xn are called decision variable. |
|
Application Areas of Linear Programming |
| |
The Application Areas of Linear Programming are: |
| |
1. Transportation Problem |
| |
2. Military Applications |
| |
3. Operation of System Of Dams |
| |
4. Personnel Assignment Problem |
| |
5. Other Applications: (a). manufacturing plants, (b). distribution centres, (c). production management and manpower management. |
|
Basic Concept of Linear Programming Problem |
| |
Objective Function:
The Objective Function is a linear function of variables which is to be optimised i.e., maximised or minimised. e.g., profit function, cost function etc. The objective function may be expressed as a linear expression. |
| |
Constraints:
A linear equation represents a straight line. Limited time, labour etc. may be expressed as linear inequations or equations and are called constraints. |
| |
Optimisation:
A decision which is considered the best one, taking into consideration all the circumstances is called an optimal decision. The process of getting the best possible outcome is called optimisation. |
| |
Solution of a LPP:
A set of values of the variables x1, x2,….xn which satisfy all the constraints is called the solution of the LPP.. |
| |
Feasible Solution:
A set of values of the variables x1, x2, x3,….,xn which satisfy all the constraints and also the non-negativity conditions is called the feasible solution of the LPP. |
| |
Optimal Solution:
The feasible solution, which optimises (i.e., maximizes or minimizes as the case may be) the objective function is called the optimal solution. Important terms Convex Region and Non-convex Sets. |
|
Mathematical Formulation of Linear Programming Problems |
| |
There are mainly four steps in the mathematical formulation of linear programming problem as a mathematical model. We will discuss formulation of those problems which involve only two variables. |
| |
1. Identify the decision variables and assign symbols x and y to them. These decision variables are those quantities whose values we wish to determine. |
| |
2. Identify the set of constraints and express them as linear equations/inequations in terms of the decision variables. These constraints are the given conditions. |
| |
3. Identify the objective function and express it as a linear function of decision variables. It might take the form of maximizing profit or production or minimizing cost. |
| |
4. Add the non-negativity restrictions on the decision variables, as in the physical problems, negative values of decision variables have no valid interpretation. |
|
Advantages of Linear Programming |
| |
i. The linear programming technique helps to make the best possible use of available productive resources (such as time, labour, machines etc.) |
| |
ii. In a production process, bottle necks may occur. For example, in a factory some machines may be in great demand while others may lie idle for some time. A significant advantage of linear programming is highlighting of such bottle necks. |
|
Limitations of Linear Programming |
| |
(a). Linear programming is applicable only to problems where the constraints and objective function are linear i.e., where they can be expressed as equations which represent straight lines. In real life situations, when constraints or objective functions are not linear, this technique cannot be used. |
| |
(b). Factors such as uncertainty, weather conditions etc. are not taken into consideration. |
|
Graphical Method of Solution of a Linear Programming Problem |
| |
The graphical method is applicable to solve the LPP involving two decision variables x1, and x2, we usually take these decision variables as x, y instead of x1, x2. To solve an LPP , the graphical method includes two major steps. |
| |
a) The determination of the solution space that defines the feasible solution (Note that the set of values of the variable x1, x2, x3,....xn which satisfy all the constraints and also the non-negative conditions is called the feasible solution of the LPP). |
| |
b) The determination of the optimal solution from the feasible region. |
| |
There are two techniques to find the optimal solution of an LPP. Corner Point Method and ISO- PROFIT (OR ISO-COST). |
|
Some Exceptional Cases |
| |
We may come across LPP which may have no feasible (infeasible) solution or may have unbounded solution.
If the intersection of the constraints is empty and the problem has no feasible solution. Therefore the given L.P.P has no solution. |
|
Conclusion |
| |
The graphical method of solving an LPP is possible only if there are two decision variables (say x and y). This method is not suitable if there are three or more decision variables. In this case, there is a powerful method called 'simplex method'. The wide usage of liner programming helps in business and economics, to use the resources available in a planned and economical way. We have just learnt the basics of LPP, there is in fact a lot to learn in higher classes. A lot of research work is carried all over the world which is based on LPP.
|
