Симплексный метод решения задач линейного программирования. Симплексный метод – это метод целенаправленного перебора опорных решений задачи линейного программирования

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

Основное содержание метода состоит в следующем:

1. Указать способ нахождения начального (опорного) решения.

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

3. Задать критерии, которые позволяют своевременно прекратить перебор решений на оптимальном решении или сделать заключение об отсутствии решения.

Пусть поставлена задача линейного программирования: среди неотрицательных решений системы уравнений

Найти такие решения, которые максимизировали (минимизировали) бы целевую функцию Z (X) = c₁x₁ + c₂x₂ + … + c_nx_n.

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

Выразим x₁, x₂, …, x_r (r£m) через остальные переменные:

где b¢₁³ 0, b¢₂³ 0,…, b¢_r³ 0. Если ограничительные условия заданы неравенствами, то их можно преобразовать в равенства путем введения новых неотрицательных балансовых переменных. Ограничительные условия могут задаваться и смешанным образом, т.е. неравенствами и уравнениями, тогда указанным способом их можно свести только к уравнениям. Переменные (неизвестные) x₁, x₂, …, x_r называются базисными, а весь набор { x₁, x₂,…, x_r}- базисом, остальные переменные называются свободными, система ограничений называется системой, приведенной к единичному базису. Подставляя в целевую функцию вместо базисных переменных их выражения через свободные из системы, получим

Z (X) = g_r+1x_r+1 + g_r+2x_r+2 + … + g_nx_n.

Теперь, полагая все свободные переменные равными нулю, найдем значения базисных переменных: x₁ = b¢₁, x₂ = b¢₂, …, x_r = b¢_r. Таким образом, решение (b¢₁, b¢₂,…, b¢_r, 0, …, 0) является допустимым- оно называется базисным. Решение задачи с помощью симплекс-метода распадается на ряд шагов, заключающихся в том, что от данного базиса Б мы переходим к другому базису Б¢ с таким расчетом, чтобы значение целевой функции увеличивалось или, по крайней мере, не уменьшалось.

Пример. Максимизировать целевую функцию Z (X) = -x₄ + x₅ при ограничениях: x₁+ x₄– 2x₅ =1, x₂ –2x₄+ x₅ =2, x₃ + 3x₄ + x₅ =3.

Решение. Данная система уравнений-ограничений совместна, т.к. ранги матрицы системы

и расширенной матрицы

совпадают и равны 3. Следовательно, система уравнений совместна и три переменные (базисные) можно линейно выразить через две свободные переменные. Выразим, например, x₁, x₂ и x₃ через x₄ и x₅, т.е. приведем систему к единичному базису:

Целевую функцию Z (X) =-x₄ + x₅ выразим через свободные переменные x₄ и x₅ (в данном примере функция уже выражена через них). Теперь при x₄=0, x₅=0 найдем значения базисных переменных: x₁ =1, x₂ =2, x₃ =3, x₄ =0, x₅ =0, или (1, 2, 3, 0, 0). При найденном допустимом решении целевая функция Z (X) имеет значение 0, т.е. Z₁ =0.

Теперь попытаемся увеличить значение Z₁; увеличение x₄ уменьшит Z₁, т.к. перед x₄ стоит отрицательный коэффициент, а увеличение x₅ дает увеличение и Z₁. Увеличим поэтому x₅ так, чтобы x₁ , x₂ , x₃ не стали отрицательными, оставив x₄ =0. Из второго уравнения системы (15) следует, что x₅ можно увеличить до 2. Таким образом, получаем следующие значения переменных: x₁ =5, x₂ =0, x₃ =1, x₄ =0, x₅ =2 или (5, 0, 1, 0, 2).

Значение целевой функции Z (X) при этом допустимом решении равно Z₂ =2, т.е. при втором шаге оно увеличилось.

Далее, примем за свободные переменные х₂ и х₄, т.е. именно те, которые в новом решении имеют нулевые значения. С этой целью из второго уравнения системы (15) выразим х₅ через х₂ и х₄ и получим х₅ =2 – х₂ + 2х₄. Тогда

Переменные х₁, х₃ и х₅ образуют новый базис. Для увеличения значения Z(X) будем увеличивать х₄. Из второго уравнения системы (16) видно, что при условии неотрицательности х₃ значение х₄ можно довести до х₄ =1/5. При этом условии новое допустимое решение есть х₁ =28 ¤ 5, х₂=0, х₃=0, х₄ =1 ¤ 5, х₅ =12 ¤ 5 или (28 ¤ 5, 0, 0, 1 ¤ 5, 12 ¤ 5). Значение целевой функции при этом Z₃ =11 ¤ 5.

Выразим теперь х₁, х₄, х₅ через свободные переменные х₂ и х₃:

Переменные х₁, х₄ и х₅ образуют новый базис. Т.к. в последней целевой функции обе свободные переменные входят с отрицательными коэффициентами, то наибольшее значение Z (X) достигает при х₂ =0, х₃ =0. Это означает, что решение (28 ¤ 5,0,0,1 ¤ 5,12 ¤ 5) является оптимальным и Z_max =11/5.