Simplex Method

Example 2

Luminous Lamps produces three types of lamps - A, B, and C. These lamps are processed on three machines - X, Y, and Z. The full technology and input restrictions are given in the following table.

Solution.

The decision problem can be formulated as

Maximize z = 12x₁ + 3x₂ + x₃

subject to

10x₁ + 2x₂ + x₃  £ 100
7x₁ + 3x₂ + 2x₃  £ 77
2x₁+ 4x₂ + x₃  £ 80

x₁, x₂, x₃ ³ 0

Converting inequalities to equalities

10x₁ + 2x₂ + x₃ + x₄ = 100
7x₁ + 3x₂ + 2x₃ + x₅ = 77
2x₁+ 4x₂ + x₃ + x₆ = 80
x₁, x₂, x₃, x₄, x₅, x₆ ³ 0

Where x₄, x₅ and x₆ are slack variables.

Including these slack variables in the objective function, we get

Maximize z = 12x₁ + 3x₂ + x₃ + 0x₄ + 0x₅ + 0x₆

Initial basic feasible solution

x₁ = 0, x₂ = 0, x₃ = 0, z = 0
x₄ = 100, x₅ = 77, x₆ = 80

Table 1

Key column = x₁ column.
Minimum (100/10, 77/7, 80/2) = 10
Key row = x₄ row
Pivot element = 10
x₄ departs and x₁ enters

Now we are assuming that you can easily calculate the values yourself.

"One that would have the fruit must climb the tree." -Thomas Fuller

Table 2

Final Table

An optimal policy is x₁ =73/8, x₂ = 35/8, x₃ = 0.
The associated optimal value of the objective function is z = 12 X (73/8) + 3 X (35/8) + 1 X 0 = 981/8.