Simplex Method

Minimization Case

In the previous section, the simplex method was applied to linear programming problems where the objective was to maximize the profit with less than or equal to type constraints. In many cases, however, constraints may of type ³ or = and the objective may be minimization (e.g., cost, time, etc.). Thus, in such cases, simplex method must be modified to obtain an optimal policy.

Consider the general linear programming problem

Minimize z = c₁x₁ + c₂x₂ + c₃x₃ + .........+ c_nx_n

subject to

a₁₁x₁ + a₁₂x₂ + a₁₃x₃ + .........+ a_1nx_n ³ b₁
a₂₁x₁ + a₂₂x₂ + a₂₃x₃ + .........+ a_2nx_n ³ b₂
.........................................................................
a_m1x₁ + a_m2x₂ + a_m3x₃ + .........+ a_mnx_n ³ b_m
x₁, x₂,....., x_n³ 0

Changing the sense of the optimization

Any linear minimization problem can be viewed as an equivalent linear maximization problem, and vice versa.

Min. z = c₁x₁ + c₂x₂ + c₃x₃ + .........+ c_nx_n

It can be written as
Max. z = -(c₁x₁ + c₂x₂ + c₃x₃ + .........+ c_nx_n)

Converting inequalities to equalities

Introducing surplus variables (negative slack variables) to convert inequalities to equalities

a₁₁x₁ + a₁₂x₂ + a₁₃x₃ + .........+ a_1nx_n - s₁ = b₁
a₂₁x₁ + a₂₂x₂ + a₂₃x₃ + .........+ a_2nx_n - s₂ = b₂
..............................................................................
a_m1x₁ + a_m2x₂ + a_m3x₃ + .........+ a_mnx_n - s_m = b_m
x₁, x₂,....., x_n³ 0
s₁, s₂,....., s_m³ 0

An initial basic feasible solution is obtained by setting x₁ = x₂ =........ = x_n = 0
-s₁ = b₁ or s₁ = -b₁
-s₂ = b₂ or s₂ = -b₂
..............................
-s_m = b_m or s_m = -b_m

which is not feasible because it violates the non-negativity stipulation, (i.e., s₁ ³ 0). Therefore, we need artificial variables.

After introducing artificial variables, the set of constraints can be written as

a₁₁x₁ + a₁₂x₂ + a₁₃x₃ + .........+ a_1nx_n - s₁ + A₁ = b₁
a₂₁x₁ + a₂₂x₂ + a₂₃x₃ + .........+ a_2nx_n - s₂ + A₂ = b₂
..............................................................................
a_m1x₁ + a_m2x₂ + a_m3x₃ + .........+ a_mnx_n - s_m + A_m = b_m

x₁, x₂,....., x_n³ 0
s₁, s₂,....., s_m³ 0
A₁, A₂,....., A_m³ 0

Now, an initial basic feasible solution can be obtained by setting all the decision and surplus variables to zero. Thus, an initial basic feasible solution to LPP is
A₁ = b₁ , A₂ = b₂, ....., A_m = b_m

Now to obtain an optimal solution, we must drive out the artificial variables. Following are the two methods to solve linear programming problems in such cases.

• Two Phase method
• M method

Don't worry if you are not able to understand the above mathematical formulation. In the following sections, we illustrate the concept with the help of some "well-behaved" examples.