Контрольная работа на тему Метод Чарнса и Купера и Методы решения задач квадратичного программирования

Содержание


1. Метод Чарнса и Купера: сущность и применение (дробно-линейное программирование) 3
Введение 3
1.1. Способ Чарнса для случая неположительности квадратичной формы 3
1.2. Постановка задачи ДЛП 5
1.3. Решение задачи ДЛП 5
1.4. Описание алгоритма решения задачи ДЛП 7
1.5. Применение метода ДЛП 7
2. Методы решения задач квадратичного программирования 8
2.1. Формулировка задачи 8
2.2. Основные понятия задачи квадратичного программирования 8
2.3. Существование и единственность решения 12
2.4. Идентификация решения 14
2.5. Метод Вулфа 16
2.6. Пример применения метода Вулфа 18
Список используемой литературы 25


1. Метод Чарнса и Купера: сущность и применение (дробно-линейное программирование)

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

Введение

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

1.1. Способ Чарнса для случая неположительности квадратичной формы

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

Ax = b
2Dx - Aт ? + v =- ст
xj*vj*=0, ?j? 1,... ,n
не будет иметь решения при x??0 и v??0.
Во-вторых, даже если задача квадратичного программирования имеет оптимальное решение, нет уверенности, что при окончании вычислительной процедуры мы получаем именно его.
Следует отметить, что неположительная квадратичная формах может быть превращена в отрицательно определенную путем малого изменения диагональных элементов матрицы D. Точнее, если xтDx - неположительная форма, то xт(D+?I)x - уже отрицательно определенная форма при любом ?. Действительно, xтDx??0 при любом х, а ?xт при любом х?0. Таким образом, xт(D+?I)x при любом х?0.Следовательно, если мы имеем задачу квадратичного программирования с неположительной квадратичной формой, то после незначительного уменьшения диагональных элементов матрицы D мы преобразуем форму в отрицательно определенную. Ввиду малости изменений можно рассчитывать, что решение преобразованной задачи будет близким к решению исходной. Изменение формы будет существенно влиять на результат лишь в том случае, когда в исходной задаче форма xтDx не знакопостоянна и задача имеет неограниченное решение. Однако, как и в задачах линейного программирования, при решении достаточно хорошо сформулированных практических задач такой случай не возникает. Указанное преобразование исходной задачи в случае неположительной формы предложено Чарнсом.
Вообще говоря, данный метод применим и в случае, когда форма xтDx неположительная. Поэтому можно сначала попытаться использовать обычную процедуру, не преобразуя D.
Безусловно интересно, как заранее определить, является ли квадратичная форма положительно определенной, отрицательно определенной и т. д. В простых случаях это можно, сделать непосредственной проверкой. В общем случае, однако требуется найти характеристические числа матрицы D. Эта задача может оказаться весьма трудной, и поэтому вид квадратичной формы