Другий метод комбінаторного відсікання та розв’язування комбінаторних транспортних задач на переставленнях
У статті розглядається комбінаторна транспортна задача на переставленнях. Для класу задач, до якого вона відноситься, запропоновано та обґрунтовано другий метод комбінаторного відсікання. В запропонованому методі, на відміну від відомого методу комбінаторного відсікання, пропонується об’єднати перев...
Saved in:
| Published in: | Штучний інтелект |
|---|---|
| Date: | 2011 |
| Main Authors: | , , , |
| Format: | Article |
| Language: | Ukrainian |
| Published: |
Інститут проблем штучного інтелекту МОН України та НАН України
2011
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/58824 |
| 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. — № 1. — С. 161-167. — Бібліогр.: 19 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859571089644978176 |
|---|---|
| author | Ємець, О.О. Ємець, Є.М. Ольховський, Д.М. Парфьонова, Т.О. |
| author_facet | Ємець, О.О. Ємець, Є.М. Ольховський, Д.М. Парфьонова, Т.О. |
| citation_txt | Другий метод комбінаторного відсікання та розв’язування комбінаторних транспортних задач на переставленнях / Ємець О.О., Ємець Є.М., Ольховський Д.М., Парфьонова Т.О. // Штучний інтелект. — 2011. — № 1. — С. 161-167. — Бібліогр.: 19 назв. — укр. |
| collection | DSpace DC |
| container_title | Штучний інтелект |
| description | У статті розглядається комбінаторна транспортна задача на переставленнях. Для класу задач, до якого вона відноситься, запропоновано та обґрунтовано другий метод комбінаторного відсікання. В запропонованому методі, на відміну від відомого методу комбінаторного відсікання, пропонується об’єднати перевірку умови належності отриманого розв’язування переставному многограннику з перевіркою додаткових лінійних умов задачі. Відсікання пропонується робити тільки на переставному многограннику.
В статье рассматривается комбинаторная транспортная задача на перестановках. Для класса задач, к которому она относится, предложен и обоснован второй метод комбинаторного отсечения. В предложенном методе, в отличие от известного метода комбинаторного отсечения, предлагается объединить проверку условия соответствия полученного решения переставному многограннику с проверкой дополнительных линейных условий задачи. Отсечениие предлагается совершать только на переставном многограннике.
Combinatorial transport task on removals is looked at the article. The second method of combinatorial cutting off is offered and proved for the class of tasks. It is offered to combine appliance condition checking of the removal polyhedron outcome-point with checking of the task extra linear conditions in the proposed method in contrast to well-known method of cutting off. The cutting off is proposed to do only on the removal polyhedron.
|
| first_indexed | 2025-11-26T23:26:47Z |
| format | Article |
| fulltext |
«Штучний інтелект» 1’2011 161
2Є
УДК 519.85
Ємець О.О., Ємець Є.М., Ольховський Д.М., Парфьонова Т.О.
Полтавський університет економіки та торгівлі, м. Полтава, Україна
contacts@informatics.org.ua
Другий метод комбінаторного відсікання
та розв’язування комбінаторних
транспортних задач на переставленнях
У статті розглядається комбінаторна транспортна задача на переставленнях. Для класу задач, до якого
вона відноситься, запропоновано та обґрунтовано другий метод комбінаторного відсікання. В запропонованому
методі, на відміну від відомого методу комбінаторного відсікання, пропонується об’єднати перевірку
умови належності отриманого розв’язування переставному многограннику з перевіркою додаткових лінійних
умов задачі. Відсікання пропонується робити тільки на переставному многограннику.
Вступ
Розвиток математичного моделювання, зокрема на базі комбінаторної оптиміза-
ції [1-8], виокремлення задач евклідової комбінаторної оптимізації, дослідження влас-
тивостей задач евклідової комбінаторної оптимізації та евклідових комбінаторних
множин обумовили розробку ряду нових методів для комбінаторних оптимізаційних
задач [3-8]. Зокрема, для задач оптимізації на переставленнях був запропонований та
обґрунтований метод комбінаторного відсікання [5], [9-14]. Задачі комбінаторної оп-
тимізації актуальні і при розробці систем штучного інтелекту. Це обумовлюється тим,
що вони є моделями задач вибору, які необхідно розв’язувати в системах штучного
інтелекту.
Актуальною є необхідність подальшого дослідження підходу, що ґрунтується
на ідеях методів відсікання для задач оптимізації лінійних функцій з лінійними додат-
ковими обмеженнями, в яких допустима точка має переставні властивості.
У цій роботі пропонується і обґрунтовується другий метод комбінаторного відсікан-
ня в застосуванні до комбінаторної транспортної задачі на переставленнях [15], [16].
Постановка задачі
В роботах [15], [16] вводиться до розгляду та досліджується комбінаторна транс-
портна задача на множині переставлень kE G , що має математичну модель: знайти
*
1 1
min
k
m n
ij ij
x R i j
C x c x
;
* * *
11
1 1
,..., arg min
k
m n
mn ij ij
x R i j
x x x c x
,
за умов
1
n
ij i
j
x a
mi J ;
Ємець О.О., Ємець Є.М., Ольховський Д.М., Парфьонова Т.О.
«Искусственный интеллект» 1’2011 162
2Є
1
m
ij i
i
x b
nj J ;
11,..., mn kx x x E G ,
де k m n , ia , jb , ijc – задані сталі, G – задана мультимножини обсягів можливих
перевезень 1,..., kG g g , kE G – множина переставлень з повтореннями з елемен-
тів мультимножини 1,...., kG g g , основа S G якої має елементів: S G .
Сенс параметрів ia – обсяг виробництва в пункті виробництва i mi J ; jb – обсяг
споживання в пункті споживання j nj J ; ijc – тариф на перевезення з пункту ви-
робництва i в пункт споживання j mi J , nj J .
Ця модель є частковим випадком наступної задачі.
Розглянемо максимізацію лінійної функції за додаткових лінійних обмежень на
множині переставлень, тобто задачу: знайти пару * ,C y y , яка визначається як
1
max
n
n
j j
y R j
C y c y
, (1)
1
1
,..., arg max
n
n
n j j
y R j
y y y c y
(2)
за додаткових лінійних умов
1
n
ij j i
j
a y b
, ri J ; (3)
0jy , nj J (4)
та за комбінаторних обмежень
1 1,..., ,...., k
k k kx x x y y E G R , (5)
де n , r , k , – визначені натуральні константи k n , nR – n -вимірний арифме-
тичний евклідовий простір, 1, 2,...,rJ r – множина перших r натуральних чисел, jc ,
ija , ib – задані дійсні числа ri J , nj J , а kE G – множина переставлень з повто-
реннями з елементів мультимножини 1,...., kG g g , основа S G якої має елемен-
тів: S G .
Другий метод комбінаторного відсікання
для розв’язування задачі (1) – (5)
У роботах [5], [9-14] запропоновано і обґрунтовано метод комбінаторного від-
сікання (назвемо його – перший метод) для задачі (1) – (5). Суттєвою є перевірка умови
kx П G . (6)
У розглянутій схемі методу відсікання многогранник M визначається як много-
гранниками kП G та (3), (4), так і нерівностями-відсіканнями, які приєднуються до (3)
в ході розв’язування задачі (1) – (5).
Другий метод комбінаторного відсікання та розв’язування…
«Штучний інтелект» 1’2011 163
2Є
У даній роботі пропонується відсікання робити тільки на переставному много-
граннику, а перевірку умови
kx E G
(7)
об’єднати з перевіркою умови (3).
Викладемо цей (другий) метод комбінаторного відсікання.
Крок 0. Задаємо цілочислову змінну q рівною нулю: 0q .
Крок 1. Розв’язуємо ДЗЛП (1), (2), (4), (6). (Зауважимо, що за умови 0ig , умо-
ва (4) автоматично виконується). Розв’язання ДЗЛП позначимо 1 ,..., ny y y , де
1 ,..., ky y x .
Зауваження 1. Задача (1), (2), (4), (6) є ЗЛП, оскільки переставний многогран-
ник kП G , як відомо [3], [4], описується такою системою лінійних обмежень:
1
i j
i j
x g
, kJ , k ; (8)
1 1
k k
i j
i j
x g
, (9)
де вважається, що елементи мультимножини G упорядковані за неспаданням:
1 2 ... kg g g . (10)
Зауваження 2. Задачу (1), (2), (4), (6), або, що теж саме ЗЛП (1), (2), (4), (8), (9),
можна розв’язувати безпосередньо методом, що дає вершину допустимої області (сим-
плекс-методом чи методом штучного базису), а можна у випадку n k (повністю
комбінаторної задачі) скористатися наступними відомими фактами. По-перше, загаль-
но відомо [17], що розв’язання ЗЛП досягається у вершині допустимого многогранни-
ка. По-друге, переставний многогранник має [3], [4] властивість збіжності множини
його вершин kvert П G з множиною переставлень kE G :
k kE G vertП G . (11)
По-третє, відоме [3], [4] розв’язання лінійної безумовної задачі оптимізації на мно-
жині переставлень (в [4] на с. 79 теорема 3.1 та зауваження 3.3 на с. 82). Це розв’язан-
ня знаходиться так: нехай
1 2
...
k
c c c , (12)
де 1,..., k – переставлення з елементів kJ (або коротко kk k k kE J E J ),
виконується умова (10). Тоді *x з (2) визначається умовами:
*
1i k ix g , ki J . (13)
Зауваження 3. По виконанню кроку 1 умова (7) завжди виконується, оскільки
допустимий многогранник М, що є опуклою оболонкою множини E M conv E ,
має властивість: vert M vert conv E E .
Для множини E ця властивість означає вершинну розташованість стосовно мно-
гогранника M [13], [14]. Обґрунтовування цього факту дано далі.
Крок 2. Перевіряємо умову, що точка * * *
1 ,..., ny y y задовольняє співвідношен-
ням (3), (4).
Якщо умови:
*
1
n
ij j i
j
a y b
, ri J ; (14)
Ємець О.О., Ємець Є.М., Ольховський Д.М., Парфьонова Т.О.
«Искусственный интеллект» 1’2011 164
2Є
* 0jy , nj J , (15)
виконалися, то вихідна задача (1) – (5) розв’язана. Алгоритм закінчує роботу. В іншо-
му разі – перехід на крок 3.
Крок 3. Збільшуємо q на одиницю.
Крок 4. Будуємо нерівність-відсікання точки *y :
1j
j j
i
i J i
y
, (16)
де J – множина небазисних змінних в точці *y ,
: 0
min
ij
i t
j i
ij tj
, j J . (17)
В (17) ij , j – елементи останньої симплекс-таблиці ДЗЛП ( i – номер її рядка,
j – номер стовпця небазисної змінної).
Перетворюємо нерівність (16) у рівність:
1j
j j
i
n q
i J i
y
y
, (18)
де 0n qy – додаткова змінна, та додаємо до системи (6) (що теж саме до системи (8),
(9)). У формулах (16), (18) 1,...,J j j – множина номерів небазисних змінних в ос-
танній точці *y (одержаної як розв’язання поточної ДЗЛП); – кількість небазисних змін-
них. Переходимо на крок 1.
Правильність відсікання (тобто те, що *y відсікається, а жодна допустима точ-
ка задачі (1) – (5) – ні) обґрунтовує теорема 1.
Теорема 1. Нехай нерівність-відсікання задається формулою (16), в якій вели-
чини j визначаються умовою (17). Нехай точка * * *
1 ,..., n qy y y – розв’язання ДЗЛП,
яке відсікається. Тоді нерівності (16) точка *y не задовольняє, а всі вершини, що су-
міжні з *y в допустимому многограннику ДЗЛП, справджують нерівність (16) як рів-
ність. Всі переставлення з kE G , що задовольняють умови (3), (4), задовольняють і (16).
Доведення. У формулі (16) при підстановці в неї точки *y всі змінні в лівій час-
тині дорівнюють нулю як небазисні в точці *y змінні. Отже з (16) в *y маємо 0 1 ,
що свідчить про те, що координати точки *y нерівність (16) не задовольняють. За по-
будовою [17], [18] суміжної з точкою *y вершини y допустимого многогранника
ДЗЛП в точці y будемо мати такі координати з тих, що входять у формулу (16): деяка
координата
jiy (для кожної з точок y власна), ji J , j J , J , дорівнює чис-
лу
ji , що обчислюється за (17), а усі інші координати точки y з (16) – нульові. Тобто
в довільній суміжній з *y вершині y допустимого многогранника ДЗЛП нерівність (16)
приймає вигляд: / 0 ... 0 1
j ji i , або 1 1 . Оскільки множина переставлень kE G
елементів з G є вершинно розташованою, то жодного переставлення, що не лежить
у вершині допустимого многогранника ДЗЛП, немає. Теорема доведена.
Другий метод комбінаторного відсікання та розв’язування…
«Штучний інтелект» 1’2011 165
2Є
Теорема 2. (Критерій переходу на гіпергрань переставного многогранника в ме-
тоді комбінаторного відсікання). Нерівність-відсікання в першому або другому методі
комбінаторного відсікання в задачах на множині переставлень kE G , яка (нерівність)
має вигляд:
1
k
j j
j
a x b
, (19)
визначає гіпергрань
1
k
j j
j
a x b
многогранника k kП G conv E G , якщо і тільки якщо:
0,1ja , kj J ; (20)
1
t
j
j
b g
(21)
або
1
1
t
k j
j
b g
, (22)
де
1
k
j
j
t a
. (23)
Доведення. Як відомо [3], [4], гіпергрань многогранника kП G визначається
нерівностями (8), або з урахуванням рівності (9) за умови (10) нерівностями, еквівалент-
ними (8):
1
1
i k j
i j
x g
, kJ , k (24)
і тільки цими нерівностями.
У системі, що описує kП G , при виконанні умов теореми є нерівність, що від-
різняється від (19) знаком. Якщо нерівність (19) (а це, нагадаємо, правильне відсікання)
мала той же знак, що і нерівність з (8) або (24), яка має такі ж ліву і праву частину,
що і (19), то така нерівність нічого б не відсікала від kП G , тобто не була правиль-
ним відсіканням. Це і означає необхідність і достатність умов (19) – (23).
Отже гіпергрань в kП G визначається за умов (20) – (23) рівністю
1
k
j j
j
a x b
. (25)
Теорема 3. (Критерій переходу на гіпергрань загального переставного многогран-
ника в методі комбінаторного відсікання). Нерівність-відсікання (19) в першому або
другому методі комбінаторного відсікання в задачах на загальній множині перестав-
лень kE G , де мультимножина G має основу 1,...,S G e e та первинну специфі-
кацію 1,..., , визначає гіпергрань (25) многогранника k kП G conv E G , якщо
і тільки якщо виконуються умови (20) – (23), а також:
1) якщо 1 1 , то t , що обчислюється за (23), таке: 1\ 2,3,...,kt J ;
2) якщо 1 , то t за (23) таке: \ , 1,..., 2kt J k k k .
Ємець О.О., Ємець Є.М., Ольховський Д.М., Парфьонова Т.О.
«Искусственный интеллект» 1’2011 166
2Є
Доведення. Як відомо [4], [19], якщо 1 1 , то надлишковими нерівностями в сис-
темі (8), що описує kП G , є нерівності спілок [4], [19] з номерами з множини 12,3,..., .
У випадку 1 надлишковими в (8) за [4], [19] є нерівності спілок з номерами ,k
1,..., 2k k . Як показано в [19], інших надлишкових нерівностей система (8) не
має. Далі доведення повторює доведення теореми 3 з заміною многогранника kП G
на kП G , та посиланням на [19], де визначені всі гіперграні загального переставного
многогранника.
Твердження 4. Перехід на грань у другому методі комбінаторного відсікання
на множині переставлень kE G відбувається не раніше, ніж через Bk відсікань, де
! ( 1)!Bk k k (26)
Доведення. Щоб перейти на грань треба відсікти всі вершини, крім вершини гра-
ні, на яку переходять. Перший доданок в (26) – це кількість вершин (переставлень) у
множині kE . У цій формулі віднімається максимально можлива кількість вершин на
гіпергрань многогранника kП .
У многограннику переставлень kП без повторень очевидно – максимальна кіль-
кість вершин є на гіперграні вигляду:
1ix g
або
1 2
k k
j j
j j
j i
x g
(чи на грані i kx g , або
1
1 1
k k
j j
j j
j i
x g
), тобто 1 !k
Зауваження 4. Перевірити порівнянням з системами, що описують переставний
многогранник, що відсікання дає грань, це 2 1k порівнянь рівнянь у випадку kП , та за [19]
1
2( ) ... ...j s
i ii
k k k kk C C C порівнянь у випадку kП ,
де 11 2 1\ \ 1 \
nj k k ki J J J J , sj J .
Висновки
У роботі розглянута комбінаторна транспортна задача на переставленнях. Для кла-
су задач, до якого вона відноситься, – умовних задачах з лінійною цільовою функцією
на множині переставлень – обґрунтовано другий метод комбінаторного відсікання.
Як напрям подальших досліджень доцільно розглянути можливість приєднання
необхідних та відкидання спрацювавших та вже зайвих обмежень, що дозволить, і в
другому і в першому методах відсікання, значно збільшити вимірність задач, що мо-
жуть бути розв’язані.
Література
1. Сергиенко И.В. Математические модели и методы решения задач дискретной оптимизации / И.В. Сер-
гиенко, М.Ф. Каспшицкая – К. : Наук. думка, 1988. – 472 с.
Другий метод комбінаторного відсікання та розв’язування…
«Штучний інтелект» 1’2011 167
2Є
2. Сергиенко И.В. Задачи дискретной оптимизации: Проблемы, методы, решения, исследования / И.В. Сер-
гиенко, В.П. Шило. – К. : Наук. думка, 2003. – 265 с.
3. Емец О.А. Евклидовы комбинаторные множества и оптимизация на них. Новое в математическом
программировании : [учебн. пособие] / Емец О.А. – К. : УМК ВО, 1992. – 92 с.
4. Стоян Ю.Г. Теорія і методи евклідової комбінаторної оптимізації / Ю.Г. Стоян, О.О. Ємець. – Київ :
Інститут систем. досліджень освіти, 1993. – 188 с.
5. Стоян Ю.Г. Оптимізація на полірозміщеннях: теорія та методи : [монографія] / Стоян Ю.Г., Ємець О.О.,
Ємець Є.М. – Полтава : РВЦ ПУСКУ, 2005. – 103 с.
6. Ємець О.О. Задачі комбінаторної оптимізації з дробово-лінійними цільовими функціями : [моно-
графія] / О.О. Ємець, Л.М. Колєчкіна. – К. : Наук. думка, 2005. – 117 с.
7. Ємець О.О. Задачі оптимізації на полікомбінаторних множинах: властивості та розв’язування :
[монографія] / О.О. Ємець, О.В. Роскладка. – Полтава : РВЦ ПУСКУ, 2006. – 129 с.
8. Емец О.А. Комбинаторная оптимизация на размещениях : [монография] / О.А. Емец, Т.Н. Барбо-
лина. – К. : Наук. думка, 2008. – 159 с.
9. Емец О.А. Об одном методе отсечений для задач комбинаторной оптимизации / О.А. Емец // Эко-
номика и матем. методы. – 1997. – Т. 33, вып. 4. – С. 120-129.
10. Ємець О.О. Відсікання в лінійних частково комбінаторних задач евклідової комбінаторної оптимі-
зації / О.О. Ємець, Є.М. Ємець // Доп. НАН України. – 2000. – № 9. – С. 105-109.
11. Емец О.А. Отсечения в линейных частично комбинаторных задачах оптимизации на перестановках /
О.А. Емец, Е.М. Емец // Экономика и матем. методы. – 2001. – Т. 37. – С. 118-121.
12. Емец О.А. Решение задач оптимизации с дробно-линейными целевыми функциями и дополнитель-
ными линейными ограничениями на перестановках / О.А. Емец, Л.Н. Колечкина // Кибернетика и
систем. анализ. – 2004. – № 3. – С. 30-43.
13. Ємець О.О. Нелінійні задачі комбінаторної оптимізації на вершинно розташованих множинах та
їх розв’язування / О.О. Ємець, Т.В. Чілікіна // Динамические системы. – 2004. – Вып. 18. – Симфе-
рополь : Тавр. нац. университет. – С. 160-165.
14. Емец О.А. Модификация метода комбинаторного отсечения в задачах оптимизации на вершинно
расположенных множествах / О.А. Емец, Е.М. Емец // Кибернетика и сист. анализ. – 2009. – № 5. –
С. 129-136.
15. Ємець О.О. Транспортні задачі комбінаторного типу / О.О. Ємець, Т.О. Парфьонова // Вестник Харь-
ковского национального автомобильно-дорожного университета. – 2005. – Вып. 29. – С. 162-164.
16. Ємець О.О. Наближений метод для розв’язування комбінаторних транспортних задач / О.О. Ємець,
Т.О. Парфьонова // Радиоэлектроника и информатика. – 2006. – № 2. – С. 39-41.
17. Математические методы исследования операций : [учебн. пособие для вузов] / Ермольев Ю.М.,
Ляшко И.И., Михалевич В.С., Тюптя В.И. – К : Вища школа, 1979. – 312 с.
18. Акулич И.Л. Математическое программирование в примерах и задачах / Акулич И.Л. – М. : Выс-
шая школа, 1986. – 319 с.
19. Ємець О.О. Загальний переставний многогранник: незвідна система лінійних обмежень та рівняння
всіх гіперграней / О.О. Ємець, С.І. Недобачій // Наукові вісті НТУУ «КПІ». – 1998. – № 1. – С. 100-106.
О.А. Емец, Е.М. Емец, Д.М. Ольховский, Т.О. Парфенова
Второй метод комбинаторного отсечения и разрешения
комбинаторных транспортных задач на перестановках
В статье рассматривается комбинаторная транспортная задача на перестановках. Для класса задач, к
которому она относится, предложен и обоснован второй метод комбинаторного отсечения. В предложенном
методе, в отличие от известного метода комбинаторного отсечения, предлагается объединить проверку
условия соответствия полученного решения переставному многограннику с проверкой дополнительных
линейных условий задачи. Отсечениие предлагается совершать только на переставном многограннике.
O.O. Yemets, E.M. Yemets, D.M. Olhovskiy, J.O. Parfionova
The Second Method of Combinational Cutting and Solution
of Combinational Transport Tasks on Removals
Combinatorial transport task on removals is looked at the article. The second method of combinatorial cutting off
is offered and proved for the class of tasks. It is offered to combine appliance condition checking of the removal
polyhedron outcome-point with checking of the task extra linear conditions in the proposed method in contrast to
well-known method of cutting off. The cutting off is proposed to do only on the removal polyhedron.
Стаття надійшла до редакції 22.12.2010.
|
| id | nasplib_isofts_kiev_ua-123456789-58824 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1561-5359 |
| language | Ukrainian |
| last_indexed | 2025-11-26T23:26:47Z |
| publishDate | 2011 |
| publisher | Інститут проблем штучного інтелекту МОН України та НАН України |
| record_format | dspace |
| spelling | Ємець, О.О. Ємець, Є.М. Ольховський, Д.М. Парфьонова, Т.О. 2014-03-31T11:38:00Z 2014-03-31T11:38:00Z 2011 Другий метод комбінаторного відсікання та розв’язування комбінаторних транспортних задач на переставленнях / Ємець О.О., Ємець Є.М., Ольховський Д.М., Парфьонова Т.О. // Штучний інтелект. — 2011. — № 1. — С. 161-167. — Бібліогр.: 19 назв. — укр. 1561-5359 https://nasplib.isofts.kiev.ua/handle/123456789/58824 519.85 У статті розглядається комбінаторна транспортна задача на переставленнях. Для класу задач, до якого вона відноситься, запропоновано та обґрунтовано другий метод комбінаторного відсікання. В запропонованому методі, на відміну від відомого методу комбінаторного відсікання, пропонується об’єднати перевірку умови належності отриманого розв’язування переставному многограннику з перевіркою додаткових лінійних умов задачі. Відсікання пропонується робити тільки на переставному многограннику. В статье рассматривается комбинаторная транспортная задача на перестановках. Для класса задач, к которому она относится, предложен и обоснован второй метод комбинаторного отсечения. В предложенном методе, в отличие от известного метода комбинаторного отсечения, предлагается объединить проверку условия соответствия полученного решения переставному многограннику с проверкой дополнительных линейных условий задачи. Отсечениие предлагается совершать только на переставном многограннике. Combinatorial transport task on removals is looked at the article. The second method of combinatorial cutting off is offered and proved for the class of tasks. It is offered to combine appliance condition checking of the removal polyhedron outcome-point with checking of the task extra linear conditions in the proposed method in contrast to well-known method of cutting off. The cutting off is proposed to do only on the removal polyhedron. uk Інститут проблем штучного інтелекту МОН України та НАН України Штучний інтелект Моделирование объектов и процессов Другий метод комбінаторного відсікання та розв’язування комбінаторних транспортних задач на переставленнях Второй метод комбинаторного отсечения и разрешения комбинаторных транспортных задач на перестановках The Second Method of Combinational Cutting and Solution of Combinational Transport Tasks on Removals Article published earlier |
| spellingShingle | Другий метод комбінаторного відсікання та розв’язування комбінаторних транспортних задач на переставленнях Ємець, О.О. Ємець, Є.М. Ольховський, Д.М. Парфьонова, Т.О. Моделирование объектов и процессов |
| title | Другий метод комбінаторного відсікання та розв’язування комбінаторних транспортних задач на переставленнях |
| title_alt | Второй метод комбинаторного отсечения и разрешения комбинаторных транспортных задач на перестановках The Second Method of Combinational Cutting and Solution of Combinational Transport Tasks on Removals |
| title_full | Другий метод комбінаторного відсікання та розв’язування комбінаторних транспортних задач на переставленнях |
| title_fullStr | Другий метод комбінаторного відсікання та розв’язування комбінаторних транспортних задач на переставленнях |
| title_full_unstemmed | Другий метод комбінаторного відсікання та розв’язування комбінаторних транспортних задач на переставленнях |
| title_short | Другий метод комбінаторного відсікання та розв’язування комбінаторних транспортних задач на переставленнях |
| title_sort | другий метод комбінаторного відсікання та розв’язування комбінаторних транспортних задач на переставленнях |
| topic | Моделирование объектов и процессов |
| topic_facet | Моделирование объектов и процессов |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/58824 |
| work_keys_str_mv | AT êmecʹoo drugiimetodkombínatornogovídsíkannâtarozvâzuvannâkombínatornihtransportnihzadačnaperestavlennâh AT êmecʹêm drugiimetodkombínatornogovídsíkannâtarozvâzuvannâkombínatornihtransportnihzadačnaperestavlennâh AT olʹhovsʹkiidm drugiimetodkombínatornogovídsíkannâtarozvâzuvannâkombínatornihtransportnihzadačnaperestavlennâh AT parfʹonovato drugiimetodkombínatornogovídsíkannâtarozvâzuvannâkombínatornihtransportnihzadačnaperestavlennâh AT êmecʹoo vtoroimetodkombinatornogootsečeniâirazrešeniâkombinatornyhtransportnyhzadačnaperestanovkah AT êmecʹêm vtoroimetodkombinatornogootsečeniâirazrešeniâkombinatornyhtransportnyhzadačnaperestanovkah AT olʹhovsʹkiidm vtoroimetodkombinatornogootsečeniâirazrešeniâkombinatornyhtransportnyhzadačnaperestanovkah AT parfʹonovato vtoroimetodkombinatornogootsečeniâirazrešeniâkombinatornyhtransportnyhzadačnaperestanovkah AT êmecʹoo thesecondmethodofcombinationalcuttingandsolutionofcombinationaltransporttasksonremovals AT êmecʹêm thesecondmethodofcombinationalcuttingandsolutionofcombinationaltransporttasksonremovals AT olʹhovsʹkiidm thesecondmethodofcombinationalcuttingandsolutionofcombinationaltransporttasksonremovals AT parfʹonovato thesecondmethodofcombinationalcuttingandsolutionofcombinationaltransporttasksonremovals |