Cтраница 4
В задаче максимизации М i должны быть большими по абсолютной величине отрицательными числами. Идея метода соответствует тому, что искусственным переменным придаются заведомо большие цены. Такой способ приводит к нулевым значениям искусственных переменных в оптимальном решении. Существует и другой способ получения начального допустимого базиса. В этом способе, как и в первом, в качестве начальных базисных переменных используются искусственные переменные. Рассматривается новая целевая функция, представляющая собой сумму искусственных переменных. Требуется минимизировать, используя z - уравнение как одно из ограничений. Если исходная система уравнений имеет допустимое решение, то все искусственные переменные должны стать равными нулю. Должно быть равно нулю. [46]
Пусть теперь граф G ( х) [) G ( у) состоит из единственного цикла С и множества Е изолированных ребер. Дополним подграф G ( л:) U G ( y) ребрами из F, а затем из полученного графа удалим ребро ( г, s) в одном варианте и ребро ( r, t) - в другом. Подматрицы А и Ат ( Ю являются допустимыми базисами, соответствующими вершинам х и у. Эти базисы отличаются между собой только одним вектор-столбцом и поэтому являются смежными. [47]
Сходимость описанного алгоритма решения невырожденной задачи гарантируется тем, что при сменах допустимых базисов значение критерия возрастает. Поэтому повторяться они не могут, и так как их число не больше, чем С, за конечное число шагов либо будет найдено решение задачи, либо установлено, что ограниченного решения не существует. Алгоритм применим и в вырожденных случаях, но тогда формальная замена одного допустимого базиса другим не обязательно приведет к изменению точки. Соответственно, возможно так называемое зацикливание - бесконечное повторение набора допустимых базисов, отвечающих одной вершине. [48]
Из полученного представления симплекс-таблицы ясно, что для перехода к новому допустимому базису по прежней схеме достаточно знать матрицу А - 1 и вектор-строку к с т А 1: последовательно перемножая К на небазисные столбцы и вычитая каждый раз из результата соответствующий элемент вектора с, вычислим оценки замещения и выделим ведущий столбец; умножив на него матрицу Л - найдем те коэффициенты замещения, которые используются в формуле для определения ведущей строки, и выделим эту строку; затем по старым формулам вычислим значения координат нового базиса. Как правило, эта версия требует значительно меньшего объема памяти, чем первоначальная. Чтобы она была, кроме того, эффективна в смысле быстродействия, надо заложить в нее экономный алгоритм пересчета ( при сменах допустимых базисов) матрицы, обратной к базисной. Вывести такой алгоритм совсем несложно. [49]
Фиксируем произвольное СКИ) - мерное подпространство Е в ty и вещественную матрицу Д размерности С н / %) ( К - Н) ранга к - Н такую, что и. Рассмотрим задачи ( I) и ( 2) и покажем, что определение допустимого базиса в задаче ( 2) естественно в том смысле, что каждый допустимый базис задачи ( I) является допустимым базисом в задаче ( 2) и наоборот. Действительно, понятие допустимого базиса в задаче ( I) хорошо известно. Набор индексов а из 4: ( ч 1) такой, что ( Ж / - Н): ( И-И) с з и М Кч-1 называется допустимым базисом в задаче ( I), если вектора СЦ, npniea линейно независимы в TtK и соответствующее базисное решение допустимо. [50]