Обобщение графического метода решения задач линейного программирования.

Вообще, с помощью графического метода может быть решена задача линейного программирования, система ограничений которой содержит n неизвестных и m линейно независимых уравнений, если N и M связаны соотношением N – M = 2.

Действительно, пусть поставлена задача линейного программирования.

Найти минимальное значение линейной функции Z = С₁х₁+С₂х₂+... +С_Nx_N при ограничениях

a₁₁x₁ + a₂₂x₂ + ... + a_1NХ_N = b₁

a₂₁x₁ + a₂₂x₂ + ... + a_2NХ_N = b₂ (2.3)

. . . . . . . . . . . . . . . . . . . . . . . .

a_М1x₁ + a_М2x₂ + ... + a_МNХ_N = b_М

x_j 0 (j = 1, 2, ..., N)

где все уравнения линейно независимы и выполняется cсоотношение N - M = 2.

Используя метод Жордана - Гаусса, производим M исключений, в результате которых базисными неизвестными оказались, например, M первых неизвестных х₁, х₂, ..., х_M, а свободными - два последних: х_М+1, и х_N, т. е. система ограничений приняла вид

x₁ + a_1,М+1x_М+1 + a_1NХ_N = b₁

x₂ + a_2,М+1x_М+1 + a_2NХ_N = b₂ (2.4)

. . . . . . . . . . . . . . . . . . . . . . . .

x_М + a_{М, М+1}x₂ + a_МNХ_N = b_М

x_j 0 (j = 1, 2, ..., N)

С помощью уравнений преобразованной системы выражаем линейную функцию только через свободные неизвестные и, учитывая, что все базисные неизвестные - неотрицательные: х_j 0 (j = 1, 2, ..., M), отбрасываем их, переходя к системе ограничений, выраженных в виде неравенств. Таким образом, окончательно получаем следующую задачу.

Найти минимальное значение линейной функции Z = С_М+1х_М+1+С_Nx_N при ограничениях

a_1,М+1x_М+1 + a_1NХ_N b₁

a_2,М+1x_М+1 + a_2NХ_N b₂

. . . . . . . . . . . . . . . . . . .

a_М,М+1x_М+1 + a_МNХ_N b_М

x_М+1 0, х_N 0

Преобразованная задача содержит два неизвестных; решая ее графическим методом, находим оптимальные значения x_М+1 и х_N, а затем, подставляя их в (2.4), находим оптимальные значения х₁, х₂, ..., х_M.

Пример.

Графическим методом найти оптимальный план задачи линейного программирования, при котором линейная функция Z = 2х₁ - х₂ + х₃ - 3х₄ + 4х₅ достигает максимального значения при ограничениях

х₁ - х₂ + 3х₃ - 18х₄ + 2х₅ = -4

2х₁ - х₂ + 4х₃ - 21х₄ + 4х₅ = 2

3х₁ - 2х₂ + 8х₃ - 43х₄ + 11х₅ = 38

x_j 0 (j = 1, 2, ..., 5)

Решение.

Используя метод Жордана-Гаусса, произведем три полных исключения неизвестных х₁, х₂, х₃. В результате приходим к системе

х₁ + х₄ - 3х₅ = 6

х₂ + 7х₄ + 10х₅ = 70

х₃ - 4х₄ + 5х₅ = 20

Откуда x₁ = 6 – х₄ + 3x₅, х₂ = 70 – 7х₄-10х₅, х₃ = 20 + 4х₄ -5х₅.

Подставляя эти значения в функцию и отбрасывая в системе базисные переменные, получаем задачу, выраженную только через свободные переменные х₄ и х₅: найти максимальное значение линейной функции Z = 6х₄ + 15х₅ – 38 при ограничениях

х₄ - х₅ 6

7х₄ + 10х₅ 70

- 4х₄ + 5х₅ 20

х₄ 0, х₅ 0.

Построим многогранник решений и линейную функцию в системе координат х₄Ох₅ заключаем, что линейная функция принимает максимальное значение в угловой точке В, которая лежит на пересечении прямых 2 и 3. В результате решения системы

7х₄ + 10х₅ = 70

-4х₄ + 5х₅ = 20

находим: х₄ = 2, х₅ = 28/5. Максимальное значение функции Z_max = -38 + 12 + 84 = 58. Для отыскания оптимального плана исходной задачи подставляем найденные значения х₄ и х₅. Окончательно получаем: х₁ = 104/5, х₂ = 0, х₃ = 0, х₄ = 2, х₅ = 28/5.