Властивості лінійних безумовних задач оптимізації на розміщеннях з імовірнісною невизначеністю
Дослiджуються властивостi безумовних оптимiзацiйних задач на розмiщеннях з лiнiйною цiльовою функцiєю, коли при заданнi допустимої множини має мiсце iмовiрнiсна невизначенiсть. Сформульовано й обгрунтовано умову, що може бути покладена в основу пошуку розв’язку, та способи побудови розв’язку у деяки...
Збережено в:
| Опубліковано в: : | Доповіді НАН України |
|---|---|
| Дата: | 2016 |
| Автори: | , |
| Формат: | Стаття |
| Мова: | Українська |
| Опубліковано: |
Видавничий дім "Академперіодика" НАН України
2016
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/99002 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Властивості лінійних безумовних задач оптимізації на розміщеннях з імовірнісною невизначеністю / О.О. Ємець, Т.М. Барболіна // Доповіді Національної академії наук України. — 2016. — № 2. — С. 31-37. — Бібліогр.: 12 назв. — укр. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859946228042694656 |
|---|---|
| author | Ємець, О.О. Барболіна, Т.М. |
| author_facet | Ємець, О.О. Барболіна, Т.М. |
| citation_txt | Властивості лінійних безумовних задач оптимізації на розміщеннях з імовірнісною невизначеністю / О.О. Ємець, Т.М. Барболіна // Доповіді Національної академії наук України. — 2016. — № 2. — С. 31-37. — Бібліогр.: 12 назв. — укр. |
| collection | DSpace DC |
| container_title | Доповіді НАН України |
| description | Дослiджуються властивостi безумовних оптимiзацiйних задач на розмiщеннях з лiнiйною цiльовою функцiєю, коли при заданнi допустимої множини має мiсце iмовiрнiсна невизначенiсть. Сформульовано й обгрунтовано умову, що може бути покладена в основу пошуку розв’язку, та способи побудови розв’язку у деяких частинних випадках.
Показано, що до розглянутої задачi може бути зведено розв’язування безумовної задачi
оптимiзацiї на розмiщеннях, у якiй дискретними випадковими величинами є коефiцiєнти цiльової функцiї.
Исследуются свойства безусловных оптимизационных задач на размещениях с линейной
целевой функцией, когда при задании допустимого множества имеет место вероятностная
неопределенность. Сформулировано и обосновано условие, которое может быть положено
в основу поиска решения, и способы построения решения в некоторых частных случаях.
Показано, что к рассмотренной задаче может быть сведено решение безусловной задачи
оптимизации на размещениях, в которой дискретными случайными величинами являются коэффициенты целевой функции.
The properties of linear unconditional optimization problems on arrangements, when a feasible
region is defined with probabilistic uncertainty, are studied. We formulate and prove the condition as
a base of solution’s search and ways of solution’s construction in particular cases. We demonstrate
that the solution of the unconditional optimization problem on arrangements with discrete random
variables as coefficients of the goal function can be reduced to that of the examined problem.
|
| first_indexed | 2025-12-07T16:14:21Z |
| format | Article |
| fulltext |
УДК 519.85 http://dx.doi.org/10.15407/dopovidi2016.02.031
О.О. Ємець1, Т.М. Барболiна2
1Полтавський унiверситет економiки i торгiвлi
2Полтавський нацiональнiй педагогiчний унiверситет iм. В.Г. Короленка
E-mail: yemetsli@ukr.net, tm-b@ukr.net
Властивостi лiнiйних безумовних задач оптимiзацiї
на розмiщеннях з iмовiрнiсною невизначенiстю
(Представлено академiком НАН України I.В. Сергiєнком)
Дослiджуються властивостi безумовних оптимiзацiйних задач на розмiщеннях з лi-
нiйною цiльовою функцiєю, коли при заданнi допустимої множини має мiсце iмовiрнi-
сна невизначенiсть. Сформульовано й обгрунтовано умову, що може бути покладена
в основу пошуку розв’язку, та способи побудови розв’язку у деяких частинних випадках.
Показано, що до розглянутої задачi може бути зведено розв’язування безумовної задачi
оптимiзацiї на розмiщеннях, у якiй дискретними випадковими величинами є коефiцiєн-
ти цiльової функцiї.
Ключовi слова: iмовiрнiсна невизначенiсть, дискретна випадкова величина, евклiдова
задача комбiнаторної оптимiзацiї, лiнiйна безумовна задача комбiнаторної оптимiзацiї,
лiнiйна безумовна задача оптимiзацiї на розмiщеннях.
Актуальним напрямом сучасної теорiї оптимiзацiї є дослiдження задач комбiнаторної
природи (див., наприклад, [1–4]). З iншого боку, побудова адекватних математичних моде-
лей практичних задач вимагає враховувати у постановках рiзнi види невизначеностi, у тому
числi iмовiрнiсну (див., наприклад, [5–8]). Об’єднання вказаних напрямiв дослiджень пред-
ставлене в роботах [9–12] та iнших, де постановки оптимiзацiйних задач здiйснюються на
основi введення вiдношення порядку на множинi вiдповiдних величин. Поширення такого
пiдходу на оптимiзацiйнi задачi з iмовiрнiсною невизначенiстю запропоновано в [11]. Дана
робота присвячена вивченню властивостей комбiнаторних стохастичних задач на розмiще-
ннях з лiнiйною цiльовою функцiєю.
Термiнологiю стосовно евклiдової комбiнаторної оптимiзацiї використовуватимемо пе-
реважно з [2], у постановках оптимiзацiйних задач застосовуватимемо пiдхiд, запропонова-
ний в [11]: введемо порядок на заданiй скiнченнiй множинi дискретних випадкових величин
i визначатимемо мiнiмум як випадкову величину, що передує в цьому порядку всiм iншим
елементам множини. У роботi використовуватимемо лiнiйний порядок, що вводиться таким
чином.
Нехай P (·) позначає ймовiрнiсть випадкової подiї, а M(A) i D(A) — вiдповiдно ма-
тематичне сподiвання i дисперсiю випадкової величини A (у рамках роботи розглядати-
мемо лише дискретнi випадковi величини, серед можливих значень яких є найменше);
H(A) = (M(A);−D(A)). Через < l позначатимемо лексикографiчне упорядкування в m-ви-
мiрному евклiдовому просторi: для будь-яких u, u′ ∈ Rm u < lu
′, якщо перша ненульова
компонента рiзницi u − u′ вiд’ємна. Якщо u < lu
′ або u = u′, то записуватимемо u 6 lu
′.
Також записуватимемо u > lu
′, якщо u′ 6 lu.
© О.О. Ємець, Т.М. Барболiна, 2016
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2016, №2 31
Означення 1. Називатимемо двi дискретнi випадковi величини A, B упорядкованими
у зростаючому порядку ≺ (позначати цей факт A ≺ B), якщо
1) H(A) < lH(B) або
2) H(A) = H(B), причому для упорядкованих за зростанням можливих значень ai i bj
випадкових величин A i B знайдеться такий iндекс t, що ai = bi, P (A = ai) = P (B = bi)
для всiх 1 6 i < t, i при цьому:
1.1) або at < bt,
1.2) або at = bt i P (A = ai) > P (B = bi).
Означення 2. Називатимемо двi дискретнi випадковi величини A, B упорядкованими
у неспадаючому порядку ≼ (позначати цей факт A ≼ B), якщо A ≺ B або A = B.
Називатимемо дискретнi випадковi величини A, B упорядкованими у незростаючому
порядку ≽ i записуватимемо A ≽ B, якщо B ≼ A.
Розглянемо спочатку таку задачу: знайти пару ⟨L(X∗), X∗⟩ таку, що
L(X∗) = min
X∈Ek
η (Γ)
k∑
j=1
cjXj , X∗ = arg min
X∈Ek
η (Γ)
k∑
j=1
cjXj , (1)
де L(X) =
k∑
j=1
cjXj , для всiх i ∈ Jk (тут i далi Jm = {1, . . . ,m}), cj ∈ R1, cj > 0, Ek
η (Γ) —
загальна множина розмiщень з елементiв мультимножини Γ = {G1, . . . , Gη}, якi є незале-
жними дискретними випадковими величинами з невiд’ємним математичним сподiванням.
Вважатимемо, що коефiцiєнти цiльової функцiї L(X) упорядкованi за незростанням, при-
чому основою (кортежем усiх рiзних елементiв) мультимножини {c1, c2, . . . , ck} є кортеж
(c1, . . . , cs), елементи якого упорядкованi за зростанням, кратнiсть (число повторiв) еле-
мента ci (i ∈ Js) позначатимемо qi. Позначимо також q1 = 1, qi+1 = qi + qi = 1 +
i∑
j=1
qj для
i ∈ Js; тодi виконуються спiввiдношення
cq1 = . . . = cq2−1 > cq2 = . . . = cq3−1 > . . . > cqs = . . . = ck > 0. (2)
Теорема 1. Якщо виконуються умови (2) i
H(G1) 6 l . . . 6 lH(Gη), (3)
то для однiєї з мiнiмалей X∗ у задачi (1) виконуються спiввiдношення
H(X∗
j ) = H(Gj) ∀j ∈ Jk. (4)
Доведення проводиться за такою схемою. Нехай L∗ — мiнiмум у задачi (1), ΓM =
= {M(G1), . . . ,M(Gη)}. Для точки X ∈ Ekη (Γ) позначимо µ(X) = (M(X1), . . . ,M(Xk)). Тодi
розв’язок задачi мiнiмiзацiї лiнiйної цiльової функцiї L(x) =
k∑
j=1
cjxj на множинi Ekη (Γ
M )
дає точка µ(X∗), де X∗ задовольняє (4). Оскiльки L(µ(X)) = M(L(X)), то M(L(X∗)) 6
6 M(L(X)) для будь-якої точки X ∈ Ek
η (Γ). З iншого боку M(L∗) 6 M(L(X∗)). Отже,
M(L∗) = M(L(X∗)). Можна також показати, що iснує така точка X ′, що L(X ′) = L∗ i при
цьому
M(X ′
j) =M(Gj) ∀j ∈ Jk. (5)
32 ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2016, №2
На наступному етапi розiб’ємо мультимножину Γ на пiдмультимножини Γi так, щоб усi
випадковi величини, належнi Γi, мали однакове математичне сподiвання. Також представи-
мо цiльову функцiю як суму функцiй вигляду L̃i(x) =
ηi+ki∑
j=ηi
c2jxj , де iндекси ηi, ki вiдповiда-
ють розбиттю Γ на пiдмультимножини Γi. Максималлю функцiї L̃i(x) на множинi розмiщень
з мультимножини ΓDi = {D(Gj) | Gj ∈ Γi} є точка δi(X) = (D(X∗
ηi), . . . , D(X∗
ηi+ki−1)). Тодi
також
k∑
j=1
c2jD(X∗
j ) >
k∑
j=1
c2jD(X ′
j), тобто D(L(X∗)) > D(L(X ′)). Але оскiльки з M(L(X ′)) =
= M(L(X∗)) i L(X ′) = L∗ ≼ L(X∗) випливає D(L(X ′)) > D(L(X∗)), то D(L(X ′)) =
= D(L(X∗)). Далi аналогiчно, як це робиться для математичного сподiвання, доводиться,
що знайдеться точкаX ′′, яка задовольняє (5), така що L(X ′′) = L∗ iD(X ′′
j ) = D(X∗
j ) ∀j ∈ Jk.
Таким чином, мiнiмаль X ′′ в задачi (1) задовольняє умови H(X ′′
j ) = H(X∗
j ) = H(Gj)
∀j ∈ Jk.
Наслiдок 1.1. Якщо виконуються умови (3) i
c1 > . . . > ck > 0, (6)
то будь-яка мiнiмаль в задачi (1) задовольняє умову (4).
Наслiдок 1.2. Якщо виконуються умови (2), (3) i
H(Gi) ̸= H(Gj), якщо Gi ̸= Gj i, j ∈ Jk, (7)
то точка
X∗
j = Gj ∀j ∈ Jk, (8)
є мiнiмаллю в задачi (1).
Наслiдок 1.3. Якщо виконуються умови (3), (6), (7), то точка (8) є єдиною мiнiмаллю
в задачi (1).
Слiд зазначити, що в загальному випадку, з одного боку, цiльова функцiя в задачi (1)
може мати мiнiмалi, якi не задовольняють умову (4), а з iншого, не всi точки, що задо-
вольняють (4), дають розв’язок задачi (1). Розглянемо питання про вибiр мiнiмалi серед
точок, що задовольняють (4).
Для мультимножини Γ = {G1, . . . , Gη} позначимо ΓH = {H(G1), . . . , H(Gη)}. Нехай ni
(i ∈ Jr) — кратностi елементiв основи мультимножини ΓH , упорядкованих у лексикографi-
чному порядку 6 l. Розiб’ємо мультимножину Γ на пiдмультимножини вигляду
Γi = {Gηi , . . . , Gηi+ni−1}, (9)
де iндекси ηi задовольняють умови
η1 = 1, ηi+1 = ηi + ni = 1 +
i∑
j=1
nj , i ∈ Jr. (10)
Нехай також σ — найменше число таке, що ησ+1 > k, покладемо ki = ni для i ∈ Jσ−1,
kσ = k + 1. Якщо у множинi Γi усi елементи рiвнi, то з умови (4) випливає, що для мiнi-
малi X∗ задачi (1) виконуються рiвностi X∗
ηi = . . . = X∗
ηi+ki−1 = Gηi . Якщо серед величин
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2016, №2 33
Gηi , . . . , Gηi+ni−1 є рiзнi, то (X∗
ηi , . . . , X
∗
ηi+ki−1) є ki-розмiщенням елементiв мультимножи-
ни Γi.
Нехай точка X̃ така, що для всiх i ∈ Jσ (X̃ηi , . . . , X̃ηi+ki−1) надає мiнiмум функцiї
Ci(X) =
ηi+ki−1∑
j=ηi
cjXj на множинi Ekini
(Γi), тобто Ci(X̃) ≼ Ci(X), де (Xηi , . . . , Xηi+ki−1) ∈
∈ Eki
ni
(Γi). Тодi з теореми 1 одержуємо, що для будь-якої точки X ∈ Ekη (Γ), яка задоволь-
няє (4), виконуються спiввiдношення C(X̃) =
σ∑
i=1
Ci(X̃) ≼
σ∑
i=1
Ci(X) = C(X), тобто точка X̃
є мiнiмаллю в задачi (1). Таким чином, має мiсце така теорема.
Теорема 2. Якщо виконуються умови (2) i (3), то принаймнi одна мiнiмаль X∗ за-
дачi (1) задовольняє умови
(X∗
ηi , . . . , X
∗
ηi+ki−1) = arg min
(Xηi ,...,Xηi+ki−1)∈E
ki
ni
(Γi)
ηi+ki−1∑
j=ηi
cjXj ∀i ∈ Jσ,
де Γi — мультимножини вигляду (9), у яких iндекси задовольняються (10), ni (i ∈ Jr) —
кратностi елементiв основи мультимножини ΓH = {H(G1), . . . , H(Gη)}, упорядкованих
у лексикографiчному порядку, ki = ni для i ∈ Jσ−1, kσ = k − ησ+1, σ визначається з умови
ησ 6 k, ησ+1 > k.
Разом iз задачею (1) розглянемо задачу пошуку пари ⟨L1(x
∗), x∗⟩ такої, що
L1(x
∗) = min
x∈Ek
η (G)
k∑
j=1
Cjxj , x∗ = arg min
x∈Ek
η (G)
k∑
j=1
Cjxj , (11)
де, на вiдмiну вiд задачi (1), коефiцiєнти Cj ∀j ∈ Jk цiльової функцiї L1(x) =
k∑
j=1
Cjxj
є незалежними дискретними випадковими величинами з додатним математичним сподiва-
нням, а елементи мультимножини G = {g1, . . . , gη} — детермiнованими. Вважатимемо, що
елементи мультимножини G додатнi й упорядкованi за неспаданням:
0 < g1 6 g2 6 . . . 6 gη. (12)
Розглянемо детермiновану задачу пошуку пари ⟨L1(x
∗), x∗⟩ такої, що
L1(x
∗) = min
x∈Ek
η (G)
k∑
j=1
cjxj , x∗ = arg min
x∈Ek
η (G)
k∑
j=1
cjxj , (13)
де L1(x) =
k∑
j=1
cjxj , cj = M(Cj) ∀j ∈ Jk. Як випливає з теореми 3.1 [2, с. 79], якщо
c̄1 > . . . > c̄k, то з мiнiмалей в задачi (13) є точка (g1, g2, . . . , gk). Можна також показа-
ти, що будь-яка iнша мiнiмаль у задачi (13) є елементом загальної множини переставлень
Ek(G
′) з елементiв мультимножини G′ = {g1, g2, .., gk}. Це означає, що для будь-якої точки
x /∈ Ek(G
′) виконується нерiвнiсть L1(x
∗) < L1(x). Враховуючи, що
L(x) =
k∑
j=1
cjxj =
k∑
j=1
M(Cj)xj =M
(
k∑
j=1
Cjxj
)
=M(L(x)),
з означення 1 отримуємо, що також L(x∗) ≺ L(x) ∀x /∈ Ek(G
′).
34 ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2016, №2
Таким чином, мiнiмаль у задачi (11) також є переставленням елементiв мультимножини
G′, тобто оптимум цiльової функцiї L∗
1 =
k∑
j=1
Cjgij , де gij ∈ G′, ij ̸= it ∀ij , it ∈ Jk, ∀j, t ∈ Jk.
Тодi задачу (11) можна розглядати як задачу пошуку пари ⟨F (Y ∗), Y ∗⟩ такої, що
F (Y ∗) = min
Y ∈Ek(Θ)
k∑
j=1
gjYj , Y ∗ = arg min
Y ∈Ek(Θ)
k∑
j=1
gjYj , (14)
де F (Y ) =
k∑
j=1
gjYj , мультимножина Θ = {C1, C2, . . . , Ck}. Вважатимемо, що елементи муль-
тимножини Θ задовольняють умову
H(C1) > lH(C2) > l . . . > lH(Ck). (15)
З теореми 1 випливає, що принаймнi для однiєї мiнiмалi Y ∗ задачi (14) виконуються
спiввiдношення H(Y ∗
j ) = H(Cj) ∀j ∈ Jk. Розiб’ємо мультимножину Θ на пiдмультимножи-
ни вигляду Θi = {Cηi , . . . , Cηi+ni−1}, де величини ηi визначаються спiввiдношеннями (10);
ni — кратностi елементiв основи мультимножини ΘH = {H(C1), . . . , H(Ck)}, розташованих
у порядку > l.
Тодi мiнiмаль Y ∗ в задачi (14) задовольняє умову (Y ∗
ηi , . . . , Y
∗
ηi+ni−1) ∈ Eni(Θi). Отже,
оптимум F ∗ задачi (14) може бути визначений таким чином: F ∗ =
r∑
i=1
(ηi+ni−1∑
j=ηi
gjClj
)
, де
Clj ∈ Θi; r — кiлькiсть елементiв основи мультимножини ΘH . А тодi також одна з мiнi-
малей x∗ задачi (11) задовольняє умову (x∗ηi , . . . , x
∗
ηi+ni−1) ∈ Eni(G
i), де мультимножини
Gi = {gηi , . . . , gηi+ni−1}, а величини ni i ηi визначаються так само, як i вище. Отже, дове-
дено таку теорему.
Теорема 3. Нехай для коефiцiєнтiв цiльової функцiї та елементiв мультимножини
в задачi (11) виконуються умови (12) i (15); основа мультимножини ΘH = {H(C1), . . .,
. . . , H(Ck)} мiстить r елементiв; для всiх i ∈ Jr G
i = {gηi , . . . , gηi+ni−1}, де ηi визначаю-
ться згiдно з (10), ni — кратностi елементiв основи мультимножини ΘH , розташованих
у порядку > l. Тодi для деякого розв’язку ⟨L1(x
∗), x∗⟩ задачi (11) виконуються умови:
(x∗ηi , . . . , x
∗
ηi+ni−1) ∈ Eni(G
i), L1(x
∗) =
n∑
i=1
(
ηi+ni−1∑
j=ηi
Cjglj
)
,
де glj ∈ Gi.
Таким чином, у роботi дослiджено властивостi лiнiйної безумовної задачi оптимiзацiї
на розмiщеннях у випадку, коли елементи мультимножини є дискретними випадковими
величинами. Розглянутi властивостi можуть використовуватися при обгрунтуваннi методiв
розв’язування таких задач.
Цитована лiтература
1. Сергиенко И.В., Каспшицкая М.Ф. Модели и методы решения на ЭВМ комбинаторных задач опти-
мизации. – Киев: Наук. думка, 1981. – 288 с.
2. Cтоян Ю.Г., Ємець О.О. Теорiя i методи евклiдової комбiнаторної оптимiзацiї. – Київ: Iнститут
системних дослiджень освiти, 1993. – 188 с. – Режим доступу: http://dspace.puet.edu.ua/handle/
123456789/487.
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2016, №2 35
3. Емец О.А., Барболина Т.Н. Комбинаторная оптимизация на размещениях. – Киев: Наук. думка,
2008. – 159 с. – Режим доступу:http://dspace. puet. edu. ua/handle/123456789/473..
4. Донець Г.П., Колєчкiна Л.М. Екстремальнi задачi на комбiнаторних конфiгурацiях. – Полтава: РВВ
ПУЕТ, 2011. – 309 с. – Режим доступу: http: // dspace. puet. edu. ua/handle/123456789/560.
5. Сергиенко И.В., Михалевич М.В. Применение методов стохастической оптимизации для исследова-
ния трансформационных процессов в экономике // Системнi дослiдження та iнформацiйнi техноло-
гiї. – 2004. – № 4. – С. 7–29.
6. Гайворонский А.А., Ермольев Ю.М., Кнопов П.С., Норкин В.И. Математическое моделирование
распределенных катастрофических и террористических рисков // Кибернетика и систем. анализ. –
2015. – № 1. – С. 97–110.
7. Кан Ю.С., Кибзун А.И. Задачи стохастического программирования с вероятностными критериями. –
Москва: ФИЗМАТЛИТ, 2009. – 375 с.
8. Marti K. Stochastic Optimization Methods. – Berlin: Springer, 2008. – 340 p.
9. Сергиенко И.В., Емец О.А., Емец А.О. Задачи оптимизации с интервальной неопределенностью:
метод ветвей и границ // Кибернетика и систем. анализ. – 2013. – № 5. – С. 38–50.
10. Ємець О.О., Ємець Ол-ра О. Розв’язування задач комбiнаторної оптимiзацiї на нечiтких множинах. –
Полтава: ПУЕТ, 2011. – 239 с. – Режим доступу: http: // dspace. uccu. org. ua/handle/123456789/352.
11. Емец О.А., Барболина Т.Н. Об оптимизационных задачах с вероятностной неопределенностью //
Доп. НАН України. – 2014. – № 11. – С. 40–45.
12. Ємець О.О., Барболiна Т.М. Побудова i дослiдження математичної моделi задачi директора зi стоха-
стичними параметрами // Вiсн. Черкаського ун-ту. Серiя Прикл. математика. Iнформатика – 2014. –
№ 18. – С. 3–11.
References
1. Sergienko I. V., Kaspshitskaya M.F. Models and methods of solving combinatorial optimization problems
by comput. Kiev: Nauk. Dumka, 1981 (in Russian).
2. Stoyan Yu.G., Iemets O.O. Theory and methods of euclidian combinatorial optimization, Kiev: Instytut
systemnykh doslidzhen osvity, 1993 (in Ukrainian).
3. Iemets O.A., Barbolina T.N. Combinatorial optimization on arrangements, Kiev: Nauk. Dumka, 2008 (in
Russian).
4. Donets G.A., Kolechkina L.M. Extremal problems on combinatorial configurations, Poltava: RVV PUET,
2011 (in Ukrainian).
5. Sergienko I. V., Mikhalevich M.V. System Research and Information Technologies, 2004, No 4: 7–29 (in
Russian).
6. Haivoronskyy O.O., Ermoliev Yu.M., Knopov P. S., Norkin V. I. Cybernetics and Systems Analysis, 2015,
51, No 1: 64–73 (in Russian).
7. Kan Yu. S., Kibzun A. I. Stochastic programming problems with probability functions, Moscow: FIZMAT-
LIT, 2009 (in Russian).
8. Marti K. Stochastic Optimization Methods, Berlin: Springer, 2008.
9. Sergienko I. V., Iemets O.O., Yemets O.O. Cybernetics and Systems Analysis, 2013, 49, No 5: 673–683
(in Russian).
10. Iemets O.O., Yemets O.O. Solving combinatorial optimization problems on fuzzy sets, Poltava: PUET,
2011 (in Ukrainian).
11. Iemets O.O., Barbolina T.M. Dop. NAN Ukraine, 2014, No 11: 40–45 (in Ukrainian).
12. Iemets O.O., Barbolina T.M. Visnyk Cherkaskoho universytetu. Seria Prykladna matematyka. Informa-
tyka, 2014, No 18: 3–11 (in Ukrainian).
Надiйшло до редакцiї 07.07.2015
36 ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2016, №2
О.А. Емец1, Т.Н. Барболина2
1Полтавский университет экономики и торговли
2Полтавский национальный педагогический университет им. В.Г. Короленко
E-mail: yemetsli@ukr.net, tm-b@ukr.net
Об оптимизационных задачах на размещениях с вероятностной
неопределенностью
Исследуются свойства безусловных оптимизационных задач на размещениях с линейной
целевой функцией, когда при задании допустимого множества имеет место вероятностная
неопределенность. Сформулировано и обосновано условие, которое может быть положено
в основу поиска решения, и способы построения решения в некоторых частных случаях.
Показано, что к рассмотренной задаче может быть сведено решение безусловной задачи
оптимизации на размещениях, в которой дискретными случайными величинами являются
коэффициенты целевой функции.
Ключевые слова: вероятностная неопределенность, дискретная случайная величина, ев-
клидова задача комбинаторной оптимизации, линейная безусловная задача оптимизации на
размещениях.
O.O. Iemets1, T. M. Barbolina2
1Poltava University of Economics and Trade
2V.G. Korolenko Poltava National Pedagogical University
E-mail: yemetsli@ukr.net, tm-b@ukr.net
Properties of linear unconditional optimization problems on
arrangements under probabilistic uncertainty
The properties of linear unconditional optimization problems on arrangements, when a feasible
region is defined with probabilistic uncertainty, are studied. We formulate and prove the condition as
a base of solution’s search and ways of solution’s construction in particular cases. We demonstrate
that the solution of the unconditional optimization problem on arrangements with discrete random
variables as coefficients of the goal function can be reduced to that of the examined problem.
Keywords: probabilistic uncertainty, discrete random variable, Euclidean problem of combinatori-
al optimization, linear unconditional optimization problem on arrangements.
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2016, №2 37
|
| id | nasplib_isofts_kiev_ua-123456789-99002 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1025-6415 |
| language | Ukrainian |
| last_indexed | 2025-12-07T16:14:21Z |
| publishDate | 2016 |
| publisher | Видавничий дім "Академперіодика" НАН України |
| record_format | dspace |
| spelling | Ємець, О.О. Барболіна, Т.М. 2016-04-20T13:36:45Z 2016-04-20T13:36:45Z 2016 Властивості лінійних безумовних задач оптимізації на розміщеннях з імовірнісною невизначеністю / О.О. Ємець, Т.М. Барболіна // Доповіді Національної академії наук України. — 2016. — № 2. — С. 31-37. — Бібліогр.: 12 назв. — укр. 1025-6415 https://nasplib.isofts.kiev.ua/handle/123456789/99002 519.85 Дослiджуються властивостi безумовних оптимiзацiйних задач на розмiщеннях з лiнiйною цiльовою функцiєю, коли при заданнi допустимої множини має мiсце iмовiрнiсна невизначенiсть. Сформульовано й обгрунтовано умову, що може бути покладена в основу пошуку розв’язку, та способи побудови розв’язку у деяких частинних випадках. Показано, що до розглянутої задачi може бути зведено розв’язування безумовної задачi оптимiзацiї на розмiщеннях, у якiй дискретними випадковими величинами є коефiцiєнти цiльової функцiї. Исследуются свойства безусловных оптимизационных задач на размещениях с линейной целевой функцией, когда при задании допустимого множества имеет место вероятностная неопределенность. Сформулировано и обосновано условие, которое может быть положено в основу поиска решения, и способы построения решения в некоторых частных случаях. Показано, что к рассмотренной задаче может быть сведено решение безусловной задачи оптимизации на размещениях, в которой дискретными случайными величинами являются коэффициенты целевой функции. The properties of linear unconditional optimization problems on arrangements, when a feasible region is defined with probabilistic uncertainty, are studied. We formulate and prove the condition as a base of solution’s search and ways of solution’s construction in particular cases. We demonstrate that the solution of the unconditional optimization problem on arrangements with discrete random variables as coefficients of the goal function can be reduced to that of the examined problem. uk Видавничий дім "Академперіодика" НАН України Доповіді НАН України Інформатика та кібернетика Властивості лінійних безумовних задач оптимізації на розміщеннях з імовірнісною невизначеністю Об оптимизационных задачах на размещениях с вероятностной неопределенностью Properties of linear unconditional optimization problems on arrangements under probabilistic uncertainty Article published earlier |
| spellingShingle | Властивості лінійних безумовних задач оптимізації на розміщеннях з імовірнісною невизначеністю Ємець, О.О. Барболіна, Т.М. Інформатика та кібернетика |
| title | Властивості лінійних безумовних задач оптимізації на розміщеннях з імовірнісною невизначеністю |
| title_alt | Об оптимизационных задачах на размещениях с вероятностной неопределенностью Properties of linear unconditional optimization problems on arrangements under probabilistic uncertainty |
| title_full | Властивості лінійних безумовних задач оптимізації на розміщеннях з імовірнісною невизначеністю |
| title_fullStr | Властивості лінійних безумовних задач оптимізації на розміщеннях з імовірнісною невизначеністю |
| title_full_unstemmed | Властивості лінійних безумовних задач оптимізації на розміщеннях з імовірнісною невизначеністю |
| title_short | Властивості лінійних безумовних задач оптимізації на розміщеннях з імовірнісною невизначеністю |
| title_sort | властивості лінійних безумовних задач оптимізації на розміщеннях з імовірнісною невизначеністю |
| topic | Інформатика та кібернетика |
| topic_facet | Інформатика та кібернетика |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/99002 |
| work_keys_str_mv | AT êmecʹoo vlastivostílíníinihbezumovnihzadačoptimízacíínarozmíŝennâhzímovírnísnoûneviznačenístû AT barbolínatm vlastivostílíníinihbezumovnihzadačoptimízacíínarozmíŝennâhzímovírnísnoûneviznačenístû AT êmecʹoo oboptimizacionnyhzadačahnarazmeŝeniâhsveroâtnostnoineopredelennostʹû AT barbolínatm oboptimizacionnyhzadačahnarazmeŝeniâhsveroâtnostnoineopredelennostʹû AT êmecʹoo propertiesoflinearunconditionaloptimizationproblemsonarrangementsunderprobabilisticuncertainty AT barbolínatm propertiesoflinearunconditionaloptimizationproblemsonarrangementsunderprobabilisticuncertainty |