Scribd
Upload
3 views4 pages

Simplex Method Solution

The document outlines the Simplex Method for solving a maximization linear program through a series of steps including setting up an initial tableau, selecting entering and leaving variables, and performing pivots. It details the iterations leading to the final tableau, where the optimal solution is found with x₁ = 20, x₂ = 60, resulting in a maximum profit of Z = 260. The process concludes when no negative coefficients remain in the Z-row, indicating that the solution is optimal.

Uploaded by

Tejas S Trivedi
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
3 views4 pages

Simplex Method Solution

The document outlines the Simplex Method for solving a maximization linear program through a series of steps including setting up an initial tableau, selecting entering and leaving variables, and performing pivots. It details the iterations leading to the final tableau, where the optimal solution is found with x₁ = 20, x₂ = 60, resulting in a maximum profit of Z = 260. The process concludes when no negative coefficients remain in the Z-row, indicating that the solution is optimal.

Uploaded by

Tejas S Trivedi
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

The Simplex Method

Solving a Maximization Linear Program

Step 1 — Initial Tableau


Basis x₁ x₂ s₁ s₂ RHS
s₁ 2 1 1 0 100
s₂ 1 1 0 1 80
Z -4 -3 0 0 0

Current basic variables:

s₁ = 100, s₂ = 80
Non-basic variables:

x₁ = x₂ = 0
Current profit:

Z=0

Step 2 — Choose Entering Variable


Look at the Z-row:

Variable Coefficient
x₁ -4
x₂ -3

For a maximization problem, the most negative coefficient enters the basis, because increasing that variable
improves the objective the fastest.
The most negative coefficient is −4, therefore:

x₁ enters the basis

Step 3 — Choose Leaving Variable (Minimum Ratio Test)


Determine which current basic variable must leave, using the ratio:

Ratio = RHS ÷ (positive coefficient of entering variable)


● Row 1 (s₁): coefficient of x₁ = 2 → ratio = 100 / 2 = 50
● Row 2 (s₂): coefficient of x₁ = 1 → ratio = 80 / 1 = 80
The smallest positive ratio determines the leaving variable. Since 50 < 80:

s₁ leaves the basis

Step 4 — Pivot
The pivot element is 2 (Row 1, column x₁). Divide Row 1 by 2:

Basis x₁ x₂ s₁ s₂ RHS
x₁ 1 0.5 0.5 0 50

Eliminate x₁ from Row 2 (New Row 2 = Old Row 2 − Row 1):

Basis x₁ x₂ s₁ s₂ RHS
s₂ 0 0.5 -0.5 1 30

Update the Z-row (New Z = Old Z + 4 × Row 1):

Basis x₁ x₂ s₁ s₂ RHS
Z 0 -1 2 0 200

Tableau After First Iteration


Basis x₁ x₂ s₁ s₂ RHS
x₁ 1 0.5 0.5 0 50
s₂ 0 0.5 -0.5 1 30
Z 0 -1 2 0 200

Current solution:

x₁ = 50, x₂ = 0, s₂ = 30
Profit:

Z = 200

Step 5 — Second Entering Variable


Look at the Z-row. The only negative coefficient remaining is −1, under x₂:

x₂ enters the basis

Step 6 — Leaving Variable


Apply the minimum ratio test again:
● Row 1 (x₁): coefficient of x₂ = 0.5 → ratio = 50 / 0.5 = 100
● Row 2 (s₂): coefficient of x₂ = 0.5 → ratio = 30 / 0.5 = 60

The smallest ratio is 60, so:

s₂ leaves the basis (pivot element = 0.5)

Step 7 — Make Pivot Element = 1


Divide Row 2 by 0.5:

Basis x₁ x₂ s₁ s₂ RHS
x₂ 0 1 -1 2 60

Step 8 — Eliminate x₂ from Other Rows


New Row 1 = Old Row 1 − 0.5 × Row 2:

Basis x₁ x₂ s₁ s₂ RHS
x₁ 1 0 1 -1 20

New Z-row = Old Z-row + Row 2:

Basis x₁ x₂ s₁ s₂ RHS
Z 0 0 1 2 260

Final Tableau
Basis x₁ x₂ s₁ s₂ RHS
x₁ 1 0 1 -1 20
x₂ 0 1 -1 2 60
Z 0 0 1 2 260

Step 9 — Read the Solution


Basic variables (from the Basis column):

x₁ = 20, x₂ = 60
Non-basic variables (equal to zero):

s₁ = 0, s₂ = 0
Maximum profit:

Z = 260
Why Does the Algorithm Stop Here?
The final Z-row is:

Variable Coefficient
x₁ 0
x₂ 0
s₁ 1
s₂ 2

There are no negative coefficients remaining in the Z-row. In the simplex method for a maximization problem, this
means no non-basic variable can enter the basis to further improve the objective value.
Therefore, the current basic feasible solution is optimal:
x₁ = 20, x₂ = 60, Z = 260

You might also like