Начальная таблица

Cтраница 1

Начальная таблица показана на рис. 5.3, а. [1]

Пусть в начальной таблице все строки, кроме, быть может, нулевой, лексикографически положительные. Если нет, то можно добавить искусственные переменные или переставить местами столбцы и переобозначить переменные. Тогда конечность будет обеспечена, если принять следующее, немного более сложное правило выбора ведущего элемента. Допустим, что в качестве ведущего выбран s - й столбец. [2]

Для того чтобы сделать начальную таблицу двойственно допустимой, введем избыточное ограничение - Xj - xz - х3 ж4 М 0, где М выбирается так, чтобы ограничение стало избыточным. [3]

Тем самым будет заполнена 1-я строка начальной таблицы. [4]

Тем самым заполняем 2 - ю строку начальной таблицы. Аналогично, исходя из 2 - й строки, находим элементы / 2, у г и ( / 2 последней, 3 - й строки начальной таблицы. Отметим, что если пересчеты элементов строк дают значительные расхождения, то этот прием не является надежным. В таком случае следует или уменьшить шаг h вычислений, или же обратиться к более точным методам. [5]

Тем самым заполняем 2 - ю строку начальной таблицы. Аналогично, исходя из 2 - й строки, находим элементы г / 2, у г и у 2 последней, 3 - й строки начальной таблицы. Отметим, что если пересчеты элементов строк дают значительные расхождения, то этот прием не является надежным. В таком случае следует или уменьшить шаг Л вычислений, или же обратиться к более точным методам. [6]

Тем самым заполняем 2 - ю строку начальной таблицы. Аналогично, исходя из 2 - й строки, находим элементы уг, у 2 и) / последней 3 - й строки начальной таблицы. [7]

Представление иерархии на шаге 0.| Представление иерархии на шаге tl. [8]

Рассмотрим работу алгоритма иерархической классификации без использования начальных таблиц данных. [9]

Графическая интерпретация отношений как точек пересечения. [10]

В следующей таблице, которая пока совпадает с начальной таблицей задачи ЛП, определим ведущий столбец, ассоциируемый с вводимой переменной, и ведущую строку, ассоциируемую с исключаемой переменной. Элемент, находящийся на пересечении ведущего столбца и ведущей строки, назовем ведущим. [11]

Так же как и в полностью целочисленном алгоритме Гомори, предположим, что начальная таблица является двойственно допустимой, и каждое ограничение выражено через небазисные переменные, взятые со знаком минус. [12]

Поэтому выбрав и зафиксировав любое упорядочение множества К, для вычислительной схемы с обратной матрицей мы получим в начальной таблице лексикографически положительные строки. Ввиду сильной вырожденности задачи целесообразно применять метод, поддерживающий эту лексикографическую положительность и строго гарантирующий конечность числа шагов метода последовательного улучшения. Заметим, что множество допустимых решений в задаче (5.9) - (5.11) ограничено, так что у нее есть и оптимальное решение. [13]

Заметим, что начальная таблица [, 0 и Л / ] имеет лексикографически положительные строки. [14]

Достаточно внести три изменения в описанную выше процедуру, чтобы получить конечный алгоритм. Во-первых, в начальную таблицу нужно добавить новую строку. Во-вторых, ведущий столбец as должен выбираться не только исходя из требования os 0, но и в соответствии с некоторыми новыми правилами. И в-третьих, строка, используемая в качестве производящей для получения отсечения Гомори не всегда является ведущей строкой симплекс-алгоритма; вместо того чтобы определять производящую строку по правилу проверки отношения, она будет выбираться из множества подходящих строк согласно другому правилу, которое входит в класс правил, гарантирующих конечность. [15]

Страницы: 1 2