11.3. Постановка задачи и ее решение

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

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

Задача оптимизации может быть сформулирована следующим образом: минимизировать к так, чтобы

Эта формулировка эквивалентна исходной задаче, потому что для заданных минимальное значение , удовлетворяющее ограничениям (11.14), равно . В этом смысле новая переменная Я может рассматриваться как целевая функция. Матричная форма записи уравнений (11.13) имеет следующий вид:

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

Так как мы имеем систему из уравнений относительно

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

где принимает значения в диапазоне от 1 до Если каждый из коэффициентов а положителен, минимум X достигается, когда все выступающие здесь в качестве условных переменных, равны нулю. Соответствующее им значение X равно . В заключение рассмотрим, как следует выполнять необходимые алгебраические операции над системой уравнений, представленной в табл. 11.1 [или вообще над системой (11.15)] для получения зависимой переменной X в виде (11.16). На лервом этапе мы ищем так

Таблица 11.1

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

Начнем с табл. 11.1. Положим каждую из независимых переменных

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

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

Таблица 11.2

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

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

Возвращаясь к табл. 11.1 и выбрав в качестве «ведущего 1-й столбец, мы видим, что для уменьшения Я следует изменять в положительную сторону, причем максимально допустимое значение определяется величиной Поэтому 6-я строка становится ведущей; результаты перестановки приведены в табл. 11.3. Две последующие перестановки, показанные в табл. 11.4 и 11.5, приводят к окончательному решению.

Таблица 11.3

Таблица 11.4

Таблица 11.5

Перечислим формальные правила выбора ведущего элемента в столбце:

Случай 1. Независимая переменная относится к переменным х (этот случай имеет место при первых перестановках), а) Выделить знак коэффициента в строке X.

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

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

минимально.

г) При отрицательном знаке выбрать в качестве ведущего элемент, для которого отношение

максимально.

Случай 2. Независимая переменная относится к переменным у (это достигается после первых перестановок).

а) Выделить знак коэффициента в строке X.

б) При положительном знаке перейти к следующему столбцу, в противном случае

в) выбрать в качестве ведущего элемент, для которого отношение

максимально.

После выбора описанным методом ведущего элемента нужна формализованная методика для получения новой системы уравнений с переставленными переменными. Она строится на основе алгоритма перестановки Штайфеля [7].