Процесс замены одних переменных в бази­се на другие (что эквивалентно перебору угловых точек симплекса) называютсимплексными и гауссовыми преобразованиями.

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

Вверху таблицы помещают все переменные и коэффициенты, с которыми соответствующие переменные входят в целевую функцию.

Первый столбец состоит из коэффициентов целевой функции при переменных, вошедших в базис.

Затем следует столбец базисных переменных и свободных членов уравнений.

Элементы остальных столбцов таблицы представляют собой коэффициенты при пере­менных, с которыми они входят в систему уравнений. Таким обра­зом, каждой строке таблицы соответствует уравнение системы, ре­шенное относительно базисной переменной.

Нижняя строка таблицы называетсяиндексной. Каждый ее элемент (оценка) определяет степень влияния каждой переменной задачи на изменение значения целевой функции.

Столбец с наименьшей положительной оценкой (для задач на минимум) или наибольшей отрицательной оценкой (для задач на максимум) называетсяразрешающим столбцом,а переменная столбца должна вводиться в базис.

Чтобы установить переменную, которая должна быть выведена из базиса, определяют отношения свободных членов к положительным элементам разре­шающего столбца. Строка с наименьшим отклонением называется разрешающей строкой, а переменная этой строки выводится из базиса. Если окажется несколько равных наименьших отношений свободных членов к коэффициентам разрешающего столбца, то следует брать отношение с наибольшим знаменателем.

Элемент симплексной таблицы, находящийся на пересечении разрешающего столбца и разрешающей строки, называетсяразре­шающим элементом.

Затем осуществляется симплексное преобра­зование таблицы, в результате которого переменная столбца вво­дится в базис. Это означает, что эта переменная должна быть ис­ключена из всех остальных строк таблицы (из остальных уравнений системы), а в разрешающей строке должна присутствовать с коэф­фициентом +1. Для этого сначала каждый элемент разрешающей строки делится на разрешающий элемент, а затем разрешающая строка вычитается из остальных строк, включая индексную. Для это­го каждый новый элемент разрешающей строки умножается на эле­мент разрешающего столбца и вычитается из каждого элемента со­ответствующей строки. Такое действие производится для всех эле­ментов всех строк симплексной таблицы, включая индексную строку.

В результате расчетов в разрешающем столбце все элементы будут иметь нулевое значение, за исключением разрешающего элемента, который равен 1, что означает, что новая базисная переменная бу­дет входить только в одно уравнение с коэффициентом +1. Сим­плексные преобразования выполняются до тех пор, пока в индексной строке не останется положительных элементов (для задачи на ми­нимум) или отрицательных элементов (для задачи на максимум).

Алгоритм симплексного метода состоит из следующих итера­ций (при решении задачи на минимум):

1) систему ограничений задачи линейного программирования необходимо решить относительно какого-либо базиса. Выра­зить линейную форму (целевую функцию) через свободные переменные;

2) составить симплексную таблицу. Если в индексной строке все элементы отрицательны, то базисное решение опти­мально. Задача решена;

3) если в индексной строке симплексной таблицы есть положи­тельные элементы, то столбец, соответствующий макси­мальному из них, принимается за разрешающий. Рассчиты­ваются отношения элементов столбца свободных членов к положительным элементам разрешающего столбца. Стро­ка, соответствующая минимальному из этих отношений, яв­ляется разрешающей. Элемент таблицы, находящийся на пересечении разрешающего столбца и разрешающей стро­ки, называется разрешающим;

4) переходить к новому базису следует, исключая из старого базиса переменную, соответствующую разрешающей строке, вводя вместо нее переменную, которая соответствует раз­решающему столбцу. Составляется новая симплексная таб­лица, соответствующая новому базису. Действия, начиная со второго, повторяются.

2)В процессе решения транспортной задачи требуется максималь­ные объемы перевозок перераспределить между наиболее дешевы­ми транспортными связями так, чтобы полностью вывезти продук­цию от всех поставщиков и удовлетворить спрос всех потребителей.

Необходимым условием решения ТЗЛП является закрытость или замкнутость моделируемой транспортной системы. В замкнутой за­даче объемы спроса равны объемам потребления. Если это условие нарушается, то транспортная задача называется «открытой» и при­водится к задаче закрытого типа путем введения в транспортную систему дополнительного (фиктивного) поставщика или потребите­ля. Этому фиктивному поставщику или потребителю приписываются соответственно недостающий объем предложения или спроса, в ре­зультате чего система становится закрытой. Кроме того, естествен­ным ограничением в ТЗЛП является условие неотрицательности объемов перевозок.