MATHEMATICS

S. I. Zukhovitskii

SOME SUPPLEMENTS TO THE ALGORITHM FOR THE SOLUTION OF A GENERALIZED LINEAR PROGRAMMING PROBLEM

(Presented by Academician N. N. Bogolyubov, 13 III 1961)

1. In \((^1)\) an algorithm was constructed for solving the following problem: in \(n\)-dimensional Euclidean space there are given \(s\) planes

\[ \eta_j \equiv \eta_j(x) \equiv b_{1j}\xi_1+b_{2j}\xi_2+\cdots+b_{nj}\xi_n=0 \quad (j=1,\ldots,s) \tag{1} \]

and a convex closed polyhedron \(\Omega\), defined by the inequalities

\[ \delta_k \equiv \delta_k(x) \equiv a_{1k}\xi_1+a_{2k}\xi_2+\cdots+a_{nk}\xi_n+a_k\geq 0 \quad (k=1,\ldots,m); \tag{2} \]

in this polyhedron one must find a point \(x^*(\xi_1^*,\ldots,\xi_n^*)\) (the optimal point) that deviates most from the planes (1), i.e., such that

\[ \min_{1\leq j\leq s}\eta_j(x^*)=\max_{x\in\Omega}\min_{1\leq j\leq s}\eta_j(x). \]

This problem was considered by L. V. Kantorovich (see \((^2)\), where references are also given) as a mathematical model of the basic problem of production planning. In the present paper it will be shown how, by means of Jordan eliminations that have proved effective in the simplex method (see \((^3)\)), one can simplify the numerical scheme of the indicated algorithm, similarly to how this was done in \((^4)\) for the algorithm of Chebyshev approximation of an inconsistent system of linear equations and a system of linear inequalities.

2. Take an arbitrary point \(x'(\xi_1',\ldots,\xi_n')\in\Omega\) and write the systems (1) and (2), the coordinates of the point \(x'\), and the deviations

\[ \eta_1(x'),\ldots,\eta_s(x');\delta_1(x'),\ldots,\delta_m(x') \]

in the form of the following table

\[ \begin{array}{cccccc} \xi_1' & \xi_2' & \ldots & \xi_n' & 1 \\ \xi_1 & \xi_2 & \ldots & \xi_n & 1 \\ \hline \ldots & \ldots & & \ldots & \ldots & \ldots \\ \eta_j \Rightarrow & b_{1j} & b_{2j} & \ldots & b_{nj} & 0 & \eta_j(x') \\ \ldots & \ldots & & \ldots & \ldots & \ldots \\ \hline \ldots & \ldots & & \ldots & \ldots & \ldots \\ \delta_k \Rightarrow & a_{1k} & a_{2k} & \ldots & a_{nk} & a_k & \delta_k(x') \\ \ldots & \ldots & & \ldots & \ldots & \ldots \end{array} \qquad (j=1,\ldots,s;\ k=1,\ldots,m), \tag{3} \]

Let

\[ \eta_{j_1}(x')=\cdots=\eta_{j_{p_1}}(x')<\eta_j(x') \quad (j\ne j_1,\ldots,j_{p_1}) \]

and

\[ \delta_{k_1}(x')=\delta_{k_2}(x')=\cdots=\delta_{k_{p_2}}(x')=0,\quad \delta_k(x')>0 \quad (k\ne k_1,\ldots,k_{p_2}). \]

Putting \(p_1+p_2=p\), we shall regard the point \(x'\) as a \(p\)-th approximation to the point \(x^*\) and denote it by

\[ x_p(\xi_1^{(p)},\ldots,\xi_n^{(p)}); \]

the deviations \(\eta_{j_1}(x'),\ldots,\eta_{j_{p_1}}(x')\) and the corresponding planes will be called minimal, and the deviations \(\delta_{k_1}(x'),\ldots,\delta_{k_{p_2}}(x')\) and the corresponding planes will be called annulling.

As in (4), we successively carry out steps of Jordan eliminations with those of the rows \(j_1\)-th, \(\ldots\), \(j_{p_1}\)-th, \(k_1\)-th, \(\ldots\), \(k_{p_2}\)-th as pivots in which there are coefficients different from zero, among the remaining \(\xi_i\) after the preceding steps, each time taking as pivot the largest, in absolute value, of the indicated coefficients of the row under consideration.*

Suppose that we have succeeded in moving to the top of the table all minimal \(\eta_j\) and all vanishing \(\delta_k\). For convenience of notation we shall assume that
\(j_1=1,\ldots,j_{p_1}=p_1;\ k_1=1,\ldots,k_{p_2}=p_2\), and that the \(\eta_j\) have been rearranged with the \(\xi_j\), and the \(\delta_k\) with \(\xi_{p_1+k}\), so that the new table will have the following form:

\[ \begin{array}{cccccccccc} \eta_1(x_p)&\eta_{p_1}(x_p)&\delta_1(x_p)&\ldots&\delta_{p_2}(x_p)&\xi'_{p+1}&\ldots&\xi'_n&1&(4)\\ \eta_1&\eta_{p_1}&\delta_1&\ldots&\delta_{p_2}&\xi_{p+1}&\ldots&\xi_n&1& \end{array} \]

\[ \begin{array}{r|cccccccc|c} \eta_{p_1+1}=& b^{(p)}_{1,p_1+1}&\ldots&b^{(p)}_{p_1+1,p_1+1}&\ldots& b^{(p)}_{p+1,p_1+1}&\ldots&b^{(p)}_{n,p_1+1}&b^{(p)}_{p_1+1} &\eta_{p_1+1}(x_p)\\ \ldots&\ldots&&\ldots&&\ldots&&\ldots&\ldots&\ldots\\ \eta_s=& b^{(p)}_{1s}&\ldots&b^{(p)}_{p_1+1,s}&\ldots& b^{(p)}_{p+1,s}&\ldots&b^{(p)}_{ns}&b^{(p)}_{s} &\eta_s(x_p)\\ \hline \delta_{p_2+1}=& a^{(p)}_{1,p_2+1}&\ldots&a^{(p)}_{p_1+1,p_2+1}&\ldots& a^{(p)}_{p+1,p_2+1}&\ldots&a^{(p)}_{n,p_2+1}&a^{(p)}_{p_2+1} &\delta_{p_2+1}(x_p)\\ \ldots&\ldots&&\ldots&&\ldots&&\ldots&\ldots&\ldots\\ \delta_m=& a^{(p)}_{1m}&\ldots&a^{(p)}_{p_1+1,m}&\ldots& a^{(p)}_{pm}&\ldots&a^{(p)}_{nm}&a^{(p)}_{m} &\delta_m(x_p) \end{array} \]

where the expressions for \(\xi_1,\ldots,\xi_p\) should be written out separately.

We shall move from the point \(x_p\) along the straight line formed by the intersection of the \((n-p_1+1)\)-dimensional bisector plane
\(\eta_1=\eta_2=\eta_3=\ldots=\eta_{p_1}\), the \((n-p_2)\)-dimensional boundary plane
\(\delta_1=0,\ \delta_2=0,\ldots,\delta_{p_2}=0\), and the \(p\)-dimensional coordinate plane
\(\xi_{p+1}=\xi'_{p+1},\ \xi_{p+2}=\xi'_{p+2},\ldots,\xi_n=\xi'_n\), until the deviations from the planes \(\eta_1=0,\ldots,\eta_{p_1}=0\), increasing, become equal to the deviation from one more, or several more, of the planes \(\eta_j=0\), or until the point falls on one more, or several more, of the boundary planes \(\delta_k=0\).

For this purpose we put
\(\eta_1=\eta_2=\ldots=\eta_{p_1}=\eta\) and
\(\delta_1=\delta_2=\ldots=\delta_{p_2}=0\), and solve the \((s-p_1)+(m-p_2)\) equations with one unknown \(\eta\)

\[ \eta=b^{(p)}_{1j}\eta+\ldots+b^{(p)}_{p_1j}\eta+ [\eta_j(x_p)-b^{(p)}_{1j}\eta_1(x_p)-\ldots-b^{(p)}_{p_1j}\eta_{p_1}(x_p)] \quad (j=p_1+1,\ldots,s); \tag{5} \]

\[ 0=a^{(p)}_{1k}\eta+\ldots+a^{(p)}_{p_1k}\eta+ [\delta_k(x_p)-a^{(p)}_{1k}\eta_1(x_p)-\ldots-a^{(p)}_{p_1k}\eta_{p_1}(x_p)] \]

\[ (k=p_2+1,\ldots,m), \]

from which we find the least solution \(\eta=\eta^{(p+1)}\), greater than
\(\eta^{(p)}=\eta_1(x_p)\). In general it is attained by several equations from (5). For convenience of notation let these equations be the first \(t_1\) equations from the first part of system (5) and the first \(t_2\) equations from the second part of this system. Denote \(t_1+t_2=t\). Then for the new \((p+t)\)-th approximation \(x_{p+t}\) we shall have

\[ \eta_1(x_{p+t})=\ldots=\eta_{p_1+t_1}(x_{p+t})<\eta_j(x_{p+t}) \quad (j>p_1+t_1); \]

\[ \delta_1(x_{p+t})=\ldots=\delta_{p_2+t_2}(x_{p+t})=0,\quad \delta_k(x_{p+t})>0\quad (k>p_2+t_2). \]

We continue the process of moving upward the minimal deviations \(\eta_j\) and the vanishing \(\delta_k\) as long as this is possible, i.e., until not

* As pivot one may take any of the indicated coefficients different from zero; this may affect only the speed of the process.

there remain only those rows with minimal deviation or vanishing rows in which all coefficients of the remaining \(\xi_i\) are zero, or until no \(\xi_i\) remains at the top of the tableau. If all constant terms in the remaining rows with minimal and vanishing deviation are zero, then we continue the process from the point \(x_{p+t}\) in the same way as from the point \(x_p\). If, however, the constant term of at least one of these minimal or vanishing rows is different from zero, then it is impossible, moving from it and remaining in the boundary planes \(\delta_1=0,\ldots,\delta_{p_2+t_2}=0\), to increase all minimal deviations while preserving their equality to one another. We shall call the point \(x_{p+t}\) stationary.

1. Let \(x_q\) be a stationary point. For convenience of notation, suppose that the minimal deviations are \(\eta_1(x_q),\ldots,\eta_{q_1}(x_q)\), and the vanishing deviations are \(\delta_1(x_q),\ldots,\delta_{q_2}(x_q)\), where \(q_1+q_2=q\), and that it has been possible to transfer upward the first \(r_1\) of the minimal deviations and the first \(r_2\) of the vanishing ones. Denote \(r_1+r_2=r\). The tableau obtained then has the following form:

An edge of dimension \(n-r\) in the problem under consideration will mean a linear manifold satisfying \(r\) equations, which are obtained by setting equal to zero any \(r\) linearly independent ones among the minimal \(\eta_i\) and vanishing \(\delta_k\). The characteristic of an edge will mean the sum of the number of planes among the minimal and vanishing ones passing through the edge, plus the number of minimal planes separating the stationary point \(x_q\) from the edge, plus the number of vanishing planes which separate the edge from the domain \(\Omega\), if \(\eta_1(x_q)>0\), and do not separate the edge from \(\Omega\), if \(\eta_1(x_q)<0\).

The characteristic of the edge \(\eta_1=0,\ldots,\eta_{r_1}=0,\delta_1=0,\ldots,\delta_{r_2}=0\), formed by the minimal and vanishing planes that have appeared at the top (these planes are, obviously, linearly independent), is computed at once. This characteristic is equal to the number \(r\) plus the number of minimal and vanishing planes not transferred upward whose constant terms are zero, plus the number of minimal and vanishing planes not transferred upward whose constant terms have sign opposite to that of \(\eta_1(x_q)\).

If this characteristic is equal to \(q\), i.e. is maximal, so that among the minimal and vanishing planes not transferred upward there are no constant terms of the same sign as \(\eta_1(x_q)\), then we move from the stationary point \(x_q\) in the direction of increasing the minimal deviations to some other stationary point. For this we set \(\eta_1=\ldots=\eta_{r_1}=\eta\)

and \(\delta_1=\ldots=\delta_{r_2}=0\), and we solve the equations

\[ \eta=b_{1j}^{(q)}\eta+\ldots+b_{r_1j}^{(q)}\eta+ \left[\eta_j(x_q)-b_{1j}^{(q)}\eta_1(x_q)-\ldots-b_{r_1j}^{(q)}\eta_{r_1}(x_q)\right] \quad (j=q_1+1,\ldots,s); \]

\[ 0=a_{1k}^{(q)}\eta+\ldots+a_{r_1k}^{(q)}\eta+ \left[\delta_k(x_q)-a_{1k}^{(q)}\eta_1(x_q)-\ldots-a_{r_1k}^{(q)}\eta_{r_1}(x_q)\right] \quad (k=q_2+1,\ldots,m), \]

from which, as before in the steps prior to obtaining a stationary point, we find the least solution \(\eta=\eta^{(q+1)}\) greater than \(\eta^{(q)}=\eta_1(x_q)\).

If, however, this characteristic has turned out to be less than \(q\), then we compute the characteristics of the edges formed by any \(r-1\) planes among the minimal and annihilating ones that have appeared at the top, and by any one of such planes not appearing at the top but whose constant term is nonzero. Taking the first, for example, of such rows, we perform one step of Jordan elimination with a pivot element from the coefficients of this row and, as shown above, check whether the characteristic of the edge formed by \(r\) minimal and annihilating planes already appearing at the top of the table is equal to \(q\). As in \({}^{(4)}\), this single step of Jordan elimination must be carried out not on the entire table, but only on the free terms of the minimal and annihilating rows (it is sufficient to determine only their signs). If the characteristic of the edge under consideration has turned out to be less than \(q\), then we make a new step of Jordan elimination, taking as pivot some other coefficient of this row, and continue the process until we find an edge with characteristic equal to \(q\) (formed with the aid of this row (plane) or another analogous one), or until we establish that all \((n-r)\)-dimensional edges formed from our \(q\) planes have characteristic less than \(q\). In the first case we move from this edge (or to this edge) with the maximal characteristic as indicated above. In the second case one can show, as in \({}^{(5)}\), that the point \(x_q\) is optimal, and the process is finished. In any event, after a finite number of steps we shall necessarily arrive at the optimal point.

1. Remark. In the case where we do not have at our disposal an “admissible” point \(x'(\xi'_1,\ldots,\xi'_n)\in\Omega\), in order to find it one must first solve the system of inequalities (2), for example by algorithm \({}^{(4)}\). However, the algorithm of the present article may also be applied: for this we take an arbitrary point \(x'(\xi'_1,\ldots,\xi'_n)\) and substitute it into (2). If all \(\delta_k(x')\) are nonnegative, then the point \(x'(\xi'_1,\ldots,\xi'_n)\) is admissible. If, among the \(\delta_k(x')\), there are negative ones, then we apply our algorithm, with the role of the planes (1) played by those planes \(\delta_k(x)=0\) for which \(\delta_k(x')<0\), and the role of the inequalities (2) by the remaining inequalities.

Kiev Technological Institute
of the Food Industry

Received
12 III 1961

REFERENCES

1. S. I. Zukhovitskii, DAN, 133, No. 1 (1960).
2. L. V. Kantorovich, Economic Calculation of the Best Use of Resources, Moscow, 1959.
3. E. Stiefel, Numer. Math., 2 (1960).
4. S. I. Zukhovitskii, DAN, 139, No. 3 (1961).
5. S. I. Zukhovitskii, Matem. sbornik, 33 (75), issue 2 (1953).