Нелинейная несепарабельная задача рационального распределения многомерного ресурса при многономенклатурном производстве
Задача рационального распределения многомерного ресурса при многономенклатурном производстве формализована как нелинейная несепарабельная задача математического программирования. Для решения задачи предложена итерационная процедура с конечным числом шагов. Задача раціонального розподілу багатовимірн...
Gespeichert in:
| Veröffentlicht in: | Математичні машини і системи |
|---|---|
| Datum: | 2014 |
| Hauptverfasser: | , , |
| Format: | Artikel |
| Sprache: | Russisch |
| Veröffentlicht: |
Інститут проблем математичних машин і систем НАН України
2014
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/84344 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Нелинейная несепарабельная задача рационального распределения многомерного ресурса при многономенклатурном производстве / Л.Г. Раскин, О.В. Серая, Т.И. Каткова // Математичні машини і системи. — 2014. — № 1. — С. 171-177. — Бібліогр.: 5 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860051003301167104 |
|---|---|
| author | Раскин, Л.Г. Серая, О.В. Каткова, Т.И. |
| author_facet | Раскин, Л.Г. Серая, О.В. Каткова, Т.И. |
| citation_txt | Нелинейная несепарабельная задача рационального распределения многомерного ресурса при многономенклатурном производстве / Л.Г. Раскин, О.В. Серая, Т.И. Каткова // Математичні машини і системи. — 2014. — № 1. — С. 171-177. — Бібліогр.: 5 назв. — рос. |
| collection | DSpace DC |
| container_title | Математичні машини і системи |
| description | Задача рационального распределения многомерного ресурса при многономенклатурном производстве формализована как нелинейная несепарабельная задача математического программирования. Для решения задачи предложена итерационная процедура с конечным числом шагов.
Задача раціонального розподілу багатовимірного ресурсу при багатономенклатурному виробництві формалізована як нелінійна несепарабельна задача математичного програмування. Для вирішення задачі запропонована ітераційна процедура з кінцевим числом кроків.
The problem of rational distribution of multidimensional resource under multinomenclature production is formalized as a nonlinear inseparable mathematical programming problem. For solving the problem the iterative procedure with a finite number of steps is suggested.
|
| first_indexed | 2025-12-07T16:59:45Z |
| format | Article |
| fulltext |
© Раскин Л.Г., Серая О.В., Каткова Т.И., 2014 171
ISSN 1028-9763. Математичні машини і системи, 2014, № 1
УДК 519.85
Л.Г. РАСКИН*, О.В. СЕРАЯ*, Т.И. КАТКОВА**
НЕЛИНЕЙНАЯ НЕСЕПАРАБЕЛЬНАЯ ЗАДАЧА РАЦИОНАЛЬНОГО
РАСПРЕДЕЛЕНИЯ МНОГОМЕРНОГО РЕСУРСА ПРИ
МНОГОНОМЕНКЛАТУРНОМ ПРОИЗВОДСТВЕ
*
Национальный технический университет «ХПИ», Харьков, Украина
**
Бердянский университет менеджмента и бизнеса, Бердянск, Украина
Анотація. Задача раціонального розподілу багатовимірного ресурсу при багатономенклатурному
виробництві формалізована як нелінійна несепарабельна задача математичного програмування.
Для вирішення задачі запропонована ітераційна процедура з кінцевим числом кроків.
Ключові слова: математичне програмування, багатовимірний ресурс, нелінійна задача, несепара-
бельна задача, ітерації.
Аннотация. Задача рационального распределения многомерного ресурса при многономенклатур-
ном производстве формализована как нелинейная несепарабельная задача математического про-
граммирования. Для решения задачи предложена итерационная процедура с конечным числом ша-
гов.
Ключевые слова: математическое программирование, многомерный ресурс, нелинейная задача,
несепарабельная задача, итерации.
Abstract. The problem of rational distribution of multidimensional resource under multinomenclature
production is formalized as a nonlinear inseparable mathematical programming problem. For solving the
problem the iterative procedure with a finite number of steps is suggested.
Keywords: mathematical programming, multidimensional resource, nonlinear problem, inseparable prob-
lem, iterations.
1. Введение
Многочисленные задачи планирования в экономике, технике, военном деле и т.п. сводятся
к математической модели, типичной для так называемых задач рационального распределе-
ния многомерного ресурса [1–4]. Характерная особенность формулировки таких задач: ли-
нейная или нелинейная сепарабельная целевая функция и линейные ограничения. Вместе с
тем, в экономических приложениях для описания функции прибыли, получаемой от рас-
пределения ресурса, предлагается более адекватная модель, приводящая к аддитивно-
мультипликативной функции типа Кобба-Дугласа [5]. Понятно, что традиционные методы
решения задачи в этом случае не эффективны.
2. Постановка задачи
В условиях ненасыщенного рынка задача рационального распределения многомерного ре-
сурса при производстве многономенклатурного продукта распадается на две подзадачи.
Подзадача 1. Отыскание рационального плана производства многономенклатурного
продукта, обеспечивающего максимальную прибыль от его реализации.
Подзадача 2. Рациональное распределение многомерного ресурса при выполнении
выработанного плана производства.
Рассмотрим последовательно методы решения поставленных задач.
3. Основные результаты
Подзадача 1.
Введем ),...,,( 21 maaaA = – вектор, задающий количество ресурса каждого вида;
172 ISSN 1028-9763. Математичні машини і системи, 2014, № 1
iC – стоимость единицы ресурса i -го вида, 1,2,...i m= ;
0C – суммарный финансовый ресурс, распределяемый при планировании произ-
водства;
),...,,( 21 nbbbB = – искомый вектор распределения ресурса;
)( jj bϕ – функция, определяющая прибыль от реализации j-го продукта при вложе-
нии ресурса
jb в его производство, 1,2,...j n= .
Математическая модель задачи имеет вид: найти набор ),...,,( 21 nbbbB = , максими-
зирующий суммарную прибыль
∑
=
=Φ
n
j
jj bB
1
)()( ϕ (1)
и удовлетворяющий ограничениям
,
1
0∑
=
=
n
j
j Cb ,0≥jb 1,2,...j n= . (2)
Пусть, например,
ja
jjjj bab 1
0)( =ϕ .
Тогда
∑
=
=Φ
n
j
a
jj
jbaB
1
0
1)( .
Решим задачу методом неопределенных множителей Лагранжа:
−−=Φ ∑∑
==
0
11
0
1)(
~
CbbaB
n
j
j
n
j
a
jj
j λ .
Далее
,0
)(
~
1
10
1 =λ−= −α j
jjj
j
baa
db
BdΦ
1,2,...j n= ;
11
1
0 1
,
a j
j
j j
b
a a
− λ=
1,2,...j n= . (3)
Подставляя (3) в (2), получим
0
1
1
10
11
C
aa
n
j jj
ja
=
∑
=
−λ
. (4)
Уравнение (4) относительно λ решается численно. Аналитическое решение легко
может быть получено, если
11 aa j = , 1,2,...j n= . Тогда уравнение (4) упрощается к виду
,
1
0
1
1
0
1
1
1111
C
aa
n
j j
aa
=
∑
=
−−λ
ISSN 1028-9763. Математичні машини і системи, 2014, № 1 173
откуда
11
11
1
0
1
1
1 0
1
a
an
j j
C
a
a
−
−
=
λ =
∑
. (5)
Теперь, подставляя (5) в (3), получим искомое значение
jb :
11
1111
11
1
11
0
0
1
1 0
1 0
1
1
,
1
a
aa
a
j
j
j n
j j
C
a
b
a a
a
−
−−
−
=
λ = =
∑
1,2,...j n= . (6)
Полученный набор входит в число исходных данных для решения подзадачи 2.
Подзадача 2.
Введем матрицу )( ijxX = , ijx – количество ресурса i -го вида, направляемого на
изготовление j -го продукта. Пусть ∏
=
=
m
i
ijjj
ijxb
1
)( βϕ – функция, задающая среднюю при-
быль, обеспечиваемую реализацией j -го продукта при вложении ),...,,( 21 mjjjj xxxX = .
Теперь сформулируем подзадачу 2 следующим образом: найти матрицу )( ijxX = ,
1,2,...i m= , 1,2,...j n= , максимизирующую среднюю суммарную прибыль, соответст-
вующую выбранному распределению многономенклатурного ресурса ),...,,( 21 maaa , вычи-
сляемую по формуле
∑∏
= =
=
n
j
m
i
ij
ijxxF
1 1
)( β
(7)
и удовлетворяющую ограничениям
1
n
ij i
j
x a
=
=∑ , 1,2,...i m= , (8)
,
1
i
n
j
iji bxC =∑
=
1,2,...j n= , (9)
,0≥ijx 1,2,...i m= , 1,2,...j n= , ∑∑
==
=
n
j
j
m
i
i ba
11
. (10)
Полученная модель задает достаточно сложную задачу математического програм-
мирования с нелинейной несепарабельной целевой функцией и ограничениями, характер-
ными для распределительных задач линейного программирования. Понятно, что непосред-
ственное решение задачи стандартными методами математического программирования
затруднительно.
Приближенное решение может быть получено с использованием следующей проце-
дуры.
174 ISSN 1028-9763. Математичні машини і системи, 2014, № 1
Вначале несколько упростим задачу, преобразовав ее ограничения к виду, типично-
му для транспортных задач линейного программирования. С этой целью введем новые пе-
ременные ijiij xCz = . Подставляя эти переменные в ограничения (8) и (9), получим
,dCaz iii
n
j
ij ==∑
=1
1,2,...i m= , (11)
,
1
j
m
i
ij bz =∑
=
1,2,...j n= , (12)
,0≥ijz 1,2,...i m= , 1,2,...j n= . (13)
Одновременно преобразуем и целевую функцию (7):
( ) ( )∑ ∏∑ ∏∑∏
= == == =
==
=
n
j
m
i
ijijj
n
j
m
i
ijj
n
j
m
i i
ij zGzG
C
z
)z(F ij
ij
1 11 11 1
ϕβ
β
, (14)
где ∏
=
β
=
m
i i
j
ij
C
G
1
1 – коэффициент, не зависящий от оптимизируемого набора, 1,2,...j n= .
Решение задачи достигается в результате реализации двухэтапной процедуры, ос-
нованной на следующей теореме.
Теорема. Для того, чтобы набор { }*
ijz был решением задачи (11)–(14), необходимо и
достаточно, чтобы этот набор, удовлетворяя (11)–(13), максимизировал
( ) ( )∏
=
Φ=Φ
m
i
ijijijj zz
1
,
то есть имело место
( ) { } ( )
= ∏∏
==
m
i
ijijz
m
i
*
ijij zmaxz
ij 11
ϕϕ (15)
для всех 1,2,...j n= .
Достаточность. Пусть { })(
ijz 0 – произвольный набор, удовлетворяющий (11)–(13) и
не совпадающий с { }*
ijz . В силу (15) имеем
( ) ( )∏∏
==
≥
m
i
)(
ijij
m
i
*
ijij zz
1
0
1
ϕϕ , 1,2,...j n= .
Тогда
( ) ( )∑∏∑∏
= == =
≥
n
j
m
i
)(
ijij
n
j
m
i
*
ijij zz
1 1
0
1 1
ϕϕ . (16)
Полученное неравенство означает, что при выполнении требований теоремы набор
{ }*
ijz является решением задачи.
Необходимость. Покажем, что из оптимального набора { }*
ijz в целом следует его
оптимальность по столбцам.
Предположим противное, что существует набор { }**
ijz , оптимальный в целом и не
совпадающий с оптимальным по столбцам набором { }*
ijz . Из оптимальности { }**
ijz в целом
следует, что
ISSN 1028-9763. Математичні машини і системи, 2014, № 1 175
( ) ( )∑∏∑∏
= == =
≥
n
j
m
i
ijij
n
j
m
i
**
ijij zz
1 11 1
ϕϕ
для любого набора { }ijz , в том числе и для набора { }*
ijz , не совпадающего с { }**
ijz , то есть
( ) ( )∑∏∑∏
= == =
≥
n
j
m
i
*
ijij
n
j
m
i
**
ijij zz
1 11 1
ϕϕ . (17)
С другой стороны, из оптимальности { }*
ijz по столбцам следует, что
( ) ( )∏∏
==
≥
m
i
ijij
m
i
*
ijij zz
11
ϕϕ
для любого набора { }ijz , в том числе и для набора { }**
ijz , не совпадающего с { }*
ijz , то есть
( ) ( )∏∏
==
≥
m
i
**
ijij
m
i
*
ijij zz
11
ϕϕ ,
откуда
( ) ( )∑∏∑∏
= == =
≥
n
j
m
i
**
ijij
n
j
m
i
*
ijij zz
1 11 1
ϕϕ . (18)
Полученные неравенства (17) и (18) противоречат друг другу. Таким образом, пред-
положение о возможности существования набора, оптимального в целом, но неоптималь-
ного по столбцам, привело к противоречию. Теорема доказана.
С использованием этой теоремы решение исходной задачи на первом этапе сводит-
ся к последовательному решению n задач (для 1,2,...j n= ) типа: найти набор { }ijz , мак-
симизирующий
( ) ( )∏
=
=Φ
m
i
ijijijj zz
1
ϕ
и удовлетворяющий ограничениям
j
m
i
ij bz =∑
=1
, 0≥ijz , 1,2,...j n= .
Если в результате решения всех n задач первого этапа получена матрица { }ijz , ком-
поненты которой удовлетворяют ограничениям (11), то эта матрица после возвращения к
исходным переменным
ijx определяет искомое решение задачи. В противном случае на
втором этапе выполняется коррекция матрицы, полученной на первом этапе. Рассмотрим
эту процедуру подробнее.
Первый этап. Формулировка задачи: для выбранного j найти вектор
),...,,( 21 mjjjj zzzZ = распределения ресурсов, максимизирующий
( ) ∏
=
β=ϕ
m
i
ijjj
ijzZ
1
(19)
и удовлетворяющий (12).
Мультипликативный критерий (19) логарифмированием преобразуем в аддитивный:
( ) ( ) .zlnzlnxL ij
m
i
ijjjjj ∑
=
==
1
βϕ
176 ISSN 1028-9763. Математичні машини і системи, 2014, № 1
Сформируем функцию Лагранжа:
( ) .bzzlnz j
m
i
ijjij
m
i
ijjj
−−=Φ ∑∑
== 11
λβ
Далее
( )
,0
1 =λ−β= j
ij
ij
ij
jj
zdz
zdΦ
откуда
,
j
ij
ijz
λ
β
= 1,2,...i m= . (20)
Подставив (20) в (12), найдем jλ :
,
1
11 1
j
m
i
ij
j
m
i
m
i j
ij
ij bz ∑∑ ∑
== =
=β
λ
=
λ
β
=
откуда .
1
1
∑
=
=
m
i
ij
j
j
b
βλ
Тогда
(0)
1
ij j
ij m
ij
i
b
z
=
β
=
β∑
, 1,2,...i m= . (21)
Компоненты )0(
ijz , вычисленные в соответствии с (21), определяют начальное реше-
ние задачи. Проверим, удовлетворяет ли матрица ( ))0()0(
ijzZ = ограничениям (11). С этой
целью вычислим
,
1
)0(∑
=
−=ε
m
i
iiji dz 1,2,...i m= . (22)
Если для всех 1,2,...i m= , ,0≤iε то полученная матрица )0(Z удовлетворяет всем
ограничениям (11)–(12) и определяет решение задачи. Если же это не так, переходим ко
второму этапу.
Второй этап. Коррекция матрицы )( ijzZ = выполняется следующим образом. Ис-
пользуя (22), выделим из множества { }mE ,...,2,1= строк матрицы )0(Z два подмножества.
,0,
1
)0()(
>−=ε∈= ∑
=
+
m
i
iiji dzEiE
.0,
1
)0()(
≤−=ε∈= ∑
=
−
m
i
iiji dzEiE
Строки, принадлежащие подмножеству ( )E + , будем называть избыточными, а строки,
принадлежащие подмножеству ( )E − , будем называть недостаточными.
Для каждого из столбцов )0(
jZ
найдем множество номеров { }.z,EiE ijj 0>∈=
Далее из
jE выделим подмножества { })()( ++ ∩∈= EEiE jj
и { })()( −− ∈= EiEj
.
ISSN 1028-9763. Математичні машини і системи, 2014, № 1 177
Выберем конкретный столбец 0j . Понятно, что если из какого-либо элемента этого
столбца с номером ( )0 0i j , ( )i E +∈ вычесть некоторое специальным образом выбранное
число ∆ и добавить его к какому-либо элементу этого столбца с номером ( )0 0k j ,
)(−∈Ek , то строка 0i станет менее избыточной, а строка 0k при правильном выборе ∆
станет менее недостаточной. Ясно также, что любое перераспределение значений )0(
ijz в
пределах одного столбца не нарушает ограничений (12). Координаты корректируемых
элементов и допустимое значение ∆ выбираются по правилам:
1. ( ) ( ) ( ) ( )0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
(0) (0) (0) (0)
0 0 0( , , ) arg min .
i j k j i j k j
j i j k j i j k ji k j G z z z z
β β β β = − − ∆ + ∆
(23)
2. { }
000
0
0
0
k
)(
ji
Ek
Ei
;zmin ε−≤∆
−
+
∈
∈
. (24)
Выбор координат корректируемых элементов по правилу (23) обеспечивает мини-
мально возможное снижение целевой функции (14) в результате корректировки. Выбор ∆
в соответствии с (24), с одной стороны, навязан ограничением (13), а с другой, – нецелесо-
образностью перевода недостаточной строки 0k в группу избыточных. В результате про-
ведения коррекции, с учетом (23), (24), получим новый план:
( ) ( ) ( ) ( )[ ]
≠∩≠∩=∪≠
==+
==−
=
.,,
,,,
,,,
0000
)0(
00
)0(
00
)0(
)1(
kiiijjjjz
jjkiz
jjiiz
z
ij
ij
ij
ij ∆
∆
Описанная процедура коррекции продолжается до выполнения всех ограничений
(11).
4. Выводы
Рассмотрена задача рационального распределения n многомерного ресурса при производ-
стве многономенклатурного продукта. Для решения возникающей при этом нелинейной
несепарабельной задачи математического программирования предложена двухэтапная
процедура. На первом этапе отыскивается начальный план задачи, который на втором эта-
пе итерационно корректируется. Сходимость процедуры обеспечивается конструктивно.
СПИСОК ЛИТЕРАТУРЫ
1. Гурин Л.С. Задачи и методы оптимального распределения ресурсов / Гурин Л.С., Дымарский
Я.С., Меркулов А.Д. – М.: Сов. радио, 1968. – 463с.
2. Раскин Л.Г. Анализ сложных систем и элементы теории оптимального управления / Раскин Л.Г.
– М.: Сов. радио, 1976. – 344с.
3. Серая О.В. Методика решения нелинейной задачи распределения многомерного ресурса /
О.В. Серая, Л.Г. Раскин // Вестник НТУ «ХПИ»: сб. науч. тр. Нац. техн. ун-та «ХПИ». – Х.: НТУ
«ХПІ», 2005. – № 56. – С. 137 – 144.
4. Серая О.В. Многомерные модели логистики в условиях неопределенности / Серая О.В. – Х.: ФЛ-
П Стеценко, 2010. – 512 с.
5. Замков О.О. Математические методы в экономике / Замков О.О., Толстопятенко А.В., Черемных
Ю.Н. – М.: МГУ им. М.В. Ломоносова, изд. «ДИС», 1998. – 368 с.
Стаття надійшла до редакції 25.06.2013
|
| id | nasplib_isofts_kiev_ua-123456789-84344 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1028-9763 |
| language | Russian |
| last_indexed | 2025-12-07T16:59:45Z |
| publishDate | 2014 |
| publisher | Інститут проблем математичних машин і систем НАН України |
| record_format | dspace |
| spelling | Раскин, Л.Г. Серая, О.В. Каткова, Т.И. 2015-07-06T16:26:50Z 2015-07-06T16:26:50Z 2014 Нелинейная несепарабельная задача рационального распределения многомерного ресурса при многономенклатурном производстве / Л.Г. Раскин, О.В. Серая, Т.И. Каткова // Математичні машини і системи. — 2014. — № 1. — С. 171-177. — Бібліогр.: 5 назв. — рос. 1028-9763 https://nasplib.isofts.kiev.ua/handle/123456789/84344 519.85 Задача рационального распределения многомерного ресурса при многономенклатурном производстве формализована как нелинейная несепарабельная задача математического программирования. Для решения задачи предложена итерационная процедура с конечным числом шагов. Задача раціонального розподілу багатовимірного ресурсу при багатономенклатурному виробництві формалізована як нелінійна несепарабельна задача математичного програмування. Для вирішення задачі запропонована ітераційна процедура з кінцевим числом кроків. The problem of rational distribution of multidimensional resource under multinomenclature production is formalized as a nonlinear inseparable mathematical programming problem. For solving the problem the iterative procedure with a finite number of steps is suggested. ru Інститут проблем математичних машин і систем НАН України Математичні машини і системи Моделювання і управління Нелинейная несепарабельная задача рационального распределения многомерного ресурса при многономенклатурном производстве Нелінійна несепарабельна задача раціонального розподілу багатовимірного ресурсу при багатономенклатурному виробництві Nonlinear inseparable problem of rational distribution of multidimensional resource under multinomenclature production Article published earlier |
| spellingShingle | Нелинейная несепарабельная задача рационального распределения многомерного ресурса при многономенклатурном производстве Раскин, Л.Г. Серая, О.В. Каткова, Т.И. Моделювання і управління |
| title | Нелинейная несепарабельная задача рационального распределения многомерного ресурса при многономенклатурном производстве |
| title_alt | Нелінійна несепарабельна задача раціонального розподілу багатовимірного ресурсу при багатономенклатурному виробництві Nonlinear inseparable problem of rational distribution of multidimensional resource under multinomenclature production |
| title_full | Нелинейная несепарабельная задача рационального распределения многомерного ресурса при многономенклатурном производстве |
| title_fullStr | Нелинейная несепарабельная задача рационального распределения многомерного ресурса при многономенклатурном производстве |
| title_full_unstemmed | Нелинейная несепарабельная задача рационального распределения многомерного ресурса при многономенклатурном производстве |
| title_short | Нелинейная несепарабельная задача рационального распределения многомерного ресурса при многономенклатурном производстве |
| title_sort | нелинейная несепарабельная задача рационального распределения многомерного ресурса при многономенклатурном производстве |
| topic | Моделювання і управління |
| topic_facet | Моделювання і управління |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/84344 |
| work_keys_str_mv | AT raskinlg nelineinaâneseparabelʹnaâzadačaracionalʹnogoraspredeleniâmnogomernogoresursaprimnogonomenklaturnomproizvodstve AT seraâov nelineinaâneseparabelʹnaâzadačaracionalʹnogoraspredeleniâmnogomernogoresursaprimnogonomenklaturnomproizvodstve AT katkovati nelineinaâneseparabelʹnaâzadačaracionalʹnogoraspredeleniâmnogomernogoresursaprimnogonomenklaturnomproizvodstve AT raskinlg nelíníinaneseparabelʹnazadačaracíonalʹnogorozpodílubagatovimírnogoresursupribagatonomenklaturnomuvirobnictví AT seraâov nelíníinaneseparabelʹnazadačaracíonalʹnogorozpodílubagatovimírnogoresursupribagatonomenklaturnomuvirobnictví AT katkovati nelíníinaneseparabelʹnazadačaracíonalʹnogorozpodílubagatovimírnogoresursupribagatonomenklaturnomuvirobnictví AT raskinlg nonlinearinseparableproblemofrationaldistributionofmultidimensionalresourceundermultinomenclatureproduction AT seraâov nonlinearinseparableproblemofrationaldistributionofmultidimensionalresourceundermultinomenclatureproduction AT katkovati nonlinearinseparableproblemofrationaldistributionofmultidimensionalresourceundermultinomenclatureproduction |