Linear programming simplex method lecture notes and solved examples

 What is Linear programming (LP) method ?

Linear programming refers to a technique for choosing the best alternative from a set of feasible alternatives whereby the objective function and constraints are expressed as linear mathematical functions.

Requirements of Linear programming Problems.

  i) There should be a clearly identifiable objective which is measured quantitatively. 

 ii)  The activities to be included should be distinctly identifiable and measurable in quantitative terms.

iii)  The resources of the system should be identifiable and measurable quantitatively and also in limited supply. 

 iv) The relationships representing objective function and the constraints equations or inequalities must be linear in nature. 

 v) There should be a series of feasible alternative courses of action available to the decision maker, which are determined by the resource constraints. 

 What are Business applications of linear programming ?

 a) Determination or optimal product mix in industries. 

 b) Determination of optimal machine and labour contribution 

 c) Determination of optimal use of storage and shipping facilities 

 d) Determining the best route in transport industry.

 e) Todetermine investment plans. 

 f) To find the appropriate number of financial auditors 

 g) Assigning advertising expenditures to different media plans. 

 h) Determining the amount of fertilizer to apply per acre in the agricultural sector. 

 i) Determining campaign strategies in politics.

 j) Determining the best marketing strategies.

What are the basic Assumptions of linear programmimg method?

 i.) Values  in the objective and constraint are known with certainty and do not change during the period        being studied. 

ii)  Proportionality exists in the objective function and the constraints inequalities.

 ii)  The total of all the activities is given by the sum total of each activity conducted                      separately. 

iii) Solutions need not be in whole numbers : they are divisible and may take any fractional     value. 

 iv.) Negative values of physical quantities are impossible, you simply cannot produce                 negative number  of chairs, shirts, lamps or computers. 

 v) All production are assumed to be instantaneous.

vi) Costs and benefits which cannot be quantified easily like goodwill, liquidity and labour         stability are ignored. 

 vii) Interdependence between demand products is ignored, products may be complementary         or a substitute for one another.

Advantages of linear programming

 i) Improves the quality of decisions. 

 ii) Helps in attaining the optimum use of production factors. 

iii) It highlights the bottlenecks in the production process 

 iv) It gives insight and perspective into problem situations, 

 v) Improves the knowledge and skills of tomorrow’s executives, 

 vi) Enable one to consider all possible solutions to problems. 

 vii) Enables one to come up with better and more successful decisions 

 viii) It is a better tool for adjusting to meet changing conditions. 

 Disadvantages of Linear programming 

 i) It treats all relationships as linear. 

ii) It is assumed that any activity is infinitely divisible. 

iii) It takes into account single objective only i.e. profit maximization or cost minimization 

 iv) It can be adopted only under the condition of certainty i.e. recourses, per unit                        contribution, costs etc. are known with certainty. 

Methods of solvimg linear programming problem

1.  Simplex Method.

It refers to a systematic and effective procedure for evaluating corner points of the feasible region until the optimal solution is obtained.

This is an iterative method of solving Linear Programming problem .It’s appropriate where the graphical method is not applicable eg unlike graphical method that only solves two linear programming variables, simplex method can solve more than two variables.

Iteration refers to the process of moving from one corner point to another in search for optimal solutions.

Basic Terms

1. Standard form - it is a linear program in which the objective function and constraints are written as equalities.

2. Slack variables - A slack means the amount of unused resources. it also refers to a variable added to the left hand side of the ≤ to a constraint  to convert it to an equality. It is denoted by S.

3. Surplus variable - it is  a variable substracted from left hand side of the ≥ constraint to convert it in an equality.

4. Optimal solution - This is a feasible solution which optimizes the objective function.

5. Simplex tablaeu - it is a table that is used to give tract of calculations made at each point of evaluation of corner points.Each iteration must have it own tableau.

PROCEDURE

1. Formulate the problem as a linear programming problem.

2. Write the problem in standard form.

3. Design the initial simplex table.

4. Test the solution for optimality, if not;

5. Revise the solution through a series of iterations until the optimal solution is obtained.