Решение линейных условных полностью комбинаторных оптимизационных задач на перестановках методом ветвей и границ

Решение линейных условных полностью комбинаторных оптимизационных задач на перестановках методом ветвей и границ

Розглянуто умовну лінійну повністю комбінаторну задачу мінімізації на переставленнях. Запропоновано способи галуження, відсікання та оцінювання в методі гілок та меж для цієї задачі. Наведено ілюстративний приклад застосування методу до задачі. Доведено властивість запропонованої оцінки допустимої п...

Повний опис

Збережено в:
Бібліографічні деталі
Опубліковано в: :Кибернетика и системный анализ
Дата:2013
Автори: Емец, О.А., Емец, Е.М., Парфёнова, Т.А., Чиликина, Т.В.
Формат: Стаття
Мова:Russian
Опубліковано: Інститут кібернетики ім. В.М. Глушкова НАН України 2013
Теми:
Системный анализ
Онлайн доступ:https://nasplib.isofts.kiev.ua/handle/123456789/86221
Теги: Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:Решение линейных условных полностью комбинаторных оптимизационных задач на перестановках методом ветвей и границ / О.А. Емец, Е.М. Емец, Т.А. Парфёнова, Т.В. Чиликина // Кибернетика и системный анализ. — 2013. — Т. 49, № 2. — С. 121-138. — Бібліогр.: 18 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine
id nasplib_isofts_kiev_ua-123456789-86221
record_format dspace
spelling Емец, О.А.
Емец, Е.М.
Парфёнова, Т.А.
Чиликина, Т.В.
2015-09-09T18:07:31Z
2015-09-09T18:07:31Z
2013
Решение линейных условных полностью комбинаторных оптимизационных задач на перестановках методом ветвей и границ / О.А. Емец, Е.М. Емец, Т.А. Парфёнова, Т.В. Чиликина // Кибернетика и системный анализ. — 2013. — Т. 49, № 2. — С. 121-138. — Бібліогр.: 18 назв. — рос.
0023-1274
https://nasplib.isofts.kiev.ua/handle/123456789/86221
519.85
Розглянуто умовну лінійну повністю комбінаторну задачу мінімізації на переставленнях. Запропоновано способи галуження, відсікання та оцінювання в методі гілок та меж для цієї задачі. Наведено ілюстративний приклад застосування методу до задачі. Доведено властивість запропонованої оцінки допустимої підмножини, яка збільшує ефективність галужень та відсікань.
A conditional linear fully combinatorial minimization problem on permutations is analyzed. The methods of branching, cutting, and estimating in the branch and bound method are proposed for this problem. An illustrative example of applying the method to the problem is presented. The property of the proposed estimation of the feasible subset, which increases the efficiency of branching and cutting, is proved.
ru
Інститут кібернетики ім. В.М. Глушкова НАН України
Кибернетика и системный анализ
Системный анализ
Решение линейных условных полностью комбинаторных оптимизационных задач на перестановках методом ветвей и границ
Розв’язок лінійних умовних повністю комбінаторних оптимізаційних задач на переставленнях методом гілок та меж
Solving linear conditional fully combinatorial optimization problems on permutations by the branch and bound method
Article
published earlier
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection DSpace DC
title Решение линейных условных полностью комбинаторных оптимизационных задач на перестановках методом ветвей и границ
spellingShingle Решение линейных условных полностью комбинаторных оптимизационных задач на перестановках методом ветвей и границ
Емец, О.А.
Емец, Е.М.
Парфёнова, Т.А.
Чиликина, Т.В.
Системный анализ
title_short Решение линейных условных полностью комбинаторных оптимизационных задач на перестановках методом ветвей и границ
title_full Решение линейных условных полностью комбинаторных оптимизационных задач на перестановках методом ветвей и границ
title_fullStr Решение линейных условных полностью комбинаторных оптимизационных задач на перестановках методом ветвей и границ
title_full_unstemmed Решение линейных условных полностью комбинаторных оптимизационных задач на перестановках методом ветвей и границ
title_sort решение линейных условных полностью комбинаторных оптимизационных задач на перестановках методом ветвей и границ
author Емец, О.А.
Емец, Е.М.
Парфёнова, Т.А.
Чиликина, Т.В.
author_facet Емец, О.А.
Емец, Е.М.
Парфёнова, Т.А.
Чиликина, Т.В.
topic Системный анализ
topic_facet Системный анализ
publishDate 2013
language Russian
container_title Кибернетика и системный анализ
publisher Інститут кібернетики ім. В.М. Глушкова НАН України
format Article
title_alt Розв’язок лінійних умовних повністю комбінаторних оптимізаційних задач на переставленнях методом гілок та меж
Solving linear conditional fully combinatorial optimization problems on permutations by the branch and bound method
description Розглянуто умовну лінійну повністю комбінаторну задачу мінімізації на переставленнях. Запропоновано способи галуження, відсікання та оцінювання в методі гілок та меж для цієї задачі. Наведено ілюстративний приклад застосування методу до задачі. Доведено властивість запропонованої оцінки допустимої підмножини, яка збільшує ефективність галужень та відсікань. A conditional linear fully combinatorial minimization problem on permutations is analyzed. The methods of branching, cutting, and estimating in the branch and bound method are proposed for this problem. An illustrative example of applying the method to the problem is presented. The property of the proposed estimation of the feasible subset, which increases the efficiency of branching and cutting, is proved.
issn 0023-1274
url https://nasplib.isofts.kiev.ua/handle/123456789/86221
citation_txt Решение линейных условных полностью комбинаторных оптимизационных задач на перестановках методом ветвей и границ / О.А. Емец, Е.М. Емец, Т.А. Парфёнова, Т.В. Чиликина // Кибернетика и системный анализ. — 2013. — Т. 49, № 2. — С. 121-138. — Бібліогр.: 18 назв. — рос.
work_keys_str_mv AT emecoa rešenielineinyhuslovnyhpolnostʹûkombinatornyhoptimizacionnyhzadačnaperestanovkahmetodomvetveiigranic
AT emecem rešenielineinyhuslovnyhpolnostʹûkombinatornyhoptimizacionnyhzadačnaperestanovkahmetodomvetveiigranic
AT parfenovata rešenielineinyhuslovnyhpolnostʹûkombinatornyhoptimizacionnyhzadačnaperestanovkahmetodomvetveiigranic
AT čilikinatv rešenielineinyhuslovnyhpolnostʹûkombinatornyhoptimizacionnyhzadačnaperestanovkahmetodomvetveiigranic
AT emecoa rozvâzoklíníinihumovnihpovnístûkombínatornihoptimízacíinihzadačnaperestavlennâhmetodomgíloktamež
AT emecem rozvâzoklíníinihumovnihpovnístûkombínatornihoptimízacíinihzadačnaperestavlennâhmetodomgíloktamež
AT parfenovata rozvâzoklíníinihumovnihpovnístûkombínatornihoptimízacíinihzadačnaperestavlennâhmetodomgíloktamež
AT čilikinatv rozvâzoklíníinihumovnihpovnístûkombínatornihoptimízacíinihzadačnaperestavlennâhmetodomgíloktamež
AT emecoa solvinglinearconditionalfullycombinatorialoptimizationproblemsonpermutationsbythebranchandboundmethod
AT emecem solvinglinearconditionalfullycombinatorialoptimizationproblemsonpermutationsbythebranchandboundmethod
AT parfenovata solvinglinearconditionalfullycombinatorialoptimizationproblemsonpermutationsbythebranchandboundmethod
AT čilikinatv solvinglinearconditionalfullycombinatorialoptimizationproblemsonpermutationsbythebranchandboundmethod
first_indexed 2025-11-24T18:06:23Z
last_indexed 2025-11-24T18:06:23Z
_version_ 1850491802853834752
fulltext ÓÄÊ 519.85 Î.À. ÅÌÅÖ, Å.Ì. ÅÌÅÖ, Ò.À. ÏÀÐÔ¨ÍÎÂÀ, Ò.Â. ×ÈËÈÊÈÍÀ ÐÅØÅÍÈÅ ËÈÍÅÉÍÛÕ ÓÑËÎÂÍÛÕ ÏÎËÍÎÑÒÜÞ ÊÎÌÁÈÍÀÒÎÐÍÛÕ ÎÏÒÈÌÈÇÀÖÈÎÍÍÛÕ ÇÀÄÀ× ÍÀ ÏÅÐÅÑÒÀÍÎÂÊÀÕ ÌÅÒÎÄÎÌ ÂÅÒÂÅÉ È ÃÐÀÍÈÖ Êëþ÷åâûå ñëîâà: êîìáèíàòîðíàÿ îïòèìèçàöèÿ, ïåðåñòàíîâêè, ìåòîä âåòâåé è ãðàíèö. ÂÂÅÄÅÍÈÅ Ïîñëåäíèå äåñÿòèëåòèÿ áûñòðî ðàçâèâàþòñÿ òåîðèÿ è ìåòîäû äèñêðåòíîé è êîìáèíàòîðíîé îïòèìèçàöèè, ÷òî îáóñëîâëåíî íåîáõîäèìîñòüþ ïîëó÷åíèÿ ïðàêòè÷åñêèõ ðåçóëüòàòîâ (â ÷àñòíîñòè, [1–10]). Øèðîêèé êëàññ çàäà÷ åâêëè- äîâîé êîìáèíàòîðíîé îïòèìèçàöèè ñîñòàâëÿþò çàäà÷è óñëîâíîé ïîëíîñòüþ êîìáèíàòîðíîé îïòèìèçàöèè íà ïåðåñòàíîâêàõ. Äëÿ ýòèõ çàäà÷ è èõ îòäåëü- íûõ ïîñòàíîâîê [4–10] ïîëó÷èëè ðàçâèòèå êàê òî÷íûå, òàê è ïðèáëèæåííûå ìåòîäû. Ïðè ýòîì àëãîðèòì ìåòîäà âåòâåé è ãðàíèö èñïîëüçóåòñÿ êàê â ñõå- ìàõ òî÷íûõ ìåòîäîâ [11, 12], òàê è â ñõåìàõ ïîëó÷åíèÿ ïðèáëèæåííûõ ðåøå- íèé íàçâàííûõ çàäà÷ îïòèìèçàöèè íà ïåðåñòàíîâêàõ [13–16]. Öåëü íàñòîÿùåé ñòàòüè — ðàñøèðèòü äëÿ çàäà÷ ëèíåéíîé îïòèìèçàöèè íà ïåðåñòàíîâêàõ ìåòîäèêó îöåíèâàíèÿ äîïóñòèìûõ ìíîæåñòâ â ìåòîäå âåòâåé è ãðàíèö èç [11, 12] è îáîñíîâàòü ïîäõîä ê âåòâëåíèþ è îòñå÷åíèþ â ýòîì ìåòîäå äîïóñòèìûõ ïîäìíîæåñòâ â óñëîâíûõ ëèíåéíûõ ïîëíîñòüþ êîìáèíàòîðíûõ çàäà÷àõ îïòèìèçàöèè íà ïåðåñòàíîâêàõ. ÏÎÑÒÀÍÎÂÊÀ ÇÀÄÀ×È Ðàññìîòðèì óñëîâíóþ ëèíåéíóþ ïîëíîñòüþ êîìáèíàòîðíóþ çàäà÷ó ìèíèìèçà- öèè íà ïåðåñòàíîâêàõ [4], ò.å. çàäà÷ó íàõîæäåíèÿ ïàðû C x x( *), * : C x c x x R j j j k k ( ) min* � � � � 1 ; (1) x c x x R j j j k k * min� � � �arg 1 (2) ïðè óñëîâèÿõ a x bij j j k j � � � 1 , i= , l1 2� �� ; (3) a x bij j j k j � � � 1 , i l l m= +1, +2� �� ; (4) x x x E Gk kn� � � �( ) ( )1 � , (5) ãäå E Gkn ( ) — ìíîæåñòâî ïåðåñòàíîâîê èç äåéñòâèòåëüíûõ ýëåìåíòîâ ìóëü- òèìíîæåñòâà G g gk� � �{ }1 � , â êîòîðûõ n ýëåìåíòîâ ðàçíûå; a b cij j j, , — çàäàííûå äåéñòâèòåëüíûå ÷èñëà äëÿ âñåõ âîçìîæíûõ â çàäà÷å èíäåêñîâ i è j , à k, m, n — çàäàííûå íàòóðàëüíûå ïîñòîÿííûå, n k� , l — öåëàÿ êîíñòàíòà, 0 � �l m . ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 2 121 © Î.À. Åìåö, Å.Ì. Åìåö, Ò.À. Ïàðô¸íîâà, Ò.Â. ×èëèêèíà, 2013 Ðåøàÿ çàäà÷ó (1)–(5) ìåòîäîì âåòâåé è ãðàíèö (ÌÂÃ), íåîáõîäèìî äàâàòü îöåí- êó äîïóñòèìûõ ìíîæåñòâ Di , i , p� � �1 2 � , íà êîòîðûå ðàçáèòî ïîäìíîæåñòâî äî- ïóñòèìûõ ðåøåíèé D , ò.å. ìíîæåñòâ Di , èìåþùèõ ñëåäóþùèå ñâîéñòâà: D D D Dp1 2� � � �� ; (6) D i Ji p� � ; (7) D Di j� � �i j ; i j J p, � . (8) Çäåñü è äàëåå J , pp � � �{ }1 2 � îáîçíà÷èì ìíîæåñòâî ïåðâûõ p íàòóðàëüíûõ ÷èñåë. Âàæíî îïðåäåëèòü, êàêîå èç ïîäìíîæåñòâ Di óäîâëåòâîðÿåò (3)–(5) ïðè âû- áðàííîì âåòâëåíèè, ïîýòîìó óñëîâèå (7) ìîæåò ïðîâåðÿòüñÿ â ïðîöåññå âåòâëå- íèÿ èëè îòñå÷åíèÿ. Êàê èçâåñòíî [17, 18], â çàäà÷å íàõîæäåíèÿ ìåòîäîì âåòâåé è ãðàíèö F x F x x R k ( ) min ( )* � � , (9) x F x x R k * min ( )� � arg (10) ïðè óñëîâèè x D R k� � , (11) ãäå F x( ): R Rk F 1, îöåíêîé äëÿ ìíîæåñòâà Di ìîæåò áûòü ÷èñëî � i R� 1, êî- òîðîå èìååò ñâîéñòâî � i F x� ( ) �x Di , �i J p . ÂÅÒÂËÅÍÈÅ È ÎÖÅÍÈÂÀÍÈÅ Â ÌÂà ÄËß ËÈÍÅÉÍÎÉ ÓÑËÎÂÍÎÉ ÇÀÄÀ×È ÎÏÒÈÌÈÇÀÖÈÈ ÍÀ ÏÅÐÅÑÒÀÍÎÂÊÀÕ Ðàññìîòðèì ïîäõîä ê âåòâëåíèþ è îöåíèâàíèþ â ìåòîäå âåòâåé è ãðàíèö â çà- äà÷å (1)–(5).  óñëîâèè (5) x x xk� � �( )1 � ÿâëÿåòñÿ ïåðåñòàíîâêîé ÷èñåë (âîîá- ùå ãîâîðÿ, äåéñòâèòåëüíûõ) g gk1� �� . Ïóñòü, íå îãðàíè÷èâàÿ îáùíîñòè, g g gk1 2� � �� . (12) Ìíîæåñòâî D ïðåäñòàâëÿåò ìíîæåñòâî òî÷åê x R k� , êîòîðûå óäîâëåòâîðÿþò óñëîâèÿì (3)–(5). Ïîýòîìó â êà÷åñòâå Di , i Jk� , ìîæåì ðàññìîòðåòü ìíîæåñòâî D x x x R x g a x a g bt k k t ij j i t i j Jk � � � � � � � � � � � � � � � �( ) | ; \{ } 1 � � �� �i J l ; a x a g b i J Jij j i t j J i m l k � � � � � � ��� � � �\{ } \ , � � Jk , (13) åñëè îíî íå ïóñòîå. Î÷åâèäíî, ÷òî äëÿ Dt � è Ds � â ïðåäñòàâëåíèè (13) âûïîëíÿåòñÿ ñâîéñòâî (8), à D Dt t k � � � 1 � . Ìíîæåñòâî D i1 1� âèäà (13), åñëè îíî ñîäåðæèò ïî êðàéíåé ìåðå äâà ýëåìåíòà, ìîæíî ðàçâåòâèòü íà ïîäìíîæåñòâà D i t1 1 2� � , t Jk� �1: 122 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 2 D x x x R x g x g i t k k i t 1 1 2 1 1 2 1 � � � � � � � � � � � � � � �� ( ) | ,� , � �1 2� , t i� 1; a x a g a g b i Jij j i i i t i l j Jk � � � � � � � � � � 1 1 2 1 2\ { , } ; a x a g a g b i J Jij j i i i t i m l j Jk � � � � � � � �� � � � � � � 1 1 2 1 2 \ \ { , } . (14) Î÷åâèäíî, ÷òî äëÿ D i t1 1 2� � è D i s1 1 2� � â ïðåäñòàâëåíèè (14) âûïîëíÿåòñÿ ñâîéñòâî (8), à D D i t i t k 1 1 2 1 1 1 1 � � �� � � � . Íà ( )r �1 -ì óðîâíå, r k� �1 , àíàëîãè÷íîãî ðàçáèåíèÿ äîïóñòèìîãî ìíîæñòâà èìååì D x x x R x g j J i i i t k k i r r r r j j1 2 1 2 1 1� � � � � � � � � � � � � � � � � � ( ) | � �� ; x g r t� � � 1 , t i j� , i J j Jj k k� � ; a x a g b i Jij j j J i i j J i l k r j j r � � � � � �� � � \{� � � 1 � } ; a x a g b i J Jij j j J i i j J i m l k r j j r � � � � � �� � � � � � �\{ \ � � � 1 � } � . (15) Êðîìå òîãî, î÷åâèäíî, ÷òî ïðè r k� �1 (ò.å. íà k-ì óðîâíå ðàçáèåíèÿ) îáðàçó- þòñÿ èñêëþ÷èòåëüíî îäíîýëåìåíòíûå ìíîæåñòâà. Îòìåòèì, ÷òî ìóëüòèìíîæåñòâî C íàçûâàåòñÿ ðàçíîñòüþ ìóëüòèìíîæåñòâà A è åãî ïîäìóëüòèìíîæåñòâà B (îáîçíà÷àåì C A B� � , ãäå B A� ), åñëè îñíîâó S Ñ( ) ñîñòàâëÿåò S C x x A( ) |� �{ , åñëè k x k xA B( ) ( )� } ; ïðè ýòîì êðàòíîñòü ýëåìåíòà â ìóëüòèìíîæåñòâå C îïðåäåëÿåòñÿ êàê k x k x k xC A B( ) ( ) ( )� � . Òåîðåìà 1. Îöåíêîé � � � � i i ir r 1 2 1 2 � � ïîäìíîæåñòâà D i i ir r 1 2 1 2 � �� � � èç (15) â ìåòîäå âåò- âåé è ãðàíèö ìîæåò ñëóæèòü �r Jk ÷èñëî � � � � �i i i j j r r r j c g 1 2 1 2 1 � � � � � ïðè óñëîâèè, ÷òî ci � 0 , gi � 0 èëè ci � 0 , g j � 0 �i Jk , ãäå � � �c c� �1 2 ... �� c k� ; g g gk1 2� � �� , à ìóëüòèìíîæåñòâî G g gi i� { 1 2 , ..., , , ...,gir 0 0} èìå- åò k ýëåìåíòîâ: | |G k� , g Gj � �j Jk . Äîêàçàòåëüñòâî. Ñîãëàñíî îïðåäåëåíèþ îöåíêè ñëåäóåò ïîêàçàòü, ÷òî c g c x x x x D j r r j j r j j j k k i i i� � � � � � � �� � � � 1 1 1 1 2 1 2= ( )� � � . ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 2 123 Ïóñòü êîýôôèöèåíòû öåëåâîé ôóíêöèè óïîðÿäî÷åíû òàê: c c p� �1 � � �� � � � � c c p k� �1 � . Ïðè ïîñòðîåíèè ïîäìíîæåñòâî D i i ir r 1 2 1 2 � �� � � îïðåäåëÿåò ìóëüòèìíîæåñòâî GB ñîãëàñíî óñëîâèþ (15): G g gB i ir � � �{ } 1 � . Íàéäåì ñóììó ìóëüòèìíîæåñòâà GB è ìóëüòèìíîæåñòâà, ñîñòîÿùåãî èç s k r� � íóëåé. Ðåçóëüòàò (ñóììà) ñîâïàäàåò ñ çàäàííûì â òåîðåìå ìóëüòèìíîæåñòâîì G g gk� � �{ }1 � , ãäå, íå íàðóøàÿ îáù- íîñòè, ìîæíî ñ÷èòàòü, ÷òî èìååò ìåñòî óïîðÿäî÷åíèå g g gk1 2� � �� . Êàê èçâåñòíî [4, òåîðåìà 3.1], min ( )x E G j j j k j j k k j c x c g � � � � �� � � 1 1 , (16) ãäå E Gk� ( ) — ìíîæåñòâî ïåðåñòàíîâîê èç ýëåìåíòîâ ìóëüòèìíîæåñòâà G , à � — êîëè÷åñòâî ýëåìåíòîâ îñíîâû S G( ) ìóëüòèìíîæåñòâà G : � �| ( )|S G . Çà- ìåòèì, ÷òî ñóììà ÷àñòè íåîòðèöàòåëüíûõ ïî óñëîâèþ òåîðåìû ñëàãàåìûõ èç (16) ìåíüøå ñóììû âñåõ ñëàãàåìûõ: c g c g j jj j r j j k � � � � � �� 1 1 . (17) Îòìåòèì, ÷òî èç ôîðìóëû (16), êîòîðàÿ äàåò ìèíèìóì íà ìíîæåñòâå x E Gk� � ( ) öåëåâîé ôóíêöèè c xj j j k � � 1 , ñëåäóåò íåðàâåíñòâî c g c g c g c g c j j j j j j jj j k i j r i j r i j r k � � � � � � � � � � � � �� � � � 1 1 1 1 � j j gi j k � � 1 , (18) ïîñêîëüêó ïðàâàÿ åãî ÷àñòü ïðåäñòàâëÿåò çíà÷åíèå òîé æå öåëåâîé ôóíêöèè íà íåêîòîðîì âåêòîðå, íå îáÿçàòåëüíî ÿâëÿþùèìñÿ ìèíèìàëüþ (â ïîñëåäíåì ñëàãàåìîì äëÿ j r r k� � �1 2, , ..., ñîìíîæèòåëè gij ÿâëÿþòñÿ íóëÿìè èç G GB� , à { } { } { }c c c c c c k rk� � � �� � � � � � � � �1 1 1 � � � ; { }g g G Gi i Bk� � � � � � 1 � ). Î÷åâèäíî, c g c g j j j ji j k i j k � � � � � �� 1 1 , (19) ãäå { }g g G Gi i Bk� � � � � � 1 � , ïîñêîëüêó ïî óñëîâèþ òåîðåìû ñëàãàåìîå âèäà c gi i � 0 � � �i Jk r\ {� �1 � } , � � �j J i ik r\ { 1 � } , à â ëåâîé ÷àñòè (18) îíè íó- ëåâûå, âñå îñòàëüíûå ñëàãàåìûå â ïðàâîé è ëåâîé ÷àñòÿõ (19) ïîïàðíî îäèíà- êîâû. Äàëåå çàìåòèì, ÷òî c g c x j ji j k j j j k � � � � �� 1 1 �x D i i i r 1 2 1 2 � � � � � � ïî ïîñòðîåíèþ ìíîæåñòâà ñîãëàñíî (15). Èç (17)–(19) ñëåäóåò, ÷òî � � � � i i ir r 1 2 1 2 � � ïðåäñòàâëÿåò îöåíêó â ÌÂà ïîäìíîæåñòâà D i i ir r 1 2 1 2 � �� � � , ÷òî è òðåáîâàëîñü äîêàçàòü. Òåîðåìà 2. Îöåíêîé � � � � i i ir r 1 2 1 2 � � ìíîæåñòâà D i i ir r 1 2 1 2 � �� � � èç (15) â ìåòîäå âåòâåé è ãðàíèö ìîæåò áûòü �r Jk ÷èñëî c g j j r r i j r i i i� � � � � � � � 1 1 2 1 2 � � , (20) 124 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 2 åñëè âûïîëíÿþòñÿ óñëîâèÿ ci � 0 è g j � 0 èëè ñi � 0 è g j � 0 �i Jk \ \ {� �1� �� r } ; j J i ik r� � �\ { 1 � } . Äëÿ äîêàçàòåëüñòâà òåîðåìû èñïîëüçóåì ðàâåíñòâî (18) è íåðàâåíñòâî (19).  ðåçóëüòàòå ïîëó÷àåì � � � � i i i j j j k r r c x 1 2 1 2 1 � � � � � � � � �x x x Dk i i ir r( )1 1 2 1 2� � �� � � , ÷òî è òðå- áîâàëîñü äîêàçàòü. Ïóñòü G g g gB i i ir � � �{ } 1 2 , � (gij îïðåäåëåíû â (15)) è ~ G G GB� � � {~ , ~g g1 2 �� ... ~� gs}, ãäå s k r� � , ïðè ñëåäóþùåé íóìåðàöèè ýëåìåíòîâ â ìóëüòèìíîæåñòâå ~ G: ~ ~ ~g g gi i is1 2 � � �� . (21) Îáîçíà÷èì C c c ck� � �{ 1 2, }� , C c c cB r � � �{ }� � �1 2 , � , ~ C C CB� � �{~ , ~ ,...c ci i1 2 ... , ~cis }, ïðè÷åì, íå íàðóøàÿ îáùíîñòè, ìîæíî ñ÷èòàòü ~ ~ ~c c ci i i s1 2 � � �� . (22) Òåîðåìà 3. Îöåíêîé ìíîæåñòâà D i i ir r 1 2 1 2 � �� � � èç (15) â ìåòîäå âåòâåé è ãðàíèö ìîæåò áûòü âåëè÷èíà � � � � i i ir r 1 2 1 2 � � = � � � � i i i i i j s r r j j ñ g 1 2 1 2 1 � � � � � ~ ~ , (23) ãäå s k r� � ; ~ci j è ~gij óäîâëåòâîðÿþò óñëîâèÿì (22) è (21) ñîîòâåòñòâåííî, âåëè÷èíà � � � � i i ir r 1 2 1 2 � � âû÷èñëÿåòñÿ ïî ôîðìóëå (20). Çàìå÷àíèå ê òåîðåìå 3. Ïðè âû÷èñëåíèè âåëè÷èíû (20) äëÿ èñïîëüçîâàíèÿ â (23) íå îáÿçàòåëüíî âûïîëíåíèå óñëîâèÿ òåîðåìû 2: c gi j � 0 èëè ci � 0 , g j � 0 � � � �i J j J i ik r k r\ ( ); \ ( , ..., )� �1 1� . Äîêàçàòåëüñòâî òåîðåìû 3. Äëÿ äîêàçàòåëüñòâà òîãî, ÷òî âåëè÷èíà (23) ÿâ- ëÿåòñÿ îöåíêîé äëÿ D i i ir r 1 2 1 2 � �� � � , íóæíî äîêàçàòü ñëåäóþùåå: � � � � � � � i i i j j j k k i i ir r r c x x x D 1 2 1 2 1 2 1 2 1 1� � � � �� � � � � � ( ) r . (24) Ïîäñòàâèâ â (24) âûðàæåíèÿ èç (20) è (23), ïîëó÷èì ñ g ñ g ñ x j j j ji j r i i j s j j j k � � � � � � �� � 1 1 1 ~ ~ . (25) Èç ôîðìóë (15) èìååì x g j ji� � �j J r , �( , ..., )x x Dk i i ir r 1 1 2 1 2 � �� � � , ò.å. ïðàâàÿ ÷àñòü (25) ñîäåðæèò ïåðâóþ ñóììó èç ëåâîé ÷àñòè (25), ýòè ñóììû âçàèìíî óíè÷òîæàþòñÿ. Èç (25) â ðåçóëüòàòå ïîëó÷àåì íåðàâåíñòâî ~ ~ \{ ñ g ñ xi i j s j j j J j j k r� � � � � �� 1 1� �� } . (26) Êîîðäèíàòû x j èç (26), îáúåäèíåííûå â âåêòîð ~ ( , ..., )x x xj js � 1 , ÿâëÿþòñÿ íå- êîòîðîé ïåðåñòàíîâêîé ýëåìåíòîâ ìóëüòèìíîæåñòâà ~ G , ò.å. ~ ( ~ )x E G� , ãäå E G( ~ ) — ìíîæåñòâî âñåõ òàêèõ ïåðåñòàíîâîê. ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 2 125 Êàê èçâåñòíî [4], min ~ ~ ~ ( ~ ) \{ , ...,x E G j j j J i i j s ñ x ñ g k r j j � � � � �� � �1 1} , (27) ÷òî ñîãëàñíî îïðåäåëåíèþ ìèíèìóìà è äîêàçûâàåò íåðàâåíñòâî (26), à ñëåäî- âàòåëüíî, è (23). Òàêèì îáðàçîì, òåîðåìà äîêàçàíà. Çàìå÷àíèå. Îòìåòèì, ÷òî âåëè÷èíó (20) â âûðàæåíèè (23) ìîæíî îïðåäå- ëèòü ñëåäóþùèì îáðàçîì: � � � � � � � � �i i i i i i i r r r r r r c g 1 2 1 2 1 2 1 1 2 1 � � � �� � � � . ÍÎÂÛÅ ÏÐÀÂÈËÀ ÎÒÑÅ×ÅÍÈß Ðàññìîòðèì ïðåäëàãàåìóþ ìåòîäèêó îòñå÷åíèÿ. Èçâåñòíî, ÷òî îñíîâíûì ïðàâèëîì îòñå÷åíèÿ íåïóñòûõ ïîäìíîæåñòâ Di äî- ïóñòèìîãî ìíîæåñòâà D â ÌÂà (ñì., íàïðèìåð [17, 18]) ÿâëÿåòñÿ îòñå÷åíèå ïðè âûïîëíåíèè íåðàâåíñòâà � � � �F F F x x D0 0 0 0, ( ), , ãäå � —îöåíêà õàðàêòåðè- çóåìîãî ïîäìíîæåñòâà Di , êîòîðàÿ íå ìåíüøå òåêóùåãî ðåêîðäà ìèíèìàëüíîãî çíà÷åíèÿ öåëåâîé ôóíêöèè F0 . Ïóñòü çàäà÷à (1)–(5) èìååò îãðàíè÷åíèÿ âèäà � � � j i j k x j � � � 1 0 ; (28) � � � j i j k x j � � � 1 0 ; (29) � � � j i j k x j � � � 1 0 , (30) ãäå � j � 0, � j � 0, � j � 0 ; k k� � ; k k� � ; k k� � , è ðåøàåòñÿ ìåòîäîì âåòâåé è ãðàíèö, êîòîðûì îáðàçîâàíî ïîäìíîæåñòâî äîïóñòèìûõ ðåøåíèé D i i ir r 1 2 1 2 � �� � � . Ïóñòü òàêæå âûïîëíÿåòñÿ óñëîâèå (21), à òàêæå ñëåäóþùèå óñëîâèÿ: � � � � � � � �1 2 10� � � � � � ��� �s s k , s J k� � 0 , (31) � � � � � � �1 10� � � � � ��� �s s k , s J k� � 0 , (32) � � � � � � �1 0 1 � � � � � � � � �s s k , s � � J k 0 , (33) ãäå ìóëüòèìíîæåñòâà A k� {� � �1, ..., } è A k� � �{ }� � �1 � ; B k� � �{ }� � �1 � è B k� � �{ }� � �1 � ; �{ }� � �1� �� k è � � � �{ }� � �1 � k ïîïàðíî ðàâíû: A A� , B B� , � �� , à J J k k 0 0� �{ } . Òåîðåìà 4. Åñëè � � �0 � �[ ; ]min max � � � � � � � � � � � � � � � � � � � � j i j s s i j k s j i j s g g g j s r j s j ~ ~ ; ~ 1 1 1 1 � � � � � �� �� � � � � � � � � � � � s j i j j k s g r ~ 1 1 , (34) ãäå r k s� � �� � ; � �0 ! min ; (35) 126 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 2 èëè åñëè � � �0 � �[ ; ]min max � � � � � � � � � � � � � � � � � � � � j i j s s i j k s j i j s g g g j s r j s j ~ ~ ; ~ 1 1 1 1 � � � � � �� �� � � � � � � � � � � � s j i j j k s g r ~ 1 1 , (36) ãäå r k s� � �� � ; � �0 � max ; (37) èëè åñëè � � �0 � �[ ; ]min max � � � � � � �� �� � � � � � � � � � � �j i j s s j i j i j s s jg g g j s r j s j ~ ~ ; ~ 1 1 1 ~gi j j k s j k s r� � �� � � � � � � � �� � � � � � � 1 11 , (38) ãäå r k s� � �� � , òî ìíîæåñòâî D i i ir r 1 2 1 2 � �� � � ÿâëÿåòñÿ ïóñòûì. Äîêàçàòåëüñòâî. Äîêàçàòåëüñòâî ñëåäóåò èç òåîðåìû 3.1 èç [4], ñîãëàñíî êî- òîðîé íàõîäÿòñÿ ìèíèìóìû è ìàêñèìóìû ëåâûõ ÷àñòåé (28)–(30) ñîîòâåòñòâåííî íà ìíîæåñòâàõ ðàçìåùåíèé ïî k k k� � �, , ýëåìåíòîâ èç ìóëüòèìíîæåñòâà ~ {~ , ~ ~ }G g g gi i is � � � 1 2 � ïðè óñëîâèè (21) è óñëîâèÿõ (31)–(33). Ëåâûìè êîíöàìè â èíòåðâàëàõ, êîòîðûå ôèãóðèðóþò â (34), (36), (38), ÿâëÿþòñÿ íàéäåííûå òàêèì îáðàçîì ñîîòâåòñòâåííî ìèíèìóìû, à ïðàâûìè êîíöàìè ýòèõ èíòåðâàëîâ — ñîîòâåòñòâåííî ìàêñèìóìû. Âûïîëíåíèå îäíîãî èç óñëîâèé (35), (37), (38) îçíà÷àåò, ÷òî íè íà îäíîì èç íàáîðîâ ïåðåìåííûõ, åùå íå îïðåäåëåííûõ íà ìíîæåñòâå äîïóñòèìûõ ðåøåíèé D i i ir r 1 2 1 2 � �� � � , ñîîòâåòñòâóþùåå èç îãðàíè÷åíèé (28)–(30) íå âûïîëíÿåòñÿ, ò.å. D i i ir r 1 2 1 2 � �� � � � , ÷òî è òðåáîâàëîñü äîêàçàòü. Çàìå÷àíèå ê òåîðåìå 4. Åñëè ðàâåíñòâî (30) ïðåâðàùàåòñÿ â xi � � 0 , íåðà- âåíñòâî (29) — â xi � � 0 , à (28) — â xi � � 0 , òî ñëåäóåò ïðîâåðèòü ñóùåñòâîâà- íèå ýëåìåíòîâ x g Gi j� � ~ , óäîâëåòâîðÿþùèõ ñîîòâåòñòâóþùåìó îãðàíè÷åíèþ (28)–(30) â òàêîì ñëó÷àå. Òåîðåìà 4 îïðåäåëÿåò îäíî èç âîçìîæíûõ ïðàâèë îòñå÷åíèÿ âåðøèí (íàçî- âåì åãî ïðàâèëîì îòñå÷åíèÿ 1), î êîòîðûõ èçâåñòíî, ÷òî îíè íå ñîäåðæàò äîïóñòèìûõ ðåøåíèé. Ïðàâèëî îòñå÷åíèÿ 2. Åñëè ïðè ïðîâåðêå îãðàíè÷åíèé âèäà (28)–(30) äëÿ ïîä- ìíîæåñòâà D i i ir r 1 2 1 2 � �� � � ïåðåìåííîé x j âîçìîæíî ïðèíÿòü òîëüêî çíà÷åíèå g Gt � ~ , òîãäà ïîäìíîæåñòâî âåòâèòñÿ îäíîçíà÷íî äî D i i i t j r r 1 2 1 2 � �� � � . Âñå îñòàëüíûå åùå íå ðàñ- ñìîòðåííûå ïîäìíîæåñòâà D i i ir r 1 2 1 2 1 1� � � �� � � , ãäå � r rj i t� �� �1 1; îòñåêàþòñÿ êàê ïóñòûå. Ïðàâèëî îòñå÷åíèÿ 3. Åñëè ïðè ïðèìåíåíèè òåîðåìû 4 ïîëó÷åíî � �0 � min èëè � �0 � max , èëè � �0 � min , èëè � �0 � max , òî ýòî îçíà÷àåò, ÷òî ïîäìíîæåñòâî D i i ir r 1 2 1 2 � �� � � âåòâèòñÿ äî îäíîýëåìåíòíîãî ïîäìíîæåñòâà, â êîòîðîì íå íàéäåííûå åùå ïåðåìåííûå ïðèíèìàþò çíà÷åíèÿ, îïðåäåëÿåìûå ðàâåíñòâàìè, â êî- òîðûå ïðåîáðàçóþòñÿ îãðàíè÷åíèÿ (28)–(30) ñîîòâåòñòâåííî. Âñå îñòàëüíûå ïîäìíî- æåñòâà áîëåå íèçêèõ óðîâíåé, ÷åì óðîâåíü ìíîæåñòâà D i i ir r 1 2 1 2 � �� � � , êîòîðûå ÿâëÿþòñÿ åãî ïîäìíîæåñòâàìè è åùå íå ïðîàíàëèçèðîâàíû, îòñåêàþòñÿ êàê ïóñòûå. ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 2 127 ÑÂÎÉÑÒÂÎ ÎÖÅÍÊÈ ÏÎÄÌÍÎÆÅÑÒÂÀ  ÌÂÃ, ÓÂÅËÈ×ÈÂÀÞÙÅÉ ÝÔÔÅÊÒÈÂÍÎÑÒÜ ÂÅÒÂËÅÍÈß È ÎÒÑÅ×ÅÍÈÉ Êàê âèäíî èç ïðèìåðà è èëëþñòðàöèè (ñì. ðèñ. 1–3) åãî ðåøåíèÿ, îöåíêè äî- ïóñòèìîãî ïîäìíîæåñòâà óâåëè÷èâàþòñÿ (íå óìåíüøàþòñÿ) ïðè äâèæåíèè ïî ñõåìå âíèç íà îäíîì óðîâíå, êîòîðûé èìååòñÿ â îäíîì ïîäìíîæåñòâå, ëèáî âïðàâî èëè âïðàâî è âíèç: îò êîðíÿ äåðåâà D ê «ëèñòüÿì» ïî âåòâÿì. Ñëó÷àé- íî ëè ýòî äëÿ äàííîãî ïðèìåðà? Îêàçûâàåòñÿ, ÷òî íåò. Îá ýòîì ñâèäåòåëüñòâó- åò ñëåäóþùàÿ òåîðåìà. Òåîðåìà 5. Åñëè äëÿ ýëåìåíòîâ ìóëüòèìíîæåñòâà G âûïîëíÿåòñÿ óñëî- âèå (12), äëÿ êîýôôèöèåíòîâ öåëåâîé ôóíêöèè — óïîðÿäî÷åííîñòü c c c k� � �1 2 � � �� , (39) à äîïóñòèìûå ïîäìíîæåñòâà D i i iq r 1 2 1 2 � �� � � (q j ir�{ }, ), D i i i i ir r r r r r 1 2 1 1 2 1 � � � � � � � � � � � � � çàäà÷è (1)–(5) â ÌÂà îïðåäåëÿþòñÿ ñîãëàñíî (13)–(15), òî ìåæäó èõ îöåíêàìè ñóùåñ- òâóþò ñîîòíîøåíèÿ � � � � � � � � � � i i i i i i i ir r r r r r r r 1 2 1 2 1 2 1 1 2 1 � � � � � � � � � � � , r k� � � �r Jk 1 , � � J k 1 0 ; (40) � � � � � � � � � i i i i i i jr r r r r 1 2 1 2 1 2 1 1 2 1 � � � �� � � , r Jk� �1 , j i ir k� �{ }1, ..., . (41) Äîêàçàòåëüñòâî. Ñïðàâåäëèâîñòü òåîðåìû ñëåäóåò èç ôîðìóë âèäà (20), (23), (27), êîòîðûå ïðèìåíÿþòñÿ ê ëåâûì è ïðàâûì ÷àñòÿì ñîîòíîøå- íèé (40), (41). Çàìå÷àíèå. Òåîðåìà ïîçâîëÿåò íå ðàññìàòðèâàòü (îòñåêàòü) ïîäìíîæåñòâà, îöåíêè äëÿ êîòîðûõ íàõîäÿòñÿ â ïðàâûõ ÷àñòÿõ (40), (41), åñëè åñòü ïîäìíîæåñò- âî ñ îöåíêîé � � � � i i ir r F 1 2 1 2 0� � � . Ïðè ýòîì � �1, ..., r îïðåäåëÿþò â ñîîòâåòñòâèè ñ (39), à gij ïðè ôîðìèðîâàíèè ïîäìíîæåñòâ ñîãëàñíî (15) âûáèðàþò â ñîîòâåò- ñòâèè ñ ïîðÿäêîì (12), èñïîëüçóÿ äëÿ îïðåäåëåíèÿ î÷åðåäíîé êîîðäèíàòû èç G ýëåìåíò ñ íàèìåíüøèì (â ñîîòâåòñòâèè ñ (12)) âîçìîæíûì íîìåðîì. ÏÐÈËÎÆÅÍÈÅ Ïðèìåð. Íàéòè ìèíèìóì ôóíêöèè 2 4 51 2 4 5x x x x� � � ïðè ñëåäóþùèõ óñëîâèÿõ: 1) x x x1 2 42 7� � � � ; 2) x x x1 2 32 3 10� � � ; 3) x x x x1 3 4 52 2� � � � ; 4) ( , , , , ) ( )x x x x x E G1 2 3 4 5 55� , ãäå G � �{ }2 1 0 3 5, , , , . Ïðè âåòâëåíèè ìíîæåñòâà äîïóñòèìûõ ðåøåíèé èñïîëüçóåì òîò ïîðÿäîê ïåðå- ìåííûõ, êîòîðûé ñîîòâåòñòâóåò òàêîé óïîðÿäî÷åííîñòè êîýôôèöèåíòîâ öåëåâîé ôóíêöèè: c c c k� � �1 2 � � �� . Èìååì óïîðÿäî÷åííîñòü c c5 15 2� � � � c4 1� � � � � � �c c3 20 4. Ñëåäîâàòåëüíî, ïîðÿäîê îïðåäåëåíèÿ ïåðåìåííûõ â äåðåâå âûáåðåì òàê: x x x x x5 1 4 3 2, , , , , a ïîðÿäîê èñïîëüçîâàíèÿ ïîäõîäÿùèõ çíà÷åíèé ïåðåìåííûõ èç G îïðåäåëèì ñîãëàñíî (12), ò.å. g1 2� � ; g2 0� ; g3 1� ; g4 3� ; g5 5� . Ñëåäîâàòåëüíî, äëÿ ïåðâîé âåðøèíû äåðåâà x5 2� � ; îáðàçóåì D 1 5 ; ïîëó÷àåì ~ C � {2, 1, 0,� 4}, ~ G � {0, 1, 3, 5}. Îïðåäåëèì îöåíêó � 1 5 � " � � " �5 2 2 0( ) ( � " � " � � " �1 1 0 3 4 5( ) ) � � � � �10 1 20 29. Äåðåâî âåòâëåíèÿ ñ îöåíêàìè âåðøèí è çíà÷åíèÿìè öåëåâûõ ôóíêöèé ïðèâåäåíî íà ðèñ. 1–3. 128 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 2 Ïðîâåðèì äëÿ D 1 5 òåîðåìó 4. Èìååì îãðàíè÷åíèÿ: 1) x x x1 2 42 7� � � � ; 2) x x x1 2 32 3 10� � � ; 3) x x x1 3 42 0� � � . Äëÿ êàæäîãî èç íèõ ïðîâåðÿåì óñëîâèÿ òåîðåìû 4: 1) � min � � � � � � min ( ) ( , , ) ( ~ )x x x E G x x x 1 2 4 44 3 1 2 42 � " � " � � " � �2 0 1 1 4 5 19( ) , � max � � � � � � max ( ) ( , , ) ( ~ )x x x E G x x x 1 2 4 44 3 1 2 42 � " � " � � " �2 5 1 3 4 0 13( ) , � 0 7 19 13� � � �[ ; ]; � � �0 �[ ; ];min max 2) �min � � � � � � min ( ) ( , , ) ( ~ )x x x E G x x x 1 2 3 44 3 1 2 32 3 � " � " � � " � �3 0 1 1 2 5 9( ) , ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 2 129 Ðèñ. 1 � �0 10 9� � � �min ; ñëåäîâàòåëüíî, íåò îñíîâàíèé óòâåðæäàòü, ÷òî D 1 5 � ; 3) �max ( , , ) ( ~ ) max ( )� � � � " � " � " �x x x E G x x x 1 3 4 44 3 1 3 42 2 5 1 3 1 1�14, � �0 0 14� ! � max ; ñëåäîâàòåëüíî, íåò îñíîâàíèé ñ÷èòàòü, ÷òî D 1 5 � . Âåòâèì íà ïåðâîì óðîâíå «âãëóáü», ò.å. x1 0� , èìååì D 12 51 , ~ C �{1, 0, �4}, ~ G �{1, 3, 5}. Îïðåäåëÿåì îöåíêó � 12 51 5 2 2 0 1 1 0 3 4 5 29� " � � " � " � " � � " � �( ) ( ( ) ) . Îãðàíè÷åíèÿ ïðèîáðåòàþò ñëåäóþùèé âèä: 2 72 4x x� � � ; � � �2 3 102 3x x ; 2 03 4x x� � . Ïðèìåíÿåì òåîðåìó 4: � min ( , ) ( ~ ) min ( )� � � " � " � � �x x E G x x 2 4 33 2 2 2 1 1 5 32 4 ; � � !7 0� � min ; ñëåäîâàòåëüíî, � � �0 �[ ; ]min max ; D 12 51 � . 130 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 2 Ðèñ. 2 Âåòâèì íà âòîðîì óðîâíå «âøèðü», ò.å. x1 1� ; îáðàçóåì D 13 51 ; ~ C �{1, 0, �4}, ~ G �{0, 3, 5}. Îïðåäåëÿåì îöåíêó � 13 51 � � " � �5 2( ) 2 1 1 0 0 3" � " � " �( ( ) )� " � �4 5 28. Ïîëó÷àåì îãðàíè÷åíèÿ äëÿ D 13 51: 1 2 82 4) x x� � � ; 2) � � �2 3 02 3x x ; 3 2 13 4) x x� � � . Ïðèìåíÿåì òåîðåìó 4: � min ( , ) ( ~ ) min ( )� � � �x x E G x x 2 4 33 2 2 2 4 � " � " � �2 0 1 5 5 ; � �8 0� , � � �min min,� � !5 0 ; çíà÷èò, âûïîëíåíî óñëîâèå (38); ñëå- äîâàòåëüíî, D 13 51 � . Âåòâèì íà âòîðîì óðîâíå «âøèðü», çàäàâ x1 3� , îáðàçóåì D 14 51; ~ C �{1, 0, – 4}, ~ G �{0, 1, 5}. Îïðåäåëÿåì � 14 51 � � � " � " � " � � " � �10 2 3 1 0 0 1 4 5 24( ( ) ) . Äëÿ D 14 51 îãðàíè÷åíèÿ ïðèîáðåòàþò âèä: 1 2 102 4) x x� � � ; 2) � � �2 3 72 3x x ; 3 2 33 4) x x� � � . Ïðèìåíèì òåîðåìó 4: � min ( , ) ( ~ ) min ( ) ;� � � " � " � � �x x E G x x 2 4 33 2 2 2 0 1 5 52 4 � �0 10 5� � ! � �min ; ñëåäîâàòåëü- íî, ñîãëàñíî (38) D 14 51 � . Âåòâèì «âøèðü», çàäàâ x1 5� ; îáðàçóåì ïîñëåäíåå ìíîæåñòâî D 14 51 ýòîãî óðîâíÿ èç D 1 5 (ïîñêîëüêó âûáèðàåì g gk � �5 5); ~ { , , }C � �1 0 4 , ~ G � {0, 1, 3}. Îïðåäåëÿåì îöåíêó: � 15 51 10 2 5 1 0 0 1 4 3 12� � � " � " � " � � " � �( ( ) ) . Äëÿ D 15 51 îãðàíè÷å- íèÿ çàäà÷è ïðèîáðåòàþò âèä:1 2 122 4) x x� � � ; 2) � � �2 3 52 3x x ; 3) 2 53 4x x� � � . Ïðèìåíèì òåîðåìó 4: � min ( , ) ( ~ ) min ( )� � � " � " � � �x x E G x x 2 4 33 2 2 2 0 1 3 32 4 ; � 0 12� � ! ! � �3 � min . Ñëåäîâàòåëüíî, ñîãëàñíî (38) D 15 51 � . Âîçâðàùàåìñÿ íà ïåðâûé óðîâåíü è ïðîäîëæàåì åãî âåòâèòü «âøèðü», îáðà- çóÿ D 2 5 , ïîëîæèâ x g1 20� � . Îáðàçóåì ~ C �{2, 1, 0, �4}, ~ { , , , }G � �2 1 3 5 . Îïðåäå- ëÿåì îöåíêó: � 2 5 5 0 2 2� " � " � �( ( ) 1 1 0 3 4 5 23" � " � � " � �( ) ) . Äëÿ D 2 5 îãðàíè÷åíèÿ ïðèîáðåòàþò âèä: 1) x x x1 2 42 7� � � � ; 2 2 3 101 2 3) x x x� � � ; 3 2 21 3 4) x x x� � � . Ïðîâåðèì òåîðåìó 4: 1) � min ( , , ) ( ~ ) min ( ) ( )� � � � " � � " � �x x x E G x x x 1 2 4 44 3 1 2 42 2 2 1 1 ( )� " � �1 5 8 , � max ( , , ) ( ~ ) max ( )� � � � �x x x E G x x x 1 2 4 44 3 1 2 42 2 5 1 3 1 2 15" � " � � " � �( ) ( ) ; � � � �7 8 150� [ ; ] ; 2) �min ( , , ) ( ~ ) min ( ) (� � � � " � " � � �x x x E G x x x 1 2 3 44 3 1 2 32 3 3 1 1 3 2 5 4)" � � ; � �0 10� � min ; ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 2 131 Ðèñ. 3 3) �max ( , , ) ( ~ ) max ( )� � � � " � " � " �x x x E G x x x 1 3 4 44 3 1 3 42 2 5 1 3 1 1�14; � �0 2 14� ! � max . Ñëåäîâàòåëüíî, íè ïî îäíîìó îãðàíè÷åíèþ íåò îñíîâàíèé óòâåðæäàòü, ÷òî âåðøèíà D 2 5 � . Çíà÷èò, åå ìîæíî âåòâèòü. Âåòâèì «âãëóáü», îáðàçóåì D 21 51 , çàäàâ x1 2� � . Èìååì ~ C �{1, 0, �4}, ~ G �{1, 3, 5}. Íàéäåì � 21 51 0 2 2 1 1 0 3 4 5 23� � " � � " � " � � " � �( ) ( ( ) ) . Äëÿ ìíîæåñòâà äîïóñòèìûõ ðåøåíèé D 21 51 èìååì îãðàíè÷åíèÿ:1 2 52 4) x x� � � ; 2 2 3 122 3) � � �x x ; 3) 2 43 4x x� � . Ïðèìåíèì òåîðåìó 4, ÷òîáû îïðåäåëèòü âîç- ìîæíîñòü îòñå÷åíèÿ D 21 51 : � min ( , ) ( ~ ) min ( )� � � �x x E G x x 2 4 33 2 2 2 4 � " � � " � �2 1 1 5 3( ) ; � �0 5 3� � � �min . Ñëåäîâàòåëüíî, ñîãëàñíî òåîðåìå 4 (óñëîâèå (38)) D 21 51 îòñåêàåòñÿ êàê ïóñòîå ìíîæåñòâî. Îáðàçóåì D 23 51 , çàäàâ x1 1� . Ïîëó÷èì ~ C �{1, 0, �4}, ~ G �{�2, 3, 5}. Íàéäåì � 23 51 0 2 1 1 2 0 3 4 5 20� � " � " � � " � � " � �( ( ) ( ) ) . Äëÿ D 23 51 èìååì îãðàíè÷åíèÿ: 1 2 82 4) x x� � � ; 2 2 3 92 3) � � �x x ; 3) 2 13 4x x� � . Ïðîâåðÿåì âûïîëíåíèå òåîðåìû 4: 1) � min ( , ) ( ~ ) min ( ) ( ) ( )� � � " � � � " � � �x x E G x x 2 4 33 2 2 2 2 1 5 92 4 , � max ( , ) ( ~ ) max ( ) ( ) ( )� � � " � � " � � �x x E G x x 2 4 33 2 2 2 5 1 2 122 4 , � � �0 8 9 12� � � � �[ ; ] [ ; ]min max ; 2) �min ( , ) ( ~ ) min ( ) ( ) ( )� � � � " � � � " � � �x x E G x x 2 3 33 2 2 3 3 2 2 52 3 16 , � �0 9 16� � � �min ; 3) �max ( , ) ( ~ ) max ( )� � � " � " � �x x E G x x 3 4 33 2 2 2 5 1 3 133 4 , � �0 1 13� ! �max . Ñëåäîâàòåëüíî, íåò îñíîâàíèé óòâåðæäàòü, ÷òî D 23 51 îòñåêàåòñÿ. Îáðàçóåì D 231 514 , çàäàâ x4 2� � . Èìååì ~ { , }C � �0 4 , ~ G �{3, 5}. Íàéäåì � 231 514 2 1 2 0 3 4 5 20� � " � � " � � " � �( ) ( ( ) ) . Îãðàíè÷åíèÿ äëÿ D 231 514 ïðèîáðåòàþò âèä: 1) 2 102x � � ; 2 2 3 92 3) � � �x x ; 3) 2 33x � . Îãðàíè÷åíèå 1 îçíà÷àåò, ÷òî x G2 5� � � ~ , ò.å. D 231 514 � . Çàäàâ x4 3� , îáðàçóåì D 234 514 ; ïîëó÷èì ~ { , }C � �0 4 , ~ { , }G � �2 5 . Îïðåäåëèì � 234 514 2 1 3 0 2 4 5 15� � " � " � � � " � �( ( ) ( ) ) . Îãðàíè÷åíèÿ äëÿ D 234 514 èìåþò âèä: 1 2 52) x � � ; x G2 5 2 � � � ~ ; ñëåäîâàòåëüíî, D 234 514 � . Çàäàâ x4 5� , îáðàçóåì D 235 514 ; ïîëó÷èì ~ C �{0, – 4}, ~ { , }G � �2 3 . Íàéäåì � 235 514 1� � . Îãðàíè÷åíèÿ äëÿ ïîäìíîæåñòâà èìåþò âèä: 1) 2 32x � � ; x G2 3 2 � � � ~ ; ñëåäîâàòåëüíî, D 235 514 � . Âîçâðàùàåìñÿ íà âòîðîé óðîâåíü, çàäàâ x1 3� ; îáðàçóåì D 24 51 ; ïîëó÷àåì ~ C �{1, 0, �4}, ~ G � {–2, 1, 5}. Íàéäåì � 24 51 16� � . 132 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 2 Îáðàçóåì îãðàíè÷åíèÿ äëÿ D 24 51 : 1) 2 102 4x x� � � ; 2) � � �2 3 72 3x x ; 3 2 13 4) x x� � � . Ïðèìåíèì ê íèì ïðàâèëî îòñå÷åíèÿ 1 (òåîðåìó 4): � min ( , ) ( ~ ) min ( ) ( ) ( )� � � " � � � " � � �x x E G x x 2 4 33 2 2 2 2 1 5 92 4 , � max ( , ) ( ~ ) max ( )� � � �x x E G x x 2 4 33 2 2 2 4 2 5 1 2 12" � � " � �( ) ( ) , � � �0 �[ ; ]min max ; ñëåäîâàòåëüíî, ïî ïðàâèëó 1 âåðøèíà D 24 51 îòñåêàåòñÿ, ïîñêîëüêó îíà ïóñòà. Çàäàâ x1 5� , îáðàçóåì D 25 51 ; ïîëó÷àåì ~ C �{1, 0, �4}, ~ G �{2, 1, 3}. Íàõîäèì � 25 51 0 2 5 1 2 0 1 4 3 4� � " � " � � " � � " � �( ( ) ( ) ) . Îãðàíè÷åíèÿ äëÿ D 25 51 ïðèíèìàþò âèä: 1) 2 122 4x x� � � ; 2) � � �2 3 52 3x x ; 3) 2 33 4x x� � � . Ïðèìåíèì òåîðåìó 4: 1) min� � min ( ) ( , ) ( ~ )x x E G x x 2 4 33 2 2 2 4 � � � 2 2 1 3 7" � � � " � �( ) ( ) ; � �0 12 7� � ! � � min ; ñëå- äîâàòåëüíî, âûïîëíÿåòñÿ óñëîâèå (38) è D 25 51 � . Âîçâðàùàåìñÿ íà ïåðâûé óðîâåíü, çàäàâ x5 1� ; îáðàçóåì D 3 5 ; ïîëó÷àåì ~ C �{2, 1, 0, �4}, ~ { , , , }G � �2 0 3 5 , � 3 5 19� � . Îãðàíè÷åíèÿ äëÿ D 3 5 òàêîâû: 1 2 71 2 4) x x x� � � � ; 2) x x x1 2 32 3 10� � � ; 3 2 31 3 4) x x x� � � . Ïðèìåíèì òåîðåìó 4: 1) � min ( , , ) ( ~ ) min ( ) ( )� � � � " � � " � �x x x E G x x x 1 2 4 44 3 1 2 42 2 2 1 0 1 5 9" � � , � max ( , , ) ( ~ ) max ( ) (� � � � " � " � � �x x x E G x x x 1 2 4 44 3 1 2 42 2 5 1 3 1) ( )" � �2 15 , � � �0 7 9 15� � � � �[ ; ] [ ; ]min max ; 2) �min ( , , ) ( ~ ) min ( ) ( )� � � � " � � " �x x x E G x x x 1 2 3 44 3 1 2 32 3 3 2 1 0� " � �2 5 16 , � �0 10 16� � � �min ; 3) �max ( , , ) ( ~ ) max ( )� � � � " � " � " �x x x E G x x x 1 3 4 44 3 1 3 42 2 5 1 3 1 0 �13; � �0 3 13� ! � max . Ñëåäîâàòåëüíî, íåò îñíîâàíèé óòâåðæäàòü, ÷òî âåðøèíà D 3 5 � . Âåòâèì ìíîæåñòâî, çàäàâ x1 2� � ; îáðàçîâàëîñü ìíîæåñòâî D 31 51 ; ïîëó÷àåì ~ C �{1, 0, �4}, ~ G �{0, 3, 5}. Îöåíêà � 31 51 5 2 2 1 0 0 3 4 5 19� � " � � " � " � � " � �( ) ( ( ) ) . Îãðàíè÷åíèå äëÿ D 31 51 : 1) 2 52 4x x� � � ; 2 2 3 122 3) � � �x x ; 3) 2 53 4x x� � . Ïðèìåíèì ê íèì òåîðåìó 4: 1) � min ( , ) ( ~ ) min ( )� � � " � " � � �x x E G x x 2 4 33 2 2 2 0 4 5 202 4 , � max ( , ) ( ~ ) max ( )� � � " � " � �x x E G x x 2 4 33 2 2 2 5 1 0 102 4 ; � 0 5 20 10� � � �[ ; ] ; 2) �min ( , ) ( ~ ) min ( )� � � � " � " � � �x x E G x x 2 3 33 2 2 3 3 0 2 5 102 3 ; � �0 12 10� � � �min ; 3) �max ( , ) ( ~ ) max ( )� � � " � " � �x x E G x x 3 4 33 2 2 2 5 1 3 133 4 ; � �0 5 13� ! �max . ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 2 133 Íåò îñíîâàíèé óòâåðæäàòü, ÷òî ìíîæåñòâî D 31 51 � . Âåòâèì ìíîæåñòâî, çàäàâ x4 0� ; ïîëó÷èì D 312 514 , ~ { , }C � �0 4 , ~ G �{3, 5}; íàõî- äèì � 312 514 19� � . Îãðàíè÷åíèÿ: 1) 2 52x � � ; x G2 5 2 � � � ~ ; ñëåäîâàòåëüíî, D 312 514 � . Îáðàçóåì ìíîæåñòâî D 314 514 , çàäàâ x4 3� , ~ { , }C � �0 4 , ~ G �{0, 5}; îöåíêà � 314 514 16� � . Ïðîâåðèì îãðàíè÷åíèÿ âèäà: 1) 2 22x � � ; x G2 1� � � ~ ; ñëåäîâàòåëü- íî, D 314 514 � . Îáðàçóåì ìíîæåñòâî D 315 514 , çàäàâ x4 5� ; ïîëó÷àåì ~ { , }C � �0 4 , ~ { , }G � 0 3 ; îöåíêà � 315 514 6� � . Îãðàíè÷åíèÿ: 1) 2 02x � ; x2 0� ; ÷èñëî 0� ~ G ; ñëåäîâàòåëüíî, x3 3� (ïî ïðàâèëó îòñå÷åíèÿ 3); îáðàçîâàëîñü ìíîæåñòâî D 31542 51432 , à D 3152 5143 � . Îöåíêà: � 31542 51432 6 3 0 4 0 6� � " � " � . Ïðîâåðèì îãðàíè÷åíèÿ 2 è 3 â îáðàçîâàííîì ìíîæåñòâå: 2) 0 3 3 12� " ! — âûïîëíÿåòñÿ; 3) 2 3 5 5" � � — âûïîëíÿåòñÿ. Ñëåäîâà- òåëüíî, ïîëó÷åíî äîïóñòèìîå ðåøåíèå x 0 2 0 3 5 1� �( ; ; ; ); ; F0 6� . Êðîìå D 3 5 , íåðàçâåòâëåííûõ âåðøèí íåò; åå íóæíî âåòâèòü äàëüøå. Îáðàçóåì ìíîæåñòâî D 32 51 , ïðèíÿâ x1 0� ; ïîëó÷àåì ~ C �{1, 0, �4}, ~ { , , }G � �2 3 5 . Íàõîäèì � 32 51 5 1 2 0 1 2 0 3 4 5 17� " � " � " � � " � � " � �( ( ) ( ) ) ; � 32 51 0! F ; ñëåäîâàòåëüíî, D 32 51 ìîæåì âåòâèòü. Ïðîâåðèì, ÷òî ìíîæåñòâî D 32 51 � ñîãëàñíî òåîðåìå 4. Ïðîàíàëèçèðóåì äëÿ ýòîãî ìíîæåñòâà îãðàíè÷åíèÿ çàäà÷è, êîòîðûå ïðèìóò âèä: 1) 2 72 4x x� � � ; 2) � � �2 3 102 3x x ; 3) 2 33 4x x� � . Ïîäñ÷èòàåì ïàðàìåòðû: 1) � min ( , ) ( ~ ) min ( ) ( )� � � " � � " � � �x x E G x x 2 4 33 2 2 2 2 1 5 92 4 , � max ( , ) ( ~ ) max ( ) ( ) ( )� � � " � � " � � �x x E G x x 2 4 33 2 2 2 5 1 2 122 4 , � 0 7 9 12� � � �[ ; ] ; 2) �min ( , ) ( ~ ) min ( ) ( )� � � � " � � " � � �x x E G x x 2 3 33 2 2 3 3 2 2 5 162 3 , � �0 10 16� � � �min ; 3) �max ( , ) ( ~ ) max ( )� � � " � " � �x x E G x x 3 4 33 2 2 2 5 1 3 133 4 , � �0 3 13� ! � max . Ñëåäîâàòåëüíî, íåò îñíîâàíèé ñ÷èòàòü D 32 51 � . Ñäåëàåì âåòâëåíèå D 32 51 , çàäàâ x4 2� � è îáðàçîâàâ D 321 514 ; ïîëó÷àåì ~ { , }C � �0 4 , ~ G �{3, 5}. Îöåíêà � 321 514 05 1 2 0 3 4 5 17� � " � � " � � " � � !( ) ( ( ) ) F ; îãðà- íè÷åíèÿ ïðèìóò âèä äëÿ ìíîæåñòâà D 321 514 : 1 2 92) x � � ; x G2 9 2 � � � ~ ; ñëåäîâà- òåëüíî, D 321 514 � . Îáðàçóåì ìíîæåñòâî D 324 514 , ïîëîæèâ x4 3� ; ïîëó÷àåì ~ { , }C � �0 4 , ~ G �{2, 5}. Ïîäñ÷èòàåì îöåíêó: � 324 514 05 3 0 2 4 5 12� � � " � � � " � � !( ( ) ( ) ) F . Ïðîâåðèì âûïîë- íåíèå îãðàíè÷åíèé, êîòîðûå ïðèîáðåòàþò âèä: 1) 2 42x � � ; x G2 2� � � ~ , çíà÷èò, x3 5� . Îáðàçîâàíî ïî ïðàâèëó 3 ìíîæåñòâî D 32451 51432( )D 3241 5143 � . Âû÷èñ- ëèì � 32451 51432 08 0 5 4 2 16� � " � � " � � �( ) ( ) F . Ïðîâåðèì â D 32451 51432 îãðàíè÷åíèÿ 2 è 3. 134 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 2 Îãðàíè÷åíèå 2 íå âûïîëíèëîñü; ñëåäîâàòåëüíî, D 32451 51432 � . Ïîëîæèì x4 5� , îáðàçîâàâ D 325 514 ; ~ { , }C � �0 4 , ~ G �{2, 3}. Ðàññ÷èòàåì îöåíêó � 325 514 05 3 0 2 4 3 4� � � " � � � " � � !( ( ) ( ) ) F . Ðàññìîòðèì íà D 325 514 îãðàíè÷åíèÿ: 1 2 22) x � � ; x G2 1� � � ~ . Ñëåäîâàòåëüíî, D 325 514 � . Âîçâðàòèìñÿ íà âòîðîé óðîâåíü, ïîëîæèì x1 3� è îáðàçóåì D 34 51 ; ïîëó÷àåì ~ C �{1, 0, �4}, ~ { ; , }G � �2 0 5 ; íàéäåì � 34 51 011� � ! F . Àíàëèçèðóåì îãðàíè÷åíèÿ â âèäå: 1) 2 102 4x x� � � ; 2 2 3 72 3) � � �x x ; 3) 2 03 4x x� � . Ïðèìåíèì òåîðåìó 4: 1) � min ( , ) ( ~ ) min ( ) ( )� � � " � � " � � �x x E G x x 2 4 33 2 2 2 2 1 5 92 4 , � max ( , ) ( ~ ) max ( ) ( ) ( )� � � " � � " � � �x x E G x x 2 4 33 2 2 2 5 1 2 122 4 , � � �0 10 9 12� � � � �[ ; ] [ ; ]min max ; D 34 51 � . Îáðàçóåì ìíîæåñòâî D 35 51, ïîëîæèâ x1 5� . Èìååì ~ C �{1, 0, �4}, ~ G �{2, 0, 3}. Ðàññ÷èòàåì îöåíêó ìíîæåñòâà D 35 51 : � 35 51 05 2 5 1 2 0 0 4 3 1� � " � " � � " � � " � !( ( ) ( ) ) F . Ñëåäîâàòåëüíî, åñëè ïîçâîëÿò îãðàíè÷åíèÿ, ìîæíî ïðîäîëæàòü âåòâèòü ìíîæå- ñòâî D 35 51 . Ïðîâåðèì âûïîëíåíèå îãðàíè÷åíèé, êîòîðûå ïðèîáðåòàþò âèä: 1 2 122 4) x x� � � ; 2) � � �2 3 52 3x x ; 3) 2 23 4x x� � � . Âû÷èñëèì � min ( , ) ( ~ ) min ( ) ( )� � � " � � " � � �x x E G x x 2 4 33 2 2 2 2 1 3 72 4 , � �0 12 7� � ! � � min ; ñëåäîâà- òåëüíî, D 35 51 � ñîãëàñíî òåîðåìå 4. Âòîðîé óðîâåíü ìíîæåñòâà D 35 51 èñ÷åðïàí, âîçâðàùàåìñÿ íà ïåðâûé, ãäå, çà- äàâ x5 3� , ñîçäàåì ìíîæåñòâî D 4 5 ; ïîëó÷àåì ~ C �{2, 1, 0, �4}, ~ { , , , }G � �2 0 1 5 . Íàéäåì äëÿ D 4 5 îöåíêó � 4 5 05 3 2 2 1 0 1 0 4 5 9� " � " � � " � " � � " � � !( ( ) ( ) ) F , ÷òî ïîçâî- ëèò ïîñëå ïðîâåðêè òåîðåìû 4 äàëüøå âåòâèòü D 4 5 . Îãðàíè÷åíèÿ ïðèìóò âèä: 1 2 71 2 4) x x x� � � � ; 2) x x x1 2 32 3 10� � � ; 3) x x x1 3 42 5� � � . Âû÷èñëèì: 1) � min ( , ) ( ~ ) min ( ) ( ) , � � � � " � � " � �x x x E G x x x 1 2 4 44 3 1 2 42 2 2 1 0 4 5 24" � � ; � max ( , , ) ( ~ ) max ( ) (� � � � " � " � � �x x x E G x x x 1 2 4 44 3 1 2 42 2 5 1 1 4) ( )" � �2 19 ; � 0 7 24 19� � � �[ ; ] ; 2) �min ( , , ) ( ~ ) min ( ) ( )� � � � " � � " �x x x E G x x x 1 2 3 44 3 1 2 32 3 3 2 1 0� " � �2 5 16 ; � �0 10 16� � � � min ; 3) �max ( , , ) ( ~ ) max ( )� � � � " � " � " �x x x E G x x x 1 3 4 44 3 1 3 42 2 5 1 1 1 0 �11; � �0 5 11� ! � max . Ñëåäîâàòåëüíî, íåò îñíîâàíèé óòâåðæäàòü, ÷òî âåðøèíà D 4 5 � . Ïðîäîëæàåì âåòâèòü åå, çàäàâ x1 2� � è ïîëó÷èâ D 41 51 . Íàõîäèì ~ C �{1, 0, �4}, ~ G �{0, 1, 5}, � 41 51 09� � ! F . Àíàëèçèðóåì ïîëó÷àåìûå îãðàíè÷åíèÿ: 1) 2 52 4x x� � � ; 2 2 3 122 3) � � �x x ; 3) 2 73 4x x� � . Íàéäåì � min ( , ) ( ~ ) min ( )� � � �x x E G x x 2 4 33 2 2 2 4 � " � " � �2 0 1 5 5 ; ïî ïðàâèëó 3 x2 0� ; x4 5� ; ñëåäîâàòåëüíî, x3 1� , ò.å. îáðàçîâàíî ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 2 135 ìíîæåñòâî D 41532 51432 (D 412 514 � , D 413 514 � , D 4152 5143 � ). Îöåíêà ýòîãî ìíîæåñòâà: � 41532 51432 15 4 5 0 0 16� � � � � � �( ) � F0 . Ïðîâåðèì â ýòîì ìíîæåñòâå îãðàíè÷åíèÿ 2 è 3: 2) � " � " !2 0 3 1 12 — âûïîëíåíî; 3) 2 1 5 7" � � — âûïîëíåíî. Ñëåäîâàòåëüíî, èìååì åùå îäíî äîïóñòèìîå ðåøåíèå: # � �x ( ; ; ; ; )2 0 1 5 3 ; F1 16� . Ïîñêîëüêó F F1 0� , òî ðåêîðä F0 íå óìåíüøàåòñÿ. Âîçâðàùàåìñÿ íà âòîðîé óðîâåíü, çàäàåì x1 0� , îáðàçóåì D 42 51 , ïîëó÷àåì ~ { , , }C � �1 0 4 , ~ { , , }G � �2 1 5 . Âû÷èñëÿåì îöåíêó � 42 51 5 3 0 2 1 2� " � " � " � �( ( ) 1 0" � � " � � !4 5 7 0) F . Ïðîàíàëèçèðóåì â D 42 51 îãðàíè÷åíèÿ, êîòîðûå èìåþò âèä: 1) 2 72 4x x� � � ; 2) � � �2 3 102 3x x ; 3 2 53 4) x x� � . Íàéäåì âåëè÷èíû: 1) � min ( , ) ( ~ ) min ( ) ( )� � � " � � " � � �x x E G x x 2 4 33 2 2 2 2 1 5 92 4 , � max ( , ) ( ~ ) max ( ) ( )� � � " � " � � �x x E G x x 2 4 33 2 2 2 5 1 2 122 4 ; � 0 7 9 12� � � �[ ; ] ; 2) �min ( , ) ( ~ ) min ( ) ( ) ( )� � � � " � � � " � � �x x E G x x 2 3 33 2 2 3 3 2 2 52 3 16 10 0! � � ; 3) � �max ( , ) ( ~ ) max ( )� � � " � " � � � �x x E G x x 3 4 33 2 2 2 5 1 1 11 53 4 0 . Ñëåäîâàòåëüíî, íåò îñíîâàíèé íå âåòâèòü äàëüøå D 42 51 . Âûïîëíèì âåòâëåíèå, çàäàâ x4 2� � è îáðàçîâàâ D 421 514 ; ïîëó÷èì ~ { , }C � �0 4 , ~ G �{1, 5}. Íàéäåì � 421 514 015 1 2 0 1 4 5 7� � " � � " � " � � !( ) ( ) F . Ïðîàíàëèçèðóåì îãðà- íè÷åíèå âèäà: 2 92x � � ; x G2 9 2 � � � ~ ; ñëåäîâàòåëüíî, D 421 514 � . Çàäàäèì x4 1� , îáðàçîâàâ D 423 514 ; ïîëó÷èì ~ { , }C � �0 4 , ~ { , }G � �2 5 . Íàéäåì � 423 514 015 1 1 0 2 4 5 4� � " � " � � " � � !( ( ) ) F . Ïðîàíàëèçèðóåì îãðàíè÷åíèÿ:1 2 62) x � � ; x G2 3� � � ~ , D 423 514 � . Çàäàäèì x4 5� , îáðàçîâàâ D 425 514 , ïîëó÷èì ~ { , }C � �0 4 , ~ { , }G � �2 1 . Íàéäåì � 425 514 015 1 5 0 2 4 1 16� � " � " � � " � �( ( ) ) F , îòñåêàåì ìíîæåñòâî D 425 514 , ïîñêîëüêó åãî îöåíêà õóæå (áîëüøå) ðåêîðäà F0 (îòìåòèì, ÷òî îòñå÷åíèå ïî ýòîé ïðè÷èíå ïîëó÷åíî âïåðâûå â ýòîì ïðèìåðå). Çàäàåì x1 1� , îáðàçîâàâ D 43 51; ïîëó÷àåì ~ C �{1, 0, �4}, ~ { , , }G � �2 0 5 . Íàéäåì � 43 51 015 1 2 1 2 0 0 4 5 5� � " � " � � " � " � � !( ( ) ) F . Ïðîàíàëèçèðóåì îãðàíè÷åíèÿ, êîòî- ðûå äëÿ D 43 51 ïðèíÿëè âèä: 1) 2 82 4x x� � � ; 2) � � �2 3 92 3x x ; 3) 2 43 4x x� � . Íàõîäèì ïàðàìåòðû: 1) � min ( , ) ( ~ ) min ( ) ( )� � � " � � " � � �x x E G x x 2 4 33 2 2 2 2 1 5 92 4 , � max ( , ) ( ~ ) max ( ) ( )� � � " � " � � �x x E G x x 2 4 33 2 2 2 5 1 2 122 4 ; � 0 8 9 12� � � �[ ; ] ; 136 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 2 2) �min ( , ) ( ~ ) min ( ) ( ) ( )� � � � " � � � " � � �x x E G x x 2 3 33 2 2 3 3 2 2 52 3 16 9 0! � � , 3) � �max ( , ) ( ~ ) max ( )� � � " � " � � � �x x E G x x 3 4 33 2 2 2 5 1 0 10 43 4 0 . Ñëåäîâàòåëüíî, ìîæíî ïðîäîëæàòü âåòâèòü D 43 51. Çàäàäèì x4 2� � , îáðàçîâàâ D 431 514 , ïîëó÷èì ~ { , }C � �0 4 , ~ G �{0, 5}. Îöåíèì D 431 514 : � 431 514 015 2 1 2 0 0 4 5 5� � � " � � " � " � � !( ) ( ) F . Ïðîàíàëèçèðóåì îãðàíè÷åíèÿ äëÿ D 431 514 , êîòîðûå ïðèíÿëè âèä: 1) 2 102x � � ; x G2 5� � � ~ ; ñëåäîâàòåëüíî, D 431 514 � . Çàäàäèì x4 0� , îáðàçîâàâ D 432 514 , ïîëó÷èì ~ { , }C � �0 4 , ~ { , }G � �2 5 . Íàõîäèì � 432 514 03� � ! F . Ïðîàíàëèçèðóåì îãðàíè÷åíèÿ: 1) 2 82x � � ; x G2 4� � � ~ ; ñëåäî- âàòåëüíî, D 432 514 � . Çàäàäèì x4 5� , îáðàçîâàâ D 435 514 , ïîëó÷èì ~ { , }C � �0 4 , ~ { , }G � �2 0 ; îöåíèì � 435 514 022� � F . Ìíîæåñòâî îòñåêàåòñÿ. Çàäàåì x1 5� , îáðàçîâàâ D 45 51, ïîëó÷èì ~ C �{1, 0, �4}, ~ { , , }G � �2 0 1 ; îöåíèì � 45 51 019� � F ; ñëåäîâàòåëüíî, âåðøèíó D 45 51 îòñåêàåì. Âîçâðàùàåìñÿ íà ïåðâûé óðîâåíü. Çàäàåì ïîñëåäíåå èç âîçìîæíûõ çíà÷åíèé äëÿ x5 5� , îáðàçîâûâàÿ ìíîæåñò- âî D 5 5 ; ïîëó÷èì ~ C �{2, 1, 0, �4}, ~ G �{2, 0, 1, 3}. Íàéäåì � 5 5 5 5 2 2 1 0� " � " � � " �( ( ) � " � " � �0 1 4 3 9 0) F ; ñëåäîâàòåëüíî, ìíîæåñòâî D 5 5 îòñåêàåì. Âñå âåðøèíû ëèáî ðàçâåòâëåíû äî îäíîýëåìåíòíûõ (äîïóñòèìûõ ðåøåíèé), ëèáî îòñå÷åíû. Ýòî îçíà÷àåò, ÷òî çàäà÷à ðåøåíà. Òåêóùèé ìèíèìàëüíûé ðåêîðä öåëå- âîé ôóíêöèè è òî÷êà, êîòîðàÿ åãî îïðåäåëÿåò, èìåþò âèä x x* � �0 ( ; ; ; ; )�2 0 3 5 1 ; C x F( )* � �0 6 . Ñõåìà ðåøåíèÿ ïðèìåðà ÌÂà ïðåäñòàâëåíà íà ðèñ. 1–3. Çàìå- òèì, ÷òî â ÌÂà äëÿ ýòîãî ïðèìåðà íå áûëî óëó÷øåíèÿ ðåêîðäà F0 , ò.å. ïåðâîå äîïóñòèìîå ðåøåíèå îêàçàëîñü îïòèìàëüíûì. ÇÀÊËÞ×ÅÍÈÅ Â íàñòîÿùåé ñòàòüå ìåòîä âåòâåé è ãðàíèö ðàñïðîñòðàíÿåòñÿ íà ðåøåíèå óñëîâíîé ëèíåéíîé ïîëíîñòüþ êîìáèíàòîðíîé çàäà÷è îïòèìèçàöèè íà ïåðå- ñòàíîâêàõ íà îñíîâå îïðåäåëåíèÿ îöåíîê äîïóñòèìûõ ïîäìíîæåñòâ, îïðåäåëå- íèÿ ïðàâèë âåòâëåíèÿ è ïðàâèë îòñå÷åíèÿ ïîäìíîæåñòâ. Ïðè ýòîì îáíàðóæåíî è îáîñíîâàíî ñâîéñòâî îöåíêè, èñïîëüçîâàíèå êîòîðîãî óâåëè÷èâàåò ýôôåê- òèâíîñòü ÌÂÃ.  äàëüíåéøåì öåëåñîîáðàçíî èññëåäîâàòü âîçìîæíîñòü ïîëó÷åíèÿ óñëîâèé, ïðè êîòîðûõ ïåðâîå äîïóñòèìîå ðåøåíèå â ÌÂà äëÿ ðàñ- ñìîòðåííîé çàäà÷è ÿâëÿëîñü áû îïòèìàëüíûì. ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ 1. Ñ å ð ã è å í ê î È .  . Ìàòåìàòè÷åñêèå ìîäåëè è ìåòîäû ðåøåíèÿ çàäà÷ äèñêðåòíîé îïòèìèçà- öèè. — Ê.: Íàóê. äóìêà, 1988. — 472 ñ. 2. Ñ å ð ã è å í ê î È .  . , Ê à ñ ï ø è ö ê à ÿ Ì . Ô . Ìîäåëè è ìåòîäû ðåøåíèÿ íà ÝÂÌ êîìáèíàòîð- íûõ çàäà÷ îïòèìèçàöèè. — Ê.: Íàóê. äóìêà, 1981. — 288 ñ. 3. Ñ å ð ã è å í ê î È .  . , Ø è ë î  . Ï . Çàäà÷è äèñêðåòíîé îïòèìèçàöèè: ïðîáëåìû, ìåòîäû ðå- øåíèÿ, èññëåäîâàíèÿ. — Ê.: Íàóê. äóìêà, 2003. — 263 ñ. ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 2 137 4. Ñ ò î ÿ í Þ . à . , ª ì å ö ü Î . Î . Òåîð³ÿ ³ ìåòîäè åâêë³äîâî¿ êîìá³íàòîðíî¿ îïòèì³çàö³¿. — Ê.: ²í-ò ñèñòåìíèõ äîñë³äæåíü îñâ³òè, 1993. — 188 ñ. 5. Ñ ò î ÿ í Þ . à . , ª ì å ö ü Î . Î . , ª ì å ö ü ª . Ì . Îïòèì³çàö³ÿ íà ïîë³ðîçì³ùåííÿõ: òåîð³ÿ òà ìå- òîäè: — Ïîëòàâà: ÐÂÖ ÏÓÑÊÓ, 2005. — 103 ñ. 6. Å ì å ö Î . À . Åâêëèäîâû êîìáèíàòîðíûå ìíîæåñòâà è îïòèìèçàöèÿ íà íèõ. Íîâîå â ìàòåìàòè- ÷åñêîì ïðîãðàììèðîâàíèè: Ó÷åá. ïîñîáèå. — Ê.: ÓÌÊ ÂÎ, 1992. — 92 ñ. 7. ª ì å ö ü Î . Î . , Ð î ñ ê ë à ä ê à Î .  . Çàäà÷³ îïòèì³çàö³¿ íà ïîë³êîìá³íàòîðíèõ ìíîæèíàõ: âëàñ- òèâîñò³ òà ðîçâ’ÿçóâàííÿ: — Ïîëòàâà: ÐÂÖ ÏÓÑÊÓ, 2006. — 129 ñ. 8. ª ì å ö ü Î . Î . , Ê î ë º ÷ ê ³ í à Ë . Ì . Çàäà÷³ êîìá³íàòîðíî¿ îïòèì³çàö³ÿ ç äðîáîâî-ë³í³éíèìè ôóíêö³ÿìè / ϳä ðåä. ².Â. Ñåð㳺íêà. — Ê.: Íàóê. äóìêà, 2005. — 117 ñ. 9. Å ì å ö Î . À . , Á à ð á î ë è í à Ò . Í . Êîìáèíàòîðíàÿ îïòèìèçàöèÿ íà ðàçìåùåíèÿõ / Ïîä ðåä. È.Â. Ñåðãèåíêî. — Ê.: Íàóê. äóìêà, 2008. — 159 ñ. 10. Å ì å ö Î . À . , Ð î ì à í î â à Í . à . Îïòèìèçàöèÿ íà ïîëèïåðåñòàíîâêàõ / Ïîä ðåä. È.Â. Ñåðãè- åíêî. — Ê.: Íàóê. äóìêà, 2010. — 105 ñ. 11. Å ì å ö Î . À . , Ï à ð ô å í î â à Ò . À . Òðàíñïîðòíûå çàäà÷è íà ïåðåñòàíîâêàõ: ñâîéñòâà îöåíîê â ìåòîäå âåòâåé è ãðàíèö // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2010. — ¹ 6. — Ñ. 106–112. 12. ª ì å ö ü Î . Î . , Ï à ð ô ü î í î â à Ò . Î . Îö³íþâàííÿ äîïóñòèìèõ ìíîæèí ðîçâ’ÿçê³â êîìá³íà- òîðíî¿ òðàíñïîðòíî¿ çàäà÷³ íà ïåðåñòàâëåííÿõ, ùî ðîçâ’ÿçóºòüñÿ ìåòîäîì ã³ëîê òà ìåæ // Íàó- êîâ³ â³ñò³ ÍÒÓÓ «Êϲ». — 2010 — ¹ 1. — Ñ. 21–28. 13. ª ì å ö ü Î . Î . , Ï à ð ô ü î í î â à Ò . Î . Íàáëèæåíèé ìåòîä äëÿ ðîçâ’ÿçóâàííÿ êîìá³íàòîðíèõ òðàíñïîðòíèõ çàäà÷ // Ðàäèîýëåêòðîíèêà è èíôîðìàòèêà. — 2006. — ¹ 2. — Ñ. 39–41. 14. ª ì å ö ü Î . , Ð î ì à í î â à Í . , Ð î ñ ê ë à ä ê à Î . Ïðî âëàñòèâîñò³ äåÿêèõ çàäà÷ åâêë³äîâî¿ êîìá³íàòîðíî¿ îïòèì³çàö³¿ íà ïåðåñòàâëåííÿõ òà ìåòîäè ¿õ ðîçâ’ÿçóâàííÿ // ³ñíèê Ëüâ³â. óí-òó. Ñåð. Ïðèêëàä. ìàòåìàòèêà òà ³íôîðìàòèêà. — 2002. — Âèï. 5. — Ñ. 13–15. 15. ªìåöü Î.Î. , Ðîìàíîâà Í.Ã. , ×³ë ³ê ³íà Ò.Â. Îïòèì³çàö³ÿ íà âåðøèííî ðîçòàøîâàíèõ åâêë³äîâèõ êîìá³íàòîðíèõ ìíîæèíàõ // Ìàòåìàòè÷íå ìîäåëþâàííÿ. — 2003. — ¹ 2 (10). — Ñ. 39–41. 16. ª ì å ö ü Î . Î . , Ð î ì à í î â à Í . à . Êîìá³íîâàíèé ìåòîä ðîçâ’ÿçóâàííÿ ë³í³éíèõ êîìá³íàòîð- íèõ çàäà÷ îïòèì³çàö³¿ íà âåðøèííî ðîçòàøîâàíèõ åâêë³äîâèõ êîìá³íàòîðíèõ ìíîæèíàõ // Äè- íàìè÷åñêèå ñèñòåìû (ìåæâåä. íàó÷. ñá.). — 2004. — Âûï. 17. — Ñ. 166–170. 17. Ì à ò å ì à ò è ÷ å ñ ê è å ìåòîäû èññëåäîâàíèÿ îïåðàöèé: Ó÷åá. ïîñîáèå äëÿ âóçîâ / Þ.Ì. Åðìîëüåâ, È.È. Ëÿøêî, Â.Ñ. Ìèõàëåâè÷, Â.È. Òþïòÿ. — Ê.: Âèùà øê., 1979. — 312 ñ. 18. Ë è í å é í î å è íåëèíåéíîå ïðîãðàììèðîâàíèå / È.Í. Ëÿøåíêî, Å.À. Êàðàãîäîâà, Í.Â. ×åðíè- êîâà, Í.Ç. Øîð. — Ê.: Âèùà øê., 1975. — 372 ñ. Ïîñòóïèëà 20.09.2011 138 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 2

Схожі ресурси