What is Linear programming simplex 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 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) To determine 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 programming 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 considers 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 solving 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 in Linear programming simplex method
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 subtracted 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 tableau – 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 OF Linear programming simplex method
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.
ILLUSTRATION OF Linear programming simplex method
A factory manufactures two products x₁ and x₂. Profit per unit is Shs 6 for x₁ and Shs 5 for x₂. Production is constrained by three resources:
x₁ + x₂ ≤ 40 (Resource 1)
2x₁ + x₂ ≤ 60 (Resource 2)
x₁ + 3x₂ ≤ 90 (Resource 3)
x₁, x₂ ≥ 0
(a) Formulate the linear programme in standard form. (4 marks)
(b) Solve the problem using the simplex method (show all tableaux / row operations). (12 marks)
(c) State the optimal production plan and the maximum profit. (2 marks)
(d) Interpret the slack variables. (2 marks)
(a) Formulation
Write the constraints in standard form, insert slack variables
Maximise Z = 6x₁ + 5x₂+s1+s2+s3
Subject to:
x₁ + x₂ + s₁ = 40
2x₁ + x₂ + s₂ = 60
x₁ + 3x₂ + s₃ = 90
x₁, x₂, s₁, s₂, s₃ ≥ 0
(b) Simplex Method – Solution
Initial simplex tableau:
| CJ | 6 | 5 | 0 | 0 | 0 | RHS | |
| BASIC | X1 | X2 | S1 | S2 | S3 | ||
| 0 | S1 | 1 | 1 | 1 | 0 | 0 | 40 |
| 0 | S2 | 2 | 1 | 0 | 1 | 0 | 60 |
| 0 | S3 | 1 | 3 | 0 | 0 | 1 | 90 |
| Z | 0 | 0 | 0 | 0 | 0 | ||
| CJ-Z | -6 | -5 | 0 | 0 | 0 |
Step 1 — Choose entering variable: Most negative in Z-row is −6
– Ratio test (RHS ÷ column x1x_1x1, only positive entries):
- Row s1s_1s1: 40/1=4040/1 = 4040/1=40
- Row s2s_2s2: 60/2=3060/2 = 3060/2=30 ← smallest → pivot row = s2s_2s2
- Row s3s_3s3: 90/1=9090/1 = 9090/1=90
Pivot element = 2 (row s2s_2s2, column x1x_1x1).
Make pivot = 1 (divide row s2s_2s2 by 2) and eliminate x1x_1x1 from other rows.
Row operations produced (showing resulting tableau):
After pivoting (x₁ enters, s₂ leaves):
| CJ | 6 | 5 | 0 | 0 | 0 | RHS | |
| BASIC | X1 | X2 | S1 | S2 | S3 | ||
| 0 | S1 | 0 | 1/2 | 1 | -1/2 | 0 | 10 |
| 0 | X1 | 1 | 1/2 | 0 | 1/2 | 0 | 30 |
| 0 | S3 | 0 | 5/2 | 0 | -1/2 | 1 | 60 |
| Z | 6 | 7 | 0 | ||||
| CJ-Z | 0 | -2 | 0 | 3 | 0 | 180 |
After pivoting (x₂ enters, s1 leaves):
| CJ | 6 | 5 | 0 | 0 | 0 | RHS | |
| BASIC | X1 | X2 | S1 | S2 | S3 | ||
| X2 | 0 | 1 | 2 | 0 | 0 | 40 | |
| X1 | 1 | 0 | -1 | 1 | 0 | 60 | |
| S3 | 0 | 0 | -5 | 0 | 1 | 90 | |
| Z | 6 | 0 | 4 | 0 | 0 | ||
| CJ-Z | 0 | -5 | 4 | 1 | 0 | 220 |
(c) Optimal Solution
x₁ = 20, x₂ = 20
Maximum profit: Zmax = 220 shillings.
(d) Interpretation of Slack Variables
s₁ = 0 → Resource 1 fully used.
s₂ = 0 → Resource 2 fully used.
s₃ = 10 → Resource 3 has 10 units unused.
