Cтраница 3
Матрица В квадратная, неособенная и соответствует обычной базисной матрице симплекс-метода; S - матрица размера mXs где 0 s л - т, и связанные с ней переменные xs называются супербазисными. Небазисные переменные XN, как и в симплекс-методе, принимают значения, равные одной из своих границ. [31]
Иногда используется иное ( неэрмитово) представление для базисных матриц. [32]
Мы теперь рассмотрим вопрос о получении структурного разложения новой базисной матрицы А [ /, J ], считая, что описанные в предыдущих пунктах предварительные преобразования структурного разложения старой базисной матрицы уже сделаны. Случаи, которые могут представиться, аналогичны случаям пункта 2.1 второй главы, где рассматривалось преобразование матрицы D [ J, I ], обратной к базисной матрице. Мы эти случаи рассмотрим в том же порядке, как это было сделано во второй главе. [33]
В случае отсутствия места в массиве коэффициентов для обратной базисной матрицы формирование очередного h - вектора происходит в буфере обратной базисной матрицы. После заполнения буфера сформированная порция выводится на МД с ключом записи, равным. [34]
В результате выполнения серии описанных шагов изменяется структурное разложение базисной матрицы. Для дальнейшего, однако, удобно сохранить старые обозначения всех хранимых величин. [35]
У имеет то Ч положительных компонент, и рассмотрим базисную матрицу В, ассоциированную с этим решением. Она должна иметь форму, показанную на рис. 4.3. Так как все базисные переменные положительны и bjkxajzQ, то коэффициенты при х 2 и х22 в последних 7 строках равны нулю. Если 7я0, то, так как число столбцов, соответствующих переменным у, не превышает 0, последние q строк в В зависимы, что невозможно. [36]
Это говорит о том, что в методе непосредственного обращения базисной матрицы плохая обусловленность одного из базисов ограничивает точность получения всех последующих базисов в отличие от метода треугольного разложения. [37]
Преобразовывая таблицу таким образом, мы получаем таблицу, соответствующую новой базисной матрице. [38]
Переменные х далее разделяются на множества зависимых и независимых путем анализа базисных матриц. Это расчленение позволяет исключить зависимые переменные и блочные ограничения из задачи, что приводит к проблемам меньшей размерности. При исключении зависимых переменных теряется контроль за выполнением условий их неотрицательности. Таким образом, можно сказать, что эти ограничения ослабляются, релаксируются, и требуются дополнительные итерации, определяющие такое новое расчленение, чтобы в конечном счете условия неотрицательности оказались выполненными. Поскольку, как было указано Джоффрионом [1], концепция релаксации ограничений является объединяющей идеей, в рамках которой может быть понята работа всех этих методов, мы начнем с обсуждения этой концепции. [39]
Наличие матрицы D [ J, I ], обратной к базисной матрице, позволяет находить решения систем линейных уравнений, встречающихся на очередном шаге метода, существенно экономнее, чем прямое их решение. В той вычислительной схеме, которую мы здесь рассмотрим, помимо базисной пары ( /, J) и матрицы D [ J, I ] к началу шага предполагаются известными столбец x [ J, строка г /, [ / ], а также текущее значение Coc [ J ] - x4J ] yi [ [ ] - b [ I ] функции цели. [40]
Предположим, что хв - - оптимальное базисное решение и В - базисная матрица этого решения. [41]
На первом шаге решения вспомогательной задачи ( для определения исходной базисной пары) базисная матрица бывает единичной, если Т - N. Единичную матрицу в качестве А [ Iq, / о ] часто выбирают и в других случаях. [42]
Пересчет обратной матрицы, При смене базисной пары могут встретиться различные случаи изменения базисной матрицы, и для перехода к следующему шагу метода нужно получить новую обратную. Ниже мы получим соответствующие формулы. [43]
Итак, предположим, что к началу очередного шага метода последовательного улучшения в базисной матрице А [ М, J ] выделена квадратная неособенная специальная матрица А [ 70, / 0 ] максимального ранга. Это значит, что / 0 а М0, Jo c J Л N0, и строки матрицы А [ М0 / 0, J f No ] линейно выражаются через строки матрицы A [ I0, J Л о ] - Последнее требование можно сформулировать в симметричной эквивалентной форме: столбцы матрицы А [ М0, ( J C-No) Jo ] являются линейными комбинациями столбцов матрицы A [ Mo, Jo ] - Преобразования разбиения (3.1) при смене базисного множества получаются объединением случаев горизонтального и вертикального окаймления. [44]
При большом числе шагов метода последовательного улучшения длина последовательностей (3.2) (3.4) молет существенно превзойти размерность базисной матрицы. [45]