WHAT IS LINEAR PROGRAMMING?
Linear Programming (LP) is a mathematical modelling technique useful for economic allocation of ‘scarce’ or ‘limited resources, such as labour, material, machine, time, warehouse space, capital, energy, etc., to several competing activities, such as products, services, jobs, new equipment, projects, etc., on the basis of a given criterion of optimality. The phrase scarce resources means resources that are not in infinite in availability during the planning period. The criterion of optimality, generally is either performance, return on investment, profit, cost, utility, time, distance, etc.
The word linear refers to linear relationship among variables in a model. Thus, a given change in one variable will always cause a resulting proportional change in another variable. For example, doubling the investment on a certain project will exactly double the rate of return. The word programming refers to modelling and solving a problem mathematically that involves the economic allocation of limited resources by choosing a particular course of action or strategy among various alternative strategies to achieve the desired objective.
ASSUMPTIONS OF LINEAR PROGRAMMING
The following four basic assumptions are for all linear programming models:-
1) Certainty:
In all LP models, it is assumed, that all model parameters such as availability of resources, profit (or cost) contribution of a unit of decision variable and consumption of resources by a unit of decision variable must be known and may be constant. In some cases, these may be either random variables represented by a known distribution (general or may statistical) or may tend to change, then the given problem can be solved by a stochastic LP model or parametric programming.
2) Divisibility (or Continuity):
The solution values of decision variables are allowed to assume continuous values. For instance, it is possible to produce 5.253 thousand gallons of a solvent in a chemical company, so these variables are divisible. But in contrast, it is not desirable to produce 4.5 machines. Such variables are not divisible and therefore must be assigned integer values. Hence, if any of the variable can assume only integer values or are limited to discrete number of values, LP model is no longer applicable, but an integer programming model may be applied to get the desired values.
3) Additivity:
The value of the objective function and the total amount of each resource used (or supplied), must be equal to the sum of the respective individual contributions (profit or cost) by decision variables. For example, the total profit earned from the sale of two products A and B must be equal to the sum of the profits earned separately from A and B. Similarly, the amount of a resource consumed for producing A and B must be equal to the sum of resources used for A and B individually.
4) Linearity (or Proportionality):
The amount of each resource used (or supplied) and its contribution to the profit (or cost) in objective function must be proportional to the value of each decision variable. For example, if production of one unit of a product uses 6 hours of a particular resource, then making 4 units of that product uses 4 x 6 = 24 hours of that resource.
ADVANTAGES OF LINEAR PROGRAMMING
Following are certain advantages of linear programming:
- Linear programming helps in attaining the optimum use of productive resources. It also indicates how a decision-maker can employ his productive factors effectively by selecting and distributing (allocating) these resources.
- Linear programming techniques improve the quality of decisions. The decision-making approach of the user of this technique becomes more objective and less subjective.
- Linear programming techniques provide possible and practical solutions since there might be other constraints operating outside the problem which must be taken into account. Just because we can produce so many units does not mean that they can be sold. Thus, necessary modification of its mathematical solution is required for the sake of convenience to the decision-maker.
- Highlighting of bottlenecks in the production processes is the most significant advantage of this technique. For example, when a bottleneck occurs, some machines cannot meet demand while other remains idle for some of the time.
- Linear programming also helps in re-evaluation of a basic plan for changing conditions. If conditions change when the plan is partly carried out, they can be determined so as to adjust the remainder of the plan for best results.
LIMITATIONS OF LINEAR PROGRAMMING
In spite of having many advantages and wide areas of applications, there are some limitations associated with this technique. These are given below:
- Linear programming treats all relationships among decision variables as linear, However, generally, neither the objective functions nor the constraints in real-life situations concerning business and industrial problems are linearly related to the variables.
- While solving an LP model, there is no guarantee that we will get integer valued solutions. For example, in finding out how many men and machines would be required to perform a particular job, a non-integer valued solution will be meaningless. Rounding off the solution to the nearest integer will not yield an optimal solution. In such cases, integer programming is used to ensure integer value to the decision variables.
- Linear programming model does not take into consideration the effect of time and uncertainty. Thus, the LP model should be defined in such a way that any change due to internal as well as external factors can be incorporated.
- Parameters appearing in the model are assumed to be constant but in real-life situations, they a frequently neither known nor constant.
- It deals with only single objective, whereas in real-life situations we may come across conflicting multi-objective problems. In such cases, instead of the LP model, a goal programming model is used to get satisfactory values of these objectives.
APPLICATION AREAS OF LINEAR PROGRAMMING
Linear programming is the most widely used technique of decision-making in business and industry and in various other fields. In this section, we will discuss a few of the broad application areas of linear programming.
1) Agricultural Applications:
These applications fall into categories of farm economics and farm management. The former deals with agricultural economy of a nation or region, while the latter is concerned with the problems of the individual farm.
The study of farm economics deals with inter-regional competition and optimum allocation of crop production Efficient production patterns can be specified by a linear programming model under regional land resources and national demand constraints.
Linear programming can be applied in agricultural planning, e.g. allocation of limited resources such as acreage, labour, water supply and working capital, etc., in a way so as to maximize net revenue.
2) Military Applications:
Military applications include the problem of selecting an air weapon system against enemy so as to keep them pinned down and at the same time minimizing the amount of aviation gasoline used.
A variation of the transportation problem that maximizes the total tonnage of bombs dropped on a set of targets and the problem of community defense against disaster, the solution of which yields the number of defense units that should be used in a given attack in order to provide the required level of protection at the lowest possible cost.
3) Production Management:
i) Product Mix:
A company can produce several different products, each of which requires the use of limited production resources. In such cases, it is essential to determine the quantity of each product to be produced knowing its marginal contribution and amount of available resource used by it The objective is to maximize the total contribution, subject to all constraints.
ii) Production Planning:
This deals with the determination of minimum cost production plan over planning period of an item with a fluctuating demand, considering the initial number of units in inventory, production capacity, constraints on production, manpower and all relevant cost factors. The objective is to minimize total operation costs. 3. Assembly-line Balancing This problem is likely to arise when an item can be made by assembling different components. The process of assembling requires some specified sequence. The objective is to minimize the total elapse time.
4) Blending Problems:
These problems arise when a product can be made from a variety of available raw materials, each of which has a particular composition and price. The objective here is to determine the minimum cost blend, subject to availability of the raw materials, and minimum and maximum constraints on certain product constituents.
5) Trim Loss:
When an item is made to a standard size (e.g. glass, paper sheet), the problem that arises is to determine which combination of requirements should be produced from standard materials in order to minimize the trim loss.
6) Financial Management:
Portfolio Selection:
This deals with the selection of specific investment activity among sever other activities. The objective is to find the allocation which maximizes the total expected return of minimizes risk under certain limitations.
Profit Planning:
This deals with the maximization of the profit margin from investment in plant facilities and equipment, cash in hand and inventory.
7) Marketing Management:
i) Media Selection:
Linear programming technique helps in determining the advertising media mix so as to maximize the effective exposure, subject to limitation of budget, specified exposure rates to different market segments, specified minimum and maximum number of advertisements in various media.
ii) Travelling Salesman Problem:
The problem of a salesman is to find the shortest route from a given city, visiting each of the specified cities and then returning to the original point of departure, provided no city shall be visited twice during the tour. Such type of problems can be solved with the help of the modified assignment technique.
iii) Physical Distribution:
Linear programming determines the most economic and efficient manner of locating manufacturing plants and distribution centers for physical distribution.
8) Personnel Management:
i) Staffing Problem:
Linear programming is used to allocate optimum manpower to a particular job so as to minimize the total overtime cost or total manpower.
ii) Determination of Equitable Salaries:
Linear programming technique has been used in determining equitable salaries and sales incentives.
iii) Job Evaluation and Selection:
Selection of suitable person for a specified job and evaluation of job in organizations has been done with the help of linear programming technique.