Курсовая работа (т): Решение и корректировка решений близких задач линейно-квадратичного программирования

Таким образом,  для любого плана , что и означает оптимальность плана х.

Необходимость (доказательство от противного). Пусть х - оптимальный план, а  - невырожденный опорный план задачи (1.1) - (1.3).

Предположим, что, вопреки утверждению, соотношения (1.19) не выполняются. Для определённости предположим, что для некоторого  соотношения (1.19) нарушаются следующим образом:  при .

Построим вектор  с компонентами

; , ; . (1.21)

Тогда, очевидно, вектор  при всех  удовлетворяет основному ограничению, т.е. является псевдопланом задачи. Покажем, что при достаточно малых  он является и ее планом. Для этого проверим на нем прямые ограничения.

Поскольку , то при всех достаточно малых  будут выполняться неравенства .

Так как , то при любом  будут справедливы неравенства

 (т.к. х - план задачи).

Рассмотрим . В силу невырожденности (1.11) опорного плана на векторе  выполнены строгие неравенства . В силу (1.21) вектор линейно зависит от , и поэтому его норма будет сколь угодно мала при достаточно малом . Следовательно, при достаточно малом  будут выполнены неравенства .

Итак показано, что , такое, что при всех , , вектор  является планом задачи (1.1) - (1.3). Учитывая квадратичную зависимость  от значения , заключаем, что, и поэтому знак  при достаточно малом  не влияет на знак  (1.17).

Оценим на векторе  (1.21) приращение целевой функции

при достаточно малом . Отсюда имеем  при достаточно малом , что противоречит оптимальности плана х.

Другие случаи нарушения соотношений (1.19) исследуются аналогично.

Пару , на которой выполняются соотношения (1.19), называют оптимальным опорным планом.

Достаточное условие субоптимальности

Пусть  - опорный план задачи (1.1) - (1.3). Рассмотрим для него линейную часть формулы при ращения (1.17)

. (1.22)

Найдём максимум функции  (т.е. величину максимального уменьшения линейной части формулы приращения) на таких псевдопланах , для неопорных компонент которых выполняются ограничения (1.3), т.е. в случае соблюдения ограничений ,

Указанное максимальное значение достигается на векторе :

 при , ,

и равно числу

 (1.23)

Число  (1.23) называют оценкой субоптимальности опорного плана , что оправдано тем, что с учетом (1.22) из формулы приращения (1.17) при  следует неравенство

 (1.24)

которое оценивает сверху отклонение по значению целевой функции плана х от оптимального плана .

Теорема 1.5 (достаточное условие субоптимальности) При любом  для ε - оптимальности плана х достаточно существования такой опоры , при которой для оценки субоптuмальности  опорного плана  выполняется неравенство

Доказательство следует из формулы (1.24):  и определения ε - оптимальности плана (1.4).

Очевидно, что в отличие от задачи ЛП, оценка (1.23) всегда будет оценкой сверху для плана х, за исключением случая оптимального опорного плана , когда . Это объясняется тем, что в отличие от линейной в линейно-квадратичной задаче оценки , зависят не только от опоры, но и от плана х. А это объясняется тем, что целевая функция (1.1) квадратичная. При нахождении формулы приращения (1.17) была выделена линейная часть приращения, а нелинейность содержится в слагаемом . При вычислении же оценки  (1.23) оптимизировалась только линейная часть формулы приращения.

1.3 Проблема построения решений близких задач квадратичного программирования

Основной вопрос при решении задачи (1.1) - (1.3) состоит в построении оптимального плана . Тут же возникает вопрос: как изменится оптимальный план и оптимальное значение функции при изменении параметров задачи? (проблема чувствительности). Для ответа на поставленный вопрос, надо найти коэффициент чувствительности.

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

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

2. Двойственная задача. основные понятия и утверждения

Согласно правилу составления двойственных задач, двойственная задача для задачи (1.1) - (1.3) имеет вид:

 (2.1)

Задача (1.1) - (1.3) называется прямой, а (2.1) - двойственная к ней.

Совокупность , удовлетворяющая ограничениям двойственной задачи (2.1), называется двойственным планом задачи. Причём  - сопровождающий опору псевдоплан.

Решение  задачи (2.1) называется оптимальным двойственным планом. Решения  задач (1.1) - (1.3) и (2.1) удовлетворяют следующим соотношениям двойственности, выражающим тесную связь между прямой и двойственной задачей:

) для существования решения  прямой задачи необходимо существования решения  двойственной задачи;

) оптимальные значения прямой и двойственной  целевых функций равны:

) для любого прямого  и двойственного  планов выполняется неравенство:

) если на некоторой паре {} из прямого и двойственного планов выполняется равенство , то  - решение задач (1.1) - (1.3), (1.2).

Копланом задачи называется вектор

 (2.2)

Для согласования двойственного плана должны выполнятся условия:

 (2.3)

Пара из коплана и опоры задачи называется опорным копланом.

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

 (2.4)

3. Классификация методов решения линейно-квадратичных задач

Исходя из соотношений (1.19) критерия оптимальности, а также с учетом формул (1.14) - (1.16), которые определяют векторы потенциалов и оценок, следует структура оптимального плана  задачи (1.1) - (1.3):

) опорные компоненты ,  "отвечают" только за соблюдение основного ограничения (1.2) и могут принимать любые значения из отрезков: , (предпочтительнее, конечно, вариант, когда все последние неравенства строгие, т.е. случай невырожденности опорного плана , что делает справедливой необходимую часть критерия оптимальности);

) неопорные компоненты , , делятся на две группы: одни из них принимают критические значения ( или ) в сочетании с определенным знаком оценок  (см. (1.19)); вторая часть принимает некритические значения () с одновременным равенством нулю их оценок. При этом очевидно, что поскольку оценки зависят от плана, то любой малый сдвиг от точки  сразу нарушит равенство нулю оценок компонент второй группы (некритических компонент), т.е. сразу будет нарушена третья группа соотношений из (1.19). Если при этом у компонент, принимающих критические значения, оценки ненулевые, то малый сдвиг от точки  не изменит знаки этих оценок, т.е. при малом сдвиге две первые группы соотношений из (1.19) будут выполняться.

Таким образом, можно выделить, две группы оптимальных признаков плана задачи (1.1) - (1.3):

) устойчивые признаки:

 (3.1)

) неустойчивые признаки:

 (3.2)

На вышеизложенном анализе структуры оптимального плана задачи (1.1) - (1.3), на разделении оптимальных признаков на две группы (3.1) и (3.2) и базируются прямые методы решения этой задачи.

Направление улучшения плана в случае невыполнения соотношений оптимальности (1.19), т.е. в случае невыполнения оптимальных признаков (3.1), (3.2) подсказывает доказательство необходимой части критерия оптимальности.

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

Если для начального опорного плана оценки всех неопорных компонент не равны нулю, то, как и в линейной задаче, все неопорные компоненты плана можно направить к соответствующим границам ( или ) прямых ограничений (в соответствии со знаком ) в надежде, что знаки оценок не изменятся, и при шаге вдоль выбранного направления, равном единице, будут выполнены условия (1.19) критерия оптимальности с критическими значениями для " (устойчивые (3.1) и неустойчивые (3.2) признаки для критических значений ).

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

Метод первого порядка и метод второго порядка различаются множествами накапливаемых оптимальных признаков и, в соответствии с этим - способами накопления этих признаков.

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

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