Алгоритм розв’язування задачі про оптимальні призначення методом гілок та меж
Наведено нову (комбінаторну) модель задачі про призначення. Досліджено особливості використання методу гілок та меж для розв’язування задачі про призначення. Поліпшено оцінку допустимих множин у методі гілок та меж; розроблено алгоритм розв’язування задачі та проілюстровано його на прикладі....
Збережено в:
| Дата: | 2013 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Ukrainian |
| Опубліковано: |
Інститут проблем штучного інтелекту МОН України та НАН України
2013
|
| Назва видання: | Искусственный интеллект |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/85163 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Алгоритм розв’язування задачі про оптимальні призначення методом гілок та меж / М.В. Леонова // Искусственный интеллект. — 2013. — № 2. — С. 14–20. — Бібліогр.: 6 назв. — укр. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-85163 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-851632015-07-22T03:02:23Z Алгоритм розв’язування задачі про оптимальні призначення методом гілок та меж Леонова, М.В. Наведено нову (комбінаторну) модель задачі про призначення. Досліджено особливості використання методу гілок та меж для розв’язування задачі про призначення. Поліпшено оцінку допустимих множин у методі гілок та меж; розроблено алгоритм розв’язування задачі та проілюстровано його на прикладі. Показана полная (комбинаторная) модель задачи о назначениях. Исследованы особенности использования метода ветвей и границ для решения задачи о назначениях. Улучшена оценка допустимых множеств в методе ветвей и границ; разработан и проиллюстрирован алгоритм решения задачи на примере. A new (combinatorial) model assignment problem. The features of the method branch and bound for solving the assignment problem. Improved assessment of admissible sets in branch and bound, the algorithm for solving the problem and illustrate it with an example. 2013 Article Алгоритм розв’язування задачі про оптимальні призначення методом гілок та меж / М.В. Леонова // Искусственный интеллект. — 2013. — № 2. — С. 14–20. — Бібліогр.: 6 назв. — укр. 1561-5359 http://dspace.nbuv.gov.ua/handle/123456789/85163 519.85 uk Искусственный интеллект Інститут проблем штучного інтелекту МОН України та НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Ukrainian |
| description |
Наведено нову (комбінаторну) модель задачі про призначення. Досліджено особливості використання
методу гілок та меж для розв’язування задачі про призначення. Поліпшено оцінку допустимих множин у
методі гілок та меж; розроблено алгоритм розв’язування задачі та проілюстровано його на прикладі. |
| format |
Article |
| author |
Леонова, М.В. |
| spellingShingle |
Леонова, М.В. Алгоритм розв’язування задачі про оптимальні призначення методом гілок та меж Искусственный интеллект |
| author_facet |
Леонова, М.В. |
| author_sort |
Леонова, М.В. |
| title |
Алгоритм розв’язування задачі про оптимальні призначення методом гілок та меж |
| title_short |
Алгоритм розв’язування задачі про оптимальні призначення методом гілок та меж |
| title_full |
Алгоритм розв’язування задачі про оптимальні призначення методом гілок та меж |
| title_fullStr |
Алгоритм розв’язування задачі про оптимальні призначення методом гілок та меж |
| title_full_unstemmed |
Алгоритм розв’язування задачі про оптимальні призначення методом гілок та меж |
| title_sort |
алгоритм розв’язування задачі про оптимальні призначення методом гілок та меж |
| publisher |
Інститут проблем штучного інтелекту МОН України та НАН України |
| publishDate |
2013 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/85163 |
| citation_txt |
Алгоритм розв’язування задачі про оптимальні призначення методом гілок та меж / М.В. Леонова // Искусственный интеллект. — 2013. — № 2. — С. 14–20. — Бібліогр.: 6 назв. — укр. |
| series |
Искусственный интеллект |
| work_keys_str_mv |
AT leonovamv algoritmrozvâzuvannâzadačíprooptimalʹnípriznačennâmetodomgíloktamež |
| first_indexed |
2025-07-06T12:19:31Z |
| last_indexed |
2025-07-06T12:19:31Z |
| _version_ |
1836900021603139584 |
| fulltext |
ISSN 1561-5359 «Искусственный интеллект» 2013 № 2 14
1Л
УДК 519.85
М.В. Леонова
Полтавський національний педагогічний університет імені В.Г. Короленка
Україна, 36000, м. Полтава, вул. Остроградського, 3
Алгоритм розв’язування задачі
про оптимальні призначення методом гілок та меж
M.V. Leonova
Poltava V.G. Korolenko National Pedagogical University
Ukraine, 36000, c. Poltava, Ostrogradsky st., 3
Algorithm Solving the Problem of Optimal Function
by Method of Branch and Bound
М.В. Леонова
Полтавский национальный педагогический университет имени В.Г. Короленка
Украина, 36000, г. Полтава, ул. Остроградского, 3
Алгоритм решения задачи
об оптимальных назначениях методом границ и ветвей
Наведено нову (комбінаторну) модель задачі про призначення. Досліджено особливості використання
методу гілок та меж для розв’язування задачі про призначення. Поліпшено оцінку допустимих множин у
методі гілок та меж; розроблено алгоритм розв’язування задачі та проілюстровано його на прикладі.
Ключові слова: метод гілок та меж, задача про призначення, оцінювання підмножин,
оптимізація на перестановках.
A new (combinatorial) model assignment problem. The features of the method branch and bound for solving
the assignment problem. Improved assessment of admissible sets in branch and bound, the algorithm for
solving the problem and illustrate it with an example.
Key words: method branch and bound, the task of appointment, evaluation of subsets, optimization
on permutations.
Показана полная (комбинаторная) модель задачи о назначениях. Исследованы особенности использования
метода ветвей и границ для решения задачи о назначениях. Улучшена оценка допустимых множеств в
методе ветвей и границ; разработан и проиллюстрирован алгоритм решения задачи на примере.
Ключевые слова: метод ветвей и границ, задача о назначениях, оценка подмножеств,
оптимизация на перестановках.
Вступ
Задача про призначення – одна з класичних задач цілочислової оптимізації [1].
Її суть полягає в тому, що є n видів робіт та n кандидатів для їх виконання (виконавців).
Вважається, що кожен з кандидатів { }1,...,
n
i J n∈ = може виконувати будь-яку
роботу { }1,...,
n
j J n∈ = , при цьому
ij
c – ефективність виконаної роботи j-го виду і-м
кандидатом.
Необхідно так розподілити кандидатів на виконання робіт, щоб кожен з канди-
датів одержав єдине призначення, кожна з робіт одержала єдиного виконавця і су-
марна ефективність, пов’язана з призначеннями, була максимальною.
Алгоритм розв’язування задачі про оптимальні призначення методом гілок та меж
«Штучний інтелект» 2013 № 2 15
1Л
Мета даної статті – розробити нову (комбінаторну) модель задачі про призна-
чення.
Розробка алгоритму за методом гілок та меж є досить актуальною для задач
такого типу, оскільки дає можливість використання його у розв’язуванні більш склад-
них задач (наприклад, задача теорії розкладів) [2].
Побудуємо нову модель задачі в рамках евклідової комбінаторної оптимізації [3-5].
Введемо змінні:
1, ;
0, .
ij
якщо i та робота виконана j м виконавцем
x
в іншому випадку
− −
=
Цільова функція має вигляд
( ) max
1 1
→=∑∑
= =
n
i
n
j
ijij
xcxF . (1)
Повинні виконуватись такі умови:
– на кожну роботу призначається тільки на один виконавець
1
1
n
ij n
i
x j J
=
= ∀ ∈∑ ; (2)
– кожен виконавець призначається тільки на одну роботу
1
1
n
ij n
j
x i I
=
= ∀ ∈∑ . (3)
– { }0;1
ij
x ∈ .
Зауважимо, що остання умова може бути записана комбінаторно.
Розглянемо мультимножину { }
2
0 ,1
n n n
G
−
= з основою ( ) ( )0,1S G = та первин-
ною специфікацією [ ] ( )2
;G n n n= − .
Тоді допустимий розв’язок задачі про призначення є впорядкованою k-вибіркою з
множини G, де 2
k n= , тобто елементом загальної множини переставлень ( ),2k
E G :
( ) ( )11 1 1 ,2
,..., ,..., ,..., .
n n nn k
x x x x x E G∈ ∈ (4)
Задача (1) – (4) є моделлю задачі про призначення як лінійної умовної повністю
комбінаторної задачі на перестановках [2].
Оцінювання допустимих підмножин
в методі гілок та меж
Моделі задач типу задачі про призначення, але з додатковими умовами (задачі
теорії розкладів [2], є актуальними, але до них не можна застосовувати поліноміальні
алгоритми (угорський метод [6]) тощо). Тому вбачається для таких задач (почавши з
задачі про призначення) дослідити алгоритм у класі методу гілок та меж [4-6].
Метод гілок та меж (МГМ) – універсальний метод, який можна застосувати до
будь-якої оптимізаційної задачі. У випадку задачі про призначення з матрицею
ефективності ( )ij
C c= будемо використовувати модель (1) – (4) цієї задачі у вигляді
лінійної умовної задачі комбінаторної оптимізації на переставленнях.
У подальшому будемо вважати, що елементи G впорядковані по незростанню:
1
...
k
g g≥ ≥ , (5)
тобто
1 2 1 2
... 1; ... 0.
n n n k
g g g g g g
+ +
= = = = = = = =
Леонова М.В.
«Искусственный интеллект» 2013 № 2 16
1Л
Суттєвим для ефективності МГМ є оцінювання допустимих підмножин.
Як відомо [4-6], в задачі максимізації на множині D функції ( )F x , оцінка для
підмножини
l
D D⊂ – це число ( )l l
F x x Dν ≥ ∀ ∈ . У задачі мінімізації знак не-
рівності міняється на протилежний.
Для організації оптимізації за методом гілок та меж необхідно визначити:
1) спосіб оцінювання допоміжної підмножини
l
D ; 2) спосіб утворення
l
D ; 3) прави-
ло (правила) відсікання безперспективних чи порожніх підмножин
l
D .
В рамках цієї роботи розглянемо оцінювання, а при виконанні алгоритму утво-
рення та відсікання
l
D , як це розглядалося в [4-6].
Оцінювання підмножини
l
D можемо здійснювати за допомогою підходу ви-
кладеного в теоремі 5.3 [4, с. 129] у вигляді
* *
,
l l
cξ ν= +
де
l
ν – це сума частини доданків у цільовій функції ( )F x (1), що визначена
вже заданими невідомими, які визначають
l
D ; *
c – оцінка невизначеної частини
цільової функції ( )F x для
l
D , тобто тих її доданків, що містять незадані в
l
D змінні.
Оцінка *
l
ξ підмножини
l
D може бути покращена за рахунок покращення *
c
внаслідок викреслення з матриці С елементів, які стоять в рядках
1
,...,
l
i i та стовпцях
1
,...,
l
j j .
Матрицю, утворену з матриці ( )0
0
0 0
0
j
i
C C i j= = = , позначимо 0
0
...
...
l
l
j j
i i
C . Вона утво-
рюється викресленням з 0 1
0 1
...
...
l
l
j j
i i
C −
−
рядка
l
i , стовпця
l
j . Підмножина множини допустимих
розв’язків (2) – (4) 1 2
1 2
...
...
l
l
j j j
i i i
D задається значеннями змінних
1 1 2 2
... 1
l l
i j i j i j
x x x= = = = .
Елементи матриці 0
0
...
...
l
l
j j
i i
C перепозначимо і перенумеруємо так:
( )
21 2
...
l l l
n l
с с с
−
≥ ≥ ≥ , (6)
не вказуючи залежності від пар ( ), , 1,2,...,
t t
i j t l= , якщо це не викликає плута-
нини.
Для зручності елементи матриці l
C будемо позначати як упорядковану множи-
ну ( )11 ,
,...,
l l l
n l n l
C c c
− −
= . При необхідності будемо використовувати елементи з l
C з
індексами з С, тобто l
uv ijс c= .
Нехай { }1 2
, ,...,
l
l
I i i i= , { }1 2
, ,...,
l
l
J j j j= . Покращення оцінки допустимої під-
множини сформульовано у вигляді такого твердження.
Теорема 1 (про оцінку в задачі максимізації). Оцінкою 1 2
1 2
...
...
l
l
j j j
i i i
ξ підмножини
1 2
1 2
...
...
l
l
j j j
i i i
D може слугувати величина
1 2 1 2
1 2 1 2
... ... *
... ...
,
l l
l l
j j j j j j
i i i i i i l
cξ ν= + (7)
де *
1
n l
l
l j
j
c c
−
=
=∑ , а 1 2
1 2
...
...
l
l
j j j
i i i
ν обчислюється так 1 2
1 2
...
...
1
l
l t t
l
j j j
i i i i j
t
cν
=
=∑ .
Алгоритм розв’язування задачі про оптимальні призначення методом гілок та меж
«Штучний інтелект» 2013 № 2 17
1Л
Доведення. Якщо
1 1 2 2
... 1
l l
i j i j i j
x x x= = = = визначають підмножину 1 2
1 2
...
...
l
l
j j j
i i i
D , то
для 1 2
1 2
...
...
l
l
j j j
i i i
x D∀ ∈
( ) 1 2
1 2
...
...
l
l
l
l
j j j
i i i ij ij
i I
j J
F x c xν
∉
∉
= +∑ ,
при виконанні умов (2) – (4). Що, очевидно, дає нерівність *
l
l
ij ij l
i I
j J
c x c
∉
∉
≤∑ , тобто
( ) 1 2 1 2
1 2 1 2
... ...*
... ...
l l
l l
j j j j j j
i i i l i i iF x cν ξ≤ + = 1 2
1 2
...
...
l
l
j j j
i i i
x D∀ ∈ . Що і треба було довести.
Алгоритм розв’язування задачі методом гілок та меж
Крок 1. Упорядковуємо та пронумеруємо одним індексом по незростанню еле-
менти матриці ефективності С:
1
... ,
k
c c≥ ≥ (8)
де { }11
,..., .
j nn
c c c∈
Крок 2. За допомогою «жадібного» алгоритму знаходимо допустимий розв’я-
зок задачі про призначення і відповідне значення сумарної ефективності як суму з n
елементів матриці ефективності
0
F . Цей алгоритм може бути таким. Нехай на по-
чатку
0
0F = .
Знаходимо найбільший елемент матриці, додаємо його до
0
F , викреслюємо рядок
і стовпець, в якому знаходиться знайдений елемент. З отриманою матрицею робимо
те, що й з вихідною, поки не залишиться один елемент, який також додаємо до
0
F .
0
F відіграє роль поточного рекордного значення цільової функції задачі, тобто
найбільше зі знайдених значень.
Оскільки знайдене
0
F не є гарантовано оптимальним, то його можна спро-
бувати покращити у наступний спосіб. Спираючись на той факт, що в оптимальному
розв’язку містяться доданки
ij
c , які не менші, ніж n найбільших елементів в упоряд-
куванні (8), починати визначення
0
F можна не тільки з найбільшого, а з будь-якого з
n «найбільших» елементів в (8), вибираючи в якості
0
F з одержаних n сум найбільшу.
Крок 3. Задаємо початкові значення 0,0 == τl , l – номер рівня дерева, τ –
номер елемента матриці, що використовується в підмножині. Позначаємо для одно-
манітності формул 0
С C= , 0
0
j
i
D D= .
Зауваження. В кожній підмножині допустимих розв’язків, що розглядаються в
алгоритмі, значення τ своє, тому для 0
0
j
i
D τ позначимо 0
0
j
i
τ (далі
0 0
,i j при наявності
1 1
,i j опускаємо).
Крок 4. Збільшуємо l на одиницю : 1l l= + .
Крок 5. Збільшуємо на одиницю номер елемента множини l
C 0 0
0 0
... ...
... ...
: 1l l
l l
j j j j
i i i i
τ τ= + .
Якщо ( )0
0
2...
...
l
l
j j
i i n
n l l Jτ = − ∀ ∈ та l n= , то перехід на крок 12; при l n< хоча б для
одного l – перехід на крок 11, інакше (тобто коли ( )0
0
2...
...
l
l
j j
i i
n lτ ≠ − ) – крок 6.
Леонова М.В.
«Искусственный интеллект» 2013 № 2 18
1Л
Крок 6. Коефіцієнту цільової функції ставимо у відповідність елемент множи-
ни G (одиницю) в якості відповідного значення
ij
x . Для цього вибираємо наступний
елемент 1l
c
τ
− матриці 1l
C
− в порядку (6), який в С має позначення
l l
i j
c . Задаємо 1
l l
i j
x = .
Виокремлюємо підмножину 1 2
1 2
...
...
l
l
j j j
i i i
D з підмножини 0 1 2 1
0 1 2 1
...
...
l
l
j j j j
i i i i
D −
−
. Далі таку підмножину
позначатимемо 1 2
1 2
...
...
l
l
j j j
i i i
D . Утворюємо матрицю l
C з 1l
C
− , викресливши рядок
l
i ,
стовпець
l
j , (тобто переходимо до наступного ( ( )1l + -го) рівня дерева галуження).
Елементи l
C перепозначимо згідно з (6).
Крок 7. Якщо l n≠ , то перехід на крок 8. Інакше ( )n l= , обчислюємо ( )F x
при
1 1 2 2
... 1
n n
i j i j i j
x x x= = = = , інші 0
ij
x = . Якщо ( ) 0
F x F≥ , то ( )0
:F F x= . Перехід на
крок 11.
Крок 8. Знаходимо для підмножини 1 2
1 2
...
...
l
l
j j j
i i i
D оцінку 1 2
1 2
...
...
l
l
j j j
i i i
ξ , що обчислюється за
формулою (7).
Крок 9. Порівнюємо оцінку 1 2
1 2
...
...
l
l
j j j
i i i
ξ із значенням
0
F . Якщо 1 2
1 2
...
... 0
l
l
j j j
i i i
Fξ ≥ , пере-
ходимо на крок 4, інакше на крок 10.
Крок 10. Оскільки 1 2
1 2
...
... 0
l
l
j j j
i i i
Fξ < , то подальше галуження поточної підмножини
1 2
1 2
...
...
l
l
j j j
i i i
D припиняється, вона відсікається.
Крок 11. Якщо ( )1
1
2...
...
l
l
j j
i i
n lτ = − , то перехід на крок 12, інакше на крок 5.
Крок 12. Повернення на ( )1l − -й рівень дерева. Для цього використовуємо
останню розглянуту підмножину цього рівня 1 2 1
1 2 1
...
...
l
l
j j j
i i i
D −
−
. Тобто зменшуємо l на одини-
цю: : 1l l= − . Перехід на крок 5.
Крок 13. Вивід відповіді – значення цільової функції
0
F та набір векторів x,
множина всіх оптимальних переставлень. Зупинка.
Проілюструємо елементи виконання алгоритму на прикладі. Нехай задана
матриця ефективності С для задачі про призначення. Знайти розв’язок задачі за
допомогою МГМ.
3 7 9 6
3 4 5 4
2 2 6 3
4 5 7 4
C
=
.
Упорядковуємо по незростанню елементи матриці ефективності С:
13 12 43 14 33 23 42 22 24
9 7 7 6 6 5 5 4 4c c c c c c c c c= > = ≥ = > = ≥ = > = ≥ = > = ≥ = ≥
41 44 11 21 34 31 32
4 4 3 3 3 2 2c c c c c c c≥ = ≥ = > = ≥ = ≥ = > = ≥ = .
За допомогою жадібного алгоритму знаходимо
0
F , починаючи визначення з n
найбільших значень
ij
c ,
0
21F = .
0 12 33 24 41
F c c c c= + + + . (9)
На першому рівні галуження привласнює
13
1x = , утворюємо 3
1
D . Знаходимо для
3
1
D перший доданок оцінки (7) 3
1
9ν = та оцінку 3
1 0
22 Fξ = > . Продовжуємо галуження,
Алгоритм розв’язування задачі про оптимальні призначення методом гілок та меж
«Штучний інтелект» 2013 № 2 19
1Л
переходимо до другого рівня ( )2l = , утворюємо 32
14
D :
42
1x = , 32
14
14ν = , 32
14 0
21 Fξ = ≥ .
Аналогічно на третьому рівні ( )3l = галуження – 324
142
D :
24
1x = , 324
142
17ν = , 324
142 0
20 Fξ = < ,
тому підмножина 324
142
D відсікається (на рис. 1 знак ⊗ ). Переходимо до наступного
елемента матриці на тому ж рівні ( )3l = і так далі (рис. 1).
Рисунок 1 – Фрагмент дерева розв’язків для трьох підмножин
Для наведеного прикладу МГМ показав, що покращення
0
F не відбулося. Отже
розв’язком є
0
21F = при призначенні, що задається формулою (9), тобто
12 33 24 41
.x x x x= = =
Висновки
У статті розроблено один з алгоритмів пошуку розв’язків методом гілок та меж
для задачі про призначення. Побудовано нову математичну модель задачі. Сформульо-
вано та доведено твердження про покращення оцінки допоміжних підмножин. Детально
описано способи галуження та відсікання порожніх та безперспективних підмножин.
В подальшому доцільно розглянути поширення способів галуження, оцінюван-
ня і відсікання, наведених в роботі, до задач теорії розкладів [2].
Література
1. Сергиенко И.В. Модели и методы решения на ЭВМ комбинаторных задач оптимизации /
И.В. Сергиенко, М.Ф. Каспшицкая – К. : Наукова думка, 1981. – 288 с.
2. Муха В.С. Задача ученого расписания: постановка и решение / В.С. Муха // Проблемы управления
и информатики. – 2012 – № 6. – С. 125-135.
3. Стоян Ю.Г. Теорія і методи евклідової комбінаторної оптимізації [Електронний ресурс] /
Ю.Г. Стоян, О.О. Ємець. – К. : Ін-т системн. досліджень освіти, 1993. – 188 с. – Режим доступу :
http://dspace.uccu.org.ua/handle/123456789/487.
4. Ємець О.О. Транспортні задачі комбінаторного типу: властивості, розв’язування, узагальнення
[Електронний ресурс] / О.О. Ємець, Т.О. Парфьонова. – Полтава : ПУЕТ, 2011. – 174 с. – Режим
доступу : http://dspace.uccu.org.ua/handle/123456789/353.
5. Ємець О.О. Розв’язування задач комбінаторної оптимізації на нечітких множинах [Електронний
ресурс] / О.О. Ємець, Ол-ра О. Ємець. – Полтава : ПУЕТ, 2011. – 239 с. – Режим доступу :
http://dspace.uccu.org.ua/handle/123456789/352.
6. Линейное и нелинейное программирование / И.Н. Ляшенко, Е.А. Карагодова, Н.В. Чернишова,
Н.З. Шор ; [под общ. ред. И.Н. Ляшенко]. – Киев : Вища шк., 1975. – 372 с.
Literatura
1. Sergienko I.V. Modeli i metody reshenija na JeVM kombinatornyh zadach optimizacii / I.V. Sergienko,
M.F. Kaspshickaja – K. : Naukova dumka, 1981. – 288 s.
2. Muha V.S. Zadacha uchenogo raspisanija: postanovka i reshenie / V.S. Muha // Problemy upravlenija i
informatiki. – 2012 – № 6. – S. 125-135.
( ),2k
E G
13
1x =
42
1x = ⊗
3 3 3
1 1 1 0
, 9, 22D Fν ξ= = ≥
32 32 32
14 14 14 0
, 14, 21D Fν ξ= = ≥
24
1x =
324 324 324
142 142 142 0
, 18, 20D Fν ξ= = <
Леонова М.В.
«Искусственный интеллект» 2013 № 2 20
1Л
3. Stojan Ju.G. Teorіja і metodi evklіdovoї kombіnatornoї optimіzacії [Elektronnij resurs] / Ju.G. Stojan,
O.O. Єmec'. – K. : Іn-t sistemn. doslіdzhen' osvіti, 1993. – 188 s. – Rezhim dostupu :
http://dspace.uccu.org.ua/handle/123456789/487.
4. Єmec' O.O. Transportnі zadachі kombіnatornogo tipu: vlastivostі, rozv’jazuvannja, uzagal'nennja
[Elektronnij resurs] / O.O. Єmec', T.O. Parf'onova. – Poltava : PUET, 2011. – 174 s. – Rezhim dostupu :
http://dspace.uccu.org.ua/handle/123456789/353.
5. Єmec' O.O. Rozv’jazuvannja zadach kombіnatornoї optimіzacії na nechіtkih mnozhinah [Elektronnij
resurs] / O.O. Єmec', Ol-ra O. Єmec'. – Poltava : PUET, 2011. – 239 s. – Rezhim dostupu :
http://dspace.uccu.org.ua/handle/123456789/352.
6. Linejnoe i nelinejnoe programmirovanie / I.N. Ljashenko, E.A. Karagodova, N.V. Chernishova, N.Z.
Shor ; [pod obshh. red. I.N. Ljashenko]. – Kiev : Vishha shk., 1975. – 372 s.
RESUME
M.V. Leonova
Algorithm Solving the Problem of Optimal Function by Method
of Branch and Bound
The article deals with the application of one of the most versatile methods for solving
optimization problems – method branch and bound. Model problems of this type, but with
additional conditions (task scheduling theory) are relevant, but they can not be used
polynomial algorithms. The study of such problems are relevant algorithms in the class of
branches and bounds. In connection with this algorithm branch and bound method for the
assignment problem. Improved estimation of secondary subset
l
D , defined auxiliary subset
evaluation method, the way of its establishment and rule pruning unpromising or empty
subsets
l
D .
Стаття надійшла до редакції 09.04.2013.
|