Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9  10  11 | Следующая страница реферата



6.Библиография

7.Приложение 1..................................................................................................................65

8.ПРиложение 2..................................................................................................................67

9.рисунок 1...........................................................................................................................78

 

1. Введение

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

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

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

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

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

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

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

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

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

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

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

Показано, что такое разбиение состоит из конечного числа отрезков, и конечного числа точек переключения траектории решения.

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

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

Составлена и отлажена программа на языке С++, функционирующая в среде операционных систем UNIX (AIX, Solaris) а также Microsoft Windows, реализующая описанные алгоритмы. Указанная программа применена к решению задачи о поиске оптимальных инвестиций в задаче о портфеле ценных бумаг, данные решения и текст программы приведен в приложениях.

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

 

Рекомендуем скачать другие рефераты по теме: реферат предприятие, реферат по русскому.

Категории:

• Информатика, программир-ние

Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9  10  11 | Следующая страница реферата