Introduction
Every organisation works with resources that are limited in some way: machine hours, raw material,
labour, money and storage space are never unlimited, yet demand for them is often high. This raises
a natural question: how should available resources be distributed among competing activities for the
best possible outcome? Linear Programming, commonly abbreviated as LPP, is one of the most
widely used mathematical tools that answers this question systematically.
A Linear Programming Model is a mathematical representation of a real-world problem in which a
linear objective function must be maximised or minimised subject to linear constraints. "Linear"
means every relationship, in the objective function and the constraints, is of the first degree, so
variables are not raised to any power and are not multiplied together, which allows the problem to be
solved using well-defined algebraic methods.
An optimisation problem, in general, is any situation where a decision maker seeks the best possible
solution among feasible alternatives, whether the highest profit, lowest cost or most efficient use of
material. Such problems appear across engineering and management, and Linear Programming is
among the earliest and most successful techniques developed to solve them mathematically.
In resource management, Linear Programming lets decisions such as how much of each product to
make or how to distribute a limited budget be modelled precisely, so management arrives at a
solution proven to be best rather than one based on guesswork — a core resource management
technique for engineering students.
Among the methods for solving Linear Programming Problems, the Simplex Method, developed by
George B. Dantzig in 1947, is the most powerful. Unlike the graphical method, limited to two
decision variables, the Simplex Method handles any number of variables and constraints, moving
systematically from one corner point of the feasible region to another until the optimum is reached.
The Simplex Maximization Method refers to using this algorithm when the objective is to maximise
a linear function such as profit, so a company can find the combination of products that yields the
greatest return from its resources. The graphical method becomes impractical beyond two variables,
whereas Simplex has no such limit, which is why it is preferred in practice and underlies computer-
based optimisation software used in industry today.
Definition of Simplex Maximization
The Simplex Maximization Method is an iterative algebraic procedure for solving a Linear
Programming Problem where the objective is to maximise a linear function of several decision
variables, subject to linear constraints and non-negativity restrictions. Starting from an initial basic
feasible solution, usually the origin, it moves to adjacent corner points that improve the objective
function, continuing until no further improvement is possible.
Key Terms Used in Simplex Maximization
● Objective Function: linear expression for the quantity to maximise, Z = c1x1 + c2x2 + ... +
cnxn.
● Decision Variables: unknown quantities (x1, x2, ...) whose values must be determined.
● Constraints: linear inequalities/equations limiting resources such as machine time, labour or
budget.
● Feasible Solution: any variable values satisfying all constraints and non-negativity.
● Feasible Region: the set of all feasible solutions, bounded by the constraint lines.
● Basic Feasible Solution: obtained by setting some variables to zero and solving for the rest.
● Slack Variables: non-negative variables added to convert a "≤" constraint into an equation.
● Pivot Element: entry at the intersection of the entering column and leaving row.
● Entering Variable: the non-basic variable entering the basis, with the most negative Z-row
coefficient.
● Leaving Variable: the basic variable removed from the basis, via the minimum ratio test.
● Optimal Solution: the solution giving maximum Z, reached when all Z-row coefficients are
non-negative.
Assumptions of Linear Programming
● Linearity: all relationships are linear functions of the decision variables.
● Certainty: all model coefficients are known and constant.
● Additivity: total effect equals the sum of individual variable effects.
● Divisibility: decision variables may take fractional values.
● Non-negativity: all decision variables are ≥ 0.
Advantages and Limitations
The method handles problems with many variables and constraints, something the graphical method
cannot do, always reaches the mathematically optimal solution when one exists, and is easily
programmed for large industrial problems. However, it assumes linearity, which is not always
realistic; hand solutions are tedious for large problems; and it assumes all data is known with
certainty, whereas real demand and costs vary. Even so, it remains one of the most reliable
optimisation techniques in resource management.
Mathematical Procedure of the Simplex Maximization Method
Step 1: Formulating the Problem
The problem is expressed mathematically by identifying the decision variables, writing the objective
function to be maximised, and expressing resource limits as linear inequalities.
Maximise Z = c1x1 + c2x2 + ... + cnxn
Subject to: a11x1 + a12x2 + ... + a1nxn ≤ b1 (and similar constraints), with x1, x2, ..., xn ≥ 0
Step 2: Converting Inequalities into Equations
Since the Simplex Method works only with equations, every "≤" constraint is converted into an
equation by adding a slack variable, which represents the amount of resource that remains unused.
Step 3: Introducing Slack Variables
A distinct slack variable is added for each constraint: a1x1 + a2x2 ≤ b becomes a1x1 + a2x2 + s = b,
with s ≥ 0. Slack variables carry a zero coefficient in the objective function since unused resources
do not add to profit.
Step 4: Constructing the Initial Simplex Table
Once all constraints are in equation form, an initial simplex table is built. The slack variables form
the starting basic feasible solution, since setting all decision variables to zero satisfies every
constraint. The table lists the basic variables, variable coefficients, right-hand-side values, and a Z-
row of negative objective-function coefficients.
Step 5: Selecting the Entering Variable
The entering variable is the column with the most negative coefficient in the Z-row, since it increases
Z the fastest if brought into the solution.
Step 6: Selecting the Leaving Variable
A minimum ratio test is performed: each positive entry in the entering column is divided into its
row's right-hand-side value, and the row with the smallest non-negative ratio becomes the pivot row,
whose basic variable leaves the basis.
Step 7: Performing Pivot Operations
The entry at the intersection of the entering column and leaving row is the pivot element. The pivot
row is divided by this element so it becomes one, and every other row, including the Z-row, is
adjusted by row operations so all other entries in the pivot column become zero, producing an
improved simplex table.
Step 8: Repeating the Iterations
Steps 5 to 7 are repeated on each new table, moving the solution to an adjacent corner point with an
equal or higher value of Z each time.
Step 9: Identifying the Optimal Solution
The process stops once the Z-row contains no negative coefficients. The current solution is then
optimal, and the Z-value in the table is the maximum value of the objective function.
Solved Problem 1
Problem Statement
A furniture company produces chairs and tables, whose production is limited by carpentry hours on
Machine A, finishing hours on Machine B, and assembly hours on Machine C. It wants the
production quantities that maximise total profit.
Objective Function and Constraints
Maximise Z = 3x1 + 5x2
Subject to the following constraints:
x1 ≤ 4 (Machine A capacity)
2x2 ≤ 12 (Machine B capacity)
3x1 + 2x2 ≤ 18 (Machine C capacity)
x1, x2 ≥ 0
Standard Form Conversion
Adding slack variables s1, s2, s3:
x1 + s1 = 4
2x2 + s2 = 12
3x1 + 2x2 + s3 = 18, Z - 3x1 - 5x2 = 0
Initial Simplex Table
Basis x1 x2 s1 s2 s3 RHS Ratio
s1 1 0 1 0 0 4 -
s2 0 2 0 1 0 12 6
s3 3 2 0 0 1 18 9
Z -3 -5 0 0 0 0
Most negative Z-row value is -5 (column x2), so x2 enters. Minimum ratio test: row s2 gives the
smallest ratio (6), so s2 leaves. Pivot element = 2.
Iteration 1
Basis x1 x2 s1 s2 s3 RHS Ratio
s1 1 0 1 0 0 4 4
x2 0 1 0 0.5 0 6 -
s3 3 0 0 -1 1 6 2
Z -3 0 0 2.5 0 30
Z-row still has -3 (column x1), so x1 enters. Ratio test: row s3 gives 2 (smaller than 4 for row s1), so
s3 leaves. Pivot element = 3.
Final Simplex Table (Optimal Solution)
Basis x1 x2 s1 s2 s3 RHS
s1 0 0 1 0.333 -0.333 2
x2 0 1 0 0.5 0 6
x1 1 0 0 -0.333 0.333 2
Z 0 0 0 1.5 1 36
All Z-row coefficients are now non-negative (0, 0, 0, 1.5, 1) — the table is optimal.
Interpretation of the Result
The optimal solution is x1 = 2 and x2 = 6, giving maximum profit Z = 36. The company should
produce 2 units of the first product and 6 units of the second. Since s1 = 2, 2 hours of Machine A
capacity remain unused, while s2 = 0 and s3 = 0 show that Machine B and Machine C are fully used,
making them the binding constraints.
Solved Problem 2
Problem Statement
An electronics workshop assembles Type 1 and Type 2 circuit boards, limited by soldering hours and
testing hours. It wants the production quantities that maximise total daily profit.
Objective Function and Constraints
Maximise Z = 4x1 + 3x2
Subject to the following constraints:
2x1 + x2 ≤ 10 (Soldering hours available)
x1 + 3x2 ≤ 15 (Testing hours available)
x1, x2 ≥ 0
Standard Form Conversion
Adding slack variables s1, s2:
2x1 + x2 + s1 = 10
x1 + 3x2 + s2 = 15, Z - 4x1 - 3x2 = 0
Initial Simplex Table
Basis x1 x2 s1 s2 RHS Ratio
s1 2 1 1 0 10 5
s2 1 3 0 1 15 15
Z -4 -3 0 0 0
Most negative Z-row value is -4 (column x1), so x1 enters. Ratio test gives 5 for row s1, so s1 leaves.
Pivot element = 2.
Iteration 1
Basis x1 x2 s1 s2 RHS Ratio
x1 1 0.5 0.5 0 5 10
s2 0 2.5 -0.5 1 10 4
Z 0 -1 2 0 20
Z-row still has -1 (column x2), so x2 enters. Ratio test: row s2 gives 4 (smaller than 10 for row x1),
so s2 leaves. Pivot element = 2.5.
Final Simplex Table (Optimal Solution)
Basis x1 x2 s1 s2 RHS
x1 1 0 0.6 -0.2 3
Basis x1 x2 s1 s2 RHS
x2 0 1 -0.2 0.4 4
Z 0 0 1.8 0.4 24
All Z-row coefficients are now non-negative (0, 0, 1.8, 0.4) — the optimal solution has been reached.
Interpretation of the Result
The optimal solution is x1 = 3 and x2 = 4, giving maximum profit Z = 24. The workshop should
assemble 3 units of the Type 1 board and 4 units of the Type 2 board each day. Since both slack
variables are zero, soldering and testing hours are both fully utilised, making them binding
constraints.
Real-World Applications
The Simplex Maximization Method is applied extensively across industries to solve genuine resource
allocation problems, as the following examples illustrate.
Manufacturing Industries
Manufacturing units producing several products with shared machinery use the Simplex Method to
decide the quantity of each product yielding the highest profit without exceeding any resource limit.
Transportation and Logistics
Logistics companies use Simplex-based models to route goods at the lowest cost or shortest time,
respecting vehicle capacity and delivery constraints.
Supply Chain Management
Organisations use the method to decide stock levels at each stage and how to allocate orders among
suppliers so overall cost is minimised, subject to storage and transport limits.
Agriculture
Farmers use Linear Programming to allocate limited land, water and labour among crops, finding the
cropping pattern that maximises yield within irrigation and land limits.
Product Mix Optimisation
Companies making multiple products from common resources use the Simplex Method to find the
product mix that generates maximum profit.
Factory Production Planning
Production planners use Simplex-based models to schedule machines and labour so targets are met at
the lowest cost without exceeding capacity.
Financial Planning
The method helps allocate a limited investment budget among projects so expected return is
maximised, subject to risk and diversification constraints.
Business Profit Maximisation
Across almost every business, combining limited capital, labour, time and material to achieve the
highest profit can be modelled as a Linear Programming Problem, and the Simplex Method gives a
reliable, mathematically sound answer.
Figure 1: A factory production line, illustrating the manufacturing environment in which product-mix decisions are
solved using the Simplex Maximization Method.
Conclusion
The Simplex Maximization Method is a significant contribution to resource management and
operations research. By converting a problem of limited resources into a precise mathematical model
and solving it through systematic iterations, the method guarantees a solution that is truly optimal,
not merely satisfactory.
Its importance lies in handling problems of practically any size, something the graphical method
cannot do, while offering step-by-step logic verifiable by hand and extendable into computer
algorithms for large applications. Its practical significance shows in its use across manufacturing,
transportation, supply chain management, agriculture, finance and general business planning.
Its main advantages are mathematical certainty of optimality, adaptability to many problem types,
and suitability for computerisation, while its limitations stem mainly from assuming linearity and
needing accurate input data. It remains relevant today as it underlies many modern optimisation
solvers, and for a second-year engineering student it builds both mathematical problem-solving skill
and practical value for real engineering and managerial decisions.