АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Квадратичное программирование

Читайте также:
  1. TRACE MODE 6 SOFTLOGIC: программирование контроллеров (часть 1).
  2. Алгоритмизация и программирование
  3. Визуальное программирование
  4. Выпуклое программирование.
  5. Выпуклое программирование. Задача выпуклого программирования
  6. Геометрическое программирование
  7. Глава 11. Программа прошлого и перепрограммирование.
  8. Глава 12. Программирование целей.
  9. Глава 2. Динамическое программирование.
  10. Динамическое программирование
  11. Динамическое программирование
  12. Интеллектуальное программирование.

 

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

Структура задач квадратичного программирования позволяет широко использовать теорию Куна - Таккера для поиска оптимальных решений. Различные интерпре­тации необходимых условий существования экстремума (4) (п. 4.4) привели к разработке целого ряда алгоритмов, многие из которых преследуют цель свести решение исход­ной квадратичной задачи к вариантам линейного про­граммирования. Что касается достаточных условий экс­тремума, то в данном случае они выражены в требовании выпуклости (вогнутости) функции . Можно показать, что рассматриваемая квадра­тичная форма обладает свойством выпуклости (вверх), если она является неположительно (или отрицательно) определенной в U, т.е. для всех хj, xk, удовлетворяющих принятым ограничениям.

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

при

(5)

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

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

и

Обозначим для удобства через pj - производную , а через производную qi - . Тогда искомые условия можно трактовать так: значения определяются теми решениями системы

(6)

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

Переход к системе (6) позволяет в большинстве случаев упростить процедуру отыскания за счёт использования симплекс-алгоритма. Возвращаясь к (6), заметим, что рассма­триваемая система содержит т+п линейных уравнений с 2(n+m) неизвестными . Предполагая уравнения (6) независимыми (поскольку независимы условия, из которых они получены), можно сказать, что п+т из названных 2(п+т) переменных являются свободными.

Если некоторое решение (6) удовлетворяет требованиям

то среди его компонент должно быть как минимум п+т равных нулю; таким образом, оно может иметь вид «ровно п+т компонент отличны от нуля, ровно п+т компонент равны нулю» или «менее п+т компонент отличны от нуля, более п+т компонент равны нулю».

Очевидно, подобные решения являются базисными, и для отыскания X* должен существовать метод, аналогичный симплекс-методу, оперирующему с базис­ными решениями. Возникает вопрос: нельзя ли сразу, вы­брать произвольно п+т свободных переменных среди положить их равными нулю, а затем определить через них остальные переменные в соответ­ствии, с уравнениями (6)? Ответ, здесь может быть только отрицательным, потому что произвольный выбор решения может привести к нарушению условий . Приходится обращаться к специальным методам определения . Одним из них является так называемый метод Вольфа, предусматривающий исследование задач линейного про­граммирования с целью получить решения задачи квад­ратичного программирования.

 

 


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.003 сек.)