Новости    Библиотека    Байки    Ссылки    О сайте


предыдущая главасодержаниеследующая глава

2.6. Квадратичное программирование. Свойства решений задачи

Задачи квадратичного программирования, как отмечалось в гл. 1, имеют (следующие особенности: целевая функция) представляет собой сумму вида


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


обычно присутствует требование не отрицательности переменных.

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

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


Можно показать, что рассматриваемая квадратичная форма обладает свойством выпуклости (вверх), если она является не положительно (или отрицательно) определенной в V, т. е.


для всех xj, хk, удовлетворяющих принятым ограничениям.

Учитывая сказанное, обратимся к задаче: найти


при


(2.11)


Положив


будем говорить в дальнейшем только о глобальном экстремуме z.

Рассмотрим необходимые условия существования X*, z*. Здесь


и



Обозначим для удобства через - производную dΦ/dxj, а через qi - производную dΦ/dλi. Тогда искомые условия можно трактовать так: значения x*j(j = 1,....,n) определяются теми решениями системы

(2.12)

которые удовлетворяют требованиям


Переход к системе (2.12) позволяет в большинстве случаев упростить процедуру отыскания x*j (j = 1,...,n) за счет использования, как будет показано ниже, симплекс- алгоритма. Возвращаясь к (2.12), заметим, что рассматриваемая система содержит m+n линейных уравнений с 2 (n+m) неизвестными x*j, p*j, λi*, q*i. Предполагая уравнения (2.12) независимыми (поскольку независимы условия, из которых они получены), можно сказать, что n+m из названных 2 (n+m) переменных являются свободными.

Если некоторое решение (2.12) удовлетворяет требованиям x*jp*j = 0 (j = 1,...,n), λ*iq*i = 0 (i = 1,...,m), то среди его компонент должно быть как минимум n+m равных нулю; таким образом, оно может иметь вид "ровно n+m компонент отличны от нуля, ровно n+m компонент "равны нулю" или "менее n+m компонент отличны от 0, более n+m компонент равны 0".

Очевидно, подобные решения являются базисными, и для отыскания X* должен существовать метод, аналогичный симплекс-методу (см. гл. 1), оперирующему с базисными решениями. Возникает вопрос: нельзя ли сразу выбрать произвольно n+m свободных переменных среди x*j, p*j, λi*, q*i, положить их равными нулю, а затем определить через них остальные переменные в соответствии с уравнениями( 2.12)? Ответ здесь может быть только отрицательным, потому что произвольный выбор решения может привести к нарушению условий ∀x*j≥0, ∀p*j≥0, ∀λi*≥0, ∀q*i≥0. Приходится

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

предыдущая главасодержаниеследующая глава





Пользовательский поиск


Диски от INNOBI.RU




© Злыгостев Алексей Сергеевич, подборка материалов, оцифровка, статьи, оформление, разработка ПО 2001-2017
При копировании материалов проекта обязательно ставить активную ссылку на страницу источник:
http://informaticslib.ru/ "InformaticsLib.ru: Информатика"