Жадібний метод розв’язання комбінаторної задачі знаходження максимального потоку в мережі
У статті розглядається комбінаторна задача знаходження максимального потоку в мережі, яка зводиться до задачі евклідової комбінаторної задачі на розміщеннях. Запропоновано наближений алгоритм для її розв’язання, визначена поліноміальна оцінка його складності. The combinatorial problem of finding of...
Збережено в:
| Опубліковано в: : | Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки |
|---|---|
| Дата: | 2012 |
| Автори: | , , |
| Формат: | Стаття |
| Мова: | Українська |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2012
|
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/48878 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Жадібний метод розв’язання комбінаторної задачі знаходження максимального потоку в мережі / О.О. Ємець, Є.М. Ємець, Ю.Ф. Олексійчук // Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки: зб. наук. пр. — Кам’янець-Подільський: Кам'янець-Подільськ. нац. ун-т, 2012. — Вип. 7. — С. 93-99. — Бібліогр.: 12 назв. — укр. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860127674746273792 |
|---|---|
| author | Ємець, О.О. Ємець, Є.М. Олексійчук, Ю.Ф. |
| author_facet | Ємець, О.О. Ємець, Є.М. Олексійчук, Ю.Ф. |
| citation_txt | Жадібний метод розв’язання комбінаторної задачі знаходження максимального потоку в мережі / О.О. Ємець, Є.М. Ємець, Ю.Ф. Олексійчук // Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки: зб. наук. пр. — Кам’янець-Подільський: Кам'янець-Подільськ. нац. ун-т, 2012. — Вип. 7. — С. 93-99. — Бібліогр.: 12 назв. — укр. |
| collection | DSpace DC |
| container_title | Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки |
| description | У статті розглядається комбінаторна задача знаходження максимального потоку в мережі, яка зводиться до задачі евклідової комбінаторної задачі на розміщеннях. Запропоновано наближений алгоритм для її розв’язання, визначена поліноміальна оцінка його складності.
The combinatorial problem of finding of the maximal flow in a network is considered in the paper. This problem is a Euclidean combinatorial problem on arrangements. The approximate algorithm for solution of this problem is proposed. The polynomial estimation of complexity of this algorithm found.
|
| first_indexed | 2025-12-07T17:42:59Z |
| format | Article |
| fulltext |
Серія: Фізико-математичні науки. Випуск 7
93
УДК 519.85
О. О. Ємець, д-р фіз.-мат. наук,
Є. М. Ємець, канд. фіз.-мат. наук,
Ю. Ф. Олексійчук, старший викладач
Полтавський університет економіки і торгівлі, м. Полтава
ЖАДІБНИЙ МЕТОД РОЗВ’ЯЗАННЯ КОМБІНАТОРНОЇ ЗАДАЧІ
ЗНАХОДЖЕННЯ МАКСИМАЛЬНОГО ПОТОКУ В МЕРЕЖІ
У статті розглядається комбінаторна задача знаходження
максимального потоку в мережі, яка зводиться до задачі евклі-
дової комбінаторної задачі на розміщеннях. Запропоновано
наближений алгоритм для її розв’язання, визначена поліноміа-
льна оцінка його складності.
Ключові слова: максимальний потік, комбінаторна оп-
тимізація, розміщення, жадібний алгоритм.
Вступ
Задача знаходження максимального потоку широко досліджена
[1—7] та відомі поліноміальні методи для її розв’язання, зокрема,
методи Форда і Фалкерсона [1], Едмондса і Карпа [4], Дініца [5], Кар-
занова [6] та ін. Задача, що розглядається, є узагальненням задачі
знаходження максимального потоку. Комбінаторну задачу знахо-
дження максимального потоку можна звести [8] до евклідової комбі-
наторної задачі оптимізації на розміщеннях [9—11], для розв’язання
якої відомі неполіноміальні алгоритми. Тому побудова наближених
поліноміальних методів є актуальною.
У статті розглядається жадібний метод розв’язання комбінатор-
ної задачі знаходження максимального потоку в мережі і аналізується
його складність.
1. Постановка задачі
Нехай дано зв’язний орієнтований граф ,V U , де V —
множина вершин, U — множина дуг. Дугу, що сполучає вершина
iv і jv , позначимо iju ; ,i jv v V .
Означення 1. Транспортною мережею називають орієнтований
граф ,V U , в якому кожній із дуг iju привласнене невід’ємне
число 0ijb , яке називають пропускною спроможністю дуги. Хоча б
одна із вершин має лише вихідні дуги. Таку вершину називають дже-
релом и позначають sv . Також є принаймні одна вершина, що має
лише вхідні дуги. Її називають стоком і позначають tv .
© О. О. Ємець, Є. М. Ємець, Ю. Ф. Олексійчук, 2012
Математичне та комп’ютерне моделювання
94
Далі будемо розглядати транспортні мережі з одним джерелом і
одним стоком. Будемо вважати, що кожна дуга iju в протилежному
напрямку має пропускну спроможність 0jib .
Означення 2. [7] Потоком називають функцію :w U R з та-
кими властивостями для будь-якої дуги iju :
1. Значення функції w на дузі iju не може перевищувати пропускну
здатність дуги, тобто ij ijw u b .
2. Збереження балансу у всіх вершинах, крім стоку и джерела, тобто
iz zj
iz zj
u U u U
w u w u
, ,z i jv v v V , z sv v , z tv v .
Означення 3. Величиною потоку w будемо називати суму зна-
чень функції w по дугах, що виходять із джерела:
si
si
u U
w w u
,
де iv V .
Величина потоку w також дорівнює сумі значень функції w по
дугах, що входять в стік.
Задача знаходження максимального потоку формулюється так:
знайти потік w , для якого величина потоку w є максимальною.
Означення 4. Залишковою пропускною спроможністю ребра iju
називають величину ij ij ijh b w u .
Якщо в транспортній мережі замінити пропускні спроможності
на залишкові пропускні спроможності, то отримаємо мережу, яку
назвемо залишковою.
Потоком на дузі iju будемо називати величину ijw u .
Введемо додаткові обмеження на потік. Нехай потік по дугах
ij cu U U , може приймати значення, які не перевищують число
ij lx g G , тобто ij ijw u x , де мультимножина 1 2, ,...,G g g g ;
причому вектор із чисел ijx є розміщенням елементів із G [9—11],
тобто
1 1 2 2
, ,...,
k k
k
i j i j i j nx x x x E G , де k
nE G — множина розмі-
щень, сk U , n — кількість різних в G елементів.
Серія: Фізико-математичні науки. Випуск 7
95
Назвемо задачу знаходження максимального потоку з додатко-
вими комбінаторними обмеженнями комбінаторною задачею знахо-
дження максимального потоку.
2. Математична модель
Розглянемо математичну модель задачі. Нехай потік по дузі iju ,
рівний ijy , тобто ij ijy w u .
Задача полягає у відшуканні максимального значення функції
f y і відповідних значень ijx , ijy :
max
jt
jt
u U
f y y
, (1)
при виконанні наступних умов:
збереження балансу у вершинах
iz zj
iz zj
u U u U
y y
, z , z t , z s , (2)
обмеження на пропускну здатність дуг
0 ij ijy b i j , iju U , (3)
додаткові комбінаторні обмеження
ij ijy x i j , ij сu U , (4)
1 1 2 2
, ,...,
k k
k
i j i j i j nx x x x E G . (5)
Задача (1)—(5) є частковим випадком задачі евклідової комбіна-
торної оптимізації на розміщеннях.
Розробці методів розв’язання задач комбінаторної оптимізації, дос-
лідженню властивостей опуклих оболонок комбінаторних множин прис-
вячено багато робіт (див., зокрема, [9—12]). Методи розв’язання комбі-
наторних задач на розміщеннях з додатковими обмеженнями запропоно-
вані, наприклад, в [11] і [12]; всі вони є неполіноміальними.
Зазначимо, що комбінаторну задачу знаходження максимально-
го потоку в мережі можна звести до задачі евклідової комбінаторної
оптимізації на переставленнях. Для цього достатньо побудувати нову
мультимножину, взявши k найбільших елементів мультимножини
G , де k — кількість дуг, на які накладені комбінаторні обмеження.
У [8] розглядається метод розв’язання задачі (1)—(5). Але вра-
ховуючи неполіноміальність методу, актуальною є розробка набли-
жених методів розв’язання задачі.
3. Жадібний метод
Розглянемо метод, який дозволяє знайти наближений розв’язок по-
ставленої задачі. В методі використовуються ідеї Едмондса і Карпа [4]
Математичне та комп’ютерне моделювання
96
для знаходження максимального потоку. На кожному етапі максимально
насичується найкоротший шлях, тому метод названий «жадібним».
Крок 0. Покладаємо потік рівним нулю. Розширимо мультим-
ножину G , додавши k нулів, де k — кількість дуг, на які накладені
додаткові комбінаторні обмеження. Для всіх дуг покладаємо 0ijx , і
будемо вважати всі ненульові елементи мультимножини G невико-
ристаними. Залишкова мережа на початковому етапі збігається з по-
чатковою мережею.
Крок 1. Знаходимо в залишковій мережі, не враховуючи додат-
кових комбінаторних обмежень, найкоротший шлях із джерела в стік
з максимальною пропускною здатністю, використовуючи модифіко-
ваний пошук у ширину. Нехай шлях складається із p дуг і має про-
пускну здатність рівну b . (Під пропускною здатністю шляху розумі-
ємо мінімальну пропускну здатність серед дуг цього шляху). Якщо
такого шляху немає — зупинка алгоритму.
Крок 2. Переберемо всі дуги знайденого шляху у порядку спа-
дання пропускних спроможностей ijb . Привласнимо всім ijx , для
яких ij ijx b y , мінімальні значення із мультимножини G , які не-
зайняті і перевищують ijb y , де ijy — поточне значення потоку по
дузі iju . Якщо такого елемента немає, беремо найбільший елемент із
G . Будемо вважати ці елементи мультимножини зайнятими, а попе-
редні значення ijx — незайнятими.
Крок 3. Пускаємо через знайдений шлях максимально можли-
вий потік (враховуючи комбінаторні обмеження).
Крок 4. Модифікуємо залишкову мережу. Змінюємо пропускні
здатності і видаляємо дуги, для яких виконується хоча б одна умова:
а) ij ijy b ;
б) ij ijy x і в G немає вільних елементів, що перевищують ijx .
При цьому, якщо умови а) і б) більше не виконуються для деякої
раніше видаленої дуги — повертаємо її в залишкову мережу.
Переходимо на крок 1.
Модифікований пошук в ширину дозволяє знайти найкоротший
шлях з джерела до стоку. Якщо таких шляхів кілька — метод дозво-
ляє знайти серед них шлях з найбільшою пропускною здатністю.
Для кожної вершини iv потрібно задати такі поля:
1) стан вершини, можливі значення: не помічена, помічена, переглянута;
2) предок — інша вершина графа;
Серія: Фізико-математичні науки. Випуск 7
97
3) відстань від джерела id ;
4) потенційний потік ip .
Модифікований пошук в ширину.
Крок 0. Джерело вважаємо поміченим, sp , 0sd . Всі інші
вершини — не поміченими, 0ip , i , i s . Створюємо чергу із
помічених вершин.
Крок 1. Якщо черга порожня — шляху не існує, зупинка алго-
ритму, інакше — вважаємо першу вершину черги cv переглянутою і
видаляємо її із черги.
Крок 2. Розглядаємо всі дуги ciu , що виходять з вершини cv , і
перебираємо вершини iv , які або містяться в черзі і i сd d , або є
непоміченими. Якщо min ,i c cip p b , то min ,i c cip p b , предком
вершини iv стає вершина cv , 1i сd d та, якщо вершина непоміче-
на, помічаємо її та додаємо в кінець черги.
Крок 3. Якщо tv міститься в черзі і t zd d , де zv — перша в
черзі вершина, то зупинка алгоритму. (Зворотній до шуканого шлях
можна отримати, почавши зі стоку і переходячи від вершини до її
предка доки не досягнемо джерела). Інакше — перехід до кроку 1.
4. Оцінка складності жадібного методу
Нехай V — кількість вершин графа, U — кількість дуг.
Теорема 1. Час роботи модифікованого алгоритму пошуку в
ширину T n O U V .
Доведення. Очевидно, що час виконання нульового кроку О V .
В черзі ми переглядаємо не більше V вершин, тобто цикл (кроки
1—3) виконується не більше V разів. На кроці 2 ми розглядаємо не
більше ніж сK вершин, де сK — число дуг, що виходять з вершини
cv . Оскільки
1
V
c
c
K U
, то час роботи алгоритму T n O U V .
Зауваження. Оскільки в роботі розглядаються зв’язні графи, то
час роботи модифікованого алгоритму пошуку в ширину рівний
T n O U .
Теорема 2. Час роботи жадібного алгоритму розв’язання комбі-
наторної задачі знаходження максимального потоку T n
Математичне та комп’ютерне моделювання
98
*O U n w , де *w — шукана величина максимального потоку,
n — кількість різних елементів у мультимножині G .
Доведення. Час виконання кроків 0, 1 та 3 можна оцінити як
O U , кроків 2 і 4 — O n U . На кожній ітерації (кроки 1—4) ве-
личина потоку зростає. Тому Загальний час роботи алгоритму —
*T n O U n w .
Висновки
У статті розглянута комбінаторна задача знаходження максималь-
ного потоку, запропонований наближений метод її розв’язання та зроб-
лена оцінка часу роботи цього методу. В подальшому доцільно оцінити
точність роботи алгоритму та провести обчислювальні експерименти.
Список використаних джерел:
1. Форд Л. Потоки в сетях / Л. Форд, Д. Фалкерсон. — М. : Мир, 1966. — 277 с.
2. Ху Т. Ч. Комбинаторные алгоритмы / Т. Ч. Ху, М. Т. Шинг. — Нижний
Новгород : Изд-во Нижегородского госуниверситета им. Н. И. Лоба-
чевского, 2004. — 330 с.
3. Ху Т. Целочисленное программирование и потоки в сетях / Т. Ху. — М. :
Мир, 1974. — 519 с.
4. Edmonds J. Theoretical Improvements in Algorithmic Efficiency for Network
How Problems / J. Edmonds, R. M. Karp // J. ACM. — 1972. — Vol. 19,
№ 2. — P. 248–264.
5. Диниц Е. А. Алгоритм решения задачи о максимальном потоке в сети со
степенной оценкой / Е. А. Диниц // Докл. АН СССР. — 1970. — Т. 194,
№ 4. — С. 754–757.
6. Карзанов А. А. Нахождение максимального потока в сети методом предпото-
ков / А. А. Карзанов // Докл. АН СССР. — 1974. — Т. 215, № 1. — С. 49–53.
7. Алгоритмы: построение и анализ / Т. Кормен, Ч. Лейзерсон, Р. Ривест,
К. Штайн. — 2-е издание. — М. : Изд. дом "Вильямс", 2005. — 1296 с.
8. Ємець О. О. Знаходження максимального потоку в мережі з додатковими
комбінаторними обмеженнями / О. О. Ємець, Є. М. Ємець, Ю. Ф. Олек-
сійчук // Таврический вестник информатики и математики. — 2011. —
№1. — С. 43–50.
9. Стоян Ю. Г. Теорія і методи евклідової комбінаторної оптимізації /
Ю. Г. Стоян, О. О. Ємець — К. : ІСДО, 1993. — 188 с. — Режим доступу:
http://informatics.org.ua/uploads/books/stoyan_emets_eko.pdf.
10. Стоян Ю. Г. Оптимізація на полірозміщеннях: теорія та методи : монографія /
Ю. Г. Стоян, О. О. Ємець, Є. М. Ємець. — Полтава : РВЦ ПУСКУ, 2005. —
103 с.
11. Емец О. А. Комбинаторная оптимизация на размещениях : монография /
О. А. Емец, Т. Н. Барболина. — К. : Наукова думка, 2008. — 159 с. — Режим
доступу: http://informatics.org.ua/uploads/books/ em_bar_monography.pdf.
Серія: Фізико-математичні науки. Випуск 7
99
12. Ємець О. О. Прямий метод відсікання для задач комбінаторної оптиміза-
ції на розміщеннях / О. О. Ємець, Є. М. Ємець, Ю. Ф. Олексійчук // Віс-
ник Запорізького національного університету : збірник наукових статей.
Фізико-математичні науки. — Запоріжжя : Запорізький національний уні-
верситет, 2011. — №1. — С. 36–43.
The combinatorial problem of finding of the maximal flow in a network is
considered in the paper. This problem is a Euclidean combinatorial problem on
arrangements. The approximate algorithm for solution of this problem is pro-
posed. The polynomial estimation of complexity of this algorithm found.
Key words: maximum flow, combinatorial optimization, arrange-
ments, greedy algorithm.
Отримано: 05.06.2012
УДК 519.8(075)
Л. В. Іващенко, аспірант
ДВНЗ «КНЕУ імені Вадима Гетьмана», м. Київ
МОДЕЛЮВАННЯ ПРОЦЕСУ ПІДКРІПЛЕННЯ
БАНКОМАТІВ ГОТІВКОВИМИ КОШТАМИ
У статті розроблена математична модель управління
залишком готівкових коштів у банкоматі з використанням
теорії управління запасами та теорії масового обслуговування.
Ключові слова: банкомат, стохастична модель, модель
керування запасами Уілсона.
Постановка проблеми. За оцінками фахівців, на сьогодні у світі
налічується 2,3 млн. банкоматів, а до 2016 року їх кількість зросте до
3,2 млн. одиниць. Багато фінансових інститутів завантажують у банко-
мати на 40% більше готівки, ніж необхідно для їх ефективної роботи, а у
структурі витрат на експлуатацію банкоматів від 35 до 60% припадають
саме на витрати, пов'язані з готівкою, така політика управління готівко-
вими коштами позбавляє банк значних фінансових ресурсів, які можна
раціональніше використовувати у інших напрямках [1].
Отже, у сучасних умовах оптимізація потоків готівки, які спря-
мовуються на виплату клієнтам саме через банкомати є актуальною
проблемою теорії і практики.
Аналіз останніх джерел чи публікацій. Проблематика дослідже-
ння у контексті визначення оптимального управління готівковими гро-
шовими коштами висвітлювалася у публікаціях В. Соловйова, В. Тка-
лича, А. Кистанова, Н.Васіна, Д. В. Пастухова, В. Д. Іушиної та інших.
Постановка завдання. На сьогодні існують програмні продук-
ти, які покликані вирішувати питання оптимізації управління готівко-
© Л. В. Іващенко, 2012
<<
/ASCII85EncodePages false
/AllowTransparency false
/AutoPositionEPSFiles true
/AutoRotatePages /All
/Binding /Left
/CalGrayProfile (Gray Gamma 2.2)
/CalRGBProfile (sRGB IEC61966-2.1)
/CalCMYKProfile (Coated FOGRA27 \050ISO 12647-2:2004\051)
/sRGBProfile (sRGB IEC61966-2.1)
/CannotEmbedFontPolicy /Warning
/CompatibilityLevel 1.3
/CompressObjects /Tags
/CompressPages true
/ConvertImagesToIndexed true
/PassThroughJPEGImages true
/CreateJobTicket false
/DefaultRenderingIntent /Default
/DetectBlends true
/DetectCurves 0.1000
/ColorConversionStrategy /sRGB
/DoThumbnails false
/EmbedAllFonts true
/EmbedOpenType false
/ParseICCProfilesInComments true
/EmbedJobOptions true
/DSCReportingLevel 0
/EmitDSCWarnings false
/EndPage -1
/ImageMemory 1048576
/LockDistillerParams false
/MaxSubsetPct 100
/Optimize true
/OPM 1
/ParseDSCComments true
/ParseDSCCommentsForDocInfo true
/PreserveCopyPage true
/PreserveDICMYKValues true
/PreserveEPSInfo false
/PreserveFlatness false
/PreserveHalftoneInfo false
/PreserveOPIComments false
/PreserveOverprintSettings true
/StartPage 1
/SubsetFonts true
/TransferFunctionInfo /Apply
/UCRandBGInfo /Remove
/UsePrologue false
/ColorSettingsFile ()
/AlwaysEmbed [ true
]
/NeverEmbed [ true
/Arial-Black
/Arial-BlackItalic
/Arial-BoldItalicMT
/Arial-BoldMT
/Arial-ItalicMT
/ArialMT
/ArialNarrow
/ArialNarrow-Bold
/ArialNarrow-BoldItalic
/ArialNarrow-Italic
/ArialUnicodeMS
/CenturyGothic
/CenturyGothic-Bold
/CenturyGothic-BoldItalic
/CenturyGothic-Italic
/CourierNewPS-BoldItalicMT
/CourierNewPS-BoldMT
/CourierNewPS-ItalicMT
/CourierNewPSMT
/Georgia
/Georgia-Bold
/Georgia-BoldItalic
/Georgia-Italic
/Impact
/LucidaConsole
/Tahoma
/Tahoma-Bold
/TimesNewRomanMT-ExtraBold
/TimesNewRomanPS-BoldItalicMT
/TimesNewRomanPS-BoldMT
/TimesNewRomanPS-ItalicMT
/TimesNewRomanPSMT
/Trebuchet-BoldItalic
/TrebuchetMS
/TrebuchetMS-Bold
/TrebuchetMS-Italic
/Verdana
/Verdana-Bold
/Verdana-BoldItalic
/Verdana-Italic
]
/AntiAliasColorImages false
/CropColorImages false
/ColorImageMinResolution 150
/ColorImageMinResolutionPolicy /OK
/DownsampleColorImages true
/ColorImageDownsampleType /Bicubic
/ColorImageResolution 150
/ColorImageDepth -1
/ColorImageMinDownsampleDepth 1
/ColorImageDownsampleThreshold 1.50000
/EncodeColorImages true
/ColorImageFilter /DCTEncode
/AutoFilterColorImages true
/ColorImageAutoFilterStrategy /JPEG
/ColorACSImageDict <<
/QFactor 0.76
/HSamples [2 1 1 2] /VSamples [2 1 1 2]
>>
/ColorImageDict <<
/QFactor 0.76
/HSamples [2 1 1 2] /VSamples [2 1 1 2]
>>
/JPEG2000ColorACSImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 15
>>
/JPEG2000ColorImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 15
>>
/AntiAliasGrayImages false
/CropGrayImages false
/GrayImageMinResolution 150
/GrayImageMinResolutionPolicy /OK
/DownsampleGrayImages true
/GrayImageDownsampleType /Bicubic
/GrayImageResolution 150
/GrayImageDepth -1
/GrayImageMinDownsampleDepth 2
/GrayImageDownsampleThreshold 1.50000
/EncodeGrayImages true
/GrayImageFilter /DCTEncode
/AutoFilterGrayImages true
/GrayImageAutoFilterStrategy /JPEG
/GrayACSImageDict <<
/QFactor 0.76
/HSamples [2 1 1 2] /VSamples [2 1 1 2]
>>
/GrayImageDict <<
/QFactor 0.76
/HSamples [2 1 1 2] /VSamples [2 1 1 2]
>>
/JPEG2000GrayACSImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 15
>>
/JPEG2000GrayImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 15
>>
/AntiAliasMonoImages false
/CropMonoImages false
/MonoImageMinResolution 1200
/MonoImageMinResolutionPolicy /OK
/DownsampleMonoImages true
/MonoImageDownsampleType /Bicubic
/MonoImageResolution 1200
/MonoImageDepth -1
/MonoImageDownsampleThreshold 1.50000
/EncodeMonoImages true
/MonoImageFilter /CCITTFaxEncode
/MonoImageDict <<
/K -1
>>
/AllowPSXObjects true
/CheckCompliance [
/PDFX1a:2001
]
/PDFX1aCheck false
/PDFX3Check false
/PDFXCompliantPDFOnly false
/PDFXNoTrimBoxError true
/PDFXTrimBoxToMediaBoxOffset [
0.00000
0.00000
0.00000
0.00000
]
/PDFXSetBleedBoxToMediaBox true
/PDFXBleedBoxToTrimBoxOffset [
0.00000
0.00000
0.00000
0.00000
]
/PDFXOutputIntentProfile (None)
/PDFXOutputConditionIdentifier ()
/PDFXOutputCondition ()
/PDFXRegistryName ()
/PDFXTrapped /False
/CreateJDFFile false
/Description <<
/ARA <FEFF06270633062A062E062F0645002006470630064700200627064406250639062F0627062F0627062A002006440625064606340627062100200648062B062706260642002000410064006F00620065002000500044004600200645062A064806270641064206290020064506390020064506420627064A064A0633002006390631063600200648063706280627063906290020062706440648062B0627062606420020062706440645062A062F062706480644062900200641064A00200645062C062706440627062A002006270644062306390645062706440020062706440645062E062A064406410629061B0020064A06450643064600200641062A062D00200648062B0627062606420020005000440046002006270644064506460634062306290020062806270633062A062E062F062706450020004100630072006F0062006100740020064800410064006F006200650020005200650061006400650072002006250635062F0627063100200035002E0030002006480627064406250635062F062706310627062A0020062706440623062D062F062B002E>
/BGR <FEFF04180437043f043e043b043704320430043904420435002004420435043704380020043d0430044104420440043e0439043a0438002c00200437043000200434043000200441044a0437043404300432043004420435002000410064006f00620065002000500044004600200434043e043a0443043c0435043d04420438002c0020043f043e04340445043e0434044f044904380020043704300020043d043004340435043604340435043d0020043f044004350433043b04350434002004380020043f04350447043004420020043d04300020043104380437043d0435044100200434043e043a0443043c0435043d04420438002e002000200421044a04370434043004340435043d043804420435002000500044004600200434043e043a0443043c0435043d044204380020043c043e0433043004420020043404300020044104350020043e0442043204300440044f0442002004410020004100630072006f00620061007400200438002000410064006f00620065002000520065006100640065007200200035002e00300020043800200441043b0435043404320430044904380020043204350440044104380438002e>
/CHS <FEFF4f7f75288fd94e9b8bbe5b9a521b5efa7684002000410064006f006200650020005000440046002065876863900275284e8e55464e1a65876863768467e5770b548c62535370300260a853ef4ee54f7f75280020004100630072006f0062006100740020548c002000410064006f00620065002000520065006100640065007200200035002e003000204ee553ca66f49ad87248672c676562535f00521b5efa768400200050004400460020658768633002>
/CHT <FEFF4f7f752890194e9b8a2d7f6e5efa7acb7684002000410064006f006200650020005000440046002065874ef69069752865bc666e901a554652d965874ef6768467e5770b548c52175370300260a853ef4ee54f7f75280020004100630072006f0062006100740020548c002000410064006f00620065002000520065006100640065007200200035002e003000204ee553ca66f49ad87248672c4f86958b555f5df25efa7acb76840020005000440046002065874ef63002>
/CZE <FEFF005400610074006f0020006e006100730074006100760065006e00ed00200070006f0075017e0069006a007400650020006b0020007600790074007600e101590065006e00ed00200064006f006b0075006d0065006e0074016f002000410064006f006200650020005000440046002000760068006f0064006e00fd00630068002000700072006f002000730070006f006c00650068006c0069007600e90020007a006f006200720061007a006f007600e1006e00ed002000610020007400690073006b0020006f006200630068006f0064006e00ed0063006800200064006f006b0075006d0065006e0074016f002e002000200056007900740076006f01590065006e00e900200064006f006b0075006d0065006e007400790020005000440046002000620075006400650020006d006f017e006e00e90020006f007400650076015900ed007400200076002000700072006f006700720061006d0065006300680020004100630072006f00620061007400200061002000410064006f00620065002000520065006100640065007200200035002e0030002000610020006e006f0076011b006a016100ed00630068002e>
/DAN <FEFF004200720075006700200069006e0064007300740069006c006c0069006e006700650072006e0065002000740069006c0020006100740020006f007000720065007400740065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e007400650072002c0020006400650072002000650067006e006500720020007300690067002000740069006c00200064006500740061006c006a006500720065007400200073006b00e60072006d007600690073006e0069006e00670020006f00670020007500640073006b007200690076006e0069006e006700200061006600200066006f0072007200650074006e0069006e006700730064006f006b0075006d0065006e007400650072002e0020004400650020006f007000720065007400740065006400650020005000440046002d0064006f006b0075006d0065006e0074006500720020006b0061006e002000e50062006e00650073002000690020004100630072006f00620061007400200065006c006c006500720020004100630072006f006200610074002000520065006100640065007200200035002e00300020006f00670020006e0079006500720065002e>
/DEU <FEFF00560065007200770065006e00640065006e0020005300690065002000640069006500730065002000450069006e007300740065006c006c0075006e00670065006e0020007a0075006d002000450072007300740065006c006c0065006e00200076006f006e002000410064006f006200650020005000440046002d0044006f006b0075006d0065006e00740065006e002c00200075006d002000650069006e00650020007a0075007600650072006c00e40073007300690067006500200041006e007a006500690067006500200075006e00640020004100750073006700610062006500200076006f006e00200047006500730063006800e40066007400730064006f006b0075006d0065006e00740065006e0020007a0075002000650072007a00690065006c0065006e002e00200044006900650020005000440046002d0044006f006b0075006d0065006e007400650020006b00f6006e006e0065006e0020006d006900740020004100630072006f00620061007400200075006e0064002000520065006100640065007200200035002e003000200075006e00640020006800f600680065007200200067006500f600660066006e00650074002000770065007200640065006e002e>
/ENU (Use these settings to create Adobe PDF documents suitable for reliable viewing and printing of business documents. Created PDF documents can be opened with Acrobat and Adobe Reader 5.0 and later.)
/ESP <FEFF005500740069006c0069006300650020006500730074006100200063006f006e0066006900670075007200610063006900f3006e0020007000610072006100200063007200650061007200200064006f00630075006d0065006e0074006f0073002000640065002000410064006f00620065002000500044004600200061006400650063007500610064006f007300200070006100720061002000760069007300750061006c0069007a00610063006900f3006e0020006500200069006d0070007200650073006900f3006e00200064006500200063006f006e006600690061006e007a006100200064006500200064006f00630075006d0065006e0074006f007300200063006f006d00650072006300690061006c00650073002e002000530065002000700075006500640065006e00200061006200720069007200200064006f00630075006d0065006e0074006f00730020005000440046002000630072006500610064006f007300200063006f006e0020004100630072006f006200610074002c002000410064006f00620065002000520065006100640065007200200035002e003000200079002000760065007200730069006f006e0065007300200070006f00730074006500720069006f007200650073002e>
/ETI <FEFF004b00610073007500740061006700650020006e0065006900640020007300e400740074006500690064002000e4007200690064006f006b0075006d0065006e00740069006400650020007500730061006c006400750073007600e400e4007200730065006b0073002000760061006100740061006d006900730065006b00730020006a00610020007000720069006e00740069006d006900730065006b007300200073006f00620069006c0069006b0065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e00740069006400650020006c006f006f006d006900730065006b0073002e00200020004c006f006f0064007500640020005000440046002d0064006f006b0075006d0065006e00740065002000730061006100740065002000610076006100640061002000700072006f006700720061006d006d006900640065006700610020004100630072006f0062006100740020006e0069006e0067002000410064006f00620065002000520065006100640065007200200035002e00300020006a00610020007500750065006d006100740065002000760065007200730069006f006f006e00690064006500670061002e>
/FRA <FEFF005500740069006c006900730065007a00200063006500730020006f007000740069006f006e00730020006100660069006e00200064006500200063007200e900650072002000640065007300200064006f00630075006d0065006e00740073002000410064006f006200650020005000440046002000700072006f00660065007300730069006f006e006e0065006c007300200066006900610062006c0065007300200070006f007500720020006c0061002000760069007300750061006c00690073006100740069006f006e0020006500740020006c00270069006d007000720065007300730069006f006e002e0020004c0065007300200064006f00630075006d0065006e00740073002000500044004600200063007200e900e90073002000700065007500760065006e0074002000ea0074007200650020006f007500760065007200740073002000640061006e00730020004100630072006f006200610074002c002000610069006e00730069002000710075002700410064006f00620065002000520065006100640065007200200035002e0030002000650074002000760065007200730069006f006e007300200075006c007400e90072006900650075007200650073002e>
/GRE <FEFF03a703c103b703c303b903bc03bf03c003bf03b903ae03c303c403b5002003b103c503c403ad03c2002003c403b903c2002003c103c503b803bc03af03c303b503b903c2002003b303b903b1002003bd03b1002003b403b703bc03b903bf03c503c103b303ae03c303b503c403b5002003ad03b303b303c103b103c603b1002000410064006f006200650020005000440046002003ba03b103c403ac03bb03bb03b703bb03b1002003b303b903b1002003b103be03b903cc03c003b903c303c403b7002003c003c103bf03b203bf03bb03ae002003ba03b103b9002003b503ba03c403cd03c003c903c303b7002003b503c003b903c703b503b903c103b703bc03b103c403b903ba03ce03bd002003b503b303b303c103ac03c603c903bd002e0020002003a403b10020005000440046002003ad03b303b303c103b103c603b1002003c003bf03c5002003ad03c703b503c403b5002003b403b703bc03b903bf03c503c103b303ae03c303b503b9002003bc03c003bf03c103bf03cd03bd002003bd03b1002003b103bd03bf03b903c703c403bf03cd03bd002003bc03b5002003c403bf0020004100630072006f006200610074002c002003c403bf002000410064006f00620065002000520065006100640065007200200035002e0030002003ba03b103b9002003bc03b503c403b103b303b503bd03ad03c303c403b503c103b503c2002003b503ba03b403cc03c303b503b903c2002e>
/HEB <FEFF05d405e905ea05de05e905d5002005d105d405d205d305e805d505ea002005d005dc05d4002005db05d305d9002005dc05d905e605d505e8002005de05e105de05db05d9002000410064006f006200650020005000440046002005e205d105d505e8002005d405e605d205d4002005d505d405d305e405e105d4002005d005de05d905e005d4002005e905dc002005de05e105de05db05d905dd002005e205e105e705d905d905dd002e002005de05e105de05db05d90020005000440046002005e905e005d505e605e805d5002005e005d905ea05e005d905dd002005dc05e405ea05d905d705d4002005d105d005de05e605e205d505ea0020004100630072006f006200610074002005d5002d00410064006f00620065002000520065006100640065007200200035002e0030002005d505d205e805e105d005d505ea002005de05ea05e705d305de05d505ea002005d905d505ea05e8002e>
/HRV (Za stvaranje Adobe PDF dokumenata pogodnih za pouzdani prikaz i ispis poslovnih dokumenata koristite ove postavke. Stvoreni PDF dokumenti mogu se otvoriti Acrobat i Adobe Reader 5.0 i kasnijim verzijama.)
/HUN <FEFF00410020006800690076006100740061006c006f007300200064006f006b0075006d0065006e00740075006d006f006b0020006d00650067006200ed007a00680061007400f30020006d0065006700740065006b0069006e007400e9007300e900720065002000e900730020006e0079006f006d00740061007400e1007300e10072006100200073007a00e1006e0074002000410064006f00620065002000500044004600200064006f006b0075006d0065006e00740075006d006f006b0061007400200065007a0065006b006b0065006c0020006100200062006500e1006c006c00ed007400e10073006f006b006b0061006c00200068006f007a006800610074006a00610020006c00e9007400720065002e0020002000410020006c00e90074007200650068006f007a006f00740074002000500044004600200064006f006b0075006d0065006e00740075006d006f006b00200061007a0020004100630072006f006200610074002000e9007300200061007a002000410064006f00620065002000520065006100640065007200200035002e0030002c0020007600610067007900200061007a002000610074007400f3006c0020006b00e9007301510062006200690020007600650072007a006900f3006b006b0061006c0020006e00790069007400680061007400f3006b0020006d00650067002e>
/ITA (Utilizzare queste impostazioni per creare documenti Adobe PDF adatti per visualizzare e stampare documenti aziendali in modo affidabile. I documenti PDF creati possono essere aperti con Acrobat e Adobe Reader 5.0 e versioni successive.)
/JPN <FEFF30d330b830cd30b9658766f8306e8868793a304a3088307353705237306b90693057305f002000410064006f0062006500200050004400460020658766f8306e4f5c6210306b4f7f75283057307e305930023053306e8a2d5b9a30674f5c62103055308c305f0020005000440046002030d530a130a430eb306f3001004100630072006f0062006100740020304a30883073002000410064006f00620065002000520065006100640065007200200035002e003000204ee5964d3067958b304f30533068304c3067304d307e305930023053306e8a2d5b9a3067306f30d530a930f330c8306e57cb30818fbc307f3092884c3044307e30593002>
/KOR <FEFFc7740020c124c815c7440020c0acc6a9d558c5ec0020be44c988b2c8c2a40020bb38c11cb97c0020c548c815c801c73cb85c0020bcf4ace00020c778c1c4d558b2940020b3700020ac00c7a50020c801d569d55c002000410064006f0062006500200050004400460020bb38c11cb97c0020c791c131d569b2c8b2e4002e0020c774b807ac8c0020c791c131b41c00200050004400460020bb38c11cb2940020004100630072006f0062006100740020bc0f002000410064006f00620065002000520065006100640065007200200035002e00300020c774c0c1c5d0c11c0020c5f40020c2180020c788c2b5b2c8b2e4002e>
/LTH <FEFF004e006100750064006f006b0069007400650020016100690075006f007300200070006100720061006d006500740072007500730020006e006f0072011700640061006d00690020006b0075007200740069002000410064006f00620065002000500044004600200064006f006b0075006d0065006e007400750073002c0020006b0075007200690065002000740069006e006b006100200070006100740069006b0069006d006100690020007000650072017e0069016b007201170074006900200069007200200073007000610075007300640069006e0074006900200076006500720073006c006f00200064006f006b0075006d0065006e007400750073002e0020002000530075006b0075007200740069002000500044004600200064006f006b0075006d0065006e007400610069002000670061006c006900200062016b007400690020006100740069006400610072006f006d00690020004100630072006f006200610074002000690072002000410064006f00620065002000520065006100640065007200200035002e0030002000610072002000760117006c00650073006e0117006d00690073002000760065007200730069006a006f006d00690073002e>
/LVI <FEFF0049007a006d0061006e0074006f006a00690065007400200161006f00730020006900650073007400610074012b006a0075006d00750073002c0020006c0061006900200076006500690064006f00740075002000410064006f00620065002000500044004600200064006f006b0075006d0065006e007400750073002c0020006b006100730020006900720020007000690065006d01130072006f00740069002000640072006f016100610069002000620069007a006e00650073006100200064006f006b0075006d0065006e007400750020006100700073006b006100740065006900200075006e0020006400720075006b010101610061006e00610069002e00200049007a0076006500690064006f006a006900650074002000500044004600200064006f006b0075006d0065006e007400750073002c0020006b006f002000760061007200200061007400760113007200740020006100720020004100630072006f00620061007400200075006e002000410064006f00620065002000520065006100640065007200200035002e0030002c0020006b0101002000610072012b00200074006f0020006a00610075006e0101006b0101006d002000760065007200730069006a0101006d002e>
/NLD (Gebruik deze instellingen om Adobe PDF-documenten te maken waarmee zakelijke documenten betrouwbaar kunnen worden weergegeven en afgedrukt. De gemaakte PDF-documenten kunnen worden geopend met Acrobat en Adobe Reader 5.0 en hoger.)
/NOR <FEFF004200720075006b00200064006900730073006500200069006e006e007300740069006c006c0069006e00670065006e0065002000740069006c002000e50020006f0070007000720065007400740065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e00740065007200200073006f006d002000650072002000650067006e0065007400200066006f00720020007000e5006c006900740065006c006900670020007600690073006e0069006e00670020006f00670020007500740073006b007200690066007400200061007600200066006f0072007200650074006e0069006e006700730064006f006b0075006d0065006e007400650072002e0020005000440046002d0064006f006b0075006d0065006e00740065006e00650020006b0061006e002000e50070006e00650073002000690020004100630072006f00620061007400200065006c006c00650072002000410064006f00620065002000520065006100640065007200200035002e003000200065006c006c00650072002e>
/POL <FEFF0055007300740061007700690065006e0069006100200064006f002000740077006f0072007a0065006e0069006100200064006f006b0075006d0065006e007400f300770020005000440046002000700072007a0065007a006e00610063007a006f006e00790063006800200064006f0020006e00690065007a00610077006f0064006e00650067006f002000770079015b0077006900650074006c0061006e00690061002000690020006400720075006b006f00770061006e0069006100200064006f006b0075006d0065006e007400f300770020006600690072006d006f0077007900630068002e002000200044006f006b0075006d0065006e0074007900200050004400460020006d006f017c006e00610020006f007400770069006500720061010700200077002000700072006f006700720061006d006900650020004100630072006f00620061007400200069002000410064006f00620065002000520065006100640065007200200035002e0030002000690020006e006f00770073007a0079006d002e>
/PTB <FEFF005500740069006c0069007a006500200065007300730061007300200063006f006e00660069006700750072006100e700f50065007300200064006500200066006f0072006d00610020006100200063007200690061007200200064006f00630075006d0065006e0074006f0073002000410064006f00620065002000500044004600200061006400650071007500610064006f00730020007000610072006100200061002000760069007300750061006c0069007a006100e700e3006f002000650020006100200069006d0070007200650073007300e3006f00200063006f006e0066006900e1007600650069007300200064006500200064006f00630075006d0065006e0074006f007300200063006f006d0065007200630069006100690073002e0020004f007300200064006f00630075006d0065006e0074006f00730020005000440046002000630072006900610064006f007300200070006f00640065006d0020007300650072002000610062006500720074006f007300200063006f006d0020006f0020004100630072006f006200610074002000650020006f002000410064006f00620065002000520065006100640065007200200035002e0030002000650020007600650072007300f50065007300200070006f00730074006500720069006f007200650073002e>
/RUM <FEFF005500740069006c0069007a00610163006900200061006300650073007400650020007300650074010300720069002000700065006e007400720075002000610020006300720065006100200064006f00630075006d0065006e00740065002000410064006f006200650020005000440046002000610064006500630076006100740065002000700065006e007400720075002000760069007a00750061006c0069007a00610072006500610020015f006900200074006900700103007200690072006500610020006c0061002000630061006c006900740061007400650020007300750070006500720069006f0061007201030020006100200064006f00630075006d0065006e00740065006c006f007200200064006500200061006600610063006500720069002e002000200044006f00630075006d0065006e00740065006c00650020005000440046002000630072006500610074006500200070006f00740020006600690020006400650073006300680069007300650020006300750020004100630072006f006200610074002c002000410064006f00620065002000520065006100640065007200200035002e00300020015f00690020007600650072007300690075006e0069006c006500200075006c0074006500720069006f006100720065002e>
/SKY <FEFF0054006900650074006f0020006e006100730074006100760065006e0069006100200070006f0075017e0069007400650020006e00610020007600790074007600e100720061006e0069006500200064006f006b0075006d0065006e0074006f0076002000410064006f006200650020005000440046002000760068006f0064006e00fd006300680020006e0061002000730070006f013e00610068006c0069007600e90020007a006f006200720061007a006f00760061006e006900650020006100200074006c0061010d0020006f006200630068006f0064006e00fd0063006800200064006f006b0075006d0065006e0074006f0076002e00200056007900740076006f00720065006e00e900200064006f006b0075006d0065006e007400790020005000440046002000620075006400650020006d006f017e006e00e90020006f00740076006f00720069016500200076002000700072006f006700720061006d006f006300680020004100630072006f00620061007400200061002000410064006f00620065002000520065006100640065007200200035002e0030002000610020006e006f0076016100ed00630068002e>
/SLV <FEFF005400650020006e006100730074006100760069007400760065002000750070006f0072006100620069007400650020007a00610020007500730074007600610072006a0061006e006a006500200064006f006b0075006d0065006e0074006f0076002000410064006f006200650020005000440046002c0020007000720069006d00650072006e006900680020007a00610020007a0061006e00650073006c006a00690076006f0020006f0067006c00650064006f00760061006e006a006500200069006e0020007400690073006b0061006e006a006500200070006f0073006c006f0076006e0069006800200064006f006b0075006d0065006e0074006f0076002e00200020005500730074007600610072006a0065006e006500200064006f006b0075006d0065006e0074006500200050004400460020006a00650020006d006f0067006f010d00650020006f0064007000720065007400690020007a0020004100630072006f00620061007400200069006e002000410064006f00620065002000520065006100640065007200200035002e003000200069006e0020006e006f00760065006a01610069006d002e>
/SUO <FEFF004b00e40079007400e40020006e00e40069007400e4002000610073006500740075006b007300690061002c0020006b0075006e0020006c0075006f0074002000410064006f0062006500200050004400460020002d0064006f006b0075006d0065006e007400740065006a0061002c0020006a006f0074006b006100200073006f0070006900760061007400200079007200690074007900730061007300690061006b00690072006a006f006a0065006e0020006c0075006f00740065007400740061007600610061006e0020006e00e400790074007400e4006d0069007300650065006e0020006a0061002000740075006c006f007300740061006d0069007300650065006e002e0020004c0075006f0064007500740020005000440046002d0064006f006b0075006d0065006e00740069007400200076006f0069006400610061006e0020006100760061007400610020004100630072006f0062006100740069006c006c00610020006a0061002000410064006f00620065002000520065006100640065007200200035002e0030003a006c006c00610020006a006100200075007500640065006d006d0069006c006c0061002e>
/SVE <FEFF0041006e007600e4006e00640020006400650020006800e4007200200069006e0073007400e4006c006c006e0069006e006700610072006e00610020006f006d002000640075002000760069006c006c00200073006b006100700061002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e007400200073006f006d00200070006100730073006100720020006600f60072002000740069006c006c006600f60072006c00690074006c006900670020007600690073006e0069006e00670020006f006300680020007500740073006b007200690066007400650072002000610076002000610066006600e4007200730064006f006b0075006d0065006e0074002e002000200053006b006100700061006400650020005000440046002d0064006f006b0075006d0065006e00740020006b0061006e002000f600700070006e00610073002000690020004100630072006f0062006100740020006f00630068002000410064006f00620065002000520065006100640065007200200035002e00300020006f00630068002000730065006e006100720065002e>
/TUR <FEFF005400690063006100720069002000620065006c00670065006c006500720069006e0020006700fc00760065006e0069006c0069007200200062006900720020015f0065006b0069006c006400650020006700f6007200fc006e007400fc006c0065006e006d006500730069002000760065002000790061007a0064013100720131006c006d006100730131006e006100200075007900670075006e002000410064006f006200650020005000440046002000620065006c00670065006c0065007200690020006f006c0075015f007400750072006d0061006b0020006900e70069006e00200062007500200061007900610072006c0061007201310020006b0075006c006c0061006e0131006e002e00200020004f006c0075015f0074007500720075006c0061006e0020005000440046002000620065006c00670065006c0065007200690020004100630072006f006200610074002000760065002000410064006f00620065002000520065006100640065007200200035002e003000200076006500200073006f006e0072006100730131006e00640061006b00690020007300fc007200fc006d006c00650072006c00650020006100e70131006c006100620069006c00690072002e>
/UKR <FEFF04120438043a043e0440043804410442043e043204430439044204350020044604560020043f043004400430043c043504420440043800200434043b044f0020044104420432043e04400435043d043d044f00200434043e043a0443043c0435043d044204560432002000410064006f006200650020005000440046002c0020044f043a04560020043d04300439043a04400430044904350020043f045604340445043e0434044f0442044c00200434043b044f0020043d0430043404560439043d043e0433043e0020043f0435044004350433043b044f043404430020044204300020043404400443043a0443002004340456043b043e04320438044500200434043e043a0443043c0435043d044204560432002e00200020042104420432043e04400435043d045600200434043e043a0443043c0435043d0442043800200050004400460020043c043e0436043d04300020043204560434043a0440043804420438002004430020004100630072006f006200610074002004420430002000410064006f00620065002000520065006100640065007200200035002e0030002004300431043e0020043f04560437043d04560448043e04570020043204350440044104560457002e>
/RUS <FEFF04180441043f043e043b044c04370443043904420435002004340430043d043d044b04350020043d0430044104420440043e0439043a043800200434043b044f00200441043e043704340430043d0438044f00200434043e043a0443043c0435043d0442043e0432002000410064006f006200650020005000440046002c0020043f043e04340445043e0434044f04490438044500200434043b044f0020043d0430043404350436043d043e0433043e0020043f0440043e0441043c043e044204400430002004380020043f04350447043004420438002004340435043b043e0432044b044500200434043e043a0443043c0435043d0442043e0432002e002000200421043e043704340430043d043d044b04350020005000440046002d0434043e043a0443043c0435043d0442044b0020043c043e0436043d043e0020043e0442043a0440044b043204300442044c002004410020043f043e043c043e0449044c044e0020004100630072006f00620061007400200438002000410064006f00620065002000520065006100640065007200200035002e00300020043800200431043e043b043504350020043f043e04370434043d043804450020043204350440044104380439002e>
>>
/Namespace [
(Adobe)
(Common)
(1.0)
]
/OtherNamespaces [
<<
/AsReaderSpreads false
/CropImagesToFrames true
/ErrorControl /WarnAndContinue
/FlattenerIgnoreSpreadOverrides false
/IncludeGuidesGrids false
/IncludeNonPrinting false
/IncludeSlug false
/Namespace [
(Adobe)
(InDesign)
(4.0)
]
/OmitPlacedBitmaps false
/OmitPlacedEPS false
/OmitPlacedPDF false
/SimulateOverprint /Legacy
>>
<<
/AllowImageBreaks true
/AllowTableBreaks true
/ExpandPage false
/HonorBaseURL true
/HonorRolloverEffect false
/IgnoreHTMLPageBreaks false
/IncludeHeaderFooter false
/MarginOffset [
0
0
0
0
]
/MetadataAuthor ()
/MetadataKeywords ()
/MetadataSubject ()
/MetadataTitle ()
/MetricPageSize [
0
0
]
/MetricUnit /inch
/MobileCompatible 0
/Namespace [
(Adobe)
(GoLive)
(8.0)
]
/OpenZoomToHTMLFontSize false
/PageOrientation /Portrait
/RemoveBackground false
/ShrinkContent true
/TreatColorsAs /MainMonitorColors
/UseEmbeddedProfiles false
/UseHTMLTitleAsMetadata true
>>
<<
/AddBleedMarks false
/AddColorBars false
/AddCropMarks false
/AddPageInfo false
/AddRegMarks false
/BleedOffset [
0
0
0
0
]
/ConvertColors /ConvertToRGB
/DestinationProfileName (sRGB IEC61966-2.1)
/DestinationProfileSelector /UseName
/Downsample16BitImages true
/FlattenerPreset <<
/PresetSelector /MediumResolution
>>
/FormElements true
/GenerateStructure false
/IncludeBookmarks false
/IncludeHyperlinks false
/IncludeInteractive false
/IncludeLayers false
/IncludeProfiles true
/MarksOffset 6
/MarksWeight 0.250000
/MultimediaHandling /UseObjectSettings
/Namespace [
(Adobe)
(CreativeSuite)
(2.0)
]
/PDFXOutputIntentProfileSelector /DocumentCMYK
/PageMarksFile /RomanDefault
/PreserveEditing true
/UntaggedCMYKHandling /UseDocumentProfile
/UntaggedRGBHandling /LeaveUntagged
/UseDocumentBleed false
>>
]
>> setdistillerparams
<<
/HWResolution [600 600]
/PageSize [419.528 595.276]
>> setpagedevice
|
| id | nasplib_isofts_kiev_ua-123456789-48878 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | XXXX-0059 |
| language | Ukrainian |
| last_indexed | 2025-12-07T17:42:59Z |
| publishDate | 2012 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Ємець, О.О. Ємець, Є.М. Олексійчук, Ю.Ф. 2013-09-05T09:14:21Z 2013-09-05T09:14:21Z 2012 Жадібний метод розв’язання комбінаторної задачі знаходження максимального потоку в мережі / О.О. Ємець, Є.М. Ємець, Ю.Ф. Олексійчук // Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки: зб. наук. пр. — Кам’янець-Подільський: Кам'янець-Подільськ. нац. ун-т, 2012. — Вип. 7. — С. 93-99. — Бібліогр.: 12 назв. — укр. XXXX-0059 https://nasplib.isofts.kiev.ua/handle/123456789/48878 519.85 У статті розглядається комбінаторна задача знаходження максимального потоку в мережі, яка зводиться до задачі евклідової комбінаторної задачі на розміщеннях. Запропоновано наближений алгоритм для її розв’язання, визначена поліноміальна оцінка його складності. The combinatorial problem of finding of the maximal flow in a network is considered in the paper. This problem is a Euclidean combinatorial problem on arrangements. The approximate algorithm for solution of this problem is proposed. The polynomial estimation of complexity of this algorithm found. uk Інститут кібернетики ім. В.М. Глушкова НАН України Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки Жадібний метод розв’язання комбінаторної задачі знаходження максимального потоку в мережі Article published earlier |
| spellingShingle | Жадібний метод розв’язання комбінаторної задачі знаходження максимального потоку в мережі Ємець, О.О. Ємець, Є.М. Олексійчук, Ю.Ф. |
| title | Жадібний метод розв’язання комбінаторної задачі знаходження максимального потоку в мережі |
| title_full | Жадібний метод розв’язання комбінаторної задачі знаходження максимального потоку в мережі |
| title_fullStr | Жадібний метод розв’язання комбінаторної задачі знаходження максимального потоку в мережі |
| title_full_unstemmed | Жадібний метод розв’язання комбінаторної задачі знаходження максимального потоку в мережі |
| title_short | Жадібний метод розв’язання комбінаторної задачі знаходження максимального потоку в мережі |
| title_sort | жадібний метод розв’язання комбінаторної задачі знаходження максимального потоку в мережі |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/48878 |
| work_keys_str_mv | AT êmecʹoo žadíbniimetodrozvâzannâkombínatornoízadačíznahodžennâmaksimalʹnogopotokuvmereží AT êmecʹêm žadíbniimetodrozvâzannâkombínatornoízadačíznahodžennâmaksimalʹnogopotokuvmereží AT oleksíičukûf žadíbniimetodrozvâzannâkombínatornoízadačíznahodžennâmaksimalʹnogopotokuvmereží |