Introduction:

The non–negativity constraint of a linear programming problem restricts that the values of all variables in the problem say for example x, y and z or a, b, c and d etc. must be = 0. Sometimes we may come across a situation that the values of the variables are unrestricted, i.e., may assume any value (0 or > 1 or < 1) i.e., to say that the ≥ sign is not required. In such cases to maintain non-negativity restriction for all variables, each variable is replaced by two non-negative variables, say for example: x, y and z are replaced by x' and x", y' and y", z' and z" respectively. If x' > x", then x is positive, while x' < x" then x is negative.

 

Example:Maximize Z = 2x 3y s.t.

–1x 2y ≤ 4

1x 1y ≤ 6

1x 3y ≤ 9 and x and y are unrestricted.

As it is given that both x and y are unrestricted in sign they are replaced by non–negative variables, x' and x", y' and y" respectively. This is subjected to x = x' – x" and y = y' – y". By introducing slack variables and non–negative variables the simplex format is: Maximize Z = 2 (x' – x") 3 (y' – y") 0S₁ 0S₂ 0S₃ s.t.

– 1 (x' – x") 2 (y' – y") 1S₁ 0S₂ 0S₃ = 4

1 (x' – x") 1 (y' – y") 0S₁ 1S₂ 0S = 6

1 (x' – x") 3 (y' – y") 0S₁ 0S₂ 1S₃ = 9

x', x", y', y" and S₁, S₂ and S₃ all ≥ 0.