CYBERNETICS AND CONTROL THEORY

B. S. VERKHOVSKII

ON A MULTI-INDEX TRANSPORTATION PROBLEM WITH AXIAL SUMS

(Presented by Academician A. I. Berg on 6 June 1963)

We consider the problem of minimizing the linear form

\[ \sum_{i_1,\ldots,i_s} P_{i_1,\ldots,i_s} x_{i_1,\ldots,i_s} \tag{1} \]

under the conditions \(x_{i_1\ldots i_s} \geqslant 0\) and

\[ \sum_{i_2,\ldots,i_s} x_{i_1\ldots i_s}=a_{i_1}^{(1)},\quad \sum_{i_1,\ldots,i_{s-2},\,i_s} x_{i_1\ldots i_s}=a_{i_{s-1}}^{(s-1)},\quad \sum_{i_1,\ldots,i_{s-1}} x_{i_1\ldots i_s}=a_{i_s}^{(s)}, \tag{2} \]

where, for all indicated \(i_k\), summation is carried out from \(1\) to \(n_k\), \(i_l=1,\ldots,n_l;\ l=1,\ldots,s;\ 0 \leqslant a_{i_l}^{(l)} < \infty\). We shall call such a problem a problem with axial sums, or a problem \(T_{s-1}(s)\). Multi-stage transportation problems, in particular, reduce to problems \(T_{s-1}(s)\).

Theorem 1. For a solution of the problem \(T_{s-1}(s)\) to exist, it is necessary and sufficient that the consistency conditions hold:

\[ \sum_{i_{l_1}=1}^{n_{l_1}} a_{i_{l_1}}^{(l_1)} = \sum_{i_{l_2}=1}^{n_{l_2}} a_{i_{l_2}}^{(l_2)} \quad \text{for all } \quad 1 \leqslant l_1 < l_2 \leqslant s. \tag{3} \]

Necessity is obvious, since

\[ \sum_{i_1}\left(\sum_{i_2,\ldots,i_s} x_{i_1\ldots i_s}\right)=\cdots \]

\[ \cdots= \sum_{i_s}\left(\sum_{i_1,\ldots,i_{s-1}} x_{i_1\ldots i_s}\right). \]

Sufficiency. By direct substitution it is easy to verify that

\[ x_{i_1\ldots i_s}=T^{1-s}\prod_{l=1}^{s} a_{i_l}^{(l)} \]

satisfy all conditions (3), where

\[ T=\sum_{i_l=1}^{n_l} a_{i_l}^{(l)}. \]

Consider the conditions

\[ \sum_{i_2,\ldots,i_s} x_{i_1\ldots i_s}=a_{i_1}^{(1)},\ldots, \sum_{i_1,\ldots,i_{s-2},\,i_s} x_{i_1\ldots i_s}=a_{i_{s-1}}^{(s-1)}. \tag{4} \]

Since

\[ 0 \leqslant x_{i_1\ldots i_s} \leqslant \min_{1\leqslant l\leqslant s} a_{i_l}^{(l)} < \infty, \]

the conditions (4) generate, in the \(\prod_{l=1}^{s} n_l\)-dimensional space, a bounded convex polyhedron \(G\). Denote by \(\xi^{(\sigma)}\) the extreme points of \(G\), \(\sigma=1,\ldots,h\), where \(h\) is the number of all vertices of the polyhedron \(G\). Then, if \((x_{11\ldots1},\ldots,x_{n_1n_2\ldots n_s})\in G\), then

\[ x_{i_1\ldots i_s}=\sum_{\sigma=1}^{h}\xi_{i_1\ldots i_s}^{(\sigma)}\lambda_\sigma. \tag{5} \]

Here

\[ \sum_{\sigma=1}^{h}\lambda_\sigma=1,\quad \lambda_\sigma\geqslant 0. \tag{6} \]

Substituting (5) into (1) and into the \(s\)-th group of conditions (2), we obtain the following problem:

Find the minimum

\[ \left(\sum_{\sigma=1}^{h}\gamma^{(\sigma)}\lambda_{\sigma}\right) \tag{7} \]

subject to

\[ \sum_{\sigma=1}^{h} g_{i_s}^{(\sigma)}\lambda_{\sigma}=a_{i_s}^{(s)} \tag{8} \]

and (6). Here

\[ \gamma^{(\sigma)}\equiv \sum_{i_1,\ldots,i_s} p_{i_1\ldots i_s}\xi_{i_1\ldots i_s}^{(\sigma)},\qquad g_{i_s}^{(\sigma)}\equiv \sum_{i_1,\ldots,i_{s-1}} \xi_{i_1\ldots i_s}^{(\sigma)}. \tag{9} \]

Theorem 2. Conditions (6) follow from Theorem 1 and conditions (8).

Proof. Summing (8) over all values of \(i_s\), we obtain

\[ \sum_{i_s}a_{i_s}^{(s)} = \sum_{i_s,\sigma} g_{i_s}^{(\sigma)}\lambda_{\sigma} = \sum_{\sigma}\lambda_{\sigma}\sum_{i_s}g_{i_s}^{(\sigma)} = T\sum_{\sigma}\lambda_{\sigma}. \]

Since \(\sum_{i_s}a_{i_s}^{(s)}=T\), it follows that \(\sum_{\sigma}\lambda_{\sigma}=1\). The theorem is proved.

Algorithm for finding a basic feasible solution of the problem \(T_{s-1}(s)\). Choose

\[ x_{1\ldots 1}=\min_{1\le l\le s} a_1^{(l)}. \]

Find \(\bar a_1^{(l)}=a_1^{(l)}-x_{1\ldots 1}\). Note that at least one of the \(\bar a_1^{(l)}\) becomes zero. For definiteness, suppose that \(\bar a_1^{(1)}=0\). We proceed to finding

\[ x_{21\ldots 1}=\min\left(a_2^{(1)},\bar a_2^{(2)},\ldots,\bar a_1^{(s)}\right). \]

In general, suppose that

\[ x_{\tau_1\ldots \tau_s} = \min_{1\le l\le s}\left(\widetilde a_{\tau_l}^{(l)}\right) = \widetilde a_{\tau_{l_*}}^{(l_*)}. \]

Here \(\widetilde a_{\tau_l}^{(l)}\) denotes the current values. We proceed to finding

\[ x_{\omega_1\ldots \omega_s} = \min_{1\le l\le s}\left(\widetilde a_{\omega_l}^{(l)}\right), \]

where

\[ \omega_k= \begin{cases} \tau_k, & \text{if } k\ne l_*,\\ \tau_k+1, & \text{if } k=l_*; \end{cases} \]

\[ \widetilde a_{\omega_k}^{(k)}= \begin{cases} \widetilde a_{\tau_k}^{(k)}-x_{\tau_1\ldots \tau_s}, & \text{if } k\ne l_*,\\ a_{\omega_k}^{(k)}, & \text{if } k=l_*. \end{cases} \]

The process ends when \(\tau_k=n_k\) for all \(k=1,\ldots,s\). From the algorithm for finding a basic feasible solution, two theorems follow:

Theorem 3. If all \(a_{i_l}^{(l)}\) are integers, then the problem \(T_{s-1}(s)\) has at least one integer basic feasible solution.

Remark. Unfortunately, an optimal integer solution does not always exist.

Theorem 4. A basic feasible solution of the problem \(T_{s-1}(s)\) contains no more than

\[ \sum_{l=1}^{s} n_l-s+1 \]

nonzero components.

It can be shown that, when solving problem (7)—(8), in order to form the initial \(n_s\) columns \(g^{(1)},\ldots,g^{(n_s)}\), one may use not only the extreme points of \(G\), but also interior points.

Choose \(n_s\) points of \(G\):

\[ x_{i_1\ldots i_s}^{(j)} = \begin{cases} T^{2-s}\displaystyle\prod_{l=1}^{s-1} a_{i_l}^{(l)}, & \text{if } j=i_s,\\ 0, & \text{if } j\ne i_s. \end{cases} \]

Then

\[ g_{i_s}^{(j)}= \begin{cases} T, & \text{if } j=i_s,\\ 0, & \text{if } j\ne i_s. \end{cases} \tag{10} \]

Substituting (10) into (8), we obtain \(\lambda_{i_s}=\dfrac{a_{i_s}^{(s)}}{T}\),

\[ \gamma^{(j)}= \sum_{i_1,\ldots,i_s} p_{i_1\ldots i_s}x_{i_1\ldots i_s}^{(j)} = T^{2-s} \sum_{i_1,\ldots,i_{s-1}} p_{i_1\ldots i_{s-1}j} \prod_{l=1}^{s-1}a_{i_l}^{(l)}. \tag{11} \]

In view of (10), the matrix \(B\) of the initial \(n_s\) vectors \(g^{(1)},\ldots,g^{(n_s)}\) has the structure \(B=T\cdot E\), where \(E\) is the identity matrix of order \(n_s\); hence the vector of estimates \(\bar{\pi}=(\pi_1,\ldots,\pi_{n_s})\) is computed as follows:

\[ \pi=\gamma_B B^{-1}=\gamma_B T^{-1}E,\qquad \text{where } \gamma_B=(\gamma^{(1)},\ldots,\gamma^{(n_s)}). \]

In view of (11),

\[ \pi_j=T^{1-s}\left( \sum_{i_1,\ldots,i_{s-1}} p_{i_1\ldots i_{s-1}j} \prod_{l=1}^{s-1}a_{i_l}^{(l)} \right). \]

It follows from the duality theorem that the solution of problem (7)—(8) is optimal if the vector of estimates \(\bar{\pi}\) satisfies the inequalities

\[ \gamma^{(\sigma)}\ge \bar{\pi}\,g^{(\sigma)}. \tag{12} \]

In expanded form, (12) is written as follows:

\[ \sum_{i_1,\ldots,i_s} \left(p_{i_1\ldots i_s}-\pi_{i_s}\right)\xi_{i_1\ldots i_s}^{(\sigma)} \ge 0,\qquad \sigma=1,\ldots,h. \tag{13} \]

It is easy to see that, in order for (13) to hold, it is necessary and sufficient that

\[ \min \sum_{i_1,\ldots,i_s} \left(p_{i_1\ldots i_s}-\pi_{i_s}\right)\xi_{i_1\ldots i_s}^{(\sigma)} \ge 0,\qquad \bar{\xi}^{(\sigma)}\in G. \tag{14} \]

Consider the following problem:

Find

\[ \min\left[ \sum_{i_1,\ldots,i_{s-1}} q_{i_1\ldots i_{s-1}}\eta_{i_1\ldots i_{s-1}}^{(\sigma)} \right] \tag{15} \]

subject to the conditions

\[ \eta_{i_1\ldots i_{s-1}}^{(\sigma)}\ge 0,\qquad \sum_{i_2,\ldots,i_{s-1}} \eta_{i_1\ldots i_{s-1}}^{(\sigma)}=a_{i_1}^{(1)},\ldots,\qquad \sum_{i_1,\ldots,i_{s-2}} \eta_{i_1\ldots i_{s-1}}^{(\sigma)}=a_{i_{s-1}}^{(s-1)}. \tag{16} \]

Let

\[ r\in R/\min_{1\le i_s\le n_s}(P_{i_1\ldots i_s}-\pi_{i_s}) = P_{i_1\ldots i_{s-1}r}-\pi_r. \]

It is clear that \(R\) is, generally speaking, different for different sets of indices \(i_1,\ldots,i_{s-1}\). Denote

\[ r^*=\min_{r\in R(i_1,\ldots,i_{s-1})} r. \]

Theorem 5. Problem (15)—(16) is equivalent to problem (14) if

\[ q_{i_1\ldots i_{s-1}}=p_{i_1\ldots i_{s-1}r^*}-\pi_{r^*}, \]

and, moreover,

\[ \xi_{i_1\ldots i_s}^{(\sigma_0)}= \begin{cases} \eta_{i_1\ldots i_{s-1}}^{(\sigma_0)}, & \text{if } i_s=r^*,\\ 0, & \text{if } i_s\ne r^*, \end{cases} \tag{17} \]

where \(\eta^{(\sigma_0)}\) is an optimal solution of problem (15)—(16).

For the proof, see \((^2)\).

Thus, the solution of problem \(T_{s-1}(s)\) has been reduced to the solution of problem \(T_{s-2}(s-1)\) (see (1), (2), (15), (16)). This procedure can be continued until we arrive at the solution of problem \(T_1(2)\), i.e., the classical transportation problem. The solution \(T_1(2)\) can be found by the same method as indicated for the general case, but any other methods may also be applied.

other algorithms for solving the classical transportation problem. In particular, if one of the numbers \(n_1\) and \(n_2\) is significantly larger than the other, it is advisable to use the algorithm described above \((^1)\).

Let us return to solving problem (15), (16). If, as a result of the solution, it turns out that

\[ \min \left[ \sum_{i_1,\ldots,i_{s-1}} q_{i_1\ldots i_{s-1}}-\eta_{i_1\ldots i_{s-1}}^{(\sigma_0)} \right] < 0, \]

then by (17) we find all \(\xi_{i_1\ldots i_s}^{(\sigma_0)}\), and then by (9) all \(g_{i_s}^{(\sigma_0)}\) and \(\gamma^{(\sigma_0)}\), where \(\bar g^{(\sigma_0)}\) is the column to be introduced into the basis. In order to determine which column should be removed from the basis, and then the new basic solution and the new estimate vector, the modified simplex method is used. Thus, at each iteration of problem \(T_{s-1}(s)\), one has to solve one problem \(T_{s-2}(s-1)\) and transform a matrix of size \(n_s \times (n_s+1)\).

In nondegenerate problems the basic solution contains exactly \(\sum_{l=1}^{s} n_l - s + 1\) positive components. From the algorithm for finding a basic solution it is clear that, in order for the problem to be nondegenerate, it is sufficient that for any \(1 \le k < l \le s\) there should not exist subsets \(I_k, I_l\) of the values of the indices \(i_k\) and \(i_l\) for which

\[ \sum_{i_k\in I_k} a_{i_k}^{(k)} = \sum_{i_l\in I_l} a_{i_l}^{(l)}. \tag{18} \]

The nonfulfillment of (18) can be ensured by the method of small perturbations, considering \(\hat a_{i_l}^{(l)}\) instead of \(a_{i_l}^{(l)}\), where

\[ \hat a_{i_l}^{(l)} = \begin{cases} a_{i_l}^{(l)} + R_l, & i_l < n_l,\\ a_{n_l}^{(l)} + T_l, & i_l = n_l, \end{cases} \qquad R_l = \begin{cases} \dfrac{R_{l+1}}{n_l}, & l=s-1,\ldots,2,\\ T_s=\varepsilon, & l=s,\\ 0, & l=1. \end{cases} \tag{19} \]

All \(\hat a_{i_l}^{(l)}\) satisfy the compatibility conditions (3), whence

\[ (n_l-1)R_l + T_l = (n_k-1)R_k + T_k \quad \text{for all } 1 \le k < l \le s. \tag{20} \]

From (19) it follows that

\[ (n_k-1)R_k < R_l \quad \text{for all } k<l. \tag{21} \]

From (20) and (21) it is easy to obtain that \(T_k > T_l + (n_l-2)R_l\) for all \(k<l\). It can be shown that for arbitrary \(I_k\) and \(I_l\)

\[ \sum_{i_l\in I_l} \hat a_{i_l}^{(l)} \ne \sum_{i_k\in I_k} \hat a_{i_k}^{(k)}, \]

if \(\varepsilon < \dfrac{\delta}{n_s}\), where

\[ \delta = \min_{I_k,I_l} \left| \sum_{i_l\in I_l} a_{i_l}^{(l)} - \sum_{i_k\in I_k} a_{i_k}^{(k)} \right| >0. \]

The author expresses gratitude to D. B. Yudin and E. G. Golshtein for valuable comments.

REFERENCES

\(^1\) S. Williams, J. Soc. Ind. and Appl. Math., 10, No. 1 (1962).
\(^2\) B. S. Verkhovsky, DAN, 151, No. 3, 515 (1963).