Cтраница 2
Пусть А ( В, N), где В является допустимым базисом. [16]
Предположим, что условия задачи представлены в канонической форме и В - текущий допустимый базис. [17]
Сходимость описанного алгоритма решения невырожденной задачи гарантируется тем, что при сменах допустимых базисов значение критерия возрастает. Поэтому повторяться они не могут, и так как их число не больше, чем С, за конечное число шагов либо будет найдено решение задачи, либо установлено, что ограниченного решения не существует. Алгоритм применим и в вырожденных случаях, но тогда формальная замена одного допустимого базиса другим не обязательно приведет к изменению точки. Соответственно, возможно так называемое зацикливание - бесконечное повторение набора допустимых базисов, отвечающих одной вершине. [18]
Число допустимых базисных пар в задаче ( 9) совпадает с числом допустимых базисов в задаче ( 2), и значения супремума у этих задач равны. [19]
В специальной разновидности модифицированного симплекс-метода используется тот факт, что матрицу, обратную к допустимому базису, совпадающую вначале с единичной матрицей, можно выразить как произведение матриц элементарных преобразований. [20]
При входе в процедуру значение и [0 ] равно максимально допустимому числу шагов обмена для вычисления первого допустимого базиса из текущего базиса. [21]
Две рершины многогранника М, заданного в канонической форме, являются смежными, когда отвечающие им допустимые базисы отличаются только одним вектор-столбцом. [22]
На этом многообразии определяется вероятностная мера и вычисляются меры множеств задач с конечными и бесконечными экстремумами и среднее число допустимых базисов в задачах. [23]
Покажем, что если из цикла С выбросить произвольное ребро / е G ( х), то полученное остовное дерево определяет допустимый базис некоторой вершины г многогранника М, смежной вершине х, так как их базисы различаются одним столбцом. Действительно, построенное дерево содержит совершенное паросочетание, которое составлено из ребер множества Е, дополненных п-р ребрами паросочетания G ( у), принадлежащими циклу С. G ( w) и С ( г) общие. [24]
Из теоремы 4.9 немедленно следует, что многогранник М ( А, Ь) является симплексом тогда и только тогда, когда симплекс-таблицы всех допустимых базисов В матрицы А 1 -подобные. Легко убедиться, что последнее утверждение имеет место, если симплекс-таблица хотя бы одного допустимого базиса является 1 -регулярной. [25]
Из теоремы 4.9 и импликации ( если симплекс-таблица допустимого базиса В матрицы А 1 -регулярная, то все симплекс-таблицы - 1 -подобные) следует, что многогранник М ( A, b) e еЭЛ ( т, п, 2) тогда и только тогда, когда симплекс-таблицы всех допустимых базисов 2-подобные. [26]
Базисом называется множество линейно независимых векторов. Допустимым базисом для задачи линейного программирования называется квадратная матрица В, составленная из множества линейно независимых векторов, выбранных из прямоугольной матрицы A ( Pi, PZ, , РП) так, чтобы для системы ВХ0 Ро выполнялось Х0 В-Фо О. [27]
Допустим, что все координаты вектора Р0 нготрица-тельны. Пусть BI - допустимый базис, то есть некоторое основное допустимое решение находится из системы BI OI РО, где Х01 ВГ Ро О. На практике BI бывает обычно единичной матрицей порядка т, а соответствующее первое допустимое решение находится мгновенно, так как матрица, обратная единичной, снова равна единичной матрице. [28]
Система неизбыточна, поскольку ее матрица содержит подматрицу - I. Первые три столбца не дают допустимого базиса г а любой допустимый базис, содержащий четвертый столбец, вырожден. [29]
Пусть минимумы в (4.11) при всех значениях / е JH достигаются на индексах i из множества JB cr JB. Тогда ясно, что в допустимом базисе В можно заменить всякий вектор-столбец А для i e JB на некоторый вектор-столбец А V / е е J / /, и в результате опять получим допустимый базис. [30]