The technique of linear programming was formulated by a Russian mathematician L.V. Kantorovich. But the present version of simplex method was developed by Geoge B. Dentzig in 1947. Linear programming (LP) is an important technique of operations research developed for optimum utilization of resources.
It is an important optimization (maximization or minimization) technique used in decision making is business and everyday life for obtaining the maximum or minimum values as required of a linear expression to satisfying certain number of given linear restrictions.
Common terminologies used in Linear Programming
- Decision Variables: The decision variables are the variables which will decide my output. They represent my ultimate solution. To solve any problem, we first need to identify the decision variables. For the above example, the total number of units for A and B denoted by X & Y respectively are my decision variables.
- Objective Function: It is defined as the objective of making decisions. In the above example, the company wishes to increase the total profit represented by Z. So, profit is my objective function.
- Constraints: The constraints are the restrictions or limitations on the decision variables. They usually limit the value of the decision variables. In the above example, the limit on the availability of resources Milk and Choco are my constraints.
- Non-negativity restriction: For all linear programs, the decision variables should always take non-negative values. Which means the values for decision variables should be greater than or equal to 0.
(a) Objective function:
There must be clearly defined objective which can be stated in quantitative way. In business problems the objective is generally profit maximization or cost minimization.
All constraints (limitations) regarding resources should be fully spelt out in mathematical form.
The value of variables must be zero or positive and not negative. For example, in the case of production, the manager can decide about any particular product number in positive or minimum zero, not the negative.
The relationships between variables must be linear. Linear means proportional relationship between two ‘or more variable, i.e., the degree of variables should be maximum one.
The number of inputs and outputs need to be finite. In the case of infinite factors, to compute feasible solution is not possible.
Advantages of Linear Programming
- LP makes logical thinking and provides better insight into business problems.
- Manager can select the best solution with the help of LP by evaluating the cost and profit of various alternatives.
- LP provides an information base for optimum allocation of scarce resources.
- LP assists in making adjustments according to changing conditions.
- LP helps in solving multi-dimensional problems.
(i) There are a number of constraints or restrictions- expressible in quantitative terms.
(ii) The prices of input and output both are constant.
(iii) The relationship between objective function and constraints are linear.
(iv) The objective function is to be optimized i.e., profit maximization or cost minimization.