Simplex Method

Two Phase Method

Example 2

Maximize z = 12x₁ + 15x₂ + 9x₃

subject to

8x₁ + 16x₂ + 12x₃ £ 250
4x₁ + 8x₂ + 10x₃ ³ 80
7x₁ + 9x₂ + 8x₃ = 105

x₁, x₂, x₃ ³ 0

Solution.

Introducing slack, surplus & artificial variables

8x₁ + 16x₂ + 12x₃ + x₄ = 250
4x₁ + 8x₂ + 10x₃ – x₅ + A₁ = 80
7x₁ + 9x₂ + 8x₃ + A₂ = 105

Where:
x₄ is a slack variable.
x₅ is a surplus variable.
A₁& A₂ are artificial variables.

Phase 1

Maximize 0x₁ + 0x₂ + 0x₃ + 0x₄ + 0x₅ + (–A₁) + (–A₂)

subject to

8x₁ + 16x₂ + 12x₃ + x₄ = 250
4x₁ + 8x₂ + 10x₃ – x₅ + A₁ = 80
7x₁ + 9x₂ + 8x₃ + A₂ = 105

x₁, x₂, x₃, x₄, x₅, A₁, A₂ ³ 0

Equating x₁, x₂, x₃, x₅ to zero.

Initial basic feasible solution

x₄ = 250, A₁= 80 , A₂ = 105

Table 1

Table 2

Here, Phase 1 terminates because both the artificial variables have been removed from the basis.

Phase 2

Table 3

Table 4

The optimal solution is:
x₁ = 6, x₂ = 7, x₃ = 0
z = 12 X 6 + 15 X 7 + 9 X 0 = 177.

Well, after going through this section you definitely deserve some food. Before moving to the next section, you must take a break because you really deserve it.

"Studying all the while without relaxation degrades a person's performance." -Vinay Chhabra & Manish Dewan