Методы решения задач линейной оптимизации большой размерности

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

1. МЕТОД РЕШЕНИЯ ПРЯМОЙ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ С БОЛЬШИМ ЧИСЛОМ НЕОТРИЦАТЕЛЬНЫХ ПЕРЕМЕННЫХ
1.1. Нахождение проекции точки на множество решений прямой задачи линейного программирования

1.2. Итерационный метод нахождения решений прямой и двойственной задач (метод ПД)

1.3. Конечная сходимость итерационного метода

1.4. Обобщенный метод Ньютона

1.5. Нахождение проекции точки на множество решений систем линейных уравнений

2. МЕТОД РЕШЕНИЯ ДВОЙСТВЕННОЙ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ С БОЛЬШИМ ЧИСЛОМ ПЕРЕМЕННЫХ
2.1. Нахождение проекции точки на множество решений двойственной задачи линейного программирования

2.2. Итерационный метод нахождения решений двойственной

и прямой задач (метод ДП)

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

3.1. Генераторы тестовых задач
3.2. Программная реализация метода ПД в системе
МАТЬАВ
3.3. Результаты численных экспериментов с программой

3.4. Программная реализация метода ДП в системе
МАТЬАВ

3.5. Результаты численных экспериментов с программой ЕСМ2
3.6. Результаты численных экспериментов с помощью программ нахождения нормальных решений линейных систем
ВЫВОДЫ
ПРИЛОЖЕНИЕ
ЦИТИРОВАННАЯ ЛИТЕРАТУРА

Список обозначений
Яп - мноэюество п-мерных вещественных векторов Щ_ - множество п-мерных вещественных векторов, все компоненты которых неотрицательные 0 - пустое множество 0П - п-мерный нулевой вектор
ап - п-мерный вектор, все компоненты которого равны скаляру а А - матрица т х п
- матрица, транспонированная к матрице А Ь - вектор т х 1 с - вектор п х
х £ X - х принадлежит множеству X х - вектор прямых переменных п х 1 X - допустимое мноэ/сество прямой задачи ЛП X* - множество решений прямой задачи ж* - решение прямой задачи
х* - проекция произвольной точка х £ на мпоснсество решений X* ж* - проекция начала координата на множество решений X*, т.е. нормальное решение прямой задачи ЛП (решение с наименьшей евклидовой нормой) и - вектор двойственных переменных т х 1 и - допустимое множество двойственной задачи ЛП I]* - множество решений двойственной задачи и* - решение двойственной задачи
щ - проекция произвольной точка й £ ПП' на множество решений С/* щ - проекция начала координата на множество решений 11*, т.е. нормальное решение двойственной задачи ЛП /* - оптимальное значение целевой функции задачи ЛП V - неотрицательный вектор дополнительных переменных (у — с — АГи > 0). хТи - скалярное произведение векторов х и у

В третьей строке даны результаты расчетов задач ЛП с 5-ю миллионами переменных, 1000-ю ограничениями, 1%-й заполненностью матрицы А; время расчетов по программе ЕСМ1 составило 16 мин. В четвертой строке приведены результаты в случае, когда задача имела 1000 ограничений, матрица А была полностью заполнена и п = 105; время расчетов было 44 минуты. Обе задачи были решены с высокой точностью (нормы невязок не превосходили 7.1 х 10-7 ). Обе эти задачи не удалось решить другими пакетами.
При решении задач невысокой размерности программа ЕОМ1 обладала примерно такой же эффективностью, что и остальные программы. Как следует из таблицы 3.2, пакет ВРМРБ был лучшим по времени при решении первой тестовой задачи. ЕОМ1 дал второй результат. Вторая тестовая задача быстрее всего была решена пакетом МОЭЕК. ЕОМ1 дал третий результат. Рекордное время для разных пакетов выделялось жирным шрифтом.
Результаты таблиц 3.3 - 3.5 иллюстрируют утверждение теоремы 3.3, согласно которому в итерационном процессе (1.34) можно брать произвольное /3 > 0. В этом случае получается какое-то решение ж* 6 X*, а не проекция вектора а?о X*; кроме того, количество итераций может быть больше, чем две, процесс сходимости сохраняется и при 0 < (3 < /3*. В таблицах 3.3 и 3.4 решались задачи небольшой размерности. В таблице
3.3 приведено 20 расчетов по методу (1.34). В ней приведено I - полное количество шагов по методу Ньютона на всех итерациях, и К - количество итераций, сделанных в процессе (1.34).
Число (3 изменялось от 0.01 до 2 X 104. Из таблицы 3.3 можно заключить, что в данной задаче 1 < /3* < 1.27, так как, начиная с седьмой строки, при всех /3 > 1.27 получались близкие результаты за две итерации (1.34), а время счета равнялось 41-45 сек. При очень больших значениях /3 (например, в последней строке /3 = 2 х 104 ) точность расчетов падала. Это объясняется тем, что задача при больших /3 становится сильно овражной и трудно обеспечить малые невязки. Расчеты при /3 < /3* требовали гораздо больше времени. Например , при /3 = 0