Алгоритм симплекс-метода. Последовательность действий можно описать следующим образом:

Последовательность действий можно описать следующим образом:

· путем преобразований система ограничений приводится к необходимой, так называемой базисной, форме;

· находится так называемое опорное решение, служащее «точкой отсчета»;

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

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

Для решения системы все неизвестные произвольно подразделяют на базисные и свободные. Число базисных переменных определяется числом линейно-независимых уравнений. Остальные неизвестные свободные. Им придают произвольные значения и подставляют в систему. Любому набору свободных неизвестных можно придать бесчисленное множество произвольных значений, которые дадут бесчисленное множество решений. Если все свободные неизвестные приравнять к нулю, то решение будет состоять из значений базисных неизвестных. Такое решение называется базисным.

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