UDC 512.251.26+519.3:330.115

MATHEMATICS

V. A. EMELICHEV, V. I. KOMLIK

SOLUTION OF DISCRETE PROGRAMMING PROBLEMS BY THE METHOD OF CONSTRUCTING A SEQUENCE OF PLANS

(Presented by Academician L. V. Kantorovich, January 29, 1969)

Consider problem A of minimizing the functional

\[ F(X)=g_1(x_1)\omega g_2(x_2)\omega \ldots \omega g_m(x_m)\omega Q(x_1,x_2,\ldots,x_m) \]

subject to the constraints

\[ \sum_{i=1}^{m} a_i x_i \leq c; \tag{1} \]

\[ X=(x_1,x_2,\ldots,x_m)\in G, \tag{2} \]

\[ x_i\in \gamma_i=\{a_{i1},a_{i2},\ldots,a_{is_i}\},\quad i=1,\ldots,m, \tag{3} \]

where \(a_i, c, a_{ij}\) are positive integers; \(\omega\) is the operation of addition or multiplication; \(Q(X)\) is a function for which there exist functions \(t_i(x_i)\), \(i=1,\ldots,m\), such that

\[ t_1(x_1)\omega t_2(x_2)\omega \ldots \omega t_m(x_m)\leq Q(X) \]

for any plan \(X\) of problem A. The set \(G\) may be specified in various ways (by equations, inequalities, logical conditions, etc.). Denote the set of plans of problem A by \(M\), and the set of plans determined by constraints (1) and (3) by \(\overline{M}\).

In the present note we propose a method for solving problem A, consisting in the construction and analysis of a sequence of plans of problem \(\overline{\mathrm{A}}\) for minimizing the functional \(\overline{F}(X)=\overline{g}_1(x_1)\omega \overline{g}_2(x_2)\omega \ldots \omega \overline{g}_m(x_m)\) on the set \(\overline{M}\). Here \(\overline{g}_i(x_i)=g_i(x_i)\omega t_i(x_i)\), \(i=1,\ldots,m\).

Let \(f_h(z)\) be the optimal value of the functional of problem \(\overline{\mathrm{A}}\), in which the index \(m\) and the parameter \(c\) are replaced respectively by \(h\) and \(z\) \((^1)\). A plan \(X_0=(x_1^0,x_2^0,\ldots,x_m^0)\) of problem \(\overline{\mathrm{A}}\) will be called \(h\)-optimal \((1\leq h\leq m)\) and denoted by

\[ (*,*,\ldots,*,x_{h+1}^0,\ldots,x_m^0), \]

if

\[ \overline{F}(X_0)=\overline{g}_{h+1}(x_{h+1}^0)\omega \ldots \omega \overline{g}_m(x_m^0)\omega f_h\left(c-\sum_{i=h+1}^{m} a_i x_i^0\right). \]

In this case the set of plans of problem \(\overline{\mathrm{A}}\) such that \(x_i=x_i^0\), \(i=h+1,\ldots,m\), will be denoted by

\[ \overline{M}(*,*,\ldots,*,x_{h+1}^0,\ldots,x_m^0)=\overline{M}(X_0). \]

Directly from the definition of \(h\)-optimality of the plan \(X_0\) it follows that

Lemma 1. \(\displaystyle \overline{F}(X_0)=\min_{X\in \overline{M}(X_0)} \overline{F}(X).\)

We describe an algorithm \(\varphi\) for constructing a sequence of plans of problem A.

First step. Among the set \(W_1\) of all \((m-1)\)-optimal pla-

of problem \(\bar A\) we find such a plan

\[ X_1=(*,*,\ldots,*,x_m^1)=(x_1^1,x_2^1,\ldots,x_m^1), \]

such that

\[ \bar F(X_1)=\min_{X\in W_1}\bar F(X). \]

\(k\)-th step \((k=2,3,\ldots)\). We transform the set \(W_{k-1}\) into the set \(W_k\) according to the following rule. We leave unchanged all plans of the set \(W_{k-1}\), except for the plan

\[ X_{k-1}=(*,*,\ldots,*,x_p^{k-1},\ldots,x_m^{k-1}) =(x_1^{k-1},x_2^{k-1},\ldots,x_m^{k-1}), \]

which we replace by the system of all possible plans of the form

\[ (*,*,\ldots,*,x_{q-1},x_q^{k-1},\ldots,x_p^{k-1},\ldots,x_m^{k-1}), \]

where \(x_{q-1}\in Y_{q-1}\), \(x_{q-1}\ne x_{q-1}^{k-1}\), \(q=2,3,\ldots,p\), and

\[ \sum_{i=1}^{q-2}\max_{1\le k\le s_i} a_{ik}\ge c-\sum_{i=q}^{m}x_i^{k-1}-x_{q-1}. \]

Next we find such a plan \(X_k\) that

\[ \bar F(X_k)=\min_{X\in W_k}\bar F(X), \]

and pass to the next step.

Introduce the notation

\[ \bar M_k=\bigcup_{X\in W_k}\bar M(X). \]

Lemma 2. \(\bar M_1=\bar M,\ \bar M_k=\bar M_{k-1}\setminus X_{k-1},\ k=2,3,\ldots\).

From Lemmas 1 and 2 it follows that

Theorem 1. The algorithm constructs such a sequence of plans \(X_1,X_2,\ldots\) of problem \(\bar A\) that

\[ \bar F(X_k)=\min_{X\in \bar M\setminus\{X_1,X_2,\ldots,X_{k-1}\}}\bar F(X),\qquad k=1,2,\ldots \]

If, from the constructed sequence of plans \(X_1,X_2,\ldots\) of problem \(\bar A\), we remove the plans that do not belong to the set \(G\), then for the remaining sequence of plans \(X'_1,X'_2,\ldots\) of problem \(A\) the following holds.

Theorem 2. If there exists a number \(k\) such that

\[ F(X'_k)\ge \min\{F(X'_1),F(X'_2),\ldots,F(X'_{k-1})\}=F(X^*), \]

then \(X^*\) is an optimal plan of problem \(A\).

Theorem 2 specifies an algorithm \(\psi\) for solving problem \(A\). The desired algorithm \(\psi\) is described as follows: the \(k\)-th step consists in constructing, with the aid of algorithm \(\varphi\), the plan \(X_k\) and checking whether it belongs to the set \(G\). If not, we pass to the next step of algorithm \(\psi\). If yes, we check whether the condition of Theorem 2 is satisfied. If not, we pass to the next step. If yes, the process terminates and \(X^*\) is an optimal plan.

The method presented is applicable to solving facility location problems \((^{2-4})\), integer programming problems \((^5,\ ^6)\), reliability problems for a complex system \((^7)\), and the traveling-salesman problem.

Belorussian State University
named after V. I. Lenin
Minsk

Received
7 I 1969

REFERENCES

1. R. Bellman, Dynamic Programming, IL, 1960.
2. V. A. Emelichev, V. I. Komlik, Dokl. AN BSSR, 10, No. 10 (1966).
3. V. A. Emelichev, V. I. Komlik, Dokl. AN BSSR, 12, No. 10 (1968).
4. V. I. Komlik, Izv. AN BSSR, Ser. Phys.-Math. Sci., No. 4 (1967).
5. V. I. Komlik, V. A. Emelichev, Dokl. AN BSSR, 11, No. 12 (1967).
6. V. I. Komlik, V. A. Emelichev, Izv. AN BSSR, Ser. Phys.-Math. Sci., No. 4 (1968).
7. V. A. Emelichev, V. I. Komlik, Izv. AN BSSR, Ser. Phys.-Math. Sci., No. 5 (1968).