Некоторые методы решения оптимизационных задач комбинаторного типа и их исследование тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

ВВЕДЕНИЕ.

ШВА I. О МАТЕМАТИЧЕСКИХ МОДЕЛЯХ ЗАДАЧ, ОПРЕДЕЛЕННЫХ

НА МНОЖЕСТВЕ ПЕРЕСТАНОВОК.II

§ I. Постановка и обсуждение некоторых задач комбинаторной оптимизации.

§ 2. Формализация одной задачи разбиения множества на подмножества.

§ 3. Один тип задач размещения модулей радиоэлектронной аппаратуры.

§ 4. Задача обслуживания требований идентичными приборами.

РЕЗУЛЬТАТЫ И КРАТКИЕ ВЫВОДЫ К ГЛАВЕ I

ГЛАВА 2. НЕКОТОРЫЕ АЛГОРИТМЫ РЕШЕНИЯ- ОДНОГО КЛАССА

ЗАДАЧ БЕЗУСЛОВНОЙ ОПТИМИЗАЦИИ.

§ I. Один новый алгоритм, реализующий схему метода ветвей и границ.

§ 2. О реализации одного алгоритма локальной оптимизации итерационного типа.

§ 3. Разработка одного алгоритма решения задач безусловной оптимизации, основанного на использовании идей метода Монте-Карло.

§ 4. Последовательный алгоритм решения задачи размещения узлов ЭВМ.

§ 5. Общая схема одного класса последовательных алгоритмов.

§ б. Метод среднего значения.

§ 7. Вычисление точных параметров функции распределения значений критерия.

§ 8. О сравнении алгоритмов.

РЕЗУЛЬТАТЫ И КРАТКИЕ ВЫВОДЫ К ГЛАВЕ

ГЛАВА 3. ВОПРОСЫ РЕАЛИЗАЦИИ АЛГОРИТМОВ НА ЭВМ.

§ I. Решение оптимизационных задач с ограничениями.

§ 2. Прерывание и восстановление вычислительного процесса при решении задач методом ветвей и границ и методом вектора спада

§ 3. Планирование вычислительного процесса и создание комбинированных схем алгоритмов.

§ 4. Функционирование пакета программ при решении задач.

§ 5. Схемы алгоритмов, допускающих распараллеливание вычислений.

РЕЗУЛЬТАТЫ И КРАТКИЕ ВЫВОДЫ К ГЛАВЕ

Дискретное программирование является одним из важных разделов прикладной математики. В частности, большое практическое и теоретическое значение имеют исследования, связанные с решением задач комбинаторной оптимизации. Такие задачи возникают в проектировании, планировании, экономике. К настоящему времени разработано значительное число разнообразных методов и алгоритмов решения оптимизационных задач: метод последовательного анализа вариантов [8,32, 33,3^, 35,3S] , метод построения последовательности планов [/6] , локальные алгоритмы

98,19,20] , метод вектора спада [5] и др. Продолжающаяся разработка новых и модификация известных методов объясняется расширением круга решаемых практических задач, а также появлением новых требований, возникающих при создании программ, реализующих алгоритмы этих методов на ЭВМ. Эти требования касаются главным образом возможности организации прикладного программного обеспечения ЭВМ в виде пакетов программ (ПП). В ходе выполнения данной работы учитываются в основном два таких требования:

1. Универсальность алгоритмов. Как правило, ПП разрабатываются для решения не одной, а целого класса оптимизационных задач. По этой причине необходимо, чтобы каждый программный модуль мог быть применен при решении каждой или хотя бы большинства из них.

2. Разнообразие алгоритмов. Как показывает опыт, обычно . не удается заранее определить, какой из алгоритмов окажется наиболее эффективным при решении конкретной прикладной задачи. Поэтому в ПП необходимо включать несколько алгоритмов для решения одних и тех же задач.

Эти требования возникли на основе изучения опыта разработки математического обеспечения задач оптимизации и нашли свое воплощение при создании ПП семейства ВЕКТОР /У/, 1Z] С другой стороны, целесообразность учета указанных требований подтверждена также результатами, связанными с развитием идей системной оптимизации [8] и исследованием множеств эвристических алгоритмов дискретной оптимизации [21]

С целью удовлетворения требованию универсальности при построении и исследовании различных типов алгоритмов, которые рассматриваются в данной работе, применяется следующая методика. Вначале создается либо выбирается из известных такая общая схема, которую при незначительной модификации можно использовать при построении алгоритмов для решения любой из рассматриваемых в работе задач. Затем в рамках этой фиксированной схемы исследуются различные алгоритмы с целью выбора лучшего из них.

Среди известных в литературе приближенных алгоритмов видное место занимают локально-оптимизационные алгоритмы. Сюда относятся алгоритмы последовательного конструирования решения и итерационные. В них на каждом шаге для имеющегося промежуточного варианта решения выделяется множество близких в некотором смысле вариантов и поиск оптимума производится среди элементов этого множества. Элемент, который улучшает целевую функцию, объявляется новым промежуточным вариантом решения. В последовательных алгоритмах счет оканчивается на том шаге, на котором конструируемое решение описывается вектором заданной длины. Остановка в итерационных алгоритмах осуществляется тогда, когда среди близких элементов не находится такого, который доставляет улучшение целевой функции.

Чтобы выполнить второе требование, в рамках данной работы были исследованы алгоритмы четырех типов:

- алгоритмы метода ветвей и границ. Модификации этих алгоритмов предназначены для поиска решения с заданной точностью;

- алгоритмы метода вектора спада. Это локально-оптимальные алгоритмы итерационного типа;

- алгоритмы метода Монте-Карло. Это алгоритмы стохастического» типа;

- локально-оптимальные алгоритмы последовательного типа.

Для решения отдельных из рассматриваемых задач существуют эффективные алгоритмы, которые, однако, не удовлетворяют требованию универсальности. Таким алгоритмом является, например, венгерский алгоритм [35] для решения линейной задачи о назначениях, которая рассматривается в работе. Подобные алгоритмы также должны включаться в ПП, однако их изучение выходит за рамки настоящей работы.

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

Пусть (ft - {р-(р{,.Рп)] - множество перестановок первых fb натуральных чисел; % <= ф - его подмножество, определяемое ограничительными условиями задачи; -f(p) - целевая функция (критерий) задачи, заданная на 2 или на всем пространстве Ф . Требуется найти такую точку p#G Z » для которой целевая функция принимает наименьшее значение:

Р#-СЬЪ(£ f(p). (О*1)

В работе рассматриваются ограничения следующих четырех типов:

I) фиксированное назначение: заданы Ь}Ц Е {13.fb} и требуется, чтобы ;

2) запретное назначение: заданы г-, U 6 и требуется, чтобы р- Ф Ц ;

3) непосредственное следование: заданы t, ь!б{1,., Л/J такие, что если » то требуется, чтобы р-н =к!

4) простое следование: заданы t,//б /гJ такие, что если и pi -tf , то требуется, чтобы file И,-,">})•

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

Ниже, говоря о типах ограничений, будем иметь в виду их нумерацию, указанную в этом перечне.

Ограничения указанных типов довольно легко учитываются при программной реализации рассматриваемых в работе алгоритмов. При этом, как следует из изучения приведенных ниже вычислительных схем алгоритмов, чем больше ограничений (при фиксированном ft ), тем меньше, как правило, объем требуемых вычислений. По этой причине основное внимание в работе уделяется исследованию задач безусловной оптимизации, т.е. когда

1 = 9 .

В работе рассматриваются несколько типов задач, удовлетворяющие постановке (0.1). Для обозначения этих типов задач будем использовать такие названия:

- линейная задача о назначениях;

- задача о коммивояжере;

- квадратичная задача о назначениях;

- задача разбиения;

- задача размещения;

- один тип задач расписания.

Все приведенные типы задач, за исключением линейной задачи о назначениях, относятся к /JP -полным [fS,23] • Общеизвестны трудности, связанные с созданием эффективных точных алгоритмов для решения таких задач [15,56] . В связи с этим для исследования были выбраны методы, большинство из которых являются приближенными.

Приведем некоторые обозначения и термины, которые используются в работе. Пусть А/ - множество первых ТЬ натуральных чисел. Пусть tfjjC Ф - множество таких перестановок, у которых первые U компонент равны соответственно заданным числам Pi /V • ПРИ будем считать, что . Для любого tf£{0J,. ,тъ} число различных множеств равно, очевидно, С W . Какое из этих множеств обозначено , ft к будет каждый раз понятно из контекста, так как будут известны первые // компонент перестановок ре Ф^ . Последнее замечание справедливо также для множеств I и J , которые опрек деляются следующим образом: если 0<Af

J , если U-Q. h =

0.3)

0.4) fftj,.,P*}» если j < Ц X/ , если =

Легко вычислить мощности множеств Ф. . Очевидно, что

I 0„1=(П-«)! . (0.5)

Если необходимо подчеркнуть, что значение Ц -той компоненты (последней из зафиксированных) перестановок р из множества 0Э равно некоторому Ъ (р^-Ъ) , то такое множество будем обозначать . Следующие обозначения касаются некоторых статистических характеристик критерия j-(p) на множествах ф ф

J0 »

Среднее значение критерия j-(p) на множестве ^^ будем обозначать Cb^ , дисперсию - SD^ , среднеквадратическое отклонение - (f и вычислять по формулам: i „ \%г\ f(P>> (О-6)

Соответствующие величины, характеризующие множество (Р0 будем обозначать Ob , Ю % V и вычислять по формулам:

Г= 1/1), (О-П)

Перестановку , определенную равенством (0.1), будем называть точным или глобальным решением оптимизационной задачи. Если же существует множество S^Z и перестановка ре 3 такие, что р'-аъд rtbin J-(P) , то р' будем называть приближенным решением.

Основным содержанием настоящей работы является исследование некоторых методов решения оптимизационных задач дискретного типа. Конечная же цель работы - это реализация предложенных алгоритмов на ЭВМ.

Целевые функции всех рассматриваемых в работе типов задач определены на множестве перестановок. В первой главе определяются способы вычисления целевой функции для этих типов задач.

Во второй главе изучаются перечисленные выше методы применительно к решению задач оптимизации без ограничений, т.е. когда % — Ф . Каждый из этих методов имеет некую общую схему. Применительно к решению конкретных типов задач разрабатываются отдельные пункты этих схем. Проводится анализ результатов численного эксперимента и теоретического исследования по изучению таких показателей эффективности алгоритмов, как их временная сложность и точность получаемого решения.

В третьей главе рассматривается ряд вопросов, касающихся реализации разработанных алгоритмов на ЭВМ. Рассматривается пригодность изучаемых алгоритмов для решения задач с ограничениями указанных выше типов. Затем рассматриваются отдельные вопросы, связанные с созданием программного обеспечения ЭВМ для решения задач оптимизации в форме ПП на примере ПП ВЕКТОР-2. Наконец, рассматриваются вопросы, связанные с разработкой в рамках рассматриваемых в диссертационной работе подходов к решению задач комбинаторного типа алгоритмов оптимизации, которые предназначены для ЭВМ с параллельной организацией вычислений.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

1. Осуществлена формализация и проведено исследование ряда важных в практическом и теоретическом отношении задач (размещения, теории расписаний и др.), сформулированных как комбинаторные задачи оптимизации.

2. Предложен ряд новых алгоритмов решения выделенного класса задач и исследована их эффективность.

3. Разработаны принципы организации и функционирования мобильных ПП для решения задач комбинаторной оптимизации, которые нашли применение при создании ПП ВЕКТОР-2.

4. Проведен численный эксперимент по решению широкого круга практических и тестовых задач комбинаторной оптимизации, который подтвердил эффективность предложенных алгоритмов.

5. Разработаны компоненты модульного программного обеспечения пакета программ ВЕКТОР-2, в котором реализованы основные алгоритмы, предложенные в диссертации.

6. Разработаны алгоритмы решения задач из выбранного класса, предназначенные для реализации на ЭВМ с параллельной организацией вычислений.

1. Ахо А., Хопкфорт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979. - 536 с.

2. Батищев Д.И., Бедная Р.И., Комардин В.М. Решение задач поисковой оптимизации в интерактивном режиме. В кн.: Интерактивная технология в САПР. Таллин: НИИ Таллинского электротехнического завода им. М.И.Калинина, 1981, с.26-27.

3. Бурдюк В.Я. Дискретные метрические пространства. Днепропетровск: ДГУ, 1982. - 99 с.

4. Бусленко Н.П., Шрейдер Ю.А. Метод статистических испытаний (Монте-Карло) и его реализация на цифровых вычислительных машинах. М.: Физматгиз, 1961. - 231 с.

5. Веселов Е.Н., Евтушенко 10.Г., Мазурик В.П. Содержательные возможности диалоговой системы оптимизации (ДИСО). В кн.: Проблемы вычислительной техники. М.: Международный центр науч. и техн. информации, 1981, с.ПО-122.

6. Волкович В.Л., Волошин А.Ф. Об одной общей схеме последовательного анализа и отсеивания вариантов. Кибернетика, 1978, № 5, с.98-105.

7. Голенко Д.И. Моделирование и статистический анализ псевдослучайных чисел на электронных вычислительных машинах. -М.: 1965. 229 с.

8. Глушков В.М. 0 системной оптимизации. Кибернетика, 1980, № 5, с.89-90.

9. Глушков В.М., Капитонова Ю.В., Летичевский А.А., Горлач С.П. Макроконвейерные вычисления функций над структурами данных. Кибернетика, 1981, № 4, с.13-21.

10. Глушков В.М., Молчанов Н.Н. 0 некоторых проблемах решения задач на ЭВМ с параллельной организацией вычислений.

11. Кибернетика, 1981, № 4, с.82-88.

12. Гуляницкий Л.Ф., Сергиенко И.В., Ходзинский А.Н. Диалоговый пакет программ ВЕКТОР-2. Киев: Ж АН УССР, 1981. -55 с. (Препринт /АН УССР. Ин-т кибернетики: 81-63).

13. Гуляницкий Л.Ф., Ходзинский А.Н. Особенности реализации алгоритмов метода ветвей и границ и метода вектора спада в пакете BEKT0P-IB. В кн.: Вычислительные аспекты в пакетах прикладных программ. Сб. научн. тр. - Киев: ИК АН УССР, 1979, с.45-48.

14. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982, 416 с.

15. Емеличев В.А., Комлик В.И. Метод построения последовательности планов для решения задач дискретной оптимизации. -И.: Наука, 1981. 208 с.

16. Желиховский А.А. Принципы организации диалоговой системы "ПИОНЕР". Кибернетика, 1978, № 5, с.62-67.

17. Журавлев Ю.И. Локальные алгоритмы вычисления информации. I. Кибернетика, 1965, № I, с.12-19.

18. Журавлев Ю.И. Локальные алгоритмы вычисления информации. II. Кибернетика, 1966, Ш 2, c.I-II.

19. Журавлев Ю.И., Финкелыптейн Ю.Ю. Локальный алгоритм для задач линейного целочисленного программирования. В кн.: Проблемы кибернетики, 1965, вып.14, с.289-296.

20. Журавлев Ю.И. Корректные алгебры над множествами некорректных (эвристических) алгоритмов. I. Кибернетика, 1977, № 4, с.14-21.

21. Карманов В.Г. Математическое программирование. М.: Наука, 1975. - 272 с.

22. Карп P.M. Сводимость комбинаторных проблем. В кн.: Кибернетический сборник. Новая серия, 1975, вып.12, с.16-36.

23. Каспшицкая М.Ф., Сергиенко И.В., Хильченко В.И. Об одном подходе к решению задач размещения. Кибернетика, 1974, № 5, с.51-60.

24. Кейс П., Графф Г., Гриффит Л. и др. Автоматизация проектирования вычислительных систем с использованием логических схем на твердом теле. В кн.: Кибернетический сборник: Сб. статей. М.: Мир, 1965, вып. I, с.71-86.

25. Ковалев М.М., Котов В.М. Анализ градиентного решения задачи коммивояжера. IBM и МФ, М.: 1981, № 4, с.1035-1038.

26. Конвей Р.В., Максвелл В.Л., Миллер Л.В. Теория расписаний.-М.: Наука, 1975. 357 с.

27. Крапчин А.И., Покровский А.Н., Мальчинов Е.Н. Компоновка и размещение модулей при автоматизации проектирования радиоэлектронной аппаратуры. Автоматика и вычислительная техника, 1965, № 5, с.7-11.

28. Кристофидес Н. Теория графов. Алгоритмический подход. -М.: Мир, 1978, 432 с.

29. Математическое обеспечение ЕС ЭВМ, Вып.9. Минск: Ин-тматематики АН БССР, 1973, с.117-123.

30. Мелихов А.Н., Берштейн Л.С., Курейчик В.М. Применения графов для проектирования дискретных устройств. М.: Наука, 1974.

31. Михалевич B.C. Последовательные алгоритмы оптимизации и их применения. Кибернетика, 1965, № I, с.45-55.

32. Михалевич B.C. Последовательные алгоритмы оптимизации и их применение. Кибернетика, 1965, № 2, с.85-89.

33. Михалевич B.C., Волкович В.Л. Вычислительные методы исследования и проектирования сложных систем. М.: Наука,1982. 286 с.

34. Михалевич B.C., Кукса А.И. Методы последовательной оптимизации в дискретных сетевых задачах оптимального распределения ресурсов. М.: Наука, 1983. - 208 с.

35. Михалевич B.C., Сергиенко И.В., Лебедева Т.Т. и др. Пакет прикладных программ ДИСПРО, предназначенный для решения задач дискретного программирования. Кибернетика, 1981, № 3, с.117-137.

36. Михалевич B.C., Сергиенко И.В., Трубин В.А. и др. Пакет программ для решения задач производственно-транспортного планирования большой размерности (ПЛАНЕР). Кибернетика,1983, № 3, с.57-71.

37. Михалевич B.C., Шор Н.З. Метод последовательного анализа вариантов при решении вариационных задач управления, планирования и проектирования. В кн.: Докл. на 1У Всесоюз. мат. съезде, М., 1961. - 91 с.

38. Пашкеев С.Д., Минязов Р.И., Могилевский В.Д. Машинные методы оптимизации в технике связи. М.: Связь, 1976. -272 с.

39. Пецко А.А., Цветков А.А. Состав и функциональные характеристики пакета математического программирования ПМП-2. -Упр. системы и машины, 1983, № 3, с.94-96.

40. Селютин Б.А. Машинное конструирование электронных устройств. М.: Советское радио, 1977. - 383 с.

41. Сергиенко И.В. О применении метода вектора спада для решения задач оптимизации комбинаторного типа. Управляющие системы и машины, 1975, № 2, с.86-94.

42. Сергиенко Й.В., Каспшицкая М.Ф. Модели и методы решения на ЭВМ комбинаторных задач оптимизации. Киев: Наук, думка, 1981. - 288 -с.

43. Сергиенко И.В., Лебедева Т.Т., Рощин В.А. Приближенные методы решения дискретных задач оптимизации. Киев: Наук, думка, 1980. - 276 с.

44. Стоян 10.Г., Соколовский В.З. Решение некоторых многоэкстремальных задач методом сужающихся окрестностей. Киев: Наук, думка, 1980. - 206 с.

45. Финкельштейн Ю.Ю. Приближенные методы и прикладные задачи дискретного программирования. М.: Наука, 1976. - 264 с.

46. Ханан М., Курцберг Дж.М. Методы размещения. В кн.: Теория и методы автоматизации проектирования вычислительных систем. - М.: Мир, 1977, с.147-225.

47. Хелд М., Карп P.M. Применение динамического программирования к задачам упорядочения. Кибернетический сборник, М.: Мир, 1964, № 9, с.202-218.

48. Ходзинекий А.Н. Об одном алгоритме поиска начального приближения в задачах размещения узлов ЭВМ. -В кн.: Вычислительные аспекты в пакетах прикладных программ. Сб. научн. тр. Киев: ИК АН УССР, 1979, с.39-44.

49. Ходзинекий А.Н. Формализация и алгоритм решения одной задачи распределения интегральных схем по конструктивным узлам ЭВМ. В кн.: Дискретные системы управления. Сб. научн. тр. - Киев: ИК АН УССР, 1980, с.66-68.

50. Юрин С.Н. Единая система автоматизации проектирования ЭВМ.-М.: Советское радио, 1976. 175 с.

51. Яблонский С.В. Об алгоритмических трудностях синтеза минимальных контактных схем. В кн.: Проблемы кибернетики,

52. М.: 1959, вып. 2, с.75-122.

53. Ьигкагс1 R.E., Stiaimann U.H.fJume,%Lco£ inifestiQcitiotis on quoxtiatic assi^ntnttbtfiwStemsr/JcLirai research iooistics Quaite%tutW4*25, Ш,р.т-т. * 7 \

54. QittrWbe. Ofitimat atvcL lubofitimal atg&uthmifot tfve tyuaaiatic cLssignrnetit /г^ввет.— „ 3f. SIflnmz, v. Ю, t!0. z, p. 305-315.

55. Land Л.Н. , $doig A. G. An, automatic rrb&tfwct &f ^oUring discrete ргодъсьттькд ргоЫетз. — bcottonutcrica, 1960,2$, //0.3t p. Ш-Ш.

56. Реализация принципа мобильности при создании ППП ВЕКТОР-2 позволяет эксплуатировать его на различных ЭВМ: ЕЭСМ-6 (мониторная система "Дубна"), .ЕС ЭВМ (ОС ЕС ЭВМ).

57. Настоящим актом подтверждаем внедрение в НИН автоматики(г.Москва) ППП ВЕКТОР-2. Он использован для решения задач оптимального размещения модулей ряда специализированных устройств цифровой аппаратуры.

58. Экономическая эффективность от внедрения ППП' ВЕКТОР-2 составляет 159,75 тыс.руб. Указанная сумма является оценкой экономической эффективности от внедрения ППП ВЕКТОР-2 и не мокет служить основанием для взаимных расчетов.

59. Расчет экономической эффективности от использования ППП ВЕКТОР—2 и справка о долевом участии сторон прилагается.

60. От ИК АН УССР От НИИ автоматики:

61. Руководитель теш Начальник отдела 710

62. Рук.группы, канд.физ.-мат.наукк.т.н.fUyuy л.Ф.Гуляницкий Млн.научн.сотрудни к

63. Начальник лаборатории 713 к.т.н.lu^^w^ В.М.Щемелининu

64. ННИАвтоматпки (г.Москва) 10143 775 15 9751. Итого: 100159 750

65. От института кибернетики АН УССР

66. Руководитель темы чле н-корр.АН УСОВГ