Том 295, № Suppl 1 (2016)

An efficient method is introduced for solving the problems of optimal control of thermal processes with phase transitions. The following statement is formulated and proved: the time of computing the components of the gradient of the objective function by means of the proposed method does not exceed the time of computing two values of the function.

A method for solving the following inverse linear programming (LP) problem is proposed. For a given LP problem and one of its feasible vectors, it is required to adjust the objective function vector as little as possible so that the given vector becomes optimal. The closeness of vectors is estimated by means of the Euclidean vector norm. The inverse LP problem is reduced to a problem of unconstrained minimization for a convex piecewise quadratic function. This minimization problem is solved by means of the generalized Newton method.

A problem of visiting megalopolises with a fixed number of “entrances” and precedence relations defined in a special way is studied. The problem is a natural generalization of the classical traveling salesman problem. For finding an optimal solution, we give a dynamic programming scheme, which is equivalent to a method of finding a shortest path in an appropriate acyclic oriented weighted graph. We justify conditions under which the complexity of the algorithm depends on the number of megalopolises polynomially, in particular, linearly.

We consider the m-Cycle Cover Problem of covering a complete undirected graph by m vertex-nonadjacent cycles of extremal total edge weight. The so-called TSP approach to the construction of an approximation algorithm for this problem with the use of a solution of the traveling salesman problem (TSP) is presented. Modifications of the algorithm for the Euclidean Max m-Cycle Cover Problem with deterministic instances (edge weights) in a multidimensional Euclidean space and the Random Min m-Cycle Cover Problem with random instances UNI(0,1) are analyzed. It is shown that both algorithms have time complexity O(n³) and are asymptotically optimal for the number of covering cycles m = o(n) and \(m \leqslant \frac{{n^{1/3} }} {{\ln n}}\), respectively.

A two-step problem of minimizing average costs of hedging a European call option is studied. The hedging is implemented by buying and selling underlying assets. It is assumed that the durations of asset purchase and sale operations at the market are random and exponentially distributed. The problem is solved by the dynamic programming method. An expression for the expected value of the future loss function at the final step is obtained. A numerical algorithm for finding an optimal strategy at the first step is proposed. An example of using the algorithm is given.

A distance-regular graph Γ with intersection array {204, 175, 48, 1; 1, 12, 175, 204} is an AT4-graph, and the antipodal quotient \(\overline \Gamma \) has parameters (800, 204, 28, 60). Automorphisms of these graphs are found. In particular, neither of the two graphs is arc-transitive.

We study the minimum weight k-size cycle cover problem (Min-k-SCCP), which consists in partitioning a complete weighted digraph into k vertex-disjoint cycles of minimum total weight. This problem is a generalization of the known traveling salesman problem and a special case of the classical vehicle routing problem. It is known that Min-k-SCCP is strongly NP-hard in the general case and preserves its intractability even in the geometric statement. For Euclidean Min-k-SCCP in ℝ^d with k = O(log n), we construct a polynomialtime approximation scheme (PTAS), which generalizes the approach proposed earlier for planar Min-2-SCCP. For each fixed c > 1 the scheme finds a (1 + 1/c)-approximate solution in time \(O\left( {{n^{O\left( d \right)}}{{\left( {\log n} \right)}^{{{\left( {O\left( {\sqrt {dc} } \right)} \right)}^{^{d - 1}}}}}} \right)\).

A problem of guaranteed closed-loop control under incomplete information is considered for a linear stochastic differential equation (SDE) from the viewpoint of the method of open-loop control packages worked out earlier for the guidance of a linear control system of ordinary differential equations (ODEs) to a convex target set. The problem consists in designing a deterministic open-loop control providing (irrespective of a realized initial state from a given finite set) prescribed properties of the solution (being a random process) at a terminal point in time. It is assumed that a linear signal on some number of realizations is observed. By the equations of the method of moments, the problem for the SDE is reduced to an equivalent problem for systems of ODEs describing the mathematical expectation and covariance matrix of the original process. Solvability conditions for the problems in question are written.

We prove that there are only finitely many symmetrical extensions of a locally finite tree by a finite graph. Moreover, we prove that there are only finitely many pairwise nonequivalent realizations of symmetrical extensions of a locally finite tree by a finite graph.

We find finite almost simple groups with prime graphs all of whose connected components are cliques, i.e., complete graphs. The proof is based on the following fact, which was obtained by the authors and is of independent interest: the prime graph of a finite simple nonabelian group contains two nonadjacent odd vertices that do not divide the order of the outer automorphism group of this group.