Итерационные методы решения задач математического программирования со специальной структурой

• Автор: Пудова, Марина Владимировна
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2002
• Место защиты: Новосибирск
• Количество страниц: 138 с. : ил

ОГЛАВЛЕНИЕ
Введение

Глава 1. Методы решения узкоблочных задач

1.1. Алгоритм, основанный на методе симплексных погружений

1.1.1. Вычислительная схема метода

1.1.2. Модификация метода для узкоблочных ЗМП

1.2. Алгоритм, основанный на методе Дикина

1.2.1. Вычислительная схема метода Дикина

1.2.2. Алгоритм решения узкоблочных ЗЛП

1.3. Алгоритм, основанный на методе Кармаркара

1.3.1. Краткое описание метода

1.3.2. Модификация метода Кармаркара для узкоблочных задач
1.4. Алгоритм, основанный на методе Ринальди
1.4.1. Краткое описание метода
1.4.2. Алгоритм решения узкоблочных ЗЛП
1.5. Сравнение трудоемкости методов решения узкоблочных задач
Глава 2. Методы решения задач с блочной и ленточной
структурой
2.1. Вычислительные схемы, основанные на методе симплексных погружений
2.2. Вычислительные схемы, основанные на методе Дикина .
2.2.1, Алгоритм решения блочных задач
2.2.2. Алгоритм решения задач с ленточной структурой

2.3. Вычислительные схемы, основанные на методе Кармаркара
2.4. Вычислительные схемы, основанные на методе Ринальди
2.5. Сравнение трудоемкости методов решения блочных и ленточных задач
Глава 3. Исследование устойчивости предложенных
методов
3.1. Исследование устойчивости метода Дикина
3.1.1. Оценка погрешности решения СЛУ методом квадратного корня
3.1.2. Определение гарантированной точности вычисления

выражения 5jv = J2 bjCjdj

3.1.3. Оценка точности итерации метода Дикина
3.2. Исследование устойчивости метода Кармаркара
3.2.1. Гарантированная точность обращения матрицы
по формуле одноранговой модификации
3.2.2. Оценка точности итерации метода Кармаркара
3.3. Устойчивая модификация метода Дикина
Заключение
Приложение . Результаты экспериментов
Список литературы
Введение
При нахождении оптимальных стратегий функционирования иерархических систем возникают задачи линейного программирования (ЗЛП) специального вида, матрицы ограничений которых имеют узкоблочную или блочную с окаймлением структуру. Каждая подсистема в этом случае (обычно соответствующая предприятию) моделируется динамической ЗЛП. Подобные задачи часто содержат несколько тысяч или десятков тысяч ограничений и переменных. Кроме того, для исследования одной иерархической системы число решаемых задач также может быть велико из-за большого числа подсистем и частой корректировки исходных данных. Поэтому актуальным является вопрос о построении эффективных алгоритмов решения задач со специальной структурой. Мы будем говорить, что одна вычислительная схема эффективнее другой, если с использованием первой схемы задача заданной размерности решается с заданной точностью более быстро.
Можно выделить два основных подхода к решению задач специальной структуры - прямые методы и методы, основанные на идеях декомпозиции. В первом случае для решения задач специального вида используются общие методы математического программирования. Методы, принадлежащие ко второму классу, основаны на разложении исходной системы ограничений на подсистемы (блоки), для каждой из которых необходимо решать задачу меньшей по сравнению с исходной размерности.
Простейшим примером ЗЛП, имеющей блочную с окаймлением структуру, является математическая модель функционирования предприятия, состоящего из нескольких филиалов. Каждый филиал производит свой набор продукции, используя при этом как локальные, так и общие ресурсы.
В работе [8] приводится модель функционирования региона, расположенного вдоль магистральной реки, зарегулированной плотинами

Е хз =

щ > М = 1,-,^.
Предполагается, что
1) хд = е/1У, где е = (1,...,1)т, является допустимой точкой;
2) если х - допустимое решение, то сх > 0, а если х* - оптимальное решение, то сх* = 0.
Опишем к-ю итерацию алгоритма Кармаркара. Вначале на шагах 3.1 - 3.5 вычисляется следующая допустимая точка последовательности
хм = ф(хк),
где функция ф(х) определяется следующими операциями:
3.1. Пусть
где Б =с^(ж1, ...,хц).
3.2. Вычисляется ортогональная проекция Бс в нуль-пространстве преобразования В:
с„ = [Е - Вт(ВВт)-1В]Бс. (1.19)
Обращение матрицы ВВТ производится по формуле одноранговой модификации за 0(М/]У) операций.
3.3. Нормируется вектор ср
3.4. Определяется сдвиг где 7 6 (0,1) - параметр.