Лінійні умовні задачі комбінаторної оптимізації на переставленнях та їх розв’язування
У статті розглядається умовна лінійна повністю комбінаторна задача оптимізації на переставленнях. Пропонується її розв’язування методом гілок та меж. Визначено три можливі варіанти оцінювання допустимих підмножин в методі гілок та меж. Запропоновано правила галуження та відсікання допустимих підмнож...
Saved in:
| Published in: | Штучний інтелект |
|---|---|
| Date: | 2011 |
| Main Authors: | , , , |
| Format: | Article |
| Language: | Ukrainian |
| Published: |
Інститут проблем штучного інтелекту МОН України та НАН України
2011
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/58833 |
| 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: | Лінійні умовні задачі комбінаторної оптимізації на переставленнях та їх розв’язування / О.О. Ємець, Є.М. Ємець, Т.О. Парфьонова, Т.В. Чілікіна // Штучний інтелект. — 2011. — № 2. — С. 131-136. — Бібліогр.: 13 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859857215356141568 |
|---|---|
| author | Ємець, О.О. Ємець, Є.М. Парфьонова, Т.О. Чілікіна, Т.В. |
| author_facet | Ємець, О.О. Ємець, Є.М. Парфьонова, Т.О. Чілікіна, Т.В. |
| citation_txt | Лінійні умовні задачі комбінаторної оптимізації на переставленнях та їх розв’язування / О.О. Ємець, Є.М. Ємець, Т.О. Парфьонова, Т.В. Чілікіна // Штучний інтелект. — 2011. — № 2. — С. 131-136. — Бібліогр.: 13 назв. — укр. |
| collection | DSpace DC |
| container_title | Штучний інтелект |
| description | У статті розглядається умовна лінійна повністю комбінаторна задача оптимізації на переставленнях. Пропонується її розв’язування методом гілок та меж. Визначено три можливі варіанти оцінювання допустимих підмножин в методі гілок та меж. Запропоновано правила галуження та відсікання допустимих підмножин в методі гілок та меж для лінійної умовної задачі комбінаторної оптимізації на переставленнях.
В работе рассматривается условная линейная полностью комбинаторная задача отпимизации на перестановках. Предлагается решать её методом ветвей и границ. Определены три возможных варианта оценивания допустимых подмножеств в методе ветвей и границ. Предложены правила ветвления и отсечения допустимых подмножеств в методе ветвей и границ для условной линейной комбинаторной задачи отпимизации на перестановках.
In the article the hypothetical linear fully combinatorial task of optimization on transpositions is considered. It is suggested to solve it by the branch-and-bound method. Certain three possible variants of evaluation of possible subsets in the branch-and-bound method. The rules of branching and pruning of possible subsets in the branch-and-bound method for the hypothetical linear combinatorial task of optimization at transpositions are offered.
|
| first_indexed | 2025-12-07T15:44:14Z |
| format | Article |
| fulltext |
«Штучний інтелект» 2’2011 131
2Є
УДК 519.85
О.О. Ємець, Є.М. Ємець, Т.О. Парфьонова, Т.В. Чілікіна
Полтавський університет економіки та торгівлі, м. Полтава, Україна
tv.0502@gmail.com
Лінійні умовні задачі
комбінаторної оптимізації
на переставленнях та їх розв’язування
У статті розглядається умовна лінійна повністю комбінаторна задача оптимізації на переставленнях.
Пропонується її розв’язування методом гілок та меж. Визначено три можливі варіанти оцінювання
допустимих підмножин в методі гілок та меж. Запропоновано правила галуження та відсікання
допустимих підмножин в методі гілок та меж для лінійної умовної задачі комбінаторної оптимізації
на переставленнях.
Останні десятиліття у зв’язку з потребами практики швидко розвивається теорія і
методи дискретної та комбінаторної оптимізації [1-9]. Широкий клас задач оптимізації
складають задачі евклідової умовної оптимізації на переставленнях. Для цих задач та їх
окремих постановок [4-9] використовуються як точні, так і наближені методи. При цьому
алгоритм методу гілок і меж використовуються як у схемах точних методів [10], [11], так і
в схемах одержання наближених розв’язків названих задач.
Мета даної статті – розвинути методику оцінювання допустимих множин в
методі гілок та меж та обґрунтувати підхід до розгалуження допустимих множин.
Постановка лінійної задачі. Розглянемо умовну лінійну повністю комбінаторну
задачу оптимізації на переставленнях [4], тобто задачу знаходження пари , С x x :
1
min
k
k
j j
x R j
C x c x
; (1)
1
arg min
k
k
j j
x R j
x c x
(2)
за умов
1
, i=1,2,...,l
k
ij j j
j
a x b
; (3)
1
, i=l+1, l+2,...,m
k
ij j j
j
a x b
; (4)
1,..., k knx x x E G , (5)
де knE G – множина переставлень з елементів мультимножини 1,..., kG g g , серед
яких n елементів різних; , , ij j ja b c – задані дійсні числа для всіх можливих в задачі
індексах i та j , а , m, nk – задані натуральні сталі, n k , l – ціла стала 0, l ml .
Ємець О.О., Ємець Є.М., Парфьонова Т.О., Чілікіна Т.В.
«Искусственный интеллект» 2’2011 132
2Є
Розв’язуючи задачу (1) – (5) методом гілок та меж, треба вміти давати оцінку
допустимих множин iD , на яких розбита підмножина допустимих розв’язків D ,
1, 2,..., pi . Тобто множин iD , що мають властивості:
;...21 DDDD p (6)
i pD i J ; (7)
pji JjijiDD , ; , (8)
де тут і далі 1, 2,..., ppJ позначимо множину перших p натуральних чисел. Як
відомо [12], [13] за оцінку множини iD в задачі знаходження
xFxF
kRx
min , (9)
arg min
kx R
x F x
, (10)
kx D R , (11)
де 1:
F
kF x R R , може слугувати число i , яке має властивість:
x D i i pF x i J .
Природним підходом до галуження та оцінювання в методі гілок та меж до
задачі (1) – (5) є такий.
Умова (5) означає, що 1,..., kx x x є переставленням чисел (взагалі кажучи,
дійсних чисел) 1,..., kg g . Нехай, не обмежуючи загальності,
....21 kggg (12)
За множину D слугує множина точок kx R , що задовольняють умовам (3) – (5).
Тому за , t Jt kD можемо розглянути множину
1
,..., ; ;
k
k
t k t ij j i t i l
j J t
D x x x R x g a x a g b i J
\
\
k
ij j i t i m l
j J t
a x a g b i J J
\
, (13)
якщо вона не порожня, kJ .
Очевидно, що для tD та sD в представлені (13) виконується (8), а
1
k
t
t
D D
.
Непорожню множину 1
1i
D , якщо вона містить принаймні два елементи вигляду
(13), можна розгалужувати на підмножини 1 2
1 1, t Ji t kD
,
1 2
1 1 1 21 1 2 1,..., , , , ; k
i t k iD x x x R x g x g t i
1 1 2
1 2
,
\
k
ij j i i i t i m l
j J
a x a g a g b i J J
\
. (14)
Очевидно, що для 1 2
1i tD та 1 2
1i sD в представлені (14) виконується (8), а
1 2 1
1 1
1
1
k
i t i
t
D D
.
Лінійні умовні задачі комбінаторної оптимізації на переставленнях…
«Штучний інтелект» 2’2011 133
2Є
На 1r -му рівні аналогічно розбиття 1r k допустимої множини матимемо
1 2 1
1 2 1
...
... 1,..., ;...; , , r r
r j r
k
i i i t k ij t j j kD x x x R x g x g t i i J
1
,...,
;
i j
k r r
ij j i i i l
j J j J
a x a g b i J
\ 1 2
,...,
\
j j
k r
ij j i i i m l
j J j J
a x a g b i J J
\
(15)
З використанням теореми 3.1 з [4] та означення оцінки обґрунтовано наступні
твердження.
Теорема 1. Оцінкою
...1 2
1 2 ...
r
ri i i
множини 1 2
1 2
...
...
r
ri i iD з (15) в методі гілок та меж може
слугувати kr J число
...1 2
1 2 ...
r
j rj
r
i i ii
j J
c g
. (16)
Якщо 0; g 0 i Ji j kc та забезпечено виконання умови:
1 2
...
i i ir
c c c ,
яку, позначивши j Ji ji j
rc c , запишемо
1 2 ... r Jr kc c c , (17)
та умови
1 2
...
i i ir
g g g ,
яку, позначивши j J
i ij j
rg g , запишемо
1 2
... r J
r ki i ig g g . (18)
Теорема 2. Оцінкою
...1 2
1 2 ...
r
ri i i
множини 1 2
1 2
...
...
r
ri i iD з (15) в методі гілок та меж може
бути число, що визначається формулою:
...1 2
1 2 ...
1
r
r j j
r
i i i i
j
c g
, (19)
якщо 0; g 0 i Ji i kc .
Теорема 3. Оцінкою
...1 2
1 2 ...
r
ri i i
множини 1 2
1 2
...
...
r
ri i iD з (15) в методі гілок та меж може
бути величина
... ...1 2 1 2
1 2 1 2... ...
1
r r
r r j j
s
i i i i i i i i
j
с g
, (20)
де s k r ; величина
...1 2
1 2 ...
r
ri i i
обчислюється за (19), і
jic та
jig задовольняють умови
(21) та (22) відповідно:
1 2 ... si i ic c c , (21)
1 2
...
si i ig g g . (22)
Теорема 4. Нехай задача (1) – (5) має обмеження вигляду
0
1
j
k
j i
j
x
; (23)
Ємець О.О., Ємець Є.М., Парфьонова Т.О., Чілікіна Т.В.
«Искусственный интеллект» 2’2011 134
2Є
0
1
j
k
j i
j
x
; (24)
0
1
j
k
j i
j
x
(25)
та розв’язується методом гілок та меж 0 00, 0, 0; k ; k ;j k k k k .
Нехай утворена множина допустимих розв’язків 1 2
1 2
...
...
r
ri i iD . Нехай виконується умова
(22) та
1 2 1
0... 0 , ss s k kJ
, (26)
1 1
0... 0 , s
s s k kJ
, (27)
1 1
0... 0 , s
s s k kJ
, (28)
де мультимножини 1 ,..., kA
та 1,..., kA
; 1
,...,
k
B
та 1,..., kB
;
1
,...,
k
Г
та 1,..., kГ
попарно рівні: A A , B B , Г Г , а 0 0k kJ J .
Тоді множина 1 2
1 2
...
...
r
ri i iD порожня, коли
0 min max
1 1
; ;
j s r j
s k s
j s ji i
j j
g g
1 1
1 1
s j r j
s k s
j s ji i
j j
g g
, (29)
та
0 min , (30)
де r k s ; або коли
1 10
1 1 1 1
;
j s r j s j r j
s k s s k s
j s j j s ji i i i
j j j j
g g g g
, (31)
та
0 max , (32)
де r k s ; або коли
0 min max
1 1
; ;
j s r j
s k s
j s ji i
j j
g g
1 1
1 1
s j r j
s k s
j s ji i
j j
g g
, (33)
де r k s .
Теорема 5. Нехай для елементів мультимножини G виконується умова (12), а
коефіцієнти цільової функції упорядковані за спаданням, а допустима множина 1 2
1 2
...
...
r
ri i iD
Лінійні умовні задачі комбінаторної оптимізації на переставленнях…
«Штучний інтелект» 2’2011 135
2Є
задачі (1) – (5) в методі гілок та меж визначається (13) – (15), тоді між оцінками існує
співвідношення:
... ...... 1 2 11 2
1 2 1 2 1
... ... ...
r r rr
r r r r
i i i i i i i i
, (34)
r k ; 1kr J ; 0
1kJ ;
... ... ... ...1 2 1 1 2 1
1 2 1 21 1
... ... ... ...
r r r r r r
r rr r r j r j
i i i i i i i i i i
, (35)
0
1kr J ; 0
1kJ ; 1,..., t r kj i i t J .
В роботі запропоновано новий підхід до розв’язування для лінійних умовних
задач оптимізації на переставленнях на основі використання методу гілок та меж.
Як перспективи подальших досліджень можна вказати поширення цього підходу
до нелінійних задач оптимізації на переставленнях.
Література
1. Сергиенко И.В. Математические модели и методы решения задач дискретной оптимизации /
Сергиенко И.В. − К. : Наукова думка, 1988. − 472 с.
2. Сергиенко И.В. Модели и методы решения на ЭВМ комбинаторных задач оптимизации /
И.В. Сергиенко, М.Ф. Каспшицкая. − К. : Наукова думка, 1981. − 288 с.
3. Сергиенко И.В. Задачи дискретной оптимизации: проблемы, методы решения, исследования /
И.В. Сергиенко, В.П. Шило. – К. : Наукова думка, 2003. – 263 с.
4. Стоян Ю.Г. Теорія і методи евклідової комбінаторної оптимізації / Ю.Г. Стоян, О.О. Ємець. – К. :
Ін-т системних досліджень освіти, 1993. – 188 с.
5. Стоян Ю.Г. Оптимізація на полірозміщеннях: теорія та методи / Стоян Ю.Г., Ємець О.О.,
Ємець Є.М. – Полтава : РВЦ ПУСКУ, 2005. – 103 с.
6. Емец О.А. Евклидовы комбинаторные множества и оптимизация на них. Новое в математическом
программировании : учеб. пособие / Емец О.А. – К. : УМК ВО, 1992. – 92 с.
7. Ємець О.О. Задачі оптимізації на полікомбінаторних множинах: властивості та розв’язування /
О.О. Ємець, О.В. Роскладка. – Полтава : РВЦ ПУСКУ, 2006. – 129 с.
8. Ємець О.О. Задачі комбінаторної оптимізації з дробово-лінійними функціями / О.О. Ємець,
Л.М. Колєчкіна. – К. : Наукова думка, 2005. – 117 с.
9. Емец О.А. Комбинаторная оптимизация на размещениях / О.А. Емец, Т.Н. Барболина. – К. :
Наукова думка, 2008. – 159 с.
10. Ємець О.О Оцінювання допустимих множин розв’язків комбінаторної транспортної задачі на
переставленнях, що розв’язується методом гілок та меж / О.О. Ємець, Т.О. Парфьонова // Наукові
вісті НТУУ «КПІ». – 2010. – № 1. – С. 21-28.
11. Емец О.А. Транспортные задачи на перестановках: свойства оценок в методе ветвей и границ /
О.А. Емец, Т.А. Парфенова // Кибернетика и системный анализ. – 2010. – № 5. – С. 1-7.
12. Математические методы исследования операций : [учеб. пособие для вузов] / Ю.М. Ермольев,
И.И. Ляшко, В.И. Тюптя, В.И. Михалевич. – К. : Вища шк., Головное изд-во, 1979. – 312 с.
13. Линейное и нелинейное программирование / [Ляшенко И.Н., Карагодова Е.А., Черникова Н.В.,
Шор Н.З.]. − К. : Вища школа, 1975. − 372 с.
Lіteratura
1. Sergienko I.V. Kiev : Naukova dumka. 1988. 472 p.
2. Sergienko I.V. Kiev : Naukova dumka. 1981. 288 p.
3. Sergienko I.V. Kiev : Naukova dumka. 2003. 263 p.
4. Stojan Ju.G. Kiev : Іnstytut systemnih doslіdzhen' osvіty. 1993. 188 p.
5. Stojan Ju.G. Poltava : RVC PUSKU. 2005. 103 p.
6. Emec O.A. Kiev : UMK VO. 1992. 92 p.
7. Emec O.A. Poltava : RVC PUSKU. 2006. 129 p.
Ємець О.О., Ємець Є.М., Парфьонова Т.О., Чілікіна Т.В.
«Искусственный интеллект» 2’2011 136
2Є
8. Emec O.A. Kiev : Naukova dumka. 2005. 117 p.
9. Emec O.A. Kiev : Naukova dumka. 2008. 159 p.
10. Emec O.A Naukovі vіstі NTUU «KPІ». 2010.№ 1. P. 21-28
11. Emec O.A. Kibernetika i sistemnyj analiz. 2010. № 5. P. 1-7
12. Ermol'evJu.M. Kiev : Vishha shkola. Golovnoe izd-vo.1979. 312 p.
13. Ljashenko I.N. Kiev : Vishha shkola. 1975. 372 p.
О.А. Емец, Е.М. Емец, Т.А. Парфенова, Т.В. Чиликина
Линейные условные задачи комбинаторной оптимизации на перестановках и их решение
В работе рассматривается условная линейная полностью комбинаторная задача отпимизации на пере-
становках. Предлагается решать её методом ветвей и границ. Определены три возможных варианта
оценивания допустимых подмножеств в методе ветвей и границ. Предложены правила ветвления и
отсечения допустимых подмножеств в методе ветвей и границ для условной линейной комбинаторной
задачи отпимизации на перестановках.
O.O. Yemets, Ye.M. Yemets, T.O. Parfonova., T.V. Chilikina
Linear Hypothetical Problems of Combinatorial Optimization at Transpositions and their Solution
In the article the hypothetical linear fully combinatorial task of optimization on transpositions is considered.
It is suggested to solve it by the branch-and-bound method. Certain three possible variants of evaluation of
possible subsets in the branch-and-bound method. The rules of branching and pruning of possible subsets in
the branch-and-bound method for the hypothetical linear combinatorial task of optimization at transpositions
are offered.
Стаття надійшла до редакції 19.04.2011.
|
| id | nasplib_isofts_kiev_ua-123456789-58833 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1561-5359 |
| language | Ukrainian |
| last_indexed | 2025-12-07T15:44:14Z |
| publishDate | 2011 |
| publisher | Інститут проблем штучного інтелекту МОН України та НАН України |
| record_format | dspace |
| spelling | Ємець, О.О. Ємець, Є.М. Парфьонова, Т.О. Чілікіна, Т.В. 2014-03-31T12:09:46Z 2014-03-31T12:09:46Z 2011 Лінійні умовні задачі комбінаторної оптимізації на переставленнях та їх розв’язування / О.О. Ємець, Є.М. Ємець, Т.О. Парфьонова, Т.В. Чілікіна // Штучний інтелект. — 2011. — № 2. — С. 131-136. — Бібліогр.: 13 назв. — укр. 1561-5359 https://nasplib.isofts.kiev.ua/handle/123456789/58833 519.85 У статті розглядається умовна лінійна повністю комбінаторна задача оптимізації на переставленнях. Пропонується її розв’язування методом гілок та меж. Визначено три можливі варіанти оцінювання допустимих підмножин в методі гілок та меж. Запропоновано правила галуження та відсікання допустимих підмножин в методі гілок та меж для лінійної умовної задачі комбінаторної оптимізації на переставленнях. В работе рассматривается условная линейная полностью комбинаторная задача отпимизации на перестановках. Предлагается решать её методом ветвей и границ. Определены три возможных варианта оценивания допустимых подмножеств в методе ветвей и границ. Предложены правила ветвления и отсечения допустимых подмножеств в методе ветвей и границ для условной линейной комбинаторной задачи отпимизации на перестановках. In the article the hypothetical linear fully combinatorial task of optimization on transpositions is considered. It is suggested to solve it by the branch-and-bound method. Certain three possible variants of evaluation of possible subsets in the branch-and-bound method. The rules of branching and pruning of possible subsets in the branch-and-bound method for the hypothetical linear combinatorial task of optimization at transpositions are offered. uk Інститут проблем штучного інтелекту МОН України та НАН України Штучний інтелект Моделирование объектов и процессов Лінійні умовні задачі комбінаторної оптимізації на переставленнях та їх розв’язування Линейные условные задачи комбинаторной оптимизации на перестановках и их решение Linear Hypothetical Problems of Combinatorial Optimization at Transpositions and their Solution Article published earlier |
| spellingShingle | Лінійні умовні задачі комбінаторної оптимізації на переставленнях та їх розв’язування Ємець, О.О. Ємець, Є.М. Парфьонова, Т.О. Чілікіна, Т.В. Моделирование объектов и процессов |
| title | Лінійні умовні задачі комбінаторної оптимізації на переставленнях та їх розв’язування |
| title_alt | Линейные условные задачи комбинаторной оптимизации на перестановках и их решение Linear Hypothetical Problems of Combinatorial Optimization at Transpositions and their Solution |
| title_full | Лінійні умовні задачі комбінаторної оптимізації на переставленнях та їх розв’язування |
| title_fullStr | Лінійні умовні задачі комбінаторної оптимізації на переставленнях та їх розв’язування |
| title_full_unstemmed | Лінійні умовні задачі комбінаторної оптимізації на переставленнях та їх розв’язування |
| title_short | Лінійні умовні задачі комбінаторної оптимізації на переставленнях та їх розв’язування |
| title_sort | лінійні умовні задачі комбінаторної оптимізації на переставленнях та їх розв’язування |
| topic | Моделирование объектов и процессов |
| topic_facet | Моделирование объектов и процессов |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/58833 |
| work_keys_str_mv | AT êmecʹoo líníiníumovnízadačíkombínatornoíoptimízacíínaperestavlennâhtaíhrozvâzuvannâ AT êmecʹêm líníiníumovnízadačíkombínatornoíoptimízacíínaperestavlennâhtaíhrozvâzuvannâ AT parfʹonovato líníiníumovnízadačíkombínatornoíoptimízacíínaperestavlennâhtaíhrozvâzuvannâ AT čílíkínatv líníiníumovnízadačíkombínatornoíoptimízacíínaperestavlennâhtaíhrozvâzuvannâ AT êmecʹoo lineinyeuslovnyezadačikombinatornoioptimizaciinaperestanovkahiihrešenie AT êmecʹêm lineinyeuslovnyezadačikombinatornoioptimizaciinaperestanovkahiihrešenie AT parfʹonovato lineinyeuslovnyezadačikombinatornoioptimizaciinaperestanovkahiihrešenie AT čílíkínatv lineinyeuslovnyezadačikombinatornoioptimizaciinaperestanovkahiihrešenie AT êmecʹoo linearhypotheticalproblemsofcombinatorialoptimizationattranspositionsandtheirsolution AT êmecʹêm linearhypotheticalproblemsofcombinatorialoptimizationattranspositionsandtheirsolution AT parfʹonovato linearhypotheticalproblemsofcombinatorialoptimizationattranspositionsandtheirsolution AT čílíkínatv linearhypotheticalproblemsofcombinatorialoptimizationattranspositionsandtheirsolution |