Симплексный метод

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

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

Рассмотрим ОЗЛП с системой ограничений в следующей форме:

(1.5)

Если ввести в систему ограничений (1.5) дополнительные переменные

то система ограничений (1.5) преобразуется в систему уравнений

(1.6)

имеющую специальный вид.

Данное система – это обычная система линейных неоднородных уравнений с n+m неизвестными и содержит m уравнений. Так как n+m>m, то система всегда имеет множество решений, среди которых и ищется оптимальный план, на котором целевая функция Z достигает максимума. Можно найти все решения системы (1.6), удовлетворяющие ограничениям (1.5) (допустимые планы) и среди них найти оптимальный план. Но таких решений может быть достаточно много, данный алгоритм может оказать очень трудоемким.

Систему (1.6) можно представить в виде, характерном для линейной алгебры:

AX=B, (1.7)

где А- матрица m×(n+m), а Х и В – столбцы (n+m)×1, n×1, соответственно:

, , (1.8)

В этой системе каждая из переменных x_n+1, x_n+2 …x_n+m исключена из всех уравнений, за исключением одного уравнения, в котором коэффициент при ней равен 1.

Для системы уравнений (1) назовем переменные x ₁, x ₂,..., x_n - свободными, а переменные x_n+1, x_n+2 …x_n+m - базисными.

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

С этой целью совершим следующие операции:

1. Рассмотрим какое-нибудь уравнение системы (1.6), в котором коэффициент a_sr при переменной x_r отличен от 0 (это уравнение с номером s).

2. Разделим это уравнение на a_sr. Тогда в нем коэффициент при переменной x_r станет равным 1.

3. Вычтем из каждого i - го уравнения системы (i ≠ s) уравнение с номером s, умноженное на a_sr.

В результате переменная x_r будет исключена из всех уравнений системы, кроме уравнения с номером s, и станет базисной, а переменная x_{n + s} станет свободной.

Описанный процесс носит название полного жорданова исключения с разрешающим элементом a_sr. Коэффициенты s - го уравнения системы (1.6) называются разрешающей строкой, а элементы r - го столбца матрицы системы уравнений (1.6) - разрешающим столбцом.

Удобный алгоритм пересчета коэффициентов системы уравнений при проведении полного жорданова исключения с разрешающим элементом a_sr состоит в следующем (здесь и далее верхний индекс «н» соответствует новому значению элемента матрицы, а верхний индекс «с» - старому значению):

1. Разделим элементы разрешающей строки на разрешающий элемент. При этом разрешающий элемент станет равным 1;

2. Все элементы разрешающего столбца, за исключением разрешающего элемента, заменим нулями. При этом разрешающий элемент останется равным 1.

3. Все остальные элементы матрицы пересчитаем в новые элементы

воспользовавшись «правилом прямоугольника»

Дата добавления: 2015-06-27