Розв'язування оптимизаційної задачі з дробово-лінійною цільовою функцією на комбінаторній конфігурації розміщень
Рассмотрены задача оптимизации с дробно-линейной функцией цели на комбинаторной конфигурации размещений и алгоритм решения таких задач на основе теории графов с учетом свойств и структуры множества размещений. Обосновано построение последовательности значений функции–ограничения, разложение точек ра...
Збережено в:
| Опубліковано в: : | Управляющие системы и машины |
|---|---|
| Дата: | 2014 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Українська |
| Опубліковано: |
Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
2014
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/83487 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Розв'язування оптимизаційної задачі з дробово-лінійною цільовою функцією на комбінаторній конфігурації розміщень / А.М. Нагірна // Управляющие системы и машины. — 2014. — № 4. — С. 48-54. — Бібліогр.: 8 назв. — укр., рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859854931950829568 |
|---|---|
| author | Нагірна, А.М. |
| author_facet | Нагірна, А.М. |
| citation_txt | Розв'язування оптимизаційної задачі з дробово-лінійною цільовою функцією на комбінаторній конфігурації розміщень / А.М. Нагірна // Управляющие системы и машины. — 2014. — № 4. — С. 48-54. — Бібліогр.: 8 назв. — укр., рос. |
| collection | DSpace DC |
| container_title | Управляющие системы и машины |
| description | Рассмотрены задача оптимизации с дробно-линейной функцией цели на комбинаторной конфигурации размещений и алгоритм решения таких задач на основе теории графов с учетом свойств и структуры множества размещений. Обосновано построение последовательности значений функции–ограничения, разложение точек размещения по подграфам графа согласно координатному методу на примере численного эксперимента.
The problem of optimization with a fractional-linear objective function on a combinatorial configuration placements is examened. The algorithm of solving such problems using graph theory, taking into account the properties and structure of the set of placements is analyzed. Building a sequence of functions-limit’s values, decomposition points of permutations on subgraphs polyhedra according to the coordinate method by the example of numerical experiment is justified.
Розглянуто задачу оптимізації з дробово-лінійною функцією цілі на комбінаторній конфігурації розміщень і алгоритм розв’язування даного типу задач на основі теорії графів з урахуванням властивостей та структури множини розміщень. Обґрунтовано побудову послідовності значень функції–обмеження, розкладання точок розміщення по підграфам графа згідно з координатним методом на прикладі числового експерименту.
|
| first_indexed | 2025-12-07T15:42:34Z |
| format | Article |
| fulltext |
48 УСиМ, 2014, № 4
Новые методы в информатике
УДК 519.8
А.М. Нагірна
Розв’язування оптимізаційної задачі з дробово-лінійною цільовою функцією
на комбінаторній конфігурації розміщень
Рассмотрены задача оптимизации с дробно-линейной функцией цели на комбинаторной конфигурации размещений и алго-
ритм решения таких задач на основе теории графов с учетом свойств и структуры множества размещений. Обосновано по-
строение последовательности значений функции–ограничения, разложение точек размещения по подграфам графа согласно
координатному методу на примере численного эксперимента.
The problem of optimization with a fractional-linear objective function on a combinatorial configuration placements is examened. The
algorithm of solving such problems using graph theory, taking into account the properties and structure of the set of placements is ana-
lyzed. Building a sequence of functions-limit’s values, decomposition points of permutations on subgraphs polyhedra according to the
coordinate method by the example of numerical experiment is justified.
Розглянуто задачу оптимізації з дробово-лінійною функцією цілі на комбінаторній конфігурації розміщень і алгоритм
розв’язування даного типу задач на основі теорії графів з урахуванням властивостей та структури множини розміщень. Обґру-
нтовано побудову послідовності значень функції–обмеження, розкладання точок розміщення по підграфам графа згідно з ко-
ординатним методом на прикладі числового експерименту.
Вступ. Велике зацікавлення спеціалістів викли-
кають математичні моделі з дробово-лінійними
функціями цілі, що зустрічаються в різних галу-
зях діяльності людини. Дробово-лінійна функція
характеризується відношенням двох лінійних
форм, тому її можна застосовувати в прикладних
задачах оптимізації деяких відносних показни-
ків, таких як рентабельність, трудомісткість, со-
бівартість, продуктивність і т.ін. [1–3].
При розгляді певного класу оптимізаційних
задач з дробово-лінійними функціями цілі до-
сить часто виникають припустимі розв’язки з
властивостями певних комбінаторних конфі-
гурацій: перестановок, розміщень, сполучень,
розбиттів. Тому необхідно розглянути нові
підходи до розв’язання такого класу задач з
урахуванням структурних властивостей комбі-
наторних множин, які забезпечують представ-
лення відповідної комбінаторної структури у
вигляді графа чи сітки. Дана властивість до-
зволяє за лічені кроки знайти розв’язання задачі
без повного перебору елементів відповідної
комбінаторної конфігурації [4–8].
Продовжуючи дослідження робіт [1, 2, 4–8],
розглянемо підхід до розв’язання оптимізацій-
ної задачі на конфігурації розміщень з дробо-
во-лінійною цільовою функцією, з подальшим
представленням конфігурації розміщень у ви-
гляді структурного графа.
Постановка задачі
Розглянемо задачу комбінаторної оптимізації,
у якій цільова функція ( )F x – дробово-лінійна ,
чисельник ( )f x і знаменник ( )g x – лінійні фун-
кції, в яких коефіцієнти визначаються за прави-
лом арифметичної прогресії:
1 ( 1)ic c i , 1 ( 1)id d i , (1)
припустима комбінаторна множина { }X x та
додаткові лінійні обмеження, які утворюють
опуклу многогранну множину nD R наступ-
ного вигляду: { | }nD x R Gx d , де m nG R ,
md R . Запишемо лінійні обмеження у вигляді
нерівностей:
1
n
ij j i
j
Gx g x d
, mi N , nj N . (2)
Необхідно знайти оптимальне розв’язання,
0x X , при якому цільова функція набуває ек-
стремального значення 0( ) extr ( )
x X
f x f X
, extr
{min,max} .
Як відомо з [4], для конфігурації перестано-
вок можна побудувати гамільтонів шлях усе-
УСиМ, 2014, № 4 49
редині кожної шестірки елементів перестанов-
ки і прослідкувати зміни значень цільової фун-
кції у вершинах графа на кожному з підграфів,
як і для лінійної функції.
Теорема 1 [4]. Граф перестановок ( )nG P для
дробово-лінійної функції ( )F x , коефіцієнти
якої визначені згідно (1), збігається з графом
перестановок для лінійної функції ( )nG P з точ-
ністю до орієнтації.
Теорема 2 [5]. Граф ( ( , ))G A n m конфігурації
розміщень ( , )A n m при n m і довільному век-
торі 1 2{ , ,..., }nA a a a
еквівалентний графу ( )nG P
комбінаторної конфігурації перестановок nP .
Отже, метод направленого структурування
можна застосувати до розв’язання задач з дро-
бово-лінійними функціями цілі та з лінійними
додатковими обмеженнями на комбінаторній
конфігурації розміщень.
Алгоритм розв’язання комбінаторної за-
дачі з дробово-лінійними функціями цілі та
лінійними додатковими обмеженнями на ком-
бінаторній конфігурації розміщень
К р о к 1. Задання дробово-лінійної функ-
ції цілі. На початковому етапі визначаються
коефіцієнти дробово-лінійної цільової функції
за формулою (1), відповідно для чисельника і
знаменника.
К р о к 2. Задання конфігурації розміщень.
Число конфігурацій графа конфігурації розмі-
щень ( , )A n m , m n , утвореного із елементів
{1, 2, ..., }n , розраховується за формулою m
nA
!/ ( )!n n m .
К р о к 3. Нормалізація. З урахуванням фор-
мули (1) дробово-лінійну функцію нормалізова-
но, тому слід визначити нормалізацію за допо-
могою вихідної перестановки u для кожної i-ї
обмежної функції gi [6]:
1 2 ...
2 1 ...i
m
m
u
. (3)
Тоді початкова множина розміщень заміню-
ється на базову за допомогою вихідної пере-
становки u , отримується індивідуальна мно-
жина розміщень iA , і відповідно для кожної
функції обмеження граф розміщень ( ( , ))G A n m
має стандартний вигляд.
К р о к 4. Розв’язання задачі локалізації [7].
Розв’язуючи задачу локалізації ig , mi N , от-
римуємо припустиму множину розміщень для
додаткового лінійного обмеження ig . За допо-
могою оберненої перестановки до (3) визнача-
ємо ту ж множину в базовій множині розмі-
щень ( ( , ))G A n m .
К р о к 5. Пошук розв’язків задачі. Знахо-
димо переріз множин розміщень обмежуваль-
них функцій та визначаємо множину розв’яз-
ків в базовій множині. Шляхом підстановки
відповідних вершин графа в дробово-лінійну
цільову функцію знаходимо необхідний екст-
ремум функції.
Розглянемо приклад застосування алгоритму.
Дано функцію ( )( )
( )
f xF x
g x
, де 1( )f x x
2 33 5x x , 1 2 3( ) 2 3 4g x x x x на множині роз-
міщень, сформовану з елементів А (1,2,3,4) .
Задано додаткові обмеження, що визначають
область припустимих значень цільової функції:
1 1 2 37 2 20g x x x , 2 14g x 2 37 35x x . Не-
обхідно знайти максимум цільової функції на
множині розміщень 3
4A .
Розв’язання. Задано нормалізовану цільову
функцію ( )F x . Тому граф G конфігурації роз-
міщень для такої функції має стандартний ви-
гляд (рис. 1), число конфігурацій 3
4 24A .
Нормалізуємо 1g шляхом перестановки
1
1 2 3
3 1 2
u
до вигляду 1 1 2 32 7 20g x x x .
Загальна структурна схема графу G розбива-
ється на структурні схеми підграфів 1G , 2G ,
3G , 4G , в крайніх вершинах яких визначають
мінімальне та максимальне значення функції
1g на підграфах.
Розв’язуючи задачу, необхідно враховувати,
що елементи множини розміщень мають задо-
вольняти умову 1 1 2 32 7 20g x x x . Згідно
рис. 2, підграф 1G не задовольняє обмеження,
50 УСиМ, 2014, № 4
а множини вершин підграфів 2G , 3G , 4G необ-
хідно розглянути детально.
4 2 3 4 3 2
3 4 2 2 4 3 2 3 4
3 2 4
3 4 1 1 4 3 1 3 4
3 1 4
6 4 2
5 3 1
11 9 7
8 10 12
19 21 23
18 16
14
17 15 13
4 1 3 4 3 1
1 2 4
2 1 4
1 4 2 2 4 1
4 1 2 4 2 1
2 3 1 1 3 2
2 1 3 3 1 2 3 2 1
1 2 3
20
22 24
Рис. 1. Стандартний вигляд графа конфігурації розміщень
1533
1735
2436
1426
(4,3,1)
(4,2,1)
(3,2,1)
(1,3,4)
(1,2,4)
(1,2,3)
(2,3,4) (4,3,2)
1G
2G
4G
3G
Рис. 2. Загальна структурна схема графу для 1g
Для вершин підграфа 2G значення 1g бу-
дуть наступні:
Т а б л и ц я 1
№ вершини 1x 2x 3x 1g
7 1 3 4 35
8 3 1 4 33
9 1 4 3 30
10 4 1 3 27
11 3 4 1 18
12 4 3 1 17
Згідно табл. 1, умову 1 1 2 32 7g x x x 20
задовольнятимуть вершини: 11, 12.
Побудуємо аналогічні таблиці для вершин
підграфів 3G , 4G .
Т а б л и ц я 2
№ вершини 1x 2x 3x 1g
13 1 2 4 33
14 2 1 4 32
15 1 4 2 23
16 4 1 2 20
17 2 4 1 17
18 4 2 1 15
Згідно табл. 2, обмеження 1 20g задоволь-
нятимуть вершини: 16, 17, 18.
Т а б л и ц я 3
№ вершини 1x 2x 3x 1g
19 1 2 3 26
20 2 1 3 25
21 1 3 2 21
22 3 1 2 19
23 2 3 1 15
24 3 2 1 14
Вершини 22, 23, 24 підграфа 4G задоволь-
няють умову обмеження (табл. 3).
Отже, припустима множина, що визначаєть-
ся обмеженням 1 20g , складатиметься із на-
ступних вершин: 11 (3,4,1)x , 12 (4,3,1)x ,
16 (4,1,2)x , 17 (2,4,1)x , 18 (4,2,1)x , 22x
(3,1,2) , 23 (2,3,1)x , 24 (3,2,1)x . Користую-
чись перестановкою нормалізації 1
1 2 3
3 1 2
u
,
знаходимо базову множину 1A : (1,3,4) , (1,4,3) ,
(2,4,1) , (1,2,4) , (1,4,2) , (2,3,1) , (1,2,3) , (1,3,2) .
Розглянемо обмежну функцію 2 1 23g x x
35 25x , в якій коефіцієнти розміщено в по-
рядку зростання, тому потреби в нормалізації не
виникає. Загальна структурна схема графу G
розбивається на структурні схеми підграфів 1G ,
G2, G3, G4 і матиме вигляд, зображений на рис. 3
1527
1830
2331
1422
(4,3,1)
( 4,2,1)
(3,2,1)
(1,3,4)
(1,2,4)
(1,2,3)
(2,3,4) (4,3,2)
1G
2G
4G
3G
Рис. 3. Загальна структурна схема графу для 2g
УСиМ, 2014, № 4 51
Для пошуку множини припустимих розв’яз-
ків, обмежених функцією 2 1 2 33 5 25,g x x x
розглянемо підграфи G1, G2, G3.
Розглянемо вершини підграфа 1G :
Т а б л и ц я 4
№ вершини 1x 2x 3x 2g
1 2 3 4 31
2 3 2 4 29
3 2 4 3 29
4 4 2 3 25
5 3 4 2 25
6 4 3 2 23
Згідно табл. 4, умову 2 25g задовольняти-
муть всі вершини підграфа G1, крім шостої.
Розглянемо вершини підграфа G2:
Т а б л и ц я 5
№ вершини 1x 2x 3x 2g
7 1 3 4 30
8 3 1 4 26
9 1 4 3 28
10 4 1 3 22
11 3 4 1 20
12 4 3 1 18
Згідно табл. 5, умову 2 1 2 33 5 25g x x x
задовольнятимуть вершини 7, 8, 9.
Побудуємо аналогічну таблицю для вершин
підграфа G3.
Вершини 13, 14 підграфа G4 задовольняють
умову обмеження (табл. 6).
Т а б л и ц я 6
№ вершини 1x 2x 3x 2g
13 1 2 4 27
14 2 1 4 25
15 1 4 2 23
16 4 1 2 17
17 2 4 1 19
18 4 2 1 15
Допустима множина 2A , що визначається об-
меженням 2 1 2 33 5 25g x x x , складатиметься
з наступних вершин: 1 (2,3,4)x , 2 (3,2,4)x ,
3 (2,4,3)x , 4 (4,2,3)x , 5 (3,4,2)x , 7 (1,3,4)x ,
8 (3,1,4)x , (1,4,3)x , 13 (1,2,4)x , 14 (2,1,4)x .
Отже, загальна множина розв’язків, яка
визначається перерізом припустимої множи-
ни першого та другого обмежень, дорівнює:
*
1 2( ) ( )A A g A g {(1,2,4);(1,3,4);(1,4,3)} . Зна-
чення цільових дробово-лінійних функцій в да-
них вершинах дорівнюють: max F(x) = F(1,2,4) =
= F(1,3,4) = F(1,4,3) = 1,1.
Висновки. Загальна схема алгоритму спря-
мованого структурування для комбінаторної
конфігурації розміщень полягає у використан-
ні властивості представлення многогранника
розміщень у вигляді структури графа і пода-
льшому пошуку розв’язків, які можуть бути
вершинами або ребрами відповідного графа.
Подальші дослідження будуть спрямовані
на створення нових підходів та алгоритмів за
умови нелінійності цільової функції та про-
грамній реалізації алгоритму для проведення
числових експериментів при збільшенні поту-
жності відповідної комбінаторної конфігурації.
1. Шор Н.З., Соломон Д.И. Декомпозиционные мето-
ды в дробно-линейном программировании . – Ки-
шенев: Штиинца, 1989. – 204 с.
2. Семенова Н.В., Колечкина Л.Н., Нагорная А.Н. Роз-
в’язування задач векторної оптимізації з дробово-
лінійними функціями критеріїв на комбінаторній
множині полірозміщень // Наук. вісті НТУУ «КПІ». –
2009. – № 2. – С. 53–60.
3. Семенова Н.В., Колечкина Л.Н., Нагорная А.Н. Об
одном подходе к решению векторных задач с дробно-
линейными функциями критериев на комбинаторном
множестве размещений // Проблемы управления и
информатики. – 2010. – № 1. – С. 131–144.
4. Донец Г.А., Колечкина Л.Н. Об одной задаче опти-
мизации дробно-линейной функции цели на пере-
становках // Там же. − № 2. – С. 12−16.
5. Емеличев В.А., Ковалев М.М., Кравцов М.К. Много-
гранники, графы, оптимизация. – М.: Наука, 1981. –
344 с.
6. Донец Г.А., Колечкина Л.Н. Об одном подходе к
решению комбинаторной задачи оптимизации на
графах / УСиМ. – 2009. − № 4. – С. 36−42.
7. Донец Г.А., Колечкина Л.Н. Построение гамильто-
нова пути в графах перестановочных многогранни-
ков // Кибернетика и системный анализ. – 2010. –
№ 1. – С. 10–16.
8. Донец Г.А., Колечкина Л.Н. Алгоритм поиска зна-
чений линейной функции на лексикографически
упорядоченных перестановках // Теорія оптималь-
них рішень. – 2009. – № 8. – С. 3−8.
Поступила 03.07.2014
Тел. для справок: +38 050 192-1433 (Киев)
E-mail: vpn2006@rambler.ru
© А.Н. Нагорная, 2014
52 УСиМ, 2014, № 4
А.Н. Нагорная
Решение оптимизационной задачи с дробно-линейной целевой функцией
на комбинаторной конфигурации размещений
Введение. Особый интерес для специалистов представ-
ляют математические модели с дробно-линейными
функциями цели, встречающиеся в различных областях
деятельности человека. Дробно-линейная функция ха-
рактеризуется отношением двух линейных форм, по-
этому ее можно применять в прикладных задачах опти-
мизации некоторых относительных показателей в каче-
стве таких, как рентабельность, трудоемкость, себе-
стоимость, производительность и др. [1–3].
При рассмотрении определенного класса оптимизаци-
онных задач с дробно-линейными функциями цели часто
возникают допустимые решения со свойствами опреде-
ленных комбинаторных конфигураций: перестановок, раз-
мещений, сочетаний, разбиений. Поэтому необходимо рас-
смотреть новые подходы к решению такого класса задач с
учетом структурных свойств комбинаторных множеств,
обеспечивающих представление соответствующей комби-
наторной структуры в виде графа или сетки. Данное свой-
ство позволяет за считанные шаги найти решение задачи
без полного перебора элементов соответствующей комби-
наторной конфигурации [4–8].
Продолжая исследования работ [1, 2, 4–8], рассмот-
рим подход к решению оптимизационной задачи на
конфигурации размещений с дробно-линейной целевой
функцией, с последующим представлением конфигура-
ции размещений в виде структурного графа.
Постановка задачи
Рассмотрим задачу комбинаторной оптимизации, в
которой целевая функция F (x) – дробно-линейная, чис-
литель f (x) и знаменатель g (x) – линейные функции, в
которых коэффициенты определяются по правилу
арифметической прогрессии:
1 ( 1)ic c i , 1 ( 1)id d i , (1)
допустимое комбинаторное множество { }X x и до-
полнительные линейные ограничения, образующие вы-
пуклое многогранное множество nD R следующего
вида: { | }nD x R Gx d , где m nG R , md R . За-
пишем линейные ограничения в виде неравенств:
1
n
ij j i
j
Gx g x d
, mi N , nj N . (2)
Необходимо найти оптимальное решение, x0 X, при
котором целевая функция принимает экстремальное
значение 0( ) extr ( )
x X
f x f X
, extr min, max .
Как известно из [4], для конфигурации перестановок
можно построить гамильтонов путь внутри каждой шес-
терки элементов перестановки и проследить изменения
значений целевой функции в вершинах графа на каждом
из подграфов, как и для линейной функции.
Теорема 1 [4]. Граф перестановок ( )nG P для дробно-
линейной функции ( )F x , коэффициенты которой опреде-
ляются согласно (1), совпадает с графом перестановок для
линейной функции ( )nG P с точностью до ориентации.
Теорема 2 [5]. Граф ( ( , ))G A n m конфигурации разме-
щений ( , )A n m при n m и произвольном векторе
1 2{ , ,..., }nA a a a
эквивалентен графу ( )nG P комбинатор-
ной конфигурации перестановок nP .
Итак, метод направленного структурирования можно
применить к решению задач с дробно-линейными функ-
циями цели и с линейными дополнительными ограниче-
ниями на комбинаторной конфигурации размещений.
Алгоритм решения комбинаторной задачи с дроб-
но-линейными функциями цели и линейными дополни-
тельными ограничениями на комбинаторной конфигу-
рации размещений.
Ш а г 1. Определение дробно-линейной функции це-
ли. На начальном этапе определяются коэффициенты
дробно-линейной целевой функции по формуле (1) со-
ответственно для числителя и знаменателя.
Ш а г 2. Задание конфигурации размещений. Число
конфигураций графа конфигурации размещений ( , )A n m ,
m n , созданного из элементов {1,2,..., }n , рассчитывается
по формуле !/ ( )!m
nA n n m .
Ш а г 3. Нормализация. С учетом формулы (1) дроб-
но-линейная функция нормализована, поэтому следует
определить нормализацию по исходной перестановке u
для каждого i-го ограничения функции g2 [6]:
1 2 ...
2 1 ...i
m
m
u
. (3)
Тогда начальное множество размещений заменяется
на базовое по исходной перестановке u, получается ин-
дивидуальное множество размещений iA и соответ-
ственно для каждой функции ограничения граф разме-
щений ( ( , ))G A n m имеет стандартный вид.
Ш а г 4. Решение задачи локализации [7]. Решая
задачу локализации ig , mi N , получаем допустимое
множество размещений для дополнительного линейного
ограничения ig . Путем обратной перестановки в (3)
определяем то же множество в базовом множестве раз-
мещений ( ( , ))G A n m .
Ш а г 5. Поиск решений задачи. Находим сечение
множеств размещений ограничивающих функций и оп-
ределяем множество решений в базовом множестве.
Подставив соответствующие вершины графа в дробно-
линейную целевую функцию, находим требуемый экс-
тремум функции.
УСиМ, 2014, № 4 53
Рассмотрим пример применения алгоритма.
Дана функция ( )( )
( )
f xF x
g x
, где 1 2 3( ) 3 5f x x x x ,
1 2 3( ) 2 3 4g x x x x на множестве размещений, сфор-
мированную из элементов А = (1, 2, 3, 4). Заданы допол-
нительные ограничения, определяющие область допус-
тимых значений целевой функции: 1 1 2 37 2g x x x
20, 2 1 2 34 7 35g x x x . Необходимо найти макси-
мум целевой функции на множестве размещений 3
4A .
Решение. Задана нормализованная целевая функция
( )F x . Поэтому граф G конфигурации размещений для
такой функции имеет стандартный вид (рис. 1), число
конфигураций 3
4 24A .
4 2 3 4 3 2
3 4 2 2 4 3 2 3 4
3 2 4
3 4 1 1 4 3 1 3 4
3 1 4
6 4 2
5 3 1
11 9 7
8 10 12
19 21 23
18 16
14
17 15 13
4 1 3 4 3 1
1 2 4
2 1 4
1 4 2 2 4 1
4 1 2 4 2 1
2 3 1 1 3 2
2 1 3 3 1 2 3 2 1
1 2 3
20
22 24
Рис. 1. Стандартный вид графа конфигурации размещений
Нормализуем 1g путем перестановки 1
1 2 3
3 1 2
u
к виду 1 1 2 32 7 20g x x x . Общая структурная схе-
ма графа G разбивается на структурные схемы подгра-
фов 1G , 2G , 3G , 4G , в крайних вершинах которых опре-
деляют минимальное и максимальное значения функции
1g на подграфах.
Решая задачу, необходимо учитывать, что элемен-
ты множества размещений должны удовлетворять
условию 1 1 2 32 7 20g x x x . Согласно рис. 2, под-
граф 1G не удовлетворяет ограничениям, а множества
вершин подграфов 2G , 3G , 4G необходимо рассмот-
реть детально.
1533
1735
2436
1426
(4,3,1)
( 4,2,1)
(3,2,1)
(1,3,4)
(1,2,4)
(1,2,3)
(2,3,4) (4,3,2)
1G
2G
4G
3G
Рис. 2. Общая структурная схема графа для 1g
Для вершин подграфа G2 значения 1g будут сле-
дующими:
Т а б л и ц а 1
№ вершины 1x 2x 3x 1g
7 1 3 4 35
8 3 1 4 33
9 1 4 3 30
10 4 1 3 27
11 3 4 1 18
12 4 3 1 17
Согласно табл. 1, условию 1 1 2 32 7 20g x x x будут
удовлетворять вершины: 11, 12.
Построим аналогичные таблицы для вершин подгра-
фов G3, G4.
Т а б л и ц а 2
№ вершины 1x 2x 3x 1g
13 1 2 4 33
14 2 1 4 32
15 1 4 2 23
16 4 1 2 20
17 2 4 1 17
18 4 2 1 15
Согласно табл. 2, ограничению 1 20g будут удовле-
творять вершины: 16, 17, 18.
Вершины 22, 23, 24 подграфа 4G удовлетворяют ус-
ловию ограничения (табл. 3).
Т а б л и ц а 3
№ вершины 1x 2x 3x 1g
19 1 2 3 26
20 2 1 3 25
21 1 3 2 21
22 3 1 2 19
23 2 3 1 15
24 3 2 1 14
Итак, допустимое множество, определяемое ограни-
чением 1 20g , будет состоять из следующих вершин:
11 (3,4,1)x , 12 (4,3,1)x , 16 (4,1, 2)x , 17 (2,4,1)x ,
18 (4,2,1)x , 22 (3,1, 2)x , 23 (2,3,1)x , 24 (3,2,1)x .
54 УСиМ, 2014, № 4
Пользуясь перестановкой нормализации 1
1 2 3
3 1 2
u
,
находим базовое множество 1A : (1,3,4), (1,4,3), (2,4,1),
(1,2,4), (1,4,2), (2,3,1), (1,2,3), (1,3,2).
Рассмотрим ограничивающую функцию 2 1g x
2 33 5 25x x , в которой коэффициенты размещены в
порядке возрастания, поэтому потребности в нормали-
зации не возникает. Общая структурная схема графа G
разбивается на структурные схемы подграфов G1, G2, G3,
G4, и будет иметь вид, изображенный на рис. 3
1527
1830
2331
1422
(4,3,1)
(4,2,1)
(3,2,1)
(1,3,4)
(1,2,4)
(1,2,3)
(2,3,4) (4,3,2)
1G
2G
4G
3G
Рис. 3. Общая структурная схема графа для g2
Для поиска множества допустимых решений, кото-
рые ограничиваются функцией 2 1 2 33 5 25g x x x ,
рассмотрим подграфы G1, G2, G3.
Рассмотрим вершины подграфа G1:
Т а б л и ц а 4
№ вершины 1x 2x 3x 2g
1 2 3 4 31
2 3 2 4 29
3 2 4 3 29
4 4 2 3 25
5 3 4 2 25
6 4 3 2 23
Согласно табл. 4, условию g2 25 будут удовлетво-
рять все вершины подграфа G1, кроме шестой.
Рассмотрим вершины подграфа G2:
Т а б л и ц а 5
№ вершины 1x 2x 3x 2g
7 1 3 4 30
8 3 1 4 26
9 1 4 3 28
10 4 1 3 22
11 3 4 1 20
12 4 3 1 18
Согласно табл. 5, условию g2 = x1 + 3x2 + 5x3 25 бу-
дут удовлетворять вершины 7, 8, 9.
Построим аналогичную таблицу для вершин подгра-
фа G3.
Т а б л и ц а 6
№ вершины 1x 2x 3x 2g
13 1 2 4 27
14 2 1 4 25
15 1 4 2 23
16 4 1 2 17
17 2 4 1 19
18 4 2 1 15
Вершины 13, 14 подграфа G4 удовлетворяют усло-
вию ограничения (табл. 6).
Допустимое множество 2A , определяемое ограниче-
нием 2 1 2 33 5 25g x x x , будет состоять из сле-
дующих вершин: 1 (2,3,4),x 2 (3,2,4),x 3 (2,4,3),x
4 (4,2,3)x , 5 (3, 4, 2)x , 7 (1,3, 4)x , 8 (3,1,4)x ,
(1, 4,3)x , 13 (1,2,4)x , 14 (2,1, 4)x .
Итак, общее множество решений, определяемых сече-
нием допустимого множества первого и второго ограни-
чений, равно: *
1 2( ) ( )A A g A g {(1,2,4);(1,3,4); (1,4,3)}.
Значение целевых дробно-линейных функций в данных
точках равно: max ( ) (1,2,4) (1,3,4)F x F F (1,4,3) 1,1F .
Заключение. Общая схема алгоритма направлен-
ного структурирования для комбинаторной конфигу-
рации размещений заключается в использовании
свойства представления многогранника размещений в
виде структуры графа и дальнейшем поиске решений,
которые могут быть вершинами или ребрами соот-
ветствующего графа.
Дальнейшие исследования будут направлены на
создание новых подходов и алгоритмов при условии
нелинейности целевой функции и программной реа-
лизации алгоритма для проведения численных экспе-
риментов при увеличении мощности соответствую-
щей комбинаторной конфигурации.
<<
/ASCII85EncodePages false
/AllowTransparency false
/AutoPositionEPSFiles true
/AutoRotatePages /None
/Binding /Left
/CalGrayProfile (Dot Gain 20%)
/CalRGBProfile (sRGB IEC61966-2.1)
/CalCMYKProfile (U.S. Web Coated \050SWOP\051 v2)
/sRGBProfile (sRGB IEC61966-2.1)
/CannotEmbedFontPolicy /Error
/CompatibilityLevel 1.4
/CompressObjects /Tags
/CompressPages true
/ConvertImagesToIndexed true
/PassThroughJPEGImages true
/CreateJobTicket false
/DefaultRenderingIntent /Default
/DetectBlends true
/DetectCurves 0.0000
/ColorConversionStrategy /CMYK
/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 true
/PreserveFlatness true
/PreserveHalftoneInfo false
/PreserveOPIComments true
/PreserveOverprintSettings true
/StartPage 1
/SubsetFonts true
/TransferFunctionInfo /Apply
/UCRandBGInfo /Preserve
/UsePrologue false
/ColorSettingsFile ()
/AlwaysEmbed [ true
]
/NeverEmbed [ true
]
/AntiAliasColorImages false
/CropColorImages true
/ColorImageMinResolution 300
/ColorImageMinResolutionPolicy /OK
/DownsampleColorImages true
/ColorImageDownsampleType /Bicubic
/ColorImageResolution 300
/ColorImageDepth -1
/ColorImageMinDownsampleDepth 1
/ColorImageDownsampleThreshold 1.50000
/EncodeColorImages true
/ColorImageFilter /DCTEncode
/AutoFilterColorImages true
/ColorImageAutoFilterStrategy /JPEG
/ColorACSImageDict <<
/QFactor 0.15
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/ColorImageDict <<
/QFactor 0.15
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/JPEG2000ColorACSImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/JPEG2000ColorImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/AntiAliasGrayImages false
/CropGrayImages true
/GrayImageMinResolution 300
/GrayImageMinResolutionPolicy /OK
/DownsampleGrayImages true
/GrayImageDownsampleType /Bicubic
/GrayImageResolution 300
/GrayImageDepth -1
/GrayImageMinDownsampleDepth 2
/GrayImageDownsampleThreshold 1.50000
/EncodeGrayImages true
/GrayImageFilter /DCTEncode
/AutoFilterGrayImages true
/GrayImageAutoFilterStrategy /JPEG
/GrayACSImageDict <<
/QFactor 0.15
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/GrayImageDict <<
/QFactor 0.15
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/JPEG2000GrayACSImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/JPEG2000GrayImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/AntiAliasMonoImages false
/CropMonoImages true
/MonoImageMinResolution 1200
/MonoImageMinResolutionPolicy /OK
/DownsampleMonoImages true
/MonoImageDownsampleType /Bicubic
/MonoImageResolution 1200
/MonoImageDepth -1
/MonoImageDownsampleThreshold 1.50000
/EncodeMonoImages true
/MonoImageFilter /CCITTFaxEncode
/MonoImageDict <<
/K -1
>>
/AllowPSXObjects false
/CheckCompliance [
/None
]
/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 ()
/PDFXOutputConditionIdentifier ()
/PDFXOutputCondition ()
/PDFXRegistryName ()
/PDFXTrapped /False
/CreateJDFFile false
/Description <<
/ARA <FEFF06270633062A062E062F0645002006470630064700200627064406250639062F0627062F0627062A002006440625064606340627062100200648062B062706260642002000410064006F00620065002000500044004600200645062A064806270641064206290020064406440637062806270639062900200641064A00200627064406450637062706280639002006300627062A0020062F0631062C0627062A002006270644062C0648062F0629002006270644063906270644064A0629061B0020064A06450643064600200641062A062D00200648062B0627062606420020005000440046002006270644064506460634062306290020062806270633062A062E062F062706450020004100630072006F0062006100740020064800410064006F006200650020005200650061006400650072002006250635062F0627063100200035002E0030002006480627064406250635062F062706310627062A0020062706440623062D062F062B002E0635062F0627063100200035002E0030002006480627064406250635062F062706310627062A0020062706440623062D062F062B002E>
/BGR <FEFF04180437043f043e043b043704320430043904420435002004420435043704380020043d0430044104420440043e0439043a0438002c00200437043000200434043000200441044a0437043404300432043004420435002000410064006f00620065002000500044004600200434043e043a0443043c0435043d04420438002c0020043c0430043a04410438043c0430043b043d043e0020043f044004380433043e04340435043d04380020043704300020043204380441043e043a043e043a0430044704350441044204320435043d0020043f04350447043004420020043704300020043f044004350434043f0435044704300442043d04300020043f043e04340433043e0442043e0432043a0430002e002000200421044a04370434043004340435043d043804420435002000500044004600200434043e043a0443043c0435043d044204380020043c043e0433043004420020043404300020044104350020043e0442043204300440044f0442002004410020004100630072006f00620061007400200438002000410064006f00620065002000520065006100640065007200200035002e00300020043800200441043b0435043404320430044904380020043204350440044104380438002e>
/CHS <FEFF4f7f75288fd94e9b8bbe5b9a521b5efa7684002000410064006f006200650020005000440046002065876863900275284e8e9ad88d2891cf76845370524d53705237300260a853ef4ee54f7f75280020004100630072006f0062006100740020548c002000410064006f00620065002000520065006100640065007200200035002e003000204ee553ca66f49ad87248672c676562535f00521b5efa768400200050004400460020658768633002>
/CHT <FEFF4f7f752890194e9b8a2d7f6e5efa7acb7684002000410064006f006200650020005000440046002065874ef69069752865bc9ad854c18cea76845370524d5370523786557406300260a853ef4ee54f7f75280020004100630072006f0062006100740020548c002000410064006f00620065002000520065006100640065007200200035002e003000204ee553ca66f49ad87248672c4f86958b555f5df25efa7acb76840020005000440046002065874ef63002>
/CZE <FEFF005400610074006f0020006e006100730074006100760065006e00ed00200070006f0075017e0069006a007400650020006b0020007600790074007600e101590065006e00ed00200064006f006b0075006d0065006e0074016f002000410064006f006200650020005000440046002c0020006b00740065007200e90020007300650020006e0065006a006c00e90070006500200068006f006400ed002000700072006f0020006b00760061006c00690074006e00ed0020007400690073006b00200061002000700072006500700072006500730073002e002000200056007900740076006f01590065006e00e900200064006f006b0075006d0065006e007400790020005000440046002000620075006400650020006d006f017e006e00e90020006f007400650076015900ed007400200076002000700072006f006700720061006d0065006300680020004100630072006f00620061007400200061002000410064006f00620065002000520065006100640065007200200035002e0030002000610020006e006f0076011b006a016100ed00630068002e>
/DAN <FEFF004200720075006700200069006e0064007300740069006c006c0069006e006700650072006e0065002000740069006c0020006100740020006f007000720065007400740065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e007400650072002c0020006400650072002000620065006400730074002000650067006e006500720020007300690067002000740069006c002000700072006500700072006500730073002d007500640073006b007200690076006e0069006e00670020006100660020006800f8006a0020006b00760061006c0069007400650074002e0020004400650020006f007000720065007400740065006400650020005000440046002d0064006f006b0075006d0065006e0074006500720020006b0061006e002000e50062006e00650073002000690020004100630072006f00620061007400200065006c006c006500720020004100630072006f006200610074002000520065006100640065007200200035002e00300020006f00670020006e0079006500720065002e>
/DEU <FEFF00560065007200770065006e00640065006e0020005300690065002000640069006500730065002000450069006e007300740065006c006c0075006e00670065006e0020007a0075006d002000450072007300740065006c006c0065006e00200076006f006e002000410064006f006200650020005000440046002d0044006f006b0075006d0065006e00740065006e002c00200076006f006e002000640065006e0065006e002000530069006500200068006f006300680077006500720074006900670065002000500072006500700072006500730073002d0044007200750063006b0065002000650072007a0065007500670065006e0020006d00f60063006800740065006e002e002000450072007300740065006c006c007400650020005000440046002d0044006f006b0075006d0065006e007400650020006b00f6006e006e0065006e0020006d006900740020004100630072006f00620061007400200075006e0064002000410064006f00620065002000520065006100640065007200200035002e00300020006f0064006500720020006800f600680065007200200067006500f600660066006e00650074002000770065007200640065006e002e>
/ESP <FEFF005500740069006c0069006300650020006500730074006100200063006f006e0066006900670075007200610063006900f3006e0020007000610072006100200063007200650061007200200064006f00630075006d0065006e0074006f00730020005000440046002000640065002000410064006f0062006500200061006400650063007500610064006f00730020007000610072006100200069006d0070007200650073006900f3006e0020007000720065002d0065006400690074006f007200690061006c00200064006500200061006c00740061002000630061006c0069006400610064002e002000530065002000700075006500640065006e00200061006200720069007200200064006f00630075006d0065006e0074006f00730020005000440046002000630072006500610064006f007300200063006f006e0020004100630072006f006200610074002c002000410064006f00620065002000520065006100640065007200200035002e003000200079002000760065007200730069006f006e0065007300200070006f00730074006500720069006f007200650073002e>
/ETI <FEFF004b00610073007500740061006700650020006e0065006900640020007300e4007400740065006900640020006b00760061006c006900740065006500740073006500200074007200fc006b006900650065006c007300650020007000720069006e00740069006d0069007300650020006a0061006f006b007300200073006f00620069006c0069006b0065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e00740069006400650020006c006f006f006d006900730065006b0073002e00200020004c006f006f0064007500640020005000440046002d0064006f006b0075006d0065006e00740065002000730061006100740065002000610076006100640061002000700072006f006700720061006d006d006900640065006700610020004100630072006f0062006100740020006e0069006e0067002000410064006f00620065002000520065006100640065007200200035002e00300020006a00610020007500750065006d006100740065002000760065007200730069006f006f006e00690064006500670061002e000d000a>
/FRA <FEFF005500740069006c006900730065007a00200063006500730020006f007000740069006f006e00730020006100660069006e00200064006500200063007200e900650072002000640065007300200064006f00630075006d0065006e00740073002000410064006f00620065002000500044004600200070006f0075007200200075006e00650020007100750061006c0069007400e90020006400270069006d007000720065007300730069006f006e00200070007200e9007000720065007300730065002e0020004c0065007300200064006f00630075006d0065006e00740073002000500044004600200063007200e900e90073002000700065007500760065006e0074002000ea0074007200650020006f007500760065007200740073002000640061006e00730020004100630072006f006200610074002c002000610069006e00730069002000710075002700410064006f00620065002000520065006100640065007200200035002e0030002000650074002000760065007200730069006f006e007300200075006c007400e90072006900650075007200650073002e>
/GRE <FEFF03a703c103b703c303b903bc03bf03c003bf03b903ae03c303c403b5002003b103c503c403ad03c2002003c403b903c2002003c103c503b803bc03af03c303b503b903c2002003b303b903b1002003bd03b1002003b403b703bc03b903bf03c503c103b303ae03c303b503c403b5002003ad03b303b303c103b103c603b1002000410064006f006200650020005000440046002003c003bf03c5002003b503af03bd03b103b9002003ba03b103c42019002003b503be03bf03c703ae03bd002003ba03b103c403ac03bb03bb03b703bb03b1002003b303b903b1002003c003c103bf002d03b503ba03c403c503c003c903c403b903ba03ad03c2002003b503c103b303b103c303af03b503c2002003c503c803b703bb03ae03c2002003c003bf03b903cc03c403b703c403b103c2002e0020002003a403b10020005000440046002003ad03b303b303c103b103c603b1002003c003bf03c5002003ad03c703b503c403b5002003b403b703bc03b903bf03c503c103b303ae03c303b503b9002003bc03c003bf03c103bf03cd03bd002003bd03b1002003b103bd03bf03b903c703c403bf03cd03bd002003bc03b5002003c403bf0020004100630072006f006200610074002c002003c403bf002000410064006f00620065002000520065006100640065007200200035002e0030002003ba03b103b9002003bc03b503c403b103b303b503bd03ad03c303c403b503c103b503c2002003b503ba03b403cc03c303b503b903c2002e>
/HEB <FEFF05D405E905EA05DE05E905D5002005D105D405D205D305E805D505EA002005D005DC05D4002005DB05D305D9002005DC05D905E605D505E8002005DE05E105DE05DB05D9002000410064006F006200650020005000440046002005D405DE05D505EA05D005DE05D905DD002005DC05D405D305E405E105EA002005E705D305DD002D05D305E405D505E1002005D005D905DB05D505EA05D905EA002E002005DE05E105DE05DB05D90020005000440046002005E905E005D505E605E805D5002005E005D905EA05E005D905DD002005DC05E405EA05D905D705D4002005D105D005DE05E605E205D505EA0020004100630072006F006200610074002005D5002D00410064006F00620065002000520065006100640065007200200035002E0030002005D505D205E805E105D005D505EA002005DE05EA05E705D305DE05D505EA002005D905D505EA05E8002E05D005DE05D905DD002005DC002D005000440046002F0058002D0033002C002005E205D905D905E005D5002005D105DE05D305E805D905DA002005DC05DE05E905EA05DE05E9002005E905DC0020004100630072006F006200610074002E002005DE05E105DE05DB05D90020005000440046002005E905E005D505E605E805D5002005E005D905EA05E005D905DD002005DC05E405EA05D905D705D4002005D105D005DE05E605E205D505EA0020004100630072006F006200610074002005D5002D00410064006F00620065002000520065006100640065007200200035002E0030002005D505D205E805E105D005D505EA002005DE05EA05E705D305DE05D505EA002005D905D505EA05E8002E>
/HRV (Za stvaranje Adobe PDF dokumenata najpogodnijih za visokokvalitetni ispis prije tiskanja koristite ove postavke. Stvoreni PDF dokumenti mogu se otvoriti Acrobat i Adobe Reader 5.0 i kasnijim verzijama.)
/HUN <FEFF004b0069007600e1006c00f30020006d0069006e0151007300e9006701710020006e0079006f006d00640061006900200065006c0151006b00e90073007a00ed007401510020006e0079006f006d00740061007400e100730068006f007a0020006c006500670069006e006b00e1006200620020006d0065006700660065006c0065006c0151002000410064006f00620065002000500044004600200064006f006b0075006d0065006e00740075006d006f006b0061007400200065007a0065006b006b0065006c0020006100200062006500e1006c006c00ed007400e10073006f006b006b0061006c0020006b00e90073007a00ed0074006800650074002e0020002000410020006c00e90074007200650068006f007a006f00740074002000500044004600200064006f006b0075006d0065006e00740075006d006f006b00200061007a0020004100630072006f006200610074002000e9007300200061007a002000410064006f00620065002000520065006100640065007200200035002e0030002c0020007600610067007900200061007a002000610074007400f3006c0020006b00e9007301510062006200690020007600650072007a006900f3006b006b0061006c0020006e00790069007400680061007400f3006b0020006d00650067002e>
/ITA <FEFF005500740069006c0069007a007a006100720065002000710075006500730074006500200069006d0070006f007300740061007a0069006f006e00690020007000650072002000630072006500610072006500200064006f00630075006d0065006e00740069002000410064006f00620065002000500044004600200070006900f900200061006400610074007400690020006100200075006e00610020007000720065007300740061006d0070006100200064006900200061006c007400610020007100750061006c0069007400e0002e0020004900200064006f00630075006d0065006e007400690020005000440046002000630072006500610074006900200070006f00730073006f006e006f0020006500730073006500720065002000610070006500720074006900200063006f006e0020004100630072006f00620061007400200065002000410064006f00620065002000520065006100640065007200200035002e003000200065002000760065007200730069006f006e006900200073007500630063006500730073006900760065002e>
/JPN <FEFF9ad854c18cea306a30d730ea30d730ec30b951fa529b7528002000410064006f0062006500200050004400460020658766f8306e4f5c6210306b4f7f75283057307e305930023053306e8a2d5b9a30674f5c62103055308c305f0020005000440046002030d530a130a430eb306f3001004100630072006f0062006100740020304a30883073002000410064006f00620065002000520065006100640065007200200035002e003000204ee5964d3067958b304f30533068304c3067304d307e305930023053306e8a2d5b9a306b306f30d530a930f330c8306e57cb30818fbc307f304c5fc59808306730593002>
/KOR <FEFFc7740020c124c815c7440020c0acc6a9d558c5ec0020ace0d488c9c80020c2dcd5d80020c778c1c4c5d00020ac00c7a50020c801d569d55c002000410064006f0062006500200050004400460020bb38c11cb97c0020c791c131d569b2c8b2e4002e0020c774b807ac8c0020c791c131b41c00200050004400460020bb38c11cb2940020004100630072006f0062006100740020bc0f002000410064006f00620065002000520065006100640065007200200035002e00300020c774c0c1c5d0c11c0020c5f40020c2180020c788c2b5b2c8b2e4002e>
/LTH <FEFF004e006100750064006f006b0069007400650020016100690075006f007300200070006100720061006d006500740072007500730020006e006f0072011700640061006d00690020006b0075007200740069002000410064006f00620065002000500044004600200064006f006b0075006d0065006e007400750073002c0020006b00750072006900650020006c0061006200690061007500730069006100690020007000720069007400610069006b007900740069002000610075006b01610074006f00730020006b006f006b007900620117007300200070006100720065006e006700740069006e00690061006d00200073007000610075007300640069006e0069006d00750069002e0020002000530075006b0075007200740069002000500044004600200064006f006b0075006d0065006e007400610069002000670061006c006900200062016b007400690020006100740069006400610072006f006d00690020004100630072006f006200610074002000690072002000410064006f00620065002000520065006100640065007200200035002e0030002000610072002000760117006c00650073006e0117006d00690073002000760065007200730069006a006f006d00690073002e>
/LVI <FEFF0049007a006d0061006e0074006f006a00690065007400200161006f00730020006900650073007400610074012b006a0075006d00750073002c0020006c0061006900200076006500690064006f00740075002000410064006f00620065002000500044004600200064006f006b0075006d0065006e007400750073002c0020006b006100730020006900720020012b00700061016100690020007000690065006d01130072006f00740069002000610075006700730074006100730020006b00760061006c0069007401010074006500730020007000690072006d007300690065007300700069006501610061006e006100730020006400720075006b00610069002e00200049007a0076006500690064006f006a006900650074002000500044004600200064006f006b0075006d0065006e007400750073002c0020006b006f002000760061007200200061007400760113007200740020006100720020004100630072006f00620061007400200075006e002000410064006f00620065002000520065006100640065007200200035002e0030002c0020006b0101002000610072012b00200074006f0020006a00610075006e0101006b0101006d002000760065007200730069006a0101006d002e>
/NLD (Gebruik deze instellingen om Adobe PDF-documenten te maken die zijn geoptimaliseerd voor prepress-afdrukken van hoge kwaliteit. De gemaakte PDF-documenten kunnen worden geopend met Acrobat en Adobe Reader 5.0 en hoger.)
/NOR <FEFF004200720075006b00200064006900730073006500200069006e006e007300740069006c006c0069006e00670065006e0065002000740069006c002000e50020006f0070007000720065007400740065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e00740065007200200073006f006d00200065007200200062006500730074002000650067006e0065007400200066006f00720020006600f80072007400720079006b006b0073007500740073006b00720069006600740020006100760020006800f800790020006b00760061006c0069007400650074002e0020005000440046002d0064006f006b0075006d0065006e00740065006e00650020006b0061006e002000e50070006e00650073002000690020004100630072006f00620061007400200065006c006c00650072002000410064006f00620065002000520065006100640065007200200035002e003000200065006c006c00650072002000730065006e006500720065002e>
/POL <FEFF0055007300740061007700690065006e0069006100200064006f002000740077006f0072007a0065006e0069006100200064006f006b0075006d0065006e007400f300770020005000440046002000700072007a0065007a006e00610063007a006f006e00790063006800200064006f002000770079006400720075006b00f30077002000770020007700790073006f006b00690065006a0020006a0061006b006f015b00630069002e002000200044006f006b0075006d0065006e0074007900200050004400460020006d006f017c006e00610020006f007400770069006500720061010700200077002000700072006f006700720061006d006900650020004100630072006f00620061007400200069002000410064006f00620065002000520065006100640065007200200035002e0030002000690020006e006f00770073007a0079006d002e>
/PTB <FEFF005500740069006c0069007a006500200065007300730061007300200063006f006e00660069006700750072006100e700f50065007300200064006500200066006f0072006d00610020006100200063007200690061007200200064006f00630075006d0065006e0074006f0073002000410064006f0062006500200050004400460020006d00610069007300200061006400650071007500610064006f00730020007000610072006100200070007200e9002d0069006d0070007200650073007300f50065007300200064006500200061006c007400610020007100750061006c00690064006100640065002e0020004f007300200064006f00630075006d0065006e0074006f00730020005000440046002000630072006900610064006f007300200070006f00640065006d0020007300650072002000610062006500720074006f007300200063006f006d0020006f0020004100630072006f006200610074002000650020006f002000410064006f00620065002000520065006100640065007200200035002e0030002000650020007600650072007300f50065007300200070006f00730074006500720069006f007200650073002e>
/RUM <FEFF005500740069006c0069007a00610163006900200061006300650073007400650020007300650074010300720069002000700065006e007400720075002000610020006300720065006100200064006f00630075006d0065006e00740065002000410064006f006200650020005000440046002000610064006500630076006100740065002000700065006e0074007200750020007400690070010300720069007200650061002000700072006500700072006500730073002000640065002000630061006c006900740061007400650020007300750070006500720069006f006100720103002e002000200044006f00630075006d0065006e00740065006c00650020005000440046002000630072006500610074006500200070006f00740020006600690020006400650073006300680069007300650020006300750020004100630072006f006200610074002c002000410064006f00620065002000520065006100640065007200200035002e00300020015f00690020007600650072007300690075006e0069006c006500200075006c0074006500720069006f006100720065002e>
/RUS <FEFF04180441043f043e043b044c04370443043904420435002004340430043d043d044b04350020043d0430044104420440043e0439043a043800200434043b044f00200441043e043704340430043d0438044f00200434043e043a0443043c0435043d0442043e0432002000410064006f006200650020005000440046002c0020043c0430043a04410438043c0430043b044c043d043e0020043f043e04340445043e0434044f04490438044500200434043b044f00200432044b0441043e043a043e043a0430044704350441044204320435043d043d043e0433043e00200434043e043f0435044704300442043d043e0433043e00200432044b0432043e04340430002e002000200421043e043704340430043d043d044b04350020005000440046002d0434043e043a0443043c0435043d0442044b0020043c043e0436043d043e0020043e0442043a0440044b043204300442044c002004410020043f043e043c043e0449044c044e0020004100630072006f00620061007400200438002000410064006f00620065002000520065006100640065007200200035002e00300020043800200431043e043b043504350020043f043e04370434043d043804450020043204350440044104380439002e>
/SKY <FEFF0054006900650074006f0020006e006100730074006100760065006e0069006100200070006f0075017e0069007400650020006e00610020007600790074007600e100720061006e0069006500200064006f006b0075006d0065006e0074006f0076002000410064006f006200650020005000440046002c0020006b0074006f007200e90020007300610020006e0061006a006c0065007001610069006500200068006f0064006900610020006e00610020006b00760061006c00690074006e00fa00200074006c0061010d00200061002000700072006500700072006500730073002e00200056007900740076006f00720065006e00e900200064006f006b0075006d0065006e007400790020005000440046002000620075006400650020006d006f017e006e00e90020006f00740076006f00720069016500200076002000700072006f006700720061006d006f006300680020004100630072006f00620061007400200061002000410064006f00620065002000520065006100640065007200200035002e0030002000610020006e006f0076016100ed00630068002e>
/SLV <FEFF005400650020006e006100730074006100760069007400760065002000750070006f0072006100620069007400650020007a00610020007500730074007600610072006a0061006e006a006500200064006f006b0075006d0065006e0074006f0076002000410064006f006200650020005000440046002c0020006b006900200073006f0020006e0061006a007000720069006d00650072006e0065006a016100690020007a00610020006b0061006b006f0076006f00730074006e006f0020007400690073006b0061006e006a00650020007300200070007200690070007200610076006f0020006e00610020007400690073006b002e00200020005500730074007600610072006a0065006e006500200064006f006b0075006d0065006e0074006500200050004400460020006a00650020006d006f0067006f010d00650020006f0064007000720065007400690020007a0020004100630072006f00620061007400200069006e002000410064006f00620065002000520065006100640065007200200035002e003000200069006e0020006e006f00760065006a01610069006d002e>
/SUO <FEFF004b00e40079007400e40020006e00e40069007400e4002000610073006500740075006b007300690061002c0020006b0075006e0020006c0075006f00740020006c00e400680069006e006e00e4002000760061006100740069007600610061006e0020007000610069006e006100740075006b00730065006e002000760061006c006d0069007300740065006c00750074007900f6006800f6006e00200073006f00700069007600690061002000410064006f0062006500200050004400460020002d0064006f006b0075006d0065006e007400740065006a0061002e0020004c0075006f0064007500740020005000440046002d0064006f006b0075006d0065006e00740069007400200076006f0069006400610061006e0020006100760061007400610020004100630072006f0062006100740069006c006c00610020006a0061002000410064006f00620065002000520065006100640065007200200035002e0030003a006c006c00610020006a006100200075007500640065006d006d0069006c006c0061002e>
/SVE <FEFF0041006e007600e4006e00640020006400650020006800e4007200200069006e0073007400e4006c006c006e0069006e006700610072006e00610020006f006d002000640075002000760069006c006c00200073006b006100700061002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e007400200073006f006d002000e400720020006c00e4006d0070006c0069006700610020006600f60072002000700072006500700072006500730073002d007500740073006b00720069006600740020006d006500640020006800f600670020006b00760061006c0069007400650074002e002000200053006b006100700061006400650020005000440046002d0064006f006b0075006d0065006e00740020006b0061006e002000f600700070006e00610073002000690020004100630072006f0062006100740020006f00630068002000410064006f00620065002000520065006100640065007200200035002e00300020006f00630068002000730065006e006100720065002e>
/TUR <FEFF005900fc006b00730065006b0020006b0061006c006900740065006c0069002000f6006e002000790061007a006401310072006d00610020006200610073006b013100730131006e006100200065006e0020006900790069002000750079006100620069006c006500630065006b002000410064006f006200650020005000440046002000620065006c00670065006c0065007200690020006f006c0075015f007400750072006d0061006b0020006900e70069006e00200062007500200061007900610072006c0061007201310020006b0075006c006c0061006e0131006e002e00200020004f006c0075015f0074007500720075006c0061006e0020005000440046002000620065006c00670065006c0065007200690020004100630072006f006200610074002000760065002000410064006f00620065002000520065006100640065007200200035002e003000200076006500200073006f006e0072006100730131006e00640061006b00690020007300fc007200fc006d006c00650072006c00650020006100e70131006c006100620069006c00690072002e>
/UKR <FEFF04120438043a043e0440043804410442043e043204430439044204350020044604560020043f043004400430043c043504420440043800200434043b044f0020044104420432043e04400435043d043d044f00200434043e043a0443043c0435043d044204560432002000410064006f006200650020005000440046002c0020044f043a04560020043d04300439043a04400430044904350020043f045604340445043e0434044f0442044c00200434043b044f0020043204380441043e043a043e044f043a04560441043d043e0433043e0020043f0435044004350434043404400443043a043e0432043e0433043e0020043404400443043a0443002e00200020042104420432043e04400435043d045600200434043e043a0443043c0435043d0442043800200050004400460020043c043e0436043d04300020043204560434043a0440043804420438002004430020004100630072006f006200610074002004420430002000410064006f00620065002000520065006100640065007200200035002e0030002004300431043e0020043f04560437043d04560448043e04570020043204350440044104560457002e>
/ENU (Use these settings to create Adobe PDF documents best suited for high-quality prepress printing. Created PDF documents can be opened with Acrobat and Adobe Reader 5.0 and later.)
>>
/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
>>
<<
/AddBleedMarks false
/AddColorBars false
/AddCropMarks false
/AddPageInfo false
/AddRegMarks false
/ConvertColors /ConvertToCMYK
/DestinationProfileName ()
/DestinationProfileSelector /DocumentCMYK
/Downsample16BitImages true
/FlattenerPreset <<
/PresetSelector /MediumResolution
>>
/FormElements false
/GenerateStructure false
/IncludeBookmarks false
/IncludeHyperlinks false
/IncludeInteractive false
/IncludeLayers false
/IncludeProfiles false
/MultimediaHandling /UseObjectSettings
/Namespace [
(Adobe)
(CreativeSuite)
(2.0)
]
/PDFXOutputIntentProfileSelector /DocumentCMYK
/PreserveEditing true
/UntaggedCMYKHandling /LeaveUntagged
/UntaggedRGBHandling /UseDocumentProfile
/UseDocumentBleed false
>>
]
>> setdistillerparams
<<
/HWResolution [2400 2400]
/PageSize [612.000 792.000]
>> setpagedevice
|
| id | nasplib_isofts_kiev_ua-123456789-83487 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0130-5395 |
| language | Ukrainian |
| last_indexed | 2025-12-07T15:42:34Z |
| publishDate | 2014 |
| publisher | Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України |
| record_format | dspace |
| spelling | Нагірна, А.М. 2015-06-19T17:59:23Z 2015-06-19T17:59:23Z 2014 Розв'язування оптимизаційної задачі з дробово-лінійною цільовою функцією на комбінаторній конфігурації розміщень / А.М. Нагірна // Управляющие системы и машины. — 2014. — № 4. — С. 48-54. — Бібліогр.: 8 назв. — укр., рос. 0130-5395 https://nasplib.isofts.kiev.ua/handle/123456789/83487 519.8 Рассмотрены задача оптимизации с дробно-линейной функцией цели на комбинаторной конфигурации размещений и алгоритм решения таких задач на основе теории графов с учетом свойств и структуры множества размещений. Обосновано построение последовательности значений функции–ограничения, разложение точек размещения по подграфам графа согласно координатному методу на примере численного эксперимента. The problem of optimization with a fractional-linear objective function on a combinatorial configuration placements is examened. The algorithm of solving such problems using graph theory, taking into account the properties and structure of the set of placements is analyzed. Building a sequence of functions-limit’s values, decomposition points of permutations on subgraphs polyhedra according to the coordinate method by the example of numerical experiment is justified. Розглянуто задачу оптимізації з дробово-лінійною функцією цілі на комбінаторній конфігурації розміщень і алгоритм розв’язування даного типу задач на основі теорії графів з урахуванням властивостей та структури множини розміщень. Обґрунтовано побудову послідовності значень функції–обмеження, розкладання точок розміщення по підграфам графа згідно з координатним методом на прикладі числового експерименту. uk Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України Управляющие системы и машины Новые методы в информатике Розв'язування оптимизаційної задачі з дробово-лінійною цільовою функцією на комбінаторній конфігурації розміщень Solution to the Optimization Problem with a Fractional-Linear Objective Function on a Combinatorial Configuration Placements Решение оптимизационной задачи с дробно-линейной целевой функцией на комбинаторной конфигурации размещений Article published earlier |
| spellingShingle | Розв'язування оптимизаційної задачі з дробово-лінійною цільовою функцією на комбінаторній конфігурації розміщень Нагірна, А.М. Новые методы в информатике |
| title | Розв'язування оптимизаційної задачі з дробово-лінійною цільовою функцією на комбінаторній конфігурації розміщень |
| title_alt | Solution to the Optimization Problem with a Fractional-Linear Objective Function on a Combinatorial Configuration Placements Решение оптимизационной задачи с дробно-линейной целевой функцией на комбинаторной конфигурации размещений |
| title_full | Розв'язування оптимизаційної задачі з дробово-лінійною цільовою функцією на комбінаторній конфігурації розміщень |
| title_fullStr | Розв'язування оптимизаційної задачі з дробово-лінійною цільовою функцією на комбінаторній конфігурації розміщень |
| title_full_unstemmed | Розв'язування оптимизаційної задачі з дробово-лінійною цільовою функцією на комбінаторній конфігурації розміщень |
| title_short | Розв'язування оптимизаційної задачі з дробово-лінійною цільовою функцією на комбінаторній конфігурації розміщень |
| title_sort | розв'язування оптимизаційної задачі з дробово-лінійною цільовою функцією на комбінаторній конфігурації розміщень |
| topic | Новые методы в информатике |
| topic_facet | Новые методы в информатике |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/83487 |
| work_keys_str_mv | AT nagírnaam rozvâzuvannâoptimizacíinoízadačízdrobovolíníinoûcílʹovoûfunkcíêûnakombínatorníikonfíguracíírozmíŝenʹ AT nagírnaam solutiontotheoptimizationproblemwithafractionallinearobjectivefunctiononacombinatorialconfigurationplacements AT nagírnaam rešenieoptimizacionnoizadačisdrobnolineinoicelevoifunkcieinakombinatornoikonfiguraciirazmeŝenii |