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

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

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

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

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

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

Розглядається застосування вказаного методу до вирішення параметричної задачі квадратичного програмування з параметром у правих частинах обмежень, шляхом зведення зазначеного завдання до кінцевого числа задач квадратичного програмування без параметра.

У силу того, що рішення параметричної задачі квадратичного програмування з параметром у правих частинах обмежень виявляється кусково-лінійною функцією, вихідна задача зводиться до покриття області допустимих значень параметра відрізками, на яких функція рішення лінійна по параметрі з постійними коефіцієнтами, що залежать тільки від значення функції в лівій точці відрізка.

Показано, що таке розбиття складається з кінцевого числа відрізків, і кінцевого числа точок перемикання траєкторії рішення.

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

Поставлено завдання пошуку оптимального вкладення в задачі про портфель цінних паперів, що є економічною інтерпретацією параметричної задачі квадратичного програмування.

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

Вказані можливі шляхи спрощення процедури пошуку рішення задачі квадратичного програмування з параметром у правих частинах обмежень шляхом відмови від розв'язання задачі квадратичного програмування в точках перемикання траєкторії.

2.Аналітіческій огляд

Для вирішення задач лінійного програмування з лінійними обмеженнями можуть застосовуватися різні методи вирішення. Для побудови таких методів використовується як правило підхід, який передбачає завдання квадратичного програмування, у певному сенсі розширенням задачі лінійного програмування.

Результатом застосування такого підходу є група методів заснованих на простроеніі апроксимації вихідної квадратичної задачі послідовністю задач лінійного програмування, а також різні узагальнення лінійного симплекс-методу на випадок опуклій функції-критерію.

Розглянутий в даній роботі метод субоптімізаціі на многовидах являє собою результат зовсім іншого підходу до розв'язання задачі квадратичного програмування. Процедура методу субоптімізаціі будується для більш загального класу задач лінійного програмування, причому вказується клас задач, для яких цей метод виявляється досить ефективним.

При цьому завдання квадратичного програмування виявляється окремим випадком завдання опуклого програмування, для якої метод субоптімізаціі дозволяє звести рішення вихідної задачі до вирішення кінцевого числа систем лінійних рівнянь.

3. Теоретична частина

3. Задача квадратичного програмування (непараметричних випадок).

3.1 Постановка завдання:

Завданням квадратичного програмування будемо називати задачу такого вигляду:

(3.1.1)

тут x -вектор стовпець розміру n , C - вектор-рядок розміру 1 ' n , D - матриця розміру n ' n , симетрична і невід'ємне певна ( D