§ 11.5. РЕШЕНИЕ ЗАДАЧИ КВАДРАТИЧНОГО ПРОГРАММИРОВАНИЯ

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

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

преобразуем сформулированную в § 11.4 задачу квадратичного программирования для шага к такой:

найти экстремум квадратичной функции

при линейных ограничениях:

Чтобы превратить неравенства (11.71) и (11.72) в равенства, введем дополнительные переменные

Тогда ограничения (11.71) и (11.72) примут вид:

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

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

С учетом выражений (11.75), (11.76) критерий (11.70) можно представить так:

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

Значения вычисляемые на каждом шаге решения задачи квадратичного программирования, удобно свести в основные и промежуточные таблицы. Первые содержат значения коэффициентов на данном, например шаге (табл. 11.1), вторые — промежуточные

Таблица 11.1 (см. скан) Основная таблица шага оптимизации

Таблица 11.2 (см. скан) Промежуточная таблица шага оптимизации

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

Промежуточная таблица (см. табл. 11.2) отличается тем, что в верхней части она содержит коэффициенты новой точки, а в нижней — промежуточные коэффициенты

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

Правила перехода от одной таблицы к другой формулируются следующим образом.

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

Пусть — элемент, стоящий на пересечении первой строки и заменяющего столбца. Последний определяет новую заменяющую переменную

2. Разделим модуль выбранного в предыдущем пункте элемента Сор на соответствующий диагональный элемент нижней части таблицы, если и разделим на модули соответствующих элементов заменяющего столбца те элементы первого столбца верхней части таблицы для которых имеют тот же знак, что и Сор.

Строка, реализующая минимум отношений является заменяющей. Элемент, стоящий на пересечении заменяющей строки и заменяющего столбца или называется опорным элементом. Если заменяющая строка принадлежит верхней части таблицы, то в промежуточной таблице на место переменной которой соответствует заменяющий столбец, ставится переменная, которой соответствует заменяющая строка. Если заменяющая строка принадлежит нижней части таблицы, то заменяется свободной переменной

3. Чтобы получить элементы столбца промежуточной таблицы, соответствующего заменяющему, следует разделить элементы заменяющего столбца на опорный элемент.

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

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

Если первая заменяющая строка лежит в нижней части таблицы, то вторая заменяющая строка совпадает с первой.

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

Рассмотренные правила определяют алгоритм квадратичного программирования, который может быть реализован на ЦВМ.

Пример 11.6. Минимизировать критерий оптимальности

при ограничениях

Вводим вспомогательную переменную и обращаем неравенство в равенство:

В качестве базисного решения на первом шаге примем Тогда можно записать

Таблица 11.3

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

Таблица 11.4 (см. скан)

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

Таблица 11.5 (см. скан)

На втором шаге в качестве заменяющего столбца по первому правилу следует выбрать столбец Сравнивая отношения , можно убедиться, что второе меньше. Это означает, что при увеличении в начале обращается в нуль переменная а затем уже производная

Заменяющей является третья строка верхней части таблицы, следовательно, переменную в дальнейшем следует считать независимой. Используя правила, строим промежуточную таблицу второго (табл. 11.6) и основную таблицу третьего шага (табл. 11.7) (переход к переменным опускаем). Поскольку в последней

Таблица 11 .6 (см. скан)

таблице элемент, стоящий на пересечении первой строки нижней части таблицы со столбцом не равен нулю, то этот столбец и следует выбрать в качестве заменяющего. Сравнивая отношенияи убеждаемся, что первое меньше и выбираем в качестве заменяющей вторую строку нижней части таблицы. Построив промежуточную таблицу третьего (табл. 11.8) и основную таблицу четвертого шага (табл. 11.9), убеждаемся, что последняя таблица по первому правилу соответствует оптимальной точке. Минимальное значение достигается в точке т. е. на ограничении.

Таблица 11.7 (см. скан)

Решение задач методом Била налагает на приращения оптимизируемых переменных требование положительности (11.72). При решении задач оптимизируемые параметры в зависимости от выбора

Таблица 11.8 (см. скан)

Таблица 11.9 (см. скан)

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

Для устранения этого недостатка можно воспользоваться несложным дополнительным алгоритмом, позволяющим применять метод Била в случае как положительных, так и отрицательных приращений оптимизируемых параметров.

Критерий оптимальности (11.77) представляет собой сумму свободного, линейных и квадратичных членов. Линейные члены имеют вид квадратичные — Если один из параметров, например при оптимизации уменьшается, т. е. его приращение отрицательно, достаточно в исходном функционале изменить знак перед коэффициентом при соответствующем и в дальнейшем рассматривать положительные изменения этого параметра. При переходе к следующей точке необходимо учесть знак «-»:

Пример 11.7. Оптимизируем следящей системы, рассмотрен ной в примере 9,2, принимая град-сек, сек и вводя ограничения Мсек.

На шаге оптимизации функционал (9.34) может быть представлен в квадратичной форме:

где

Введем обозначения

За исходные значения примем

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

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

Таблица 11.10 (см. скан)

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

или, учитывая дополнительные переменные

Получим основную таблицу первого шага (табл. 11.11). Промежуточной для первого шага является табл. 11.12, основной для второго шага — табл. 11.13.

Таблица 11.11 (см. скан)

Таблица 11.12 (см. скан)

Таблица 11.13 (см. скан)

(кликните для просмотра скана)

(кликните для просмотра скана)

Таблица 11.21 (см. скан)

Таблица 11.22 (см. скан)

В табл. 11.14-11.22 приведены выполненные на ЦВМ вычисления (таблицы изменения знаков коэффициентов не показаны).

Оптимизация пооисходит за четыре шага. Исходные данные:

Первый шаг оптимизации:

Второй шаг:

Третий шаг:

Четвертый шаг:

Приведенный пример достаточно хорошо иллюстрирует метод последовательной оптимизации.