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.
