ICM 1998, Berlin, Aug. 18–27

Abstracts of Short Communications and Posters

Section:

17. Control Theory and Optimization

1991 MS Classification: 5, 49, 90 Popova, Elena, Karachai-Cherkes Technological Institute, Russia Estimates of Complexity of the Vector Ordering Problem The set of admissible solutions is the set X = {x} of all n! permutations x = (i_{1}, i_{2}, ..., i_{n}) of numbers 1, 2, ..., n. The vector objective function (VOF) is defined on X: F (x) = (F_{1}(x), F_{2}(x)), F_{ν}(x) ∈ {φ_{ν}, ψ_{ν}(x)}, 1 ≤

ν ≤ 2, φ_{ν}(x) = ∑_{k=1}^{n} α_{i_{k}}^{ν}z_{i_{k}}^{ν} → min, ψ_{ν}(x) = max_{1≤k≤n} α_{i_{k}}^{ν}z_{i_{k}}^{ν} → min, z_{i_{k}}^{ν} =

max(t_{i_{k}} − D_{i_{k}}^{ν}, 0), t_{i_{k}} = ∑_{s=1}^{k} T_{i_{s}}. VOF determines Pareto set X̃ ⊆ X. Re-

quired solution is the complete set of alternatives (CSA) X^{0} where the subset X^{0} ⊆ X̃ satisfies the equality F (X^{0}) = F (X̃) = {F (x̃) : x̃ ∈ X̃} and has minimal cardinality | X^{0} |. Theorem 1. If criteria F_{ν}(x). have a view φ_{ν}(x), then maximal cardinality of CSA | X^{0} |= n!. Theorem 2. If one of the criterion φ_{ν}(x) has a view ψ_{ν}(x). then maximal cardinality of CSA | X^{0} |≥ 2^{n} .