ICM 1998, Berlin, Aug. 18–27

Abstracts of Short Communications and Posters

Section:

17. Control Theory and Optimization

1991 MS Classification: 5, 49, 90 Kasaev, Anzor, Karachai-Cherkes Technological Institute, Russia Assigment Probllem in Consideration of Discounting The set of admissible solutions (SAS) is defined by system of equalities:

∑_{i=1}^{n} ∑_{j=1}^{n} x_{ij}z_{ij}^{k} = 1; k = \overline{1, n}; ∑_{j=1}^{n} ∑_{k=1}^{n} x_{ij}z_{ij}^{k} = 1; i = \overline{1, n}; ∑_{i=1}^{n} ∑_{k=1}^{n} x_{ij}z_{ij}^{k} = 1; j =

\overline{1, n}; x_{ij}, z_{ij}^{k} ∈ \{0, 1\}, i, i, k = \overline{1, n}. The objective function (OF) is defined on

SAS: ∑_{k=1}^{n} ∑_{i=1}^{n} ∑_{j=1}^{n} c_{ij}x_{ij}z_{ij}^{k}(1 + ρ) → max, ρ > 0. When ρ = 0 then this OF is

OF of polynomialy solvable classical assigment problem. The stated above assigment problem in consideration of discounting (i. e when (ρ > 0) is NP-hard problem and the set of optimums of this problem changes with the increasing ρ. In this work there were also determined adequete conditions in which the assigment problem is polynomaly solvable when ρ > 0.