Лінійні оптимізаційні задачі на разміщеннях з імовірнісною невизначеністю: властивості і розв’язання
Authors study properties of linear optimization problems under probabilistic uncertainty while defining a problem based on the linear order on the set of discrete random variables. Properties of unconditional problem are established whose coefficients of the goal function or multiset's elements...
Збережено в:
| Дата: | 2016 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | Українська |
| Опубліковано: |
The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute"
2016
|
| Онлайн доступ: | https://journal.iasa.kpi.ua/article/view/41735 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | System research and information technologies |
| Завантажити файл: |  |
Репозитарії
System research and information technologies| _version_ | 1866301462949134336 |
|---|---|
| author | Iemets, Oleg Oleksiiovych Barbolina, Tetiana Mykolaivna |
| author_facet | Iemets, Oleg Oleksiiovych Barbolina, Tetiana Mykolaivna |
| author_sort | Iemets, Oleg Oleksiiovych |
| baseUrl_str | http://journal.iasa.kpi.ua/oai |
| collection | OJS |
| datestamp_date | 2016-07-25T14:59:53Z |
| description | Authors study properties of linear optimization problems under probabilistic uncertainty while defining a problem based on the linear order on the set of discrete random variables. Properties of unconditional problem are established whose coefficients of the goal function or multiset's elements (but not both simultaneously) are discrete random variables. Based on properties of the solution of an unconditional problem with deterministic coefficients, we prove solution's properties for the problem with the goal function's coefficients as discrete random variables. The scheme of the branch and bound method for solving the linear optimization problems on permutations under probabilistic uncertainty is proposed as well as rules of branching and truncation of sets. |
| doi_str_mv | 10.20535/SRIT.2308-8893.2016.1.11 |
| first_indexed | 2025-07-17T10:18:36Z |
| format | Article |
| fulltext |
© О.О. Ємець, Т.М. Барболіна, 2016
Системні дослідження та інформаційні технології, 2016, № 1 107
УДК 519.85
DOI: 10.20535/SRIT.2308-8893.2016.1.11
ЛІНІЙНІ ОПТИМІЗАЦІЙНІ ЗАДАЧІ
НА РОЗМІЩЕННЯХ З ІМОВІРНІСНОЮ НЕВИЗНАЧЕНІСТЮ:
ВЛАСТИВОСТІ І РОЗВ’ЯЗАННЯ
О.О. ЄМЕЦЬ, Т.М. БАРБОЛІНА
Досліджено властивості лінійних задач оптимізації на розміщеннях з імовірні-
сною невизначеністю, постановку яких здійснено на основі введення лінійного
порядку на множині дискретних випадкових величин. Установлено властивос-
ті безумовної задачі, у якій коефіцієнти цільової функції або елементи муль-
тимножини (але не те й те одночасно) є дискретними випадковими величинами.
Ґрунтуючись на властивостях розв’язку безумовної задачі з детермінованими
коефіцієнтами цільової функції, доведено властивості розв’язку для задачі, у
якій коефіцієнти цільової функції є випадковими величинами. Запропоновано
схему методу гілок і меж для розв’язання лінійних задач оптимізації на розмі-
щеннях з імовірнісною невизначеністю, у якій також запропоновано правила
галуження та відсікання множин.
ВСТУП
Актуальним напрямом сучасної теорії оптимізації є дослідження (див., зокре-
ма [1–5]) задач комбінаторної природи: вивчаються як загальні властивості
задач комбінаторної оптимізації, так і методи розв’язання окремих класів
задач, зокрема евклідових задач комбінаторної оптимізації (див., наприклад,
[4–5]).
Розглянемо спочатку необхідні поняття й означення евклідової комбі-
наторної оптимізації, спираючись переважно на працю [4]. Під мультимно-
жиною розуміємо сукупність елементів, серед яких можуть бути й однакові.
Будь-яку мультимножину },...,{ 1 ηggG = можна задати основою )(GS , тоб-
то кортежем усіх її різних елементів, і кратністю — кількістю повторень
кожного елемента основи цієї мультимножини. Кратність елемента
)(GSg ∈ позначають через )(gkG . Мультимножину B з основою )(BS
називають підмультимножиною мультимножини A з основою )(AS (по-
значають як AB ⊂ ), якщо )()( ASBS ⊂ і для кожного елемента )(BSa∈
виконується нерівність )()( akak AB ≤ . Якщо AB ⊂ , то різниця BA− муль-
тимножин A і B містить елементи мультимножини A , причому )(ASa∈∀
)()()( akakak BABA −=− ( 0)( ≥− ak BA ).
Евклідовою комбінаторною множиною називають множину, різними
елементами якої є різні впорядковані k -вибірки з мультимножини вигляду
,),...,(
1 kii gg (1)
де Gg
ji ∈ , ηJiiii tjtj ∈∀≠ , , kJtj ∈∀ , (тут і далі через nJ позначено мно-
жину n перших натуральних чисел). Прикладами евклідових комбінаторних
множин є:
О.О. Ємець, Т.М. Барболіна
ISSN 1681–6048 System Research & Information Technologies, 2016, № 1 108
− загальна множина розміщень ( )GEk
η — множина всіх k -вибірок ви-
гляду (1) з мультимножини G ;
− загальна множина переставлень ( )GEk — множина всіх k -вибірок
вигляду (1) з мультимножини G за умови .η=k
Поняття евклідової комбінаторної множини дозволяє виділити з мно-
жини задач оптимізації комбінаторного типу евклідові задачі комбінаторної
оптимізації, що полягають у знаходженні екстремуму та екстремалі функції
кількох змінних на деякій евклідовій комбінаторній множині.
Іншим актуальним напрямом досліджень у галузі оптимізації є дослі-
дження оптимізаційних задач з урахуванням різних невизначеностей, у тому
числі ймовірнісної (див., наприклад, [6–9]). Такі задачі виникають і в комбі-
наторній оптимізації. З одного боку, досліджуються властивості окремих
класів комбінаторних задач з урахуванням того чи іншого виду невизначе-
ності: екстремальні задачі на графах з інтервальними та нечіткими парамет-
рами [10; 11], нечітка і стохастична задача комівояжера [12; 13], стохастичні
задачі, пов’язані з комбінаторними оптимізаційними задачами на допусти-
мій множині nF }1,0{⊂ [14] тощо. З другого боку, вивчаються властивості
досить широких класів евклідових задач комбінаторної оптимізації з інтер-
вальною та нечіткою невизначеністю. Зокрема, побудовані й досліджені ін-
тервальні моделі задач геометричного проектування, їх відображень в евклі-
дові простори [15–17], деякі результати стосовно задач комбінаторної
оптимізації на нечітких множинах узагальнено у праці [18]. Водночас майже
не досліджувалися оптимізаційні задачі на евклідових комбінаторних мно-
жинах з імовірнісною невизначеністю.
Мета роботи — вивчення властивостей комбінаторних стохастичних
задач з лінійною цільовою функцією. Автори використовують підхід до фор-
мулювання оптимізаційних задач, який ґрунтується на введенні відношення
порядку на множині відповідних величин. Такий підхід для задач з інтерва-
льною та нечіткою невизначеністю розглянуто, зокрема у працях [18; 19],
його поширення на оптимізаційні задачі з імовірнісною невизначеністю за-
пропоновано в [20]. Ця робота є продовженням [21; 22].
ПОСТАНОВКИ ОПТИМІЗАЦІЙНИХ ЗАДАЧ З ІМОВІРНІСНОЮ
НЕВЗНАЧЕНІСТЮ НА ОСНОВІ ВІДНОШЕННЯ ПОРЯДКУ
Позначатимемо дискретні випадкові величини великими латинськими літе-
рами ( ,..., BA ), їх можливі значення — малими ( ,..., ii ba ). Розглядатимемо ті
випадкові величини, серед можливих значень яких існує найменше. Вважа-
тимемо, що можливі значення впорядковані за зростанням, причому най-
менше значення має індекс 1. Нехай також )(⋅P позначає ймовір-
ність випадкової події, а )(AM і )(AD — відповідно математичне
сподівання і дисперсію дискретної випадкової величини A . Визначимо та-
кож характеристичний вектор дискретної випадкової величини A як век-
тор .))();(()( ADAMAH −= Зазначимо, що коли випадкові величини A і B
є незалежними, то для їх характеристичних векторів справедливе співвід-
ношення .)()()( BHAHBAH +=+ Дійсно, з властивостей математичного
Лінійні оптимізаційні задачі на розміщеннях з імовірнісною невизначеністю: властивості …
Системні дослідження та інформаційні технології, 2016, № 1 109
сподівання і дисперсії випливає, що для незалежних випадкових величин
виконуються рівності )()()( BMAMBAM +=+ , ,)()()( BDADBAD +=+
звідки і випливає правильність співвідношення.
Через l< позначатимемо лексикографічне упорядкування у m -вимірному
евклідовому просторі: для будь-яких mRuu ∈′, uu l ′< , якщо перша нену-
льова компонента різниці uu ′− від’ємна. Якщо uu l ′< або uu ′= , то запи-
суватимемо uu l ′≤ , якщо uu l≤′ , то записуватимемо uu l ′≥ .
Вважатимемо, що порядок на множині дискретних випадкових величин
уведено поданими нижче означеннями.
Означення 1. Називатимемо дві дискретні випадкові величини BA,
упорядкованими у зростаючому порядку p (і позначатимемо цей факт че-
рез BAp ), якщо )()( BHAH l< або якщо )()( BHAH = , знайдеться такий t ,
що ii ba = , )()( ii bBPaAP === для всіх ti <≤1 , і при цьому:
або tt ba < , або tt ba = і .)()( ii bBPaAP =>=
Означення 2. Називатимемо дві дискретні випадкові величини BA,
упорядкованими у неспадному порядку
−
p (і позначатимемо цей факт через
BA
−
p ), якщо BAp або BA = .
Називатимемо дискретні випадкові величини BA, упорядкованими
у незростаючому порядку
−
f і записуватимемо BA
−
f , якщо AB
−
p .
Безпосередньою перевіркою властивостей можна показати, що відно-
шення, уведене означенням 1, є лінійним порядком на множині дискретних
випадкових величин. Також, якщо для дискретних випадкових величин A
і B виконується умова BAp і величини A і C , B і C — незалежні, то
виконується співвідношення CBCA ++ p . Крім того, як доведено у праці
[21], якщо для незалежних випадкових величин nAA ,...,1 і nBB ,...,1 викону-
ються умови ii BA
−
p nJi∈∀ , то ∑∑
=
−
=
n
i
i
n
i
i BA
11
p .
Використовуючи введений означенням 2 порядок, упорядкуємо елеме-
нти заданої скінченної множини Ω дискретних випадкових величин:
sXXX
−−−
ppp ...21 . Максимумом є величина sX , а мінімумом — величина 1X .
Визначення мінімуму і максимуму дає змогу ставити задачі оптимізації для
знаходження екстремальних елементів за заданих умов. Зокрема, у праці [21]
розглядається розв’язання лінійних безумовних задач стохастичної оптиміза-
ції на розміщеннях у такій постановці: знайти пару **),( XXL таку, що
∑
=Γ∈ η
=
k
j
jj
EX
XcXL
k
1)(
* min)( , ∑
=Γ∈ η
=
k
j
jj
EX
XcX
k 1)(
* minarg , (2)
де ),...,( 1 kXXX = , ∑
=
=
k
j
jj XcXL
1
)( , 1Rc j ∈ , 0>jc kJj∈∀ , ( )ΓkEη — за-
гальна множина розміщень з елементів мультимножини },...,{ 1 η=Γ GG , які
О.О. Ємець, Т.М. Барболіна
ISSN 1681–6048 System Research & Information Technologies, 2016, № 1 110
є незалежними дискретними випадковими величинами, що мають скінченну
кількість можливих значень, причому 0)( ≥iGM η∈∀ Ji . Унаслідок скін-
ченності мультимножини Γ множина значень функції )(XL також є скін-
ченною і на ній може бути визначений мінімум у розглянутому вище розу-
мінні.
ВЛАСТИВОСТІ ЛІНІЙНИХ БЕЗУМОВНИХ ЗАДАЧ ОПТИМІЗАЦІЇ
НА РОЗМІЩЕННЯХ З ІМОВІРНІСНОЮ НЕВИЗНАЧЕНІСТЮ
Разом із задачею (2) розглянемо задачу пошуку пари **
1 ),( xxL такої, що
∑
=∈ η
=
k
j
jj
GEx
xCxL
k
1)(
*
1 min)( , ∑
=∈ η
=
k
j
jj
GEx
xCx
k 1)(
* minarg , (3)
де на відміну від задачі (2) коефіцієнти jC kJj∈∀ цільової функції
∑
=
=
k
j
jj xCxL
1
1 )( є незалежними дискретними випадковими величинами. Тут
),...,( 1 kxxx = , а елементи мультимножини },...,{ 1 ηggG = — детерміновані.
Покажемо, що коли математичні сподівання величин jC kJj∈∀ та
елементи мультимножини G є додатними, розв’язання задачі (3) можна
звести до розв’язання задачі вигляду (2) з детермінованим коефіцієнтами
цільової функції й елементами мультимножини, що є дискретними випадко-
вими величинами. Вважатимемо, що елементи мультимножини G упоряд-
ковані за неспаданням:
ηggg ≤≤≤< ...0 21 , (4)
а коефіцієнти цільової функції задовольняють умову
.)(...)()( 21 klll CHCHCH ≥≥≥ (5)
Розглянемо детерміновану задачу пошуку пари **
1 ),( xxL такої, що
∑
=∈ η
=
k
j
jj
GEx
xcxL
k
1)(
*
1 min)( , ∑
=∈ η
=
k
j
jj
GEx
xcx
k 1)(
* minarg , (6)
де ∑
=
=
k
j
jj xcxL
1
1 )( , )( jj CMc = kJj∈∀ .
Як випливає з теореми 3.1 [4, с.79], однією з мінімалей задачі (6) є точ-
ка .),...,,( 21 kggg Як відомо [4], множина вершин опуклої оболонки множи-
ни )(GEk
η — загального багатогранника розміщень — є підмножиною мно-
жини .)(GEk
η Нехай для суміжних вершин x і x′ загального багатогранника
розміщень виконується умова .)()( xLxL ′= Згідно з критерієм суміжності
вершин загального багатогранника розміщень [4] вершина x є суміжною
з вершиною x′ , якщо вона одержана з вершини x′ переставленням компо-
Лінійні оптимізаційні задачі на розміщеннях з імовірнісною невизначеністю: властивості …
Системні дослідження та інформаційні технології, 2016, № 1 111
нент, що дорівнюють елементам 1, +tt gg ( 1+≠ tt gg ) або заміною rkg − (або
1+−η rg ) на rg −η (чи 1+−rkg відповідно) за умови rrk gg −η− ≠
( 11 +−+−η ≠ rkr gg ). Якщо вершина x отримана з x′ заміною rki gx −=′ на
ri gx −η= , то
0)()()()()(
11
11 ≠−+−′=−′=′− −η−
≠
==
∑∑ rrki
k
ij
j
jjj
k
j
jjj ggcxxcxxcxLxL ,
оскільки jj xx =′ ij ≠∀ kJj∈∀ , rrk gg −η− ≠ , 0)( >= jj CMc kJj∈∀ . Та-
кий самий результат отримується, якщо 1+−=′ ri gx η замінюється на
1+−= rki gx . У випадку, коли вершина x отримана з x′ переставленням ком-
понент ti gx =′ і 1+=′ tq gx ( 1+≠ tt gg ) , тоді
=−′+−′+−′=−′ ∑
≠≠
=
)()()()()(
;
1
11 qqqiii
k
qjij
j
jjj xxcxxcxxcxLxL
).()( qqqiii xxcxxc −′+−′=
Оскільки qi xx =′ , iq xx =′ , то )()( 11 xLxL =′ , якщо 0))(( 1 =−−′ +iiii ccxx .
Ураховуючи, що ii xx ≠′ , дістаємо 1+= ii cc .
Таким чином, якщо для суміжних вершин x і x′ загального багато-
гранника розміщень виконується умова )()( 11 xLxL =′ , то коефіцієнти цільо-
вої функції, що відповідають нерівним елементам ii xx ′≠ , qq xx ′≠ , рівні між
собою: qi cc = .
Нехай точки x′ і *x є мінімалями функції .)(1 xL . Це означає, що знай-
деться послідовність вершин rxx ,...,1 таких, що 1, +ii xx ( 1−∈ rJi ) є суміж-
ними вершинами і )(...)( 1
1
1
rxLxL == . Тоді для кожного індексу l такого,
що *
ll xx ≠′ , знайдеться така множина індексів },...{ 1 piiI = , що
pii cc == ...
1
і мультимножини },...,{
1 pii xx ′′ і },...,{ **
1 pii xx рівні. Тоді також рівні мульти-
множини },...,{ 1 kxx ′′ і },...,{ **
1 kxx . Оскільки однією з мінімалей є точка
),...,( 1 kgg , то будь-яка мінімаль *x задачі (6) є переставленням чисел
kgg ,...,1 , тобто )(* GEx k ′∈ , де )(GEk ′ — загальна множина переставлень
з мультимножини .},...,{ 1 kggG =′ . Це означає, що для будь-якої точки
)(GEx k ′∉ виконується нерівність .)()( 1
*
1 xLxL < Оскільки
( ) ,))(()( 1
111
1 xLMxCMxCMxcxL
k
j
jj
k
j
jj
k
j
jj =
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
=== ∑∑∑
===
то з означення 1 випливає, що також )()( 1
*
1 xLxL p .)(xEx k∉∀
О.О. Ємець, Т.М. Барболіна
ISSN 1681–6048 System Research & Information Technologies, 2016, № 1 112
Таким чином, мінімаль задачі (3) також є переставленням елементів
мультимножини G′ , тобто оптимум цільової функції ∑
=
=
k
j
ij j
gCL
1
*
1 , де
Gg
ji ′∈ , ktjtj Jiiii ∈∀≠ , , kJtj ∈∀ , . Тоді задачу (3) можна розглядати як
задачу пошуку пари **),( YYF такої, що
∑
=Θ∈
=
k
j
jj
EY
YgYF
k 1)(
* min)( , ∑
=Θ∈
=
k
j
jj
EY
YgY
k 1)(
* minarg , (7)
де ∑
=
=
k
j
jjYgYF
1
)( , мультимножина },...,,{ 21 kCCC=Θ .
Оскільки, як доведено у праці [22], за умов kccc ≥≥≥ ...21
і )(...)( 1 ηGHGH l ≤≤ принаймні одна з мінімалей задачі (2) задовольняє
умову )()( *
jj GHXH = kJj∈∀ , то принаймні для однієї мінімалі *Y задачі
(7) виконуються співвідношення )()( *
jj CHYH = kJj∈∀ . Нехай основа
( )HS Θ мультимножини
)}(),...,({ 1 kH CHCH=Θ (8)
містить n елементів, упорядкованих як l≥ , відповідні кратності позначати-
мемо через in . Розіб’ємо мультимножину Θ на підмультимножини вигляду
},...,{ 1−+ηη=Θ
iii ni CC , де величини iη визначаються співвідношеннями:
11 =η , ∑
=
+ +=+η=η
i
j
jiii nn
1
1 1 для nJi∈ . (9)
Тоді мінімаль *Y задачі (7) задовольняє умову ∈−+ηη ),...,( *
1
*
iii nYY
)( ini
E Θ∈ і оптимум *F задачі (7) може бути визначений так:
∑ ∑
=
−+η
η=
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
=
n
i
n
j
lj
ii
i
j
CgF
1
1
* , де il j
C Θ∈ . Тоді також одна з мінімалей *x задачі
(3) задовольняє умову ,)(),...,( *
1
*
inn GExx
iiii
∈−+ηη де мультимножини
},...,{ 1−+ηη=
iii ni ggG , величини in і iη визначаються так само, як і вище.
При цьому оптимум *
1L функції )(1 XL визначається так:
∑ ∑
=
−+η
η=
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
=
n
i
k
j
lj
ii
i
j
gCL
1
1
*
1 , де il Gg
j
∈ . Отже, доведено таку теорему.
Теорема 1. Нехай для елементів мультимножини та коефіцієнтів цільо-
вої функції в задачі (3) виконуються умови (4) і (5) відповідно; мультимно-
жина HΘ визначається згідно з виразом (8), )( HSn Θ= , in — кратності
елементів )( HS Θ , упорядкованих у порядку l≥ ; для всіх nJi∈
Лінійні оптимізаційні задачі на розміщеннях з імовірнісною невизначеністю: властивості …
Системні дослідження та інформаційні технології, 2016, № 1 113
},...,{ 1−+ηη=
iii ni ggG , де iη визначаються згідно зі співвідношенням (9).
Тоді для деякого розв’язку **
1 ),( xxL виконуються умови:
)(),...,( *
1
*
inn GExx
iiii
∈−+ηη , ∑ ∑
=
−+η
η=
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
=
n
i
k
j
lj
ii
i
j
gCxL
1
1
*
1 )( , де il Gg
j
∈ .
ВИКОРИСТАННЯ МЕТОДУ ГІЛОК І МЕЖ
Розглянемо задачу пошуку пари ** ),( xxL такої, що
∑
=∈
=
k
j
jj
Sx
xcxL
1
* min)( , ∑
=∈
=
k
j
jj
Sx
xcx
1
* minarg (10)
за умови
,)(),...,( 1 Γ∈= η
k
k Exxx (11)
де для коефіцієнтів jc цільової функції та елементів мультимножини
},...,{ 1 ηgg=Γ виконується одна з двох умов:
1) k
k Rcc ∈),...,( 1 , 0>jc kJj∈∀ , елементи мультимножини є незале-
жними дискретними випадковими величинами з додатним математичним
сподіванням, відповідно S — деяка область k -вимірних дискретних випад-
кових величин;
2) коефіцієнти цільової функції є незалежними дискретними випадко-
вими величинами, причому 0)( >jcM kJj∈∀ ; 1Rgi ∈ , 0>ig η∈∀ Ji
і kRS ⊂ .
Розглянемо особливості застосування методу гілок і меж для
розв’язання задачі (10)–(11). Допустиму множину задачі (10)–(11) познача-
тимемо через Q , тобто )(Γ∩= η
kESQ . Галуження проводитимемо, надаю-
чи певне можливе значення змінним jx . Це означає, що множина QQ ⊂′ ,
що отримується на деякому рівні галуження у методі гілок і меж, визнача-
ється такими умовами:
jrj gx = , Ij∈ , (12)
де I — деяка множина індексів kJI ⊂ , tI = . При цьому у множині Q′
зафіксовані значення змінних jx , Ij∈ . Змінні, що залишилися невизначе-
ними, позначимо як τxx ~,...,~
1 ( tk −=τ ). Позначимо також
}|{ IjcC jB ∈= — мультимножину коефіцієнтів цільової функції, значення
змінних у цільовій функції при яких зафіксовані, BCCC −=
~ — мультимно-
жину коефіцієнтів, значення змінних при яких ще не визначені. Змінні iX~
( τJi∈ ) нумеруватимемо таким чином, щоб елементи мультимножини
}~,...,~{~
1 τccC = були упорядковані за незростанням (тобто τcc ~...~
1 ff , якщо
О.О. Ємець, Т.М. Барболіна
ISSN 1681–6048 System Research & Information Technologies, 2016, № 1 114
коефіцієнти цільової функції є випадковими величинами, і τcc ~...~
1 ≥≥ у ви-
падку детермінованих). Нехай також }|{ Ijg jB ∈=Γ , BΓ−Γ=Γ~ . Елементи
мультимножини Γ~ позначатимемо через ig~ ( pJi∈ , tp −η=Γ= |~| ) і вважа-
тимемо впорядкованими у неспадному порядку: pgg ~...~
1 pp , якщо елементи
мультимножини — випадкові величини, pgg ~...~
1 ≤≤ — якщо детерміновані.
Розглянемо величину
( ) ∑∑
=∈
+=′
τ
ξ
1
~~
i
ii
Ij
rj gcgcQ
j
. (13)
Теорема 3. Нехай множина QQ ⊂′ визначається згідно з форму-
лою (12). Тоді для будь-якої точки Qxxx k ′∈= ),...,( 1 виконується співвід-
ношення ))(())(( XLHQH l≤′ξ , де величина )(Q′ξ визначається згідно з ве-
личиною (13).
Доведення. Нехай ( ) ∑
=
=
τ
1
~~~~
i
ii xcxL . Оскільки характеристичний вектор
суми незалежних випадкових величин дорівнює сумі їх характеристичних
векторів, то ))~(~(~~))((
1
xLHgcHxcHgcHxLH
Ij
rj
i
ii
Ij
rj jj
+
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
=⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
+
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
= ∑∑∑
∈=∈
τ
і ⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
+
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
=′ξ ∑∑
τ
=∈ 1
~~))((
i
ii
Ij
rj gcHgcHQH
j
, отже, умова ))(())(( xLHQH l≤′ξ
рівносильна умові ))~(~())~(~( xLHxLH l≤′ , де ii gx ~~ =′ τJi∈∀ . Таким чином,
необхідно показати, що для будь-якої точки )~(~ Γ∈ τ
pEx виконуються спів-
відношення .))~(~())~(~( xLHxLH l ′≤′
Розглянемо спочатку випадок, коли коефіцієнти цільової функції є де-
термінованими величинами, а елементи мультимножини — випадковими.
Оскільки елементи мультимножини Γ~ упорядковані у неспадному порядку,
то )~(...)~( 1 kll gHgH ≤≤ . Ураховуючи також упорядкування в незростаючо-
му порядку коефіцієнтів цільової функції, згідно з теоремою 2 [22] маємо,
що принаймні одна з мінімалей *~x функції )~(~ xL на множині )~(Γτ
pE задо-
вольняє співвідношення )~()~( *
jj gHxH = τ∈∀ Jj . Отже, )~(~)(~ * xLxL
−
p
,)~(~ Γ∈∀ τ
pEx звідки .))~(~())(~( * xLHxLH l≤ Також
))~(~()~(~)~(~)~(~))~(~( *
111
xLMxMcgMcxMcxLM
i
ii
i
ii
i
ii =′=′=′=′ ∑∑∑
τ
=
τ
=
τ
=
,
))~(~()~(~)~(~)~(~))~(~( *
1
*2
1
2
1
2 xLDxDcgDcxDcxLD
i
ii
i
ii
i
ii ===′=′ ∑∑∑
===
τττ
,
Лінійні оптимізаційні задачі на розміщеннях з імовірнісною невизначеністю: властивості …
Системні дослідження та інформаційні технології, 2016, № 1 115
звідки ))~(~())~(~( * xLHxLH ′= . Таким чином, для будь-якої точки )~(~ Γ∈ τ
pEx
виконуються співвідношення .))(~())~(~( xLHxLH l ′≤′
Нехай тепер коефіцієнти цільової функції є випадковими величинами,
а елементи мультимножини — детермінованими. Згідно з теоремою 1 опти-
мум цільової функції ∑ ∑
=
−+η
η=
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
=
n
i
n
j
lj
ii
i
j
gcL
1
1
* ~~~ , де }~,...,~{~~
1−+ηη=∈
iiij nil ggGg ,
in — кратності елементів основи мультимножини )}~(),...,~({ 1 kcHcH , упо-
рядкованих як l≥ , iη визначаються згідно зі співвідношенням (9). Тоді
)~(...)~( 1−+ηη ==
iii ncHcH . Оскільки
,))~(~(~)~(~)~()~(
1
1
1
1
* xLMgcMgcMLM
n
i
k
j
jj
n
i
k
j
lj
ii
i
ii
i
j
′=
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
=
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
= ∑ ∑∑ ∑
=
−+η
η==
−+η
η=
аналогічно ,))~(~()~( * xLDLD ′= то ))~(~())~(~( * xLHxLH ′= і для будь-якої точки
)~(~ Γ∈ τ
pEx виконуються співвідношення .))~(~())~(~( xLHxLH l≤′ Теорему до-
ведено.
Наслідок 3.1. Якщо існує допустимий розв’язок x′ задачі (10)–(11),
для якого виконується умова ))(())(( QHxLH l ′ξ<′ , то множина Q′ не міс-
тить оптимального розв’язку.
Зауваження. Величину ))(( QH ′ξ можна використовувати як оцінку
в методі гілок і меж у випадку, коли для всіх різних значень цільової функ-
ції відповідні характеристичні вектори також є різними. У противному ви-
падку залишається необхідність перебирання тих розв’язків, для яких харак-
теристичні вектори відповідних значень цільової функції є рівними.
Наслідок 3.1 визначає умову відсікання множини у методі гілок і меж
при розв’язанні задачі (10)–(11): якщо для множини Q′ виконується умова
))(())(( xLHQH l ′>′ξ ( x′ — деякий допустимий розв’язок, отриманий на
попередніх ітераціях методу гілок і меж), то множина Q′ надалі не підлягає
галуженню, тобто відсікається.
Таким чином, пропонується така схема методу гілок і меж з викорис-
танням відсікання з наслідку 3.1 для задачі (10)–(11).
1. Розбиваємо множину Q на підмножини
1rQ , що визначені умовою
(12), де }1{=I ,
1rg — різні елементи мультимножини Γ . Далі використову-
ватимемо позначення
irrrQ ...21
для множини, у якій зафіксовані значення
i змінних ixx ,...1 , причому irr ,...,1 — індекси відповідних елементів з муль-
тимножини Γ .
2. Для кожної із множин
1rQ знаходимо характеристичний вектор ве-
личини (13). Для подальшого галуження обираємо множину, для якої відпо-
відний характеристичний вектор передує всім іншим у порядку l≤ (нехай це
множина sQ ).
О.О. Ємець, Т.М. Барболіна
ISSN 1681–6048 System Research & Information Technologies, 2016, № 1 116
3. Розгалужуємо sQ на підмножини
2srQ , для кожної з яких знаходимо
характеристичний вектор величини (13).
4. Продовжуємо процес галуження доти, доки не будуть зафіксовані
значення всіх змінних (тобто не справджуватиметься умова ki = ). Якщо
жодне з отриманих при цьому розміщень не належить до множини S , то
повертаємося на попередній рівень галуження і розгалужуємо наступну
з множин на цьому рівні. Якщо таких множин немає, то повертаємося на ще
один рівень і т.д. У випадку, коли не знайдено допустимого розв’язку і на пер-
шому рівні не залишилося негалужених множин, то задача розв’язку не має.
5. Нехай знайдено допустимий розв’язок hx ( 1=h ), характеристичний
вектор відповідного значення цільової функції .))(()( hh xLHLH =
6. Відкидаємо підмножини
irrrQ ...21
, для яких
.))(()( ...21 irrrl
h QHLH ξ< (14)
7. Продовжуємо галуження множин за вказаним вище правилом. Якщо
для деякої підмножини
irrrQ ...21
виконується умова (14), то ця множина від-
кидається і надалі не розгалужується. Якщо отримано множину
krrrQ ...21
,
тоді:
− перевіряємо, чи належить отримане розміщення множині S ; якщо
ні, то множина відкидається;
− порівнюємо )( ...21 krrrQξ з hL ; якщо hk
rr LQ
k
p)( ...1
ξ , то збільшуємо h
на одиницю і покладаємо )( hh xLL = , де .),...,(
1 krr
h ggx =
8. Процес завершується, коли не залишиться негалужених множин, для
яких характеристичний вектор величини (13) лексикографічно менший за
)( hLH . Тоді розв’язком є пара **),( xxL , де hxx =* .
Приклад. Проілюструємо розглянуті вище правила галуження і відсі-
кання множин у методі гілок і меж при розв’язанні задачі мінімізації функції
3212)( XXXXL ++= на загальній множині розміщень з елементів мульти-
множини ,},,,{ 4321 GGGG=Γ які є дискретними випадковими величинами,
заданими рядами розподілу згідно з таблицею.
Ряди розподілу випадкових величин з наведеного прикладу
Величини 21 GG = 3G 4G
Значення величин 4 9 4 6 9 5 9
Відповідні ймовірності
5
2
5
3
5
1
3
1
15
7
2
1
2
1
Характеристичні вектори елементів мультимножини мають вигляд:
)6;7()( 1 −=GH , .)4;7()()( 43 −== GHGH Таким чином, 31 GG p , 41 GG p .
Ураховуючи також, що перше можливе значення 3G менше від першого
Лінійні оптимізаційні задачі на розміщеннях з імовірнісною невизначеністю: властивості …
Системні дослідження та інформаційні технології, 2016, № 1 117
можливого значення 4G , отримуємо, що 43 GG p . Таким чином,
4321 GGGG pp= .
Розгалужуємо множину )(3
4 ΓE , використовуючи порядок змінних, що
відповідає упорядкуванню 12 321 ==>= ccc , }1{=I . Отже, }2{=BC ,
}1,1{~
=C : }{ 111 GXQ == , }{ 313 GXQ == , .}{ 414 GXQ == Знаходимо відпо-
відні величини (13) та їх характеристичні вектори.
Для }{ 111 GXQ == маємо: }{ 1GB =Γ , .},,{~
432 GGG=Γ У величині (13):
перший доданок 111 2GGcgc
Ij
rj j
==∑
∈
, другий — =⋅+⋅=∑
=
32
1
11~~ GGgc
i
ii
τ
32 GG += , тобто 32111 2)( GGGQ ++=ξ=ξ , +−+−=ξ )6;7()24;14()( 1H
)34;28()4;7( −=−+ . Для }{ 313 GXQ == }{ 3GB =Γ , },,{~
421 GGG=Γ ; додан-
ки у величині (13): 32Ggc
Ij
rj j
=∑
∈
, 21
1
~~ GGgc
i
ii +=∑
=
τ
. Тоді =ξ=ξ )( 32 Q
2132 GGG ++= . )28;28()( 2 −=ξH . Нарешті 21443 2)( GGGQ ++=ξ=ξ ,
)28;28()( 3 −=ξH . Оскільки )()()( 321 ξ=ξ<ξ HHH l , обираємо для галу-
ження підмножину 1Q .
Розгалужуючи 1Q , отримаємо підмножини },{ 221112 GXGXQ === ,
},{ 321113 GXGXQ === , },{ 421114 GXGXQ === . Знаходимо для цих мно-
жин характеристичні вектори величин (13). Для 12Q маємо }2,1{=I ,
}1,2{=BC , }1{~
=C , },{ 21 GGB =Γ , },{~
43 GG=Γ ; доданки у величині (13):
212 GGgc
Ij
rj j
+=∑
∈
, 3
1
~~ Ggc
i
ii =∑
=
τ
, звідки 1321124 2)( ξ=++=ξ=ξ GGGQ .
Аналогічно 1231135 )2()( ξ=++=ξ=ξ GGGQ , 241146 )2()( GGGQ ++=ξ=ξ ,
.)()()( 165 ξ=ξ=ξ HHH
Виберемо для галуження підмножину .},{ 221112 GXGXQ === Отри-
маємо множини, у яких зафіксовані значення усіх змінних:
},,{ 332211123 GXGXGXQ ==== , звідки ),,(),,( 311321
1 GGGGGGX == ,
321123
1 2)( GGGQL ++=ξ= , )34;28()( 1 −=LH ;
},,{ 432211124 GXGXGXQ ==== , тоді 421124 2)( GGGQ ++=ξ
,)())(( 1
124 LHQH =ξ але )( 124
1 QL ξp , оскільки суми 3212 GGG ++
і 4212 GGG ++ відрізняються лише останнім доданком і при цьому 43 GG p .
Оскільки ))(())(( 43
1 QHQHL l ξ=ξ< , то підмножини 3Q і 4Q надалі не
розглядаються. Відкидати підмножини 13Q і 14Q підстав немає, оскільки
)())(())(( 1
1413 LHQHQH =ξ=ξ .
Оберемо для галуження підмножину },{ 321113 GXGXQ === . Діс-
таємо:
О.О. Ємець, Т.М. Барболіна
ISSN 1681–6048 System Research & Information Technologies, 2016, № 1 118
},,{ 233211132 GXGXGXQ ==== , тоді 1
231132 2)( LGGGQ =++=ξ ,
),,( 131
2 GGGX = ;
},,{ 433211134 GXGXGXQ ==== , тоді 431134 2)( GGGQ ++=ξ ,
,)()32;28())(( 1
134 LHQH l>−=ξ звідки також .)( 134
1 QL ξp
Нарешті розгалуження підмножини },{ 421114 GXGXQ === дає такі
результати:
},,{ 234211142 GXGXGXQ ==== , )(2)( 124241142 QGGGQ ξ=++=ξ ,
тобто ;)( 142
1 QL ξp
},,{ 334211143 GXGXGXQ ==== , тоді =++=ξ 341143 2)( GGGQ
,)( 134Qξ= звідки )( 143
1 QL ξp .
Таким чином, мінімумом функції 3212)( XXXXL ++= на множині
)(3
4 ΓE є випадкова величина 311
1 2 GGGL ++= , причому це значення дося-
гається у двох точках: ),,( 311
1 GGGX = та ),,( 131
2 GGGX = .
ВИСНОВКИ
У роботі досліджувалися лінійні оптимізаційні задачі на розміщеннях з імо-
вірнісною невизначеністю, постановку яких виконано на основі введення
відношення порядку на множині дискретних випадкових величин. Установ-
лено властивості розв’язку безумовної задачі, у якій коефіцієнти цільової
функції є дискретними випадковими величинами, а елементи мультимножи-
ни — детермінованими. Запропоновано схему методу гілок і меж для ліній-
них оптимізаційних задач на розміщеннях з імовірнісною невизначеністю,
спосіб галуження та відсікання множин у цій схемі. Як перспективний на-
прям подальших досліджень вбачається удосконалення процедури оціню-
вання множин й обґрунтування інших правил їх відсікання у межах
розв’язання методом гілок і меж таких задач.
ЛІТЕРАТУРА
1. Сергиенко И.В. Модели и методы решения на ЭВМ комбинаторных задач
оптимизации / И.В. Сергиенко, М.Ф. Каспшицкая. — К. : Наук. думка,
1981. —288 с.
2. Згуровский М.З. Принятие решений в сетевых системах с ограниченными
ресурсами / М.З. Згуровский, А.А. Павлов. — К.: Наук. думка, 2010. —573 с.
3. Сергиенко И.В. Классификация прикладных методов комбинаторной
оптимизации / И.В. Сергиенко, Л.Ф. Гуляницкий, С.И. Сиренко //
Кибернетика и системный анализ. — 2009. — № 5. — С. 71–83.
4. Cтоян Ю.Г. Теорія і методи евклідової комбінаторної оптимізації /
Ю.Г. Cтоян, О.О. Ємець. — К.: Ін-т систем. досліджень освіти, 1993. —
188 с. — Режим доступу: http://dspace.puet.edu.ua/handle/123456789/487.
5. Емец О.А. Комбинаторная оптимизация на размещениях / О.А. Емец,
Т.Н. Барболина. — К.: Наук. думка, 2008. — 159 с. — Режим доступу:
http://dspace.puet.edu.ua/handle/123456789/473.
Лінійні оптимізаційні задачі на розміщеннях з імовірнісною невизначеністю: властивості …
Системні дослідження та інформаційні технології, 2016, № 1 119
6. Сергиенко И.В. Применение методов стохастической оптимизации для иссле-
дования трансформационных процессов в экономике / И.В. Сергиенко,
М.В. Михалевич // Системні дослідження та інформаційні технології. —
2004. — № 4. — С. 7–29.
7. Ермольев Ю.М. Стохастические модели и методы в экономическом планирова-
нии / Ю.М. Ермольев, А.И. Ястремский. — М.: Наука. Гл. ред. физико-
матем. лит-ры, 1979. — 256 с.
8. Наумов A.B. Исследование задачи стохастического линейного программирова-
ния с квантильным критерием / A.B. Наумов, C.B. Иванов // Автоматика и
телемеханика. — 2011. — № 2. — С. 142–158.
9. Marti K. Stochastic Optimization Methods.–Springer-Verlag Berlin Heidelberg /
K.Marti. — 2008. — 340 p.
10. Перепелица В.А. Дискретная оптимизация и моделирование в условиях неопре-
деленности даннях / В.А. Перепелица, Ф.Б. Тебуева. — М.: Академия есте-
ствознания. — 2007. — 151 с.
11. Тебуева Ф. Б. Принятие решений в дискретных задачах оптимизации на графах
с нечеткими весами / Ф.Б. Тебуева // Горный информационно-аналитический
бюллетень. — 2008. —№ 6. — С. 373–391.
12. Серая О.В. Нечеткая задача коммивояжера / О.В. Серая // Математическое мо-
делирование. — 2007. — № 2 (17). — С. 13–15.
13. Серая О.В. Стохастическая задача коммивояжера / О.В. Серая, Л.В. Бачкир //
Вестн. Нац. техн. ун-та «Харьковский политехнический институт». Серия:
Информатика и моделирование. — 2006. — № 40. —С. 169–173.
14. Nikolova E. Approximation algorithms for reliable stochastic combinatorial optimi-
zation / E. Nikolova // Approximation, Randomization, and Combinatorial Opti-
mization. Algorithms and Techniques. Springer–Berlin: Heidelberg, 2010. —
P. 338–351.
15. Стоян Ю.Г. Оптимизационная задача размещения правильних интервальных
многоугольников / Ю.Г. Стоян, Т.Е. Романова, Ю.А. Сысоева // Докл. НАН
Украины. — 1998. — № 9. — С. 114–120.
16. Гребенник И.В. Отображение интервальных комбинаторных множеств
в евклидово пространство / И.В. Гребенник, Т.Е. Романова // Проблемы
машиностроения. — 2002. — 5. — № 2. — С. 87–91.
17. Гребенник И.В. Классы интервальных комбинаторных оптимизационных задач
геометрического проектирования / И.В. Гребенник, Т.Е. Романова,
С.Б. Шеховцов // Искусственный интеллект. — 2005. — № 3. — С. 18–24.
18. Ємець О.О. Розв'язування задач комбінаторної оптимізації на нечітких множи-
нах / О.О. Ємець, О.О. Ємець. — Полтава: ПУЕТ, 2011. — 239 с. — Режим
доступу: http://dspace.uccu.org.ua/handle/123456789/352.
19. Сергиенко И.В. Задачи оптимизации с интервальной неопределенностью: ме-
тод ветвей и границ / И.В. Сергиенко, О.А. Емец, А.О. Емец // Кибернетика
и системный анализ. — 2013. — № 5. — С. 38–50.
20. Емец О.А. Об оптимизационных задачах с вероятностной неопределенностью /
О.А. Емец, Т.Н. Барболина // Доп. НАН України. — 2014. — № 11. —
С. 40–45.
21. Ємець О.О. Побудова і дослідження математичної моделі задачі директора зі
стохастичними параметрами / О.О. Ємець, Т.М. Барболіна // Вісн.
Черкаського ун-ту. Серія: Прикладна математика. Інформатика. — 2014. —
№ 18 (311). — С. 3–11.
22. Барболіна Т.М. Розв'язування лінійних безумовних оптимізаційних задач на
розміщеннях з імовірнісною невизначеністю / Т.М. Барболіна, О.О. Ємець //
Матеріали VI Всеукр. наук.-практ. конф. за міжнародною участю
«Інформатика та системні науки» (м. Полтава, 19–21 берез. 2015 р.). —
Режим доступу: http://dspace.puet.edu.ua/handle/123456789/2384.
Надійшла 24.04.2015
|
| id | journaliasakpiua-article-41735 |
| institution | System research and information technologies |
| keywords_txt_mv | keywords |
| language | Ukrainian |
| last_indexed | 2025-07-17T10:18:36Z |
| publishDate | 2016 |
| publisher | The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" |
| record_format | ojs |
| resource_txt_mv | journaliasakpiua/de/3e971a2904a27895f89e19e78d5711de.pdf |
| spelling | journaliasakpiua-article-417352016-07-25T14:59:53Z Linear optimization problems on permutations under probabilistic uncertainty: properties and solution Линейные оптимизационные задачи на размещениях с вероятностной неопределенностью: свойства и решение Лінійні оптимізаційні задачі на разміщеннях з імовірнісною невизначеністю: властивості і розв’язання Iemets, Oleg Oleksiiovych Barbolina, Tetiana Mykolaivna Authors study properties of linear optimization problems under probabilistic uncertainty while defining a problem based on the linear order on the set of discrete random variables. Properties of unconditional problem are established whose coefficients of the goal function or multiset's elements (but not both simultaneously) are discrete random variables. Based on properties of the solution of an unconditional problem with deterministic coefficients, we prove solution's properties for the problem with the goal function's coefficients as discrete random variables. The scheme of the branch and bound method for solving the linear optimization problems on permutations under probabilistic uncertainty is proposed as well as rules of branching and truncation of sets. Исследуются свойства линейных задач оптимизации на размещениях с вероятностной неопределенностью, постановка которых осуществлена на основе введения линейного порядка на множестве дискретных случайных величин. Установлены свойства безусловной задачи, у которой коэффициенты целевой функции или элементы мультимножества (но не то и другое одновременно) являются дискретными случайными величинами. Основываясь на свойствах решения безусловной задачи с детерминированными коэффициентами целевой функции, доказаны свойства решения для задачи, в которой коэффициенты целевой функции являются случайными величинами. Предложена схема метода ветвей и границ для решения линейных задач оптимизации на размещениях с вероятностной неопределенностью, в которой также предложены правила ветвления и отсечения множеств. Досліджено властивості лінійних задач оптимізації на розміщеннях з імовірнісною невизначеністю, постановку яких здійснено на основі введення лінійного порядку на множині дискретних випадкових величин. Установлено властивості безумовної задачі, у якій коефіцієнти цільової функції або елементи мультимножини (але не те й те одночасно) є дискретними випадковими величинами. Ґрунтуючись на властивостях розв’язку безумовної задачі з детермінованими коефіцієнтами цільової функції, доведено властивості розв’язку для задачі, у якій коефіцієнти цільової функції є випадковими величинами. Запропоновано схему методу гілок і меж для розв’язання лінійних задач оптимізації на розміщеннях з імовірнісною невизначеністю, у якій також запропоновано правила галуження та відсікання множин. The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2016-03-18 Article Article application/pdf https://journal.iasa.kpi.ua/article/view/41735 10.20535/SRIT.2308-8893.2016.1.11 System research and information technologies; No. 1 (2016); 107-119 Системные исследования и информационные технологии; № 1 (2016); 107-119 Системні дослідження та інформаційні технології; № 1 (2016); 107-119 2308-8893 1681-6048 uk https://journal.iasa.kpi.ua/article/view/41735/61024 Copyright (c) 2021 System research and information technologies |
| spellingShingle | Iemets, Oleg Oleksiiovych Barbolina, Tetiana Mykolaivna Лінійні оптимізаційні задачі на разміщеннях з імовірнісною невизначеністю: властивості і розв’язання |
| title | Лінійні оптимізаційні задачі на разміщеннях з імовірнісною невизначеністю: властивості і розв’язання |
| title_alt | Linear optimization problems on permutations under probabilistic uncertainty: properties and solution Линейные оптимизационные задачи на размещениях с вероятностной неопределенностью: свойства и решение |
| title_full | Лінійні оптимізаційні задачі на разміщеннях з імовірнісною невизначеністю: властивості і розв’язання |
| title_fullStr | Лінійні оптимізаційні задачі на разміщеннях з імовірнісною невизначеністю: властивості і розв’язання |
| title_full_unstemmed | Лінійні оптимізаційні задачі на разміщеннях з імовірнісною невизначеністю: властивості і розв’язання |
| title_short | Лінійні оптимізаційні задачі на разміщеннях з імовірнісною невизначеністю: властивості і розв’язання |
| title_sort | лінійні оптимізаційні задачі на разміщеннях з імовірнісною невизначеністю: властивості і розв’язання |
| url | https://journal.iasa.kpi.ua/article/view/41735 |
| work_keys_str_mv | AT iemetsolegoleksiiovych linearoptimizationproblemsonpermutationsunderprobabilisticuncertaintypropertiesandsolution AT barbolinatetianamykolaivna linearoptimizationproblemsonpermutationsunderprobabilisticuncertaintypropertiesandsolution AT iemetsolegoleksiiovych linejnyeoptimizacionnyezadačinarazmeŝeniâhsveroâtnostnojneopredelennostʹûsvojstvairešenie AT barbolinatetianamykolaivna linejnyeoptimizacionnyezadačinarazmeŝeniâhsveroâtnostnojneopredelennostʹûsvojstvairešenie AT iemetsolegoleksiiovych líníjníoptimízacíjnízadačínarazmíŝennâhzímovírnísnoûneviznačenístûvlastivostíírozvâzannâ AT barbolinatetianamykolaivna líníjníoptimízacíjnízadačínarazmíŝennâhzímovírnísnoûneviznačenístûvlastivostíírozvâzannâ |