Симплекс-метод. Алгоритм симплекс-метода. Особенности табличного симплекс-метода. Понятия модифицированного симплекс-метода и двойственного симплекс-метода

Задачей оптимизации в математике называется задача о нахождении экстремума вещественной функции в некоторой области. Как правило, рассматриваются области, принадлежащие и заданные набором равенств и неравенств.

3.1. Описание

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

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

Уравнение W(x) = c, где W(x) – максимизируемый (или минимизируемый) линейный функционал, порождает гиперплоскость L(c). Зависимость от c порождает семейство параллельных гиперплоскостей. При этом экстремальная задача приобретает следующую формулировку: требуется найти такое наибольшее c, что гиперплоскость L(c) пересекает многогранник хотя бы в одной точке. Заметим, что пересечение оптимальной гиперплоскости и многогранника будет содержать хотя бы одну вершину, причем их будет более одной, если пересечение содержит ребро или k-мерную грань. Поэтому максимум функционала можно искать в вершинах многогранника. Принцип симплекс-метода состоит в том, что выбирается одна из вершин многогранника, после чего начинается движение по его рёбрам от вершины к вершине в сторону увеличения значения функционала. Когда переход по ребру из текущей вершины в другую вершину с более высоким значением функционала невозможен, считается, что оптимальное значение c найдено.

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

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

Последовательность вычислений симплекс-методом можно разделить на две основные фазы:

1.  нахождение исходной вершины множества допустимых решений;

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

В некоторых случаях исходное решение очевидно или его определение не требует сложных вычислений, – например, когда все ограничения представлены неравенствами вида «меньше или равно» (тогда нулевой вектор совершенно точно есть допустимое решение, хотя, скорее всего, далеко не оптимальное). В таких задачах первую фазу симплекс-метода можно вообще не проводить. Симплекс-метод соответственно делится на однофазный и

двухфазный.

3.2. Алгоритм симплекс-метода

Усиленная постановка задачи

Рассмотрим следующую задачу линейного программирования:

Теперь поставим эту задачу в эквивалентной усиленной форме. Необходимо максимизировать Z, где:

Здесь x – переменные из исходного линейного функционала; x_s – новые переменные, дополняющие старые таким образом, что неравенство переходит в равенство; c – коэффициенты исходного линейного функционала; Z – переменная, которую необходимо максимизировать. Полупространства  и  в пересечении образуют многогранник, представляющий множество допустимых решений. Разница между числом переменных и уравнений даёт число степеней свободы. Проще говоря, если рассматривать вершину многогранника, это есть число рёбер, по которым можно продолжать движение.

Тогда можно присвоить такому числу переменных значение 0 и назвать