ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ 7
1. МЕТОД РЕШЕНИЯ ПРЯМОЙ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ С БОЛЬШИМ ЧИСЛОМ НЕОТРИЦАТЕЛЬНЫХ ПЕРЕМЕННЫХ 13
1.1. Нахождение проекции точки на множество решений прямой задачи линейного программирования .................. 13
] .2. Итерационный метод нахождения решений прямой и двойственной задач (метод Г1Д).............................. 23
1.3. Конечная сходимость итерационного метода ......... 26
1.4. Обобщенный метод Ныотона........................ 28
1.5. Нахождение проекции точки на множество решений систем линейных уравнений ............................... 29
2. МЕТОД РЕШЕНИЯ ДВОЙСТВЕННОЙ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ С БОЛЬШИМ ЧИСЛОМ ПЕРЕМЕННЫХ 31
2.1. Нахождение проекции точки на множество решений двойственной задачи линейного программирования............. 31
2.2. Итерационный метод нахождения решений двойственной
и прямой задач (метод ДП) ........................ 38
3. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ И ВЫЧИСЛИТЕЛЬНЫЕ ЭКСПЕРИМЕНТЫ 40
3.1. Генераторы тестовых задач....................... 40
3.2. Программная реализация метода ПД в системе
МАТЬАВ............................................ 44
3.3. Результаты численных экспериментов с программой
ЕСМ1.............................................. 46
3.4. Программная реализация метода ДП в системе
МАТЬАВ............................................ 62
2
3.5. Результаты численных экспериментов с программой
Ев М2........................................... 63
3.6. Результаты численных экспериментов с помощью программ нахождения нормальных решений линейных систем 69
ВЫВОДЫ 74
ПРИЛОЖЕНИЕ 75
ЦИТИРОВАННАЯ ЛИТЕРАТУРА 91
3
Список обозначений
Яп - множество п-мерных вещественных векторов Щ. - множество п-мериых вещественных векторов, все компоненты которых неотрицательные 0 - пустое мпооіссство 0П - п-мерный нулевой вектор
ап - п-мерный вектор, все компоненты которого равны скаляру а А - матрица т, х п
АТ - матрица, транспонированная к матрице А Ь - вектор т х 1 с - вектор п х 1
х Є X - х принадлеоісит множеству X х - вектор прямых переменных п х 1 X - допустимое множество прямой задачи ЯП X* - множество решений прямой задачи х¥ - решение прямой задачи
х* - проекция, произвольной точка х Є Яп на мноэюество решений X* ж* - проекция начала координата на множество решений Хя, т.е. нормальное решение прямой задали ЯП (решение с наименьшей евклидовой нормой) и - вектор двойственных переменных т х I и - допустимое множество двойственной задачи ЯП V* - мнооісество решений двойственной задачи и* - решение двойственной задали
й* - проекция произвольной точка и Є Ят на множество решений Ь\ •и* - проекция начала координата на множество решений 11+, т.е. нормальное решение двойственной задачи ЯП /* - оптимальное значе7іие целевой функции задачи ЯГІ у - неотрицательный вектор дополнительных переменных [и — с - АТи > 0). хти - скалярное произведение векторов х и и
4
[3. а - вспомогательные параметры є - параметр регуляризации
В{г) - диагональная матрица, у которой г—й диагональный элемент есть і—я компонента вектора г - диагональная матрица в обобщенную матрицу Гессе а+ - вектор а, у которого все отрицательные компоненты заменены па пули
||а|| - евклидова норма вектора а IIа II оо ~ чебышевская норма вектора а ЛП - линейное программирование Р - прямая задача ЛП Г) - двойственная задача ЛГІ
ПД - метод нахождения решений прямой и двойственной задач ДП - метод нахождения решений двойственной и прямой задач
5
Список программ, составленных для системы
MATLAB
Code 1 - Генератор тестовых задач линейного программирования . . 41
Code 2 - Генератор тестовых задач линейного программирования
с целочисленными элементами.............................42
Code 3 - Генератор линейных систем уравнений с
неотрицательными переменными............................43
Code 4 - Генератор линейных систем, уравнений...................44
Code 5 - Программа EGM1 для решение задач ЛП....................45
Code 6 - Программа EGM2 для решения задач ЛП....................62
Code 7 - Программа SS1 для решения линейных систем..............70
Code 8 - Программа SS2 для решения линейных систем
с неотрицательными переменными..........................71
б
ВВЕДЕНИЕ
Теории и методам решения задач линейного программирования (ЛП) и систем линейных неравенств посвящено огромное количество исследований. Укажем лишь несколько опубликованных на русском языке монографий [2], [4], [51, [131, [18] - [22], [26J, [29], 130], [33], [36], [42], [43]. Огромный интерес к задачам ЛП определяется прежде всего их экономической содержательностью, многочисленными практическими приложениями и применением в качестве вспомогательных процедур во многих численных методах нелинейной оптимизации. Несмотря на продолжающееся повышение производительности вычислительной техники, всегда актуальным остается возможность решения задач линейного программирования очень большой размерности.
Первоначально исследования в области численных методов ЛП концентрировались в основном па симплекс-методе. Далее разрабатывались разнообразные итерационные методы, а после опубликования статей [24], [14], [15], [16], [52] внимание многих исследователей переключилось па методы внутренних точек. При этом возникли новые формулировки задач ЛП и появились новые формы задания необходимых и достаточных условий оптимальности (см. например, [60], [17], [49]). Укажем на специальный выпуск журнала Optimization Methods &: Software [61], целиком посвященный методу внутренней точки, а также обзор [50].
В работах советских математиков в 70-х годах активно разрабатывался подход к задачам ЛП, основанный на использовании метода внешних штрафных функций (квадратичная функция штрафа). Хорошо известны работы в этом направлении, которые проводились А.С. Антипиным, Ф.П. Васильевым, Е.Г. Гольштейном, И.И. Ереминым, Б.Т. Поляком, Б.С. Разумихиным, II.В. Третьяковым и другими исследователями из МГУ, ИПУ, ЦЭМИ, МММ УрО РАН, ВЦ РАН [3], [13], [51], |32]-[35), [42], [44]. Примерно в это же время в США близкие исследования проводились
О.Мангасарьяиом и его сотрудниками. В их работах [53]-[55] основное внимание уделялось нахождению нормальных решений в задачах ЛП,
7
- Киев+380960830922