Алгебраический подход к задаче решения систем линейных неравенств
Викладено алгебраїчний підхід до побудови алгоритму розв’язання системи лінійних нерівностей. Суть цього підходу полягає у тому, що в термінах багатосортних алгебраїчних систем конструктивно визначається спеціальна алгебра Aconstr, у якій система лінійних нерівностей представлена як вираз. Розв’язан...
Збережено в:
| Опубліковано в: : | Кибернетика и системный анализ |
|---|---|
| Дата: | 2010 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2010
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/45154 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Алгебраический подход к задаче решения систем линейных неравенств / М.С. Львов // Кибернетика и системный анализ. — 2010. — № 2. — С. 175-188. — Бібліогр.: 19 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859712291546595328 |
|---|---|
| author | Львов, М.С. |
| author_facet | Львов, М.С. |
| citation_txt | Алгебраический подход к задаче решения систем линейных неравенств / М.С. Львов // Кибернетика и системный анализ. — 2010. — № 2. — С. 175-188. — Бібліогр.: 19 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | Викладено алгебраїчний підхід до побудови алгоритму розв’язання системи лінійних нерівностей. Суть цього підходу полягає у тому, що в термінах багатосортних алгебраїчних систем конструктивно визначається спеціальна алгебра Aconstr, у якій система лінійних нерівностей представлена як вираз. Розв’язання цієї системи полягає в обчисленні значення даного виразу як елемента алгебри Aconstr — канонічної форми системи лінійних нерівностей. Результат застосування цього підходу до задачі, яка розглядається, — алгебраїчні специфікації алгебри Aconstr.
The paper outlines an algebraic approach to designing a solution algorithm for a system of linear inequalities. The approach implies that a special algebra Aconstr , where the system of linear inequalities (SLI) is presented as an expression is constructively defined in terms of multisorted algebraic systems. The SLI is solved by computing the value of this expression as an element of Aconstr algebra (canonical form expressions). The result of applying this approach is algebraic specifications of Aconstr .
|
| first_indexed | 2025-12-01T05:55:25Z |
| format | Article |
| fulltext |
Ì.Ñ. ËÜÂÎÂ
ÓÄÊ 004.421.6 ÀËÃÅÁÐÀÈ×ÅÑÊÈÉ ÏÎÄÕÎÄ Ê ÇÀÄÀ×Å
ÐÅØÅÍÈß ÑÈÑÒÅÌ ËÈÍÅÉÍÛÕ ÍÅÐÀÂÅÍÑÒÂ
Êëþ÷åâûå ñëîâà: ìíîãîñîðòíûå àëãåáðû, ñèñòåìû ëèíåéíûõ íåðàâåíñòâ, àë-
ãåáðàè÷åñêîå ïðîãðàììèðîâàíèå, àëãåáðàè÷åñêèå ñïåöèôèêàöèè .
 íàñòîÿùåé ðàáîòå èçëîæåí àëãåáðàè÷åñêèé ïîõîä ê ïîñòðîåíèþ àëãîðèòìà ðåøå-
íèÿ ñèñòåìû ëèíåéíûõ íåðàâåíñòâ (ÑËÍ). Îòìåòèì, ÷òî ìíîãîñîðòíûå (òî÷íåå, óïî-
ðÿäî÷åíîñîðòíûå) àëãåáðàè÷åñêèå ñèñòåìû øèðîêî èñïîëüçóþòñÿ â êà÷åñòâå òåîðåòè-
÷åñêîé ìîäåëè àëãåáðàè÷åñêèõ âû÷èñëåíèé [1, 2]. Ýòà ìîäåëü ðåàëèçîâàíà, íàïðèìåð,
â ÿçûêàõ ëîãèêî-àëãåáðàè÷åñêèõ ñïåöèôèêàöèé ñåðèè Obj [3, 4], Eqlog [5].
Êëàññè÷åñêèå àáñòðàêòíûå àëãåáðàè÷åñêèå òèïû äàííûõ âìåñòå ñ èõ ïðåäñòàâ-
ëåíèÿìè â ñòàíäàðòíûõ ñòðóêòóðàõ äàííûõ (ò.å. êîíñòðóêòèâíûìè ïðåäñòàâëåíèÿ-
ìè) èñïîëüçóþòñÿ, íàïðèìåð, â ÿçûêå ïðîãðàììèðîâàíèÿ ñèñòåìû êîìïüþòåðíîé
àëãåáðû Axiom [6, 7].
Ìåòîäîëîãèÿ àëãåáðàè÷åñêîãî ïðîãðàììèðîâàíèÿ, èñïîëüçîâàííàÿ â íàñòîÿ-
ùåé ðàáîòå, çàêëþ÷àåòñÿ â êîíñòðóêòèâíîì îïðåäåëåíèè ìíîãîñîðòíîé àëãåáðàè-
÷åñêîé ñèñòåìû, îáúåêòû êîòîðîé ïðåäñòàâëåíû â âèäå âûðàæåíèé, à àëãîðèòìû,
ïî ñóùåñòâó, âû÷èñëÿþò çíà÷åíèÿ ýòèõ âûðàæåíèé, ò.å. ñòðîÿò èõ êàíîíè÷åñêèå
ôîðìû. Ðåçóëüòàò ïðèìåíåíèÿ ýòîãî ïîäõîäà — àëãåáðàè÷åñêèå ñïåöèôèêàöèè ñî-
îòâåòñòâóþùèõ ïðåäìåòíûõ îáëàñòåé è àëãîðèòìîâ. Ñïåöèôèêàöèè èñïîëüçóþò
ïîíÿòèÿ íàñëåäîâàíèÿ, ðàñøèðåíèÿ è ìîðôèçìîâ ìíîãîñîðòíûõ àëãåáð. Ïîäðîáíî
ýòîò ïîäõîä èçëîæåí â [8–11].
Îòìåòèì, ÷òî ýòà ìåòîäîëîãèÿ ïðèìåíèìà ê øèðîêîìó êëàññó ïðåäìåòíûõ îáëàñ-
òåé, îíà ïîçâîëÿåò õîðîøî ñòðóêòóðèðîâàòü àëãåáðàè÷åñêèå ïðîãðàììû, à òàêæå ðå-
øàòü çàäà÷è ñèíòåçà è âåðèôèêàöèè àëãåáðàè÷åñêèõ ïðîãðàìì. Íàïðèìåð, â [12] ýòîò
ïîäõîä ïðèìåíÿåòñÿ ê òàêîé ïðåäìåòíîé îáëàñòè, êàê àëãåáðà âûñêàçûâàíèé. Ïîä÷åðê-
íåì, ÷òî ìû ñïåöèôèöèðóåì ñîáñòâåííî ïðåäìåòíûå îáëàñòè, à íå òîëüêî àëãîðèòìû.
 ÷àñòíîñòè, îïèñûâàåìûé àëãîðèòì ðåøåíèÿ ÑËÍ ñòðîèò êàíîíè÷åñêóþ ôîðìó
ýòîé ñèñòåìû. Êðîìå òîãî, â ðàáîòå íàìå÷åíû è äðóãèå àëãîðèòìû: àëãîðèòì ñâåäåíèÿ
êðàòíîãî èíòåãðàëà ïî ìíîãîãðàííîé îáëàñòè ê ïîâòîðíûì èíòåãðàëàì, àëãîðèòì èç-
ìåíåíèÿ ïîðÿäêà èíòåãðèðîâàíèÿ, à òàêæå àëãîðèòì ðåøåíèÿ çàäà÷è ëèíåéíîãî ïðî-
ãðàììèðîâàíèÿ (ïîèñê ìàêñèìóìà ëèíåéíîé ôóíêöèè íà ìíîãîãðàííîé îáëàñòè).
Êàíîíè÷åñêàÿ ôîðìà èñïîëüçóåò èäåþ ïðîåêòèðîâàíèÿ (ýëèìèíàöèè êâàíòîðà)
ìåòîäîâ Ôóðüå–Ìîöêèíà [13, 14], ×åðíèêîâà [15].
1. ÑÈÑÒÅÌÛ ËÈÍÅÉÍÛÕ ÍÅÐÀÂÅÍÑÒÂ. ÎÁÙÈÅ ÑÂÅÄÅÍÈß
Ëèíåéíîå íåðàâåíñòâî (ËÍ) L èìååò âèä
L a x a x a x bm m� � � � �1 1 2 2 � , x a bj j� �Variable Coef, , ,
A a a X x x L A X bm m� � � � �( ,... , ), ( ,... , ),1 1 .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 2 175
© Ì.Ñ. Ëüâîâ, 2010
Òàêèì îáðàçîì, àëãåáðà ËÍ èñïîëüçóåò ëèíåéíîå ïðîñòðàíñòâî LinComb íàä
óïîðÿäî÷åííûì ïîëåì Coef, à òàêæå àëãåáðó ïåðåìåííûõ Variable.
ÑËÍ çàäàþòñÿ ëîãè÷åñêèìè ôîðìóëàìè âèäà S L L Ln� 1 2& & &� , ãäå L j —
ëèíåéíûå íåðàâåíñòâà.
Îñíîâíûå çàäà÷è òåîðèè ÑËÍ:
1) ïðîâåðèòü ñîâìåñòíîñòü (ñóùåñòâîâàíèå ðåøåíèÿ);
2) ïðèâåñòè ê êàíîíè÷åñêîìó âèäó (ðåøèòü); ðåøåíèå — âûïóêëûé ìíîãî-
ãðàííèê â n-ìåðíîì ïðîñòðàíñòâå, òàêèì îáðàçîì, êàíîíè÷åñêàÿ ôîðìà äîëæíà îïè-
ñûâàòü ìíîãîãðàííèê ðåøåíèé, íàïðèìåð, ÷åðåç âåðøèíû èëè óðàâíåíèÿ ãðàíåé.
Îñîáàÿ íîðìàëüíàÿ ôîðìà ËÍ è ÑËÍ — x-ðàçðåøåííàÿ ôîðìà. Ïóñòü x —
ïåðåìåííàÿ, âõîäÿùàÿ â ëåâóþ ÷àñòü ËÍ ñ íåíóëåâûì êîýôôèöèåíòîì. Òîãäà ËÍ
ìîæíî ïðåîáðàçîâàòü ê âèäó
x B X b� � � èëè x B X b� � � . (1)
Òàêóþ ôîðìó ËÍ áóäåì íàçûâàòü ðàçðåøåííîé îòíîñèòåëüíî x, èëè x-ðàçðåøåííîé.
Åñëè êàæäîå ËÍ ñèñòåìû, çàâèñÿùåå îò x, ïðåäñòàâëåíî â ðàçðåøåííîé ôîðìå, òî
òàêóþ ÑËÍ áóäåì íàçûâàòü ïðåäñòàâëåííîé â x-ðàçðåøåííîé ôîðìå. Ëþáóþ ÑËÍ
ìîæíî ïðåäñòàâèòü â x-ðàçðåøåííîé ôîðìå. Òî÷íåå, â âèäå LL x GL x FL( )& ( )& , ãäå
êàæäîå íåðàâåíñòâî LL x( ) èìååò âèä x B X b� � � , êàæäîå íåðàâåíñòâî GL x( ) èìååò
âèä x B X b� � � , êàæäîå íåðàâåíñòâî FL íå çàâèñèò îò x.
Èçâåñòíûé àëãîðèòì Ôóðüå–Ìîöêèíà ïðîâåðêè ñîâìåñòíîñòè ÑËÍ [13, 14]
è åãî óñîâåðøåíñòâîâàíèå — ìåòîä ×åðíèêîâà [15] — îñíîâàí íà ñëåäóþùåì
ôàêòå: ÑËÍ ( )&( )x B X b x B X b� � � �1 1 2 2 ñîâìåñòíà òîãäà è òîëüêî òîãäà, êîãäà
ñîâìåñòíî ËÍ B X b B X b2 2 1 1� � � .  òåîðåòèêî-ëîãè÷åñêîé ôîðìóëèðîâêå ïðåîá-
ðàçîâàíèå èìååò âèä
� � � � � � � � � � � � � �X x x B X b x B X b X B X b B X b( )&( ) ~ ( )1 1 2 1 1 2 2 . (2)
Ïî ñóùåñòâó îíî ýëèìèíèðóåò êâàíòîð � x. Ãåîìåòðè÷åñêè ïðåîáðàçîâàíèå çà-
êëþ÷àåòñÿ â ïðîåêòèðîâàíèè îáëàñòè ðåøåíèé íà ïîäïðîñòðàíñòâî X .
Ïóñòü äàío äâà ËÍ îäíîãî çíàêà: L x B X b L x B X b1 1 1 2 2 2� � � � � � � �, . Òîã-
äà ìíîæåñòâî ðåøåíèé L L1 2& îïèñûâàåòñÿ ôîðìóëîé
L L x x B X b B X b1 2 1 1 2 2& : min ( , )� � � � � �{ }. (3)
Àíàëîãè÷íî äëÿ ËÍ ïðîòèâîïîëîæíîãî çíàêà ïîëó÷àåì
G G x x B X b B X b1 2 1 1 2 2& : max( , )� � � � � �{ }. (4)
Ìíîæåñòâî ðåøåíèé CËÍ ïðîòèâîïîëîæíûõ çíàêîâ L G& íà ÷èñëîâîì ìíîæåñòâå S
îñè Ox îáîçíà÷èì R x S L G( , , , ) .
Òîãäà
R x S L G R x S L G( , , , ) ( , , , )1 1 2 2 �
� R x S L L( , , min ( , ),1 2
max( , ))G G1 2 . (5)
Íà ðèñ. 1 ïîêàçàíî, ÷òî ÷èñ-
ëîâîé ïðîìåæóòîê ïðîåêöèÿìè
òî÷åê ïåðåñå÷åíèÿ A L L1 1 2� ,
A R R2 1 2� ðàçáèâàåòñÿ íà òðè
÷àñòè. Íà êàæäîé èç íèõ ìíîæåñ-
òâî ðåøåíèé îïèñûâàåòñÿ ôîð-
ìóëîé R x S L G( , , , ) .
176 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 2
xR
G1
G2
L1
L2
À1
À2
Ðèñ. 1
2. ×ÀÑÒÍÛÉ ÑËÓ×ÀÉ: ÐÅØÅÍÈÅ ÑËÍ ÍÀ ÏËÎÑÊÎÑÒÈ
Çàäà÷à ïîñòðîåíèÿ îáëàñòè ðåøåíèÿ ÑËÍ äîñòàòî÷íî èçâåñòíà.  ÷àñòíîì ñëó-
÷àå, êîãäà n � 2, ýòó çàäà÷ó ìîæíî ïåðåôîðìóëèðîâàòü êàê çàäà÷ó ïîñòðîåíèÿ
âûïóêëîé ëèíåéíîé îáîëî÷êè ïî ñèñòåìå ËÍ, çàäàþùèõ ñòîðîíû ìíîãîóãîëüíè-
êà ðåøåíèÿ — îäíó èç îñíîâíûõ çàäà÷ âû÷èñëèòåëüíîé ãåîìåòðèè è êîìïüþòåð-
íîé ãðàôèêè [16, 17].  ìàòåìàòè÷åñêèõ ñèñòåìàõ ó÷åáíîãî íàçíà÷åíèÿ ýòó çàäà-
÷ó ìîæíî ñôîðìóëèðîâàòü êàê çàäà÷ó ðåàëèçàöèè òàê íàçûâàåìîãî ãðàôè÷åñêîãî
ìåòîäà â ëèíåéíîì ïðîãðàììèðîâàíèè [18]. Îñíîâíàÿ èäåÿ ìåòîäà ïðîèëëþñ-
òðèðîâàíà ðèñ. 1–3. Ïðåäïîëîæèì, ÷òî ìíîãîóãîëüíèê ðåøåíèÿ R , êàæäàÿ ñòîðî-
íà êîòîðîãî çàäàíà ËÍ, ðàçáèò íà îáëàñòè-òðàïåöèè R1, R2 , R3 , R4 .
R R R R R� � � � � � �1 2 3 4 (ñì. ðèñ. 2). Äîáàâëåíèå íîâîãî ËÍ â ÑËÍ çàêëþ÷à-
åòñÿ â òîì, ÷òî R2 è R4 ðàçáèâàþòñÿ íà äâå ÷àñòè, à ó R3 èçìåíÿåòñÿ âåðõíÿÿ
ñòîðîíà (øàïêà):
R R R2 2 2� � �' ' ' , R R R4 4 4� � �' ' ' , R R3 3
1� . (6)
Óòî÷íèì, ÷òî ðàâåíñòâà (6) èíòåðïðåòèðîâàíû êàê ïåðåïèñûâàþùèå ïðàâèëà.
 ðåçóëüòàòå ïðåîáðàçîâàíèÿ ïîëó÷èì
R R R R R R R' ' '' ' ' ' '� � � � � � � � � � �1 2 2 3 4 4 . (7)
Âîçìîæåí òàêæå âàðèàíò, ïðè êîòîðîì äîáàâëåíèå íîâîãî íåðàâåíñòâà ïðèâî-
äèò ê ñëèÿíèþ íåñêîëüêèõ îáëàñòåé â îäíó (ñì. ðèñ. 3).
Òàêèì îáðàçîì, àëãîðèòì ïîñëåäîâàòåëüíî äîáàâëÿåò ê ïîñòðîåííîìó ìíîãîóãîëü-
íèêó íîâîå ïîëóïðîñòðàíñòâî, ïåðåñåêàÿ åãî ñ ìíîãîóãîëüíèêîì. Îòìåòèì, ÷òî âîçìîæ-
íû è äðóãèå âàðèàíòû óïðàâëåíèÿ âû÷èñëåíèÿìè: íàïðèìåð, ìîæíî ïðèìåíèòü ìåòîä
«ðàçäåëÿé è âëàñòâóé». Â ýòîì âàðèàíòå àëãîðèòìà ÑËÍ ðàçáèâàåòñÿ íà äâå ïîäñèñòåìû,
ñîäåðæàùèå ïðèìåðíî ðàâíîå ÷èñëî íåðàâåíñòâ. Ðåêóðñèâíîå ïðèìåíåíèå îñíîâíîé
ïðîöåäóðû ñòðîèò äâà ìíîãîóãîëüíèêà, êîòîðûå çàòåì íóæíî ïåðåñå÷ü, ïîëó÷èâ ðåøå-
íèå âñåé ÑËÍ. Îáùèé àëãîðèòì âïîëíå àíàëîãè÷åí àëãîðèòìó â ýòîì ÷àñòíîì ñëó÷àå.
3. ÊÎÍÑÒÐÓÊÒÈÂÍÀß ÀËÃÅÁÐÀ ÑËÍ (ÀËÃÅÁÐÀ ÂÛÏÓÊËÛÕ ÌÍÎÃÎÃÐÀÍÍÈÊÎÂ)
Cóòü äàííîãî ïîäõîäà ê çàäà÷å ðåøåíèÿ ÑËÍ ñîñòîèò â ñëåäóþùåì. Âî-ïåðâûõ,
îïðåäåëèì òàêóþ èñõîäíóþ ìíîãîñîðòíóþ àëãåáðó ÑËÍ Ainit , ÷òî ÑËÍ îïèñû-
âàåòñÿ âûðàæåíèåì â ñèãíàòóðå Ainit . Âî-âòîðûõ, îïðåäåëèì ñïåöèàëüíóþ ìíî-
ãîñîðòíóþ êîíñòðóêòèâíóþ àëãåáðó ÑËÍ Aconstr . Åå êîíñòðóêòèâíîñòü çàêëþ÷à-
åòñÿ â òîì, ÷òî â åå îïèñàíèå âêëþ÷åíû òàê íàçûâàåìûå êîíñòðóêòîðû ýëåìåí-
òîâ è èíòåðïðåòàòîðû îïåðàöèé â âèäå ñèñòåì ïåðåïèñûâàþùèõ ïðàâèë.
Â-òðåòüèõ, îïðåäåëèì èçîìîðôèçìû � : A Ainit constr
, �
�
1: A Aconstr init . Âû-
÷èñëåíèÿ çíà÷åíèÿ Val ( ( ))F X âûðàæåíèÿ F X( ) ñòðîÿòñÿ ïî ñõåìå
Val Can( ( )) ( ( ( ( )))F X F X� �
� �
1 . (8)
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 2 177
Ðèñ. 2
R1
R2
R3
R4
R2
'
R2
''
R4
'
R4
''
Ðèñ. 3
R1
R2
R3
R4
Ïîäðîáíîå îïèñàíèå îáùåãî ïîäõîäà èçëîæåíî â [8–11].
Ïðèâåäåì êðàòêîå îïèñàíèå àëãåáð Ainit è Aconstr .
1. Ìíîãîñîðòíàÿ àëãåáðà ÑËÍ Ainit èñïîëüçóåò ñëåäóþùèå ñîðòà:
� Coef — óïîðÿäî÷åííîå ÷èñëîâîå ïîëå;
� Variable — ëèíåéíî-óïîðÿäî÷åííîå ìíîæåñòâî ïåðåìåííûõ;
� LinComb — âåêòîðíîå ïðîñòðàíñòâî àôôèííûõ ëèíåéíûõ êîìáèíàöèé;
� LinUnEqu — àëãåáðà ëèíåéíûõ íåðàâåíñòâ;
� SysLinUnEqu — àëãåáðà ñèñòåì ëèíåéíûõ íåðàâåíñòâ.
2. Äëÿ îïèñàíèÿ êîíñòðóêòèâíîé àëãåáðû ÑËÍ Aconstr íàì ïîíàäîáÿòñÿ ñîðòà,
îïèñàííûå íèæå. Ñîðòà Coef è Variable (áàçîâûå ñîðòà) äîëæíû áûòü ðåàëèçîâàí-
íû â ñèñòåìå àëãåáðàè÷åñêîãî ïðîãðàììèðîâàíèÿ.
3.1. Ñîðò LinUnEqu. Ýëåìåíòàìè ýòîãî ñîðòà ÿâëÿþòñÿ ËÍ, ïðåäñòàâëåííûå
â x-ðàçðåøåííîé ôîðìå, ãäå x — ñòàðøàÿ ïåðåìåííàÿ ËÍ:
x a x a x bn n n� � � � � �� �1 1 1 1 1� èëè x a x a x bn n n� � � � � �� �1 1 1 1 1� . (9)
Ñïåöèàëüíàÿ îïåðàöèÿ X LCan( ) ïðèâîäèò ïðîèçâîëüíîå âûðàæåíèå L B X b� � � �1 1
� � �B X b2 2 â ñèãíàòóðå àëãåáðû ËÍ ê êàíîíè÷åñêîé ôîðìå [9]. Ñåëåêòîðû ñîðòà
âûäåëÿþò èìÿ ïåðåìåííîé, çíàê íåðàâåíñòâà (� èëè �) è åãî ïðàâóþ ÷àñòü.
3.2. Ñîðò Interval — ýòî ñîðò ÷èñëîâûõ ïðîìåæóòêîâ íà ðàñøèðåííîé ÷èñëî-
âîé îñè. Ðàñøèðåíèå ÷èñëîâîé îñè îñóùåñòâëÿåòñÿ äîáàâëåíèåì ê óïîðÿäî÷åííîìó
÷èñëîâîìó ïîëþ Coef ñèìâîëîâ – Inf , � Inf (ìèíóñ áåñêîíå÷íîñòü, ïëþñ áåñêîíå÷-
íîñòü). Ðàñøèðåííóþ ÷èñëîâóþ îñü áóäåì íàçûâàòü ExtCoef .
 àëãåáðå Interval ÷èñëîâûõ ïðîìåæóòêîâ íà ðàñøèðåííîé ÷èñëîâîé îñè îïðå-
äåëåíû àííóëèðóþùèé ýëåìåíò — ïóñòîé îòðåçîê O è íåéòðàëüíûé ýëåìåíò
I � � �[ , ]Inf Inf . Ïî îïðåäåëåíèþ äëÿ ëþáîãî ýëåìåíòà c �Coef èìååò ìåñòî äâîé-
íîå íåðàâåíñòâî �
�Inf Infc . Îòíîñèòåëüíî îïåðàöèè ïåðåñå÷åíèÿ àëãåáðà
Interval îáðàçóåò èäåìïîòåíòíóþ êîììóòàòèâíóþ ïîëóãðóïïó ñ íóëåì è åäèíèöåé.
Êðîìå îïåðàöèè ïåðåñå÷åíèÿ îòðåçêîâ, îáîçíà÷àåìîé «&», äëÿ ñîðòà Interval
îïðåäåëåíà îïåðàöèÿ ðàçáèåíèÿ îòðåçêà:
Partition ([ , ], ) [ , ] [ , ]a b c a c c b� � � . (10)
Ðåçóëüòàò ýòîé îïåðàöèè îïðåäåëåí â íåêîòîðîì ðàñøèðåíèè ñîðòà Interval.
Îáðàòíàÿ îïåðàöèÿ — îïåðàöèÿ ñëîæåíèÿ îòðåçêîâ — îïðåäåëåíà ñîîòíîøåíèåì
[ , ] [ , ] [ , ]a c c b a b� � � . (11)
3.3. Ñîðò VarSegment. Ýòî ñîðò ýëåìåíòàðíûõ ìíîãîãðàííèêîâ ïðîñòðàíñòâà
ðåøåíèé ÑËÍ. Ýëåìåíò ýòîãî ñîðòà îïèñûâàåòñÿ êîíñòðóêòîðîì
S L Y x G Y� [ ( ), , ( )] (12)
ñ ñåìàíòèêîé
L Y x G Y( ) ( )� � , (13)
ãäå x — ïåðåìåííàÿ, Y x xk� �{ , , }1 , L Y( ) , G Y( ) — ëèíåéíûå êîìáèíàöèè ïåðå-
ìåííûõ èç Variable ñ êîýôôèöèåíòàìè èç Coef, ò.å. ýëåìåíòàìè ñîðòà
LinComb Coef( , )Y . Ýëåìåíòû ñîðòà VarSegment íàçîâåì x-ñåãìåíòàìè, èëè ïðîñ-
òî ñåãìåíòàìè. Ñîðò Interval ìîæíî ðàññìàòðèâàòü êàê ÷àñòíûé ñëó÷àé ñîðòà
VarSegment.
3.4. Ñîðò Trapezoid — ýòî ñîðò ýëåìåíòàðíûõ òðàïåöîèäîâ â ïðîñòðàíñòâå ðå-
øåíèé ÑËÍ. Äëÿ äâóìåðíîãî ïðîñòðàíñòâà W x y( , ) ýëåìåíò ýòîãî ñîðòà çàäàí êîíñò-
ðóêöèåé T l x g L x y Q x� [ , , ] [ ( ), , ( )]. c cåìàíòèêîé T l x g L x y Q x� � � � �( )&( ( ) ( )) .
178 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 2
Äëÿ n-ìåðíîãî ïðîñòðàíñòâà W X( ) , ãäå X x xn� �{ , , }1 , ýëåìåíò ýòîãî ñîðòà
çàäàí êîíñòðóêöèåé
T L X x G X L x x G x Ln n n n n� � � �[ ( ), , ( )] [ ( ), , ( )] [ ,. . .1 1 2 1 2 2 1 1 x G1 1, ] , (14)
ãäå X x xk k� �� �1 1 1( , , ) , c ñåìàíòèêîé
T L X x G X l x x g x L xn n n n n� � � � � � �� �( ( ) ( )& &( ( ) ( ))&(1 1 2 1 2 2 1 1 1 1� G ) . (15)
Òî÷êà «.» — îòìåòêà êîíñòðóêòîðà ñîðòà Trapezoid. Äîïóñêàåòñÿ èñïîëüçîâàíèå
è äðóãèõ îáîçíà÷åíèé:
T S Sx y� � , S l x gx � [ , , ] , S L y Qy � [ , , ] , T S x S y
l
g
L
Q
� �( ) ( ) .
Çàìå÷àíèå 1. Òðàïåöîèä —
âûïóêëàÿ ôèãóðà â n-ìåðíîì ïðî-
ñòðàíñòâå, ïîñëåäîâàòåëüíûå ïðî-
åêöèè êîòîðîé íà ïîäïðîñòðàí-
ñòâà ìåíüøåé ðàçìåðíîñòè — òàê-
æå òðàïåöîèäû (ðèñ. 4). Óðàâíå-
íèÿ x L Xn n� �( )1 , x G Xn n� �( )1
çàäàþò íèæíþþ è âåðõíþþ
«øàïêè» òðàïåöîèäà, åñëè ÷èñëî-
âóþ îñü Oxn ðàññìàòðèâàòü êàê
âåðòèêàëüíóþ. Òàêèì îáðàçîì,
åñëè òðàïåöîèä T çàäàí ôîðìóëîé
T S T� . 1 , xn — îòðåçîê, S îïðå-
äåëÿåò T ïî êîîðäèíàòå xn , à T1
— ïðîåêöèÿ T íà ïîäïðîñòðàíñò-
âî W X n( )�1 . �
Òî÷êà — îòìåòêà êîíñòðóê-
òîðà ñîðòà Trapezoid — èíòåðïðåòèðóåòñÿ êàê îïåðàöèÿ ïåðåñå÷åíèÿ, åñëè ââåñòè â
ðàññìîòðåíèå åäèíèöó ïîëóãðóïïû — áåñêîíå÷íûé ñåãìåíò I x( ) [ ,� � Inf x, ]� Inf . Òîãäà
äëÿ T S y S x� 1 2( ) ( ). , T S y I x1 1� ( ) ( ). , T I y S x2 2� ( ) ( ). ñïðàâåäëèâî ñîîòíîøåíèå
T T T� 1 2& .
Òàêèì îáðàçîì, àëãåáðà òðàïåöîèäîâ TR ïðåäñòàâëåíà â âèäå ïðÿìîãî ïðåäåëà
âîçðàñòàþùåé ïîñëåäîâàòåëüíîñòè àëãåáð:
TR TR TR( ) ( , ) ( , , )x x x x xn1 1 2 1� � �� � � �, (16)
TR TR { } Variable� � �
�
�
j
j j jX X x x
1
1� ( ), ,... , . (17)
 òåðìèíîëîãèè [8] TR — ëèíåéíîå äèíàìè÷åñêîå ðàñøèðåíèå àëãåáðû VarSegment.
Êðîìå åäèíèöû, â àëãåáðå TR åñòü åùå è íîëü (àííóëÿòîð) — ïóñòîé ÷èñëîâîé
ïðîìåæóòîê. Íóëåì ÿâëÿåòñÿ ýëåìåíò ñîðòà VarSegment âèäà [ , , ]a x b , a b, �Coef,
a b� . Òàêèì îáðàçîì, èìåþò ìåñòî ñîîòíîøåíèÿ
( )&( )&( ) [ , , ]a b a b a x b O� � �
�Coef Coef , (18)
S O O. � .
Êðîìå ýòîãî, ñâîéñòâàìè íóëåâîãî ýëåìåíòà îïåðàöèè ñëîæåíèÿ ñåãìåíòîâ îáëà-
äàåò ñåãìåíò âèäà [ , , ]a x a , òî÷íåå, èìåþò ìåñòî ñîîòíîøåíèÿ
[ , , ] [ , , ] [ , , ], [ , , ] [ , , ] [ , , ]L x G G x G L x G L x L L x G L x G� � � � � � .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 2 179
G2(x, y)
L2(x, y)
G1(x)L1(x)G0
L0
x
y
z
Ðèñ. 4
4. ÑÎÐÒ CONPOL
Ñîðò ConPol (Convex Polygon) — ýòî ñîðò âûïóêëûõ ìíîãîãðàííèêîâ â ïðîñòðàíñò-
âå ðåøåíèé ÑËÍ. Â n-ìåðíîì ïðîñòðàíñòâå ýëåìåíò ýòîãî ñîðòà (âûïóêëûé ìíî-
ãîãðàííèê) çàäàí êîíñòðóêöèåé
P T T Tk� � � � � �� �1 2 . (19)
Çàìå÷àíèå 2. Îòìåòêà «� �» êîíñòðóêòîðà ñîðòà îòìå÷àåò ðàçáèåíèå âûïóêëîãî
ìíîãîãðàííèêà íà (íåïåðåñåêàþùèåñÿ) òðàïåöîèäû. Ëèíåéíûé ïîðÿäîê, çàôèêñèðî-
âàííûé íà ìíîæåñòâå ïåðåìåííûõ Variable, îïðåäåëÿåò ïîñëåäîâàòåëüíîñòü ïðîåêòè-
ðîâàíèé âûïóêëîãî ìíîãîãðàííèêà P íà ïîäïðîñòðàíñòâà âñå ìåíüøåé è ìåíüøåé
ðàçìåðíîñòè. Îñíîâíàÿ èäåÿ äàííîé êîíñòðóêöèè èñõîäèò èç ñëåäóþùåé çàäà÷è.
Ïóñòü G — ìíîãîãðàííàÿ îáëàñòü n-ìåðíîãî ïðîñòðàíñòâà, çàäàííàÿ ÑËÍ, íå-
îáõîäèìî âû÷èñëèòü (êðàòíûé) èíòåãðàë f X dX
G
( )� . Ïðè ïåðåõîäå îò êðàòíîãî èí-
òåãðàëà ê ïîâòîðíûì íóæíî îïðåäåëèòü ïîðÿäîê è ïðåäåëû èíòåãðèðîâàíèÿ. Îòìå-
òèì, ÷òî ïðåäåëû èíòåãðèðîâàíèÿ äîëæíû áûòü àíàëèòè÷åñêèìè âûðàæåíèÿìè, ò.å.
ëèíåéíûìè êîìáèíàöèÿìè ïåðåìåííûõ. Òàêèì îáðàçîì, èñêîìûé êðàòíûé èíòåã-
ðàë äîëæåí áûòü ïðåäñòàâëåí â âèäå ñóììû ïîâòîðíûõ èíòåãðàëîâ, â êàæäîì èç
êîòîðûõ ïðåäåëû èíòåãðèðîâàíèÿ îïðåäåëÿþò èìåííî òðàïåöîèäû:
f X dX f X dX
TjG j
( ) ( )� ��� ., f X dX f x x dx dx dxn n
l
g
L
G
L
G
n
n
n
n
( ) ( ,... , ) ...� ��
�
�
� 1 1 2
1
1
1
1
��
Tj
.
ßñíî, ÷òî ðåøåíèå ýòîé çàäà÷è ñóùåñòâóåò, è åñëè óñòàíîâèòü ïîðÿäîê èíòåãðè-
ðîâàíèÿ è ïîòðåáîâàòü ìèíèìàëüíîñòè êîëè÷åñòâà ðàçáèåíèé, òàêîå ïðåäñòàâëå-
íèå îáëàñòè åäèíñòâåííî ñ òî÷íîñòüþ äî êîììóòàòèâíîñòè. �
Îñíîâíàÿ îïåðàöèè ñîðòà ConPol — îïåðàöèÿ ïåðåñå÷åíèÿ äâóõ âûïóêëûõ
ìíîãîãðàííèêîâ. Åùå îäíà îïåðàöèÿ — îïåðàöèÿ ñëîæåíèÿ/ðàçáèåíèÿ (ðàçáèåíèå
ìíîæåñòâà íà äâà íåïåðåñåêàþùèõñÿ ïîäìíîæåñòâà èëè îáúåäèíåíèå). Ñîðò ConPol
ÿâëÿåòñÿ ëèíåéíûì äèíàìè÷åñêèì ðàñøèðåíèåì ñîðòà Trapezoid, ïîýòîìó ýòè îïå-
ðàöèè îïðåäåëÿþòñÿ ÷åðåç ñîîòâåòñòâóþùèå îïåðàöèè ñîðòà Trapezoid. Ñîðò
Trapezoid, â ñâîþ î÷åðåäü, ÿâëÿåòñÿ ðàñøèðåíèåì ñîðòà VarSegment, ïîýòîìó ýòè
îïåðàöèè, â ñâîþ î÷åðåäü, îïðåäåëÿþòñÿ ÷åðåç ñîîòâåòñòâóþùèå îïåðàöèè ñîðòà
VarSegment. Îòìåòèì, ÷òî îïåðàöèÿ ðàçáèåíèÿ îïðåäåëåíà ÷àñòè÷íî.
4.1. Îïåðàöèÿ ïåðåñå÷åíèÿ íà ñîðòå ConPol. Ýôôåêòèâíîñòü àëãîðèòìà â öå-
ëîì çàâèñèò îò ýôôåêòèâíîñòè ðåàëèçàöèè îïåðàöèè ïåðåñå÷åíèÿ íà ñîðòå ConPol.
Ñèìâîë îïåðàöèè ïåðåñå÷åíèÿ — çíàê êîíúþíêöèè &. Ýòà îïåðàöèÿ çàäàíà íà ñîð-
òå ConPol ÷åðåç åå îïðåäåëåíèÿ íà áàçîâûõ ñîðòàõ VarSegment è Trapezoid. Íà ñîðòå
VarSegment ïåðåñå÷åíèå îïðåäåëåíî ôîðìóëàìè
[ ( ), , ( )]&[ ( ), , ( )] [max( , ), , min (L X y G X L X y G X L L y1 1 2 2 1 2� G G1 2, )] . (20)
Ïðè ýòîì ðåçóëüòàò îïåðàöèè äîëæåí óäîâëåòâîðÿòü ñîîòíîøåíèþ
max( , ) min ( , )L L G G1 2 1 2� . (21)
Çàìåòèì, ÷òî max( , )L L1 2 , min ( , )G G1 2 íå ïðèíàäëåæàò áàçîâîìó ñîðòó
LinComb. Ïîýòîìó îïåðàöèþ ïåðåñå÷åíèÿ íóæíî îïðåäåëèòü áîëåå òî÷íî. Ñëåäóþ-
ùèå ðèñóíêè èëëþñòðèðóþò âñåâîçìîæíûå âàðèàíòû âçàèìíîãî ðàñïîëîæåíèÿ ãðà-
íèö ñåãìåíòîâ äëÿ ñëó÷àÿ n � 2, ïðè êîòîðîì ðàññìàòðèâàåìûå ìíîãîãðàííèêè —
ñóòü òðàïåöèè. Âî-ïåðâûõ, îãðàíè÷èìñÿ ðàññìîòðåíèåì ïåðåñå÷åíèÿ òðàïåöèè ñ ïî-
ëóïëîñêîñòüþ, çàäàííîé íåðàâåíñòâîì y G X� ( ) . Âïîëíå àíàëîãè÷íî ðàññìàòðèâà-
åòñÿ ïåðåñå÷åíèå òðàïåöèè ñ ïîëóïëîñêîñòüþ y L X� ( ). Âî-âòîðûõ, áóäåì ñ÷èòàòü,
÷òî ïåðåñåêàåìûé ïîëóïëîñêîñòüþ ñåãìåíò S L X y G X1 1 1� [ ( ), , ( )] îïðåäåëåí íà
òðàïåöîèäå T ïîäïðîñòðàíñòâà W x u u x xn n( ) { : ( , , )}� �� � �1 1 1 . Îïåðàöèÿ ïåðåñå÷å-
180 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 2
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 2 181
íèÿ îïðåäåëåíà íà ýëåìåíòàõ S T1. , S T. , ïðè÷åì L X G X
X T1 1( ) ( )�
�
. Äëÿ ñëó÷àÿ n � 2
òðàïåöîèä T — îòðåçîê ÷èñëîâîé îñè Ò L x G� [ , , ]0 0
.
Ëîãè÷åñêè âîçìîæíî øåñòü âàðèàíòîâ âçàèìíîãî ðàñïîëîæåíèÿ òðàïåöîèäà è
ïîëóïëîñêîñòè, êîòîðàÿ åãî ïåðåñåêàåò (ðèñ. 5).
Âàðèàíò 1 (ðèñ. 5, à): G G S T S S TT� � �1 1 1. . .
Âàðèàíò 2 (ðèñ. 5, á) : ( & )&( ) [ , , ]. .G G G L S T S L y G TT T1 1 1 1 1 1� � � � � �
� [ , , ] .L y G T1 2 , T X G GT1 1� �{ : }, T T T2 1� � .
Âàðèàíò 3 (ðèñ. 5, â): ( & )& ( & ) [ , , ]. .G G G L S T S L y G TT T1 1 1 1 1 1� � � � � � �
� [ , , ].L y G T1 2, T X G GT1 1� �{ : }, T X G GT2 1� �{ : }.
Âàðèàíò 4 (ðèñ. 5, ã): ( )&( ) [ , , ]. .G L G G S T S G y L TT T� � � �1 1 1 1 .
Âàðèàíò 5 (ðèñ. 5, ä): ( )&( & ) [ , , ]. .G L G L S T S L y G TT T� � � � �1 1 1 1 1,
T X L GT1 1� �{ : }.
Âàðèàíò 6 (ðèñ. 5, å): G G S T ST� � � �1 1. & .
Îñíîâíîé èñòî÷íèê íåýôôåêòèâíîñòè àëãîðèòìà, îïèñûâàåìîãî ñîîòíîøåíèÿ-
ìè ýòèõ âàðèàíòîâ, — íàëè÷èå äâóõ ñëàãàåìûõ â ïðàâûõ ÷àñòÿõ ñîîòíîøåíèé è íå-
îáõîäèìîñòü âû÷èñëåíèÿ íîâûõ òðàïåöîèäîâ-ïðîåêöèé: T1 è T2 .  âàðèàíòå 6 êîëè-
÷åñòâî òðàïåöîèäîâ â ïåðåñå÷åíèè óìåíüøàåòñÿ, â âàðèàíòàõ 1, 4 íå èçìåíÿåòñÿ,
ïðè÷åì ïðîåêöèè îñòàþòñÿ íåèçìåííûìè, â âàðèàíòå 5 èõ êîëè÷åñòâî íå èçìåíÿåò-
ñÿ, íî èçìåíÿåòñÿ ïðîåêöèÿ. Õóäøèå ñëó÷àè — âàðèàíòû 2, 3, â êîòîðûõ êîëè÷åñò-
âî òðàïåöîèäîâ óâåëè÷èâàåòñÿ è ïðîåêöèè èçìåíÿþòñÿ.
4.2. Àëãîðèòì ðàñïîçíàâàíèÿ âàðèàíòà. Âñå ñîîòíîøåíèÿ, îïðåäåëåííûå
â âàðèàíòàõ, óñëîâíûå. Óñëîâèÿ îïðåäåëåíû â òåðìèíàõ îòíîøåíèÿ ÷àñòè÷íîãî ïî-
G1
L1
G0L0
G
G1
L1
G0L0
G
G1
L1
G0L0
G
G0
L0
G1
L1
G
G1
L1
G0L0
G
G1
L1
G0L0
G
Ðèñ. 5
à á â
åäã
ðÿäêà «�T ». L GT� îçíà÷àåò, ÷òî òðàïåöèÿ y L X� ( ) ðàñïîëîæåíà íèæå òðàïåöèè
y G X� ( ) íà îáëàñòè T , òî÷íåå, íà T âûïîëíÿåòñÿ íåðàâåíñòâî G X L X( ) ( )� � 0.
 ñâîþ î÷åðåäü, ýòî îçíà÷àåò, ÷òî
y L X G X
X T
max max ( ( ) ( ))� � �
�
0. (22)
Èç òîãî, ÷òî ôóíêöèÿ y L X G X� �( ) ( ) ëèíåéíà è ÷òî òðàïåöîèä T — ìíîãîãðàí-
íàÿ îáëàñòü, ñëåäóåò, ÷òî ìàêñèìóì äîñòèãàåòñÿ â îäíîé èç âåðøèí òðàïåöîèäà T.
Íàêîíåö, ôîðìà ïðåäñòàâëåíèÿ òðàïåöîèäà â âèäå ïîñëåäîâàòåëüíîñòè åãî ïðî-
åêöèé íà ïîäïðîñòðàíñòâà âñå ìåíüøåé ðàçìåðíîñòè ïîçâîëÿåò âû÷èñëèòü èñêî-
ìûé ìàêñèìóì äîñòàòî÷íî ýôôåêòèâíî — çà âðåìÿ O n( )2 . Ïîêàæåì ýòî.
1. Ïðèâåäåì òðàïåöîèä T S S Sn n� �1
2. . . ê âèäó S x g Xi i i i� �[ , , ( )]0 1 ïðåîá-
ðàçîâàíèåì
S l X x g X x l X g Xi i i i i i i i i i i� � � �� � � �[ ( ), , ( )] [ , ( ), ( )1 1 1 10 l Xi i( )]�1 (23)
è ïîñëåäóþùåé çàìåíîé ïåðåìåííûõ x x l xi i i i� � �( )1 . Ýòè ïðåîáðàçîâàíèÿ âû-
ïîëíÿþòñÿ íà òðàïåöîèäå çà âðåìÿ O n( )2 .
2. Ðàññìîòðèì ñëåäóþùóþ çàäà÷ó ëèíåéíîãî ïðîãðàììèðîâàíèÿ (ÇËÏ): íàéòè
maxF ëèíåéíîé ôóíêöèè F c x c x c xn n n n� ��� �� �1 1 1 1 íà ïðèâåäåííîì òðàïåöîèäå
Tn . Ïîñêîëüêó ðåøåíèå ÇËÏ äîñòèãàåòñÿ íà ãðàíèöàõ òðàïåöîèäà Tn , ðàññìîòðèì
äâà ñëó÷àÿ:
� xn � 0, ÇËÏ ñâîäèòñÿ ê çàäà÷å ðàçìåðíîñòè n �1: íà òðàïåöîèäå Tn� �1
� � �S S S n1 2 1. . . íàéòè maxF1 ôóíêöèè
F c x c xn n1 1 1 1 1� ��� � � . (24)
� x g xn n n� �( )1 , ÇËÏ ñâîäèòñÿ ê ñëåäóþùåé ÇËÏ ðàçìåðíîñòè n �1: íà òðàïå-
öîèäå T S S Sn n� �� �1 1 2 1. . . íàéòè maxF2 ôóíêöèè
F c x c x c g xn n n n n2 1 1 1 1 1� ��� �� � �( ). (25)
Òàêèì îáðàçîì, max max(max , max )F F F� 1 2 .
Ïîñêîëüêó íà Tn�1 g Xn n( )� �1 0, èìååì íåñêîëüêî ñëó÷àåâ:
a) cn
0: max(max , max ) max(max , ) maxF F F F g F1 2 1 1 1� � � , g � 0;
á) cn � 0: max(max , max max(max , ) max)F F F F F1 2 1 2 2� � , g � 0.
Èòàê, ÇËÏ ðàçìåðíîñòè n íà òðàïåöîèäå ñâîäèòñÿ ê çàäà÷å ðàçìåðíîñòè n �1 íà
òðàïåöîèäå çà âðåìÿ O n( ).
Ýòè ñîîòíîøåíèÿ ñëåäóåò äîïîëíèòü ÷àñòíûìè ñëó÷àÿìè, êîòîðûå îïðåäåëÿ-
þòñÿ òåì, ÷òî ñîðò ExtCoef — ðàñøèðåíèå ïîëÿ Coef ýëåìåíòàìè � Inf , � Inf. Åñëè
ñåãìåíò S èìååò âèä S x G xn n� � �[ , , ( )]Inf 1 , åãî íåëüçÿ ïðèâåñòè ê âèäó (23). Îäíà-
êî ïðè cn
0 maxF � � Inf. Ïðè cn � 0, ïî ñóùåñòâó, èìååò ìåñòî ñëó÷àé á) è ÇËÏ
ðåøàåòñÿ ôîðìóëîé (25). Àíàëîãè÷íî ðàññìàòðèâàåòñÿ ñëó÷àé, êîãäà íåîãðàíè÷åí-
íûé ñåãìåíò çàäàåòñÿ ôîðìóëîé S L x xn n� ��[ ( ), , ]1 Inf . Äëÿ ðåàëèçàöèè âû÷èñëå-
íèé â ýòèõ ñëó÷àÿõ îïðåäåëÿåòñÿ ñîðò ExtCoef. Âû÷èñëåíèÿ â àëãåáðå ExtCoef îïðå-
äåëÿþòñÿ ñëåäóþùèìè ñîîòíîøåíèÿìè:
a a�
� � �0 * ( )Inf Inf ,
a a� �
� � �0 * ( )Inf Inf ,
a a
� � �0 * ( )Inf Inf ,
a a
� � �0 * ( )Inf Inf ,
a � � � �Inf Inf ,
a � � � �Inf Inf ,
a � � � �Inf Inf ,
a � � � �Inf Inf .
182 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 2
Ñëåäîâàòåëüíî, ÇËÏ ðàçìåðíîñòè n ðåøàåòñÿ íà òðàïåöîèäå çà âðåìÿ O n( )2 .
Çàìå÷àíèå 3. Îïèñàííûé àëãîðèòì ðåøàåò ÇËÏ íà òðàïåöîèäå. Èç ôîðìóë
(27), (28) ñëåäóåò, ÷òî ìíîãîãðàííàÿ îáëàñòü ïðåäñòàâëÿåòñÿ â âèäå ðàçáèåíèÿ íà
òðàïåöîèäû, ïîýòîìó ÇËÏ ìîæåò áûòü ðåøåíà ýòèì ìåòîäîì íà ïðîèçâîëüíîé ìíî-
ãîãðàííîé îáëàñòè. �
4.3. Êàíîíè÷åñêèå ïðåäñòàâëåíèÿ ýëåìåíòîâ ñîðòà ConPol. Êàê óæå îòìå-
÷àëîñü, âûïóêëûé ìíîãîãðàííèê — ýëåìåíò ñîðòà ConPol, ïðåäñòàâèì â âèäå ðàç-
áèåíèÿ åãî íà òðàïåöîèäû. Òàêèì îáðàçîì,
P T T Tk� � � � � �� �1 2 . (26)
Íà ìíîæåñòâå òðàïåöîèäîâ åñòåñòâåííûì îáðàçîì ìîæåò áûòü çàäàíî îòíîøåíèå
ëèíåéíîãî ïîðÿäêà, èíäóöèðîâàííîå îòíîøåíèÿìè ïîðÿäêà íà ñîðòàõ Coef,
Variable è ðàñøèðåííîå ñíà÷àëà íà ñîðò Trapezoid , à çàòåì è íà ñîðò ConPol. Òà-
êèì îáðàçîì, ìîæíî ñ÷èòàòü, ÷òî T T Tk1 2� � �� , T S S Sj jn jn j� ��. . .1 1 .
Ïðèìåíÿÿ ñîîòíîøåíèÿ S O O. � , S I S. � , T O T� � � , O T T� � � , ìîæíî èçáà-
âèòüñÿ îò «ëèøíèõ» ñëàãàåìûõ è ñîìíîæèòåëåé. Òîãäà ýëåìåíò P ïðåäñòàâèì â êà-
íîíè÷åñêîé ôîðìå
P S
i
n
ji
j
k
�
��
��
11
, (27)
íàïðèìåð, P S S� 13 12. , S S S S S S S S S S11 23 22 21 33 32 31 43 42 41� � � � � �. . . . . . .
Òàêèì îáðàçîì, ñîðò ConPol — ëèíåéíîå äèíàìè÷åñêîå ðàñøèðåíèå ñîðòà
Trapezoid . Çäåñü ïðåäèêàòíûå ïåðåìåííûå S jk èíòåðïðåòèðîâàíû â àëãåáðå
VarSegment .
Ëåãêî ïîêàçàòü, ÷òî ìíîæåñòâî âûðàæåíèé òàêîãî âèäà óäîâëåòâîðÿåò âñåì
ñâîéñòâàì (àêñèîìàì) êîëüöà ìíîãî÷ëåíîâ Æåãàëêèíà â ñèãíàòóðå îïåðàöèé-îòìå-
òîê
� � �, , ,. O I , çà èñêëþ÷åíèåì ñâîéñòâà êîììóòàòèâíîñòè óìíîæåíèÿ. Ïîýòîìó
ìíîãîãðàííèêè ìîæíî íàçûâàòü ïîëèíîìàìè, òðàïåöîèäû — ìîíîìàìè, à ñåãìåí-
òû — ïåðåìåííûìè.
Çàìå÷àíèå 4. Ïåðåñòàíîâêà ñîìíîæèòåëåé â ïðîèçâåäåíèÿõ S S Sjn jn j. . .�1 1� —
ýòî çàäà÷à èçìåíåíèÿ ïîðÿäêà èíòåãðèðîâàíèÿ (ñì. çàìå÷àíèå 2). Ýòà çàäà÷à ïðåä-
ñòàâëÿåò ñàìîñòîÿòåëüíûé èíòåðåñ, ïðè÷åì íå òîëüêî äëÿ èíòåãðàëîâ ïî âûïóêëûì
ìíîãîãðàííèêàì, íî è äëÿ îáëàñòåé, çàäàííûõ ñèñòåìàìè âûïóêëûõ íåðàâåíñòâ. �
Ïîñêîëüêó â êîíñòðóêòèâíîé àëãåáðå ConPol èìååò ìåñòî çàêîí äèñòðèáóòèâíîñòè,
íàðÿäó ñ ïðåäñòàâëåíèåì ìíîãî÷ëåíà P â âèäå ñóììû ìîíîìîâ T j (26) ìîæíî îïðåäåëèòü
åùå îäíó êàíîíè÷åñêóþ ôîðìó — òàê íàçûâàåìîå ðåêóðñèâíîå ïðåäñòàâëåíèå P.
Èíäåêñîì (ðàçìåðíîñòè) ïåðåìåííîé — ýëåìåíòà S L y G� [ , , ] , íàçîâåì ïîðÿäêî-
âûé íîìåð ïåðåìåííîé y â ñîðòå Variable, èíäåêñîì ýëåìåíòà (ìîíîìà) T — èíäåêñ
åãî ñòàðøåãî ýëåìåíòà, íàêîíåö, èíäåêñîì ïîëèíîìà — èíäåêñ åãî ñòàðøåãî ìîíîìà.
Ïóñòü â (27) íåñêîëüêî ñëàãàåìûõ èìåþò âèä S T S Tk. ., ,1 � , ãäå S — ïåðåìåí-
íàÿ ìàêñèìàëüíîãî èíäåêñà. Òîãäà S ìîæíî âûíåñòè çà ñêîáêè. Îñóùåñòâèâ ýòî
ïðåîáðàçîâàíèå äëÿ âñåõ ïåðåìåííûõ S j ìàêñèìàëüíîãî èíäåêñà, èç (27) ïîëó÷èì
P S P S P S Pk k� � � � ��1 1 2 2. . . . (28)
 (28), èíäåêñû ïîëèíîìîâ Pj ìåíüøå èíäåêñîâ ïåðåìåííûõ S j . Ïðèìåíÿÿ ðå-
êóðñèâíî îïèñàííîå ïðåîáðàçîâàíèå êî âñåì ïîëèíîìàì âñå ìåíüøåãî èíäåêñà,
ïîëó÷àåì ðåêóðñèâíóþ êàíîíè÷åñêóþ ôîðìó ýëåìåíòà àëãåáðû ConPol, ðàññìàò-
ðèâàåìîãî êàê ìíîãî÷ëåí Æåãàëêèíà.
Ñëåäóþùåå ïðåîáðàçîâàíèå, îñíîâàííîå íà ñâîéñòâå ñëîæåíèÿ (11), íàçîâåì
ïðèâåäåíèåì ïîäîáíûõ. Ïóñòü P S P S P� � �1 1 2 1. . è S A x C1 � [ , , ] , S C x B2 � [ , , ] .
Òîãäà P A x B P� [ , , ] . 1. Òàêèì îáðàçîì, ïðèâåäåíèå ïîäîáíûõ îïèñûâàåòñÿ ðàâåíñòâîì
[ , , ] [ , , ] [ , , ]. . .A x C T C x B T A x B T� � � . (29)
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 2 183
Ðåêóðñèâíîé íîðìàëüíîé ôîðìîé (ÐÍÔ) ïîëèãîíà — ýëåìåíòà àëãåáðû ConPol,
áóäåì íàçûâàòü ôîðìó (28), â êîòîðîé ïðèâåäåíû âñå ïîäîáíûå ñëàãàåìûå ïî
ïðàâèëó (29). Ïîíÿòíî, ÷òî ÐÍÔ ïðåäñòàâëÿåò ïîëèãîí ýêîíîìíåå, ÷åì ïîëèíî-
ìèàëüíàÿ íîðìàëüíàÿ ôîðìà (ÏÍÔ) (27).
 çàêëþ÷åíèå îòìåòèì, ÷òî ìîæíî áûëî áû ðàññìàòðèâàòü è äðóãèå êàíîíè-
÷åñêèå ôîðìû ïðåäñòàâëåíèÿ ïîëèãîíîâ. Íàïðèìåð, èíòåðåñíî ïðåäñòàâëÿòü ïîëè-
ãîíû êàê ïåðåñå÷åíèÿ «íèæíèõ» è «âåðõíèõ» øàïîê. Âîçìîæíî, òàêîå ïðåäñòàâëå-
íèå áóäåò ýôôåêòèâíåå, ÷åì ÐÍÔ.
4.4. Èçîìîðôèçìû èíèöèàëüíîãî è êîíñòðóêòèâíîãî ïðåäñòàâëåíèé àë-
ãåáðû ÑËÍ. Àëãîðèòì ðåøåíèÿ ÑËÍ íà÷èíàåò ñâîþ ðàáîòó ñ ïðåîáðàçîâàíèé êàæ-
äîãî ëèíåéíîãî íåðàâåíñòâà ñèñòåìû â ýëåìåíòàðíûé ñåãìåíò (àòîì). Ñîîòâåòñòâó-
þùèå ïðàâèëà èìåþò âèä
� �( ) [ , , ] , ( ) [ , , ]y G y G y L L y� � � � � �Inf Inf . (30)
Ýòè ïðåîáðàçîâàíèÿ îïðåäåëÿþò èçîìîðôèçì àëãåáðû � : A Ainit constr
. Â ðå-
àëèçàöèè èìååò ñìûñë ñîâìåñòèòü ýòè ïðåîáðàçîâàíèÿ ñ âû÷èñëåíèÿìè õ-ðàçðåøåí-
íîé ôîðìû ËÍ.
Ïî ñóòè äåëà, ïîëèãîí P, ïðåäñòàâëåííûé â ÐÍÔ (28), îïèñûâàåò ðåøåíèå
ÑËÍ. Îäíàêî, åñëè íåîáõîäèìî ïðåäñòàâèòü òîëüêî îáîëî÷êó ðåøåíèÿ â n-ìåðíîì
ïðîñòðàíñòâå, èãíîðèðóÿ ïðîåêöèè â ïðîñòðàíñòâà ìåíüøåé ðàçìåðíîñòè, ýòî ìîæ-
íî ñäåëàòü ñ ïîìîùüþ îáðàòíîãî èçîìîðôèçìà �
�
1: A Aconstr init . Ñîîòâåòñòâóþ-
ùåå îñíîâíîå ïðàâèëî èìåþò âèä
� �
� �� � � � �1 1([ , , ] ) ( )&( )& ( ).L x G P Q x G x L Q . (31)
5. ÎÁÙÅÅ ÓÏÐÀÂËÅÍÈÅ È ÑËÎÆÍÎÑÒÜ ÂÛ×ÈÑËÅÍÈÉ
Ïî-âèäèìîìó, íàèáîëåå ïðîñòîé ïîäõîä ê óïðàâëåíèþ âû÷èñëåíèÿìè çàêëþ÷àåò-
ñÿ â ïîñëåäîâàòåëüíîì äîáàâëåíèè ê óæå ïîñòðîåííîé ÐÍÔ íîâîãî íåðàâåíñòâà
S P S S P S P& &( . .� � � � � �1 1 2 2
�� � � � ��S P S S P S S Pk k k k. . .) ( & ) ( & )1 1 . (32)
Èòàê, àëãîðèòì ïåðåâû÷èñëÿåò íåðàâåíñòâà, îïðåäåëÿþùèå òðàïåöîèä, çà âðåìÿ
O n( )2 . Ïóñòü C m n( , ) — êîëè÷åñòâî òðàïåöîèäîâ (ìîíîìîâ) â òåêóùåì ïðåäñòàâ-
ëåíèè (26). Òîãäà íà ïåðåâû÷èñëåíèå ïîëèíîìà (27) òðàòèòñÿ O n C m n( ( , ))2 øà-
ãîâ. Ïîñêîëüêó àëãîðèòì äîáàâëåíèÿ íåðàâåíñòâà ïîâòîðÿåòñÿ m ðàç,
T m n O mn C m n( , ) ( ( , ))� 2 . (33)
Íåòðóäíî ïîêàçàòü, ÷òî â ðàçáèåíèè ìíîãîãðàííîé îáëàñòè Ð íà òðàïåöîèäû
êàæäûé òðàïåöîèä ìîæíî àññîöèèðîâàòü, ïî êðàéíåé ìåðå, ñ îäíîé (ñâîåé) âåð-
øèíîé Ð. Èíà÷å òðàïåöîèä ìîæíî áûëî áû «ðàñøèðèòü», óâåëè÷èâ îäèí èç åãî
ñåãìåíòîâ. Ïîýòîìó êîëè÷åñòâî òðàïåöîèäîâ â Ð íå ïðåâîñõîäèò êîëè÷åñòâà V
åãî âåðøèí (0-ãðàíåé). Ïðè ýòîì íåîáõîäèìî ó÷èòûâàòü è áåñêîíå÷íî óäàëåííûå
âåðøèíû, îäíà èç êîîðäèíàò êîòîðûõ ðàâíà � Inf . Îäíàêî äàæå îäèí òðàïåöîèä,
êîòîðûé îïðåäåëÿåòñÿ 2n íåðàâåíñòâàìè (ïî äâå íà êàæäóþ ïåðåìåííóþ), ñîäåð-
æèò 2n âåðøèí, ïîýòîìó îöåíêó ìåòîäà
T m n O mn V m n( , ) ( ( , ))� 2 , (34)
â êîòîðîé V m n( , ) — êîëè÷åñòâî âåðøèí Ð [19], ñëåäóåò ñ÷èòàòü ýêñïîíåíöèàëüíîé.
184 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 2
6. ÑÏÅÖÈÔÈÊÀÖÈÈ ÑÎÐÒÀ CONPOL
Sort ExtCoef::LinOrdField;
Constructor {
ExtCoef a = Coef a | Const –Inf | Const +Inf;
};
// Îïðåäåëåíèÿ îïåðàöèé è îòíîøåíèé ïîðÿäêà íà êîíñòàíòàõ –Inf, +Inf
Operations
Mult:{
a > 0 - a*(+Inf = +Inf,
a > 0 - a*(-Inf = -Inf,
a < 0 - a*(+Inf = -Inf,
a < 0 - a*(-Inf = +Inf
};
...
};
Sort VarSegment::Interval;
Constructor {
VarSegment S = [LinComb L,Variable x, LinComb G];
// Cåëåêòîðû
LowGran(S) = L,
UpGran(S) = G,
Var(S) = x;
// Êîíòåêñòíûå óñëîâèÿ
L < = G,
x < LeadVar(L),
x < LeadVar(G);
// Ðåäóêöèè
[-Inf,x,+Inf] = I,
(a�Coef)&(b�Coef)&(ab)-> [a,x,b] = O; };
Signature
XCan(1):LinUnEqu -> VarSegment,
Intersection(2): ()&(),VarSegment^2->ConPol, ac;
Addition(2): ()+(),VarSegment^2->VarSegment, ac;
Operations
XCan{
L � R = LinCombCan(L-R),
L � R = LinCombCan(R-L),
a� 0 -> a = I,
a>0 -> a = O
};
// Ïðàâèëà, óíàñëåäîâàííûå îò ñîðòà Interval
Intersection{
S&O = O,
S&I = S
};
/
Ïåðåñå÷åíèå ïîëóîñåé. Îñíîâíîé ñëó÷àé. Äîïîëíèòåëüíûå ñëó÷àè: x y
èëè
x y� . Cëó÷àé x y
èëè x y� âûâîäèòñÿ èç îñíîâíîãî: x y S y I x S y�
�( ) ( ) ( ). .
Îïåðàöèÿ «� » äèñòðèáóòèâíà îòíîñèòåëüíî îïåðàöèè «&». Îíà óïîðÿäî÷èâàåò
cëàãàåìûå â ñóììå, âîçâðàùàÿ ñóììó ñî çíàêàìè «� � ».
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 2 185
/
Intersection{
GrEq(G,G1,T) -> S1.T&S = S1.T, //1
~Eq(G&G1,0,T)&GrEq(G,L1,T)->{S1.T&S=[L1,y,G1].T1+ [L1,y,G].T2,
where T1 = GrEq(G,G1,T), T2 = T-T1}, //2
~Eq(G&G1,0,T)&~Eq(G&L1,Empty,T)->{S1.T&S=[L1,y,G1].T1+[L1,y,G].T2,
where T1 = GrEq(G,G1,T), T2 = GrEq(G,G1,T) //3
GrEq(L1,G,T)&GrEq(G,G1,T) -> S1.T&S = [G,y,L1].T, //4
GrEq(L1,G,T)&~Eq(G&G1,0) -> {S1.T&S =[L1,y,G].T1,
where T1 = GrEq(G,L1,T), //5
GrEq(G,G1,T) -> S1.T & S = 0 //6
};
// Ïðèâåäåíèå ïîäîáíûõ
Addition{
[L,x,H] + [H,x,G] = [L,x,G]
};
Sort Trapezoid::ConSemyGroup;
Constructor {
Trapezoid T = (VarSegment S).(Trapezoid R);
// Cåëåêòîðû
Head(T) = S,
Tail(T) = R,
LeadVar(T) = Var(S);
// Êîíòåêñòíûå óñëîâèÿ
LowGran(S) <=R UpGran(S),
Var(S) > LeadVar(R);
// Ðåäóêöèè
T.I = T,
I.T = T,
T.O = O;
};
Signature
Intersection(2):,()&(),VarSegment*Traperzoid->ConPol, ac;
Addition(2): ()+(),Trapezoid^2->Trapezoid, ac;
Operations
Intersection{
// Îñíîâíîå ïðàâèëî
Var(S1) == Var(S) -> S1&S.T = (S1&S).T
// Äîïîëíèòåëüíûå ïðàâèëà âûâîäÿòñÿ èç îñíîâíîãî ñ èñïîëüçîâàíèåì ðåäóêöèé
};
// Äèñòðèáóòèâíûé çàêîí
Addition{
// Îñíîâíîå ïðàâèëî
S1.T + S2.T = (S1 + S2).T
};
Sort ConPol::GegalkinPolynomials;
Constructor {
ConPol P = (VarSegment S).(ConPol Q) ++ ConPol R;
// Cåëåêòîðû
Head(P) = T.Q,
Tail(P) = R,
186 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 2
LeadVar(P) = LeadVar(T);
// Êîíòåêñòíûå óñëîâèÿ
LeadVar(P) = LeadVar(R),
LeadVar(P) LeadVar(Q);
// Ðåäóêöèè
T.Q ++ O = T.Q,
O ++ P = P
};
Signature
Intersection(2):, ()&(),VarSegment*ConPol -> ConPol, ac;
Addition(2): ()+(),ConPol^2->ConPol, ac;
Operations
Intersection{
// Îñíîâíîå ïðàâèëî
Var(S1) = Var(S) - S1&(S.Q ++ R) = (S1&S).Q + S1&R,
// Äîïîëíèòåëüíûå ïðàâèëà âûâîäÿòñÿ èç îñíîâíîãî ñ èñïîëüçîâàíèåì ðåäóêöèé
};
// Äèñòðèáóòèâíûé çàêîí
Addition{
// Îñíîâíîå ïðàâèëî
(S1.Q ++ R1) + (S2.Q ++ R2) = (S1 + S2).Q ++ (R1 + R2)
// Äîïîëíèòåëüíûå ïðàâèëà ÄÇ ââîäÿòñÿ ñ ïîìîùüþ ñîîòíîøåíèé ðåäóêöèè
// Äîïîëíèòåëüíûå ïðàâèëà — ïðàâèëà ñëèÿíèÿ — óïîðÿäî÷èâàþò ñëàãàåìûå
Q1>Q2 -> (Q1++R1) + (Q2++R2) = Q1++(R1 + (Q2++R2),
Q1>Q2 -> (Q1++R1) + (Q2++R2)=Q2++(Q1++R1) + Q2),
// Îñòàëüíûå ïðàâèëà âûâîäÿòñÿ ñ ïîìîùüþ ñîîòíîøåíèé ðåäóêöèè
};
Àâòîð áëàãîäàðèò àêàäåìèêà À.À. Ëåòè÷åâñêîãî, êîòîðûé àêöåíòèðîâàë âíè-
ìàíèå íà çàäà÷å ïîñòðîåíèÿ àëãîðèòìà ðåøåíèÿ ÑËÍ ìåòîäàìè àëãåáðàè÷åñêîãî
ïðîãðàììèðîâàíèÿ è òåì ñàìûì èíèöèèðîâàë äàííóþ ðàáîòó.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. G o g u e n J . A . , T h a t c h e r J . W . , W a g n e r E . An initial algebra approach to the specification,
correctness and implementation of abstract data types. — Current trends in programming methodology
(R.Yeh ed.). — Englewood Cliffs; New York: Prentice Hall, 1978. — P. 80–149.
2. G o g u e n J . , M e s e g u e r J . Ordered-sorted algebra I: partial and overloaded operations. Errors and in-
heritance. — SRI International, Comput. Scie. Lab., 1987.
3. G o g u e n J . A . Parameterized programming // IEEE Transact. On Soft Engineering. — 1984. — SE-10,
N 5. — P. 528–543.
4. F u t a t s u g i K . , G o g u e n J . A . , J o u a n n a u d J . P . , M e s e g u e r J . Principles of OBJ-2 // Proc.
12th ACM Symposium on Principles of Program. Languages (B. Reid ed.). — 1985. — ACM. —
P. 52–66.
5. G o g u e n J . A . , M e s e g u e r J . Eqlog: equality, types and generic modules for logic programming //
Functional and Logic Programming / Ed. by D. DeGroot, G. Lindstrom. — New York: Prentice Hall, 1986.
— P. 295–363.
6. http://www.axiom-developer.org/
7. http://www.axiom-developer.org/axiom-website/bookvol10.2full.html
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 2 187
8. Ë ü â î â Ì . Ñ . Ñèíòåç ³íòåðïðåòàòîð³â àëãåáðà¿÷íèõ îïåðàö³é â ðîçøèðåííÿõ áàãàòîñîðòíèõ àëãåáð
// ³ñí. Õàðê³â. íàö. óí-òó. Ñåð. «Ìàòåìàòè÷íå ìîäåëþâàííÿ. ²íôîðìàö³éí³ òåõíîëî㳿. Àâòîìàòè-
çîâàí³ ñèñòåìè óïðàâë³ííÿ». — 2009. — ¹ 847. — Ñ. 221–238.
9. Ë ü â î â Ì . Ñ . Âåðèô³êàö³ÿ ³íòåðïðåòàòîð³â àëãåáðà¿÷íèõ îïåðàö³é â ðîçøèðåííÿõ áàãàòîñîðòíèõ
àëãåáð // Çá. íàóê. ïðàöü Õàðê³â. óí-òó Ïîâ³òðÿíèõ Ñèë. — Õàðê³â: ÕÓÏÑ, 2009. — Âèï. 3 (21). —
Ñ. 127–137.
10. Ë ü â î â Ì . Ñ . Ìåòîä ìîðô³çì³â ðåàë³çàö³¿ àëãåáðà¿÷íèõ îá÷èñëåíü â ìàòåìàòè÷íèõ ñèñòåìàõ íàâ-
÷àëüíîãî ïðèçíà÷åííÿ // Ñèñòåìè îáðîáêè ³íôîðìàö³¿. — 2009. — Âèï. 6(80). — Ñ. 183–190.
11. Ë ü â î â Ì . Ñ . Ìåòîä ñïàäêóâàííÿ ïðè ðåàë³çàö³¿ àëãåáðà¿÷íèõ îá÷èñëåíü â ìàòåìàòè÷íèõ ñèñòåìàõ
íàâ÷àëüíîãî ïðèçíà÷åííÿ // Ñèñòåìè óïðàâë³ííÿ, íàâ³ãàö³¿ òà çâ’ÿçêó. — 2009. — Âèï. 3 (11). —
Ñ. 120–130.
12. Ë ü â î â Ì . Îá îäíîì ïîäõîäå ê ðåàëèçàöèè àëãåáðàè÷åñêèõ âû÷èñëåíèé: âû÷èñëåíèÿ â àëãåáðå
âûñêàçûâàíèé // ³ñí. Õàðê³â. íàö. óí-òó. Ñåð. «Ìàòåìàòè÷íå ìîäåëþâàííÿ. ²íôîðìàö³éí³ òåõ-
íîëî㳿. Àâòîìàòèçîâàí³ ñèñòåìè óïðàâë³ííÿ». — 2009. — ¹ 848. — Ñ. 211–226.
13. Ì î ö ê è í Ò . Ñ . , Ð à é ô à Õ . , Ò î ì ï ñ î í Ä æ . Ë . , Ò ð î ë ë Ð . Ì . Ìåòîä äâîéíîãî îïèñàíèÿ.
Ìàòðè÷íûå èãðû. — Ì.: Ôèçìàòãèç, 1961. — Ñ. 81–109.
14. Z e i d l e r G . L . Lectures on polytopes. Graduate texts in mathematics. — New York: Springer-Verlag,
1994. — 370 p.
15. × å ð í è ê î â Ñ . Í . Ëèíåéíûå íåðàâåíñòâà. — Ì.: Íàóêà, 1968. — 490 c.
16. Ï ð å ï à ð à ò à Ô . , Ø å é ì î ñ Ì . Âû÷èñëèòåëüíàÿ ãåîìåòðèÿ: Ââåäåíèå. — Ì.: Ìèð, 1989. —
478 ñ.
17. Ë à ñ ë î Ì . Âû÷èñëèòåëüíàÿ ãåîìåòðèÿ è êîìïüþòåðíàÿ ãðàôèêà íà Ñ++ / Ïåð. ñ àíãë. — Ì.:
Áèíîì, 1997. — 304 ñ.
18. Ñ î ë î ä î â í è ê î â À . Ñ . Ñèñòåìû ëèíåéíûõ íåðàâåíñòâ. — Ì.: Íàóêà, 1977. — 112 ñ.
19. Å ì å ë è ÷ å â Â . À . , Ê î â à ë å â Ì . Ì . , Ê ð à â ö î â Ì . Ê . Ìíîãîãðàííèêè, ãðàôû, îïòèìèçàöèÿ.
— Ì.: Íàóêà, 1981. — 348 ñ.
Ïîñòóïèëà 13.07.2009
188 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 2
|
| id | nasplib_isofts_kiev_ua-123456789-45154 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0023-1274 |
| language | Russian |
| last_indexed | 2025-12-01T05:55:25Z |
| publishDate | 2010 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Львов, М.С. 2013-06-08T06:58:37Z 2013-06-08T06:58:37Z 2010 Алгебраический подход к задаче решения систем линейных неравенств / М.С. Львов // Кибернетика и системный анализ. — 2010. — № 2. — С. 175-188. — Бібліогр.: 19 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/45154 004.421.6 Викладено алгебраїчний підхід до побудови алгоритму розв’язання системи лінійних нерівностей. Суть цього підходу полягає у тому, що в термінах багатосортних алгебраїчних систем конструктивно визначається спеціальна алгебра Aconstr, у якій система лінійних нерівностей представлена як вираз. Розв’язання цієї системи полягає в обчисленні значення даного виразу як елемента алгебри Aconstr — канонічної форми системи лінійних нерівностей. Результат застосування цього підходу до задачі, яка розглядається, — алгебраїчні специфікації алгебри Aconstr. The paper outlines an algebraic approach to designing a solution algorithm for a system of linear inequalities. The approach implies that a special algebra Aconstr , where the system of linear inequalities (SLI) is presented as an expression is constructively defined in terms of multisorted algebraic systems. The SLI is solved by computing the value of this expression as an element of Aconstr algebra (canonical form expressions). The result of applying this approach is algebraic specifications of Aconstr . ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Программно-технические комплексы Алгебраический подход к задаче решения систем линейных неравенств Алгебраїчний підхід до задачі розв’язання систем лінійних нерівностей Algebraic approach to the problem of solving systems of linear inequalities Article published earlier |
| spellingShingle | Алгебраический подход к задаче решения систем линейных неравенств Львов, М.С. Программно-технические комплексы |
| title | Алгебраический подход к задаче решения систем линейных неравенств |
| title_alt | Алгебраїчний підхід до задачі розв’язання систем лінійних нерівностей Algebraic approach to the problem of solving systems of linear inequalities |
| title_full | Алгебраический подход к задаче решения систем линейных неравенств |
| title_fullStr | Алгебраический подход к задаче решения систем линейных неравенств |
| title_full_unstemmed | Алгебраический подход к задаче решения систем линейных неравенств |
| title_short | Алгебраический подход к задаче решения систем линейных неравенств |
| title_sort | алгебраический подход к задаче решения систем линейных неравенств |
| topic | Программно-технические комплексы |
| topic_facet | Программно-технические комплексы |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/45154 |
| work_keys_str_mv | AT lʹvovms algebraičeskiipodhodkzadačerešeniâsistemlineinyhneravenstv AT lʹvovms algebraíčniipídhíddozadačírozvâzannâsistemlíníinihnerívnostei AT lʹvovms algebraicapproachtotheproblemofsolvingsystemsoflinearinequalities |