ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Вспомним построение линейных зависимостей. Начнём с уравнений.

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

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

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

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

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

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

Построим каждое неравенство в системе координат х₁б х₂ в виде соответствующих полуплоскостей (рис.2.4).

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

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

Например, построим системы (рис.2.5):

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

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

С увеличением числа переменных выше трёх, геометрическая интерпретация невозможна, но система неравенств – ОДР в k-мерном пространстве.

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

Если мы хотим найти оптимальное решение, то должны принять ЦФ. Допустим, мы хотим, чтобы решение было оптимальным в смысле максимизации выпуска в целом. Тогда ЦФ: max L = x₁+x₂.

Положим L равной какому-либо числу (любому), например 2, и построим уравнение ЦФ: .

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

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

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

1. Найти вершины ОДР как точки пересечения ограничений.

2. Определить последовательно значения ЦФ в вершинах.

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

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