Some aspects of nonlinear synthesis of communications networks (Q1090632)

The following optimization problem is considered: Find \(x=\{x_ i\}_{i\in A}\), \(y=\{x_ j\}_{j\in \Gamma}\) and \(Y^ k=\{y^ k_ j\}_{j\in \Gamma}\), \(k=1,...,\ell\), such that \[ (*)\quad \sum_{i\in A}x_ i+\sum_{j\in \Gamma}x_ j\to \min \] , \(\sum_{j\in D(i)}y^ k_ j-\sum_{j\in C(i)}y^ k_ j\geq d_ i\) (i\(\in C)\), \(\sum_{j\in C(i)}y^ k_ j-\sum_{j\in D(i)}y^ k_ j\leq \phi_ i(x_ i,k)\) (i\(\in A)\) \[ y^ k_ j\leq \phi_ j(x_ j,k)\quad (j\in \Gamma),\quad \sum_{j\in C(i)}y^ k_ j=\sum_{j\in D(i)}y^ k_ j\quad (i\in B),\quad y\geq 0,\quad x\geq 0,\quad k=1,...,\ell, \] where: \(\Gamma\) is a set of arcs; A is a set of vertices in which a certain product may be produced; C is a set of vertices in which the product is demanded (the demand in vertex \(i\in C\) is equal to \(d_ i)\); B is the set of remaining vertices; D(i) and C(i) are sets of arcs entering and leaving the vertex i, respectively; x and y determine a distribution of some funds to vertices of A and to all arcs; \(Y^ k\) is a variant of product flow in the network, for the case when the k-th factor from \(\ell\) possible uncertain factors occurs. The capacity of any arc \(j\in \Gamma\) as well as the supply of product in any vertex \(i\in A\) depend on the quantity \(x_ j\) (or \(x_ i)\) of distributed funds as well as on the factor k. Assuming that functions \(\phi_ j(x_ j,k)\) are nondecreasing and concave with respect to \(x_ j\) the author shows that the dual problem to the problem (*) may be transformed to a problem of maximization of a certain concave function with linear constraints. This dual problem may be easily solved if \(\phi_ j(x_ j,k)\) are polynomials of the degree less or equal to five.