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

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

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Veröffentlicht in:	Кибернетика и системный анализ
Datum:	2013
Hauptverfasser:	Емец, О.А., Емец, Е.М., Парфёнова, Т.А., Чиликина, Т.В.
Format:	Artikel
Sprache:	Russian
Veröffentlicht:	Інститут кібернетики ім. В.М. Глушкова НАН України 2013
Schlagworte:	Системный анализ
Online Zugang:	https://nasplib.isofts.kiev.ua/handle/123456789/86221
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:	Решение линейных условных полностью комбинаторных оптимизационных задач на перестановках методом ветвей и границ / О.А. Емец, Е.М. Емец, Т.А. Парфёнова, Т.В. Чиликина // Кибернетика и системный анализ. — 2013. — Т. 49, № 2. — С. 121-138. — Бібліогр.: 18 назв. — рос.

Institution

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

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

Institution

Ähnliche Einträge