# Minimization Case: Simplex Method

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.

## Minimization Problem: General Linear Programming Problem (LPP)

Minimize z = c1x1 + c2x2 + c3x3 + .........+ cnxn

subject to

a11x1 + a12x2 + a13x3 + .........+ a1nxn ≥ b1
a21x1 + a22x2 + a23x3 + .........+ a2nxn ≥ b2
.........................................................................
am1x1 + am2x2 + am3x3 + .........+ amnxn ≥ bm
x1, x2,....., xn≥ 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 = c1x1 + c2x2 + c3x3 + .........+ cnxn

It can be written as
Max. z = -(c1x1 + c2x2 + c3x3 + .........+ cnxn)

##### Converting inequalities to equalities

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

a11x1 + a12x2 + a13x3 + .........+ a1nxn - s1 = b1
a21x1 + a22x2 + a23x3 + .........+ a2nxn - s2 = b2
..............................................................................
am1x1 + am2x2 + am3x3 + .........+ amnxn - sm = bm
x1, x2,....., xn≥ 0
s1, s2,....., sm≥ 0

An initial basic feasible solution is obtained by setting x1 = x2 =........ = xn = 0
-s1 = b1 or s1 = -b1
-s2 = b2 or s2 = -b2
..............................
-sm = bm or sm = -bm

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

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

a11x1 + a12x2 + a13x3 + .........+ a1nxn - s1 + A1 = b1
a21x1 + a22x2 + a23x3 + .........+ a2nxn - s2 + A2 = b2
..............................................................................
am1x1 + am2x2 + am3x3 + .........+ amnxn - sm + Am = bm

x1, x2,....., xn≥ 0
s1, s2,....., sm≥ 0
A1, A2,....., Am≥ 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
A1 = b1 , A2 = b2, ....., Am = bm

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.

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.

Share and Recommend