Linear programming is a mathematical technique for allocating scarce resources in an optimum manner.
The word linear means that the relationships are represented by straight lines and the word programming means a procedure that is used to get the best solution to a problem that involves limited resources.
Basic variable:
The non-zero variables in a basic feasible solution are called, basic variable.
Slack variables:
If a constraint has a sign <, something positive has to be added to the left side to make it, equal. The positive variable, that is added is, called slack variable.
Surplus variable:
If a constraint has a sign >, something positive has to be subtracted from the left side to make it equal. The positive variable, that is added, is called surplus variable.
Formulation of Linear Programming problem, involves the following steps:
- Identify the unknown variables to be determined and assign symbols to them.
- Identify all the restrictions or constraints in the problem and express them as linear equation orinequalities of decision variable.
- Identify the objective or aim and represent it also as a linear function of decision variables.
Solution of linear programming problems:
Two methods are generally used for.the solution i.e. Geometrical (or graphical) method and Simplex method.
Geometrical (or graphical) method :
This method can be used where Z is function of 2 variables only as with increase in variables, the calculations become complicated.
The following steps are involved:
Step-1: formulate linear programming problem by restating the given information in mathematical form i.e. an equation for the objective function.
Step-2: plot the constraints on the graph.
Step-3: identify feasibility region and ascertain coordinates for its corner points.
Step-4: test which corner point is most suitable. Find a point in the permissible region as obtained in Step-3,that gives the optimum value of Z
Simplex method:
This technique also known as Simplex Algorithm is an iterative procedure (i.e. doing repetitively) for solving a linear programming problem in finite number of steps. The method is an algebraic procedure that progressively approaches the optimal solution. The method assumes that the variables are non-negative. The value of the objective function is increased at each step of iteration till further improvement is not possible. The method begins at the point of no production or zero solution. It involves the following steps:
Step-1: Write the program relating to the given. problem.
Step-2: To eliminate the inequalities add slack or surplus variable and rewrite the program.
Step-3: Determine the first basic feasible solution by starting at the origin (i.e. starting with zero solution)
Step-4: Write the initial simplex Tableau 1
Step-5: Calculate Z j (which is inner product of cj and xi)
Step-6: Calculate Zj Cj and select the greatest absolute value with negative sign in index row
Step-7: Highest number with negative sign determines the key column and also determines the Entering variables.
Step-8: Develop ratio column where R = bi / ai.) for the column of entering variables.
Step-9: Select the least, positive ratio (or value of R) and determine the exiting variables. The row containing the least positive ratio is the key row and variable corresponding to it is the exiting variable.
Step-10: Determine the key figure which is the number at the intersection of the key column and key row.
Step-11: Obtain new tableaus for entering variable, divide the figures in the row of leaving variable by key figure.
Step-12 Repeat the step 5 to 11, till no negative numbers exist in theindex row.
Importance of linear programming :
- It can provide insight into problem situations.
- It leads to optimum utilization of productive factors by providing information base
- Different solutions are generated and best could be adopted by the management
Limitations of linear programming
- It assumes linear .relationship between variables, but in real business situations, the Constraints may notbe expressed linearly.
- LP does not take into account the effect of time and uncertainty.
- Parameters in LP are taken as constants but in real situation, that is not, the case.
- Solutions provided by LP are good in static conditions and not ‘in dynamic situation because the effect ofTime is not taken..