Simplex Method: Special Cases

In this section, we will discuss some special cases of simplex method in linear programming (LP).

1. Unrestricted (unconstrained) Variables

Sometimes decision variables are unrestricted in sign (positive, negative or zero). In all such cases, the decision variables can be expressed as the difference between two non-negative variables. For example, if x₁ is unrestricted in sign, then

Put x₁ = x₁^' - x₁''

Unrestricted Variables: Simplex Method Examples

Maximize z = 2x₁ + 3x₂

subject to

-x₁ + 2x₂ ≤ 4
x₁ + x₂ ≤ 6
x₁ + 3x₂ ≤ 9

x₁, x₂ are unrestricted in sign

Solution.

Since x₁ and x₂ are unrestricted in sign, we can replace them by non-negative variables x₁^' , x₁'', x₂^' , x₂^'' .

Put x₁ = x₁^' - x₁''
x₂ = x₂^' - x₂''

The given problem can be written as

Max. z = 2(x₁^' - x₁'') + 3(x₂^' - x₂'')

subject to

-(x₁^' - x₁'') + 2(x₂^' - x₂'') ≤ 4
(x₁^' - x₁'') + (x₂^' - x₂'') ≤ 6
(x₁^' - x₁'') + 3(x₂^' - x₂'') ≤ 9

Introducing slack variables

Max. z = 2x₁^' - 2x₁'' + 3x₂^' - 3x₂''

subject to

-x₁^' + x₁'' + 2x₂^' - 2x₂'' + x₃ = 4
x₁^' - x₁'' + x₂^' - x₂'' + x₄ = 6
x₁^' - x₁'' + 3x₂^' - 3x₂'' + x₅ = 9

Where x₃, x₄ and x₅ are slack variables

Simplex Method: Table 1

On small screens, scroll horizontally to view full calculation

Key column = x₂^' column.
Minimum (4/2, 6/1, 9/3) = 2
Key row = x₃ row.
Pivot element = 2
x₃ departs and x₂^' enters.

Table 2

Table 3

Use Horizontal Scrollbar to View Full Table Calculation

Table 4

The optimal solution is:
x₁^' = 9/2, x₁'' = 0, x₂^' = 3/2, x₂'' = 0.

Solution of the original problem is:
x₁ = x₁^' - x₁'' = 9/2 - 0 = 9/2
x₂ = x₂^' - x₂'' = 3/2 - 0 = 3/2
z = 2 X 9/2 + 3 X 3/2 = 27/2.