Formulation of Linear Programming Problem(LPP)
The construction of objective function as well as the constraints is known as formulation of Linear Programming Problem (LPP).
The following are the basic steps in formulation of LPP.
i. Identify the variables to be determined and then express these by some algebraic symbols.
ii. Locate the various constraints/restrictions present in the problem ans express these linear equations/inequalities which are some linear functions of the variables identified in step
iii. Determine the objective of the problem and express it as linear function of the decision variable involved in the phenomenon.
Assumptions in Linear Programming
The following assumptions may be true or valid over the area of search appropriate to the problems:
i. There are a number of restrictions or constraints expressible in quantitative terms.
ii. The parameters are subject to variations in magnitude.
iii. The relationships expressed by constraints and the objective functions are linear.
iv. The objective function is to be optimized w.r.t. the variables involved in the phenomenon.
v. The fundamental characteristics in all such cases is to find some optimum strategy under certain known specifications.
Limitations of Linear Programming
i. The assumption that all relations are linear may not hold good in many real situations e.g. production cost may not be a linear function of output, in the case of variable costs the profit coefficients may not satisfy the linearity restriction.
ii. In L.P. all coefficients and constraints are stated with certainty.
iii. The solution many times is in rounding – off.
iv. When the number of variables or constraints involved in the phenomenon are quite large then it may become necessary to use computers.
Solution of Linear Programming Problem
There are many methods to find the optimal solution of Linear Programming Problem. The methods are :
- Graphical Method
- Simplex Method
- Transportation Method
In the remaining sections of this chapter the methods to find the optimal solution and some of the problems experienced during the course of getting a solution are discussed in detail.
- Graphical Method
The industrial problems involving two or three variables can be easily and effectively solved by drawing the graph for various constraints and the objective function. The graphical method is simple and provides useful insights for the solution of complex problems. But the limitation of this method is that it cannot be used for solving problems with more than three decision variables. When used for solving problems with three variables, the graph becomes complex and cumbersome.
Steps in Graphical Solution of Linear Programming Problem
i. The constraints of the problem are taken as equalities and plotted on the graph paper. The region satisfying each constraints is determined and then the region common to all the constraint relations is located. This region is known as feasible region for the problem as all points lying in this region will simultaneously satisfy the given constraints. The solution set of the system of constraints is found to be represented by some convex polygon termed as feasible region
ii. Objective function is also plotted on the same graph paper by taking some arbitrary value of Z.
iii. Trial and error method is used to locate the optimal solution inside the feasible region determined in step one so that objective function is optimized. It is experienced the optimal solution is located near the extreme points of feasible region. Thus the optimal feasible point should be searched only at the corners of convex polygon.
The graph for all the constraints and the objective function will be straight line in Linear programming problem.
Example : Solve graphically
Here one of the constraints is in ≥ form. So the identification of the feasible region will be done in a different way.
2. Simplex Method
The graphical method can be used for solving linear programming problems with two decision variables. Problems with three decision variables need a three dimensional graph for solution, and problems with more than three decision variables cannot be handled at all by this method. The simplex method developed by Professor George B Dantzig in 1947, is basically an algebraic procedure for solving linear problems. It is an algorithm which is an iteration method of computation, to move from one solution to another until it reaches the best solution.
To solve a problem by simplex method requires
- Arranging the objective function and cosntraints in a special way and
- Following a systematic procedure and a set of rules in finding the desired solution.
Steps in the simplex maximization procedure can be summarized as follows:
- Convert constraint inequalities to equalities by adding a slack variable ( +S with an appropriate subscript ) to every equation with a ≤ sign. Set up the initial tableau.
- Copy the coefficients of your objective function into a simplex tableau. Be sure to have a separate column for every real or slack variable as well as for the amount on the right hand side of the constraint equations.
- Compute values for the Z row. Multiply the values in each constraint row by the row’s C. Add the results within each column. Compute the ( Cj – Zj ) row and evaluate the net profit contribution of each column.
- Elect the column ( or variable) with the most positive net contribution (Cj – Zj).The column so selcted is called the pivot column.
- Determine which variable will be replaced. This is done in the following manner:
- Divide the right hand side values by their corresponding numbers in the pivot column.
- Select the row with the smaller nonnegative ration as the row to be replaced. The row so selected is called the pivot row.
- Circle the pivot element, which is the element in the pivot column and the pivot row. Develop the new tableau by calculating the new rows using the formula:
- For the new row of the old pivot row, divide each number in the old pivot row by the pivot element.
- For all other rows,
- Transportation Problem
In every day life various manufacturing organizations or other establishments due to a number of considerations store their product or items at various place termed as origins or warehouses. When supply is to be made to customers or other users then the items are transported. Origins to one or more destinations. The overall purpose of this exercise is to have a distribution policy such that total transportation cost is minimum or the time taken in transshipment is minimum. Alternately finished products from the plant are also to be transported to warehouse in this mist commercial manner. Transportation problem can slo be visualized as a problem of allocating resources from the source to the place requiring the facility, when requirement at some particular place may be fulfilled by combining resource from one more resources. Thus transportation problem can also be visualized as a typical Linear Programming Problem.