# An alternative approach to the LP problem with equality constraints.

Abstract This paper gives an alternative approach to the solution of the LP problem with equality constraints. In this scheme, the constraint system of linear equations is first solved by elementary row operations (if such a solution exists. In the second stage, the solution of the system of linear equations is directly plugged in the objective function and then it is minimized. This scheme thus avoids the use of the simplex method.

Keywords Linear programming, equality constraint, elementary row operations.

[section] 1. Introduction

In a recent paper, Ru, Shen and Xue [1] considered the problem of finding an initial basic feasible solution (bfs) of the LP problem of the form

min z - [C.sup.t] X s.t. AX = B, X [greater than or equal to] 0, (1)

where

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

In (1), without loss of generality, we may assume that B > 0; for otherwise, if some [b.sub.i] < 0 (1 [less than or equal to] i [less than or equal to] m), then multiplying the i-th constraint throughout by (-1), we get one with (-[b.sub.i]) > 0.

To find an initial bfs of the LP problem (1), the procedure suggested by Ru et al. [1] is as follows

Step 1 : Starting with the augmented matrix (A | B), reduce it to a form with an identity matrix of desired order, by elementary row operations only.

Note that, the elementary row operations applicable in this case are

(a) multiplying any row of (A | B) by a positive constant,

(b) multiplying any row of (A | B) by a constant and adding it to a second row.

Throughout this paper, the first row operation would be denoted by [R.sub.i] [right arrow] [kR.sub.i], (which means that the i-th row [R.sub.i] is multiplied by the constant k, where k > 0), and the second row operation would be denoted by [R.sub.i], [right arrow] [R.sub.i] + [kR.sub.j] (which means that the j-th row [R.sub.j] is multiplied by the constant k and the resulting row is added, term-by-term, to the i-th row [R.sub.i], to get the new i-th row. Note that the latter row operation is allowed only if [b.sub.i] + [kb.sub.j] [greater than or equal to] 0.

If rank(A) = rank(A | B) = l([less than or equal to] m), then using the above elementary row operations, it is possible to find a unit matrix of order l, which may be exploited to find an initial bfs of the LP problem (1). It may be mentioned here that, if l < m, then only l of the m system of linear equations AX = B are independent, and the remaining l - m equations can be ignored. It may also be mentioned here that, if rank(A) [not equal to] rank(A | B), then the system of linear equations AX = B is inconsistent, and as such, the LP problem (1) is infeasible.

Step 2 : With the initial bfs found in Step 1 above, form the initial simplex tableau in the usual manner.

Step 3 : Proceed in the usual way of the simplex method to find an optimal solution. The method outlined above is nevertheless not a new one. In fact, the same procedure has been followed by Papadimitriou and Steiglitz [2].

In the next section, we propose an alternative approach.

[section] 2. An alternative approach

In this section, we suggest an alternative approach to the solution of the LP problem (1). The procedure is quite simple, and can be done in the following two steps.

Step 1 : Reduce the system of linear equations AX = B to a form containing the unit matrix of requisite order, using elementary row operations only.

Step 2 : With the solution found in Step 1, consider the problem of minimizing z = [C.sub.t]X.

Thus, the method works with the solution of the system of linear equations AX = B and the objective function only, avoiding the simplex method completely.

We illustrate our method with the help of the following examples, due to Ru et al. [1].

Example 2.1. Consider the following LP problem:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

To solve the above LP problem, we first solve the constraint system of linear equations, using elementary row operations only. We thus start with the augmented matrix (A | B) and proceed as follows, using the indicated row operations:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The final tableau gives the following solution:

[x.sub.1] = 2, [x.sub.3] = 0, [x.sub.2] = 1 + 2/3[x.sub.4] = 1 + 2/3 t; (t [greater than or equal to] 0 is any real number),

and the objective function is z = 4[x.sub.1] + 3[x.sub.2] = 8 + 3(1 + 2/3 t) = 11 + 2/3 t. Since the objective is to minimize z, it is clear that z is minimized when t = 0, and the optimal solution of the given LP problem is thus [x.sup.*.sub.1] = 2, [x.sup.*.sub.2] = 1, [x.sup.*.sub.3] = 0, [x.sup*.sub.4 = 0; min [z.sup.*] = 11.

Example 2.2. To solve the LP problem

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

we first solve the constraint system of linear equations by elementary row operations. This is done below.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The final tableau is equivalent to the following system of linear equations

3[x.sub.1] + [x.sub.4] -2[x.sub.5] = 12

[x.sub.2] -[x.sub.5] = 2

-2[x.sub.1] + [x.sub.3] = 1

with the solution

[x.sub.1] = [t.sub.1], [x.sub.5] = [t.sub.2], [x.sub.2] = 1 + [t.sub.2], [x.sub.3] = 1 + 2[t.sub.1], [x.sub.4] = 12 - 3[t.sub.1] + 2[t.sub.2]; ([t.sub.1] [greater than or equal to] 0, [t.sub.2] [greater than or equal to] 0 are any real numbers), and the objective function is z = 2 - [t.sub.1] + [t.sub.2].

Since the objective is to minimize z, it is evident that [t.sub.2] should be as small as possible and [t.sub.1] should be as large as possible. Now, since [x.sub.4] = 12 - 3[t.sub.1] + 2[t.sub.2] [greater than or equal to] 0, we see that, we must have [t.sub.2] = 0, [t.sub.1] = 4. Hence, the desired optimal solution is

[x.sup.*.sub.1] = 4, [x.sup.*.sub.2] = 1, [x.sup.*.sub.3] = 9, [x.sup.*.sub.4] = 0, [x.sup.*.sub.5] = 0; min [z.sup.*] = -3.

Example 2.3. To solve the LP problem

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

we start with the augmented matrix (A | B) and proceed as follows, using the indicated row operations:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The final tableau is equivalent to the following system of linear equations

[x.sub.2] + 1/4 [x.sub.3] - 2/3 [x.sub.4] = 1

[x.sub.1] + 1/2 [x.sub.3] = 2

with the solution

[x.sub.3] = [t.sub.1], [x.sub.1] = 2 - 1/2 [t.sub.1], [x.sub.4] = [t.sub.2], [x.sub.2] = 1 - 1/4 [t.sub.1] + 2/3 [t.sub.2]; ([t.sub.1] [greater than or equal to] 0, [t.sub.2] [greater than or equal to] 0 are any real numbers),

and the objective function is z = 8 + [t.sub.1].

Since the objective is to minimize z, we must have [t.sub.1] - 0. Hence, the desired solution is

[x.sup.*.sub.1] = 2, [x.sup.*.sub.2] = 1 + 2/3 t, [x.sup.*.sub.3] = 0, [x.sup.*.sub.4] = t(t [greater than or equal to] 0 is any real number); min z* = 8.

The above solution shows that the given LP problem has infinite number of solutions.

[section] 3. Some observations and remarks

In the previous section, we have illustrated our method with the help of three simple examples. However, in large-scale problems, the success as well as the computational efficiency of the method remains to be checked out.

Clearly, the method is useful when the correct basis has been found. This point is illustrated with the help of the following example, due to Papadimitriou and Steiglitz [2].

Example 3.1. Consider the LP problem below

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

We first solve the constraint system of linear equations by elementary row operations, using the indicated row operations.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

The final tableau is equivalent to the following system of linear equations

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

with the solution

[x.sub.1] = [t.sub.1], [x.sub.3] = [t.sub.2]([t.sub.1] [greater than or equal to] 0, [t.sub.2] [greater than or equal to] 0 are any real numbers),

[x.sub.2] = 1/2 - 3/2 [t.sub.1] - 1/2 [t.sub.2], [x.sub.4] = 5/2 - 7/2 [t.sub.1] - 1/2 [t.sub.2], [x.sub.5] = 3/2 + 11/2 [t.sub.] + 3/2 [t.sub.2];

and the objective function is z = 9/2 + 3/2([t.sub.1] + [t.sub.2]).

Since the objective is to minimize z, it is evident that we must have [t.sub.1] = 0, [t.sub.2] = 0, giving the desired optimal solution

[x.sup.*.sub.1 = 0, [x.sup.*.sub.2] = 1, [x.sup.*.sub.3] = 0, [x.sup.*.sub.4] = 5/2, [x.sup.*.sub.5] = 3/2; min [z.sup.*] = 9/2.

On the other hand, the solution below

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

leads to the system of equations

3[x.sub.1] +2[x.sub.2] +[x.sub.3] = 1

2[x.sub.1] -[x.sub.2] +[x.sub.4] = 2

-[x.sub.1] +3[x.sub.2] +[x.sub.5] = 3

whose solution is

[x.sub.1] = [t.sub.1], [x.sub.2] = [t.sub.2] ([t.sub.1] [greater than or equal to] 0, [t.sub.2] [greater than or equal to] 0 are any real numbers,

[x.sub.3] = 1 - 3[t.sub.1] - 2[t.sub.2], [x.sub.4] - 2 - 2[t.sub.1] + [t.sub.2], [x.sub.5] - 3 + t1 - 3[t.sub.2];

and the objective function is z = 3[2 - ([t.sub.1] + [t.sub.2])].

Thus, the problem of finding the solution of the given LP problem reduces to the problem of solving the LP problem

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

The optimal solution of the above LP problem is [t.sub.1] = 0, [t.sub.2] = 1/2. Hence, the optimal solution of the original LP problem is

[x.sup.*.sub.1] = 0, [x.sup.*.sub.2] = 1/2, [x.sup.*.sub.3 = 0, [x.sup.*.sub.4] = 5/2, [x.sup.*.sub.5] = S min [z.sup.*] = 9/2.

The above example shows that, in the alternative approach proposed in this paper, as well as the method suggested by Ru et al. [1], the choice of the unit matrix (of desired order during the solution of the system of linear equations AX = B (by elementary row operations may save the number of iterations considerably. However, no particular criterion is specified in this respect. It thus still remains to check how far these methods can compete with the existing method.

References

[1] Shaofeng Ru, Maoxing Shen and Xifeng Xue, A Concise Way of Determination for LP Initial Feasible Basis of Simplex Method, Scientia Magna, 4(2008, No.1, 142-147.

[2] Christos H. Papadimitriou and Kenneth Steiglitz, "Combinatorial Optimization : Algorithms and Complexity" , Dover Publications, Inc., 1998.