6.3. Проекции при ограничениях на параметры

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

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

Пусть вектор шаг, который следовало бы сделать при отсутствии ограничений. Легко видеть, что произведение.

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

Легко проверить, что нижеследующая процедура эквивалентна алгоритму из раздела 6.2 в следующем изложении:

1) построить матрицу имеющую строк и столбец;

2) пусть для число если строка соответствует переменной, совпадающей со своей границей;

3) пусть для

4) пусть величина обозначает текущее значение последнего элемента в строке матрицы Найдем число Если перейти к пункту 6;

в противоположном случае:

5) пусть это индекс, для которого . Выполнить выметание по строке (т. е. кручение по Гауссу — Жордану на опорном элементе и изменить знак у числа вернуться к пункту 4;

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

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

Проиллюстрируем этот метод численным примером (дальнейшие иллюстрации приведены в разделе 6.12):

Допустим, что в итерации получены следующие величины:

Следовательно, Предположим, что все параметры ограничены отрезком между нулем и единицей. Таким образом, совпали со своими нижней и верхней границами

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

5) , поэтому мы выполняем кручение на элементе получая новые таблицы:

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

Как и ожидалось, могли бы элементы, отмеченные звездочками в равенстве заменить нулями, не меняя результата.

Фактический шаг а будет отличаться от на некоторый множитель, т. е. Множитель ограничен отрезком: причем величина ртах определяется требованием, чтобы вектор оставался допустимым, т. е. мы должны иметь:

Следовательно,

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