Lecture 39: The Simplex Method
Complete Exam Study Notes & Explanations (Page 1 to 13)
1. Introduction: Why Use the Simplex Method?
In our previous lectures, we used the Graphical Method to solve linear programming problems.
However, graphs are limited because they can only handle two decision variables (X and Y) on a flat
sheet of paper.
If a business makes 3, 5, or 100 different types of items, we cannot draw a graph for it. To solve real-
world problems with many variables, we use the Simplex Method. This method uses structured math
tables (matrices) instead of drawings to find the optimal solution step-by-step.
2. Problem Setup & The Core Story
A factory wants to maximize its total profit by manufacturing two goods: Item X and Item Y.
• Decision Variables:
◦ X: Quantity of Item X produced
◦ Y: Quantity of Item Y produced
• Objective Function (Our Main Goal):
Maximize Profit (P) = 5X + 6Y
• Structural Constraints (The Factory Rules):
◦ Labor Limit: 3X + 2Y ≤ 120 (Maximum available labor is 120 hours)
◦ Material Limit: 4X + 6Y ≤ 260 (Maximum available material is 260 units)
◦ Non-Negative Rule: X ≥ 0 and Y ≥ 0 (Production numbers cannot be negative)
3. The Trick: Introducing "Slack Variables" (S₁ and S₂)
The Simplex Method cannot process "less than or equal to" (≤) signs directly. It needs exact equations
with equal (=) signs. To fix this, we introduce hidden dummy variables called Slack Variables.
What is a Slack Variable? It represents unused or wasted resources.
• S₁ (Slack 1): Unused labor hours leftover in the factory.
• S₂ (Slack 2): Unused material units leftover in the factory.
We rewrite our mathematical statements into direct equations by keeping all resource limits on the
right side and moving objective coefficients to the left side:
Line 0 (Objective Row): P - 5X - 6Y + 0(S₁) + 0(S₂) = 0
Line 1 (Labor Equation): 3X + 2Y + S₁ = 120
Line 2 (Material Equation): 4X + 6Y + S₂ = 260
4. Table 1: The Initial Step (Pages 5 - 8)
At the very beginning, we assume we are lazy and producing nothing: X = 0 and Y = 0. This means
our profit is 0, all labor hours are wasted (S₁ = 120), and all materials are wasted (S₂ = 260).
Basic Variable P X Y (Entering) S₁ S₂ Constant Ratio (Constant / Y)
P (Profit) 1 -5 -6 0 0 0 -
S₁ 0 3 2 1 0 120 120 / 2 = 60
S₂ (Leaving) 0 4 6 (Pivot) 0 1 260 260 / 6 = 43.33
How to Read Table 1 & Make Moves:
1. Find the Entering Variable (The Column): Look at the Profit Row. Find the most negative
number. It is -6 under column Y. This means Y enters the basis because it gives the highest
per-unit profit.
2. Find the Leaving Variable (The Row): Divide the Constant values by the values in the Y
column to find the replacement ratios. The smallest positive ratio wins. 43.33 is smaller than
60, so row S₂ leaves the table.
3. Find the Pivot Element: The intersection point of the entering column and leaving row is the
number 6.
5. Page 9 & 10: Transforming Table 1 into Table 2
The golden rule of Simplex is: Convert the Pivot Element into 1, and make all other numbers in its
column equal to 0 using Row Operations.
Step A: Make the Pivot Element = 1
To turn the 6 into a 1, we divide the entire third row (Row 3) by 6. This row changes its name from S₂
to Y:
New Row 3 (R₃') = [0, 4/6, 1, 0, 1/6, 43.33]
Step B: Turn all other numbers in Column Y into 0
• Fixing the Profit Row (Row 1): It has a value of -6. We remove it by calculating: Old Row 1 + (6 ×
New Row 3).
New Row 1 = [1, -1, 0, 0, 1, 260]
Notice that our constant profit has successfully jumped from 0 up to 260!
• Fixing the S₁ Row (Row 2): It has a value of 2. We remove it by calculating: Old Row 2 - (2 ×
New Row 3).
New Row 2 = [0, 5/3, 0, 1, -1/3, 33.33]
6. Page 11 & 12: Analyzing Table 2 & Initiating Cycle 2
Let's compile our new values into Table 2 to inspect if we have achieved the absolute best outcome.
Basic Variable P X (Entering) Y S₁ S₂ Constant Ratio (Constant / X)
P (Profit) 1 -1 0 0 1 260 -
S₁ (Leaving) 0 5/3 (Pivot) 0 1 -1/3 33.33 33.33 / (5/3) = 20
Y 0 4/6 1 0 1/6 43.33 43.33 / (4/6) = 65
Is the Game Over yet?
No! Look at the top Profit Row. There is still a negative value remaining: -1 under column X. This
indicates we can make more profit by producing Item X.
• New Entering Column: Column X enters because of the negative value (-1).
• New Leaving Row: Compare ratios. 20 is smaller than 65. Therefore, row S₁ leaves the
table.
• New Pivot Element: The intersection point is 5/3.
7. Page 12 & 13: Table 3 (The Final Optimal Winner)
We repeat the exact row transformation rules to clean our new pivot column X:
1. Multiply the leaving row (Row 2) by 3/5 to turn the pivot element (5/3) into 1. This row changes its
name to X.
2. Eliminate the -1 in the Profit Row and the 4/6 in Row 3 using row addition and subtraction routines.
This outputs our final completed math arrangement:
Basic Variable P X Y S₁ S₂ Constant (Final Answer)
P (Profit) 1 0 0 0.6 0.8 280
X 0 1 0 0.6 -0.2 20
Y 0 0 1 -0.4 0.3 30
8. Final Exam Summary & Conclusion
Why is this the final solution?
Look closely at the top Profit row of Table 3. There are absolutely no negative values remaining
([1, 0, 0, 0.6, 0.8]). This indicates that no more profit can be squeezed out. We have reached the
peak outcome!
Exact Coordinates to Write in the Exam:
• Optimal Quantity of Item X to produce = 20 units
• Optimal Quantity of Item Y to produce = 30 units
• Maximum Achievable Profit (P) = Rs. 280
Double Check Rule: Profit = 5X + 6Y → 5(20) + 6(30) = 100 + 180 = Rs. 280. The matrix matches
perfectly!