«Анализ и проектирование алгоритма симплекс-метода для решения задач линейного программирования.»

Определение. Коэффициент ∝_фv=∝_iv , стоящий на пересечении направляющих строки и столбца называется направляющим (разрешающим, генеральным) элементом таблицы.
4) Формируем новые множества:

Дальнейшие действия алгоритма:

• 
  преобразуем задачу, т.е. все базисные переменные и целевую функцию выражаем через свободные переменные;
  
• 
  заполняем новую симплексную таблицу;
  
• 
  делаем все свободные переменные х_j = 0 и находим опорный план;
  

Опорный план (вектор) такой Х'=< β₁,β₂,...,β_v,,...,β_m, 0, 0...,0>; Q(Х') ≤ Q₀ ;

• 
  если план не оптимален, то определяем направляющий столбец;
  
• 
  проверяем существует ли оптимальный план;
  
• 
  если оптимальный план существует, то находим направляющую строку и вновь изменяем базис и т. д.
  
• 
  Переход от одной таблицы к другой связан с трудоемкими расчетами (о чем надо еще написать) Вводимую в базис переменную х_ν (икс ню) выражаем через свободные переменные и выводимую х_i. Действуем так.
  

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

Рисунок С - Структурная схема алгоритма симплекс-метода
При решении задач линейного программирования вычисляются ранги у матрицы ограничений и расширенной матрицы ранги должны быть равны r=m.