ABSTRACTS*

CERTAIN PROBLEMS IN STOCHASTIC PROGRAMMING ARISING IN CONVERSATIONAL PLANNING SYSTEMS IN THE PRESENCE OF INCOMPLETE INFORMATION V. M. Gtushkov and G. B. Oleyarsh

U D C 007:65.012.t22

The conversational planning system DISPLAN, developed at the tnstimte of Cybernetics of the Ukrainian Academy of Sciences, is intended for multicriteriat optimization of national economy planning in a conversational mode. The system is based on the model of input-output accounting (a static linear Leontief model), with additional constraints on the resources. The system allows the user to obtain on-line plan indices of production volume in an expanded nomenclature, by varying the technological norms of outlays. The user can make such changes in the conversational mode until a satisfactory balance is obtained in the resources of the solufiqn. Essentially the system DISPLAN solves the problem of on-line resources balancing (taking into account direct and indirect costs) on the basis of the proposals obtained from the user for changes in the technoIo~cM norms. On the mathematical level the system provides solutions of systems of linear algebraic equations of high dimensionality (up to 1200 variables) and to verify the degree to which the solution obtained satisfies the constraints on the resources. It is assumed in this that all of the system parameters are deterministic quantities. However in many planning problems encountered in practice such an assumption is by far not always justified. The decision about the volume of production is taken at the start of the planning period when, as a rule, the values of the technological .norms are not known exactly, due to errors arising in the determination of these values. In the general case the assigned production plan is not the solution of a system of Leontief input-output balance equations after the true values of the norms become known. To achieve balancing of the adopted plan it is necessary to carry out corrections, which leads to additional outlays. What is understood in such a case as an optimal plan depends on the concrete formulation of the problem. By way of example it is possible to present two problems in the construction of optimal plans, in the first of which the plan is found by the criterion of minimum mathematical expectation of the outlay of a critical resource (in particular, labor resources), in the second by the c~terion of minimum mathematical expectation of correctional outlays. On the mathematical level these problems are two-stage stochastic programming problems, and the method of stochastic quasigradients is used for their solution. Formulations of the problems, algorithms for their solution, questions of using these algorithms in the construction of conversational planning systems, and the possibilities of programming the proposed algorithms are discussed in an article which will be published in the first issue of Kibernetika in 1977.

DYNAMIC MODEL OF LONG-TERM PLANNING OF CIVIL AVIATION" AIRCRAFT PARK N. Z. Shor, G. N. Yun, S. K. Andrusenko, and V. N. Kas'yanenko

The problem is considered of determining the ne~ds of civil aviation (CA) in passenger aircraft under certain assumptions with regard to the delivery of aircraft for CA, the capacity of the airports, the interaction of routes, and the seasonal character of demand for air transport. The problem is formulated in the following way. A planning period T is given, in each of whose subperiods T E [1, T] the volume of air transportation djt on each of the airlines jE{1 .... , nt} under consideration , is known, where the dynamics of modification of the airline network is considered to be known in advance. At the start of the planning period there exists a certain park of aircraft all , which in each subperiod can be increased by aircraft whose production is planned by industry. The annual operating costs cijt connected with traffic and capital invest-

*The complete text of these articles is available at the Editorial Office. Translated from Kibernetika, No. 5, pp. 149-151, September-October, 1976. I This material is protected by copyright registered in the name of Plenum Publishing Corporation, 227 West 17th Street, New York, N.Y. IO011. No par~ of this publication may be reproduced, stored in a retrieval system, or transmitted, in any form or by any means, electronic, mechanical, photocopying, microfilming, recording or otherwise, without written permission of the publisher. A copy of this article is available from the publisher for $ 7.50.

811

It is necessary to enlarge the park by new aircraft Yit

ment cit , connected with production of aircraft, are known.

and to allocate the entire park { 1, ..., m} over the airlines in such a way as to carry out the tong-term plan for air transport in the m o s t efficient way (with minimal reduced cost c). The mathematical model of the formulated problem is written in terms of a linear program. Tlnt

m

C i jr

m

C it

Minimize

\

e = ~ [ Z Z(-]--~txijt+~--f--~-~tgu) under the constraints t=17=1 ~=~ -- "

~=l . . . . ~pijtXijt t~l

~ djt,

nt

j = l,nt'-'~, t = ~,T, ~

t

Z xijt
T=t

xm~0,

y.~0,

I=L~--v i =l,--A, t=l,--~,

where xijt is the number of aircraft of the i-th type over the j-th airline in the t-th subperiod, t~~ is the service life (technical resource) o f an aircraft o f i-th type, P~it is the annual productivity o f an aircraft of i-th type on the j-th airline in the t-th subperiod, E is the norm for investment efficiency, O~t

1, if 0, if

The problem is o f high dimensionality (m • n x T =

t - - ~ < t ? I, t--x>t~

1.

20 • 1400 • 7). A stagewise approach is therefore proposed

for the solution, based on the ideas of block programming. The variables of individual blocks are coupled by means o f an algorithm of generalized gradient descent, for which the corresponding programs have been written in FORTRAN for the BESM-6 computer.

OBTAINING ADDITIVE NUMERICAL DETECTING SYSTEMS USING VARIABLE PRECISION ARITHMETIC SIMULATED ON A GENERAL-PURPOSE COMPUTER UDC 511 ;518;519.1;51:621.391;518.74

V. I. Uberman and V. I. Shleinikov The set of integers studied:

A~(x)={a~}~, l~<~al(.~ .~%~
the sums ~ e~ai eiEl0 ' 11,

ei)0

are all distinct.

A definition is introduced for detecting system (D-

system), whose indications A k, k = 1, 2, ..., are one-time additive detecting systems (IADC). Extensive and important fields of application o f D-systems are given in discrete mathematics and cybernetics. The article discusses the function of natural density of 1ADC: f ( x ) = r ~ a x ~ . The latest known result in this direction is the M o s e r - E r d o s bound: tAk(x)~

f ( x ) ~ log xtlog2+ log log x/21og2+ c "(1). More than 20 years ago P. Erd6s assumed

Ihat the second term could be

excluded without violating the bound, but the application of much effort in this direction by many investigators has not produced results. This question is of major importance for the theory of D-systems and their application. The density characteristic is investigated o f the family ~co of sequences, given by the recurrent expressions a ( k + 1, 1 ) = a ( k , a(k+l,i)=a(k+l, a(1, I ) = a ( 2 ,

Ni(V-~k)), k : l , 2 . . . . . 1)+a(k,

i--I),

]

2~i~
(l)

I) = 1,

where a (k, 0 = at E Ak and Ni (r) is the nearest integer to r. In 1968 Conway and Gay assumed that all

AkC ~cG are 1ADC.

This hypothesis was demonstrated by the first o f the present authors in 1973. The nature o f ~co is investigated and it is shown that all

A~C~cG have a greatest density among the known

1ADC o f corresponding cardinality. A general scheme is constructed for estimating the density f(x) in triangular tables o f type (1) with generalization o f the equality for a(k + 1, 1), based on the analysis of the solution of an almost linear finite-difference equation, which in the case of ~cQ has the form

812

a(k v 1) = 2a (k~ -- 1,1), I~ = (i2 + 0/2 + 2, a(k~ + j, l) __-2a(tq + i - - t,1) -- a(k~ - - +1--2,1), ]~l,i:

(2)

~=1,2 ....

Using the proposed method ~t is shown that f(x)~
for all A~E 91co. A "greatest" family ~a- of

sequences is obtained o f a form analogous to (1), in which dot

a(k+ 1,1)=a(k,g(k)),g(k)~max{i+

and f ( x ) ~ l o g x / l o g 2 + ~ ( x ) + O ( 1 ) ,

where ~0 is monotonically increasing, positive, and unbounded.

already does not consist o f 1ADC.

(3)

~= 1,2,...},g(1)=1

l : 2 i-~ + ~ < k ,

However

~-

It is shown that in the last analysis the presence of ~ x ) in the bound for

f(x) depends on the behavior of the zeros of the function

/:r~(Z)=Z ~ - z ~-~. . . . --1 as n -+ oo.

The problems arising in the computer investigation of D-systems are expounded, the most important o f which is the need to manipulate unboundedly increasing integer sequences. Reliable results can be obtained for. sufficiently long sequences and their terms. The manipulation o f the latter is only possible with an arbitrary-precision (AP) arithmetic package, while the recursively related AP numbers are effectively obtained by the programmed organization of virtual memory. A survey is given of the hardware and software for carrying out AP computation by computer. An AP arithmetic package is described, part o f the symbolic processing program system "Sputnik." On the basis of the latter a complex has been developed, "Sputnik"-ALGOL, allowing the work to be organized with numbers of arbitrary length and range in ALGOL-60. An ALGOL program is presented for the generation of ~ca, ~ i - ,

with results of experiments on estimating

their densities, illustrating the possibilities of AP arithmetic; its utilization is described. Families o f sequences were generated by two algorithms on the basis o f relations o f the type (1) and (2)-(3), which are not equivalent from the computational point of view. The density characteristics of %0 were obtained as follows: for k ~ 28, Y~3
For this family 2"2m~/a (2017,1) = 4. 25305 17328 37168 32684.2"a~

(2017. 2017)=2. i265258664 18584 16330. The analogous

characteristics of the family 9~-: 2~659/a(2060,I)= 10. 44050 63767 12156 37755, 2~~

(2060, 2060~= 5. 21961 49368 24368 45860.

The length of sequence obtained was 2060 terms, where the numbers contained 621 decimal digits. An experimental variant o f "Sputnik"-ALGOL, implemented on M-222, was used. The results obtained agree fully with the theoretical estimates and substantially complement the latter, allowing the constants that appear in them to be determined.

818