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

Вспомним построение линейных зависимостей. Начнем с уравнений. Линейное уравнение с двумя переменными может быть записано a ₁ x ₁ + a ₂ x ₂ = b. Чтобы построить это уравнение, найдем точки пересечения с осями координат. При x ₁ = 0 получим a ₂ x ₂ = b, откуда x ₂ = b / a ₂. При x ₂ = 0 будем иметь a ₁ x ₁ = b и x ₁ = b / a ₁ (рис. 2.1).

Рис. 2.1

Разделим теперь левую и правую части уравнения на b и перепишем уравнение, которое называют уравнением прямой в отрезках:

, или

, или

.

Такое представление уравнения удобно для построения прямой, так как величины a₁ и a₂ – это отрезки, отсекаемые прямой на тех осях, которые указаны в числителе. Например, 2 x ₁ + x ₂ = 2 или в форме уравнения в отрезках: то есть a₁ = 1, a₂ = 2.

Теперь о неравенствах. Если линейное уравнение с двумя переменными 2 x ₁ + x ₂ = 2 может быть представлено прямой на плоскости, то неравенство a ₁ x ₁ + a ₂ x ₂ £ b изображается как полуплоскость.

Так неравенство 2 x ₁ + x ₂ £ 2 представляет собой заштрихованную полуплоскость, координаты всех точек которой, то есть x ₁ и x ₂ удовлетворяют заданному равенству. Значит, эти значения составляют область допустимых решений (рис. 2.2).

Рис. 2.2

Рассмотрим построение системы линейных неравенств:

,

или в форме, аналогичной уравнениям в отрезках:

.

Построим каждое неравенство в системе координат x ₁, x ₂ в виде соответствующих полуплоскостей (рис. 2.3). Решение этой системы неравенств – координаты всех точек, принадлежащих области допустимых решений, то есть АВСДО. Так как в области допустимых решений бесчисленное множество точек, значит, рассматриваемая задача имеет бесчисленное множество допустимых решений.

Рис. 2.3

n Не любая система линейных неравенств имеет область допустимых решений, то есть допустимые решения.

Например, построим систему:

Рис. 2.4

Из рис. 2.4 видно, что нет таких точек, которые бы удовлетворяли всем неравенствам системы.

Итак, мы рассмотрели линейные уравнения и неравенства с двумя переменными. Если перейти к линейным зависимостямс тремя переменными, то тогда они будут описывать плоскость в трехмерном пространстве; линейное неравенство характеризует полупространство, а система линейных неравенств – многогранник как область допустимых решений в трехмерном пространстве.

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

При этом мерность пространства определяют так: если ограничения заданы неравенствами, то k = n, где n – число переменных; если ограничения в виде уравнений, то k = n – m, где m – число уравнений.

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

max L = x ₁ + x ₂.

Положим L, равной какому–либо числу (любому), например 2, и построим уравнение целевой функции:

Так как нам требуется найти оптимальное решение, при котором достигается max L, будем перемещать линию целевой функции в направлении увеличения L. Очевидно, что оптимальным решением будут координаты точки С, равные x ₁^*, x ₂^*. При этом L = L ^*.

n Отсюда можно сделать исключительно важный вывод: оптимальное решение – координаты вершины области допустимых решений.

Из этого вывода следует метод решения задач линейного программирования, который заключается в следующем:

Найти вершины области допустимых решений как точки пересечения ограничений.

Определить последовательно значения целевой функции в вершинах.

Вершина, в которой целевая функция приобретает оптимальное (max или min) значение, является оптимальной вершиной.

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