Abstract Generated abstract
This paper addresses linear programming problems in which special algorithms are available when all constraint vectors belong to a set permitting simplified solution of associated linear systems, but only part of the vectors satisfy this condition. It proposes a general device for applying such special methods when a comparatively small number of vectors are arbitrary, by replacing the systems arising in the successive improvement method with a bounded number of systems of the simplified admissible forms. The construction maintains auxiliary sets and expansion coefficients through basis changes, giving formulas for updating them after each pivot. The method requires storage of at most the square of the number of exceptional vectors and solves no more than five simplified systems per step, independently of the current number of exceptional basis vectors.
Full Text
UDC 512.251.26+519.3:330.115
MATHEMATICS
M. A. YAKOVLEVA
ON EXTENDING THE RANGE OF APPLICATION OF SPECIAL ALGORITHMS OF LINEAR PROGRAMMING
(Presented by Academician L. V. Kantorovich on 3 VI 1967)
We shall consider a linear programming problem in the following formulation. Vectors \(A_s\) \((s = 1, 2, \ldots, N)\) and a vector \(P\) from the Euclidean space \(R^n\) are given, as well as real numbers \(c_s\) \((s = 1,2,\ldots,N)\). It is required to determine such nonnegative values of the variables \(x_s\) \((s = 1, 2, \ldots, N)\) that
\[ \sum_{s=1}^{N} x_s A_s = P \]
and the quantity
\[ \sum_{s=1}^{N} c_s x_s \]
attains its minimum. In addition to general methods for solving the stated problem, a number of special methods have been developed which assume that the family of vectors \(A_s\) satisfies certain conditions. Some of these methods are constructed according to the following scheme. In the space \(R^n\) a set \(V\) is singled out in such a way that it is possible to construct certain simplified algorithms for solving systems of the form
\[ (B_k, y) = d_k, \qquad k = 1, 2, \ldots, n, \tag{1} \]
\[ \sum_{k=1}^{n} z_k B_k = D, \tag{2} \]
where \(D \in R^n\), \(d_k\) \((k = 1, 2, \ldots, n)\) are arbitrary real numbers, and \(B_k\) \((k = 1, 2, \ldots, n)\) form a linearly independent family of vectors from \(V\). If all the vectors \(A_s\) in the formulation of the linear programming problem belong to the set \(V\), then, in solving this problem by the method of successive improvement of an admissible vector \((^1,^2)\), one has to solve only systems of the form (1) and (2), and the existence of simplified algorithms makes it possible to increase substantially the volume of problems amenable to solution. For example, in order to construct algorithms for solving the general two-component problem \((^3,^4)\), \(V\) is taken to be the set of vectors in \(R^n\) in which no more than two components are different from zero. A number of special methods for solving the transportation problem and the problem with a block structure of the constraint matrix \((^5)\) also fit into this scheme.
In the present article we propose one general device which makes it possible to extend the range of application of special methods to the case where only part of the vectors \(A_s\) belongs to \(V\). In what follows we shall assume that \(A_s \in V\) for \(s = 1, 2, \ldots, M\), while the vectors \(A_{M+1}, A_{M+2}, \ldots, A_N\) are arbitrary. It is assumed here that the number \(N - M\) is comparatively small.
As is known, one step of the method of successive improvement of an admissible vector consists in the following. At the beginning of the step a set \(S \subset \{1, 2, \ldots, N\}\) is singled out such that the family \(\{A_s\}_{s \in S}\) forms a basis in \(R^n\). A vector \(y \in R^n\) is determined which satisfies the system
\[ (A_s, y) = c_s, \qquad s \in S. \tag{3} \]
Then one finds \(\sigma \in \{1, 2, \ldots, N\}\) for which \((A_\sigma, y) > c_\sigma\), and the coefficients of the expansion of the vector \(A_\sigma\) in the basis \(\{A_s\}_{s \in S}\), i.e., one solves the system
\[ \sum_{s \in S} g_s A_s = A_\sigma . \tag{4} \]
After this, according to certain rules whose application does not require laborious computations, one determines the number \(\tau \in S\) to be replaced by the number \(\sigma\). The set \(\bar S = (S \setminus \{\tau\}) \cup \{\sigma\}\) serves as the initial set for the next step. If the set \(S\) contains \(s > M\), then the existing simplified algorithms are not directly applicable to systems (3) and (4). The main idea of the device described below is that the solutions of systems (3) and (4) are obtained with the aid of solutions of certain systems of the form (1) and (2).
Let \(S = I \cup K\), where \(I \subset \{1, 2, \ldots, M\}\), \(K \subset \{M+1, M+2, \ldots, N\}\). Suppose, moreover, that some set \(J \subset \{1, 2, \ldots, M\}\) has been selected with a number of elements equal to the number of elements of the set \(K\), and such that the family \(\{A_s\}_{s \in I \cup J}\) forms a basis in \(R^n\). Since the family \(\{A_s\}_{s \in S}\) forms a basis in \(R^n\), for \(\mu \in J\)
\[ A_\mu = \sum_{\nu \in S} r_{\mu \nu} A_\nu . \]
We shall assume that, at the beginning of the step being described, some of the coefficients are known, namely, the coefficients \(r_{\mu \nu}\) are known for \(\mu \in J\), \(\nu \in K\). Under these assumptions the solution \(y\) of system (3) can be found in the following way. We find the vector \(\tilde y\) from the system
\[ (A_\mu, \tilde y) = \begin{cases} c_\mu & \text{for } \mu \in I,\\ 0 & \text{for } \mu \in J. \end{cases} \tag{5} \]
Then the desired vector \(y\) can be found from the system
\[ (A_\mu, y) = \begin{cases} c_\mu & \text{for } \mu \in I,\\ \displaystyle \sum_{\nu \in K} r_{\mu \nu}\,[c_\nu - (A_\nu, \tilde y)] & \text{for } \mu \in J. \end{cases} \tag{6} \]
Systems (5) and (6) are already systems of the form (1) and can be solved by the simplified algorithm.
After the number \(\sigma\) has been found, the solution of system (4) can be obtained with the aid of the solution of two systems of the form (2). For this we first find the numbers \(\tilde g_s\) from the system
\[ \sum_{\mu \in I \cup J} \tilde g_\mu A_\mu = A_\sigma . \tag{7} \]
Then, for \(\nu \in K\), the desired coefficients \(g_\nu\) can be found by the formulas
\[ g_\nu = \sum_{\mu \in J} r_{\mu \nu}\tilde g_\mu . \]
The remaining coefficients \(g_\nu\) (for \(\nu \in I\)) are found from the system
\[ \sum_{\nu \in I} g_\nu A_\nu + \sum_{\nu \in J} p_\nu A_\nu = A_\sigma - \sum_{\nu \in K} g_\nu A_\nu, \]
and in the solution of this system all \(p_\nu\) will turn out to be equal to zero.
As has already been said, in order to pass to the next step, one finds the number \(\tau\) in the set \(S\) and sets \(\bar S = (S - \{\tau\}) \cup \{\sigma\}\). In this case one obtains
the following partition of the set \(\bar S\) into the sets \(\bar I\) and \(\bar K\):
\[ \begin{array}{ll} \bar I=(I\setminus\{t\})\cup\{\sigma\}, & \bar K=K\setminus\{t\}, \qquad \text{if } \sigma \le M,\\[3pt] \bar I=(I\setminus\{t\}), & \bar K=(K\setminus\{t\})\cup\{\sigma\}, \qquad \text{if } \sigma > M. \end{array} \]
In order that the step described can be repeated, it is also necessary to specify a new set \(\bar J\) and the coefficients \(\bar r_{\mu\nu}\) \((\mu\in\bar J,\ \nu\in\bar K)\) in the expansions
\[ A_\mu=\sum_{\nu\in\bar S}\bar r_{\mu\nu}A_\nu,\qquad \mu\in\bar J. \tag{8} \]
As for the set \(\bar J\), it is required only that the family \(\{A_s\}_{s\in\bar I\cup\bar J}\) form a basis in \(R^n\). If \(\sigma>M\) and \(\tau\in\bar K\), then \(I=\bar I\), and one may put \(\bar J=J\). If \(\sigma>M\) and \(\tau\in I\), then as \(\bar J\) one may take the set \(J\cup\{\tau\}\). In the case \(\sigma\le M\) the number \(\sigma\) enters the set \(\bar I\), and some element \(a\) of the old set \(I\cup J\) must be removed. From the rule for forming the set \(\bar I\) it is clear that the required element \(a\) must belong to the set \(R\), where \(R=I\) if \(\tau\in K\), and \(R=J\cup\{t\}\) if \(\tau\in I\). In this case the requirement of linear independence of the family \(\{A_s\}_{s\in\bar I\bar J}\) is equivalent to the coefficient \(\bar g_\alpha\) in the expansion (7) being different from zero. As \(a\) one may take that number for which \(|\bar g_\alpha|=\max_{\mu\in R}(|\bar g_\mu|)\).
If the rule for choosing the number \(\tau\) is taken into account, then one can show that in this case \(\bar g_\alpha\ne0\). Thus, \(\bar J=R\) if \(\sigma>M\), and \(\bar J=R\setminus\{\alpha\}\) if \(\sigma\le M\).
The coefficients \(\bar r_{\mu\nu}\) in the expansions (8) can be found by the usual formulas for transforming coefficients when passing to a new basis, i.e.,
\[ \bar r_{\mu\nu}= \begin{cases} r_{\mu\nu}-\dfrac{g_\nu}{g_\tau}r_{\mu\tau}, & \text{for } \nu\in\bar K\setminus\{\sigma\},\\[8pt] \dfrac{r_{\mu\tau}}{g_\tau}, & \text{for } \nu=\sigma\ (\text{if } \sigma\in\bar K). \end{cases} \tag{9} \]
This determines the coefficients \(\bar r_{\mu\nu}\) for \(\nu\in\bar K,\ \mu\in\bar J\setminus\{\tau\}\). If \(\tau\in\bar J\), then one must also put
\[ \bar r_{\tau\nu}= \begin{cases} -\dfrac{g_\nu}{g_\tau}, & \text{for } \nu\in\bar K\setminus\{\sigma\},\\[8pt] \dfrac{1}{g_\tau}, & \text{for } \nu=\sigma. \end{cases} \]
The right-hand sides of formulas (9) contain the coefficients \(r_{\mu\tau}\). If \(\tau\in I\), then, before applying formulas (9), it is necessary to compute the coefficients \(r_{\mu\tau}\). For this one should solve the system
\[ (A_\mu,z)= \begin{cases} 0, & \text{for } s\in(I\setminus\{t\})\cup J,\\ -1, & \text{for } s=\tau, \end{cases} \tag{10} \]
which is a system of the form (1), and then put
\[ r_{\mu\tau}=\sum_{\nu\in K} r_{\mu\nu}(A_\nu,z). \]
In conclusion we note that the number of elements of the set \(K\) cannot exceed \(N-M\), and therefore the number of coefficients \(r_{\mu\nu}\) stored at each step is no more than \((N-M)^2\). Moreover, the number of systems of the form (1) or (2) solved at each step is no more than five (system (10) need be solved only when \(\tau\in I\)), i.e., it does not depend on the number of elements of the set \(K\).
Institute of Mathematics
Siberian Branch of the Academy of Sciences of the USSR
Received
25 V 1967
REFERENCES
- L. V. Kantorovich, Economic Calculation of the Best Use of Resources, Publishing House of the Academy of Sciences of the USSR, 1959.
- D. B. Yudin, E. G. Golshtein, Linear Programming, Moscow, 1963.
- M. K. Gavurin, G. P. Rubinshtein, S. S. Shur, Siberian Mathematical Journal, 3, No. 4, 481 (1962).
- M. A. Yakovleva, collection Optimal Planning, vol. 2, Novosibirsk, 1964, p. 23.
- R. A. Zvyagina, collection Optimal Planning, vol. 2, Novosibirsk, 1964, p. 50.