Линейное программирование постановка задач и графическое решение (стр. 3 из 3)

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

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

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

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

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

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

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

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₁

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

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

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.5). Из рис. 2.5 заключаем, что линейная функция принимает максимальное значение в угловой точке В, которая лежит на пересечении прямых 2 и 3. В результате решения системы

7х₄ + 10х₅ = 70

- 4х₄ + 5х₅ = 20

-

находим: х₄ = 2, х₅ = 28/5. Максимальное значение функции Z_max = -38 + 12 + 84 = 58.

Для отыскания оптимального плана исходной задачи подставляем найденные значения х₄ и х₅. Окончательно получаем: х₁ = 104/5, х₂ = 0, х₃ = 0, х₄ = 2, х₅ = 28/5.

ЛИТЕРАТУРА

1. Математические методы анализа экономики /под ред. А.Я.Боярского. М.,Изд-во Моск. Ун-та, 1983

2. А.И.Ларионов, Т.И.Юрченко “Экономико-математические методы в планировании: Учебник – М.: Высш.школа, 1984

3. Ашманов С.А. “Линейное программирование”,- М.: 1961