Розв'язування оптимизаційної задачі з дробово-лінійною цільовою функцією на комбінаторній конфігурації розміщень

Рассмотрены задача оптимизации с дробно-линейной функцией цели на комбинаторной конфигурации размещений и алгоритм решения таких задач на основе теории графов с учетом свойств и структуры множества размещений. Обосновано построение последовательности значений функции–ограничения, разложение точек ра...

Full description

Saved in:

Bibliographic Details
Published in:	Управляющие системы и машины
Date:	2014
Main Author:	Нагірна, А.М.
Format:	Article
Language:	Ukrainian
Published:	Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України 2014
Subjects:	Новые методы в информатике
Online Access:	https://nasplib.isofts.kiev.ua/handle/123456789/83487
Tags:	Add Tag No Tags, Be the first to tag this record!
Journal Title:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Cite this:	Розв'язування оптимизаційної задачі з дробово-лінійною цільовою функцією на комбінаторній конфігурації розміщень / А.М. Нагірна // Управляющие системы и машины. — 2014. — № 4. — С. 48-54. — Бібліогр.: 8 назв. — укр., рос.

Institution

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

Розв'язування оптимизаційної задачі з дробово-лінійною цільовою функцією на комбінаторній конфігурації розміщень

Institution

Similar Items