Cтраница 3
Сказанное приводит к новому, эквивалентному предыдущему, определению допустимого базисного решения: допустимое решение задачи (3.1) называется базисным, если все его координаты удается разбить на две группы так, чтобы в первую попало ровно т координат и соответствующие им векторы условий были линейно независимы, а вторая состояла бы только из нулей. Список координат первой группы принято называть допустимым базисом, а сами эти координаты и отвечающие им векторы условий - базисными. Координаты, относящиеся ко второй группе, и их векторы условий называют небазисными. Если все координаты, составляющие допустимый базис, положительны, говорят, что он не вырожден. [31]
Система неизбыточна, поскольку ее матрица содержит подматрицу - I. Первые три столбца не дают допустимого базиса г а любой допустимый базис, содержащий четвертый столбец, вырожден. [32]
Не всегда, конечно, можно получить такой наипростейший метод алгоритмического расширения. Тем не менее этого можно достичь путем изменения способов образования допустимых базисов в симплексном алгоритме, а дальнейшие ограничения на векторе, которые можно принять в качестве базисных, могут расширить нелинейную область применения симплекс-метода. [33]
Фиксируем произвольное СКИ) - мерное подпространство Е в ty и вещественную матрицу Д размерности С н / %) ( К - Н) ранга к - Н такую, что и. Рассмотрим задачи ( I) и ( 2) и покажем, что определение допустимого базиса в задаче ( 2) естественно в том смысле, что каждый допустимый базис задачи ( I) является допустимым базисом в задаче ( 2) и наоборот. Действительно, понятие допустимого базиса в задаче ( I) хорошо известно. Набор индексов а из 4: ( ч 1) такой, что ( Ж / - Н): ( И-И) с з и М Кч-1 называется допустимым базисом в задаче ( I), если вектора СЦ, npniea линейно независимы в TtK и соответствующее базисное решение допустимо. [34]
Из теоремы 4.9 немедленно следует, что многогранник М ( А, Ь) является симплексом тогда и только тогда, когда симплекс-таблицы всех допустимых базисов В матрицы А 1 -подобные. Легко убедиться, что последнее утверждение имеет место, если симплекс-таблица хотя бы одного допустимого базиса является 1 -регулярной. [35]
Фиксируем произвольное СКИ) - мерное подпространство Е в ty и вещественную матрицу Д размерности С н / %) ( К - Н) ранга к - Н такую, что и. Рассмотрим задачи ( I) и ( 2) и покажем, что определение допустимого базиса в задаче ( 2) естественно в том смысле, что каждый допустимый базис задачи ( I) является допустимым базисом в задаче ( 2) и наоборот. Действительно, понятие допустимого базиса в задаче ( I) хорошо известно. Набор индексов а из 4: ( ч 1) такой, что ( Ж / - Н): ( И-И) с з и М Кч-1 называется допустимым базисом в задаче ( I), если вектора СЦ, npniea линейно независимы в TtK и соответствующее базисное решение допустимо. [36]
Пусть минимумы в (4.11) при всех значениях / е JH достигаются на индексах i из множества JB cr JB. Тогда ясно, что в допустимом базисе В можно заменить всякий вектор-столбец А для i e JB на некоторый вектор-столбец А V / е е J / /, и в результате опять получим допустимый базис. [37]
Фиксируем произвольное СКИ) - мерное подпространство Е в ty и вещественную матрицу Д размерности С н / %) ( К - Н) ранга к - Н такую, что и. Рассмотрим задачи ( I) и ( 2) и покажем, что определение допустимого базиса в задаче ( 2) естественно в том смысле, что каждый допустимый базис задачи ( I) является допустимым базисом в задаче ( 2) и наоборот. Действительно, понятие допустимого базиса в задаче ( I) хорошо известно. Набор индексов а из 4: ( ч 1) такой, что ( Ж / - Н): ( И-И) с з и М Кч-1 называется допустимым базисом в задаче ( I), если вектора СЦ, npniea линейно независимы в TtK и соответствующее базисное решение допустимо. [38]
Для этого составлена следующая последовательность процедур: problem ( 1, и, fail) - масштабирование; problem ( 2, и, fail) - описание ограничений, заданных соотношениями ( 3); problem ( 5, и, fail) - введение правой части; problem ( 9, и, fail) - вычисление допустимого базиса; problem ( 7, и, fail) - вывод допустимого решения. [39]
Фиксируем произвольное СКИ) - мерное подпространство Е в ty и вещественную матрицу Д размерности С н / %) ( К - Н) ранга к - Н такую, что и. Рассмотрим задачи ( I) и ( 2) и покажем, что определение допустимого базиса в задаче ( 2) естественно в том смысле, что каждый допустимый базис задачи ( I) является допустимым базисом в задаче ( 2) и наоборот. Действительно, понятие допустимого базиса в задаче ( I) хорошо известно. Набор индексов а из 4: ( ч 1) такой, что ( Ж / - Н): ( И-И) с з и М Кч-1 называется допустимым базисом в задаче ( I), если вектора СЦ, npniea линейно независимы в TtK и соответствующее базисное решение допустимо. [40]
Перечисление допустимых базисов многогранников из класса ЭЛ ( т, п) является сложной задачей. Как будет видно из дальнейшего, эта задача не всегда тождественна задаче перечисления вершин многогранника. Рассмотрим один возможный метод перечисления допустимых базисов. [41]
Сходимость описанного алгоритма решения невырожденной задачи гарантируется тем, что при сменах допустимых базисов значение критерия возрастает. Поэтому повторяться они не могут, и так как их число не больше, чем С, за конечное число шагов либо будет найдено решение задачи, либо установлено, что ограниченного решения не существует. Алгоритм применим и в вырожденных случаях, но тогда формальная замена одного допустимого базиса другим не обязательно приведет к изменению точки. Соответственно, возможно так называемое зацикливание - бесконечное повторение набора допустимых базисов, отвечающих одной вершине. [42]
Сначала рассмотрим двойственный метод. Он состоит из двух частей - основной и вспомогательной. В основной части используется таблица двойственного симплекс-метода; вычисления начинаются с получения двойственно допустимого базиса и соответствующего двойственно допустимого у. С помощью вспомогательной части формируются неравенства, используемые в основной части. [43]
Поэтому каждая компонента связности графа G ( x) ] G ( y) есть либо ребро, либо цикл с четным числом ребер. Пусть среди компонент связности графа имеется более чем один цикл. Тогда граф T ( x) J jT ( y) также содержит более одного цикла. Поэтому допустимые базисы ЛГ ( л) и АТ ( у) отличаются более чем одним вектор-столбцом и, следовательно, не являются смежными. [44]
Сказанное приводит к новому, эквивалентному предыдущему, определению допустимого базисного решения: допустимое решение задачи (3.1) называется базисным, если все его координаты удается разбить на две группы так, чтобы в первую попало ровно т координат и соответствующие им векторы условий были линейно независимы, а вторая состояла бы только из нулей. Список координат первой группы принято называть допустимым базисом, а сами эти координаты и отвечающие им векторы условий - базисными. Координаты, относящиеся ко второй группе, и их векторы условий называют небазисными. Если все координаты, составляющие допустимый базис, положительны, говорят, что он не вырожден. [45]