Некоторые методы решения оптимизационных задач комбинаторного типа и их исследование

• Автор: Ходзинский, Александр Николаевич
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 1984
• Место защиты: Киев
• Количество страниц: 128 c. : ил

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

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

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

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

на подмножества

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

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

приборами

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

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

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

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

ления значений критерия
§ 8. О сравнении алгоритмов
РЕЗУЛЬТАТЫ И КРАТКИЕ ВЫВОДЫ К ГЛАВЕ 2
ГЛАВА 3. ВОПРОСЫ РЕАЛИЗАЦИИ АЛГОРИТМОВ НА ЭВМ
§ I. Решение оптимизационных задач с ограничениями. 86 § 2. Прерывание и восстановление вычислительного процесса при решении задач методом ветвей и
границ и методом вектора спада
§ 3. Планирование вычислительного процесса и создание комбинированных схем алгоритмов
§ А. Функционирование пакета программ при решении
задач
§ 5. Схемы алгоритмов, допускающих распараллеливание вычислений
РЕЗУЛЬТАТЫ М КРАТКИЕ ВЫВОДЫ К ГЛАВЕ 3
ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ
СПИСОК ЛИТЕРАТУРЫ
ПРИЛОЖЕНИЕ

Дискретное программирование является одним из важных разделов прикладной математики. В частности, большое практическое и теоретическое значение имеют исследования, связанные с решением задач комбинаторной оптимизации. Такие задачи возникают в проектировании, планировании, экономике. К настоящему времени разработано значительное число разнообразных методов и алгоритмов решения оптимизационных задач: метод последовательного анализа вариантов Гб, за, 35,34,35.38], метод построения последовательности планов [/6] , локальные алгоритмы №лго] , метод вектора спада [43,44,45 ] и др. Продолжающаяся разработка новых и модификация известных методов объясняется расширением круга решаемых практических задач, а также появлением новых требований, возникающих при создании программ, реализующих алгоритмы этих методов на ЭВМ. Эти требования касаются главным образом возможности организации прикладного программного обеспечения ЭВМ в виде пакетов программ (ПП). В ходе выполнения данной работы учитываются в основном два таких требования:
1. Универсальность алгоритмов. Как правило, ПП разрабатываются для решения не одной, а целого класса оптимизационных задач. По этой причине необходимо, чтобы каждый программный модуль мог быть применен при решении каждой или хотя бы большинства из них.
2. Разнообразие алгоритмов. Как показывает опыт, обычно . не удается заранее определить, какой из алгоритмов окажется наиболее эффективным при решении конкретной прикладной задачи. Поэтому в ПП необходимо включать несколько алгоритмов для решения одних и тех же задач.

ба построения датчика случайных чисел [4]
2. Из того, что является функцией только ,
следует независимость между собой • Кроме того, из равномерного распределения Ьг на [0, I) следует, что вероятность попадания б полуинтервал
[ П-І+Ґ ' 1 , піч) для любого ^ Є (1,..п--ь 4-'/} рав-на їьІч * ПоэтомУ функция распределения случайной величины , ъеУ>...,п} задается формулой:
■ (2.46)
Из (2.46) и из независимости величин %■ , гє{І,.. .,ъ ,
следует, что вероятность получения любого наперед заданного вектора Ж^) равна произведению соответствующих
вероятностей для его компонент:
Р={Ж=сО(і)=Х'!,=П Р{х~х1)=П+2 =&
г~4 г=
3. Функция У является взаимно-однозначным отображением множества векторов {%} на множество перестановок ^ . Это легко доказать, если принять во внимание, что: I) оба эти множества имеют одну и ту же мощность - *ъ/ и 2) для любых Ж'
и %" : если Ж'Ф 7с" , то и р'=У(7і')Фр"-У(Ж,;)
Поэтому вероятность получения произвольной перестановки рє Ф равна вероятности получения соответствующего ей вектора
% = Ц *(р) , то ЄСТЬ ЇРГ
Георема 2.7 доказана.
Описанную процедуру можно модифицировать для получения случайных перестановок, равномерно распределенных по множеству ^ і при .г /г-/} . Это можно сделать, если на