Комбінаторні алгоритми підтримки прийняття управлінських рішень
Наводиться постановка обмеженої та необмеженої задач комбiнаторного розпiзнавання. На прикладi задачi про вимикачi показано, яким способом необхiдно розбити на групи множину вимикачiв, щоб за мiнiмальну кiлькiсть спроб знайти потрiбну кiлькiсть несправних вимикачiв. Розглядається також задача вибор...
Gespeichert in:
| Veröffentlicht in: | Доповіді НАН України |
|---|---|
| Datum: | 2014 |
| Hauptverfasser: | , , |
| Format: | Artikel |
| Sprache: | Ukrainian |
| Veröffentlicht: |
Видавничий дім "Академперіодика" НАН України
2014
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/88546 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Комбінаторні алгоритми підтримки прийняття управлінських рішень / Г.П. Донець, В.А. Пепеляєв, О.М. Трофимчук // Доповiдi Нацiональної академiї наук України. — 2014. — № 11. — С. 33-39. — Бібліогр.: 6 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-88546 |
|---|---|
| record_format |
dspace |
| spelling |
Донець, Г.П. Пепеляєв, В.А. Трофимчук, О.М. 2015-11-16T18:20:13Z 2015-11-16T18:20:13Z 2014 Комбінаторні алгоритми підтримки прийняття управлінських рішень / Г.П. Донець, В.А. Пепеляєв, О.М. Трофимчук // Доповiдi Нацiональної академiї наук України. — 2014. — № 11. — С. 33-39. — Бібліогр.: 6 назв. — укр. 1025-6415 https://nasplib.isofts.kiev.ua/handle/123456789/88546 519.1 Наводиться постановка обмеженої та необмеженої задач комб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 bounded and unbounded combinatorial recognition problems are posed. Using a problem of switches as an example, we show how to divide the subset of switches into groups so that the given number of faulty switches could be found by minimal number of tests. We also consider the problem of choosing the number of elements of the same type from two given sets. For every problem, we give the evaluating formulas for the minimal number of tests. uk Видавничий дім "Академперіодика" НАН України Доповіді НАН України Інформатика та кібернетика Комбінаторні алгоритми підтримки прийняття управлінських рішень Комбинаторные алгоритмы поддержки принятия управленческих решений Combinatorial algorithms making support of managerial decisions Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Комбінаторні алгоритми підтримки прийняття управлінських рішень |
| spellingShingle |
Комбінаторні алгоритми підтримки прийняття управлінських рішень Донець, Г.П. Пепеляєв, В.А. Трофимчук, О.М. Інформатика та кібернетика |
| title_short |
Комбінаторні алгоритми підтримки прийняття управлінських рішень |
| title_full |
Комбінаторні алгоритми підтримки прийняття управлінських рішень |
| title_fullStr |
Комбінаторні алгоритми підтримки прийняття управлінських рішень |
| title_full_unstemmed |
Комбінаторні алгоритми підтримки прийняття управлінських рішень |
| title_sort |
комбінаторні алгоритми підтримки прийняття управлінських рішень |
| author |
Донець, Г.П. Пепеляєв, В.А. Трофимчук, О.М. |
| author_facet |
Донець, Г.П. Пепеляєв, В.А. Трофимчук, О.М. |
| topic |
Інформатика та кібернетика |
| topic_facet |
Інформатика та кібернетика |
| publishDate |
2014 |
| language |
Ukrainian |
| container_title |
Доповіді НАН України |
| publisher |
Видавничий дім "Академперіодика" НАН України |
| format |
Article |
| title_alt |
Комбинаторные алгоритмы поддержки принятия управленческих решений Combinatorial algorithms making support of managerial decisions |
| 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 спроб.
Приводится постановка ограниченной и неограниченной задач комбинаторного распознавания. На примере задачи о выключателях показано, каким способом необходимо разбить на
группы множество выключателей, чтобы за минимальное число проб найти нужное количество неисправных выключателей. Рассматривается также задача выбора количества
однотипных элементов из двух заданных множеств. Для каждой задачи приводятся формулы оценок минимального числа проб.
The bounded and unbounded combinatorial recognition problems are posed. Using a problem of
switches as an example, we show how to divide the subset of switches into groups so that the given
number of faulty switches could be found by minimal number of tests. We also consider the problem
of choosing the number of elements of the same type from two given sets. For every problem, we
give the evaluating formulas for the minimal number of tests.
|
| issn |
1025-6415 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/88546 |
| citation_txt |
Комбінаторні алгоритми підтримки прийняття управлінських рішень / Г.П. Донець, В.А. Пепеляєв, О.М. Трофимчук // Доповiдi Нацiональної академiї наук України. — 2014. — № 11. — С. 33-39. — Бібліогр.: 6 назв. — укр. |
| work_keys_str_mv |
AT donecʹgp kombínatorníalgoritmipídtrimkipriinâttâupravlínsʹkihríšenʹ AT pepelâêvva kombínatorníalgoritmipídtrimkipriinâttâupravlínsʹkihríšenʹ AT trofimčukom kombínatorníalgoritmipídtrimkipriinâttâupravlínsʹkihríšenʹ AT donecʹgp kombinatornyealgoritmypodderžkiprinâtiâupravlenčeskihrešenii AT pepelâêvva kombinatornyealgoritmypodderžkiprinâtiâupravlenčeskihrešenii AT trofimčukom kombinatornyealgoritmypodderžkiprinâtiâupravlenčeskihrešenii AT donecʹgp combinatorialalgorithmsmakingsupportofmanagerialdecisions AT pepelâêvva combinatorialalgorithmsmakingsupportofmanagerialdecisions AT trofimčukom combinatorialalgorithmsmakingsupportofmanagerialdecisions |
| first_indexed |
2025-11-26T02:45:40Z |
| last_indexed |
2025-11-26T02:45:40Z |
| _version_ |
1850609239080304640 |
| fulltext |
УДК 519.1
Г.П. Донець, В. А. Пепеляєв,
член-кореспондент НАН України О.М. Трофимчук
Комб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–6]. При цьому iнколи кiлькiсть альтернатив настiльки велика, що
виникає загроза комбiнаторного вибуху. Це вимагає вироблення правил, якi звужують пов-
ний перебiр варiантiв, або розробки спецiальних методiв оптимiзацiї перебору. Розглянемо
типову задачу, яка може мати широку iнтерпретацiю.
Задача 1. Нехай в наявностi є n альтернатив прийняття економiчних рiшень
A={A1, A2, . . . , An}, про якi тiльки вiдомо, що серед них є m прийнятних. Iснує механiзм,
який для фiксованого k (k 6 m) дозволяє визначити, чи iснує серед альтернатив довiльної
k-вибiрки хоча б одна неприйнятна. Необхiдно за мiнiмальну кiлькiсть k-вибiрок знайти k
прийнятних альтернатив.
Поняття механiзму, що дозволяє отримати вiдповiдь на експеримент, можна трактувати
в самому широкому розумiннi слова. Наведемо кiлька прикладiв.
Приклад 1. Нехай n вимикачiв приєднанi до однiєї лампочки. Вiдомо, що серед них m
зiпсованi. Експеримент полягає в одночасному вмиканнi k вимикачiв. Якщо серед них є хо-
ча б один справний, то лампочка засвiчується. Необхiдно за мiнiмальну кiлькiсть спроб
знайти k несправних вимикачiв.
Велику кiлькiсть задач про монети, серед яких є фальшивi, можна звести до задачi 1,
при цьому вiдповiддю на рiзнi експерименти є результат зважування на двох терезах певних
комбiнацiй монет.
Приклад 2. Задача про лотерею. Задано множину натуральних чисел Nn =
= {1, 2, . . . , n}. Випадково вибирається пiдмножина виграшних чисел M = {i1, i2, . . . , im}.
Експеримент полягає в виборi k чисел iз Nn. Необхiдно вибрати мiнiмальну кiлькiсть таких
k-вибiрок, щоб хоча одна з них належала M .
Приклад 1 допоможе нам сформулювати задачу 1 у новiй математичнiй постановцi.
Задача 1′. Задано множину n чисел X = {x1, x2, . . . , xn} з m одиниць та n −m нулiв.
Експеримент полягає у виборi фiксованої кiлькостi k (k 6 m) чисел, пiсля чого стає вiдомим
їх добуток. Необхiдно за мiнiмальну кiлькiсть спроб знайти k чисел, якi дорiвнюють 1.
© Г.П. Донець, В.А. Пепеляєв, О.М. Трофимчук, 2014
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2014, №11 33
Позначимо цю мiнiмальну кiлькiсть F km(n). В подальшому будемо розглядати задачу 1
тiльки в такiй постановцi, як задачу 1′. Розглянемо приклад 1 для таких значень: n = 9,
m = 4, k = 2.
Найпростiшим розв’язком є такий: пробуємо всi комбiнацiї з двох вимикачiв, поки не
натрапимо на два зiпсованих — i тодi лампочка не засвiтиться. Всього таких комбiнацiй
C2
9 = 36, серед них C2
4 = 6 комбiнацiй iз зiпсованими вимикачами. Отже в найгiршому
випадку через 31 спробу ми розв’яжемо задачу. Бiльш вдалий розв’язок отримаємо, коли 9
вимикачiв розiб’ємо на двi групи (5 + 4). Тодi в якiйсь групi буде не менше двох зiпсова-
них вимикачiв i, комбiнуючи по два вимикачi у кожнiй групi, одержуємо розв’язок задачi.
Щоб отримати оцiнку кiлькостi спроб, необхiдно розглянути всi варiанти розбиття чоти-
рьох зiпсованих вимикачiв на двi групи. Якщо в групi з p вимикачiв q зiпсованих (q > 2),
то кiлькiсть спроб дорiвнює C2
p −C2
q +1. Тодi серед розбиттiв (0,4), (1,3), (2,2), (3,1) та (4,0)
найгiрший випадок (1,3), або (3,1) дає 14 спроб. Можна розбити 9 вимикачiв на чотири
групи (3 + 2 + 2 + 2). Спочатку зробимо C2
3 + C2
2 + C2
2 + C2
2 = 6 спроб. Якщо лампочка
засвiтиться кожний раз, то це може бути тiльки тодi, коли в кожнiй групi буде по одному
зiпсованому вимикачу.
Беремо двi групи по 2 вимикача i комбiнуємо з них 2, по одному з кожної групи. Це
вимагає 4 спроби, а в сумi розв’язок отримаємо за 10 спроб. Але iснує ще один розв’язок,
коли 9 вимикачiв розбиваємо на три групи (3 + 3 + 3). Тодi обов’язково знайдеться група,
в якiй не менш двох зiпсованих вимикачiв. Кiлькiсть спроб тепер становить C2
3+C
2
3+C
2
3 = 9,
що i буде оптимальним розв’язком, iншими словами, F 2
4 (9) = 9.
Розглянемо ще одну задачу, яка тiсно пов’язана з задачею 1, у математичнiй постановцi.
Задача 2. Задано множину n чисел X = {x1, x2, . . . , xn} з m одиниць та n −m нулiв.
Експеримент полягає у виборi фiксованої кiлькостi k (k 6 m) чисел, пiсля чого стає вiдомим
їх добуток. Необхiдно за мiнiмальну кiлькiсть спроб знайти значення заданого xi (1 6 i 6
6 n).
Позначимо таку кiлькiсть Ckm(n). Покажемо, що ця задача не має самостiйного значення
вiдносно задачi 1. Дiйсно, якщо включати xi в кожну комбiнацiю з k чисел, то розв’язок
ми отримаємо тiльки тодi, коли будемо певнi, що iншi k − 1 чисел складаються з одиниць.
Тодi добуток всiх k чисел дорiвнює xi. Таким чином, ця задача зводиться до задачi 1,
якщо з множини X видалити xi i комбiнувати в нiй по k − 1 чисел. Найгiрший випадок
буде тодi, коли xi = 1, тобто в множинi X залишиться m − 1 одиниць. Це означає, що
Ckm(n) = F k−1
m−1(n − 1), звiдси i видно, що достатньо вивчати розв’язки тiльки задачi 1,
тобто функцiю F km(n). Очевидно, що Fmm (n) = Cmn , тому що набiр з одиниць єдиний i для
його знаходження в найгiршому випадку потрiбно перебрати всi комбiнацiї. Для k = 2 вже
є досвiд розв’язування задачi. При цьому був знайдений принцип, за яким, краще всього,
потрiбно розбивати всю множину чисел на групи.
Принцип оптимальностi. Для k = 2 необхiдно всю множину чисел розбити на стiльки
груп, щоб хоча в однiй з них було не менше двох одиниць. Звiдси випливає, що число груп
повинно бути m − 1.
Позначимо λ ≡ n (modm − 1).
Лема 1.
F 2
3 (n) =
n(n− 2) + λ
4
. (1)
Нехай λ ≡ n ≡ 0 (mod 2). Тодi n розбивається на двi однаковi групи з n/2 чисел, i
34 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2014, №11
F 2
3 (n) = C2
n/2 + C2
n/2 = 2 ·
n
2
(
n
2
− 1
)
2
=
n(n− 2)
4
.
Якщо λ ≡ 1 (mod 2), то n розбивається на два рiзних числа (n+1)/2 та (n−1)/2. Тодi
F 2
3 (n) = C2
n+1
2
+ C2
n−1
2
=
1
2
(
n+ 1
2
n− 1
2
+
n− 1
2
n− 3
2
)
=
(
n− 1
2
)2
.
Можна записати загальну формулу
F 2
3 (n) =
(n− λ)(n− 2 + λ)
4
=
n(n− 2) + 2λ− λ2
4
.
Враховуючи те, що λ2 ≡ λ (mod 2), отримаємо формулу (1).
Лема 2. При подiлу n на m − 1 груп отримаємо розбиття:
n = (m− 1− λ)
(
n− λ
m− 1
)
+ λ
(
n− λ
m− 1
+ 1
)
. (2)
При дiленнi числа n на q отримаємо залишок n (mod q).
Отже, n = q
⌊
n
q
⌋
+ n (mod q). Запишемо q = [q − n (mod q)] + n (mod q), звiдки
n = [q − n (mod q)]
⌊
n
q
⌋
+ n (mod q)
(⌊
n
q
⌋
+ 1
)
.
Пiдставляючи сюди q = m− 1 та
⌊
n
m− 1
⌋
=
n− λ
m− 1
, одержуємо шукану формулу (2).
Звiдси легко вивести загальну формулу
n =
q−1∑
i=0
⌊
n+ i
q
⌋
. (3)
Теорема 1.
F 2
m(n) =
(n− λ)(n+ λ−m+ 1)
2(m− 1)
. (4)
Скористаємося результатами леми 2 при розбиттi множини чисел на m− 1 груп
F 2
m(n) = (m− 1− λ)C2
n−λ
m−1
+ λC2
n−λ
2
+1
=
=
m− 1− λ
2
(
n−λ
m−1
)(
n− λ
m− 1
− 1
)
+
λ
2
(
n− λ
m− λ
+ 1
)(
n− λ
m− 1
)
.
Пiсля скорочень отримаємо формулу (4).
Теорема 2.
F 3
2r+1(n) =
1
6r2
(n− λ)(n− λ− r)(n− 2r + 2λ) (r > 1). (5)
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2014, №11 35
Для k = 3 будемо знаходити отриманий розв’язок, користуючись принципом оптималь-
ностi. Потрiбно розбити n на r приблизно рiвних груп, тодi хоча б в однiй з них буде
не менше трьох одиниць. При цьому необхiдно, щоб кожна група мала об’єм, не менший
трьох. Тому з (3) випливає
F 3
2r+1(n) =
r−1∑
i=0
C3
⌊n+i
r ⌋. (6)
Якщо скористатися параметром λ ≡ n (mod r), то групи будуть складатися з r−λ чисел
по (n − λ)/r i λ чисел по (n − λ)/r + 1. Тому
F 3
2r+1(n) = (r − λ)C3
n−λ
r
+ λC3
n−λ
r
+1
=
(
r − λ
6
)(
n− λ
r
)(
n− λ
r
− 1
)(
n− λ
r
− 2
)
+
+
λ
6
(
n− λ
r
+ 1
)(
n− λ
r
)(
n− λ
r
− 1
)
. (7)
Спрощуючи цей вираз, одержимо формулу (6).
Приклад 3. Нехай n = 73, m = 11. Тодi r = 5, а λ = 3.
За формулою (7) при розбиттi числа 73 на 5 груп (14, 14, 15, 15, 15) отримаємо
F 3
11(73) = 2C3
15 + 3C3
14 = 2 · 364 + 3 · 455 = 2093,
а за формулою (5) — вiдповiдно
F 3
11(73) =
1
6 · 25
(73− 3)(73− 3− 5)(73− 10 + 6) =
70 · 65 · 69
150
= 2093.
Задача 1 може породити бiльш складну задачу, яка яка буде використана в подальших
дослiдженнях.
Задача 3. Задано множини чисел X = {x1, x2, . . . , xn1} та Y = {y1, y2, . . . , yn2}, причому
в першiй множинi мiститься m1 одиниць (m1 6 n1), а в другiй — m2 одиниць (m2 6 n2).
Експеримент полягає у виборi k (k > 1) чисел з будь-яких множин (k 6 m1 + m2), пiсля
чого стає вiдомим їх добуток. Необхiдно за мiнiмальну кiлькiсть спроб знайти k чисел, якi
дорiвнюють 1.
Позначимо цю кiлькiсть F km1,m2
(n1, n2). У загальному виглядi цю задачу ще не розв’я-
зано. Розглянемо її частинний випадок для k = 3, m1 = m2 = 2. Нам необхiдно знайти
F 3
2,2(n1, n2). Очевидно, що всi комбiнацiї по три повиннi складатися з чисел iз рiзних мно-
жин: одне число з однiєї множини, а два — з другої. Ми можемо перебрати в однiй множинi
всi комбiнацiї по два числа i по черзi приєднувати числа з другої множини. Зрештою ми
натрапимо на одну комбiнацiю з двох одиниць, а в другiй натрапимо на одиницю пiсля
n2 − 1 спроб. Це дає оцiнку F 3
2,2(n1, n2) 6 C2
n1
(n2 − 1). Очевидно, що комбiнувати по два
числа треба в множинi з меншою кiлькiстю чисел, оскiльки з n2 > n1 випливає
C2
n2
(n1 − 1) > C2
n1
(n2 − 1).
Але така стратегiя в загальному виглядi не є оптимальною. Оптимальною є покрокова
стратегiя.
36 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2014, №11
1. Якщо n2 > n1, то беремо всi комбiнацiї по два елементи з множини X i один з множи-
ни Y , наприклад, y1. Якщо добуток трьох чисел хоч один раз дорiвнюватиме 1, то задача
розв’язана, в противному разi — y1 = 0. Вилучаємо y1 з множини Y , тепер її об’єм дорiв-
нює n2 − 1.
2. Нехай s = min(n1, n2). За |n2 − n1|C2
s спроб ми досягнемо ситуацiї, коли об’єм бiль-
шої зменшиться до рiвня меншої, i необхiдно знайти F 3
2,2(s, s). Тепер ситуацiя симетрична
i можна комбiнувати в будь-якiй множинi. За C2
s спроб ми перейдемо до ситуацiї з об’ємами
множин (s, s − 1). Тепер, комбiнуючи по два у меншiй множинi, за C2
s−1 спроб перейдемо
до ситуацiї з об’ємами множин (s − 1, s − 1).
3. На i-му кроцi (3 6 i 6 s) за допомогою C2
i + C2
i−1 спроб ми переходимо до об’ємiв
множин (i − 1, i − 1). Якщо добуток трьох чисел в будь-який момент дорiвнюватиме 1, то
задача розв’язана, iнакше продовжуємо спроби.
4. У найгiршому випадку зрештою дiйдемо до ситуацiї, коли залишаться двi множини
X1 = Y1 = (1, 1). Тепер можна брати довiльнi 3 елементи з них, якi є розв’язком задачi.
Пiдрахуємо кiлькiсть спроб для найгiршого випадку, починаючи з об’ємiв множин (s, s),
(C2
s + C2
s−1) + (C2
s−1 + C2
s−2) + . . .+ (C2
3 + C2
2 ) = C2
s + 2
s−1∑
i=3
C2
i + C2
2 = C2
s + 2C3
s − 1.
Тим самим доведена
Теорема 3.
F 3
2,2(n1, n2) = (|n2 − n1| − 1)C2
s + 2C3
s − 1, (8)
де s = min(n1, n2).
Зокрема,
F 3
2,2(s, s) =
s(s− 1)(2s− 1)
6
− 1. (9)
Тепер розглянемо задачу для випадку, коли m = 2r, тобто необхiдно знайти F 3
2r(n).
Можливi двi стратегiї: розбивати n на r груп, або на r − 1 груп.
Розглянемо першу стратегiю, яку оцiнимо як F1. Позначимо
⌊n
r
⌋
= α, λ1 ≡ n (mod r) =
= n − αr. Тодi число n розбивається на r − λ1 груп по α чисел в кожнiй та λ1 груп по
α + 1 чисел в кожнiй. По (7) необхiдно зробити (r − λ1)C
3
α + λ1C
3
α+1 спроб. У найгiршому
випадку цього не досить, оскiльки може виникнути ситуацiя, коли кожна група має рiвно
по двi одиницi. Тодi слiд скористатися формулою (8) i зробити ще F 3
2,2(α, α) спроб, якщо
λ ̸= r − 1, або F 3
2,2(α, α + 1) для λ = r − 1. Разом це дає
F1 = (r − λ1)
α(α− 1)(α− 2)
6
+ λ1
α(α− 1)(α− 2)
6
+
α(α− 1)
2
[2− sgn(r − 1− λ1)] +
+
α(α− 1)(α− 2)
6
− 1.
Пiсля перетворень отримаємо
F1 =
α(α− 1)
6
[rα− 2r + 3λ1 + 2α− 3 sgn(r − 1− λ1) + 2].
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2014, №11 37
Тепер пiдставимо вираз для λ1 i остаточно маємо
F1 =
α(α− 1)
6
[3(n− sgn(r − 1− λ1))− 2(α+ 1)(r − 1)]− 1. (10)
Оцiнимо другу стратегiю як F2. Позначимо⌊
n
r − 1
⌋
= β, λ2 ≡ n (mod r − 1) = n− (r − 1)β.
Тодi число n розбивається на r − 1 − λ2 груп по β чисел у кожнiй та λ2 груп по β +
+ 1 чисел у кожнiй. Але, на вiдмiну вiд першої стратегiї, тут, якщо пiсля перевiрки r − 2
груп не досягнемо розв’язку, то це означає, що в (r − 1)-й групi знаходяться не менше
чотирьох одиниць. Якщо в цiй групi чотири числа, то всi вони дорiвнюють одиницi, тобто
для розв’язку достатньо з цiєї групи взяти будь-якi три одиницi. Якщо група мiстить бiльше
чотирьох чисел, то потрiбно розбити її на двi частини. Залежно вiд величини останньої
групи отримаємо двi оцiнки другої стратегiї. Якщо λ2 = 0, то всi групи мають по β чисел,
в противному разi остання група має β + 1 чисел. Це означає, що
F2 = (r − 1− λ2)C
3
β + (λ2 − 1)C3
β+1 + F 3
4 (β + 1) для λ2 > 0; (11)
F2 = (r − 2)C3
β+ F 3
4 (β) для λ2 = 0. (12)
Розбиваючи останню групу на двi, можемо скористатися формулами (3) та (8). В першо-
му випадку одержуємо розбиття групи на двi компоненти
(⌊
β + 1
2
⌋
, β+1−
⌊
β + 1
2
⌋)
, в дру-
гому випадку, враховуючи формулу (3), на такi:
(⌊
β
2
⌋
, β −
⌊
β
2
⌋)
=
(
β −
⌊
β + 1
2
⌋
,
⌊
β
2
⌋)
.
Позначимо
⌊
β + 1
2
⌋
= γ. Для перевiрки необхiдно зробити в першому випадку C3
γ +C
3
β+1−γ
спроб, а в найгiршому — ще F 3
2,2(γ, β+1− γ). Враховуючи вираз для λ2, пiсля перетворень
першої формули отримаємо остаточний вигляд
F2 =
β(β − 1)
6
[3n− (β + 1)(2r − 1) + C3
⌊β
2 ⌋+1
+
⌊
β
2
⌋
C2
⌊β+1
2 ⌋ − 1 для λ2 > 0. (13)
Для другого випадку потрiбно спочатку зробити C3
β−γ+C
3
γ перевiрок, а потiм ще F 3
2,2(β−
− γ, γ) спроб. В результатi перетворень остаточно отримаємо
F2 =
β(β − 1)(β − 2)
6
(r − 2) + C3
⌊β+1
2 ⌋ +
⌊
β − 1
2
⌋
C2
⌊β+1
2 ⌋ − 1 для λ2 = 0. (14)
Оцiнити, яка стратегiя з двох краща, поки що не вдалося. На чисельних експериментах
залежно вiд рiзних значень r та n висновок про перевагу будь-якої з них неоднозначний.
Для k > 3 виведення формул ускладнюється, а кiлькiсть стратегiй збiльшується.
Отже можна сказати, що для ситуацiй, в яких необхiдно розпiзнавати рiзну структуру
множин, започатковано пiдхiд, який за допомогою набору формул дозволяє чiтко визначити
вiдповiдну ситуацiю. Цей пiдхiд передбачає подальше удосконалення.
1. Довгий С.О., Бiдюк П. I., Трофимчук О.М., Савенков О. I. Методи прогнозування в системах пiд-
тримки прийняття рiшень. – Київ: Азимут, 2011. – 608 с.
38 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2014, №11
2. Бiдюк П. I., Трофимчук О.М., Федоров Д.В. Iнформацiйна система пiдтримки прийняття рiшень
для прогнозування фiнансово-економiчних процесiв на основi структурно-параметричної адаптацiї
моделей // Наук. вiстi НТУУ “КПI”. – 2011. – № 6. – С. 42–53.
3. Пепеляєв В.А., Кнопов П.С., Атоєв К.Л. та iн. Iнформацiйно-аналiтична система для аналiзу
комплексних ризикiв природно-техногенних та соцiально-економiчних загроз в галузi житлово-кому-
нального господарства України // Наука та iнновацiї. – 2010. – № 3. – С. 39–46.
4. Атоев К.Л., Пепеляев В.А. Информационная система для поддержки принятия решений при прове-
дении реформ в сфере жилищно-коммунального хозяйства // Компьют. математика. – 2010. – № 2. –
С. 32–41.
5. Голодникова Н.А., Левашко Т.П., Пепеляев В.А. Метод поиска оптимальных планов проведения
выборочного обследования // Там же. – 2010. – № 2. – С. 42–51.
6. Пепеляев В.А., Атоев К.Л. Ранжирование регионов Украины по уровням социально-экономических
и природно-техногенных угроз // Материалы 18-й междунар. конф. “Проблемы принятия решений
в условиях неопределенности (PDMU – 2011)”. – Ялта, 19–23 сентября. – 2011. – С. 139–140.
Надiйшло до редакцiї 07.07.2014Iнститут кiбернетики iм. В.М. Глушкова
НАН України, Київ
Iнститут телекомунiкацiй та глобального
iнформацiйного простору НАН України, Київ
Г.А. Донец, В.А. Пепеляев,
член-корреспондент НАН Украины А.Н. Трофимчук
Комбинаторные алгоритмы поддержки принятия управленческих
решений
Приводится постановка ограниченной и неограниченной задач комбинаторного распознава-
ния. На примере задачи о выключателях показано, каким способом необходимо разбить на
группы множество выключателей, чтобы за минимальное число проб найти нужное ко-
личество неисправных выключателей. Рассматривается также задача выбора количества
однотипных элементов из двух заданных множеств. Для каждой задачи приводятся фор-
мулы оценок минимального числа проб.
G.A. Donets, V.A. Pepelyaev,
Corresponding Member of the NAS Ukraine O.M. Trofymchuk
Combinatorial algorithms making support of managerial decisions
The bounded and unbounded combinatorial recognition problems are posed. Using a problem of
switches as an example, we show how to divide the subset of switches into groups so that the given
number of faulty switches could be found by minimal number of tests. We also consider the problem
of choosing the number of elements of the same type from two given sets. For every problem, we
give the evaluating formulas for the minimal number of tests.
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2014, №11 39
|