Элементарное преобразование базиса

Перебор базисов, который происходит при решении задачи симплекс-методом, производится посредством минимального из­менения рассматриваемого в данный момент базиса. Таким ми­нимальным изменением, очевидно, является замена одного из ба­зисных столбцов на другой столбец матрицы А из числа неба­зисных. Подобное преобразование базиса мы и будем называть элементарным. Естественно, выбор того и другого столбца при этом преобразовании не является произвольным, а производится в соответствии с определенными правилами, что и делает перебор целенаправленным.Наша ближайшая цель — проследить за изменением симплекс-таблицы при таком преобразовании базиса и установить правило,которое может быть использовано для получения симплекс-таб­лицы, соответствующей преобразованному базису.Пусть в базисе В = [А^),..., Аст(т)], которому соответствует симплекс-таблица (2.5), столбец Аа^ решено заменить на стол­бец А3, в 6 Б1. Результатом такой замены будет новый базис В' = [А(7(1),..., А(7(г_1), А3, А(7(г+1),..., А(7(т)], если только элемент ггз симплекс-таблицы не равен 0. Это легко понять, если учесть, что согласно (2.4) (г1з,..., гтз)т = В~1 А31 т.е. А3 = В(г1з,..., гтз)т илит А3 = ^2 ггв^-а(%) • г = 1Поскольку разложение любого вектора по векторам базиса един­ственно, то при ггз ф 0 вектор А3 не может быть представлен в ви­де линейной комбинации векторов Аа^,..., А(7(г_1), Аа^г+1^,..., ^ст(т)) ЧТО означает линейную независимость столбцов в В'. В случае ггз = 0 вышеприведенное представление вектора А3 сви­детельствует о линейной зависимости столбцов матрицы В'.Чтобы сформулировать правило, согласно которому может быть получена симплекс-таблица, соответствующая преобразо­ванному базису В', напомним, что элементами таблицы являют­ся коэффициенты линейной системы (2.1"), (2.2"), полученной из системы (2.1), (2.2) путем приведения ее к диагональной форме относительно базисных переменных и переменной —ги. Так как новый набор базисных переменных отличается от старого только одной переменной х3 (заменившей переменную ж^,.)), то для полу­чения элементов новой симплекс-таблицы достаточно выполнить один шаг метода исключения Гаусса-Жордана, чтобы исключить х3 из всех, кроме одного, уравнений системы (2.1"), (2.2"), соот­ветствующей старому базису В (используя для этого единствен­ное уравнение данной системы, содержащее из числа базисных только исключаемую из базиса переменную жст(г), т.е. г-е уравне­ние).Таким образом, мы приходим к следующему правилу: разде­лить г-ю строку симплекс-таблицы на ггз и прибавить ее, умноженную на надлежащим образом подобранные числа, к другим строкам так, чтобы 1 в позиции (г, в) осталась единственным не­нулевым элементом й-го столбца. Если воспользоваться обозна­чением о.і для г-ж вектор-строки симплекс-таблицы, то правило преобразования можно изобразить схематично следующим обра­зом:

21. «Симплекс-таблица» и алгоритм ее построения.

Симплексный метод – метод последовательного улучшения плана.

Метод является универсальным, так как позволяет решить практически любую задачу линейного программирования. Математическая модель задачи приводится к каноническому (стандартному) виду. Заполняется опорная симплекс – таблица с использованием коэффициентов целевой функции и системы ограничений. Решается задача по алгоритму.

Идея симплексного метода заключается в том, что начиная с некоторого исходного опорного решения осуществляется последовательно направленное перемещение по допустимым решениям к оптимальному. Значение целевой функции для задач на максимум не убывает. Так как число допустимых решений конечно, то через конечное число шагов получим оптимальное решение.

1.Математическую модель задачи привести к каноническому (стандартному) виду.

2. Построить начальную симплекс-таблицу исходя из стандартного вида.

3. Найти разрешающий столбец. В строке коэффициентов ЦФ найти значение с самим маленьким отрицательным числом. Этот столбец и будет разрешающим.

4. Вычислить разрешающую строку и ведущий элемент (Почленно разделить столбец свободных членов на элементы разрешающего столбца, за исключением строки ЦФ. Выбрать наименьшее из частных. Эта строка будет разрешающей.Ведущий элемент будет на пересечении разрешающего столбца и разрешающей строки.).

5.Построить новую симплекс-таблицу-второй шаг.

При построении новой таблицы убрать из базиса строку с переменной разрешающей строки в предыдущей таблице. Ввести в базис строку с названием разрешающего столбца предыдущей таблицы.

Построение ведущей строки в новой таблице. Почленно поделить всю разрешающую строку на разрешающий элемент. Построение других строк в новой таблице. Почленно умножить ведущую строку на соответствующие этим строкам элементы разрешающего столбца из предыдущей таблицы и прибавить к соответствующим строкам в старой таблице.

6. Проверяем таблицу второго шага на оптимальность. Если в строке целевой функции нет отрицательных элементов, тогда таблица имеет оптимальный план, записать ответ. Если в строке ЦФ есть отрицательный элемент (элементы), тогда переходят к следующему (третьему) шагу, строят новую симплекс-таблицу в соответствии п.5 и затем проверяют ее на оптимальность. Построение таблиц заканчивается с нахождением оптимального плана.

Прямая задача на минимум решается следующим образом:

Написать математическую модель двойственной задачи в стандартном виде

Решить двойственную модель симплекс - методом

Записать ответ.

Связь между задачами двойственной пары в том, что, решая симплексным методом одну из них, автоматически получаем решение другой.

Для этого достаточно воспользоваться соответствием переменных прямой и двойственной задач в последней симплекс-таблице.