Решение задачи о ранце: постоптимальный анализ и метод ветвей и границ

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

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2011
1. Verfasser:	Михайлюк, В.А.
Format:	Artikel
Sprache:	Russian
Veröffentlicht:	Інститут кібернетики ім. В.М. Глушкова НАН України 2011
Schriftenreihe:	Проблемы управления и информатики
Schlagworte:	Оптимальное управление и методы оптимизации
Online Zugang:	https://nasplib.isofts.kiev.ua/handle/123456789/207376
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:	Решение задачи о ранце: постоптимальный анализ и метод ветвей и границ / В.А. Михайлюк // Проблемы управления и информатики. — 2011. — № 6. — С. 43–51. — Бібліогр.: 9 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-207376
record_format	dspace
spelling	irk-123456789-2073762025-10-07T00:05:37Z Решение задачи о ранце: постоптимальный анализ и метод ветвей и границ Розв’язання задачі про ранець: постоптимальний аналіз та метод гілок і меж Solving Knapsack Problem: Postoptimality Analysis and Branch and Bound Method Михайлюк, В.А. Оптимальное управление и методы оптимизации Запропоновано алгоритм постоптимального аналізу для визначення точних розв’язків сімейства споріднених задач про ранець, до яких належить вихідна задача. Обчислювальний експеримент показує, що середній час розв’язання задачі сімейства принаймні в десять разів менший за час розв’язання вихідної задачі методом гілок і меж. An algorithm of postoptimality analysis for determining exact solutions of a family of knapsack problems including an initial problem is proposed. Computational experiments show that the average time of solving a problem of the family is at least ten times less than the time of solving the initial problem by the branch and bound method. 2011 Article Решение задачи о ранце: постоптимальный анализ и метод ветвей и границ / В.А. Михайлюк // Проблемы управления и информатики. — 2011. — № 6. — С. 43–51. — Бібліогр.: 9 назв. — рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/207376 519.854 10.1615/JAutomatInfScien.v43.i11.50 ru Проблемы управления и информатики application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Оптимальное управление и методы оптимизации Оптимальное управление и методы оптимизации
spellingShingle	Оптимальное управление и методы оптимизации Оптимальное управление и методы оптимизации Михайлюк, В.А. Решение задачи о ранце: постоптимальный анализ и метод ветвей и границ Проблемы управления и информатики
description	Запропоновано алгоритм постоптимального аналізу для визначення точних розв’язків сімейства споріднених задач про ранець, до яких належить вихідна задача. Обчислювальний експеримент показує, що середній час розв’язання задачі сімейства принаймні в десять разів менший за час розв’язання вихідної задачі методом гілок і меж.
format	Article
author	Михайлюк, В.А.
author_facet	Михайлюк, В.А.
author_sort	Михайлюк, В.А.
title	Решение задачи о ранце: постоптимальный анализ и метод ветвей и границ
title_short	Решение задачи о ранце: постоптимальный анализ и метод ветвей и границ
title_full	Решение задачи о ранце: постоптимальный анализ и метод ветвей и границ
title_fullStr	Решение задачи о ранце: постоптимальный анализ и метод ветвей и границ
title_full_unstemmed	Решение задачи о ранце: постоптимальный анализ и метод ветвей и границ
title_sort	решение задачи о ранце: постоптимальный анализ и метод ветвей и границ
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate	2011
topic_facet	Оптимальное управление и методы оптимизации
url	https://nasplib.isofts.kiev.ua/handle/123456789/207376
citation_txt	Решение задачи о ранце: постоптимальный анализ и метод ветвей и границ / В.А. Михайлюк // Проблемы управления и информатики. — 2011. — № 6. — С. 43–51. — Бібліогр.: 9 назв. — рос.
series	Проблемы управления и информатики
work_keys_str_mv	AT mihajlûkva rešeniezadačiorancepostoptimalʹnyjanalizimetodvetvejigranic AT mihajlûkva rozvâzannâzadačíproranecʹpostoptimalʹnijanalíztametodgílokímež AT mihajlûkva solvingknapsackproblempostoptimalityanalysisandbranchandboundmethod
first_indexed	2025-10-07T01:12:19Z
last_indexed	2025-10-08T01:06:54Z
_version_	1845373818127777792
fulltext	© В.А. МИХАЙЛЮК, 2011 Международный научно-технический журнал «Проблемы управления и информатики», 2011, № 6 43 УДК 519.854 В.А. Михайлюк РЕШЕНИЕ ЗАДАЧИ О РАНЦЕ: ПОСТОПТИМАЛЬНЫЙ АНАЛИЗ И МЕТОД ВЕТВЕЙ И ГРАНИЦ Проведение постоптимального анализа дискретных оптимизационных за- дач [1–5] предусматривает решение следующих вопросов:  как изменится оптимальное решение конкретной задачи, если определен- ным образом изменить значения ее коэффициентов;  каким образом использовать информацию, полученную при решении неко- торой задачи тем или иным конкретным методом, для решения измененной задачи;  какую минимальную дополнительную информацию необходимо накопить при решении исходной задачи для эффективного решения измененной задачи. Областью применения постоптимального анализа является анализ деятельно- сти некоторого реального процесса, описываемого моделью дискретной оптими- зации, который лежит в основе различного рода нововведений. Кроме того, при небольших изменениях в исходных данных модели дискретного программирова- ния ведут себя, как правило, неустойчиво и непредсказуемо. Постоптимальный анализ той или иной задачи дискретного программирова- ния проводится на основе некоторого определенного подхода (метода), применяе- мого для решения этой задачи. Известны процедуры постоптимального анализа за- дач целочисленного программирования, основанные на методе отсечений Гомори, на методе ветвей и границ [4]. При проведении постоптимального анализа можно использовать приближенные методы, в частности методы локального поиска. С постоптимальным анализом тесно связан параметрический анализ и вопро- сы устойчивости дискретных задач оптимизации. При параметрическом анализе используется семейство однотипных задач, отличающихся некоторым парамет- ром (либо в целевой функции, либо в ограничениях). Что можно сказать об опти- мальных решениях всего семейства, исходя из оптимальных решений задач неко- торого подсемейства? При исследовании устойчивости изучаются вопросы такого изменения исходных данных, которые не влияют на оптимальные решения. Вопросы устойчивости, параметрического и постоптимального анализа рас- сматривались в [3, 5]. В данной работе для решения задачи о ранце предлагается метод ветвей и границ с использованием идей постоптимального анализа при решении семейства родственных задач. Общая схема метода ветвей и границ Рассмотрим общую схему данного метода для задачи )},({max)( 0 xfxf Gx  (1) множество G конечно, . NG Алгоритм метода ветвей и границ основан на следующих построениях, поз- воляющих уменьшить объем перебора [6]. 1. Вычисление оценки. Пусть ,GG  тогда )(G называется верхней оцен- кой, если для любого 'Gx выполняется ).()( Gxf  (2) 44 ISSN 0572-2691 2. Ветвление (разбиение множества G на подмножества). Положим GG 0 и разобьем множество 0G на 1r непересекающихся подмножеств: .,0,,...,,, 11 1 1011 2 1 1 1 1 jiGGGGGGG ji r i ir    Этот шаг алгоритма считаем начальным, нулевым. Рассмотрим шаг алгорит- ма с номером .k Пусть k r kk k GGG ...,,, 21 — множества, еще не подвергавшиеся разбиению. Выберем одно из этих множеств — k sG и разобьем его на непересе- кающиеся подмножества: . 1 , r t k ts k s GG   Выполним модификацию списка множеств, еще не подвергавшихся разбие- нию. Заменим множество k sG множествами ,, k tsG и множества, еще не подвер- гавшиеся разбиению, переобозначим: ....,,, 11 2 1 1 1   k r kk k GGG Эти множества обра- зуют список задач для ветвления. Выберем одно из них и снова повторим проце- дуру разбиения. 3. Пересчет оценок. Если ,21 GG  то )}.({max)}({max 21 xfxf GxGx   Поэтому, разбивая в процессе ветвления подмножество GG ' на непересекающиеся под- множества ,,...,,, 1 s21  s i iGGGGG   будем предполагать, что ),()( GGi  (3) при этом хотя бы для некоторых 0i выполняется строгое неравенство ).()( 0 GGi  4. Вычисление планов (допустимых решений). Для вычисления планов исполь- зуются особенности решаемой задачи. Если на шаге ветвления с номером k изве- стен план ,kx на шаге с номером )1( k — план ,1kx и если ),()( 1 kk xfxf то план kx игнорируется и вместо него сохраняется план .1kx Наилучшее из по- лученных допустимых решений принято называть рекордом. 5. Признак оптимальности. Пусть , 1  s i iGG   ).1( slGx l  Тогда план x оптимален, т.е. ,0xx  если выполняется условие ),()()( il GGxf  ....,,2,1 si  6. Оценка точности приближенных решений. Пусть , 1  s i iGG   0 )},({max 1 i si G  kx — рекорд, тогда имеет место неравенство .)()( 0 0  xfxf k (4) Международный научно-технический журнал «Проблемы управления и информатики», 2011, № 6 45 Разность )(0 kxf — оценка гарантированного отклонения рекорда kx от оптимума .0x Из приведенного неравенства следует, что для ветвления необхо- димо выбрать множество с максимальным значением верхней оценки. При этом в силу (3) обеспечивается уменьшение (точнее, неувеличение) величины  и га- рантируется получение не только точного, но и -приближенного )0(  реше- ния, если таковым считать решение, для которого . 7. Правило отсева. Пусть снова 0 1 , xGG s i i   — оптимум, kx — рекорд. Если ),()( k r xfG  (5) то множество rG можно отсеять, т.е. исключить из рассмотрения, так как оно не может содержать оптимальных решений. Более сильное правило )()( k r xfG  (5) гарантирует, что хотя бы одно оптимальное решение будет найдено, оно и приме- няется при практическом решении задачи. 8. Конечность алгоритма. Конечность алгоритма следует из конечности множества .G Общая схема решения задачи На начальном (первом) шаге процесса ветвления множество 0G записывает- ся в список задач для ветвления. После выполнения процедуры ветвления список модифицируется: в него вместо 0G записываются множества ....,,2,1, siGi  Та- кая модификация выполняется на каждом шаге процесса ветвления. Полученный список обычно называют списком задач-кандидатов. Задача решена, если список задач-кандидатов пуст, т.е. если все они отсеяны по правилам отсева. Алгоритм метода ветвей и границ можно представить схемой: 1) в список задач-кандидатов записывается исходная задача; 2) если список пуст, то задача решена, иначе — переход к п. 3; 3) осуществляется выбор множества для ветвления; 4) выполняется ветвление и модифицируется список задач; 5) вычисляются оценки и находятся рекорды; 6) выполняется отсев множеств, не содержащих оптимальных решений, и про- веряется признак оптимальности; 7) осуществляется переход к п. 2. Особенности метода ветвей и границ для задачи о ранце Введем множества iin nnn xxxxxZB ,0\|)...,,({,}1,0{ 1  — целые, }....,,1 ni  Одномерную булеву задачу о ранце рассмотрим в постановке :)),,(( cbaR :)},(\|)(max{ 1 baQxxcxf i n i i   }.\|{),( 1 bxaBxbaQ j n j j n    46 ISSN 0572-2691 Будем считать, что все ,ja jc и b — целые неотрицательные числа: .,)...,,(,),...,( 1 11 ZbZcccZaaa n n n n  Известно, что задача ),,( cbaR NP-полна [7]. Для векторов ,),...,,( 1 11    n nn Zxxxx 1 11 ),...,,(    n nn Zyyyy введем метрику .\|\|),( 1 0 i n i i yxyx     Для применения к решению задачи R(a, b, c) метода ветвей и границ необхо- димо указать способ получения верхней оценки для задач-кандидатов. Наряду с задачей R(a, b, c) будем рассматривать непрерывную релаксацию CR(a, b, c) за- дачи R(a, b, c), в которой условие nBx заменено условием ),...,,( 1 nxxx  ....,,1,10 nixi  Предположим, что предметы, упорядоченные согласно условию ,... 2 2 1 1 n n a c a c a c  (6) последовательно заполняют ранец, пока не найдется первый предмет s, который нельзя вставить (жадный алгоритм относительно последовательности (6)). Будем называть этот предмет критическим пунктом, т.е. ,:min 1            bajs j i i при этом .1 ns  Задача CR(a, b, c) может быть решена согласно свойству, установлен- ному Данцигом (Dantzig, 1957) [8], которое сформулируем формально. Теорема [8]. Оптимальное решение x задачи CR(a, b, c) есть 1jx при ,1...,,2,1  sj 0jx при ,...,,1 nsj  , s s a b x  где , 1 1     s j jabb s — критический пункт. Таким образом, оптимальное решение )...,,( 1 nxxx  задачи CR(a, b, c) тако- во, что .)( 1 1 s s s j j a c bcxf     Поскольку все jj xc , — целые, верхняя оценка )(xf для R(a, b, c) имеет вид , 1 1 1           s s s j j a c bcU (7) где ][a — наибольшее целое, не большее .a Для решения задачи о ранце R(a, b, c) будем пользоваться верхней оцен- кой (7) и применим алгоритм Хоровитца–Сани (Horowitz–Sahni algorithm) [8], ос- новная идея которого состоит в следующем: а) ветвление осуществляется по нефиксированной переменной jx согласно упорядочению (6) и выбирается две задачи-кандидата );0,1(  jj xx Международный научно-технический журнал «Проблемы управления и информатики», 2011, № 6 47 б) поиск продолжается вставкой предмета j (условие ),1jx т.е. согласно жадной стратегии, соответствующей (6); в) для вычисления верхних оценок задач-кандидатов используется оцен- ка 1U (7). Шаг-вперед состоит во вставке наибольшего множества предметов в текущее решение, шаг-возврат состоит в отмене последнего вставленного предмета в те- кущее решение. После того как выполнен шаг-вперед, вычисляется верхняя оцен- ка ,1U соответствующая текущему решению, и сравнивается с наилучшим реше- нием, чтобы проверить, получится ли лучшее решение. Если так, выполняется шаг-вперед, иначе — шаг-возврат. После рассмотрения последнего предмета те- кущее решение сформировано и проверяются дальнейшие его улучшения. Алго- ритм останавливает свою работу, когда не может быть выполнен дальнейший шаг-возврат. Алгоритм с использованием постоптимального анализа на основе метода ветвей и границ для задачи о ранце Суть алгоритма состоит в использовании идей из [9] при установлении слож- ности постоптимального анализа задачи о ранце (доказательство теоремы 4 [9]). Пусть ,),...,,( 1 1  n n Zbaaa а a  такой, что 1),(  aa (задачу ),,( cbaR будем обозначать и так )).,(: caR Пусть },...,,2,1{ nN  }...,,{11 kiiK  — некото- рая выборка из N объема ),1( nkk  n n Bxxx  )...,,( ** 1 * такой, что ...* 1 ix ,1... *  ki x остальные координаты вектора x равны нулю. Пусть вектор ),...,,( ** 1 * baaa n такой, что 1,1... *** 1  kaaa jii k при ,\ 1KNj .* kb  Рассмотрим лемму 2 из [9]. Пусть x — оптимальное решение экземпляра I задачи ).,( caR Пусть для произвольного вектора 1 nZa имеем )(aT — пре- образование вектора a с увеличением или уменьшением ровно одного его ком- понента на единицу. Будем считать, что ),(aTa  если после применения к a преобразования Т получили вектор a (ясно, что ).1),(  aa Если считать, что компоненты вектора a ограничены сверху константой c, которая не зависит от размерности задачи n, произвольный вектор a можно получить из вектора ,a применяя не более )1( nc преобразований :T ;...1 aaaa kTTT  (8) где ),( 1 aTa  ;1),( 1  aa ),(1 ii aTa  ,1),( 1   ii aa ;1...,,1  ki ).1(  nck Пусть Knaps_HS )),,(( 0 xxa — процедура метода ветвей и границ Хоровитца- Сани (HS) для задачи ),( caR с начальным приближением ,0x результат — век- тор x (вектор c в названии процедуры опущен, поскольку он не меняется). Алгоритм постоптимального анализа Postopt_Knaps для решения задачи о ранце ),( caR можно записать в виде последовательности шагов. Шаг 1. Применение приближенного полиномиального алгоритма для реше- ния ),,( caR x — решение (приближенное). 48 ISSN 0572-2691 Шаг 2. Построение a по x (согласно лемме 2 из [9]). Шаг 3. ).( 1 aTa  Шаг 4. Если x — допустимое решение ),,( 1 caR то переходим на шаг 5, иначе модификация ( x )(modif ( x )), переходим на шаг 5. Шаг 5. Knaps_HS ),,( 11 xxa на шаг 6. Шаг 6. .1:i Шаг 7. ).(1 ii aTa  Шаг 8. Если ix — допустимое решение ),,( 1 caR i то переходим на шаг 9, иначе модификация ( ix )(modif( ix )) и переходим на шаг 9. Шаг 9. Knaps_HS ).,,( 11  iii xxa Если ,1 aa i  то конец 1( ix — опти- мальное решение задачи ),,( 1 caR i иначе 1:  ii и переходим на шаг 7. Шаги 3–9 выполняются согласно (8). Процедура модификация (z) (modif (z)) применяется, когда )...,,( 1 nzzz  не есть допустимое решение задачи ),( 1 caR i при некотором фиксированном i ).0( i Для ),...,,,( 11 2 1 1 1 baaaa i n iii   это возможно в одном из двух случаев: а) для некоторого фиксированного j 1i ja увеличивается на единицу )1:( 11   i j i j aa и при этом ;1jx б) b уменьшается на единицу ).1:(  bb Определяем }1:{minarg 1   ii ni zcl и в обоих случаях положим .0lz В шаге 1 можно применить любой алгоритм локальной оптимизации (напри- мер, метод вектора спада [2]), либо жадные алгоритмы относительно последова- тельностей (6) или (9): ....21 nccc  (9) Замечание 1. Уменьшение вычислительной сложности алгоритма Postopt_Knaps основано на том, что на каждом шаге при решении ),( 1 caR i мы используем оп- тимальное решение предыдущей задачи ix (Knaps_HS )),,,( 12  iii xxa что дает возможность при отсеве вариантов использовать оценку )( ixf и отсеивать те ва- рианты, верхняя оценка которых строго меньше ).( ixf Приведем пример работы алгоритма Postopt_Knaps. При 4n рассмотрим задачу о ранце ),,( caR где ).3,6,7,5(),9()9,7,5,3,2(  cba Согласно шагу 1 алгоритма для решения ),( caR применим жадный алгоритм относительно последовательности (6), получим решение ).0,0,1,1(* x Со- гласно шагу 2 )2,3,3,1,1(* a (x — точное решение задачи )).,( caR Со- гласно шагу 3 строим :)( 1 aTa  увеличим на единицу координату 1a );1:( * 1 * 1  aa ).2,3,3,1,2(1 a Согласно шагу 4 x — уже недопустимое реше- Международный научно-технический журнал «Проблемы управления и информатики», 2011, № 6 49 ние ),( 1 caR ),2312(  применяем modif ).( x В нашем случае 1l и поло- жим 01  xxl (решение стало (0, 1, 0, 0)). Шаг 5 это решение не изменит. Рас- смотрим задачи 1–16:  задача 1 — это ),,( 1 caR )3,6,7,5(),2,3,3,1,2(1  ca (вектор c в даль- нейшем не изменяется, и мы его опускаем) с оптимальным решением );0,0,1,0(1 x  задача 2: ),,( 2 caR )2,3,3,2,2(2 a с оптимальным решением 2x );0,0,1,0(  задача 3: );0,0,0,1(),2,3,3,3,2(),,( 333  xacaR  задача 4: );0,0,0,1(),2,3,4,3,2(),,( 444  xacaR  задача 5: );0,0,0,1(),2,3,5,3,2(),,( 555  xacaR  задача 6: );0,0,0,1(),2,4,5,3,2(),,( 666  xacaR  задача 7: );0,0,0,1(),2,5,5,3,2(),,( 777  xacaR  задача 8: );0,0,0,1(),2,6,5,3,2(),,( 888  xacaR  задача 9: );0,0,0,1(,)2,7,5,3,2(),,( 999  xacaR  задача 10: );0,0,1,0(),3,7,5,3,2(),,( 101010  xacaR  задача 11: );0,0,1,0(),4,7,5,3,2(),,( 111111  xacaR  задача 12: );0,0,1,1(),5,7,5,3,2(),,( 122̀112  xacaR  задача 13: );0,0,1,1(),6,7,5,3,2(),,( 131313  xacaR  задача 14: );0,0,1,1(),7,7,5,3,2(),,( 141414  xacaR  задача 15: );0,1,1,0(),8,7,5,3,2(),,( 151515  xacaR  задача 16 (исходная): ).0,1,1,0(),9,7,5,3,2(),,( 161616  xacaR Таким образом, с помощью шагов 6–9 мы получили последовательность за- дач 2–16, кроме того, в результате работы алгоритма точно решена исходная за- дача и, кроме того, найдены точные решения 15-ти родственных задач. Вычислительный эксперимент В системе программирования Borland C++ Builder 6 под управлением ОС Mi- crosoft Windows XP на персональном компьютере с микропроцессором Intel Celeron 1200 MHz проведен вычислительный эксперимент. Согласно [8] применя- лись данные трех типов:  некоррелированные данные: jc и ja равномерно распределены на [1,  ];  слабо коррелированные данные: ja равномерно распределены на [1,  ]; jc равномерно распределены на ];,[ rara jj   сильно коррелированные данные: ja равномерно распределены на [1,  ], .rac jj  Увеличение степени коррелированности означает уменьшение значения раз- ности                  j j jj j j a c a c minmax и, следовательно, увеличение ожидаемой вычисли- тельной сложности соответствующих задач. Потребностям практики больше от- 50 ISSN 0572-2691 вечают слабо коррелированные задачи. Рассматривались случаи  2b и    n j jab 1 5,0 ).10,100(  r В первом случае оптимальное решение содержало «незначительное» количество единиц и сгенерированные задачи оказались легче, чем во втором случае, где в оптимальном решении около половины единиц. Для каждого случая в результатах вычислительного эксперимента (таблица) было проведено усреднение по десяти задачам, время измеряется в секундах. В таблице строки 2–7 соответствуют некоррелированным данным, строки 8–13 — слабо коррелированным данным, а строки 14–18 — сильно коррелированным данным. Таблица Вместимость ранца (b) Размерность задачи (n) Метод ветвей и границ (Knaps_HS), время решения исходной задачи Алгоритм постоптимального анализа (Postopt_Knaps) Суммарное время решения задач семейства Количество задач в семействе Среднее время реше- ния задачи  2b 50 0,008 0,08 820 0,000097 100 0,01 0,25 3576 0.000069 200 0,01 1,22 17407 0.000070 300 0,016 5,11 38512 0,00013 400 0,017 11,40 72270 0,00016  jab 5,0 50 0,81 29,26 1009 0,029  2b 50 0,012 0,18 951 0,00019 100 0,012 2,93 4181 0,00070 200 0,012 13,37 16519 0,00081 300 0,014 50,20 41984 0,0012 400 0,016 99,67 75043 0,0013  jab 5,0 50 6,03 238,92 1185 0,20  2b 50 0,02 1,51 797 0,0019 100 0,086 30,61 3826 0,008 200 0,036 59,33 16951 0,0035 300 0,12 504,36 42030 0,012  jab 5,0 50 5,57 227,04 1032 0,22 Установлен лимит времени — 600 с (10 мин), в результатах вычислительного эксперимента это отражено отсутствием соответствующих данных в таблице. Ес- ли проанализировать результаты эксперимента, то в любом случае можно конста- тировать, что среднее время решения одной задачи семейства задач в алгоритме Postopt_Knaps в десять раз меньше решения соответствующей основной исходной задачи алгоритма Knaps_HS. Более эффективным представляется использование алгоритма Postopt_Knaps, когда в оптимальном решении исходной задачи «незна- чительное» количество единиц. Таким образом, алгоритм Postopt_Knaps решает не только одну основную исходную задачу, а целое семейство родственных задач; среднее время решения одной задачи семейства на порядок меньше времени ре- шения основной исходной задачи. Замечание 2. Данный подход можно применить к любой дискретной оптими- зационной задаче, условия которой удовлетворяют условиям работы [9] (напри- мер, к задаче о покрытии множествами). Международный научно-технический журнал «Проблемы управления и информатики», 2011, № 6 51 В.О. Михайлюк РОЗВ’ЯЗАННЯ ЗАДАЧІ ПРО РАНЕЦЬ: ПОСТОПТИМАЛЬНИЙ АНАЛІЗ ТА МЕТОД ГІЛОК І МЕЖ Запропоновано алгоритм постоптимального аналізу для визначення точних розв’язків сімейства споріднених задач про ранець, до яких належить вихідна задача. Обчислювальний експеримент показує, що середній час розв’язання задачі сімейства принаймні в десять разів менший за час розв’язання вихідної задачі методом гілок і меж. V.A. Mikhailyuk SOLVING KNAPSACK PROBLEM: POSTOPTIMALITY ANALYSIS AND BRANCH AND BOUND METHOD It is proposed an algorithm of postoptimality analysis for determining exact solutions of family of knapsack problems including an initial problem. Computational experi- ment shows that the middle time of solving the problem of family at least 10 times less than time of solving initial problem by branch and bound method. 1. Козерацкая Л.Н., Лебедева Т.Т., Сергиенко И.В. Вопросы устойчивости, параметрический и постоптимальный анализ задач дискретной оптимизации // Кибернетика. — 1983. — № 4. — С. 71–80. 2. Сергиенко И.В., Шило В.П. Задачи дискретной оптимизации. Проблемы, методы решения, исследования. — Киев : Наук. думка, 2003. — 261 с. 3. Geoffrion A.M., Nauss R. Parametric and postoptimality analysis in integer linear programming // Management Sci. — 1977. — 23, N 5. — P. 453–466. 4. Roodman G.M. Postoptimality analysis in zero one programming by implicit enumeration // Na- val Res. Logist. Quart. — 1972. — 19, N 3. — P. 435–447. 5. Greenberg H.J. An annotated bibliography for post-solution analysis in mixed integer program- ming and combinatorial optimization // D.L. Woodruff (ed.) Advances in computational and sto- chastic optimization, logic programming, and heuristic search. — N.Y. : Kluwer Academ. Publ., 1998. — P. 97–148. 6. Сигал И.Х., Иванова А.П. Введение в прикладное дискретное программирование: модели и вычислительные алгоритмы: Уч. пособие. — М. : Физматлит, 2003. — 240 с. 7. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. — М. : Мир, 1982. — 416 с. 8. Martello S., Toth P. Knapsack problems. Algorithms and computer implementations. — Chiches- ter, England : John Wiley & Sons Ltd, Baffins Lane, 1990. — 296 p. 9. Михайлюк В.А. Общий подход к оценке сложности постоптимального анализа дискретных задач оптимизации // Кибернетика и системный анализ. — 2010. — 46, № 2. — С. 134–141. Получено 04.07.2011 Статья представлена к публикации членом редколлегии И.В. Сергиенко.

Решение задачи о ранце: постоптимальный анализ и метод ветвей и границ

Institution

Ähnliche Einträge