Задача розподілу ресурсів
У різних предметних галузях актуальною є задача такого розподілу ресурсів керованої системи між окремими елементами (обʼєктами), у якому забезпечується найефективніше функціонування системи в заданих обставинах. Розглянуто проблему розподілу заданого глобального ресурсу при обмеженнях знизу, що накл...
Saved in:
| Published in: | Проблемы управления и информатики |
|---|---|
| Date: | 2022 |
| Main Authors: | , |
| Format: | Article |
| Language: | Ukrainian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2022
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/210859 |
| 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: | Задача розподілу ресурсів / А.М. Воронін, А.С. Савченко // Проблеми керування та інформатики. — 2022. — № 1. — С. 5-10. — Бібліогр.: 4 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860007551810142208 |
|---|---|
| author | Воронін, А.М. Савченко, А.С. |
| author_facet | Воронін, А.М. Савченко, А.С. |
| citation_txt | Задача розподілу ресурсів / А.М. Воронін, А.С. Савченко // Проблеми керування та інформатики. — 2022. — № 1. — С. 5-10. — Бібліогр.: 4 назв. — укр. |
| collection | DSpace DC |
| container_title | Проблемы управления и информатики |
| description | У різних предметних галузях актуальною є задача такого розподілу ресурсів керованої системи між окремими елементами (обʼєктами), у якому забезпечується найефективніше функціонування системи в заданих обставинах. Розглянуто проблему розподілу заданого глобального ресурсу при обмеженнях знизу, що накладаються на парціальні ресурси. Показано, що проблема полягає в побудові адекватної цільової функції для оптимізації процесу розподілу ресурсів в умовах їхньої обмеженості. Цільова функція є скалярною згорткою вектора парціальних ресурсів. Вимоги до цільової функції: вона має штрафувати парціальні ресурси за небезпечне наближення до своїх обмежень та бути диференційованою за своїми аргументами. У даній задачі парціальні ресурси мають двояку природу. З одного боку, їх можна розглядати як незалежні змінні, аргументи оптимізації цільової функції. З іншого боку, для кожного з обʼєктів логічним є прагнення максимізувати свій парціальний ресурс, піти якнайдалі від небезпечного обмеження для підвищення ефективності свого функціонування. З цієї точки зору, ресурси можуть розглядатися як часткові критерії якості функціонування відповідних обʼєктів. Ці критерії підлягають максимізації, вони обмежені знизу, невідʼємні та суперечливі (збільшення одного ресурсу можливе лише за рахунок зменшення інших). Для рішення розглянутої проблеми використовується підхід багатокритеріальної оптимізації із застосуванням нелінійної схеми компромісів. Запропонований підхід рекомендується для компромісно-оптимального розподілу ресурсів у практичних задачах широкого спектру. Приведено модельний приклад.
In various subject areas, the problem of distributing the resources of a controlled system among individual elements (objects) is relevant, where the most effective functioning of the system is ensured under given conditions. The problem of distributing a given global resource under lower bounds imposed on partial resources is considered.
|
| first_indexed | 2026-03-18T13:43:50Z |
| format | Article |
| fulltext |
© А.М. ВОРОНІН, А.С. САВЧЕНКО, 2022
Міжнародний науково-технічний журнал
«Проблеми керування та інформатики», 2022, № 1 5
МЕТОДИ ОПТИМІЗАЦІЇ ТА ОПТИМАЛЬНЕ КЕРУВАННЯ
УДК 519.9
А.М. Воронін, А.С. Савченко
ЗАДАЧА РОЗПОДІЛУ РЕСУРСІВ
Ключові слова: розподіл ресурсів, багатокритеріальна оптимізація, обмеження
ресурсів, нелінійна схема компромісів.
Keywords: resource distribution, multicriteria optimization, resource constraints,
nonlinear trade-off scheme.
У різних предметних областях виникає завдання розподілу ресурсів між ок-
ремими об’єктами. Розглянемо це завдання з позицій системного аналізу. У сфе-
рах управління та економіки актуальним є завдання такого розподілу ресурсів ке-
рованої системи між окремими елементами (обʼєктами), при якому забезпечується
найбільш ефективне функціонування системи в заданих обставинах. Проблема
розподілу обмежених ресурсів — основна проблема економіки. Кажуть, що пра-
вильний розподіл і перерозподіл ресурсів — це і є економіка. Аналогічні пробле-
ми є й у інших предметних областях. Мистецтво полягає у тому, щоб у залежності
від обставин уміти правильно розподіляти обмежені ресурси.
Часто це завдання вирішується субʼєктивно, на основі досвіду та професійної
кваліфікації особи, яка приймає рішення (ОПР). У найпростіших випадках такий
підхід може бути виправданим. Однак при великій кількості обʼєктів та у відпові-
дальних випадках різко зростає ціна помилки управлінського рішення. Стає необ-
хідною розробка формалізованих методів підтримки прийняття рішень для грамо-
тного розподілу ресурсів між обʼєктами з урахуванням усіх заданих обставин.
Однією з таких обставин зазвичай є обмеженість ресурсів. Найбільш поши-
рений випадок обмеженості зверху сумарного (глобального) ресурсу системи, що
підлягає розподілу між окремими обʼєктами.
У практичних випадках обмеження накладаються не тільки на глобальний
ресурс, а й на парціальні ресурси, що виділяються окремим обʼєктам. При цьому
обмеження можуть накладатися як знизу, так і зверху. Найбільш цікавим є випа-
док обмеженості парціальних ресурсів знизу. Цей вид обмежень трапляється у ба-
гатьох предметних областях. Так, медики та фізіологи знають, що критична маса
окремих органів та тканин, достатня для підтримки життєдіяльності організму,
становить для печінки 15 % від нормального обсягу, для нирок — 25 %, для ерит-
роцитів — 35 % і для легенів — 45 %; обсяг циркулюючої плазми — 70 %. Зни-
ження обсягів менше зазначених обмежень знизу призводить до незворотних змін
в організмі.
Іншим прикладом обмежень знизу є розподіл палива між літаками при
виконанні авіарейсів до різних міст. Для кожного рейсу існує нижня межа,
менше якої виділяти паливо безглуздо, тому що літак просто не долетить до
свого пункту призначення. У цьому полягає суть обмеження знизу для кож-
6 ISSN 1028-0979
ного парціального ресурсу. Якщо ж цей рейс одержує паливо понад відому
нижню межу, то в нього зʼявляється можливість вільного маневрування по
ешелонах, обходу грозового фронту, заходження на запасний аеродром і т.п.
З іншого боку, збільшувати парціальний ресурс необмежено теж не можна,
для нього існує обмеження зверху. Це зрозуміло хоча б тому, що кожен літак
має певну ємність баків, більше за яку прийняти паливо на борт він фізично
не може.
Такі обмеження або заздалегідь відомі, або визначаються техніко-еконо-
мічними розрахунками чи методами експертних оцінок. Слід розрізняти обме-
ження умовні (коли порушення меж небажане) та обмеження безумовні (коли їх
порушення фізично неможливе). Неважко бачити, що сума обмежень знизу для
всіх парціальних ресурсів є обмеженням для глобального ресурсу знизу, а сума
обмежень зверху обмежує глобальний ресурс зверху.
Враховуючи заданий комплекс обмежень, потрібно так розподілити глобаль-
ний ресурс системи між обʼєктами, щоб забезпечувалася найбільш ефективна ро-
бота всієї системи в цілому. Проблема полягає у побудові адекватної цільової фу-
нкції для оптимізації процесу розподілу ресурсів в умовах їхньої обмеженості.
Простий рівномірний розподіл у цьому випадку не годиться, оскільки може по-
ставити деякі обʼєкти на межу неможливості їх функціонування, тоді як інші
обʼєкти отримають невиправдано великий ресурс.
У цій роботі на вирішення аналізованої проблеми використовується підхід
багатокритеріальної оптимізації із застосуванням нелінійної схеми компромі-
сів [1–3].
Постановка задачі
Ця проблема актуальна для різних предметних областей, тому викладемо по-
становку завдання у загальному вигляді. Задані глобальний ресурс ,R що підля-
гає розподілу, а також 2n елементів системи (обʼєктів), кожному з яких виді-
ляється парціальний ресурс ,
i
r їх сукупність становить вектор
1
{ } .n
i i
r r
=
= Зрозу-
міло, що
1
.
n
i
i
r R
=
= (1)
Для кожного обʼєкта відома (або визначається методом експертних оці-
нок) гранично допустима величина виділеного ресурсу min
,
i
r менше якого да-
ний обʼєкт функціонувати не може. Таким чином, задається система обме-
жень знизу
min min
1
, , [1, ].
n
i i i
i
r r r R i n
=
(2)
З іншого боку, для кожного з обʼєктів відома величина
max
,
i
r перевищувати
яку ресурс обʼєкта неспроможний чи не повинен. Система обмежень зверху має
вигляд
max max
1
, , [1, ].
n
i i i
i
r r r R i n
=
(3)
З (2) та (3) випливає, що
max min
, [1, ],
i i i
r r r i n
Міжнародний науково-технічний журнал
«Проблеми керування та інформатики», 2022, № 1 7
max min
1 1
.
n n
i i
i i
r R r
= =
(4)
Формула для області визначення вектора r має вигляд
max min
{ , [1, ]}.
r i i i
r X r r r r i n =
Розглянемо полярні (вироджені) випадки нерівності (4). Якщо
min
1
,
n
i
i
R r
=
=
то завдання, що розглядається, зводиться до такого розподілу глобального ре-
сурсу, при якому кожен обʼєкт отримує свій мінімально допустимий парціаль-
ний ресурс:
min
, [1, ].*
i i
r r i n=
Якщо ж глобальний ресурс дозволяє повністю задовольняти потреби
обʼєктів, тобто max
1
,
n
i
i
R r
=
= то завдання вирішується як
max
, [1, ].*
i i
r r i n=
Таким чином, у полярних випадках нерівності (4) аналізована проблема має
тривіальні рішення. І тільки якщо вираз (4) стає суворою нерівністю
max min
1 1
,
n n
i i
i i
r R r
= =
(5)
завдання оптимізації розподілу обмежених ресурсів набуває сенсу.
Завдання оптимізації передбачає наявність цільової функції ( ),f r екстремі-
зація якої дає вирішення задачі, що розглядається:
arg extr ( ).*
r
r X
r f r
=
Ставиться завдання: в умовах (5) визначити такі парціальні ресурси ,*
r
r X
при яких виконується вимога (1) і набуває екстремального значення деяка цільова
функція ( ),f r вид якої слід вибрати та обґрунтувати.
Метод вирішення
Аналіз показує, що завдання оптимізації розподілу обмежених ресурсів обме-
ження зверху
max
, [1, ],
i i
r r i n сприймається як просте оптимізаційне обмежен-
ня, наближення до якого зазвичай нічим особливим для системи не загрожує. Зо-
всім інший сенс має обмеження знизу
min
, [1, ].
i i
r r i n Наближення ресурсу до
цього свого обмеження загрожує можливості функціонування відповідного обʼєкта.
Можна сказати, що обмеження знизу має змушувати шукану цільову функцію збі-
льшувати різницю між парціальними ресурсами та їх обмеженнями знизу.
Тому вираз шуканої цільової функції має: 1) включати обмеження знизу в
явному вигляді, 2) штрафувати систему за наближення парціальних ресурсів
до цих обмежень і 3) бути диференційованим за своїми аргументами. Найпро-
стішою цільовою функцією, що задовольняє зазначеним вимогам, є
1
min min
1
( ) ( ) .
n
i i i
i
f r r r r −
=
= − (6)
8 ISSN 1028-0979
Аналіз формули (6) показує, що це не що інше, як вираз скалярної згортки
максимізованих часткових критеріїв , [1, ],
i
r i n за нелінійною схемою компромі-
сів (НСК) у задачі багатокритеріальної оптимізації [2].
Дійсно, у розглянутому завданні ресурси , [1, ],
i
r i n мають двояку природу.
З одного боку, їх можна розглядати як незалежні змінні аргументи оптимізації ці-
льової функції ( ).f r З іншого боку, для кожного з обʼєктів логічне прагнення мак-
симізувати свій парціальний ресурс, піти якнайдалі від небезпечного обмеження
mini
r для підвищення ефективності свого функціонування.
З цієї точки зору ресурси
min
, [1, ],
i i
r r i n можуть розглядатися як част-
кові критерії якості функціонування відповідних обʼєктів. Ці критерії підлягають
максимізації, вони обмежені знизу, невідʼємні та суперечливі (збільшення одного
ресурсу можливе лише за рахунок зменшення інших).
Концепція НСК заснована на принципі «подалі від обмежень». Передбача-
ється, що функція корисності ОПР оцінює як кращі рішення, які дають більше
віддалення критеріїв від небезпечних обмежень. Скалярна згортка ( )f r являє со-
бою модель функції корисності і включає в себе в явному вигляді різницю
mini i
r r− як характеристику напруженості ситуації прийняття рішення. Це дозво-
ляє штрафувати критерії за наближення до своїх обмежень.
На підставі викладеного завдання векторної оптимізації розподілу обмеже-
них ресурсів з урахуванням ізопериметричного обмеження для аргументів (1) на-
буває вигляду
1
min min
1 1
arg min ( ) arg min ( ) , .*
r r
n n
i i i i
r X r X i i
r f r r r r r R−
= =
= = − = (7)
Завдання (7) можна вирішувати як аналітично, використовуючи метод неви-
значених множників Лагранжа, так і чисельними методами, якщо аналітичне рі-
шення виявляється скрутним. Аналітичне рішення передбачає побудову функції
Лагранжа як
1
( , ) ( ) ,
n
i
i
L r f r r R
=
= + −
де — невизначений множник Лагранжа, та вирішення системи рівнянь
1
( , )
0, [1, ],
( , )
0.
i
n
i
i
L r
i n
r
L r
r R
=
=
= − =
Для вирішення багатокритеріальних завдань чисельними методами із засто-
суванням концепції НСК та з обмеженнями на аргументи та критерії розроблено
алгоритми та складено компʼютерну програму [2].
Ілюстраційний приклад
Для виконання двох далеких автобусних рейсів (n= 2) автостанція має в сво-
єму розпорядженні паливо загальним обсягом R= 12 тонн (цифри умовні). Міні-
мальна потреба першого рейсу складає
1 1min
2r r = тонни, другого рейсу —
Міжнародний науково-технічний журнал
«Проблеми керування та інформатики», 2022, № 1 9
2 2 min
5r r = тонн. Це обмеження знизу для парціальних ресурсів. Місткість ба-
ків першого автобуса — 1max
7r = тонн, другого автобуса —
2 max
10r = тонн. Це
обмеження зверху.
Умова (5) як суворої нерівності (розмірності опущені)
1min 2min 1max 2max
7 12 17r r R r r+ = = + =
дотримується. Отже, завдання оптимізації розподілу обмежених ресурсів може
бути поставлене і рішення буде нетривіальним.
Ставиться завдання отримати аналітичне рішення компромісно-оптималь-
ного розподілу палива між рейсами.
Будуємо функцію Лагранжа
1 1
1min 1 1min 2min 2 2min 1 2
( , ) ( ) ( ) ( ).L r r r r r r r r r R− − = − + − + + −
Отримуємо систему рівнянь
2
1min 1 1min
1
2
2min 2 2min
2
1 2
( , )
( ) 0
( , )
( ) 0
0.
L r
r r r
r
L r
r r r
r
r r R
−
−
= − − + =
= − − + =
+ − =
Підставляючи числові дані
2
1
2
2
1 2
2( 2) 0
5( 5) 0
12 0
r
r
r r
−
−
− − + =
− − + =
+ − =
і вирішуючи цю систему методом Гауса (послідовного виключення змінних),
отримуємо
1
3,94*r = тонни,
2
8,06*r = тонни.
Поставлене завдання вирішено у припущенні, що відносна важливість обох
рейсів для ОПР однакова. Якщо ж ні, то в цільову функцію вводяться вагові кое-
фіцієнти 1
і
2
, що відображають індивідуальні переваги ОПР. Ці коефіцієнти
повинні бути нормовані та визначені на симплексі:
2
1 2
1
, 0, 1, [1; 2]
n
i i i
i
X i
=
=
= =
.
У тому випадку, коли глобальний ресурс розподіляється між обʼєктами не
безпосередньо, а через проміжні ланки, система стає ієрархічною [4]. Викладений
підхід може бути використаний і в цьому випадку.
А.М. Воронін, А.С. Савченко
ЗАДАЧА РОЗПОДІЛУ РЕСУРСІВ
У різних предметних галузях актуальною є задача такого розподілу ресурсів керо-
ваної системи між окремими елементами (обʼєктами), у якому забезпечується най-
10 ISSN 1028-0979
ефективніше функціонування системи в заданих обставинах. Розглянуто проблему
розподілу заданого глобального ресурсу при обмеженнях знизу, що накладаються
на парціальні ресурси. Показано, що проблема полягає в побудові адекватної цільо-
вої функції для оптимізації процесу розподілу ресурсів в умовах їхньої обмеженос-
ті. Цільова функція є скалярною згорткою вектора парціальних ресурсів. Вимоги до
цільової функції: вона має штрафувати парціальні ресурси за небезпечне наближен-
ня до своїх обмежень та бути диференційованою за своїми аргументами. У даній
задачі парціальні ресурси мають двояку природу. З одного боку, їх можна розгляда-
ти як незалежні змінні, аргументи оптимізації цільової функції. З іншого боку, для
кожного з обʼєктів логічним є прагнення максимізувати свій парціальний ресурс, пі-
ти якнайдалі від небезпечного обмеження для підвищення ефективності свого функ-
ціонування. З цієї точки зору, ресурси можуть розглядатися як часткові критерії
якості функціонування відповідних обʼєктів. Ці критерії підлягають максимізації,
вони обмежені знизу, невідʼємні та суперечливі (збільшення одного ресурсу мож-
ливе лише за рахунок зменшення інших). Для рішення розглянутої проблеми вико-
ристовується підхід багатокритеріальної оптимізації із застосуванням нелінійної
схеми компромісів. Запропонований підхід рекомендується для компромісно-опти-
мального розподілу ресурсів у практичних задачах широкого спектру. Приведено
модельний приклад.
A.N. Voronin, A.S. Savchenko
RESOURCE DISTRIBUTION PROBLEM
In various subject areas, the problem of such a distribution of the resources of a con-
trolled system between individual elements (objects) is relevant, which ensures the
most efficient functioning of the system in given circumstances. The problem of dis-
tribution of the given global resource is considered at restrictions from below, ap-
plied on partial resources. It is shown, that the problem consists in construction of
adequate criterion function for optimization of process of distribution of resources in
conditions of their limitation. The objective function is a scalar convolution of the
partial resource vector. Requirements for the objective function: it must penalize par-
tial resources for dangerously approaching its limits and be differentiable in its argu-
ments. In the problem under consideration, partial resources have a dual nature. On
the one hand, they can be considered as independent variables, arguments for the op-
timization of the objective function. On the other hand, it is logical for each of the
objects to strive to maximize its partial resource, to go as far as possible from a dan-
gerous limitation in order to increase the efficiency of its functioning. From this point
of view, resources can be considered as particular criteria for the quality of the func-
tioning of the corresponding objects. These criteria are subject to maximization, they
are limited from below, non-negative and contradictory (an increase in one resource
is possible only at the expense of a decrease in others). For the decision of a consid-
ered problem the approach of multicriteria optimization with use of the nonlinear
trade-off scheme is undertaken. The proposed approach is recommended for a com-
promise-optimal allocation of resources in a wide range of practical problems. The
illustrating example is given.
REFERENCES
1. Воронин А.Н. Векторная оптимизация иерархических структур. Проблемы управления и
информатики. 2004. № 6. С. 26–34.
2. Воронин А.Н., Зиатдинов Ю.К., Козлов А.И. Векторная оптимизация динамических си-
стем. Киев : Техніка, 1999. 284 с.
3. Воронин А.Н. Нелинейная схема компромиссов в многокритериальных задачах оценивания
и оптимизации. Кибернетика и системный анализ. 2009. № 4. С. 106–114.
4. Прилуцкий М.Х. Многокритериальное распределение однородного ресурса в иерархиче-
ских системах. Автоматика и телемеханика. 1996. № 2. С. 24–29.
Отримано 29.12.2021
|
| id | nasplib_isofts_kiev_ua-123456789-210859 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0572-2691 |
| language | Ukrainian |
| last_indexed | 2026-03-18T13:43:50Z |
| publishDate | 2022 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Воронін, А.М. Савченко, А.С. 2025-12-19T14:08:33Z 2022 Задача розподілу ресурсів / А.М. Воронін, А.С. Савченко // Проблеми керування та інформатики. — 2022. — № 1. — С. 5-10. — Бібліогр.: 4 назв. — укр. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/210859 519.9 10.34229/1028-0979-2022-1-1 У різних предметних галузях актуальною є задача такого розподілу ресурсів керованої системи між окремими елементами (обʼєктами), у якому забезпечується найефективніше функціонування системи в заданих обставинах. Розглянуто проблему розподілу заданого глобального ресурсу при обмеженнях знизу, що накладаються на парціальні ресурси. Показано, що проблема полягає в побудові адекватної цільової функції для оптимізації процесу розподілу ресурсів в умовах їхньої обмеженості. Цільова функція є скалярною згорткою вектора парціальних ресурсів. Вимоги до цільової функції: вона має штрафувати парціальні ресурси за небезпечне наближення до своїх обмежень та бути диференційованою за своїми аргументами. У даній задачі парціальні ресурси мають двояку природу. З одного боку, їх можна розглядати як незалежні змінні, аргументи оптимізації цільової функції. З іншого боку, для кожного з обʼєктів логічним є прагнення максимізувати свій парціальний ресурс, піти якнайдалі від небезпечного обмеження для підвищення ефективності свого функціонування. З цієї точки зору, ресурси можуть розглядатися як часткові критерії якості функціонування відповідних обʼєктів. Ці критерії підлягають максимізації, вони обмежені знизу, невідʼємні та суперечливі (збільшення одного ресурсу можливе лише за рахунок зменшення інших). Для рішення розглянутої проблеми використовується підхід багатокритеріальної оптимізації із застосуванням нелінійної схеми компромісів. Запропонований підхід рекомендується для компромісно-оптимального розподілу ресурсів у практичних задачах широкого спектру. Приведено модельний приклад. In various subject areas, the problem of distributing the resources of a controlled system among individual elements (objects) is relevant, where the most effective functioning of the system is ensured under given conditions. The problem of distributing a given global resource under lower bounds imposed on partial resources is considered. uk Інститут кібернетики ім. В.М. Глушкова НАН України Проблемы управления и информатики Методи оптимізації та оптимальне керування Задача розподілу ресурсів Resource allocation problem Article published earlier |
| spellingShingle | Задача розподілу ресурсів Воронін, А.М. Савченко, А.С. Методи оптимізації та оптимальне керування |
| title | Задача розподілу ресурсів |
| title_alt | Resource allocation problem |
| title_full | Задача розподілу ресурсів |
| title_fullStr | Задача розподілу ресурсів |
| title_full_unstemmed | Задача розподілу ресурсів |
| title_short | Задача розподілу ресурсів |
| title_sort | задача розподілу ресурсів |
| topic | Методи оптимізації та оптимальне керування |
| topic_facet | Методи оптимізації та оптимальне керування |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/210859 |
| work_keys_str_mv | AT voronínam zadačarozpodíluresursív AT savčenkoas zadačarozpodíluresursív AT voronínam resourceallocationproblem AT savčenkoas resourceallocationproblem |