Cтраница 2
Общий объем памяти, требуемый для размещения числовой информации при решении задачи линейного программирования с п - - т переменными и т ограничениями типа ( VIII, 195), исключая память, необходимую для размещения программы вычислений, складывается из массивов: 1) для размещения матрицы обобщенных векторов Ys: ( п т) ( т 3) ячеек; 2) для размещения обратной матрицы исходного базида: т2 ячеек; 3) для размещения коэффициентов разложения небазисных векторов: 2т или т2 ячеек, если матрица коэффициентов разложения небазисных векторов запоминается полностью. [16]
Интересующие нас коэффициенты разложения вектора по базису находим из системы (3.14), которая, как уже отмечалось, имеет единственное решение. [17]
Этот вариант требует для хранения коэффициентов разложения небазисных векторов только двух массивов ( рабочего и эталонного) по т ячеек в каждом. Основная идея заключается в сравнении приращения критерия оптимальности только для двух небазисных векторов, в результате чего находится вектор, дающий наибольшее приращение, который размещается в эталонном массиве. В дальнейшем каждый следующий небазисный вектор сравнивается с эталонным и если он дает большее приращение критерия оптимальности, то его коэффициенты разложения располагаются в эталонном массиве. [18]
Однако можно избежать необходимости запоминания всей матрицы коэффициентов разложения небазисных векторов, если объединить выполнение этапов 2 - 5 ЦИКЛИЧЕСКОЙ программы. Этот вариант требует для хранения коэффициентов разложения небазисных векторов только двух массивов ( рабочего и эталонного) по т ячеек в каждом. Основная идея заключается в сравнении приращения критерия оптимальности только для двух небазисных векторов, в результате чего находится вектор, дающий наибольшее приращение, который размещается в эталонном массиве. В дальнейшем каждый следующий - небазисный вектор сравнивается с эталонным, и если он дает большее приращение критерия оптимальности, то его коэффициенты разложения располагаются в эталонном массиве. [19]
Обратно, если заранее даны формулы, вида ( 3), то они представляют в выбранных координатах некоторое линейное преобразование х Ах. Матрица А, составленная из коэффициентов формул ( 3), и матрица А, составленная из коэффициентов разложений векторов Аег, Ае2 по базису еъ е %, переводятся одна в другую транспонированием. [20]
Задачи детерминированного и статистического анализа можно успешно решать численно с применением спектральных методов. Более того, спектральные методы для такого класса задач существенно более эффективны многих других численных методов, поскольку они позволяют сохранить в явном виде линейную зависимость между набором коэффициентов разложения вектора входа и вектора состояния системы. [21]
Но тогда через конечное число шагов мы обязательно должны прийти к базисному множеству (5.14), которое будет одновременно допустимым и двойственно допустимым. А это означает, что отвечающая ему матрица х ( К) и вектор у ( К) являются оптимальными в интересующих нас прямой, и двойственной задачах. Наиболее трудоемкие операции на каждом шаге прямого метода последовательного улучшения, как мы уже знаем, - вычисление компонент вектора у ( К) и определение коэффициентов разложения вновь вводимого вектора по базисным векторам. [22]
Любое его ребро / представляет собой пересечение симплекса Тп с гиперплоскостями л: г 0, 1фр, s, где р, s Nn. Любая нормаль к ребру / имеет компоненты ар а 1, а остальные at, i. Матрица А, составленная из векторов а1 для всех ребер / симплекса TVi, является абсолютно унимодулярной в силу теоремы 4.1. Благодаря лемме 2.4 матрица коэффициентов разложения небазисных векторов по каждому базису В является также абсолютно унимодулярной. [23]