Linear Programming 

The term linear programming consists of two words, linear and programming. The linear programming considers only linear relationship between two or more variables. By linear relationship we mean that relations between the variable can be represented by straight lines. Programming means planning or decision- making in a systematic way. “Linear programmingrefers to a technique for the formulation and solution of problems in which some linear function of two or more variables is to be optimized subject to a set of linear constraints at least one of which must be expressed as inequality”. American mathematician George B. Danzig, who invented the linear programming technique. Linear programming is a practical tool of analysis which yields the optimum solution for the linear objective function subject to the constraints in the form of linear inequalities. Linear objective function and linear inequalities and the techniques, we use is called linear programming, a special case of mathematical programming.

Terms of Linear Programming
(1) Objective Function
Objective function, also called criterion function, describe the determinants of the quantity to be maximized or to be minimized. If the objective of a firm is to maximize output or profit, then this is the objective function of the firm. If the linear programming requires the minimization of cost, then this is the objective function of the firm. An objective function hastwo parts – the primal and dual. If the primal of the objective function is to maximize output then its dual will be the minimization of cost.
(2) Technical Constraints
The maximization of the objective function is subject to certain limitations, which are called constraints. Constraints are also called inequalities because they are generally expressed in the form of inequalities. Technical constraints are set by the state of technology and the availability of factors of production. The number of technical constraints in a linear programming problem is equal to the number of factors involved it.
(3) Non- Negativity Constraints
This express the level of production of the commodity cannot be negative, ie it is either positive or zero.
(4) Feasible Solutions
After knowing the constraints, feasible solutions of the problem for a consumer, a particular, a firm or an economy can be ascertained. Feasible solutions are those which meet or satisfy the constraints of the problem and therefore it is possible to attain them.
(5) Optimum Solution
The best of all feasible solutions is the optimum solution. In other words, of all the feasible solutions, the solution which maximizes or minimizes the objective function is the optimum solution. For instance, if the objective function is to maximize profits from the production of two goods, then the optimum solution will be that combination of two products that will maximizes the profits for the firm. Similarly, if the objective function is to minimize cost by the choice of a process or combination of processes, then the process or a combination of processes which actually minimizes the cost will represent the optimum solution. It is worthwhile to repeat that optimum solution must lie within the region of feasible solutions.
 Assumptions of LPP
The LPP are solved on the basis of some assumptions which follow from the nature of the problem.
(a) Linearity: The objective function to be optimized and the constraints involve only linear relations. They should be linear in their variables. If they are not, alternative technique to solve the problem has to be found. Linearity implies proportionality between activity levels and resources. Constraints are rules governing the process.
(b) Non- negativity: The decision variable should necessarily be non –negative.
(c) Additive and divisibility:  Resources and activities must be additive and divisible.

(d) Alternatives: There should be alternative choice of action with a well defined objective function to be maximized or minimized.
(e) Finiteness: Activities, resources, constraints should be finite and known.
(f) Certainty: Prices and various coefficients should be known with certainty.
Formulation of Linear Programming

The formulation has to be done in an appropriate form. We should have,

(1) An objective function to be maximized or minimized. It will have n decision variables x1,x2 ….xn and is written in the form.

Where, each Cj is a constant which stands for per unit contribution of profit (in the maximization case) or cost (in the minimization case to each Xj)
(2) The constraints in the form of linear inequalities.

Briefly written

Where bi, stands for the i^th requirement or constraint
The non-negativity constraints are

In matrix notation, we write

Applications of linear programming
1. Production Management: LP is applied for determining the optimal allocation of such resources as materials, machines, manpower, etc. by a firm. It is used to determine the optimal product- mix of the firm to maximize its revenue. It is also used for product smoothing and assembly line balancing.
2. Personnel Management: LP technique enables the personnel manager to solve problems relating to recruitment, selection, training, and deployment of manpower to different departments of the firm. It is also
used to determine the minimum number of employees required in various shifts to meet production schedule within a time schedule.
3. Inventory Management: A firm is faced with the problem of inventory management of raw materials and finished products. The objective function in inventory management is to minimise inventory cost and the constraints are space and demand for the product. LP technique is used to solve this problem.

4. Marketing Management: LP technique enables the marketing manager in analysing the audience coverage of advertising based on the available media, given the advertising budget as the constraint. It also helps the
sales executive of a firm in finding the shortest route for his tour. With its use, the marketing manager determines the optimal distribution schedule for transporting the product from different warehouses to various market locations in such a manner that the total transport cost is the minimum.
5. Financial Management: The financial manager of a firm, mutual fund, insurance company, bank, etc. uses the LP technique for the selection of investment portfolio of shares, bonds, etc. so as to maximise return on investment.
6. Blending Problem: LP technique is also applicable to blending problem when a final product is produced by mixing a variety of raw materials. The blending problems arise in animal feed, diet problems, petroleum products, chemical products, etc. In all such cases, with raw materials and other inputs as constraints, the objective function is to minimise the cost of final product.

7. Diet problems:  To determine the minimum requirements of nutrients subjects to availability of foods and their prices.
8. Transportation problem:  To decide the routes, number of units, the choice of factories, so that tha cost of operation is the minimum.
9. Manufacturing problems:  To find the number of items of each type that should be made so as to maximize the profits.
10. Assembling problems: To have, the best combination of basic components to produce goods according to certain specifications.
11. Purchasing problems: To have the least cost objective in, say, the processing of goods purchased from outside and varying in quantity, quality and prices.
12. Job assigning problem: To assign jobs to workers for maximum effectiveness and optimum results subject to restrictions of wages and other costs.
 

The steps for solving a LPP by graphic method are:

1. Formulate the given problems into a LPP

2. Each inequality in the constraint may be written as equality

3. Draw strainghl lines corresponding to the equations obtained in step 2.

4. ldentity the feasible region (ie. region which satisfies all the constraints simultaneously).

5. The feasible .egion is a many sided fig. The corner point ot the fig. are to be located and their co -ordinates are to be measured.

6. Calculate the value of lhe objeclive lunciion lor each corner point.

7. The solution is given by the co - ordinates ol that corner which optimises the objective lunction. The draw back of this method is that the problem oI higher dimensionality can't be handled by this. A problem of three dimensions can also be solved by this method but it is complicated enough.

Examples And Exercises
 

Example: A firm can produce a good either by (1) a labour intensive technique, using 8 units of labour and 1 unit of capital or (2) a capital intensive technique using 1 unit of labour and 2unit of capital. The firm can arrange up to 200 units of labour and 100 units of capital. It can sell the good at a constant net price (P), ie P is obtained after subtracting costs. Obviously we have simplified the problem because in this ‘P’ become profit per unit. Let P = 1.

Let x1 and x2 be the quantities of the goods produced by the processes 1 and 2
respectively. To maximize the profit P x1 + P x2, we write the objective function.
Π = x1 + x2 (since P = 1). The problem becomes

Max π = x1 + x2
Subject to: The labour constraint 8 x1 + x2 ≤ 200
The capital constraint x1 + x2 ≤ 100
And the non- negativity conditions x1 ≥ 0, x2 ≥ 0
This is a problem in linear programming.

Example: Two foods F1, F2 are available at the prices of Rs. 1 and Rs. 2 per unit respectively. N1, N2, N3 are essential for an individual. The table gives these minimum requirements and nutrients available from one unit of each of F1, F2. The question is of minimizing cost (C), while satisfying these requirements

Graphical Solution
If the LPP consist of only two decision variable. We can apply the graphical method of solving the problem. It consists of seven steps, they are

1. Formulate the problem in to LPP.
2. Each inequality in the constraint may be treated as equality.
3. Draw the straight line corresponding to equation obtained steps (2) so there will be as many
straight lines, as there are equations.
4. Identify the feasible region. This is the region which satisfies all the constraints in the
problem.
5. The feasible region is a many sided figures. The corner point of the figure is to be located
and they are coordinate to be measures.
6. Calculate the value of the objective function at each corner point.
7. The solution is given by the coordinate of the corner point which optimizes the objective
function.
Example: Solve the following LPP graphically.

Limitations of Linear Programming Technique

Linear programming has turned out to be a highly useful tool of analysis for the business executive. It is being increasingly made use of in theory of the firm, in managerial economics, in interregional trade, in general equilibrium analysis, in welfare economics and in development planning. But it has its limitations.
1. it is not easy to define a specific objective function.
2. Even if a specific objective function is laid down, it may not be so easy to find out various technological, financial and other constraints which may be operative in
pursuing the given objective.
3. Given a specific objective and a set of constraints, it is possible that the constraints may not be directly expressible as linear inequalities.
4. Even if the above problems are surmounted, a major problem is one of estimating relevant values of the various constant coefficients that enter into a linear programming model, i.e., prices, etc.
5. This technique is based on the assumption of linear relations between inputs and outputs. This means that inputs and outputs can be added, multiplied and divided. But the relations between inputs and outputs are not always linear. In real life, most of the relations are non-linear.
6. This technique assumes perfect competition in product and factor markets. But perfect competition is not a reality.
7. The LP technique is based on the assumption of constant returns. In reality, there are either diminishing or increasing returns which a firm experiences in production.

8. It is a highly mathematical and complicated technique. The solution of a problem with linear programming requires the maximization or minimization of a clearly specified variable. The solution of a linear programming problem is also arrived at with such complicated method as the ‘simplex method’ which involves a large number of mathematical calculations. It requires a special computational technique, an electric computer or desk calculator. Mostly, linear programming models present trial- and-error solutions and it is difficult to find out really optimal solutions to the various economic problems.

The computations required in complex problems may be enormous. The assumption of divisibility of resources may often be not true. Linearity of the objective function and Linear programming may be defined as a method of determining optimum programme of independent activities in views of available resourses. The objective in a linear programming problem is to maximise profit or minimise cost as the case may be subject to a number of limitation known as constraints. For this an objective function is constructed which represents total profit or total cost as the case may be. The constraints are expressed in the form of inequalities or equations. Both the objeciive function and the constraints are linear relationship between the variables. The solution to a linear programming problem show how much should be produced (or sold or purchased) which will optimise the objective function and satisfy the constraints. lt is a technique for determing the utilisation ol resources.

 Methods of finding the dual of a given primal:

1. lf lhe primal is maximisation the dual is minimisation and viz.

2. Constant in the right hand side of the constraints become the co efticient in the objective ,function and viz.

3. The transpose of the coefficents in the constrainsts ol dual from the co - efficients for lhe other viz.

4. The inequalities in the constrainst are reversed.

CHARACTERISTICS OF THE DUAL PROBLEM.

1. Dual of the dual is primal.

2. lf ths primal (or dual) has a finite optimal solution, then the other also has finite optimal solution.

3. Optimal value of objective tunction (ie Z) will be same tor both primal and dual.

4. lf one ol the primal or dual has an unbounded oplimum solution then lhe other has no leasible solution at all.

5. lf one has no feasible solution, then the other will also have no feasible solution.
Soluiion ol a L.P.P. by graphical method. lf the LPP is a two variablos problem, the problem can be solved graphically.