Background Image
Previous Page  5 / 14 Next Page
Information
Show Menu
Previous Page 5 / 14 Next Page
Page Background

Для задач комбинаторной оптимизации она была предложена в рабо-

тах [5, 9].

Определение.

Параметрическая задача называется конечнознач-

ной на

[

a, b

]

, если существует такой набор интервалов

(

t

i

, t

i

+1

)

,

i

= 1

, . . . , N

1

, что

[

a, b

] =

{

a

} ∪ {

b

}

N

S

i

=1

{

t

i

}

N

1

S

i

=1

(

t

i

, t

i

+1

)

, и реше-

ние любой задачи в точке

t

(

t

i

, t

i

+1

)

является ее решением на всем

интервале

(

t

i

, t

i

+1

)

,

i

= 1

, . . . , N

1

.

Интервалы в этом определении представляют собой аналоги обла-

стей устойчивости, а размер интервала — аналог радиуса устойчиво-

сти. В работе [9] проведен подробный анализ параметрических задач

оптимизации и получен критерий конечнозначности.

Пусть

ϕ

ij

(

t

) =

τ

i

(A(

t

))

τ

j

(A(

t

))

,

i, j

= 1

, . . . , q

. Множество этих

функций обозначим как

Φ

. Знак функции — это знаки “+”, “–” или “0”.

Точка

t

0

называется точкой перемены знака функции, если для любого

ε >

0

в любой

ε

-окрестности точки найдется точка

t

1

такая, что знаки

функции в этих точках разные.

Очевидно, что для задачи линейного программирования конечно-

значность обеспечивается. В работе [9] показано, что и для полиноми-

альной зависимости от параметра можно доказать конечнозначность

в случае линейного функционала и функционала на “узкие места”.

Получен ряд других достаточных условий конечнозначности, но они

имеют весьма специфический характер. Однако в случае этих функци-

оналов до сих пор неизвестен критерий (необходимое и достаточное

условие) конечнозначности, который бы формулировался только на

базе аналитических свойств функций

A(

t

)

. Приведем пример указан-

ного общего критерия, в котором необходимо учитывать структуру

множества траекторий задачи.

Содержательный смысл критерия состоит в возможности исключе-

ния из рассмотрения некоторого подмножества траекторий в окрест-

ности некоторых точек на интервале

[

a, b

]

. Этими точками являются

“точки сгущения точек перемен знака”, точки в полуокрестности ко-

торых некоторая функция

ϕ

ij

(

t

)

меняет знак бесконечное число раз.

Если удается установить, что в этой окрестности ни одна из траек-

торий

τ

i

(A(

t

))

,

τ

j

(A(

t

))

не может быть оптимальной, то получается

необходимое и достаточное условие конечнозначности задачи. Конеч-

нозначность дает возможность вместо решения задачи во всех точках

[

a, b

]

ограничиться ее решением в конечном числе точек этого интер-

вала.

Применение исследования устойчивости в математическом

моделировании.

Рассмотрим следующую ситуацию: моделируется

процесс

P

, происходящий во времени и имеющий несколько компо-

нент

K

1

, . . . , K

s

, математические модели которых представлены опти-

мизационными задачами или задачами вычислительной геометрии

ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2015. № 5 65