Математичне моделювання практичних задач у вигляді лінійних задач на переставленнях та їх розв’язання з застосуванням властивостей комбінаторних многогранників
В роботі дано огляд сучасних підходів до розв’язання умовних лінійних задач на комбінаторних множинах. Особливу увагуприділено дослідженню допустимих областей переставних многогранників з додатковими обмеженнями спеціальноговигляду. Показано, що в окремих випадках додаткове дослідження допустимої об...
Gespeichert in:
| Datum: | 2007 |
|---|---|
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Ukrainian |
| Veröffentlicht: |
Інститут проблем математичних машин і систем НАН України
2007
|
| Schlagworte: | |
| Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/785 |
| 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: | Математичне моделювання практичних задач у вигляді лінійних задач на переставленнях та їх розв’язання з застосуванням властивостей комбінаторних многогранників / Пічугіна О.С. // Математичні машини і системи. – 2007. – № 3, 4. – С. 185 – 195. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-785 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-7852008-07-02T12:00:23Z Математичне моделювання практичних задач у вигляді лінійних задач на переставленнях та їх розв’язання з застосуванням властивостей комбінаторних многогранників Пічугіна, О.С. Моделювання і управління великими системами В роботі дано огляд сучасних підходів до розв’язання умовних лінійних задач на комбінаторних множинах. Особливу увагуприділено дослідженню допустимих областей переставних многогранників з додатковими обмеженнями спеціальноговигляду. Показано, що в окремих випадках додаткове дослідження допустимої області дозволяє зменшити вимірність задачі,перейти від розгляду переставних многогранників з обмеженнями до поліпереставних без обмежень, знаходити розв’язкиумовних задач без використання методів лінійного або дискретного лінійного програмування. Побудовано математичнумодель однієї задачі розміщення виробництва у вигляді лінійної задачі на переставленнях з додатковими обмеженнями, дорозв’язання якої пропонується застосовувати викладені підходи. Бібліогр.: 10 назв. В работе дан обзор современных подходов к решению условных линейных задач на комбинаторных множествах. Особоевнимание уделено исследованию допустимых областей перестановочных многогранников с дополнительнымиограничениями специального вида. Показано, что в отдельных случаях дополнительное исследование допустимой областипозволяет уменьшить размерность задачи, перейти от рассмотрения перестановочных многогранников с ограничениями кполиперестановочным без ограничений, находить решения условных задач без использования методов линейного илидискретного линейного программирования. Построена математическая модель одной задачи размещения производства ввиде линейной задачи на перестановках с дополнительными ограничениями, к решению которой предлагается применятьизложенные подходы. Библиогр.: 10 назв. At the article a review of modern approaches to solution of linear optimization problems with constraints on combinatorial sets isgiven. The special attention is given for investigating permutation polyhedron’s admissible domains with special constraints. It isshown, that sometimes additional research of admissible domain allows reducing dimension of problems, passing from considerationof permutation polyhedrons with constraints to polypermutation polyhedrons without constraints, finding solutions of problems withrestrictions without using linear optimization methods or discrete linear optimization methods. The mathematical model of somemanufacture accommodation problem as a linear problem on permutations with additional restrictions is constructed. For solution ofthe problem using the se approaches is recommended. Refs.: 10 titles. 2007 Article Математичне моделювання практичних задач у вигляді лінійних задач на переставленнях та їх розв’язання з застосуванням властивостей комбінаторних многогранників / Пічугіна О.С. // Математичні машини і системи. – 2007. – № 3, 4. – С. 185 – 195. 1028-9763 http://dspace.nbuv.gov.ua/handle/123456789/785 519.85 uk Інститут проблем математичних машин і систем НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Ukrainian |
| topic |
Моделювання і управління великими системами Моделювання і управління великими системами |
| spellingShingle |
Моделювання і управління великими системами Моделювання і управління великими системами Пічугіна, О.С. Математичне моделювання практичних задач у вигляді лінійних задач на переставленнях та їх розв’язання з застосуванням властивостей комбінаторних многогранників |
| description |
В роботі дано огляд сучасних підходів до розв’язання умовних лінійних задач на комбінаторних множинах. Особливу увагуприділено дослідженню допустимих областей переставних многогранників з додатковими обмеженнями спеціальноговигляду. Показано, що в окремих випадках додаткове дослідження допустимої області дозволяє зменшити вимірність задачі,перейти від розгляду переставних многогранників з обмеженнями до поліпереставних без обмежень, знаходити розв’язкиумовних задач без використання методів лінійного або дискретного лінійного програмування. Побудовано математичнумодель однієї задачі розміщення виробництва у вигляді лінійної задачі на переставленнях з додатковими обмеженнями, дорозв’язання якої пропонується застосовувати викладені підходи. Бібліогр.: 10 назв. |
| format |
Article |
| author |
Пічугіна, О.С. |
| author_facet |
Пічугіна, О.С. |
| author_sort |
Пічугіна, О.С. |
| title |
Математичне моделювання практичних задач у вигляді лінійних задач на переставленнях та їх розв’язання з застосуванням властивостей комбінаторних многогранників |
| title_short |
Математичне моделювання практичних задач у вигляді лінійних задач на переставленнях та їх розв’язання з застосуванням властивостей комбінаторних многогранників |
| title_full |
Математичне моделювання практичних задач у вигляді лінійних задач на переставленнях та їх розв’язання з застосуванням властивостей комбінаторних многогранників |
| title_fullStr |
Математичне моделювання практичних задач у вигляді лінійних задач на переставленнях та їх розв’язання з застосуванням властивостей комбінаторних многогранників |
| title_full_unstemmed |
Математичне моделювання практичних задач у вигляді лінійних задач на переставленнях та їх розв’язання з застосуванням властивостей комбінаторних многогранників |
| title_sort |
математичне моделювання практичних задач у вигляді лінійних задач на переставленнях та їх розв’язання з застосуванням властивостей комбінаторних многогранників |
| publisher |
Інститут проблем математичних машин і систем НАН України |
| publishDate |
2007 |
| topic_facet |
Моделювання і управління великими системами |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/785 |
| citation_txt |
Математичне моделювання практичних задач у вигляді лінійних задач на переставленнях та їх розв’язання з застосуванням властивостей комбінаторних многогранників / Пічугіна О.С. // Математичні машини і системи. – 2007. – № 3, 4. – С. 185 – 195. |
| work_keys_str_mv |
AT píčugínaos matematičnemodelûvannâpraktičnihzadačuviglâdílíníjnihzadačnaperestavlennâhtaíhrozvâzannâzzastosuvannâmvlastivostejkombínatornihmnogogrannikív |
| first_indexed |
2025-07-02T04:25:38Z |
| last_indexed |
2025-07-02T04:25:38Z |
| _version_ |
1836507819372707840 |
| fulltext |
ISSN 1028-9763. Математичні машини і системи, 2007, № 3, 4
185
УДК 519.85
О.С. ПІЧУГІНА
МАТЕМАТИЧНЕ МОДЕЛЮВАННЯ ПРАКТИЧНИХ ЗАДАЧ У ВИГЛЯДІ ЛІНІЙНИХ
ЗАДАЧ НА ПЕРЕСТАВЛЕННЯХ ТА ЇХ РОЗВ’ЯЗАННЯ ІЗ ЗАСТОСУВАННЯМ
ВЛАСТИВОСТЕЙ КОМБІНАТОРНИХ МНОГОГРАННИКІВ
Abstract: At the article a review of modern approaches to solution of linear optimization problems with constraints on
combinatorial sets is given. The special attention is given for investigating permutation polyhedron’s admissible
domains with special constraints. It is shown, that sometimes additional research of admissible domain allows
reducing dimension of problems, passing from consideration of permutation polyhedrons with constraints to
polypermutation polyhedrons without constraints, finding solutions of problems with restrictions without using linear
optimization methods or discrete linear optimization methods. The mathematical model of some manufacture
accommodation problem as a linear problem on permutations with additional restrictions is constructed. For solution of
the problem using the se approaches is recommended.
Key words: combinatorial polyhedron, permutation set, polypermutation set, optimization, a linear problem, a problem
with constraints, cutting.
Анотація: В роботі дано огляд сучасних підходів до розв’язання умовних лінійних задач на комбінаторних
множинах. Особливу увагу приділено дослідженню допустимих областей переставних многогранників з
додатковими обмеженнями спеціального вигляду. Показано, що в окремих випадках додаткове дослідження
допустимої області дозволяє зменшити вимірність задачі, перейти від розгляду переставних
многогранників з обмеженнями до поліпереставних без обмежень, знаходити розв’язки умовних задач без
використання методів лінійного або дискретного лінійного програмування. Побудовано математичну
модель однієї задачі розміщення виробництва у вигляді лінійної задачі на переставленнях з додатковими
обмеженнями, до розв’язання якої пропонується застосовувати викладені підходи.
Ключові слова: комбінаторний многогранник, множина переставлень, множина поліпереставлень,
оптимізація, лінійна задача, умовна задача, відсікання.
Аннотация: В работе дан обзор современных подходов к решению условных линейных задач на
комбинаторных множествах. Особое внимание уделено исследованию допустимых областей
перестановочных многогранников с дополнительными ограничениями специального вида. Показано, что в
отдельных случаях дополнительное исследование допустимой области позволяет уменьшить
размерность задачи, перейти от рассмотрения перестановочных многогранников с ограничениями к
полиперестановочным без ограничений, находить решения условных задач без использования методов
линейного или дискретного линейного программирования. Построена математическая модель одной
задачи размещения производства в виде линейной задачи на перестановках с дополнительными
ограничениями, к решению которой предлагается применять изложенные подходы.
Ключевые слова: комбинаторный многогранник, множество перестановок, множество полиперестановок,
оптимизация, линейная задача, условная задача, отсечения.
1. Вступ
Кожен з нас щоденно зустрічається з задачами вибору найкращого з якоїсь точки зору варіанта із
скінченного набору елементів. Частину цих задач удається формалізувати і в результаті
одержуються задачі дискретної, зокрема, комбінаторної, оптимізації. При реалізації
обчислювальних алгоритмів розв’язання таких задач великої вимірності вимагається настільки
багато ресурсів, що досить початкова оптимізаційна заміняється задачею не стільки одержання
оптимального розв’язку задачі, а просто одержання хоч якогось допустимого розв’язку.
У зв’язку з цим актуальним було і залишається вилучення класів задач, властивості
допустимих областей яких дозволяють розв’язувати задачі спеціальними методами, що враховують
специфіку задач.
Якщо говорити про комбінаторні задачі, то одним із відомих підходів дослідження їх
властивостей є занурення в арифметичний евклідів простір і розгляд замість комбінаторних об’єктів
множини точок евклідового простору – евклідової комбінаторної множини, а також її опуклої
оболонки – комбінаторного многогранника. Дослідження цих об’єктів в залежності від типу вихідної
комбінаторної множини – (множини переставлень, розміщень, сполучень, полі-множини) –
ISSN 1028-9763. Математичні машини і системи, 2007, № 3, 4
186
дозволило встановити ряд властивостей таких, як аналітичний опис, критерій вершин та суміжності
вершин комбінаторних многогранників, вершинну розташованість деяких евклідових комбінаторних
множин тощо [1–10]. Ці властивості, в свою чергу, лягли в основу методів розв’язання специфічних
задач оптимізації [1–10]. Проте невирішених проблем, зокрема в області розв’язання умовних
лінійних комбінаторних задач, чимало. Одним з найперспективніших напрямків їх вирішення є
встановлення нових властивостей комбінаторних множин і многогранників.
У даній роботі буде сформульовано одну практичну задачу, яка являє собою умовну лінійну
задачу на переставленнях, частина додаткових обмежень яких має специфічний вигляд. Перед
застосуванням безпосередньо методів умовної оптимізації пропонується дослідити допустиму
область задачі на предмет її звуження за допомогою запропонованих ітераційних процедур
уточнення. Це дозволяє в окремих випадках перейти до розгляду задач меншої вимірності; до
розгляду комбінаторних множин переставлень та поліпереставлень, що є підмножинами вихідної;
до безумовних задач оптимізації, що фактично означає розв’язання вихідної задачі, оскільки
розв’язки безумовних лінійних задач оптимізації на переставленнях і поліпереставленнях відомі.
2. Одна задача розміщення виробництва та підходи до її розв’язання
Розглянемо задачу розміщенння виробництва у наступній постановці: є n населених пунктів
1iA , i ,n= , в яких планується розмістити підприємства потужності 1jg , j ,n= (ум.од.). Треба так
спланувати будівництво, щоб максимізувати сумарну ефективність роботи всіх підприємств, якщо в
кожному пункті задана величина 1ic , i ,n= – коефіцієнт ефективності роботи нового підприємства в
пункті 1iA , i ,n= (гр.од./ ум.од. потужності) і є обмеження по кількості працівників, яких можливо
залучити в новому виробництві по обсягу капіталовкладень на освоєння нового виробництва та інші
обмеження по ресурсах (наприклад, на транспортування).
Побудуємо математичну модель задачі.
Введемо змінні 1ix , i ,n= – потужності підприємств у пунктах iA , тоді вектор 1 nx ( x , , x )= K –
шуканий план розміщення виробництва.
Розглянемо також мультимножину потужностей потенційних підприємств 1 nG { g , ,g }= K . Не
обмежуючи загальності, можна вважати, що 1 1 1i ig g , i ,n+≤ = − . Нехай 1 l{G } { e , e }= K – основа
G , [ ] [ ]1
1
l
l i
i
G n , n , n n
=
= =∑K – первинна специфікація G .
Тоді очевидно, що x являє собою переставлення з мультимножини G , тобто має вигляд
{ }
1 1n nj j j jx ( g , , g ), g , , g G= =K K . Позначимо nlP (G ) загальну множину переставлень з G , тоді
математична модель задачі така:
знайти
nlx P (G )∈ , (1)
що максимізує
1
n
j j
j
c x
=
∑ і задовольняє обмеження
ISSN 1028-9763. Математичні машини і системи, 2007, № 3, 4
187
по трудових ресурсах:
1i i i iL l x L' , i ,n≤ ≤ = , (2)
де il , 1i ,n= – коефіцієнт трудомісткості в пункті 1iA ,i ,n= (кількість чоловік, що забезпечують
роботу підприємств міста потужності 1), i iL ,L' , 1i ,n= – нижня і верхня межі кількості працівників,
що можуть бути використані у пункті 1iA , i ,n= ;
по капіталовкладеннях:
1
1 1 1
1
k
k
N N
k i k
i N N
m x M , k ,K
−
+
= + +
≤ =∑
K
K
(3)
(нехай всі розглянуті населені пункти розподіляються також по декількох регіонах, по кожному з
яких наперед задані обсяги капіталовкладень на освоєння нового виробництва. Нехай K – кількість
регіонів, перші 1N пункти відносяться до 1-го регіону (
11 NA , , AK ), наступні 2N пункти – до 2-го
регіону (
1 1 21N N NA , , A+ +K ), …, останні KN пункти відносяться до K -го регіону ( 1KN N NA , , A− + K ).
Задано 1kM , k ,K= (гр.од.) – обсяги капіталовкладень в освоєння нового виробництва у регіонах,
1km , k ,K= – норма капіталовкладень на освоєння нового виробництва потужності 1 в k -му
регіоні;
по потужностях нововведених підприємств:
1
1 1 1
1
k
k
N N
k i k
i N N
C x C' , k ,K
−
+
= + +
≤ ≤ =∑
K
K
(4)
(тут k kC ,C' , 1k ,K= – нижня і верхня межі обсягу нововведених потужностей у k -му регіоні);
по інших ресурсах, витрати яких залежать також від номера підприємства:
1
1
n
ij j i
j
a x b , i ,m
=
≤ =∑ (5)
( m– кількість ресурсів, наявних в обмеженій кількості, 1 1ija , i ,m, j ,n= = – норма витрат i -го
ресурсу на забезпечення роботи підприємства jA потужністю 1, 1ib , i ,m= – обсяг i -го ресурсу).
Задача: знайти вектор x , що задовольняє умови (1) – (5), такий, що
1
n
j j
j
z c x max
=
= →∑ . (6)
(1) – (6) – умовна лінійна задача на загальній множині переставлень, яку можна представити в
матричній формі так:
nlcx max, x P (G ), Ax b→ ∈ ≤ ( A – матриця вимірності M n× ). (7)
До її розв’язання можна застосувати, наприклад, наступний прийом [1, 3, 4]:
1) Провести занурення множини nlP (G ) в арифметичний евклідів простір
nR : nl nlP (G ) E (G )→ .
2) Розглянути релаксацію задачі
ISSN 1028-9763. Математичні машини і системи, 2007, № 3, 4
188
nlcx max, x П (G ), Ax b→ ∈ ≤ , (8)
де nl nlП (G ) conv( E (G ))= – загальний многогранник переставлень з мультимножини G .
3) Від розв’язку 0x задачі (8) провести комбінаторне заокруглення до елемента 1x з
nlP ( G ) .
Але жоден спосіб комбінаторного заокруглення не гарантує, що 1x задовольняє обмеження
Ax b≤ [1, 3, 4]. Отже, є якимось розв’язком задачі (7). Тому для одержання допустимого розв’язку
пропонується замість (8) розглянути задачу
nlcx max, x П (G ), Ax b', b'=b- , >0σ σ→ ∈ ≤ . (9)
Позначимо 2x – розв’язок (9), а результат комбінаторного заокруглення від точки 2x до
елемента nlP (G ) – 3x . Вектор >0σ обирається так, щоб 3x задовольняло Ax b≤ , тобто було
розв’язком задачі (7), а отже, і (1) – (6).
Вектор 3x , очевидно, наближений розв’язок (7). Якщо нас не задовольняє точність розв’язку
3x , можна застосувати метод меж та гілок для розв’язання (7) з додатковим обмеженням
3
0cx b cx≥ = . (10)
Точний розв’язок можна також одержати методом комбінаторного відсікання на
переставленнях [6–8], в якому суттєво використовується вершинна розташованість множини
переставлень і, як наслідок, те, що всередині многогранника переставлень та його граней довільної
вимірності точок переставлень немає. В ході реалізації методу розв’язується послідовність
релаксованих задач умовної лінійної оптимізації на переставному многограннику.
Зауважимо, що розв’язання лінійних задач на комбінаторних многогранниках, не говорячи
вже про задачі на комбінаторних множинах, викликає значні труднощі в силу наявності великої
кількості обмежень у системах, які задають ці комбінаторні многогранники. Крім цього, на
сьогоднішній день відомі аналітичні описи далеко не всіх комбінаторних многогранників.
Якщо ж аналітичний опис комбінаторного многогранника відомий, можна використати
комбінаторні властивості і надалі працювати лише з частиною обмежень многогранника і
додатковими обмеженнями Ax b≤ . Незважаючи на це, розв’язання реальних задач вимагає
значних ресурсів, тому актуальним залишається дослідження нових властивостей комбінаторних
множин з метою зменшення кількості нерівностей, що розглядаються, переходу у простір меншої
вимірності, проведення декомпозиції на задачі меншої вимірності тощо.
Проведемо аналіз системи обмежень нашої задачі (1) – (6). Неважко помітити, що
обмеження (2) – (4) мають спеціальну структуру, а саме (2) переписуються і уточнюються таким
чином:
1i i
i i i
i iG G
L L'
a x b , i ,n
l l
= ≤ ≤ = =
, (11)
де jG
a g= – найближчий елемент G , не менший за a , j 'G
b g= – найближчий елемент G , не
більший за b (в (11) суттєво використовується той факт, що всі елементи множини переставлень
nlE (G ) лежать на сімействі гіперплощин вигляду i jx g , i,j=1,n= [1]).
ISSN 1028-9763. Математичні машини і системи, 2007, № 3, 4
189
Не обмежуючи загальності, можна вважати, що 1 1 1 1i i j ja a , i ,n , a b , j ,n+< = − < = , інакше
можна перенумерувати змінні або зафіксувати їх частину і перейти до розгляду задачі меншої
вимірності.
Перепишемо (3), (4) у формі
1
1 1 1
1
k
k
k
NN N
k
i
i N N k G
M
x , k ,K
m
−
+
= + +
≤ =
∑
K
K
, (12)
1
1 1 1
1
k
k k
k
N N
N N
k i kG G
i N N
C x C' , k ,K
−
+
= + +
≤ ≤ = ∑
K
K
, (13)
де
1
iG
m
m
j
i
a g
=
= ∑ – найближча сума m елементів G , не менша за a ,
1
iG
m
m
j '
i
b g
=
= ∑ – найближча
сума m елементів G , не більша за b .
Називатимемо додаткові обмеження обмеженнями спеціального вигляду, якщо їх
коефіцієнти набувають лише значень 0,1, тобто це обмеження типу ax b≤ , де 0 1ja { , }, j=1,n= . Ці
обмеження цікаві тим, що відповідні гіперплощини ax b= паралельні гіперграням загального
многогранника переставлень [1, 2, 5, 6], таким чином, введення обмежень спеціального вигляду
дозволяє викинути з розгляду частину надлишкових обмежень многогранника переставлень, які для
даної задачі будуть надлишковими. Крім цього, можна запропонувати ітераційну процедуру
уточнень нижньої і верхньої меж змінних та сум змінних, що може призвести як до зменшення
вимірності задачі, так і до переходу від розгляду многогранника переставлень з обмеженнями
спеціального вигляду до розгляду поліпереставного многогранника [1, 7–10]. В окремих випадках це
дозволяє не тільки спростити задачу, але і одразу записати розв’язок вихідної задачі без
використання методів лінійного програмування. Цінність цих випадків полягає і в тому, що таким
чином одержується не розв’язок релаксованої задачі (8), а точний розв’язок вихідної задачі (7).
Серед обмежень (11) – (13) можуть бути надлишкові. Щоб показати це, введемо позначення
1nJ { , ,n }= K ,
1
1 1
1
k k
k k ' k ' 0
k ' k '
I { N , , N }, k=1,K , N =0.
−
= =
= +∑ ∑K
Тепер (12) – (13) можна переписати:
1
k
k
N
k
i
i I k G
M
x , k ,K
m∈
≤ =
∑ ; (14)
1k k
k
N N
k i kG G
i I
C x C' , k ,K
∈
≤ ≤ = ∑ . (15)
Звідси видно, що з (14), (15) випливає:
1
k
k
k
N
Nk
i k kG
i I k G
M
x min , C ' D" , k ,K
m∈
≤ = =
∑ . (16)
Отже, (14), (15) переписується:
ISSN 1028-9763. Математичні машини і системи, 2007, № 3, 4
190
1k
k
N
k k i kG
i I
D' C x D" , k ,K
∈
= ≤ ≤ = ∑ . (17)
Введемо позначення для підмультимножин G , сума елементів яких визначає
1k kD' ,D" , k ,K= :
1
1
N j
NN
i i i
j G
G'( a,N ) { g , , g } G : g a
=
= ⊆ = ∑L , (18)
1
1
N j
NN
i i i
j G
G"( a,N ) { g , , g } G : g a
=
= ⊆ = ∑L . (19)
(17) можна переписати таким чином:
1
k k k k k
i i i
i G '( D ,N ) i I i G"( D ,N )
g x g , k ,K
∈ ∈ ∈
≤ ≤ =∑ ∑ ∑ . (20)
Спробуємо зменшувати допустиму область, комбінуючи обмеження (20), що відповідають
різним k , і використовуючи властивості множини та многогранника переставлень.
Утворимо дві допоміжні мультимножини з елементів k k k k
G '( D , N ), G '( D , N ), k=1,K :
1 1
K K
, k k k k
k k
G' G'( D ,N ) G" G"( D ,N )
= =
= =U U .
Якщо виконано
G' G,G" G⊆ ⊆ , (21)
то ми не можемо посилити додаткові обмеження комбінацією (19), (20). Якщо ж (21) не виконано,
доцільно будувати комбінації обмежень такого вигляду: нехай 1 2 Kk ,k J∈ такі, що
221 1 k kk k
G '( D , N ) G '( D ,N ) G⊄U , (22)
тоді
1 2
1 2
1 21 2
21 1 2 1 1 1 2
22
k k
k k
k k k k k k k k
k k
N N
N N
k ,ki i i k k iG
i G '( D ,N ) i G '( D ,N ) i G '( D ,N ) i I ,I
i G '( D ,N )
G
g g g D D D x
+
+
∈ ∈ ∈ ∈
∈
+ < = + = ≤
∑ ∑ ∑ ∑ . (23)
Як видно, обмеження (23) не є наслідком (20) (називатимемо їх далі посиленими).
Аналогічно (23) можна побудувати нові обмеження зверху і знизу, отже отримуємо цілий набір
нових обмежень, що посилює початкові обмеження (8):
1 2 1 2 3
1 2 1 2 3
1
K
k k k k k K
n
k ,k k ,k ,k Ji i i i
i I ,I i I ,I ,I i J i
D x , D x , , D x x
∈ ∈ ∈ =
≤ ≤ ≤ =∑ ∑ ∑ ∑K , (24)
1 2 1 2 3
1 2 1 2 3
1
K
k k k k k K
n
k ,k k ,k ,k Ji i i i
i I ,I i I ,I ,I i J i
x D , x D , , x x D
∈ ∈ ∈ =
≤ ≤ = ≤∑ ∑ ∑ ∑K . (25)
ISSN 1028-9763. Математичні машини і системи, 2007, № 3, 4
191
Зауважимо, що умова (22) може не виконуватися 1 2 Kk ,k J∀ ∈ , але може виконатися для
трьох чи більшої кількості обмежень (20). Якщо така комбінація i Kk J , 2 i K∈ ≤ ≤ (позначатимемо
множину таких номерів обмежень для (24), (25) – K ', K" відповідно) визначена і побудоване
посилене обмеження типу (24), (25)
k
k K ' i
i I ,k K '
D x∈
∈ ∈
≤ ∑ ,
k
k K "i
i I ,k K "
x D ∈
∈ ∈
≤∑ , (26)
то додавання до K ', K" довільного іншого kk J∈ також формує посилене обмеження. В результаті
може бути сформовано велику кількість посилених обмежень, кожне з яких визначає гіпергрань
допустимої області, паралельну гіперграні переставного многогранника [1, 2, 5]. Отже, всі відповідні
обмеження переставного многогранника стають надлишковими.
Нагадаємо, що переставний многогранник розташовано у гіперплощині [1, 2, 5]
n n
i i
i J i J
x g SG
∈ ∈
= =∑ ∑ . (27)
Неважко побачити, що для сумісності вихідної задачі необхідно, щоб виконувалося
1 1
K K
n n
J Ji i
i i
x D D g SG
= =
= = = =∑ ∑ . (28)
Отже, останні обмеження (24), (25) будуть надлишковими.
З (27), зокрема, випливає
1
k k
i i
i I i I
x SG x , k ,K
∈ ∉
= − =∑ ∑ . (29)
Після підстановки (29) у (17) одержуємо
1
k k
k i i
i I i I
D' x SG x , k ,K
∈ ∉
≤ = − =∑ ∑ , (30)
1
k k
i i k
i I i I
x SG x D" , k ,K
∈ ∉
= − ≤ =∑ ∑ , (31)
звідки
1
k
i k
i I
x SG D' , k ,K
∉
≤ − =∑ , (32)
1
k
i k
i I
x SG D" , k ,K
∉
≥ − =∑ . (33)
Обмеження (30) і (32), а також (31) і (32) називатимемо доповнюючими. Після формування
кожного посиленого обмеження типу (26) можна побудувати доповнююче обмеження і спробувати
посилити їх вищенаведеним способом.
Головна мета додаткового дослідження допустимої області многогранника переставлень:
нехай на певному кроці ітераційної процедури посилення обмежень виявилося, що у (26)
k K " k K 'D D , K'=K"∈ ∈= ,
ISSN 1028-9763. Математичні машини і системи, 2007, № 3, 4
192
отже,
ik
i i
i I ,k K " g G
G G : x g
∈ ∈ ∈
∃ ⊂ =∑ ∑
%
%
, (34)
тоді з (27) випливає, що
ik
i i
i I ,k K " g G
x g
∈ ∉ ∉
=∑ ∑
%
. (35)
Таким чином, від розгляду множини переставлень ми переходимо до розгляду множини
поліпереставлень по
~~
21 , GnGn == елементів з мультимножин
~~~
\, GGGG = відповідно
( 1 2n=n n+ ). Це означає, що від початкового многогранника переставлень ми переходимо до
розгляду лише його частини. Треба відзначити, що при переході до цієї задачі в аналізі системи
обмежень ми суттєво використовуємо вихідні обмеження (12), (13), тому не виключено, що після
переходу до поліпереставлень усі або частина обмежень (12), (13) стануть надлишковими. В
реальних прикладах досить часто вдається встановити, що можливий перехід до розгляду
поліпереставлень з 1 21 1n ,n n= = − елементів. Це означає, що одну координату розв’язку можна
зафіксувати і перейти до розгляду многогранника переставлень з 1n − -го елемента.
Процедуру уточнень доцільно проводити доти, доки це можливо.
Як видно, система уточнених обмежень, з одного боку, зменшує допустиму область, що
розглядається, і дозволяє переходити до розгляду поліпереставлень чи переставлень у просторах
меншої вимірності, що може бути дуже суттєвим при розв’язанні реальних задач великої вимірності.
Але, з іншого боку, вона може перетворитися на систему з такою величезною кількістю обмежень,
що буде подібна системі обмежень переставного многогранника, яку, як правило, не формують і не
зберігають одразу, а використовують лише частину обмежень многогранника, шукають перше
наближення до розв’язку, а потім поступово під’єднують обмеження, що не справдилися у
початковій точці (метод послідовного під’єднання обмежень див. у [1, 3, 4]). Спроба використати
переваги вказаного підходу і уникнути недоліків відображена у наступній ітераційній процедурі.
Неважко побачити, що обмеження на змінні (11) є окремим випадком (20), коли
K n,= 1kN , k=1,K= , тобто все вищевикладене відноситься до всіх обмежень спеціального
вигляду вихідної системи. Порядок проведення процедури уточнень, що пропонується,
продемонструємо на прикладі системи (11). Для (12), (13) вона проводиться аналогічно:
1. Впорядковуємо обмеження (11) у порядку неспадання нижньої межі, тобто так:
11i ij i i jg a a g , i=1,n-1
++≤ ≤ = .
2. У відповідності з (22) ознакою можливості побудови посилених обмежень знизу є те, що
1 1 11 i in j j j ji J : { g , ,g } G, { g , ,g } G
−−∃ ∈ ⊂ ⊄K K . (36)
Якщо 1ni J −∈ , яке задовольняє (36), знайдено, будуємо посилене обмеження
ISSN 1028-9763. Математичні машини і системи, 2007, № 3, 4
193
1 1 1
i' i'
ii i i
i ' j j
i ' i ' i 'G
x g g
= = =
≥ >
∑ ∑ ∑ . (37)
3. Одразу ж будуємо доповнююче обмеження
1 1
i'
n in i
i ' j
i ' i i ' G
x SG g
−
= + =
≤ −
∑ ∑ (38)
і перевіряємо його на суттєвість, виконуючи для цього кроки 4, 5.
4. Впорядковуємо обмеження (11) у порядку незростання верхньої межі, тобто так:
1 1i i i ij ' l l j 'g b b g , i=1,n-1
+ +
≥ ≥ = .
5. Тут ознакою можливості побудови посилених обмежень зверху є те, що
а) виконано
1 1 11 i in j ' j ' j ' j 'i J : { g , ,g } G, { g , , g } G
−−∃ ∈ ⊂ ⊄K K (39)
(по 1ni J −∈ , яке задовольняє (36), будуємо посилене обмеження
1 1
i' i'
ii i
l j
i ' i ' G
x g '
= =
≤
∑ ∑ ); (40)
b) виконано
1 1
i'
n ii n
j i '
i ' i ' iG
SG g b
−
= = +
− <
∑ ∑ . (41)
Можна ще сформувати і перевірити виконання обмежень типу
1 2
1
1 1 1
i' i'
n i n ii n i n
j i i ' j i i i
i ' i ' i i ' i ' iG G
SG g b b , SG g b b b
− + − +
−
= = = = −
− + < − + + <
∑ ∑ ∑ ∑ тощо. (42)
6. Як тільки знайдено перше обмеження, для якого одна з умов (40) – (42) виконана,
формуємо для цього обмеження доповнююче і переходимо на крок 2, враховуючи тепер, що
ознакою побудови посиленого обмеження є не тільки (36), а й умова суттєвості доповнюючого до
нього обмеження (сформованого для обмежень знизу подібно до (41), (42)).
Процедуру уточнень зверху і знизу проводимо, доки це можливо, слідкуючи при цьому, чи не
виконана для певної групи змінних умова (34). Якщо так, переходимо до розгляду множини
поліпереставлень. Тепер для кожної групи змінних, що утворюють переставлення, повторюємо
вищенаведену процедуру.
Працездатність наведеної процедури було перевірено на тестових прикладах лінійних задач
на переставленнях з додатковими обмеженнями на змінні та обмеженнями загального вигляду, при
цьому обмеження на окремі змінні генерувалися випадковим чином. У більшості випадків після
послідовності уточнень або доводилася несумісність вихідної системи, або те, що після уточнень
додаткові обмеження на змінні стають несуттєвими, тобто можна надалі розглядати лінійну задачу з
загальними обмеженнями. Якщо при цьому розв’язок безумовної задачі на комбінаторній множині,
що розглядалася після процедури уточнень обмежень, задовольняв цю систему обмежень, то ця
ISSN 1028-9763. Математичні машини і системи, 2007, № 3, 4
194
точка і визначалася як розв’язок вихідної задачі. Лише в решті небагаточисельної кількості
прикладів пропонувалося застосовувати методи розв’язання умовних лінійних задач.
По закінченні процедури уточнень можна також перевірити, чи є серед додаткових
обмежень (7) надлишкові, для чого слід розв’язати допоміжні задачі. Наведемо тут лише одне
правило, за яким можна перевіряти можливість викидання конкретного додаткового обмеження
системи (7) з розгляду. Визначимо ті обмеження, закритий напівпростір яких не перетинає
многогранник переставлень (поліпереставлень) або перетинає його лише в одній точці.
Введемо позначення:
•
1
11
ij ,n
ij i ,Mi ,m
A ( a ) ( a )=
==
= = ;
• 1i n
minx R , i ,M∈ = – множина оптимальних розв’язків задачі мінімізації вигляду
i
x П
a x min∈⋅ → ; (43)
• i i i
min minz a x= ⋅ , 1i ,M= ;
• 1i n
maxx R , i ,M∈ = – множина оптимальних розв’язків задачі максимізації вигляду
i
x П
a x max∈⋅ → . (44)
•
i i i
max maxz a x= ⋅ , 1i ,M= .
Твердження. Якщо для деякого Mi J∈ :
– i
i maxb z≥ , то i -е обмеження системи (7) є надлишковим і може бути вилучене з системи;
– i
i minb z< , то система обмежень (7) є несумісною і задача оптимізації розв’язків не має;
–
i
i minb z= , то єдиним розв’язком задач (7) може бути лише точка i
minx (в разі, якщо вона
задовольняє систему (7)).
Зауважимо, у твердженні ми не використовуємо наявність додаткових обмежень, в тому
числі обмежень спеціального вигляду, тому одержані оцінки розмаху значень цільових функцій
можуть бути досить грубими, хоча і легко одержуються, оскільки розв’язки лінійних задач на
переставленнях і поліпереставленнях відомі [1, 2].
3. Висновки
У даній роботі представлено новий підхід до розв’язання лінійних задач на переставленнях із
обмеженнями, частина яких має специфічний вигляд. Він полягає у попередньому застосуванні
ітераційних процедур уточнення меж допустимої області і ґрунтується на таких властивостях
множини переставлень, як її розташованість на сім’ях гіперплощин, паралельних гіперграням
переставного многогранника, вершинна розташованість множини переставлень тощо. Подібний
попередній аналіз допустимої області дозволяє в окремих випадках суттєво спростити задачу.
Таким чином, з одного боку, застосування до нової задачу методів умовної лінійної оптимізації
дозволяє одержати розв’язок значно швидше, а з іншого боку, сама принципова можливість
уточнення вихідної системи обмежень, переходу у простір меншої вимірності або до розгляду
поліпереставної множини – це нова встановлена властивість евклідової комбінаторної множини
ISSN 1028-9763. Математичні машини і системи, 2007, № 3, 4
195
переставлень. У роботі йшлося про перспективний напрямок дослідження допустимої області по
вилученню надлишкових додаткових обмежень загального вигляду. Нові теоретичні результати в
даному напрямку будуть одержані, якщо буде точно розв’язано лінійну задачу на переставленнях із
обмеженнями спеціального вигляду, зокрема, обмеженнями на змінні.
Практична доцільність результатів роботи полягає у можливості одержати точний розв’язок
широкого класу практичних задач, які зводяться до лінійних умовних задач на переставленнях.
СПИСОК ЛІТЕРАТУРИ
1. Стоян Ю.Г., Ємець О.О. Теорія і методи евклідової комбінаторної оптимізації. – Киів: ІСДО, 1993. – 188 с.
2. Емец О.А. Евклидовы комбинаторные множества и оптимизация на них. Новое в математическом
программировании. – Киев: УМК ВО, 1992. – 92 с.
3. Пичугина О.С. Методы и алгоритмы решения некоторых задач оптимизации на множествах сочетаний и
размещений: Дис. ... кандидата физ.-мат. наук: 01.05.02. – Х., 1996. – 169 с.
4. Пічугіна О.С. Методи і алгоритми розв’язання деяких задач оптимізації на множинах сполучень та
розміщень: Автореф. дис. ... кандидата фіз.-мат. наук: / Ін-т проблем машинобудування НАН України. – Х.,
1996. – 24 с.
5. Ємець О.О., Недобачій С.І. Загальний переставний многогранник: незвідна система лінійних обмежень на
рівняння всіх гіперграней // Наукові вісті НТУУ „КПІ”. – 1998. – №1. – С.100 –106.
6. Емец О.А. Об одном методе отсечения для задач комбинаторной оптимизации // Экономика и
математические методы. – 1997. – Т. 33, Вып. 4. – С.120 – 129.
7. Ємець О.О, Ємець Є.М. Відсікання в лінійних частково комбінаторних задачах евклідової комбінаторної
оптимізації // Доп. НАН. – 2000. – № 9. – С.105 – 109.
8. Стоян Ю.Г. Оптимізація на полірозміщеннях: теорія та методи / Ю.Г. Стоян, О.О. Ємець, Є.М. Ємець. –
Полтава: РВЦ ПУСКУ, 2005. – 103 с.
9. Ємець О.О., Колєчкіна Л.М. Задачі оптимізації з дробово-лінійними цільовими функціями. – Київ: Наукова
думка, 2005. – 117 с.
10. Ємець О.О., Роскладка О.В. Задачі оптимізації на комбінаторних множинах: властивості та розв’язування. –
Полтава: РВЦ ПУСКУ, 2006. – 129 с.
Стаття надійшла до редакції 29.08.2007
|