Глава 4. Геометрический метод решения задач линейного программирования

Рассмотрим задачу в стандартной форме (1.4) — (1.6) с двумя переменными (n = 2). К такой форме может быть сведена каноническая задача (с ограничениями в виде уравнений) когда число переменных п больше числа уравнений т на 2, т.е. n - т = 2.

Рис. 4.1

Пусть геометрическим изображением системы ограничении является многоугольник ABCDE (рис. 4.1). Необходимо среди точек этого многоугольника найти такую точку, в которой линейная функция принимает максимальное (или минимальное) значение.

Рассмотрим так называемую линию уровня линейной функции F, т.е. линию, вдоль которой эта функция принимает одно и тоже фиксированное значение a, т.е. F = a или . (4.1)

Уравнение линии уровня функции (4.1) есть уравнение прямой линии. При различных уровнях a линии уровня параллельны, так как их угловые коэффициенты определяются только соотношением между коэффициентами c ₁ и c ₂ и, следовательно, равны. Таким образом, линии уровня функции F это своеобразные «параллели», расположение обычно под углом к осям координат.

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

Теорема. Пусть имеются три линии уровня

(I)

(II)

(III)

причем линия II заключена между линиями I и III. Тогда или .

На штриховой линии (перпендикулярной к линиям уравнения на рис. 4.2 уровень является линейной функцией, а значит при смещении в одном из направлений возрастает, а в другую — убывает.

Рис 4.2

Для определения направления возрастания рекомендует изобразить две линии уровня и определить, на которой из них уровень больше. Например, одну из линий можно взять проходящей через начало координат (если линейная функция имеет вид без свободного члена, то это соответствует нулевому уровню). Другую линию можно провести произвольно, так, например, чтобы она проходила через множество решений системы ограничений. Далее, с определив направление возрастания линейной функции (обозначим его вектором ), найдем точку, в которой функция принимает максимальное или минимальное значения подобно тому как на карте находится самая северная или самая южная точка (на рис. 4.1 - точка С или А).

Пример 4.1. Решить геометрически задачу 1 в § 1.2: при ограничениях

Рис.4.3

Решение. Изобразим многоугольник решений (аналогично тому, как в примере 2.5) на рис. 4.3. Очевидно, что при F = 0 линия уровня 2 x ₁ + 3 х ₂ = 0 проходит через начало координат (строить ее не обязательно). Зададим, например, F = 6 и построим линию уровня 2 x ₁+ 3 x ₂ = 6. Ее расположение указывает на направление возрастания линейной функции (вектор ). Так как рассматриваемая задача на отыскание максимума, то оптимальное решение в угловой точке С, находящейся на пересечении прямых I и II, т.е. координаты точки С определяются решением системы уравнении

откуда , т.е. C (6;4).

Максимум (максимальное значение) линейной функции F _max= .

Итак, F _max= при оптимальном решении , т.е. максимальная прибыль в 24 руб. может быть достигнута при производстве 6 единиц продукции Р ₁и 4 единиц продукции Р ₂.

Пример 4.2. Решить геометрически задачу 2 в § 1.2:

F = 4x ₁ + 6 х ₂ min при ограничениях

Решение. Многоугольник решений представляет неограниченную многоугольную область (рис. 4.4). По расположен линии уровня, например, F = 12 или 4х ₁+ 6 x ₂ = 12, находим направление вектора (этот вектор указывает на направление возрастания линейной функции).

Рис. 4.4

Очевидно, что точка минимума — это точка "В входа" в многоугольник решений, при дальнейшем перемещении линии уровня в направлении вектора значения линейной функции увеличиваются. Находим координаты точки В (2;3), при этом F _min= .

Итак, F _min= при оптимальном решении x ₁=2, x ₂=3 т.е. минимальная стоимость рациона 26 руб., если в него включить 2 единицы корма 1 и 3 единицы корма II.

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

Пример 4.3. Решить геометрически следующие задачи:

а) б)

при ограничениях при ограничениях

Решение. а) Геометрическое решение задачи показано на рис. 4.5 а, из которого следует, что линия уровня с макси­мальным уровнем совпадает с граничной линией АВ много­угольника решений ABCD, т.е. с линией . Следовательно, на всем отрезке АВ линейная функция принимает одно и то же максимальное значение, равное . Это означает, что задача имеет бесконечно много оптимальных решений (их задают координаты точек отрезка АВ), среди которых базисных оптимальных решений два — соответственно в угловых точках А (3;5) и В(6;2). Точки отрезка АВ задаются уравнением х ₂ = 8 - х ₁ где . Итак, F _max= 24 при бесконечном множестве оптимальных решений .

Рис. 4.5

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

б) Геометрическое решение задачи показано на рис. 4.5,б, из которого следует, что если линию уровня перемещать в на­правлении убывания линейной функции (т.е. в направлении, противоположном вектору ), то она всегда будет пересекать многоугольник решений, следовательно, линейная функция неограниченно убывает. Итак, конечного оптимума линейной функции нет, т.е. .

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

Рассмотренный в этой главе геометрический метод решения задач линейного программирования обладает рядом достоинств. Он прост, нагляден, позволяет быстро и легко получить ответ.

Однако только геометрический метод решения никак не может удовлетворить ни математиков, ни экономистов. Воз­можны "технические" погрешности, которые неизбежно воз­никают при приближенном построении графиков. Другим важным недостатком геометрического метода является то, что многие величины, имеющие четкий экономический смысл (такие, как остатки ресурсов производства, избыток питатель­ных веществ и т.п.), не выявляются при геометрическом ре­шении задач. Но самое главное – геометрический метод не­приемлем для решения практических задач. Он применим только в случае, если число переменных в стандартной задаче равно двум. Поэтому необходимы аналитические методы, по­зволяющие решать задачи линейного программирования с лю­бым числом переменных и выявлять экономический смысл входящих в них величин.