Operations Research – The Simplex Method
Section 1: Introduction to Linear Programming Problems (LPP)
Linear Programming Problem (LPP) is a mathematical technique used to optimize a linear objective
function subject to a set of linear equality and/or inequality constraints. It is widely applied in fields such
as operations research, economics, engineering, and management sciences.
Section 2: Formulation of LPP
The general form of a linear programming problem is: Maximize/Minimize Z = c■x■ + c■x■ + ... +
c■x■ Subject to: a■■x■ + a■■x■ + ... + a■■x■ ≤ b■ a■■x■ + a■■x■ + ... + a■■x■ ≤ b■ ...
a■■x■ + a■■x■ + ... + a■■x■ ≤ b■ and x■, x■, ..., x■ ≥ 0
Section 3: Standard Form, Slack & Surplus Variables
To apply the Simplex Method, the LPP must be expressed in standard form: 1. The objective function
should be a maximization problem. 2. All constraints must be expressed as equalities. 3. All variables
must be non-negative. Slack variables are added to '≤' constraints, surplus variables are subtracted
from '≥' constraints, and artificial variables may be introduced for equality constraints in certain cases.
Section 4: The Simplex Method – Steps
Step 1: Convert the LPP to standard form. Step 2: Construct the initial simplex tableau. Step 3: Identify
the entering and leaving variables using the optimality condition. Step 4: Perform pivot operations to
update the tableau. Step 5: Repeat until no further improvement is possible. Step 6: Interpret the final
tableau to obtain the optimal solution.
Section 5: Solved Example – Maximization
Example: Maximize Z = 3x■ + 2x■ subject to constraints: x■ + x■ ≤ 4 x■ ≤ 2 x■ ≤ 3 x■, x■ ≥ 0
Solution using Simplex Method: Step 1: Introduce slack variables s■, s■, s■. Step 2: Initial tableau is
constructed. Step 3: Apply pivoting until optimal solution is reached. Final solution: x■ = 2, x■ = 2, Z =
10.
Section 6: Special Cases in Simplex Method
1. Multiple Optimal Solutions: Occurs when more than one solution yields the same optimal value. 2.
Unbounded Solutions: When the objective function can be increased indefinitely. 3. Infeasible Solutions:
When no solution satisfies all constraints. 4. Degeneracy: Occurs when a basic variable takes value
zero in the solution.
Section 7: Practice Problems
1. Maximize Z = 5x■ + 4x■ subject to: 6x■ + 4x■ ≤ 24 x■ + 2x■ ≤ 6 x■, x■ ≥ 0 2. Minimize Z = 2x■ +
3x■ subject to: x■ + x■ ≥ 5 x■ + 3x■ ≥ 8 x■, x■ ≥ 0 3. Solve any two LPPs using Simplex Method and
interpret the results.