A LINEAR PROGRAMMING TRANSFORMATION

OF AN INCONSISTENT SYSTEM OF LINEAR EQUATIONS

INTO A CONSISTENT SYSTEM

Mohammad Fatehi, Miguel Paredes, Richard Hinthorn, and Hushang Poorkarimi

The University of Texas–Pan American

1. Introduction. The solution of many decision making problems requires solving a system of linear equations. If such a system happens to be inconsistent, then it is possible to transform it into a consistent system. In [3], Paredes et al. used an algebraic transformation in order to obtain a consistent system; and a weakness of this method from the point of view of the decision maker is discussed there, namely that it involves changing the amount of those resources whose coefficients caused the inconsistency, without taking into account the possibility of changing the amounts of the other resources. In the same paper Paredes et al. proposed to overcome such weakness by parameterizing the constant terms of the system, thus achieving a more flexible solution and giving the decision maker the chance to change the available amount of several resources. A new weakness arises because the solution set obtained is infinite. In [3], it was suggested that this new weakness may be overcome by using linear programming methods, which is the objective of this paper.

Let us informally state our problem and an outline of the solution. If we have an inconsistent system of linear equations, we shall transform it into a consistent system using an iterative process. It is assumed that the system has been operated on by the Gauss Jordan elimination method or some other method to determine the body of consistent and inconsistent equations. The iteration begins with the minimization of the left hand side of any one of the equations causing the inconsistency with respect to the body of consistent equations playing the role of constraints. The phase I of the simplex method [4] is used here to solve the linear programming problems. The objective function formed by the artificial variables is optimized. The left side of the first equation causing the inconsistency is equated to its minimum value obtained from the optimum solution of phase I; and this equation is added to the constraint equations. The left side of the second equation causing the inconsistency is minimized in the same manner as the first equation. It is then set equal to its value obtained from the phase I optimum solution and added to the constraint equations. This process continues until all equations causing the inconsistency have new constants and are added to the constraint equations. The equations that formed a consistent subsystem of the original system, together with the new equations obtained by iteration process, now form a consistent system.

2. Theorem. Let AX = B be a non–homogeneous inconsistent system of equations, where matrix A is of size m × n for m ≥ n; X and B are matrices of size n × 1 and m × 1, respectively. Furthermore, we assume that the inconsistent system has exactly k consistent equations with a non–negative solution. Then, the optimum solution of the phase I problem of the linear programming problem defined below will provide a solution to the system AX = B_{0}, where the first k components of B_{0} and B are the same and the remaining m − k components of B_{0} are θ_{i}, where θ_{i} is the value of each objective function obtained from the phase I problem.

(1)  θ_{i} = min ∑_{j=1}^{n} a_{ij}x_{j},

where

∑_{j=1}^{n} a_{ij}x_{j}

is the left hand side of the ith equation of the system AX = B when i = k + 1, k + 2, …, m subject to

∑_{j=1}^{n} a_{sj}x_{j} = b_{s}, s = 1, 2, 3, …, k,

and

∑_{j=1}^{n} a_{i−1,j}x_{j} = θ_{i−1}, when i = k + 2, …, m,

and

x_{j} ≥ 0, j = 1, 2, 3, …, n.

3. Proof. Let us define the objective function of the phase I problem by:

ϕ_{r} = min ∑_{i=1}^{r} x_{n+i} when r = k, k + 1, …, m − 1.

The objective function of the phase I problem is minimized subject to all the constraint equations formed in (1) in each iteration using phase I of the simplex method. Since the constraint equations formed in (1) are consistent, there will be a basic solution satisfying all the constraint equations. This implies that there will be a basic feasible solution. Since the phase I objective row of the simplex tableau is a linear combination of all the consistent system of equations formed in (1), ϕ_{r} can always be made equal to zero by phase I of the simplex method. If x_{j} is an optimum solution of the phase I problem for j = 1, 2, …, n+m, it follows that x_{j} = 0 for j = n + 1, …, n + m. Thus, the optimum solution of the phase I problem is a basic feasible solution to the original problem. Hence, the final optimum solution of the phase I problem satisfies all the constraints formed in (1) including the hyperplanes formed by:

∑_{j=1}^{n} a_{ij}x_{j} = θ_{i} when i = k + 1, k + 2, …, m.

Therefore, the inconsistent system AX = B will be transformed into a consistent system AX = B_{0}.

The following example illustrates a practical application of the method described in the theorem.

Example. A farmer is planning to cultivate three types of crops: cantaloupes, tomatoes, and watermelon. Table 1 shows the nitrogen, phosphate, and total hours of labor required for each acre of land. If he has 320 acres of land and wishes to utilize all his resources, how should he allocate the land to each crop so that all his available resources are used?

Table 1 Allocation of Crops to the Available Resources.

Cantaloupes  Tomatoes  Watermelon  Total
Land (acre)  x_{1}  x_{2}  x_{3}  320
Nitrogen (lb/acre)  120  150  40  26400
Phosphate (lb/acre)  80  80  0  12500
Labor (hour/acre)  27  31  17  9920

The solution is found by solving the system of equations

x_{1}+ x_{2}+ x_{3} = 320
120x_{1}+150x_{2}+40x_{3} =26400
80x_{1}+ 80x_{2}  =12500
27x_{1}+ 31x_{2}+17x_{3} = 9920,

whose reduced Gauss–Jordan form is

( \begin{matrix}1 & 0 & 0 & 1435/12 \\ 0 & 1 & 0 & 110/3 \\ 0 & 0 & 1 & 655/4 \\ 0 & 0 & 0 & 16625/6 \end{matrix} ) .

This implies that there is no solution to the system. The following linear programming problem, where we shall consider minimizing the total amount of labor, will transform the inconsistent system into a consistent system.

min θ = 27x_{1} + 31x_{2} + 17x_{3}

subject to

x_{1} +  x_{2} +  x_{3} = 320
120x_{1} + 150x_{2} + 40x_{3} =26400
80x_{1} + 80x_{2}  =12500
x_{1} ,  x_{2} ,  x_{3} ≥ 0.

Solving the problem using the phase I of the simplex algorithm, we obtain the following tableau with an optimum solution to the phase I problem given as:

x_{1} = \frac{1435}{12}, x_{2} = \frac{110}{3}, x_{3} = \frac{655}{4},

and objective value to the original problem and the phase I problem, respectively as:

θ = \frac{42895}{6}, ϕ = 0.

( \begin{matrix}0 & 0 & 1 & 1 & 0 & −1/80 & 655/4 \\ 0 & 1 & 0 & −4/3 & 1/30 & −1/30 & 110/3 \\ 1 & 0 & 0 & 4/3 & −1/30 & 11/240 & 1435/12 \\ 0 & 0 & 0 & 35/3 & 2/15 & −1/120 & 42895/6 \\ 0 & 0 & 0 & −1 & −1 & −1 & 0 \end{matrix} ) .

Hence, the following system is consistent.

x_{1} +  x_{2} +  x_{3} = 320
120x_{1} + 150x_{2} + 40x_{3} = 26400
80x_{1} + 80x_{2}  = 12500
27x_{1} + 31x_{2} + 17x_{3} =\frac{42895}{6}

Note that b_{4} of the original system has been changed to the objective value θ = 42895/6, obtained from the objective row of the simplex tableau.

Furthermore, Table 2 summarizes the allocation of resources corresponding to various optimal strategies.

Table 2 Optimal Strategies for the Farmer’s Problem.

Optimal strategy  Allocation of Resources
Cantaloupes  Tomatoes  Watermelon  Total
Minimizing Labor  \frac{1435}{12}  \frac{110}{3}  \frac{655}{4}  320
Minimizing Land  No Feasible Solution
Minimizing Nitrogen  No Feasible Solution
Minimizing Phosphate  No Feasible Solution

In real life applications, farmers might be interested in one particular optimal strategy, which is what was illustrated in our example, where we have minimized the total amount of labor. If the user has not defined preferences for a particular optimal strategy, then Table 2 presents a detailed definition of these alternative strategies in terms of the allocation of resources. This may help the user to define a ranking of the alternative allocation of resources which will induce a ranking of the optimal strategies. For example, the most cost effective strategy can be found in the situation described in Table 2. Let the prices of land, nitrogen, phosphate, and labor be p_{1}, p_{2}, p_{3} and p_{4}, respectively. Then the cost of the optimal strategy of minimizing labor is

320p_{1} + 26400p_{2} + 12500p_{3} + \frac{42895}{6}p_{4}.

If there were other optimal strategies providing a solution, then we would compute their cost as we did for the minimization of labor strategy, and select the optimal strategy with the smallest cost. It is important to observe that in this example the most cost effective solution out of all possible optimal solutions is the same as the solution obtained using the algebraic method proposed in [3]. Thus in this particular case, the application of the method described in the Theorem results in proving that the algebraic solution discussed in [3] actually has an optimality property.

One pedagogical value of the work in this paper is that it shows how, in real world applications, optimization may arise as a necessity imposed by the weakness in the solutions obtained by modeling using systems of linear equations. This paper has also a methodological value because it illustrates with a minimum of mathematical tools and in an applied context, how in the construction of mathematical models, the nature of the data creates the need for a sequence of models, which may or may not produce a solution for the problems. When solutions are obtained, they have different properties, presenting the user different options. This situation is a particular case of the methodology advocating the production of a sequence of models in order to improve the explanation of the phenomena being modeled. This methodology is attributed to Lakatos [2] and is rooted in Kuhn’s Theory on the structure of scientific revolutions [1]. Mathematics majors are rarely exposed to relatively simple examples that they can understand illustrating the contribution of mathematics in implementing scientific methodological principles.

\underline{References}

1. T. S. Kuhn, The Structure of Scientific Revolutions, 2nd edition, Chicago University Press, 1970.

2. I. Lakatos, “Falsification and the Methodology of Scientific Research Programs,” Criticism and the Growth of Knowledge, edited by I. Lakatos and A. Musgrave, Cambridge University Press, Cambridge, 1970.

3. M. Paredes, M. Fatehi, and R. Hinthorn, “The Transformation of an Inconsistent Linear System Into a Consistent System,” The AMATYC Review, 13 (1992), 28–33.

4. A. H. Taha, Operations Research An Introduction, 3rd edition, MacMillan Publishing Co., New York, 1982. æ