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.

**Minimize z** = c_{1}x_{1} + c_{2}x_{2} + c_{3}x_{3} + .........+ c_{n}x_{n}

subject to

a_{11}x_{1} + a_{12}x_{2} + a_{13}x_{3} + .........+ a_{1n}x_{n} ≥
b_{1}

a_{21}x_{1} + a_{22}x_{2} + a_{23}x_{3} + .........+ a_{2n}x_{n} ≥
b_{2}

.........................................................................

a_{m1}x_{1} + a_{m2}x_{2} + a_{m3}x_{3} + .........+ a_{mn}x_{n} ≥
b_{m}

x_{1}, x_{2},....., x_{n}≥
0

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

Min. z = c_{1}x_{1} + c_{2}x_{2} +
c_{3}x_{3} + .........+ c_{n}x_{n}

It can be written as

Max. z = -(c_{1}x_{1} + c_{2}x_{2} +
c_{3}x_{3} + .........+ c_{n}x_{n})

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

a_{11}x_{1} + a_{12}x_{2} + a_{13}x_{3} + .........+ a_{1n}x_{n} - s_{1} = b_{1}

a_{21}x_{1} + a_{22}x_{2} + a_{23}x_{3} + .........+ a_{2n}x_{n} - s_{2} = b_{2}

..............................................................................

a_{m1}x_{1} + a_{m2}x_{2} + a_{m3}x_{3} + .........+ a_{mn}x_{n} - s_{m} = b_{m}

x_{1}, x_{2},....., x_{n}≥
0

s_{1}, s_{2},....., s_{m}≥
0

An initial basic feasible solution is obtained by setting
x_{1} = x_{2} =........ = x_{n} = 0

-s_{1} =
b_{1} or s_{1} =
-b_{1}

-s_{2} =
b_{2} or s_{2} =
-b_{2}

..............................

-s_{m} =
b_{m} or s_{m} =
-b_{m}

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

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

a_{11}x_{1} + a_{12}x_{2} + a_{13}x_{3} + .........+ a_{1n}x_{n} - s_{1} + A_{1} = b_{1}

a_{21}x_{1} + a_{22}x_{2} + a_{23}x_{3} + .........+ a_{2n}x_{n} - s_{2} + A_{2} = b_{2}

..............................................................................

a_{m1}x_{1} + a_{m2}x_{2} + a_{m3}x_{3} + .........+ a_{mn}x_{n} - s_{m} + A_{m} = b_{m}

x_{1}, x_{2},....., x_{n}≥
0

s_{1}, s_{2},....., s_{m}≥
0

A_{1}, A_{2},....., 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_{1} = b_{1} , A_{2} = b_{2}, .....,
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.