Linear Programming: Simplex Method Example

In this section we will provide a simplex method example. Standard maximization problems are special kinds of linear programming problems (LPP).

For problems involving more than two variables or problems involving numerous constraints, it is advisable to use solution techniques that are adaptable to computers. One such technique is discussed below:

Maximization Case: Linear Programming Simplex Method Example

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.

Find out a suitable product mix so as to maximize the profit.

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

Use Horizontal Scrollbar to View Full Table Calculation.

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.

Table 2

Simplex Method: Final Optimal 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.